Irit Dinur

According to our database1, Irit Dinur authored at least 71 papers between 1998 and 2021.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Explicit SoS Lower Bounds from High-Dimensional Expanders.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020
Explicit and structured sum of squares lower bounds from high dimensional expanders.
Electron. Colloquium Comput. Complex., 2020

Locally testable codes via high-dimensional expanders.
Electron. Colloquium Comput. Complex., 2020

2019
Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
SIAM J. Comput., 2019

Near Coverings and Cosystolic Expansion - an example of topological property testing.
Electron. Colloquium Comput. Complex., 2019

Direct sum testing - the general case.
Electron. Colloquium Comput. Complex., 2019

Agreement testing theorems on layered set systems.
Electron. Colloquium Comput. Complex., 2019

Testing tensor products.
CoRR, 2019

Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract].
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

From Local to Robust Testing via Agreement Testing.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network.
Electron. Colloquium Comput. Complex., 2018

From Local to Robust Testing via Agreement Testing.
Electron. Colloquium Comput. Complex., 2018

List Decoding with Double Samplers.
Electron. Colloquium Comput. Complex., 2018

Every set in P is strongly testable under a suitable encoding.
Electron. Colloquium Comput. Complex., 2018

Boolean function analysis on high-dimensional expanders.
Electron. Colloquium Comput. Complex., 2018

Boolean functions on high-dimensional expanders.
CoRR, 2018

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity.
Comput. Complex., 2018

2017
Exponentially Small Soundness for the Direct Product Z-test.
Electron. Colloquium Comput. Complex., 2017

On Non-Optimally Expanding Sets in Grassmann Graphs.
Electron. Colloquium Comput. Complex., 2017

High dimensional expanders imply agreement expanders.
Electron. Colloquium Comput. Complex., 2017

Agreement tests on graphs and hypergraphs.
Electron. Colloquium Comput. Complex., 2017

Low degree almost Boolean functions are sparse juntas.
Electron. Colloquium Comput. Complex., 2017

Multiplayer Parallel Repetition for Expanding Games.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016
Towards a Proof of the 2-to-1 Games Conjecture?
Electron. Colloquium Comput. Complex., 2016

Multiplayer parallel repetition for expander games.
Electron. Colloquium Comput. Complex., 2016

Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover.
Electron. Colloquium Comput. Complex., 2016

Cube vs. Cube Low Degree Test.
Electron. Colloquium Comput. Complex., 2016

2015
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.
Electron. Colloquium Comput. Complex., 2015

A parallel repetition theorem for entangled projection games.
Comput. Complex., 2015

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Derandomized Graph Product Results Using the Low Degree Long Code.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

2014
The Computational Benefit of Correlated Instances.
Electron. Colloquium Comput. Complex., 2014

Direct Sum Testing.
Electron. Colloquium Comput. Complex., 2014

Analytical approach to parallel repetition.
Proceedings of the Symposium on Theory of Computing, 2014

2013
Direct Product Testing.
Electron. Colloquium Comput. Complex., 2013

On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors.
Electron. Colloquium Comput. Complex., 2013

PCPs via low-degree long code and hardness for constrained hypergraph coloring.
Electron. Colloquium Comput. Complex., 2013

Clustering in the Boolean Hypercube in a List Decoding Regime.
Electron. Colloquium Comput. Complex., 2013

Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword.
Comput. Complex., 2013

2012
Covering CSPs.
Electron. Colloquium Comput. Complex., 2012

2011
Dense locally testable codes cannot have constant rate and distance.
Electron. Colloquium Comput. Complex., 2011

Derandomized Parallel Repetition via Structured PCPs.
Comput. Complex., 2011

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.
Comput. Complex., 2011

2010
Composition of Low-Error 2-Query PCPs Using Decodable PCPs.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Derandomized Parallel Repetition of Structured PCPs.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010

The Structure of Winning Strategies in Parallel Repetition Games.
Proceedings of the Approximation, 2010

2009
Composition of low-error 2-query PCPs using decodable PCPs.
Electron. Colloquium Comput. Complex., 2009

Intersecting Families are Essentially Contained in Juntas.
Comb. Probab. Comput., 2009

2008
PCPs with small soundness error.
SIGACT News, 2008

Special Issue on Foundations of Computer Science.
SIAM J. Comput., 2008

Decodability of Group Homomorphisms beyond the Johnson Bound.
Electron. Colloquium Comput. Complex., 2008

Locally Testing Direct Product in the Low Error Range.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
The PCP theorem by gap amplification.
J. ACM, 2007

2006
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem.
SIAM J. Comput., 2006

Robust Local Testability of Tensor Products of LDPC Codes.
Electron. Colloquium Comput. Complex., 2006

Proof of an Intersection Theorem via Graph Homomorphisms.
Electron. J. Comb., 2006

On the fourier tails of bounded functions over the discrete cube.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
SIAM J. Comput., 2005

Conditional Hardness for Approximate Coloring
Electron. Colloquium Comput. Complex., 2005

The Hardness of 3-Uniform Hypergraph Coloring.
Comb., 2005

2004
On the hardness of approximating label-cover.
Inf. Process. Lett., 2004

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

Revealing information while preserving privacy.
Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

2002
Approximating SVP<sub>infinity</sub> to within almost-polynomial factors is NP-hard.
Theor. Comput. Sci., 2002

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon)
Electron. Colloquium Comput. Complex., 2002

2001
The Importance of Being Biased
Electron. Colloquium Comput. Complex., 2001

1999
Approximating SVP<sub>infty</sub> to within Almost-Polynomial Factors is NP-hard
Electron. Colloquium Comput. Complex., 1999

1998
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability
Electron. Colloquium Comput. Complex., 1998

Approximating CVP to Within Almost Polynomial Factor is NP-Hard
Electron. Colloquium Comput. Complex., 1998

Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998


  Loading...