Irit Dinur

According to our database, Irit Dinur authored at least 87 papers between 1998 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Bipartite Unique Neighbour Expanders via Ramanujan Graphs.

Ron Asherov, Irit Dinur

Entropy, April, 2024

Sparse juntas on the biased hypercube.

Irit Dinur, Yuval Filmus, Prahladh Harsha

TheoretiCS, 2024

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs.

Yotam Dikstein, Irit Dinur, Alexander Lubotzky

Electron. Colloquium Comput. Complex., 2024

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

Irit Dinur, Ting-Chun Lin, Thomas Vidick

CoRR, 2024

Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers.

Yotam Dikstein, Irit Dinur

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes.

Irit Dinur, Ting-Chun Lin, Thomas Vidick

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

New Codes on High Dimensional Expanders.

Irit Dinur, Siqi Liu, Rachel Yun Zhang

Electron. Colloquium Comput. Complex., 2023

Swap cosystolic expansion.

Yotam Dikstein, Irit Dinur

Electron. Colloquium Comput. Complex., 2023

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

Yotam Dikstein, Irit Dinur

Electron. Colloquium Comput. Complex., 2023

Coboundary and cosystolic expansion without dependence on dimension or degree.

Yotam Dikstein, Irit Dinur

Electron. Colloquium Comput. Complex., 2023

The linear time encoding scheme fails to encode.

Yotam Dikstein, Irit Dinur, Shiri Sivan

CoRR, 2023

Good Quantum LDPC Codes with Linear Time Decoders.

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

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

From Local to Robust Testing via Agreement Testing.

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

Adv. Math. Commun., 2022

A Characterization of Multiclass Learnability.

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

Electron. Colloquium Comput. Complex., 2022

Good Locally Testable Codes.

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

CoRR, 2022

Expanders in Higher Dimensions (Invited Talk).

Irit Dinur

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

List-Decoding with Double Samplers.

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

SIAM J. Comput., 2021

Locally Testable Codes with constant rate, distance, and locality.

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

Electron. Colloquium Comput. Complex., 2021

Explicit SoS Lower Bounds from High-Dimensional Expanders.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Explicit and structured sum of squares lower bounds from high dimensional expanders.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2020

Locally testable codes via high-dimensional expanders.

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2020

2019

Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).

Irit Dinur, Or Meir, Swastik Kopparty

SIAM J. Comput., 2019

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

Irit Dinur, Roy Meshulam

Electron. Colloquium Comput. Complex., 2019

Direct sum testing - the general case.

Irit Dinur, Konstantin Golubev

Electron. Colloquium Comput. Complex., 2019

Agreement testing theorems on layered set systems.

Yotam Dikstein, Irit Dinur

Electron. Colloquium Comput. Complex., 2019

Testing tensor products.

Irit Dinur, Konstantin Golubev

CoRR, 2019

Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract].

Irit Dinur, Yuval Filmus, Prahladh Harsha

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

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

Irit Dinur, Pasin Manurangsi

Electron. Colloquium Comput. Complex., 2018

From Local to Robust Testing via Agreement Testing.

Irit Dinur, Tali Kaufman, Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2018

Every set in P is strongly testable under a suitable encoding.

Irit Dinur, Oded Goldreich, Tom Gur

Electron. Colloquium Comput. Complex., 2018

Boolean function analysis on high-dimensional expanders.

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2018

Boolean functions on high-dimensional expanders.

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

CoRR, 2018

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

Irit Dinur, Or Meir

Comput. Complex., 2018

2017

Direct Sum Testing.

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

SIAM J. Comput., 2017

Exponentially Small Soundness for the Direct Product Z-test.

Irit Dinur, Inbal Livni Navon

Electron. Colloquium Comput. Complex., 2017

On Non-Optimally Expanding Sets in Grassmann Graphs.

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

Electron. Colloquium Comput. Complex., 2017

High dimensional expanders imply agreement expanders.

Irit Dinur, Tali Kaufman

Electron. Colloquium Comput. Complex., 2017

Agreement tests on graphs and hypergraphs.

Irit Dinur, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2017

Low degree almost Boolean functions are sparse juntas.

Irit Dinur, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2017

Multiplayer Parallel Repetition for Expanding Games.

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

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

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

Electron. Colloquium Comput. Complex., 2016

Multiplayer parallel repetition for expander games.

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Electron. Colloquium Comput. Complex., 2016

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

Irit Dinur

Electron. Colloquium Comput. Complex., 2016

Cube vs. Cube Low Degree Test.

Amey Bhangale, Irit Dinur, Inbal Livni Navon

Electron. Colloquium Comput. Complex., 2016

2015

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.

Irit Dinur, Prahladh Harsha, Guy Kindler

Electron. Colloquium Comput. Complex., 2015

