Shmuel Safra

Best Publications

• Probabilistic checking of proofs: a new characterization of NP

  Sanjeev Arora;Shmuel Safra

  2016
  Citations

• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

  Ran Raz;Shmuel Safra

  1089
  Citations

• Approximating clique is almost NP-complete

  U. Feige;S. Goldwasser;L. Lovasz;S. Safra

  597
  Citations

• Interactive proofs and the hardness of approximating cliques

  Uriel Feige;Shafi Goldwasser;Laszlo Lovász;Shmuel Safra

  566
  Citations

• On the complexity of omega -automata

  Unknown

  508
  Citations

• On Data Structures and Asymmetric Communication Complexity

  Peter Bro Miltersen;Noam Nisan;Shmuel Safra;Avi Wigderson

  390
  Citations

• Algorithmic construction of sets for k-restrictions

  Noga Alon;Dana Moshkovitz;Shmuel Safra

  353
  Citations

• The importance of being biased

  Irit Dinur;Shmuel Safra

  321
  Citations

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

  I. Dinur;G. Kindler;R. Raz;S. Safra

  293
  Citations

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

  Per Austrin;Subhash Khot;Muli Safra

  234
  Citations

• Probabilistic checking of proofs; a new characterization of NP

  S. Arora;S. Safra

  230
  Citations

• On the complexity of approximating k -set packing

  Elad Hazan;Shmuel Safra;Oded Schwartz

  213
  Citations

• On the complexity of equilibria

  Xiaotie Deng;Christos Papadimitriou;Shmuel Safra

  207
  Citations

• Approximating shortest lattice vectors is not harder than approximating closet lattice vectors

  O. Goldreich;D. Micciancio;S. Safra;J. P. Seifert

  207
  Citations

• On the hardness of approximating the chromatic number

  S. Khanna;N. Linial;S. Safra

  200
  Citations

• Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion

  Unknown

  165
  Citations

• Proving hard-core predicates using list decoding

  A. Akavia;S. Goldwasser;S. Safra

  148
  Citations

• Testing juntas

  Eldar Fischer;Guy Kindler;Dana Ron;Shmuel Safra

  141
  Citations

• Extractors from Reed-Muller codes

  Amnon Ta-Shma;David Zuckerman;Shmuel Safra

  135
  Citations

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

  Per Austrin;Subhash Khot;Muli Safra

  113
  Citations