Shmuel Safra

CoRR, 2023

NP-Hardness of Almost Coloring Almost 3-Colorable Graphs.

[BibT_eX]

[DOI]

Yahli Hecht

Proceedings of the Approximation, 2023

2020

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Towards a Proof of the Fourier-Entropy Conjecture?

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Revisiting Bourgain-Kalai and Fourier Entropies.

[BibT_eX]

[DOI]

CoRR, 2019

2018

On Monotonicity Testing and Boolean Isoperimetric-type Theorems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Small Set Expansion in The Johnson Graph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

2017

On Non-Optimally Expanding Sets in Grassmann Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

2016

On Independent Sets, 2-to-2 Games and Grassmann Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

On the Converse of Talagrand's Influence Inequality.

[BibT_eX]

[DOI]

CoRR, 2015

2013

A Two-Prover One-Round Game with Strong Soundness.

[BibT_eX]

[DOI]

Theory Comput., 2013

2012

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

Towards An Optimal Query Efficient PCP?

[BibT_eX]

[DOI]

Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2012

2011

Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Per Austrin

Theory Comput., 2011

Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity

[BibT_eX]

[DOI]

CoRR, 2011

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

[BibT_eX]

[DOI]

Comput. Complex., 2011

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

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

[BibT_eX]

[DOI]

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

2008

The Erdös-Hajnal conjecture for bull-free graphs.

[BibT_eX]

[DOI]

Maria Chudnovsky

J. Comb. Theory B, 2008

Ranged hash functions and the price of churn.

[BibT_eX]

[DOI]

James Aspnes

Yitong Yin

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Hardness amplification for errorless heuristics.

[BibT_eX]

[DOI]

Andrej Bogdanov

Electron. Colloquium Comput. Complex., 2007

2006

Algorithmic construction of sets for <i>k</i>-restrictions.

[BibT_eX]

[DOI]

Noga Alon

Dana Moshkovitz

ACM Trans. Algorithms, 2006

Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Extractors from Reed-Muller codes.

[BibT_eX]

[DOI]

Amnon Ta-Shma

David Zuckerman

J. Comput. Syst. Sci., 2006

On the complexity of approximating tsp with neighborhoods and related problems.

[BibT_eX]

[DOI]

Comput. Complex., 2006

On the complexity of approximating <i>k</i>-set packing.

[BibT_eX]

[DOI]

Elad Hazan

Comput. Complex., 2006

Relating word and tree automata.

[BibT_eX]

[DOI]

Orna Kupferman

Moshe Y. Vardi

Ann. Pure Appl. Log., 2006

Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics.

[BibT_eX]

Gil Kalai

Christos H. Papadimitriou

Proceedings of the Computational Complexity and Statistical Physics., 2006

2005

On Non-Approximability for Quadratic Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

The complexity of low-distortion embeddings between point sets.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Testing juntas.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

On the hardness of approximating label-cover.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Inf. Process. Lett., 2004

2003

On the complexity of price equilibria.

[BibT_eX]

[DOI]

Xiaotie Deng

J. Comput. Syst. Sci., 2003

On the Hardness of Approximating k-Dimensional Matching

[BibT_eX]

[DOI]

Elad Hazan

Electron. Colloquium Comput. Complex., 2003

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

[BibT_eX]

[DOI]

Comb., 2003

On the Complexity of Approximating k-Dimensional Matching.

[BibT_eX]

[DOI]

Elad Hazan

Proceedings of the Approximation, 2003

Proving Hard-Core Predicates Using List Decoding.

[BibT_eX]

[DOI]

Adi Akavia

Shafi Goldwasser

Christos H. Papadimitriou

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

On the complexity of equilibria.

[BibT_eX]

[DOI]

Xiaotie Deng

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

The Importance of Being Biased

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

2000

A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.

[BibT_eX]

[DOI]

Oded Goldreich

SIAM J. Comput., 2000

On the Hardness of Approximating the Chromatic Number.

[BibT_eX]

[DOI]

Sanjeev Khanna

Nathan Linial

Comb., 2000

1999

Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

1998

On Data Structures and Asymmetric Communication Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Probabilistic Checking of Proofs: A New Characterization of NP.

[BibT_eX]

[DOI]

Sanjeev Arora

J. ACM, 1998

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

[BibT_eX]

[DOI]

Guy Kindler

Electron. Colloquium Comput. Complex., 1998

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

[BibT_eX]

[DOI]

Guy Kindler

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

1997

A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.

[BibT_eX]

[DOI]

Ran Raz

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

Interactive Proofs and the Hardness of Approximating Cliques.

[BibT_eX]

[DOI]

J. ACM, 1996

A Combinatorial Consistency Lemma with application to the PCP Theorem

[BibT_eX]

[DOI]

Oded Goldreich

Electron. Colloquium Comput. Complex., 1996

1994

On Planning while Learning.

[BibT_eX]

[DOI]

Moshe Tennenholtz

J. Artif. Intell. Res., 1994

1993

A Well-Characterized Approximation Problem.

[BibT_eX]

[DOI]

Johan Håstad

Steven J. Phillips

Inf. Process. Lett., 1993

1992

Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Low Communication 2-Prover Zero-Knowledge Proofs for NP.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1992

1991

Approximating Clique is Almost NP-Complete (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1989

On omega-Automata and Temporal Logic (Preliminary Report)

[BibT_eX]

[DOI]

Moshe Y. Vardi

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

On the Complexity of omega-Automata

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Notes on the Complexity of Systolic Programs.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1987

1986

Multiway Merge with Constant Delay in Concurrent Prolog.

[BibT_eX]

[DOI]

New Gener. Comput., 1986

A parallel implementation of Flat Concurrent Prolog.

[BibT_eX]

[DOI]

Stephen Taylor

Int. J. Parallel Program., 1986

Meta Interpreters For Real (Invited Paper).

[BibT_eX]

Proceedings of the Information Processing 86, 1986

1985

Fast Multiway Merge Using Destructive Operation.

[BibT_eX]