A parallel repetition theorem

Keywords

Citation, Repetition (rhetorical device), Computer science, World Wide Web, Philosophy

References

• The Parallel Repetition Conjecture for Trees is TrueOleg Verbitsky — 1995
• Hardness of approximationsSanjeev Arora, Carsten Lund — 1996
• The probabilistic communication complexity of set intersectionGeorg Schnitger, Bala Kalyanasundaram — 1987
• Entropy and Information TheoryRobert M. Gray — 1990
• Error reduction by parallel repetition-the state of the artUriel Feige — 1995
• Two-prover one-round proof systems: their power and their problems (extended abstract)Uriel Feige, László Lovász — 1992
• Towards the parallel repetition conjectureOleg Verbitsky — 1994
• Complexity-Theoretic Aspects of Interactive Proof SystemsLance Fortnow — 1989
• On bounded round multiprover interactive proof systemsJun-Xiong Cai, Anne Condon, R.J. Lipton — 1990
• Error Reduction by Parallel Repetition—A Negative ResultUriel Feige, Oleg Verbitsky — 1996
• The Probabilistic Communication Complexity of Set IntersectionBala Kalyanasundaram, Georg Schintger — 1992
• Testing of the long code and hardness for cliqueJohan Håstad — 1996
• Improved non-approximability resultsMihir Bellare, Madhu Sudan — 1994
• Direct product results and the GCD problem, in old and new communication modelsItzhak Parnafes, Ran Raz, Avi Wigderson — 1997
• On the Power of Multi-Prover Interactive ProtocolsLance Fortnow, John Rompel, Michael Sipser — 1994
• The complexity of approximating a nonlinear programMihir Bellare, Phillip Rogaway — 1995
• A one-round, two-prover, zero-knowledge protocol for NPDror Lapidot, Adi Shamir — 1991
• On the maximum density of 0-1 matrices with no forbidden rectanglesDavid Peleg — 1995
• On the hardness of approximating minimization problemsCarsten Lund, Mihalis Yannakakis — 1994
• On the Distributional Complexity of DisjointnessAlexander Razborov — 1990

Cited by

• Almost Optimal Bounds for Direct Product Threshold TheoremCharanjit S. Jutla — 2010
• Efficient Communication Using Partial InformationMark Braverman, Anup Rao — 2010
• A lower bound for approximating the grundy numberGuy Kortsarz — 2007
• Approximation for Dominating Set Problem with Measure FunctionsNing Chen, Jie Meng, Jiawei Rong — 2012
• On Vulnerability of Banking NetworksPiotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder — 2011
• The Approximability of Learning and Constraint Satisfaction ProblemsRyan O’Donnell, Yi Wu — 2010
• Improved approximation algorithms for Directed Steiner ForestMoran Feldman, Guy Kortsarz, Zeev Nutov — 2007
• Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphsMatthew Andrews, Julia Chuzhoy, Venkatesan Guruswami — 2010
• Local Constraints in Combinatorial OptimizationLuca Trevisan, Madhur Tulsiani — 2009
• The Hilbertian Tensor Norm and its Connection to Quantum Information TheoryDejan D. Dukaric — 2010
• P=BPP unless E has sub-exponential circuits: Derandomizing the XOR LemmaRussell Impagliazzo, Avi Wigderson — 2002
• Approximation Algorithms for Network Design and OrienteeringChandra Chekuri, Nitish Korula — 2010
• Minimizing DNF Formulas and AC0 Circuits Given a Truth TableEric Allender, Lisa Hellerstein, Paul McCabe — 2005
• Quantum Two Provers Interactive Proof SystemsBeverly Sackler, Alex Rapaport — 2007
• A Simple Biased Distribution for Dinur's ConstructionCharanjit S. Jutla — 2006
• Approximating np-hard problems efficient algorithms and their limitsVenkatesan Guruswami, Prasad Raghavendra — 2009
• Graph Partitioning and Semi-definite Programming HierarchiesVenkatesan Guruswami, Ali Kemal Sinop — 2011
• Locally Testable Codes Analogues to the Unique Games Conjecture Do Not ExistGillat Kol, Ran Raz — 2009
• Hardness amplification proofs require majorityRonen Shaltiel, Emanuele Viola — 2008
• Towards optimal lower bounds for clique and chromatic numberLars Engebretsen, Jonas Holmerin — 2003

Related papers

• Repetitions of a text: A text on repetitionKatja Čičigoj — 2018
• Recall it again, Sam. Practices of Repetition in the Security CouncilWouter Werner — 2017
• A Study of the Repetitive Narration in NovelsHU Ming-gu — 2005
• Stylistic Use of Repetition in English LiteratureDjabbarova Qizlarkhan — 2019
• The Repetition Phenomena in the DialogueZhang Yong-qun — 2004
• The Effect of Repetition on the Academic Performance of Primary School RepeatersDianna Kenny — 1985
• And Finally . . . Repetition, Repetition, RepetitionKim Tame — 2008