Online Publications

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

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

  3. Irit Dinur, Elazar Goldenberg
    The Structure of Winning Strategies in Parallel Repetition Games
    APPROX-RANDOM 2010
    [Pdf]

  4. Irit Dinur, Igor Shinkar
    On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
    APPROX-RANDOM 2010
    [Pdf]

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

  6. Irit Dinur, Or Meir
    Derandomized Parallel Repetition of Structured PCPs
    Submitted, http://arxiv.org/abs/1002.1606v1.
    [Pdf]

  7. Irit Dinur, Prahladh Harsha
    Composition of low-error 2-query PCPs using decodable PCPs
    FOCS 2009.
    [Pdf]

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

  9. Irit Dinur and Elazar Goldenberg
    Locally testing direct products in the low error range.
    FOCS 2008.
    [Pdf]

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

  11. Irit Dinur, Ehud Friedgut
    Intersecting families are essentially contained in juntas.
    Combinatorics, Probability and Computing, volume 18, issue 1-2, pp. 107-122, 2008.
    [Pdf] [BibTeX]

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

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

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

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

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

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

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

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

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

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

  22. Irit Dinur, Venkatesan Guruswami, Subhash Khot
    Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon).
    ECCC TR02-027, Results in this paper have been subsumed by (9).
    [Pdf] [BibTeX]

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

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

  25. Irit Dinur, Shmuel Safra
    On the hardness of approximating label-cover.
    Information Processing Letters, 89(5):247-254, 2004.
    [Pdf] [BibTeX]

  26. Irit Dinur
    Approximating SVPinfty to within almost polynomial factors is NP-hard.
    Information Processing Letters, 89(5):247-254, 2004.
    [Pdf] [BibTeX]

  27. Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra
    An Improved Lower Bound for Approximating-CVP.
    Combinatorica, 23(2):205-243, 2003.
    [Pdf] [Conference version Postscript] [BibTeX]

  28. Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
    PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
    Proc. of 31st STOC, 1999.
    [Pdf] [BibTeX]