No photo of Shmuel Safra

View Scopus Profile

Shmuel Safra

Professor

Former affiliations
1986 …2023

Research activity per year

Filter
Conference contribution

Search results

  • 2023

    NP-Hardness of Almost Coloring Almost 3-Colorable Graphs

    Hecht, Y., Minzer, D. & Safra, M., Sep 2023, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023. Megow, N. & Smith, A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 51. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 275).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    2 Scopus citations
  • 2021

    Theorems of KKL, friedgut, and talagrand via random restrictions and log-sobolev inequality

    Kelman, E., Khot, S., Kindler, G., Minzer, D. & Safra, M., 1 Feb 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 26. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    2 Scopus citations
  • 2020

    Towards a proof of the fourier-entropy conjecture?

    Kelman, E., Kindler, G., Lifshitz, N., Minzer, D. & Safra, M., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 247-258 12 p. 9317968. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    3 Scopus citations
  • 2018

    On non-optimally expanding sets in grassmann graphs

    Dinur, I., Khot, S., Kindler, G., Minzer, D. & Safra, M., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 1193-1206 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    38 Scopus citations

  • Pseudorandom sets in Grassmann graph have near-perfect expansion

    Khot, S., Minzer, D. & Safra, M., 30 Nov 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 592-601 10 p. 8555140. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    73 Scopus citations

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

    Dinur, I., Khot, S., Kindler, G., Minzer, D. & Safra, M., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 1297-1306 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    50 Scopus citations
  • 2017

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

    Khot, S., Minzer, D. & Safra, M., 19 Jun 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 576-589 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    61 Scopus citations
  • 2015

    On Monotonicity Testing and Boolean Isoperimetric Type Theorems

    Khot, S., Minzer, D. & Safra, M., 11 Dec 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 52-58 7 p. 7354387. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    40 Scopus citations
  • 2013

    Towards an optimal query efficient PCP?

    Khot, S., Safra, M. & Tulsiani, M., 2013, ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. p. 173-186 14 p. (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    2 Scopus citations
  • 2011

    Approximating the influence of monotone boolean functions in O(√n) query complexity

    Ron, D., Rubinfeld, R., Safra, M. & Weinstein, O., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. p. 664-675 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    7 Scopus citations

  • A two prover one round game with strong soundness

    Khot, S. & Safra, M., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 648-657 10 p. 6108226. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    9 Scopus citations
  • 2010

    Hardness of finding independent sets in almost 3-colorable graphs

    Dinur, I., Khot, S., Perkins, W. & Safra, M., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 212-221 10 p. 5670828. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    11 Scopus citations
  • 2009

    Inapproximability of vertex cover and independent set in bounded degree graphs

    Austrin, P., Khot, S. & Safra, M., 2009, Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009. p. 74-80 7 p. 5231231. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    44 Scopus citations
  • 2008

    Ranged hash functions and the price of churn

    Aspnes, J., Safra, M. & Yin, Y., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1066-1075 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    1 Scopus citations
  • 2007

    Hardness amplification for errorless heuristics

    Bogdanov, A. & Safra, M., 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 418-426 9 p. 4389512. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    13 Scopus citations
  • 2005

    On non-approximability for quadratic programs

    Arora, S., Berger, E., Hazan, E., Kindler, G. & Safra, M., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 206-215 10 p. 1530715. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    60 Scopus citations
  • 2003

    Proving hard-core predicates using list decoding

    Akavia, A., Goldwasser, S. & Safra, S., 2003, Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003. IEEE Computer Society, p. 146-157 12 p. 1238189. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2003-January).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    34 Scopus citations
  • 1997

    A combinatorial consistency lemma with application to proving the PCP theorem

    Goldreich, O. & Safra, S., 1997, Randomization and Approximation Techniques in Computer Science - International Workshop, RANDOM 1997, Proceedings. Rolim, J. (ed.). Springer Verlag, p. 67-84 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1269).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    10 Scopus citations
  • 1995

    On data structures and asymmetric communication complexity

    Miltersen, P. B., Nisan, N., Safra, S. & Wigderson, A., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing. Leighton, F. T. & Borodin, A. (eds.). New York, NY, USA: Association for Computing Machinery, p. 103–111 8 p. (STOC '95).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 1993

    Low communication 2-prover zero-knowledge proofs for NP

    Dwork, C., Feige, U., Kilian, J., Naor, M. & Safra, M., 1993, Advances in Cryptology — CRYPTO 1992 - 12th Annual International Cryptology Conference, Proceedings. Brickell, E. F. (ed.). Springer Verlag, p. 215-227 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 740 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    24 Scopus citations
  • 1992

    Exponential determinization for ω-automata with strong-fairness acceptance condition

    Safra, S., 1 Jul 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, p. 275-282 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129722).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    56 Scopus citations

  • Probabilistic checking of proofs; A new characterization of NP

    Arora, S. & Safra, S., 1992, Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992. IEEE Computer Society, p. 2-13 12 p. 267824. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 1992-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    163 Scopus citations
  • 1991

    Approximating clique is almost NP-complete

    Feige, U., Goldwasser, S., Lovasz, L., Safra, S. & Szegedy, M., Dec 1991, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 2-12 11 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    214 Scopus citations
  • 1989

    On ω-automata and temporal logic

    Safra, S. & Vardi, M. Y., 1989, Proc Twenty First Annu ACM Symp Theory Comput. Association for Computing Machinery (ACM), p. 127-137 11 p. (Proc Twenty First Annu ACM Symp Theory Comput).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    53 Scopus citations
  • 1988

    On the complexity of ω-automata

    Safra, S., 1988, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 319-327 9 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    465 Scopus citations