# zbMATH — the first resource for mathematics

## Safra, Shmuel

Compute Distance To:
 Author ID: safra.shmuel Published as: Safra, Shmuel; Safra, S.; Safra, Samuel
 Documents Indexed: 31 Publications since 1986
all top 5

#### Co-Authors

 1 single-authored 6 Dinur, Irit 4 Kindler, Guy 4 Raz, Ran 4 Schwartz, Oded 3 Fischer, Eldar 3 Papadimitriou, Christos Harilaos 2 Arora, Sanjeev 2 Bro Miltersen, Peter 2 Deng, Xiao-Tie 2 Goldreich, Oded 2 Hazan, Elad 2 Nisan, Noam 2 Wigderson, Avi 1 Alon, Noga M. 1 Chudnovsky, Maria 1 Feige, Uriel 1 Goldwasser, Shafi 1 Håstad, Johan Torkel 1 Kalai, Gil 1 Khanna, Sanjeev 1 Kupferman, Orna 1 Linial, Nathan 1 Lovász, László 1 Micciancio, Daniele 1 Moshkovitz, Dana 1 Phillips, Steven J. 1 Ron, Dana 1 Samorodnitsky, Alex 1 Seifert, Jean-Pierre 1 Shapiro, Ehud Y. 1 Szegedy, Mario 1 Ta-Shma, Amnon 1 Vardi, Moshe Y. 1 Zuckerman, David
all top 5

#### Serials

 4 Journal of Computer and System Sciences 3 Information Processing Letters 3 Computational Complexity 2 SIAM Journal on Computing 2 Combinatorica 2 Journal of the ACM 1 Journal of Combinatorial Theory. Series B 1 Annals of Pure and Applied Logic 1 International Journal of Parallel Programming 1 Annals of Mathematics. Second Series 1 ACM Transactions on Algorithms
all top 5

#### Fields

 29 Computer science (68-XX) 4 Operations research, mathematical programming (90-XX) 3 Combinatorics (05-XX) 2 Mathematical logic and foundations (03-XX) 2 Numerical analysis (65-XX) 2 Information and communication theory, circuits (94-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX)

#### Citations contained in zbMATH Open

