Online Publications
A Characterization of Multiclass Learnability
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff
ECCC: TR22-035
[Paper]
Locally Testable Codes with constant rate, distance, and locality
Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes
STOC 2022
[Paper] [Slides]
Near Coverings and Cosystolic Expansion -- an example of topological property testing
Irit Dinur, Roy Meshulam
Archiv der Mathematik 2022
[Pdf (arxiv)] [html (journal)]
Explicit SoS Lower Bounds from High-Dimensional Expanders
Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani
ITCS 2021: 38:1-38:16
[Pdf]
Agreement testing theorems on layered set systems
Yotam Dikstein, Irit Dinur
FOCS 2019
[Pdf]
"Testing Tensor Products" or
"Direct Sum Testing: the general case"Irit Dinur, Konstantin Golubev
RANDOM 2019
[Pdf]
From Local to Robust Testing via Agreement Testing
Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi
ITCS 2019
[Pdf]
Every Set in P Is Strongly Testable Under a Suitable Encoding
Irit Dinur, Oded Goldreich, Tom Gur
ITCS 2019
[Pdf]
List Decoding with Double Samplers
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta Shma
SODA 2019
[Pdf]
Boolean functions on high-dimensional expanders
Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha
RANDOM 2018
[Pdf]
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Irit Dinur, Pasin Manurangsi
ITCS 2018
[Pdf]
Agreement tests on graphs and hypergraphs
Irit Dinur, Yuval Filmus, Prahladh Harsha
appeared together with paper below in SODA 2019
[Pdf]
Low degree almost Boolean functions are sparse juntas
Irit Dinur, Yuval Filmus, Prahladh Harsha
appeared together with paper above in SODA 2019
[Pdf]
Exponentially Small Soundness for the Direct Product Z-test
Irit Dinur, Inbal Livni Navon
CCC 2017
[Pdf]
On Non-Optimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
STOC 2018
[Pdf]
High dimensional expanders imply agreement expanders
Irit Dinur, Tali Kaufman
FOCS 2017
[Pdf]
Cube vs. Cube Low Degree Test
Amey Bhangale, Irit Dinur, Inbal Livni Navon
ITCS 2017
[Pdf]
-
Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
STOC 2018
[Pdf]
-
Multiplayer parallel repetition for expander games
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen
ITCS 2017
[Pdf]
-
Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover
Irit Dinur
ECCC TR16-128
[Pdf]
-
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
Irit Dinur, Or Meir
CCC 2016
[Pdf]
-
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Irit Dinur, Prahladh Harsha, Guy Kindler
STOC 2015
[Pdf]
-
Derandomized Graph Product Results Using the Low Degree Long Code
Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma
STACS 2015
[Pdf]
-
The Computational Benefit of Correlated Instances
Irit Dinur, Shafi Goldwasser, and Huijia Lin
ITCS 2015
[Pdf]
-
Direct Sum Testing
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar
ITCS 2015
[Pdf]
-
Direct Product Testing
Irit Dinur, David Steurer
CCC 2014: 188-196
[Pdf]
-
A parallel repetition theorem for entangled projection games.
Irit Dinur, Thomas Vidick, David Steurer
CCC 2014: 197-208
[Pdf]
-
Analytical approach to parallel repetition
Irit Dinur, David Steurer
STOC 2014: 624-633.
[Pdf]
-
PCPs via low-degree long code and hardness for constrained hypergraph coloring
Irit Dinur, Venkatesan Guruswami
FOCS 2013
[Pdf]
-
Irit Dinur, Elazar Goldenberg
Clustering in the boolean hypercube in a list decoding regime.
ICALP 2013
[Pdf]
-
Covering CSPs.
Irit Dinur, Gillat Kol
CCC 2013
[Pdf]
-
Irit Dinur, Tali Kaufman
Locally testable codes and expanders.
Manuscript
[Pdf]
-
Dense locally testable codes cannot have constant rate and distance.
Irit Dinur, Tali Kaufman
RANDOM 2011
[Pdf]
-
Hardness of Finding Independent Sets in Almost 3-Colorable Graphs
Irit Dinur, Subhash Khot, Will Perkins, Muli Safra
FOCS 2010: 212-221
[Pdf]
-
The Structure of Winning Strategies in Parallel Repetition Games
Irit Dinur, Elazar Goldenberg
APPROX-RANDOM 2010
[Pdf]
-
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
Irit Dinur, Igor Shinkar
APPROX-RANDOM 2010
[Pdf]
-
Probabilisitically Checkable Proofs (survey and talk)
Irit Dinur
ICM 2010, plenary talk
[Slides] [Video of talk] [Accompanying paper (PDF)]
-
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]
-
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]
-
Guest complexity theory column: PCPs with small soundness error.
Irit Dinur
ACM SIGACT News, 2008.
[Pdf]
-
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]
-
Decodability of group homomorphisms beyond the Johnson bound.
Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan
STOC 2008, pp. 275-284.
[Pdf]
-
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]
-
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]
-
The PCP Theorem by gap amplification.
Irit Dinur
JACM, 54(3), 2007.
[Pdf] [BibTeX]
-
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]
-
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]
-
Robust local testability of tensor products of LDPC codes.
Irit Dinur, Madhu Sudan, Avi Wigderson
RANDOM 2006.
[Pdf] [BibTeX]
-
Proof of an intersection theorem via graph homomorphisms.
Irit Dinur, Ehud Friedgut
Electronic Journal of Combinatorics, 13(1), 2006.
[Pdf] [BibTeX]
-
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]
-
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]
-
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]
-
On the Hardness of Coloring 3-Uniform Hyper-Graphs.
Irit Dinur, Oded Regev, Clifford Smyth
Combinatorica, 25(1):519–535, 2005.
[Pdf] [BibTeX]
-
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]
-
On the Privacy of Statistical Databases.
Irit Dinur, Kobbi Nissim
Proc. of PODS, 2003.
[Pdf] [BibTeX]
-
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]
-
On the hardness of approximating label-cover.
Irit Dinur, Shmuel Safra
Information Processing Letters, 89(5):247-254, 2004.
[Pdf] [BibTeX]
-
Approximating SVPinfty to within almost polynomial factors is NP-hard.
Irit Dinur
Information Processing Letters, 89(5):247-254, 2004.
[Pdf] [BibTeX]
-
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]
-
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]