×

zbMATH — the first resource for mathematics

Safra, Shmuel

Compute Distance To:
Author ID: safra.shmuel Recent zbMATH articles by "Safra, Shmuel"
Published as: Safra, Shmuel; Safra, S.; Safra, Samuel
Documents Indexed: 31 Publications since 1986

Publications by Year

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
187
1999
On the hardness of approximating minimum vertex cover. Zbl 1084.68051
Dinur, Irit; Safra, Samuel
130
2005
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
128
1998
Algorithmic construction of sets for \(k\)-restrictions. Zbl 1321.68445
Alon, Noga; Moshkovitz, Dana; Safra, Shmuel
64
2006
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
59
1996
Probabilistic checking of proofs; a new characterization of NP. Zbl 0945.68516
Arora, Sanjeev; Safra, Shmuel
43
1992
On the complexity of approximating \(k\)-set packing. Zbl 1103.90105
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
37
2006
The importance of being biased. Zbl 1192.68318
Dinur, Irit; Safra, Shmuel
37
2002
Approximating CVP to within almost-polynomial factors is NP-hard. Zbl 1049.68072
Dinur, I.; Kindler, G.; Raz, R.; Safra, S.
25
2003
Testing juntas. Zbl 1076.68112
Fischer, Eldar; Kindler, Guy; Ron, Dana; Safra, Shmuel; Samorodnitsky, Alex
23
2004
Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. Zbl 1156.82317
Kalai, Gil; Safra, Shmuel
22
2006
The Erdős-Hajnal conjecture for bull-free graphs. Zbl 1168.05317
Chudnovsky, Maria; Safra, Shmuel
21
2008
On data structures and asymmetric communication complexity. Zbl 0920.68042
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
20
1998
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
15
2000
On the complexity of approximating \(k\)-dimensional matching. Zbl 1279.68106
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
14
2003
On the complexity of price equilibria. Zbl 1067.90102
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
13
2003
On the hardness of approximating label-cover. Zbl 1178.68676
Dinur, Irit; Safra, Shmuel
12
2004
Extractors from Reed-Muller codes. Zbl 1094.68036
Ta-Shma, Amnon; Zuckerman, David; Safra, Shmuel
12
2006
The complexity of low-distortion embeddings between point sets. Zbl 1297.68246
Papadimitriou, Christos; Safra, Shmuel
10
2005
On the complexity of equilibria. Zbl 1192.91145
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
9
2002
PCP characterizations of NP: toward a polynomially-small error-probability. Zbl 1234.68133
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
9
2011
On data structures and asymmetric communication complexity. Zbl 0968.68507
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
8
1995
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1137.90753
Safra, Shmuel; Schwartz, Oded
8
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.
7
1999
A combinatorial consistency lemma with application to proving the PCP theorem. Zbl 0948.68084
Goldreich, Oded; Safra, Shmuel
6
2000
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1266.90200
Safra, Shmuel; Schwartz, Oded
5
2003
A well-characterized approximation problem. Zbl 0782.68057
Håstad, Johan; Phillips, Steven; Safra, Shmuel
4
1993
Relating word and tree automata. Zbl 1097.03034
Kupferman, Orna; Safra, Shmuel; Vardi, Moshe Y.
4
2006
A parallel implementation of flat concurrent Prolog. Zbl 0614.68007
Taylor, Stephen; Safra, Shmuel; Shapiro, Ehud
4
1986
PCP characterizations of NP: towards a polynomially-small error-probability. Zbl 1346.68096
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
4
1999
Exponential determinization for \(\omega\)-automata with a strong fairness acceptance condition. Zbl 1120.68072
Safra, Shmuel
3
2006
PCP characterizations of NP: toward a polynomially-small error-probability. Zbl 1234.68133
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
9
2011
The Erdős-Hajnal conjecture for bull-free graphs. Zbl 1168.05317
Chudnovsky, Maria; Safra, Shmuel
21
2008
Algorithmic construction of sets for \(k\)-restrictions. Zbl 1321.68445
Alon, Noga; Moshkovitz, Dana; Safra, Shmuel
64
2006
On the complexity of approximating \(k\)-set packing. Zbl 1103.90105
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
37
2006
Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. Zbl 1156.82317
Kalai, Gil; Safra, Shmuel
22
2006
Extractors from Reed-Muller codes. Zbl 1094.68036
Ta-Shma, Amnon; Zuckerman, David; Safra, Shmuel
12
2006
Relating word and tree automata. Zbl 1097.03034
Kupferman, Orna; Safra, Shmuel; Vardi, Moshe Y.
4
2006
Exponential determinization for \(\omega\)-automata with a strong fairness acceptance condition. Zbl 1120.68072
Safra, Shmuel
3
2006
On the hardness of approximating minimum vertex cover. Zbl 1084.68051
Dinur, Irit; Safra, Samuel
130
2005
The complexity of low-distortion embeddings between point sets. Zbl 1297.68246
Papadimitriou, Christos; Safra, Shmuel
10
2005
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1137.90753
Safra, Shmuel; Schwartz, Oded
8
2005
Testing juntas. Zbl 1076.68112
Fischer, Eldar; Kindler, Guy; Ron, Dana; Safra, Shmuel; Samorodnitsky, Alex
23
2004
On the hardness of approximating label-cover. Zbl 1178.68676
Dinur, Irit; Safra, Shmuel
12
2004
Approximating CVP to within almost-polynomial factors is NP-hard. Zbl 1049.68072
Dinur, I.; Kindler, G.; Raz, R.; Safra, S.
25
2003
On the complexity of approximating \(k\)-dimensional matching. Zbl 1279.68106
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
14
2003
On the complexity of price equilibria. Zbl 1067.90102
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
13
2003
On the complexity of approximating TSP with neighborhoods and related problems. Zbl 1266.90200
Safra, Shmuel; Schwartz, Oded
5
2003
The importance of being biased. Zbl 1192.68318
Dinur, Irit; Safra, Shmuel
37
2002
On the complexity of equilibria. Zbl 1192.91145
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
9
2002
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
15
2000
A combinatorial consistency lemma with application to proving the PCP theorem. Zbl 0948.68084
Goldreich, Oded; Safra, Shmuel
6
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
187
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.
7
1999
PCP characterizations of NP: towards a polynomially-small error-probability. Zbl 1346.68096
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
4
1999
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
128
1998
On data structures and asymmetric communication complexity. Zbl 0920.68042
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
20
1998
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
59
1996
On data structures and asymmetric communication complexity. Zbl 0968.68507
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
8
1995
A well-characterized approximation problem. Zbl 0782.68057
Håstad, Johan; Phillips, Steven; Safra, Shmuel
4
1993
Probabilistic checking of proofs; a new characterization of NP. Zbl 0945.68516
Arora, Sanjeev; Safra, Shmuel
43
1992
A parallel implementation of flat concurrent Prolog. Zbl 0614.68007
Taylor, Stephen; Safra, Shmuel; Shapiro, Ehud
4
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

Citations by Year