31 Publications have been cited 943 times in 807 Documents Cited by Year
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Zbl 0963.68175
Raz, Ran; Safra, Shmuel
1999
On the hardness of approximating minimum vertex cover. Zbl 1084.68051
Dinur, Irit; Safra, Samuel
2005
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
1998
Algorithmic construction of sets for $$k$$-restrictions. Zbl 1321.68445
Alon, Noga; Moshkovitz, Dana; Safra, Shmuel
2006
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
1996
Probabilistic checking of proofs; a new characterization of NP. Zbl 0945.68516
Arora, Sanjeev; Safra, Shmuel
1992
On the complexity of approximating $$k$$-set packing. Zbl 1103.90105
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
2006
The importance of being biased. Zbl 1192.68318
Dinur, Irit; Safra, Shmuel
2002
Approximating CVP to within almost-polynomial factors is NP-hard. Zbl 1049.68072
Dinur, I.; Kindler, G.; Raz, R.; Safra, S.
2003
Testing juntas. Zbl 1076.68112
Fischer, Eldar; Kindler, Guy; Ron, Dana; Safra, Shmuel; Samorodnitsky, Alex
2004
Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. Zbl 1156.82317
Kalai, Gil; Safra, Shmuel
2006
The Erdős-Hajnal conjecture for bull-free graphs. Zbl 1168.05317
Chudnovsky, Maria; Safra, Shmuel
2008
On data structures and asymmetric communication complexity. Zbl 0920.68042
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
1998
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
2000
On the complexity of approximating $$k$$-dimensional matching. Zbl 1279.68106
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
2003
On the complexity of price equilibria. Zbl 1067.90102
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
2003
On the hardness of approximating label-cover. Zbl 1178.68676
Dinur, Irit; Safra, Shmuel
2004
Extractors from Reed-Muller codes. Zbl 1094.68036
Ta-Shma, Amnon; Zuckerman, David; Safra, Shmuel
2006
The complexity of low-distortion embeddings between point sets. Zbl 1297.68246
2005
On the complexity of equilibria. Zbl 1192.91145
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
2002
PCP characterizations of NP: toward a polynomially-small error-probability. Zbl 1234.68133
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
2011
On data structures and asymmetric communication complexity. Zbl 0968.68507
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
1995
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1137.90753
Safra, Shmuel; Schwartz, Oded
2005
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Zbl 0999.68085
Goldreich, O.; Micciancio, D.; Safra, S.; Seifert, J.-P.
1999
A combinatorial consistency lemma with application to proving the PCP theorem. Zbl 0948.68084
Goldreich, Oded; Safra, Shmuel
2000
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1266.90200
Safra, Shmuel; Schwartz, Oded
2003
A well-characterized approximation problem. Zbl 0782.68057
Håstad, Johan; Phillips, Steven; Safra, Shmuel
1993
Relating word and tree automata. Zbl 1097.03034
Kupferman, Orna; Safra, Shmuel; Vardi, Moshe Y.
2006
A parallel implementation of flat concurrent Prolog. Zbl 0614.68007
Taylor, Stephen; Safra, Shmuel; Shapiro, Ehud
1986
PCP characterizations of NP: towards a polynomially-small error-probability. Zbl 1346.68096
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
1999
Exponential determinization for $$\omega$$-automata with a strong fairness acceptance condition. Zbl 1120.68072
Safra, Shmuel
2006
PCP characterizations of NP: toward a polynomially-small error-probability. Zbl 1234.68133
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
2011
The Erdős-Hajnal conjecture for bull-free graphs. Zbl 1168.05317
Chudnovsky, Maria; Safra, Shmuel
2008
Algorithmic construction of sets for $$k$$-restrictions. Zbl 1321.68445
Alon, Noga; Moshkovitz, Dana; Safra, Shmuel
2006
On the complexity of approximating $$k$$-set packing. Zbl 1103.90105
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
2006
Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. Zbl 1156.82317
Kalai, Gil; Safra, Shmuel
2006
Extractors from Reed-Muller codes. Zbl 1094.68036
Ta-Shma, Amnon; Zuckerman, David; Safra, Shmuel
2006
Relating word and tree automata. Zbl 1097.03034
Kupferman, Orna; Safra, Shmuel; Vardi, Moshe Y.
2006
Exponential determinization for $$\omega$$-automata with a strong fairness acceptance condition. Zbl 1120.68072
Safra, Shmuel
2006
On the hardness of approximating minimum vertex cover. Zbl 1084.68051
Dinur, Irit; Safra, Samuel
2005
The complexity of low-distortion embeddings between point sets. Zbl 1297.68246
2005
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1137.90753
Safra, Shmuel; Schwartz, Oded
2005
Testing juntas. Zbl 1076.68112
Fischer, Eldar; Kindler, Guy; Ron, Dana; Safra, Shmuel; Samorodnitsky, Alex
2004
On the hardness of approximating label-cover. Zbl 1178.68676
Dinur, Irit; Safra, Shmuel
2004
Approximating CVP to within almost-polynomial factors is NP-hard. Zbl 1049.68072
Dinur, I.; Kindler, G.; Raz, R.; Safra, S.
2003
On the complexity of approximating $$k$$-dimensional matching. Zbl 1279.68106
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
2003
On the complexity of price equilibria. Zbl 1067.90102
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
2003
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1266.90200
Safra, Shmuel; Schwartz, Oded
2003
The importance of being biased. Zbl 1192.68318
Dinur, Irit; Safra, Shmuel
2002
On the complexity of equilibria. Zbl 1192.91145
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
2002
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
2000
A combinatorial consistency lemma with application to proving the PCP theorem. Zbl 0948.68084
Goldreich, Oded; Safra, Shmuel
2000
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Zbl 0963.68175
Raz, Ran; Safra, Shmuel
1999
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Zbl 0999.68085
Goldreich, O.; Micciancio, D.; Safra, S.; Seifert, J.-P.
1999
PCP characterizations of NP: towards a polynomially-small error-probability. Zbl 1346.68096
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
1999
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
1998
On data structures and asymmetric communication complexity. Zbl 0920.68042
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
1998
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
1996
On data structures and asymmetric communication complexity. Zbl 0968.68507
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
1995
A well-characterized approximation problem. Zbl 0782.68057
Håstad, Johan; Phillips, Steven; Safra, Shmuel
1993
Probabilistic checking of proofs; a new characterization of NP. Zbl 0945.68516
Arora, Sanjeev; Safra, Shmuel
1992
A parallel implementation of flat concurrent Prolog. Zbl 0614.68007
Taylor, Stephen; Safra, Shmuel; Shapiro, Ehud
1986
all top 5