A parallel repetition theorem for entangled projection games.

Irit Dinur, David Steurer, Thomas Vidick

Comput. Complex., 2015

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

Irit Dinur, Prahladh Harsha, Guy Kindler

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Derandomized Graph Product Results Using the Low Degree Long Code.

Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

2014

The Computational Benefit of Correlated Instances.

Irit Dinur, Shafi Goldwasser, Huijia Lin

Electron. Colloquium Comput. Complex., 2014

Analytical approach to parallel repetition.

Irit Dinur, David Steurer

Proceedings of the Symposium on Theory of Computing, 2014

2013

Composition of Low-Error 2-Query PCPs Using Decodable PCPs.

Irit Dinur, Prahladh Harsha

SIAM J. Comput., 2013

Direct Product Testing.

Irit Dinur, David Steurer

Electron. Colloquium Comput. Complex., 2013

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

Irit Dinur, Igor Shinkar

Electron. Colloquium Comput. Complex., 2013

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

Irit Dinur, Venkatesan Guruswami

Electron. Colloquium Comput. Complex., 2013

Clustering in the Boolean Hypercube in a List Decoding Regime.

Irit Dinur, Elazar Goldenberg

Electron. Colloquium Comput. Complex., 2013

Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword.

Boaz Barak, Irit Dinur

Comput. Complex., 2013

2012

Covering CSPs.

Irit Dinur, Gillat Kol

Electron. Colloquium Comput. Complex., 2012

2011

Dense locally testable codes cannot have constant rate and distance.

Irit Dinur, Tali Kaufman

Electron. Colloquium Comput. Complex., 2011

Derandomized Parallel Repetition via Structured PCPs.

Irit Dinur, Or Meir

Comput. Complex., 2011

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

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

Comput. Complex., 2011

2010

Composition of Low-Error 2-Query PCPs Using Decodable PCPs.

Irit Dinur, Prahladh Harsha

Proceedings of the Property Testing - Current Research and Surveys, 2010

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

Irit Dinur, Subhash Khot, Will Perkins, Muli Safra

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Derandomized Parallel Repetition of Structured PCPs.

Irit Dinur, Or Meir

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

The Structure of Winning Strategies in Parallel Repetition Games.

Irit Dinur, Elazar Goldenberg

Proceedings of the Approximation, 2010

2009

Conditional Hardness for Approximate Coloring.

Irit Dinur, Elchanan Mossel, Oded Regev

SIAM J. Comput., 2009

Intersecting Families are Essentially Contained in Juntas.

Irit Dinur, Ehud Friedgut

Comb. Probab. Comput., 2009

2008

PCPs with small soundness error.

Irit Dinur

SIGACT News, 2008

Special Issue on Foundations of Computer Science.

Irit Dinur, Éva Tardos

SIAM J. Comput., 2008

Decodability of Group Homomorphisms beyond the Johnson Bound.

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Electron. Colloquium Comput. Complex., 2008

Locally Testing Direct Product in the Low Error Range.

Irit Dinur, Elazar Goldenberg

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2006

Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem.

Irit Dinur, Omer Reingold

SIAM J. Comput., 2006

Robust Local Testability of Tensor Products of LDPC Codes.

Irit Dinur, Madhu Sudan, Avi Wigderson

Electron. Colloquium Comput. Complex., 2006

Proof of an Intersection Theorem via Graph Homomorphisms.

Irit Dinur, Ehud Friedgut

Electron. J. Comb., 2006

On the fourier tails of bounded functions over the discrete cube.

Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev

SIAM J. Comput., 2005

The PCP theorem by gap amplification

Irit Dinur

Electron. Colloquium Comput. Complex., 2005

The Hardness of 3-Uniform Hypergraph Coloring.

Irit Dinur, Oded Regev, Clifford D. Smyth

Comb., 2005

2004

On the hardness of approximating label-cover.

Irit Dinur, Shmuel Safra

Inf. Process. Lett., 2004

2003

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.

Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra

Comb., 2003

Revealing information while preserving privacy.

Irit Dinur, Kobbi Nissim

Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

2002

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

Irit Dinur

Theor. Comput. Sci., 2002

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

Irit Dinur, Venkatesan Guruswami, Subhash Khot

Electron. Colloquium Comput. Complex., 2002

2001

The Importance of Being Biased

Irit Dinur, Shmuel Safra

Electron. Colloquium Comput. Complex., 2001

1999

Approximating SVP_infty to within Almost-Polynomial Factors is NP-hard

Irit Dinur

Electron. Colloquium Comput. Complex., 1999

1998

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

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

Electron. Colloquium Comput. Complex., 1998

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

Irit Dinur, Guy Kindler, Shmuel Safra

Electron. Colloquium Comput. Complex., 1998

Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.

Irit Dinur, Guy Kindler, Shmuel Safra

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998