Muli Safra
List of publications from the DBLP Bibliography Server - FAQ
- CSB - MetaPress - Google - Bing - Yahoo
 | 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. TOCT 4(4): 11 (2012) |
| i12 | | Subhash Khot, Muli Safra, Madhur Tulsiani: Towards An Optimal Query Efficient PCP? Electronic Colloquium on Computational Complexity (ECCC) 19: 109 (2012) |
| 2011 | ||
| j24 | | Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra: PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Computational Complexity 20(3): 413-504 (2011) |
| j23 | | Per Austrin, Subhash Khot, Muli Safra: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory of Computing 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 | | |
| i11 | | 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 |
| 2009 | ||
| c28 | | Per Austrin, Subhash Khot, Muli Safra: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. IEEE Conference on Computational Complexity 2009: 74-80 |
| 2008 | ||
| j22 | | Maria Chudnovsky, Shmuel Safra: The Erdös-Hajnal conjecture for bull-free graphs. J. Comb. Theory, Ser. 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 | | |
| i10 | | Andrej Bogdanov, Muli Safra: Hardness amplification for errorless heuristics. Electronic Colloquium on Computational Complexity (ECCC) 14(102) (2007) |
| 2006 | ||
| j21 | | Orna Kupferman, Shmuel Safra, Moshe Y. Vardi: Relating word and tree automata. Ann. Pure Appl. Logic 138(1-3): 126-146 (2006) |
| j20 | | Shmuel Safra, Oded Schwartz: On the complexity of approximating tsp with neighborhoods and related problems. Computational Complexity 14(4): 281-307 (2006) |
| j19 | | Elad Hazan, Shmuel Safra, Oded Schwartz: On the complexity of approximating k-set packing. Computational Complexity 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 Transactions on Algorithms 2(2): 153-177 (2006) |
| 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 |
| i9 | | Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra: On Non-Approximability for Quadratic Programs. Electronic Colloquium on Computational Complexity (ECCC)(058) (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. Combinatorica 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 |
| i8 | | Elad Hazan, Shmuel Safra, Oded Schwartz: On the Hardness of Approximating k-Dimensional Matching. Electronic Colloquium on Computational Complexity (ECCC) 10(020) (2003) |
| 2002 | ||
| c20 | | Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky: Testing Juntas. FOCS 2002: 103-112 |
| c19 | | |
| c18 | | Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra: On the complexity of equilibria. STOC 2002: 67-71 |
| 2001 | ||
| c17 | | |
| i7 | | Amnon Ta-Shma, David Zuckerman, Shmuel Safra: Extractors from Reed-Muller Codes. Electronic Colloquium on Computational Complexity (ECCC) 8(36) (2001) |
| i6 | | Irit Dinur, Shmuel Safra: The Importance of Being Biased. Electronic Colloquium on Computational Complexity (ECCC)(104) (2001) |
| 2000 | ||
| j11 | | Sanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. Combinatorica 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) |
| 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 |
| i5 | | Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert: Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors. Electronic Colloquium on Computational Complexity (ECCC) 6(2) (1999) |
| i4 | | Irit Dinur, Shmuel Safra: On the Hardness of Approximating Label Cover. Electronic Colloquium on Computational Complexity (ECCC) 6(15) (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 |
| i3 | | Irit Dinur, Guy Kindler, Shmuel Safra: Approximating CVP to Within Almost Polynomial Factor is NP-Hard. Electronic Colloquium on Computational Complexity (ECCC) 5(48) (1998) |
| i2 | | Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra: PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. Electronic Colloquium on Computational Complexity (ECCC) 5(66) (1998) |
| 1997 | ||
| c14 | | Oded Goldreich, Shmuel Safra: A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. RANDOM 1997: 67-84 |
| c13 | | |
| 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 | | |
| i1 | | Oded Goldreich, Shmuel Safra: A Combinatorial Consistency Lemma with application to the PCP Theorem. Electronic Colloquium on Computational Complexity (ECCC) 3(47) (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. (JAIR) 2: 111-129 (1994) |
| 1993 | ||
| j4 | | Johan Håstad, Steven 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 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 |
| 1989 | ||
| c4 | | Shmuel Safra, Moshe Y. Vardi: On omega-Automata and Temporal Logic (Preliminary Report). STOC 1989: 127-137 |
| 1988 | ||
| c3 | | |
| 1987 | ||
| j3 | | Stephen Taylor, Lisa Hellerstein, Shmuel Safra, Ehud Y. Shapiro: Notes on the Complexity of Systolic Programs. J. Parallel Distrib. Comput. 4(3): 250-265 (1987) |
| 1986 | ||
| j2 | | Stephen Taylor, Shmuel Safra, Ehud Y. Shapiro: A parallel implementation of Flat Concurrent Prolog. International Journal of Parallel Programming 15(3): 245-275 (1986) |
| j1 | | Ehud Y. Shapiro, Shmuel Safra: Multiway Merge with Constant Delay in Concurrent Prolog. New Generation Comput. 4(2): 211-216 (1986) |
| c2 | | Shmuel Safra, Ehud Y. Shapiro: Meta Interpreters For Real (Invited Paper). IFIP Congress 1986: 271-278 |
| 1985 | ||
| c1 | | |
Data released under the ODC-BY 1.0 license — See also our legal information page