Online Publications

  1. Exponentially Small Soundness for the Direct Product Z-test

    Irit Dinur, Inbal Livni Navon

    CCC 2017

    [Pdf]

  2. On Non-Optimally Expanding Sets in Grassmann Graphs

    Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

    ECCC TR17-094

    [Pdf]

  3. High dimensional expanders imply agreement expanders

    Irit Dinur, Tali Kaufman

    ECCC TR17-089 (to appear in FOCS 2017)

    [Pdf]

  4. Cube vs. Cube Low Degree Test

    Amey Bhangale, Irit Dinur, Inbal Livni Navon

    ITCS 2017

    [Pdf]

  5. Towards a Proof of the 2-to-1 Games Conjecture?

    Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

    ECCC TR16-198

    [Pdf]

  6. Multiplayer parallel repetition for expander games

    Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

    ITCS 2017

    [Pdf]

  7. Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover

    Irit Dinur

    ECCC TR16-128

    [Pdf]

  8. Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

    Irit Dinur, Or Meir

    CCC 2016

    [Pdf]

  9. Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

    Irit Dinur, Prahladh Harsha, Guy Kindler

    STOC 2015

    [Pdf]

  10. Derandomized Graph Product Results Using the Low Degree Long Code

    Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

    STACS 2015

    [Pdf]

  11. The Computational Benefit of Correlated Instances

    Irit Dinur, Shafi Goldwasser, and Huijia Lin

    ITCS 2015

    [Pdf]

  12. Direct Sum Testing

    Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar

    ITCS 2015

    [Pdf]

  13. Direct Product Testing

    Irit Dinur, David Steurer

    CCC 2014: 188-196

    [Pdf]

  14. A parallel repetition theorem for entangled projection games.

    Irit Dinur, Thomas Vidick, David Steurer

    CCC 2014: 197-208

    [Pdf]

  15. Analytical approach to parallel repetition

    Irit Dinur, David Steurer

    STOC 2014: 624-633.

    [Pdf]

  16. PCPs via low-degree long code and hardness for constrained hypergraph coloring

    Irit Dinur, Venkatesan Guruswami

    FOCS 2013

    [Pdf]

  17. Irit Dinur, Elazar Goldenberg

    Clustering in the boolean hypercube in a list decoding regime.

    ICALP 2013

    [Pdf]

  18. Covering CSPs.

    Irit Dinur, Gillat Kol

    CCC 2013

    [Pdf]

  19. Irit Dinur, Tali Kaufman

    Locally testable codes and expanders.

    Manuscript

    [Pdf]

  20. Dense locally testable codes cannot have constant rate and distance.

    Irit Dinur, Tali Kaufman

    RANDOM 2011

    [Pdf]

  21. Hardness of Finding Independent Sets in Almost 3-Colorable Graphs

    Irit Dinur, Subhash Khot, Will Perkins, Muli Safra

    FOCS 2010: 212-221

    [Pdf]

  22. The Structure of Winning Strategies in Parallel Repetition Games

    Irit Dinur, Elazar Goldenberg

    APPROX-RANDOM 2010

    [Pdf]

  23. On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors

    Irit Dinur, Igor Shinkar

    APPROX-RANDOM 2010

    [Pdf]

  24. Probabilisitically Checkable Proofs (survey and talk)

    Irit Dinur

    ICM 2010, plenary talk

    [Slides] [Video of talk] [Accompanying paper (PDF)]

  25. Derandomized Parallel Repetition of Structured PCPs

    Irit Dinur, Or Meir

    Special issue of CCC'10 published in Computational Complexity 20(2): 207-327 (2011)

    [Pdf]

  26. Composition of low-error 2-query PCPs using decodable PCPs

    Irit Dinur, Prahladh Harsha

    SIAM J. Comput. 42(6): 2452-2486 (2013), preliminary version appeared in FOCS 2009.

    [Pdf]

  27. Guest complexity theory column: PCPs with small soundness error.

    Irit Dinur

    ACM SIGACT News, 2008.

    [Pdf]

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

  29. Decodability of group homomorphisms beyond the Johnson bound.

    Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan

    STOC 2008, pp. 275-284.

    [Pdf]

  30. Intersecting families are essentially contained in juntas.

    Irit Dinur, Ehud Friedgut

    Combinatorics, Probability and Computing, volume 18, issue 1-2, pp. 107-122, 2008.

    [Pdf] [BibTeX]

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

  32. The PCP Theorem by gap amplification.

    Irit Dinur

    JACM, 54(3), 2007.

    [Pdf] [BibTeX]

  33. Conditional Hardness for Approximate Coloring.

    Irit Dinur, Elchanan Mossel, Oded Regev

    SIAM Journal on Computing, 39(3):843-873, 2009. Prelim version in STOC 2006.

    [Pdf] [BibTeX]

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

  35. Robust local testability of tensor products of LDPC codes.

    Irit Dinur, Madhu Sudan, Avi Wigderson

    RANDOM 2006.

    [Pdf] [BibTeX]

  36. Proof of an intersection theorem via graph homomorphisms.

    Irit Dinur, Ehud Friedgut

    Electronic Journal of Combinatorics, 13(1), 2006.

    [Pdf] [BibTeX]

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

  38. Graph Products, Fourier Analysis and Spectral Techniques.

    Noga Alon, Irit Dinur, Ehud Friedgut, Benny Sudakov

    GAFA, vol. 14, no. 5, pp. 913-940 (2004).

    [Pdf] [BibTeX]

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

  40. On the Hardness of Coloring 3-Uniform Hyper-Graphs.

    Irit Dinur, Oded Regev, Clifford Smyth

    Combinatorica, 25(1):519–535, 2005.

    [Pdf] [BibTeX]

  41. Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon).

    Irit Dinur, Venkatesan Guruswami, Subhash Khot

    ECCC TR02-027, Results in this paper have been subsumed by (9).

    [Pdf] [BibTeX]

  42. On the Privacy of Statistical Databases.

    Irit Dinur, Kobbi Nissim

    Proc. of PODS, 2003.

    [Pdf] [BibTeX]

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

  44. On the hardness of approximating label-cover.

    Irit Dinur, Shmuel Safra

    Information Processing Letters, 89(5):247-254, 2004.

    [Pdf] [BibTeX]

  45. Approximating SVPinfty to within almost polynomial factors is NP-hard.

    Irit Dinur

    Information Processing Letters, 89(5):247-254, 2004.

    [Pdf] [BibTeX]

  46. An Improved Lower Bound for Approximating-CVP.

    Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra

    Combinatorica, 23(2):205-243, 2003.

    [Pdf] [Conference version Postscript] [BibTeX]

  47. PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.

    Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

    Proc. of 31st STOC, 1999.

    [Pdf] [BibTeX]