#### Cited by 1,388 Authors

 11 Keller, Nathan 11 Kortsarz, Guy 11 Rawitz, Dror 9 Ben-Sasson, Eli 9 Dinur, Irit 9 Sudan, Madhu 8 Alon, Noga M. 8 Caragiannis, Ioannis 8 Goldreich, Oded 8 Khot, Subhash Ajit 8 Mossel, Elchanan 8 Servedio, Rocco A. 7 Grigorescu, Elena 7 Håstad, Johan Torkel 7 Kaklamanis, Christos 7 Manurangsi, Pasin 7 Paschos, Vangelis Th. 7 Ron, Dana 7 Tokushige, Norihide 7 Trevisan, Luca 6 Butenko, Sergiy I. 6 Chen, Wenbin 6 Chiesa, Alessandro 6 Chudnovsky, Maria 6 Escoffier, Bruno 6 Feige, Uriel 6 Fernau, Henning 6 Guruswami, Venkatesan 6 Kindler, Guy 6 Monnot, Jérôme 6 Mustafa, Nabil Hassan 6 Rubinfeld, Ronitt 5 Bazgan, Cristina 5 Blais, Eric 5 Chlebík, Miroslav 5 Chlebíková, Janka 5 Demange, Marc 5 Deng, Xiao-Tie 5 Elbassioni, Khaled M. 5 Fomin, Fedor V. 5 Lifshitz, Noam 5 Mestre, Julián 5 Ono, Hirotaka 5 Patt-Shamir, Boaz 5 Ray, Saurabh 5 Safra, Shmuel 5 Saurabh, Saket 5 Vidick, Thomas 5 Weinstein, Amit 4 Bilò, Davide 4 DasGupta, Bhaskar 4 Diakonikolas, Ilias 4 Dondi, Riccardo 4 Fox, Jacob 4 Grimmett, Geoffrey R. 4 Halldórsson, Magnús Mar 4 Hassin, Refael 4 Haviv, Ishay 4 Kopparty, Swastik 4 Levin, Asaf 4 Liśkiewicz, Maciej 4 Matulef, Kevin 4 Meir, Or 4 Meunier, Frédéric 4 Mishra, Sounaka 4 Nutov, Zeev 4 O’Donnell, Ryan 4 Pardalos, Panos M. 4 Parekh, Ojas 4 Peleg, David 4 Raz, Ran 4 Saket, Rishi 4 Sampaio, Rudini Menezes 4 Segev, Danny 4 Song, Yinglei 4 Viderman, Michael 4 Woeginger, Gerhard Johannes 4 Wu, Weili 3 Alekhnovich, Michael 3 Angluin, Dana 3 Applebaum, Benny 3 Arora, Sanjeev 3 Athanassopoulos, Stavros 3 Bhangale, Amey 3 Boginski, Vladimir L. 3 Boros, Endre 3 Bro Miltersen, Peter 3 Brody, Joshua E. 3 Bshouty, Nader H. 3 Bus, Norbert 3 Cai, Jin-Yi 3 Campêlo, Manoel B. 3 Çivril, Ali 3 El Ouali, Mourad 3 Engebretsen, Lars 3 Ergun, Funda 3 Feldman, Vitaly 3 Filmus, Yuval 3 Fortnow, Lance J. 3 Fujito, Toshihiro ...and 1,288 more Authors
all top 5

