default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDShmuel Safra
Person information
- affiliation: Tel Aviv University, Israel
- award (2001): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2023
[c40]Yahli Hecht, Dor Minzer, Muli Safra:
NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. APPROX/RANDOM 2023: 51:1-51:12- [i23]Yael Eisenberg, Itamar Rot, Muli Safra:
On the Shortest Lattice Vector vs. the Shortest Basis. CoRR abs/2305.19777 (2023) - 2021
- [c39]Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
:
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. ITCS 2021: 26:1-26:17 - 2020
- [c38]Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra:
Towards a Proof of the Fourier-Entropy Conjecture? FOCS 2020: 247-258 - [i22]Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [i21]Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra:
Revisiting Bourgain-Kalai and Fourier Entropies. CoRR abs/1911.10579 (2019) - 2018
- [j27]Subhash Khot, Dor Minzer, Muli Safra:
On Monotonicity Testing and Boolean Isoperimetric-type Theorems. SIAM J. Comput. 47(6): 2238-2276 (2018) - [c37]Subhash Khot, Dor Minzer, Muli Safra:
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion. FOCS 2018: 592-601 - [c36]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
Towards a proof of the 2-to-1 games conjecture? STOC 2018: 376-389 - [c35]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
On non-optimally expanding sets in Grassmann graphs. STOC 2018: 940-951 - [i20]Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra:
Small Set Expansion in The Johnson Graph. Electron. Colloquium Comput. Complex. TR18 (2018) - [i19]Subhash Khot, Dor Minzer, Muli Safra:
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c34]Subhash Khot, Dor Minzer, Muli Safra:
On independent sets, 2-to-2 games, and Grassmann graphs. STOC 2017: 576-589 - [i18]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
On Non-Optimally Expanding Sets in Grassmann Graphs. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i17]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
Towards a Proof of the 2-to-1 Games Conjecture? Electron. Colloquium Comput. Complex. TR16 (2016) - [i16]Subhash Khot, Dor Minzer, Muli Safra:
On Independent Sets, 2-to-2 Games and Grassmann Graphs. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c33]Subhash Khot, Dor Minzer, Muli Safra:
On Monotonicity Testing and Boolean Isoperimetric Type Theorems. FOCS 2015: 52-58 - [i15]Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman, Yinon Spinka:
On the Converse of Talagrand's Influence Inequality. CoRR abs/1506.06325 (2015) - [i14]Subhash Khot, Dor Minzer, Muli Safra:
On Monotonicity Testing and Boolean Isoperimetric type Theorems. Electron. Colloquium Comput. Complex. TR15 (2015) - 2013
- [j26]Subhash Khot, Muli Safra:
A Two-Prover One-Round Game with Strong Soundness. Theory Comput. 9: 863-887 (2013) - [c32]Subhash Khot, Muli Safra, Madhur Tulsiani:
Towards an optimal query efficient PCP? ITCS 2013: 173-186 - 2012
- [j25]Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein:
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity. ACM Trans. Comput. Theory 4(4): 11:1-11:12 (2012) - [i13]Subhash Khot, Muli Safra, Madhur Tulsiani:
Towards An Optimal Query Efficient PCP? Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j24]Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Comput. Complex. 20(3): 413-504 (2011) - [j23]Per Austrin, Subhash Khot, Muli Safra:
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory Comput. 7(1): 27-43 (2011) - [c31]Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein:
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity. APPROX-RANDOM 2011: 664-675 - [c30]Subhash Khot, Muli Safra:
A Two Prover One Round Game with Strong Soundness. FOCS 2011: 648-657 - [i12]Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein:
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity. CoRR abs/1101.5345 (2011) - 2010
- [c29]Irit Dinur, Subhash Khot, Will Perkins, Muli Safra:
Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. FOCS 2010: 212-221
2000 – 2009
- 2009
- [c28]Per Austrin, Subhash Khot, Muli Safra:
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. CCC 2009: 74-80 - 2008
- [j22]Maria Chudnovsky, Shmuel Safra:
The Erdös-Hajnal conjecture for bull-free graphs. J. Comb. Theory B 98(6): 1301-1310 (2008) - [c27]James Aspnes, Muli Safra, Yitong Yin:
Ranged hash functions and the price of churn. SODA 2008: 1066-1075 - 2007
- [c26]Andrej Bogdanov, Muli Safra:
Hardness Amplification for Errorless Heuristics. FOCS 2007: 418-426 - [i11]Andrej Bogdanov, Muli Safra:
Hardness amplification for errorless heuristics. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j21]Orna Kupferman, Shmuel Safra, Moshe Y. Vardi:
Relating word and tree automata. Ann. Pure Appl. Log. 138(1-3): 126-146 (2006) - [j20]Shmuel Safra, Oded Schwartz:
On the complexity of approximating tsp with neighborhoods and related problems. Comput. Complex. 14(4): 281-307 (2006) - [j19]Elad Hazan, Shmuel Safra, Oded Schwartz:
On the complexity of approximating k-set packing. Comput. Complex. 15(1): 20-39 (2006) - [j18]Amnon Ta-Shma, David Zuckerman, Shmuel Safra:
Extractors from Reed-Muller codes. J. Comput. Syst. Sci. 72(5): 786-812 (2006) - [j17]Shmuel Safra:
Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition. SIAM J. Comput. 36(3): 803-814 (2006) - [j16]Noga Alon, Dana Moshkovitz, Shmuel Safra:
Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2): 153-177 (2006) - [p1]Gil Kalai, Shmuel Safra:
Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics. Computational Complexity and Statistical Physics 2006: 25-62 - 2005
- [c25]Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra:
On Non-Approximability for Quadratic Programs. FOCS 2005: 206-215 - [c24]Christos H. Papadimitriou, Shmuel Safra:
The complexity of low-distortion embeddings between point sets. SODA 2005: 112-118 - [i10]Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra:
On Non-Approximability for Quadratic Programs. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j15]Irit Dinur, Shmuel Safra:
On the hardness of approximating label-cover. Inf. Process. Lett. 89(5): 247-254 (2004) - [j14]Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky:
Testing juntas. J. Comput. Syst. Sci. 68(4): 753-787 (2004) - 2003
- [j13]Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra:
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Comb. 23(2): 205-243 (2003) - [j12]Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
On the complexity of price equilibria. J. Comput. Syst. Sci. 67(2): 311-324 (2003) - [c23]Shmuel Safra, Oded Schwartz:
On the Complexity of Approximating TSP with Neighborhoods and Related Problems. ESA 2003: 446-458 - [c22]Adi Akavia, Shafi Goldwasser, Shmuel Safra:
Proving Hard-Core Predicates Using List Decoding. FOCS 2003: 146-157 - [c21]Elad Hazan, Shmuel Safra, Oded Schwartz:
On the Complexity of Approximating k-Dimensional Matching. RANDOM-APPROX 2003: 83-97 - [i9]Elad Hazan, Shmuel Safra, Oded Schwartz:
On the Hardness of Approximating k-Dimensional Matching. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [c20]Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky:
Testing Juntas. FOCS 2002: 103-112 - [c19]Irit Dinur, Shmuel Safra:
The importance of being biased. STOC 2002: 33-42 - [c18]Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
On the complexity of equilibria. STOC 2002: 67-71 - 2001
- [c17]Amnon Ta-Shma, David Zuckerman, Shmuel Safra:
Extractors from Reed-Muller Codes. FOCS 2001: 638-647 - [i8]Amnon Ta-Shma, David Zuckerman, Shmuel Safra:
Extractors from Reed-Muller Codes. Electron. Colloquium Comput. Complex. TR01 (2001) - [i7]Irit Dinur, Shmuel Safra:
The Importance of Being Biased. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j11]Sanjeev Khanna, Nathan Linial, Shmuel Safra:
On the Hardness of Approximating the Chromatic Number. Comb. 20(3): 393-415 (2000) - [j10]Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. SIAM J. Comput. 29(4): 1132-1154 (2000)
1990 – 1999
- 1999
- [j9]Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert:
Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors. Inf. Process. Lett. 71(2): 55-61 (1999) - [c16]Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. STOC 1999: 29-40 - [i6]Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert:
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors. Electron. Colloquium Comput. Complex. TR99 (1999) - [i5]Irit Dinur, Shmuel Safra:
On the Hardness of Approximating Label Cover. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j8]Sanjeev Arora, Shmuel Safra:
Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM 45(1): 70-122 (1998) - [j7]Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson:
On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998) - [c15]Irit Dinur, Guy Kindler, Shmuel Safra:
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. FOCS 1998: 99-111 - [i4]Irit Dinur, Guy Kindler, Shmuel Safra:
Approximating CVP to Within Almost Polynomial Factor is NP-Hard. Electron. Colloquium Comput. Complex. TR98 (1998) - [i3]Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [c14]Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. RANDOM 1997: 67-84 - [c13]Ran Raz, Shmuel Safra:
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. STOC 1997: 475-484 - 1996
- [j6]Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
Interactive Proofs and the Hardness of Approximating Cliques. J. ACM 43(2): 268-292 (1996) - [c12]Orna Kupferman, Shmuel Safra, Moshe Y. Vardi:
Relating Word and Tree Automata. LICS 1996: 322-332 - [i2]Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with application to the PCP Theorem. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [c11]Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson:
On data structures and asymmetric communication complexity. STOC 1995: 103-111 - 1994
- [j5]Shmuel Safra, Moshe Tennenholtz:
On Planning while Learning. J. Artif. Intell. Res. 2: 111-129 (1994) - [i1]Shmuel Safra, Moshe Tennenholtz:
On Planning while Learning. CoRR abs/cs/9409101 (1994) - 1993
- [j4]Johan Håstad, Steven J. Phillips, Shmuel Safra:
A Well-Characterized Approximation Problem. Inf. Process. Lett. 47(6): 301-305 (1993) - [c10]Sanjeev Khanna, Nathan Linial, Shmuel Safra:
On the Hardness of Approximating the Chromatic Number. ISTCS 1993: 250-260 - [c9]Johan Håstad, Steven J. Phillips, Shmuel Safra:
A Well-Characterized Approximation Problem. ISTCS 1993: 261-265 - 1992
- [c8]Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, Shmuel Safra:
Low Communication 2-Prover Zero-Knowledge Proofs for NP. CRYPTO 1992: 215-227 - [c7]Sanjeev Arora, Shmuel Safra:
Probabilistic Checking of Proofs; A New Characterization of NP. FOCS 1992: 2-13 - [c6]Shmuel Safra:
Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract). STOC 1992: 275-282 - 1991
- [c5]Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
Approximating Clique is Almost NP-Complete (Preliminary Version). FOCS 1991: 2-12
1980 – 1989
- 1989
- [c4]Shmuel Safra, Moshe Y. Vardi:
On omega-Automata and Temporal Logic (Preliminary Report). STOC 1989: 127-137 - 1988
- [c3]Shmuel Safra:
On the Complexity of omega-Automata. FOCS 1988: 319-327 - 1987
- [j3]Stephen Taylor, Lisa Hellerstein, Shmuel Safra, Ehud Shapiro:
Notes on the Complexity of Systolic Programs. J. Parallel Distributed Comput. 4(3): 250-265 (1987) - 1986
- [j2]Stephen Taylor, Shmuel Safra, Ehud Shapiro:
A parallel implementation of Flat Concurrent Prolog. Int. J. Parallel Program. 15(3): 245-275 (1986) - [j1]Ehud Shapiro, Shmuel Safra:
Multiway Merge with Constant Delay in Concurrent Prolog. New Gener. Comput. 4(2): 211-216 (1986) - [c2]Shmuel Safra, Ehud Shapiro:
Meta Interpreters For Real (Invited Paper). IFIP Congress 1986: 271-278 - 1985
- [c1]Ehud Shapiro, Shmuel Safra:
Fast Multiway Merge Using Destructive Operation. ICPP 1985: 118-122
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:19 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
