Online Publications
Exponentially Small Soundness for the Direct Product Ztest
Irit Dinur, Inbal Livni Navon
CCC 2017
[Pdf]
On NonOptimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
ECCC TR17094
[Pdf]
High dimensional expanders imply agreement expanders
Irit Dinur, Tali Kaufman
ECCC TR17089 (to appear in FOCS 2017)
[Pdf]
Cube vs. Cube Low Degree Test
Amey Bhangale, Irit Dinur, Inbal Livni Navon
ITCS 2017
[Pdf]

Towards a Proof of the 2to1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
ECCC TR16198
[Pdf]

Multiplayer parallel repetition for expander games
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen
ITCS 2017
[Pdf]

Mildly exponential reduction from gap3SAT to polynomialgap labelcover
Irit Dinur
ECCC TR16128
[Pdf]

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
Irit Dinur, Or Meir
CCC 2016
[Pdf]

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Irit Dinur, Prahladh Harsha, Guy Kindler
STOC 2015
[Pdf]

Derandomized Graph Product Results Using the Low Degree Long Code
Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma
STACS 2015
[Pdf]

The Computational Benefit of Correlated Instances
Irit Dinur, Shafi Goldwasser, and Huijia Lin
ITCS 2015
[Pdf]

Direct Sum Testing
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar
ITCS 2015
[Pdf]

Direct Product Testing
Irit Dinur, David Steurer
CCC 2014: 188196
[Pdf]

A parallel repetition theorem for entangled projection games.
Irit Dinur, Thomas Vidick, David Steurer
CCC 2014: 197208
[Pdf]

Analytical approach to parallel repetition
Irit Dinur, David Steurer
STOC 2014: 624633.
[Pdf]

PCPs via lowdegree long code and hardness for constrained hypergraph coloring
Irit Dinur, Venkatesan Guruswami
FOCS 2013
[Pdf]

Irit Dinur, Elazar Goldenberg
Clustering in the boolean hypercube in a list decoding regime.
ICALP 2013
[Pdf]

Covering CSPs.
Irit Dinur, Gillat Kol
CCC 2013
[Pdf]

Irit Dinur, Tali Kaufman
Locally testable codes and expanders.
Manuscript
[Pdf]

Dense locally testable codes cannot have constant rate and distance.
Irit Dinur, Tali Kaufman
RANDOM 2011
[Pdf]

Hardness of Finding Independent Sets in Almost 3Colorable Graphs
Irit Dinur, Subhash Khot, Will Perkins, Muli Safra
FOCS 2010: 212221
[Pdf]

The Structure of Winning Strategies in Parallel Repetition Games
Irit Dinur, Elazar Goldenberg
APPROXRANDOM 2010
[Pdf]

On the Conditional Hardness of Coloring a 4Colorable Graph with SuperConstant Number of Colors
Irit Dinur, Igor Shinkar
APPROXRANDOM 2010
[Pdf]

Probabilisitically Checkable Proofs (survey and talk)
Irit Dinur
ICM 2010, plenary talk
[Slides] [Video of talk] [Accompanying paper (PDF)]

Derandomized Parallel Repetition of Structured PCPs
Irit Dinur, Or Meir
Special issue of CCC'10 published in Computational Complexity 20(2): 207327 (2011)
[Pdf]

Composition of lowerror 2query PCPs using decodable PCPs
Irit Dinur, Prahladh Harsha
SIAM J. Comput. 42(6): 24522486 (2013), preliminary version appeared in FOCS 2009.
[Pdf]

Guest complexity theory column: PCPs with small soundness error.
Irit Dinur
ACM SIGACT News, 2008.
[Pdf]

Locally testing direct products in the high error range.
(earlier title: "Locally testing direct products in the low error range")
Irit Dinur and Elazar Goldenberg
FOCS 2008.
[Pdf]

Decodability of group homomorphisms beyond the Johnson bound.
Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan
STOC 2008, pp. 275284.
[Pdf]

Intersecting families are essentially contained in juntas.
Irit Dinur, Ehud Friedgut
Combinatorics, Probability and Computing, volume 18, issue 12, pp. 107122, 2008.
[Pdf] [BibTeX]

Independent Sets in Graph Powers are Almost Contained in Juntas
Irit Dinur, Ehud Friedgut, Oded Regev
Geometric and Functional Analysis (GAFA), 18(1):77–97, 2008.
[Pdf] [BibTeX]

The PCP Theorem by gap amplification.
Irit Dinur
JACM, 54(3), 2007.
[Pdf] [BibTeX]

Conditional Hardness for Approximate Coloring.
Irit Dinur, Elchanan Mossel, Oded Regev
SIAM Journal on Computing, 39(3):843873, 2009. Prelim version in STOC 2006.
[Pdf] [BibTeX]

On the Fourier tails of bounded functions over the discrete cube.
Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell
Israel Journal of Mathematics, 160(1):389–412, 2007.
[Pdf] [BibTeX]

Robust local testability of tensor products of LDPC codes.
Irit Dinur, Madhu Sudan, Avi Wigderson
RANDOM 2006.
[Pdf] [BibTeX]

Proof of an intersection theorem via graph homomorphisms.
Irit Dinur, Ehud Friedgut
Electronic Journal of Combinatorics, 13(1), 2006.
[Pdf] [BibTeX]

Assignment Testers: Towards a combinatorial proof of the PCP theorem.
Irit Dinur, Omer Reingold
SIAM J. Computing, 36(4):975–1024, 2006. Special Issue on Randomness and Complexity.
[Pdf] [BibTeX]

Graph Products, Fourier Analysis and Spectral Techniques.
Noga Alon, Irit Dinur, Ehud Friedgut, Benny Sudakov
GAFA, vol. 14, no. 5, pp. 913940 (2004).
[Pdf] [BibTeX]

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
SIAM Journal on Computing, 34(5):1129–1146, 2005.
[Pdf] [BibTeX]

On the Hardness of Coloring 3Uniform HyperGraphs.
Irit Dinur, Oded Regev, Clifford Smyth
Combinatorica, 25(1):519–535, 2005.
[Pdf] [BibTeX]

Vertex Cover on kUniform Hypergraphs is Hard to Approximate within Factor (k3epsilon).
Irit Dinur, Venkatesan Guruswami, Subhash Khot
ECCC TR02027, Results in this paper have been subsumed by (9).
[Pdf] [BibTeX]

On the Privacy of Statistical Databases.
Irit Dinur, Kobbi Nissim
Proc. of PODS, 2003.
[Pdf] [BibTeX]

Irit Dinur, Shmuel Safra
On the Hardness of Approximating Minimum VertexCover.
Annals of Mathematics, 162(1):439485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").
[Pdf] [BibTeX]

On the hardness of approximating labelcover.
Irit Dinur, Shmuel Safra
Information Processing Letters, 89(5):247254, 2004.
[Pdf] [BibTeX]

Approximating SVP_{infty} to within almost polynomial factors is NPhard.
Irit Dinur
Information Processing Letters, 89(5):247254, 2004.
[Pdf] [BibTeX]

An Improved Lower Bound for ApproximatingCVP.
Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra
Combinatorica, 23(2):205243, 2003.
[Pdf] [Conference version Postscript] [BibTeX]

PCP Characterizations of NP: Towards a PolynomiallySmall ErrorProbability.
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
Proc. of 31st STOC, 1999.
[Pdf] [BibTeX]