Online Publications

  1. List Decoding with Double Samplers

    Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta Shma

    ECCC TR18-136

    [Pdf]

  2. Boolean functions on high-dimensional expanders

    Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

    RANDOM 2018

    [Pdf]

  3. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

    Irit Dinur, Pasin Manurangsi

    ITCS 2018

    [Pdf]

  4. Agreement tests on graphs and hypergraphs

    Irit Dinur, Yuval Filmus, Prahladh Harsha

    ECCC TR17-181

    [Pdf]

  5. Low degree almost Boolean functions are sparse juntas

    Irit Dinur, Yuval Filmus, Prahladh Harsha

    ECCC TR17-180

    [Pdf]

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

    Irit Dinur, Inbal Livni Navon

    CCC 2017

    [Pdf]

  7. On Non-Optimally Expanding Sets in Grassmann Graphs

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

    STOC 2018

    [Pdf]

  8. High dimensional expanders imply agreement expanders

    Irit Dinur, Tali Kaufman

    FOCS 2017

    [Pdf]

  9. Cube vs. Cube Low Degree Test

    Amey Bhangale, Irit Dinur, Inbal Livni Navon

    ITCS 2017

    [Pdf]

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

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

    STOC 2018

    [Pdf]

  11. Multiplayer parallel repetition for expander games

    Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

    ITCS 2017

    [Pdf]

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

    Irit Dinur

    ECCC TR16-128

    [Pdf]

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

    Irit Dinur, Or Meir

    CCC 2016

    [Pdf]

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

    Irit Dinur, Prahladh Harsha, Guy Kindler

    STOC 2015

    [Pdf]

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

    Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

    STACS 2015

    [Pdf]

  16. The Computational Benefit of Correlated Instances

    Irit Dinur, Shafi Goldwasser, and Huijia Lin

    ITCS 2015

    [Pdf]

  17. Direct Sum Testing

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

    ITCS 2015

    [Pdf]

  18. Direct Product Testing

    Irit Dinur, David Steurer

    CCC 2014: 188-196

    [Pdf]

  19. A parallel repetition theorem for entangled projection games.

    Irit Dinur, Thomas Vidick, David Steurer

    CCC 2014: 197-208

    [Pdf]

  20. Analytical approach to parallel repetition

    Irit Dinur, David Steurer

    STOC 2014: 624-633.

    [Pdf]

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

    Irit Dinur, Venkatesan Guruswami

    FOCS 2013

    [Pdf]

  22. Irit Dinur, Elazar Goldenberg

    Clustering in the boolean hypercube in a list decoding regime.

    ICALP 2013

    [Pdf]

  23. Covering CSPs.

    Irit Dinur, Gillat Kol

    CCC 2013

    [Pdf]

  24. Irit Dinur, Tali Kaufman

    Locally testable codes and expanders.

    Manuscript

    [Pdf]

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

    Irit Dinur, Tali Kaufman

    RANDOM 2011

    [Pdf]

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

    Irit Dinur, Subhash Khot, Will Perkins, Muli Safra

    FOCS 2010: 212-221

    [Pdf]

  27. The Structure of Winning Strategies in Parallel Repetition Games

    Irit Dinur, Elazar Goldenberg

    APPROX-RANDOM 2010

    [Pdf]

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

    Irit Dinur, Igor Shinkar

    APPROX-RANDOM 2010

    [Pdf]

  29. Probabilisitically Checkable Proofs (survey and talk)

    Irit Dinur

    ICM 2010, plenary talk

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

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

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

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

    Irit Dinur

    ACM SIGACT News, 2008.

    [Pdf]

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

  34. Decodability of group homomorphisms beyond the Johnson bound.

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

    STOC 2008, pp. 275-284.

    [Pdf]

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

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

  37. The PCP Theorem by gap amplification.

    Irit Dinur

    JACM, 54(3), 2007.

    [Pdf] [BibTeX]

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

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

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

    Irit Dinur, Madhu Sudan, Avi Wigderson

    RANDOM 2006.

    [Pdf] [BibTeX]

  41. Proof of an intersection theorem via graph homomorphisms.

    Irit Dinur, Ehud Friedgut

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

    [Pdf] [BibTeX]

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

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

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

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

    Irit Dinur, Oded Regev, Clifford Smyth

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

    [Pdf] [BibTeX]

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

  47. On the Privacy of Statistical Databases.

    Irit Dinur, Kobbi Nissim

    Proc. of PODS, 2003.

    [Pdf] [BibTeX]

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

  49. On the hardness of approximating label-cover.

    Irit Dinur, Shmuel Safra

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

    [Pdf] [BibTeX]

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

    Irit Dinur

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

    [Pdf] [BibTeX]

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

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