Fast Multiway Merge Using Destructive Operation. - Ehud Shapiro; Shmuel Safra (ICPP, 1985)

Meta Interpreters For Real (Invited Paper). - Shmuel Safra; Ehud Shapiro (IFIP Congress, 1986)

A parallel implementation of Flat Concurrent Prolog. - Stephen Taylor; Shmuel Safra; Ehud Shapiro (Int. J. Parallel Program., 1986)

Multiway Merge with Constant Delay in Concurrent Prolog. - Ehud Shapiro; Shmuel Safra (New Gener. Comput., 1986)

Notes on the Complexity of Systolic Programs. - Stephen Taylor; Lisa Hellerstein; Shmuel Safra; Ehud Shapiro (J. Parallel Distributed Comput., 1987)

On the Complexity of omega-Automata - Shmuel Safra (FOCS, 1988)

On omega-Automata and Temporal Logic (Preliminary Report) - Shmuel Safra; Moshe Y. Vardi (STOC, 1989)

Approximating Clique is Almost NP-Complete (Preliminary Version) - Uriel Feige; Shafi Goldwasser; László Lovász 001; Shmuel Safra; Mario Szegedy (FOCS, 1991)

Low Communication 2-Prover Zero-Knowledge Proofs for NP. - Cynthia Dwork; Uriel Feige; Joe Kilian; Moni Naor; Shmuel Safra (CRYPTO, 1992)

Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract) - Shmuel Safra (STOC, 1992)

A Well-Characterized Approximation Problem. - Johan Håstad; Steven J. Phillips; Shmuel Safra (Inf. Process. Lett., 1993)

On Planning while Learning. - Shmuel Safra; Moshe Tennenholtz (J. Artif. Intell. Res., 1994)

A Combinatorial Consistency Lemma with application to the PCP Theorem - Oded Goldreich 001; Shmuel Safra (Electron. Colloquium Comput. Complex., 1996)

Interactive Proofs and the Hardness of Approximating Cliques. - Uriel Feige; Shafi Goldwasser; László Lovász 001; Shmuel Safra; Mario Szegedy (J. ACM, 1996)

A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. - Ran Raz; Shmuel Safra (STOC, 1997)

Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. - Irit Dinur; Guy Kindler; Shmuel Safra (FOCS, 1998)

Approximating CVP to Within Almost Polynomial Factor is NP-Hard - Irit Dinur; Guy Kindler; Shmuel Safra (Electron. Colloquium Comput. Complex., 1998)

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability - Irit Dinur; Eldar Fischer; Guy Kindler; Ran Raz; Shmuel Safra (Electron. Colloquium Comput. Complex., 1998)

Probabilistic Checking of Proofs: A New Characterization of NP. - Sanjeev Arora; Shmuel Safra (J. ACM, 1998)

On Data Structures and Asymmetric Communication Complexity. - Peter Bro Miltersen; Noam Nisan; Shmuel Safra; Avi Wigderson (J. Comput. Syst. Sci., 1998)

Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors. - Oded Goldreich 001; Daniele Micciancio; Shmuel Safra; Jean-Pierre Seifert (Inf. Process. Lett., 1999)

On the Hardness of Approximating the Chromatic Number. - Sanjeev Khanna; Nathan Linial; Shmuel Safra (Comb., 2000)

A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. - Oded Goldreich 001; Shmuel Safra (SIAM J. Comput., 2000)

The Importance of Being Biased - Irit Dinur; Shmuel Safra (Electron. Colloquium Comput. Complex., 2001)

On the complexity of equilibria. - Xiaotie Deng; Christos H. Papadimitriou; Shmuel Safra (STOC, 2002)

Proving Hard-Core Predicates Using List Decoding. - Adi Akavia; Shafi Goldwasser; Shmuel Safra (FOCS, 2003)

On the Complexity of Approximating k-Dimensional Matching. - Elad Hazan; Shmuel Safra; Oded Schwartz (RANDOM-APPROX, 2003)

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. - Irit Dinur; Guy Kindler; Ran Raz; Shmuel Safra (Comb., 2003)

On the Hardness of Approximating k-Dimensional Matching - Elad Hazan; Shmuel Safra; Oded Schwartz (Electron. Colloquium Comput. Complex., 2003)

On the complexity of price equilibria. - Xiaotie Deng; Christos H. Papadimitriou; Shmuel Safra (J. Comput. Syst. Sci., 2003)

On the hardness of approximating label-cover. - Irit Dinur; Shmuel Safra (Inf. Process. Lett., 2004)

