Shmuel Safra

CoRR, October, 2025

2023

On the Shortest Lattice Vector vs. the Shortest Basis.

[BibT_eX]

[DOI]

Yael Eisenberg

Itamar Rot

CoRR, 2023

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

[BibT_eX]

[DOI]

Yahli Hecht

Proceedings of the Approximation, 2023

2021

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

[BibT_eX]

[DOI]

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

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

Small Set Expansion in The Johnson Graph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

On non-optimally expanding sets in Grassmann graphs.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Towards a proof of the 2-to-1 games conjecture?

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

On independent sets, 2-to-2 games, and Grassmann graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2015

On the Converse of Talagrand's Influence Inequality.

[BibT_eX]

[DOI]

CoRR, 2015

On Monotonicity Testing and Boolean Isoperimetric Type Theorems.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2013

Towards an optimal query efficient PCP?

[BibT_eX]

[DOI]

Madhur Tulsiani

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

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

A Two Prover One Round Game with Strong Soundness.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 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

2009

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

[BibT_eX]

[DOI]

Per Austrin

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

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

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

Algorithmic construction of sets for k-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

On the complexity of approximating k-set packing.

[BibT_eX]

[DOI]

Elad Hazan

Comput. Complex., 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

The complexity of low-distortion embeddings between point sets.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

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

On Non-Approximability for Quadratic Programs.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

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

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

On the Complexity of Approximating TSP with Neighborhoods and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2003

2002

The importance of being biased.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 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

Testing Juntas.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Extractors from Reed-Muller Codes.

[BibT_eX]

[DOI]

Amnon Ta-Shma

David Zuckerman

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

1999

On the Hardness of Approximating Label Cover

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

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

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

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

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

[BibT_eX]

[DOI]

Oded Goldreich

Proceedings of the Randomization and Approximation Techniques in Computer Science, 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

Relating Word and Tree Automata.

[BibT_eX]

[DOI]

Orna Kupferman

Moshe Y. Vardi

Proceedings of the Proceedings, 1996

1995

On data structures and asymmetric communication complexity.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1994

On Planning while Learning.

[BibT_eX]

[DOI]

Moshe Tennenholtz

J. Artif. Intell. Res., 1994

1993

On the Hardness of Approximating the Chromatic Number.

[BibT_eX]

[DOI]

Sanjeev Khanna

Nathan Linial

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

A Well-Characterized Approximation Problem.

[BibT_eX]

[DOI]

Johan Håstad

Steven J. Phillips

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 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

Probabilistic Checking of Proofs; A New Characterization of NP

[BibT_eX]

[DOI]

Sanjeev Arora

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 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]