Online Publications

  1. Near Coverings and Cosystolic Expansion -- an example of topological property testing

    Irit Dinur, Roy Meshulam

    arxiv:1909.08507

    [Pdf]

  2. Agreement testing theorems on layered set systems

    Yotam Dikstein, Irit Dinur

    FOCS 2019

    [Pdf]

  3. "Testing Tensor Products" or
    "Direct Sum Testing: the general case"

    Irit Dinur, Konstantin Golubev

    RANDOM 2019

    [Pdf]

  4. From Local to Robust Testing via Agreement Testing

    Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi

    ITCS 2019

    [Pdf]

  5. Every Set in P Is Strongly Testable Under a Suitable Encoding

    Irit Dinur, Oded Goldreich, Tom Gur

    ITCS 2019

    [Pdf]

  6. List Decoding with Double Samplers

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

    SODA 2019

    [Pdf]

  7. Boolean functions on high-dimensional expanders

    Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

    RANDOM 2018

    [Pdf]

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

    Irit Dinur, Pasin Manurangsi

    ITCS 2018

    [Pdf]

  9. Agreement tests on graphs and hypergraphs

    Irit Dinur, Yuval Filmus, Prahladh Harsha

    appeared together with paper below in SODA 2019

    [Pdf]

  10. Low degree almost Boolean functions are sparse juntas

    Irit Dinur, Yuval Filmus, Prahladh Harsha

    appeared together with paper above in SODA 2019

    [Pdf]

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

    Irit Dinur, Inbal Livni Navon

    CCC 2017

    [Pdf]

  12. On Non-Optimally Expanding Sets in Grassmann Graphs

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

    STOC 2018

    [Pdf]

  13. High dimensional expanders imply agreement expanders

    Irit Dinur, Tali Kaufman

    FOCS 2017

    [Pdf]

  14. Cube vs. Cube Low Degree Test

    Amey Bhangale, Irit Dinur, Inbal Livni Navon

    ITCS 2017

    [Pdf]

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

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

    STOC 2018

    [Pdf]

  16. Multiplayer parallel repetition for expander games

    Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

    ITCS 2017

    [Pdf]

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

    Irit Dinur

    ECCC TR16-128

    [Pdf]

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

    Irit Dinur, Or Meir

    CCC 2016

    [Pdf]

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

    Irit Dinur, Prahladh Harsha, Guy Kindler

    STOC 2015

    [Pdf]

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

    Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

    STACS 2015

    [Pdf]

  21. The Computational Benefit of Correlated Instances

    Irit Dinur, Shafi Goldwasser, and Huijia Lin

    ITCS 2015

    [Pdf]

  22. Direct Sum Testing

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

    ITCS 2015

    [Pdf]

  23. Direct Product Testing

    Irit Dinur, David Steurer

    CCC 2014: 188-196

    [Pdf]

  24. A parallel repetition theorem for entangled projection games.

    Irit Dinur, Thomas Vidick, David Steurer

    CCC 2014: 197-208

    [Pdf]

  25. Analytical approach to parallel repetition

    Irit Dinur, David Steurer

    STOC 2014: 624-633.

    [Pdf]

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

    Irit Dinur, Venkatesan Guruswami

    FOCS 2013

    [Pdf]

  27. Irit Dinur, Elazar Goldenberg

    Clustering in the boolean hypercube in a list decoding regime.

    ICALP 2013

    [Pdf]

  28. Covering CSPs.

    Irit Dinur, Gillat Kol

    CCC 2013

    [Pdf]

  29. Irit Dinur, Tali Kaufman

    Locally testable codes and expanders.

    Manuscript

    [Pdf]

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

    Irit Dinur, Tali Kaufman

    RANDOM 2011

    [Pdf]

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

    Irit Dinur, Subhash Khot, Will Perkins, Muli Safra

    FOCS 2010: 212-221

    [Pdf]

  32. The Structure of Winning Strategies in Parallel Repetition Games

    Irit Dinur, Elazar Goldenberg

    APPROX-RANDOM 2010

    [Pdf]

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

    Irit Dinur, Igor Shinkar

    APPROX-RANDOM 2010

    [Pdf]

  34. Probabilisitically Checkable Proofs (survey and talk)

    Irit Dinur

    ICM 2010, plenary talk

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

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

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

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

    Irit Dinur

    ACM SIGACT News, 2008.

    [Pdf]

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

  39. Decodability of group homomorphisms beyond the Johnson bound.

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

    STOC 2008, pp. 275-284.

    [Pdf]

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

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

  42. The PCP Theorem by gap amplification.

    Irit Dinur

    JACM, 54(3), 2007.

    [Pdf] [BibTeX]

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

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

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

    Irit Dinur, Madhu Sudan, Avi Wigderson

    RANDOM 2006.

    [Pdf] [BibTeX]

  46. Proof of an intersection theorem via graph homomorphisms.

    Irit Dinur, Ehud Friedgut

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

    [Pdf] [BibTeX]

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

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

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

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

    Irit Dinur, Oded Regev, Clifford Smyth

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

    [Pdf] [BibTeX]

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

  52. On the Privacy of Statistical Databases.

    Irit Dinur, Kobbi Nissim

    Proc. of PODS, 2003.

    [Pdf] [BibTeX]

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

  54. On the hardness of approximating label-cover.

    Irit Dinur, Shmuel Safra

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

    [Pdf] [BibTeX]

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

    Irit Dinur

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

    [Pdf] [BibTeX]

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

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