Shmuel Safra | Academic Influence

Shmuel Safra's AcademicInfluence.com Rankings

Shmuel Safra

Computer Science

#1615

World Rank

#1670

Historical Rank

Database

#8272

World Rank

#8635

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Shmuel Safra's Degrees

Bachelors Mathematics Tel Aviv University
Masters Computer Science Weizmann Institute of Science
PhD Computer Science Weizmann Institute of Science

Similar Degrees You Can Earn

Why Is Shmuel Safra Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Shmuel Safra is an Israeli computer scientist. He is a Professor of Computer Science at Tel Aviv University, Israel. He was born in Jerusalem. Safra's research areas include complexity theory and automata theory. His work in complexity theory includes the classification of approximation problemss—showing them NP-hard even for weak factors of approximation—and the theory of probabilistically checkable proofs and the PCP theorem, which gives stronger characterizations of the class NP, via a membership proof that can be verified reading only a constant number of its bits.

(See a Problem?)

Shmuel Safra's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Probabilistic checking of proofs; a new characterization of NP (1992) (1340)
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP (1997) (919)
On the hardness of approximating minimum vertex cover (2005) (642)
On the complexity of omega -automata (1988) (477)
Approximating clique is almost NP-complete (1991) (468)
Interactive proofs and the hardness of approximating cliques (1996) (465)
On data structures and asymmetric communication complexity (1994) (330)
Algorithmic construction of sets for k-restrictions (2006) (300)
The importance of being biased (2002) (236)
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard (2003) (235)
On the Hardness of Approximating the Chromatic Number (1993) (205)
On the complexity of approximating k-set packing (2006) (184)
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors (1999) (159)
On the complexity of equilibria (2002) (134)
Testing juntas (2002) (134)
Proving hard-core predicates using list decoding (2003) (119)
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion (2018) (114)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs (2009) (110)
On the complexity of approximating tsp with neighborhoods and related problems (2003) (96)
Exponential determinization for ω-automata with strong-fairness acceptance condition (extended abstract) (1992) (89)
Extractors from Reed-Muller codes (2001) (85)
Meta interpreters for real (1988) (81)
Towards a proof of the 2-to-1 games conjecture? (2018) (78)
On Monotonicity Testing and Boolean Isoperimetric Type Theorems (2015) (73)
On The Complexity of w-Automata (1988) (69)
On independent sets, 2-to-2 games, and Grassmann graphs (2017) (69)
On the hardness of approximating label-cover (2004) (68)
On non-approximability for quadratic programs (2005) (68)
Noise-Resistant Boolean-Functions are Juntas (2003) (67)
On ω-automata and temporal logic (1989) (66)
On non-optimally expanding sets in Grassmann graphs (2018) (64)
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability (1999) (63)
On the complexity of price equilibria (2003) (60)
The Erdös-Hajnal conjecture for bull-free graphs (2008) (60)
On the Complexity of Approximating k-Dimensional Matching (2003) (48)
Low Communication 2-Prover Zero-Knowledge Proofs for NP (1992) (47)
Relating word and tree automata (1996) (41)
A well-characterized approximation problem (1993) (39)
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem (1997) (39)
The complexity of low-distortion embeddings between point sets (2005) (38)
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity (2011) (29)
Threshold Phenomena and Influence, with Some Perspectives from Mathematics, Computer Science, and Economics (2005) (28)
On the Hardness of Approximating k-Dimensional Matching (2003) (28)
Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics (2006) (26)
Hardness Amplification for Errorless Heuristics (2007) (25)
A Two Prover One Round Game with Strong Soundness (2011) (24)
Hardness of Finding Independent Sets in Almost q-Colorable Graphs (2010) (20)
Small Set Expansion in The Johnson Graph (2018) (20)
On Planning while Learning (1994) (17)
IDAS : Interactive Directory Assistance Service (2000) (16)
Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition (2006) (15)
On Parallel-Repetition, Unique-Game and Max-Cut (2007) (14)
On omega-Automata and Temporal Logic (Preliminary Report) (1989) (14)
Complexity of Automata on Innnite Objects (1989) (14)
Algorithmic construction of sets for (2006) (12)
Meta Interpreters For Real (Invited Paper) (1986) (7)
A parallel implementation of Flat Concurrent Prolog (1986) (7)
Testing juntas [combinatorial property testing] (2002) (5)
Towards a Proof of the Fourier-Entropy Conjecture? (2019) (4)
Notes on the Complexity of Systolic Programs (1987) (4)
Towards an optimal query efficient PCP? (2013) (4)
Ranged hash functions and the price of churn (2008) (3)
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity (2011) (3)
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality (2020) (3)
Fast Multiway Merge Using Destructive Operation (1985) (3)
A Combinatorial Consistency Lemma with application to the PCP Theorem (1996) (3)
Approximating Clique is Almost NP-Complete (Preliminary Version) (1991) (2)
On the Converse of Talagrand's Influence Inequality (2015) (2)
Idas : Interactive Directory Assistance Services (2000) (2)
Threshold Phenomena and Influences (2005) (2)
Multiway merge with constant delay in Concurrent Prolog (1986) (1)
Revisiting Bourgain-Kalai and Fourier Entropies (2019) (1)
On the Complexity of the Catalog-Segmentation Problem (2001) (1)
Themes Complexity Theory ’ 94 In the months of August and September , 1994 (0)
On the Complexity of Flexible Approximation Problems (2004) (0)
On !-Automata and Temporal Logi Preliminary Report (2017) (0)
Timed Modal Specifications........ 8 (0)
An Improved Lower Bound for Ap-proximating CVP (2000) (0)

This paper list is powered by the following services:

Other Resources About Shmuel Safra

en.wikipedia.org

What Schools Are Affiliated With Shmuel Safra?

Shmuel Safra is affiliated with the following schools: