Online Publications

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes

Irit Dinur, Ting-Chun Lin, Thomas Vidick

arXiv:2402.07476

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Yotam Dikstein, Irit Dinur, Alexander Lubotzky

ECCC: TR24-019

Swap cosystolic expansion

Yotam Dikstein, Irit Dinur

STOC 2024

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Yotam Dikstein, Irit Dinur

STOC 2024

The linear time encoding scheme fails to encode

Yotam Dikstein, Irit Dinur, Shiri Sivan

arxiv:2312.16125

New Codes on High Dimensional Expanders

Irit Dinur, Siqi Liu, Rachel Zhang

ECCC: TR23-127

Good Quantum LDPC Codes with Linear Time Decoders

Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick

STOC 2023: 905-918

Coboundary and cosystolic expansion without dependence on dimension or degree

Yotam Dikstein, Irit Dinur

ECCC: TR23-043

Bipartite unique-neighbour expanders via Ramanujan graphs

Ron Asherov, Irit Dinur

Invited to Entropy, Special Issue on Extremal and Additive Combinatorial Aspects in Information Theory

A Characterization of Multiclass Learnability

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff

FOCS 22

Locally Testable Codes with constant rate, distance, and locality

Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes

STOC 2022

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

Irit Dinur, Roy Meshulam

Archiv der Mathematik 2022

Explicit SoS Lower Bounds from High-Dimensional Expanders

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

ITCS 2021: 38:1-38:16

Agreement testing theorems on layered set systems

Yotam Dikstein, Irit Dinur

FOCS 2019

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

Irit Dinur, Konstantin Golubev

RANDOM 2019

From Local to Robust Testing via Agreement Testing

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

ITCS 2019

Every Set in P Is Strongly Testable Under a Suitable Encoding

Irit Dinur, Oded Goldreich, Tom Gur

ITCS 2019

List Decoding with Double Samplers

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

SODA 2019

Boolean functions on high-dimensional expanders

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

RANDOM 2018

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

Irit Dinur, Pasin Manurangsi

ITCS 2018

Agreement tests on graphs and hypergraphs

Irit Dinur, Yuval Filmus, Prahladh Harsha

appeared together with paper below in SODA 2019

Low degree almost Boolean functions are sparse juntas

Irit Dinur, Yuval Filmus, Prahladh Harsha

appeared together with paper above in SODA 2019

Exponentially Small Soundness for the Direct Product Z-test

Irit Dinur, Inbal Livni Navon

CCC 2017

On Non-Optimally Expanding Sets in Grassmann Graphs

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

STOC 2018

High dimensional expanders imply agreement expanders

Irit Dinur, Tali Kaufman

FOCS 2017

Cube vs. Cube Low Degree Test

Amey Bhangale, Irit Dinur, Inbal Livni Navon

ITCS 2017

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

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

STOC 2018

Multiplayer parallel repetition for expander games

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

ITCS 2017

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

Irit Dinur

ECCC TR16-128

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

Irit Dinur, Or Meir

CCC 2016

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Irit Dinur, Prahladh Harsha, Guy Kindler

STOC 2015

Derandomized Graph Product Results Using the Low Degree Long Code

Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

STACS 2015

The Computational Benefit of Correlated Instances

Irit Dinur, Shafi Goldwasser, and Huijia Lin

ITCS 2015

Direct Sum Testing

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

ITCS 2015

Direct Product Testing

Irit Dinur, David Steurer

CCC 2014: 188-196

A parallel repetition theorem for entangled projection games.

Irit Dinur, Thomas Vidick, David Steurer

CCC 2014: 197-208

Analytical approach to parallel repetition

Irit Dinur, David Steurer

STOC 2014: 624-633.

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

Irit Dinur, Venkatesan Guruswami

FOCS 2013

Irit Dinur, Elazar Goldenberg

Clustering in the boolean hypercube in a list decoding regime.

ICALP 2013

Covering CSPs.

Irit Dinur, Gillat Kol

CCC 2013

Irit Dinur, Tali Kaufman

Locally testable codes and expanders.

Manuscript

Dense locally testable codes cannot have constant rate and distance.

Irit Dinur, Tali Kaufman

RANDOM 2011

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs

Irit Dinur, Subhash Khot, Will Perkins, Muli Safra

FOCS 2010: 212-221

The Structure of Winning Strategies in Parallel Repetition Games

Irit Dinur, Elazar Goldenberg

APPROX-RANDOM 2010

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

Irit Dinur, Igor Shinkar

APPROX-RANDOM 2010

Probabilisitically Checkable Proofs (survey and talk)

Irit Dinur

ICM 2010, plenary talk

Derandomized Parallel Repetition of Structured PCPs

Irit Dinur, Or Meir

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

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.

Guest complexity theory column: PCPs with small soundness error.

Irit Dinur

ACM SIGACT News, 2008.

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.

Decodability of group homomorphisms beyond the Johnson bound.

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

STOC 2008, pp. 275-284.

Intersecting families are essentially contained in juntas.

Irit Dinur, Ehud Friedgut

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

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.

The PCP Theorem by gap amplification.

Irit Dinur

JACM, 54(3), 2007.

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.

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.

Robust local testability of tensor products of LDPC codes.

Irit Dinur, Madhu Sudan, Avi Wigderson

RANDOM 2006.

Proof of an intersection theorem via graph homomorphisms.

Irit Dinur, Ehud Friedgut

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

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.

Graph Products, Fourier Analysis and Spectral Techniques.

Noga Alon, Irit Dinur, Ehud Friedgut, Benny Sudakov

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

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.

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

Irit Dinur, Oded Regev, Clifford Smyth

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

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).

On the Privacy of Statistical Databases.

Irit Dinur, Kobbi Nissim

Proc. of PODS, 2003.

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").

On the hardness of approximating label-cover.

Irit Dinur, Shmuel Safra

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

Approximating SVP_infty to within almost polynomial factors is NP-hard.

Irit Dinur

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

An Improved Lower Bound for Approximating-CVP.

Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra

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

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.