Testing juntas. - Eldar Fischer; Guy Kindler; Dana Ron; Shmuel Safra; Alex Samorodnitsky (J. Comput. Syst. Sci., 2004)

The complexity of low-distortion embeddings between point sets. - Christos H. Papadimitriou; Shmuel Safra (SODA, 2005)

On Non-Approximability for Quadratic Programs - Sanjeev Arora; Eli Berger; Elad Hazan; Guy Kindler; Muli Safra (Electron. Colloquium Comput. Complex., 2005)

Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics. - Gil Kalai; Shmuel Safra (Computational Complexity and Statistical Physics, 2006)

Relating word and tree automata. - Orna Kupferman; Shmuel Safra; Moshe Y. Vardi (Ann. Pure Appl. Log., 2006)

On the complexity of approximating k-set packing. - Elad Hazan; Shmuel Safra; Oded Schwartz (Comput. Complex., 2006)

On the complexity of approximating tsp with neighborhoods and related problems. - Shmuel Safra; Oded Schwartz (Comput. Complex., 2006)

Extractors from Reed-Muller codes. - Amnon Ta-Shma; David Zuckerman; Shmuel Safra (J. Comput. Syst. Sci., 2006)

Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition. - Shmuel Safra (SIAM J. Comput., 2006)

Algorithmic construction of sets for k-restrictions. - Noga Alon; Dana Moshkovitz; Shmuel Safra (ACM Trans. Algorithms, 2006)

Hardness amplification for errorless heuristics. - Andrej Bogdanov; Muli Safra (Electron. Colloquium Comput. Complex., 2007)

Ranged hash functions and the price of churn. - James Aspnes; Muli Safra; Yitong Yin (SODA, 2008)

The Erdös-Hajnal conjecture for bull-free graphs. - Maria Chudnovsky; Shmuel Safra (J. Comb. Theory B, 2008)

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. - Irit Dinur; Subhash Khot; Will Perkins 001; Muli Safra (FOCS, 2010)

Approximating the Influence of Monotone Boolean Functions in $O( sqrt{n})$ Query Complexity. - Dana Ron; Ronitt Rubinfeld; Muli Safra; Omri Weinstein (APPROX-RANDOM, 2011)

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. - Irit Dinur; Eldar Fischer; Guy Kindler; Ran Raz; Shmuel Safra (Comput. Complex., 2011)

Approximating the Influence of a monotone Boolean function in O( sqrt{n}) query complexity - Dana Ron; Ronitt Rubinfeld; Muli Safra; Omri Weinstein (CoRR, 2011)

Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. - Per Austrin; Subhash Khot; Muli Safra (Theory Comput., 2011)

Towards An Optimal Query Efficient PCP? - Subhash Khot; Muli Safra; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2012)

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity. - Dana Ron; Ronitt Rubinfeld; Muli Safra; Alex Samorodnitsky; Omri Weinstein (ACM Trans. Comput. Theory, 2012)

A Two-Prover One-Round Game with Strong Soundness. - Subhash Khot; Muli Safra (Theory Comput., 2013)

On the Converse of Talagrand's Influence Inequality. - Saleet Klein; Amit Levi; Muli Safra; Clara Shikhelman; Yinon Spinka (CoRR, 2015)

Towards a Proof of the 2-to-1 Games Conjecture? - Irit Dinur; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2016)

On Independent Sets, 2-to-2 Games and Grassmann Graphs. - Subhash Khot; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2016)

On Non-Optimally Expanding Sets in Grassmann Graphs. - Irit Dinur; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2017)

Small Set Expansion in The Johnson Graph. - Subhash Khot; Dor Minzer; Dana Moshkovitz; Muli Safra (Electron. Colloquium Comput. Complex., 2018)

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion. - Subhash Khot; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2018)

On Monotonicity Testing and Boolean Isoperimetric-type Theorems. - Subhash Khot; Dor Minzer; Muli Safra (SIAM J. Comput., 2018)

Revisiting Bourgain-Kalai and Fourier Entropies. - Esty Kelman; Guy Kindler; Noam Lifshitz; Dor Minzer; Muli Safra (CoRR, 2019)

Towards a Proof of the Fourier-Entropy Conjecture? - Esty Kelman; Guy Kindler; Noam Lifshitz; Dor Minzer; Muli Safra (FOCS, 2020)

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. - Esty Kelman; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra (Electron. Colloquium Comput. Complex., 2020)

NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. - Yahli Hecht; Dor Minzer; Muli Safra (APPROX/RANDOM, 2023)

On the Shortest Lattice Vector vs. the Shortest Basis. - Yael Eisenberg; Itamar Rot; Muli Safra (CoRR, 2023)