Online Publications

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

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

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

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

  5. 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]

  6. 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]

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

  8. 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]

  9. 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]

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

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

  12. 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]

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

  14. 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.
    [Postscript] [BibTeX]

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

  16. 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).
    [Postscript] [BibTeX]

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

  18. 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]

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

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

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

  22. 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.
    [Postscript] [BibTeX]