#### Cited in 120 Serials

 108 Theoretical Computer Science 53 Algorithmica 44 Discrete Applied Mathematics 38 Information Processing Letters 38 Journal of Computer and System Sciences 32 Journal of Combinatorial Optimization 21 Computational Complexity 20 SIAM Journal on Computing 15 Theory of Computing Systems 14 Information and Computation 13 Random Structures & Algorithms 13 Computational Geometry 12 Journal of Discrete Algorithms 11 Mathematical Programming. Series A. Series B 9 Discrete Mathematics 8 Discrete & Computational Geometry 7 Artificial Intelligence 7 Combinatorica 7 SIAM Journal on Discrete Mathematics 7 Combinatorics, Probability and Computing 6 Journal of Combinatorial Theory. Series A 6 Journal of Combinatorial Theory. Series B 6 Mathematics of Operations Research 6 Networks 6 European Journal of Combinatorics 6 Operations Research Letters 6 Annals of Operations Research 6 Journal of Global Optimization 5 European Journal of Operational Research 5 Discrete Optimization 5 Algorithms 4 Journal of Graph Theory 4 Journal of Cryptology 4 Distributed Computing 4 Annals of Mathematics and Artificial Intelligence 4 Computer Science Review 3 Israel Journal of Mathematics 3 Information Sciences 3 Annals of Pure and Applied Logic 3 Computers & Operations Research 3 Data Mining and Knowledge Discovery 3 4OR 2 Communications in Mathematical Physics 2 Acta Mathematica 2 The Annals of Probability 2 Journal of Computer Science and Technology 2 New Generation Computing 2 International Journal of Parallel Programming 2 Mathematical and Computer Modelling 2 Machine Learning 2 International Journal of Foundations of Computer Science 2 Discrete Event Dynamic Systems 2 Designs, Codes and Cryptography 2 Geometric and Functional Analysis. GAFA 2 Bulletin of the American Mathematical Society. New Series 2 Annales de l’Institut Henri Poincaré. Probabilités et Statistiques 2 Chicago Journal of Theoretical Computer Science 2 Annals of Mathematics. Second Series 2 Journal of the European Mathematical Society (JEMS) 2 RAIRO. Operations Research 2 Optimization Letters 2 RAIRO. Theoretical Informatics and Applications 2 ACM Transactions on Computation Theory 1 Advances in Applied Probability 1 International Journal of Control 1 International Journal of Theoretical Physics 1 Journal of the Franklin Institute 1 Journal of Mathematical Biology 1 Journal of Statistical Physics 1 ACM Transactions on Database Systems 1 Mathematics of Computation 1 Chaos, Solitons and Fractals 1 The Mathematical Intelligencer 1 Advances in Mathematics 1 BIT 1 Fuzzy Sets and Systems 1 International Journal of Game Theory 1 Journal of Environmental Economics and Management 1 Journal of Optimization Theory and Applications 1 Operations Research 1 Opsearch 1 Transactions of the American Mathematical Society 1 Mathematical Social Sciences 1 Graphs and Combinatorics 1 Probability Theory and Related Fields 1 Journal of Complexity 1 Science in China. Series A 1 International Journal of Computational Geometry & Applications 1 The Annals of Applied Probability 1 MSCS. Mathematical Structures in Computer Science 1 Games and Economic Behavior 1 International Journal of Computer Mathematics 1 Computational Statistics and Data Analysis 1 Formal Methods in System Design 1 Journal of Mathematical Sciences (New York) 1 The Electronic Journal of Combinatorics 1 The Journal of Artificial Intelligence Research (JAIR) 1 INFORMS Journal on Computing 1 Journal of Graph Algorithms and Applications 1 Journal of the ACM ...and 20 more Serials
all top 5

#### Cited in 30 Fields

 555 Computer science (68-XX) 248 Combinatorics (05-XX) 206 Operations research, mathematical programming (90-XX) 71 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 68 Information and communication theory, circuits (94-XX) 24 Number theory (11-XX) 21 Probability theory and stochastic processes (60-XX) 20 Numerical analysis (65-XX) 17 Quantum theory (81-XX) 16 Mathematical logic and foundations (03-XX) 16 Convex and discrete geometry (52-XX) 14 Biology and other natural sciences (92-XX) 10 Order, lattices, ordered algebraic structures (06-XX) 8 Statistical mechanics, structure of matter (82-XX) 7 Statistics (62-XX) 4 Measure and integration (28-XX) 4 Systems theory; control (93-XX) 3 Group theory and generalizations (20-XX) 2 Commutative algebra (13-XX) 2 Algebraic geometry (14-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 1 General and overarching topics; collections (00-XX) 1 History and biography (01-XX) 1 General algebraic systems (08-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Functional analysis (46-XX) 1 Operator theory (47-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX)