Threshold Phenomena and Influence with some perspectives from Mathematics (2008)
“Threshold phenomena ” refer to settings in which the probability for an event to occur changes rapidly as some underlying parameter varies. Thresh-old phenomena play an important role in...
Threshold Phenomena and Influence with some perspectives from Mathematics (2008)
“Threshold phenomena ” refer to settings in which the probability for an event to occur changes rapidly as some underlying parameter varies. Thresh-old phenomena play an important role in...
Threshold Phenomena and Influence with some perspectives from Mathematics (2008)
Threshold phenomena refer to settings in which the probability for an event to occur changes rapidly as some underlying parameter varies. Threshold phenomena play an important role in probability...
Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (2007)
In [Saf88] an exponential determinization procedure for Buchi automata was shown, yielding tight bounds for decision procedures of some logics ([EJ88, Saf88, SV89, KT89]). In [SV89] the complexity of...
Noise-resistant boolean-functions are juntas, prerint (2007)
We consider Boolean functions over n binary variables, and a general p-biased, product measure over the inputs. We show that if f is of low-degree, that is, so that the weight of f on the...
Algorithmic construction of sets for k-restrictions (2006)
Noga Alon, Dana Moshkovitz, Shmuel Safra
This work addresses k-restriction problems, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σ m that satisfies a given set of k-wise...
The Complexity of Low-Distortion Embeddings between Point Sets (2005)
Christos Papadimitriou, Shmuel Safra
We prove that, given two three-dimensional sets of points, deciding whether there is a bijection between the two, within a given distortion (maximum proportional increase or decrease of the distance...
The complexity of low-distortion embeddings between point sets (2005)
Christos Papadimitriou, Shmuel Safra
Abstract We prove that it is NP-hard to approximate by a ratio better than 3 the minimum distortionof a bijection between two given finite three-dimensional sets of points.
Extractors from Reed-Muller Codes (2003)
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and...
Journal of Computer and System Sciences] (]]]])]]]–]]] (2003)
Eldar Fischer, Guy Kindler, B Dana Ron, Shmuel Safra, Alex Samorodnitsky D
On the complexity of approximating k-set packing (2003)
Elad Hazan, Shmuel Safra, Oded Schwartz
Given a k-uniform hypergraph, the Maximum k-Set Packing problem is to find the maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within a factor of Ω (...
On the complexity of approximating k-set packing (2003)
Elad Hazan, Shmuel Safra, Oded Schwartz
Abstract. We study the complexity of bounded packing problems, mainly the problem of k-Set Packing (k-SP), We prove that k-SP cannot be efficiently approximated to within a factor of O ( k ln k)...
On the Complexity of Equilibria (2002)
Xiaotie Deng, Christos Papadimitriou, Shmuel Safra
We prove complexity, approximability, and inapproximability results for the problem of nding an exchange equilibrium in markets with indivisible (integer) goods, most notably a polynomial-time...
Eldar Fischer Guy, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
We show that a boolean function over n variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter #. We...
Extractors from Reed-Muller codes (2001)
Amnon Ta-shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the...
Extractors from Reed-Muller Codes (2001)
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the...
Amnon Ta-shma, Shmuel Safra, David Zuckerman
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the...
Extractors from Reed-Muller Codes (2001)
Amnon Ta-shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and...
PCP characterizations of NP: Towards a polynomially-small error-probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a witness for the membership of a given input...
Xiaotie Deng, Christos Papadimitriou, Shmuel Safra
We prove complexity, approximability, and inapproximability results for the problem of nding an exchange equilibrium in markets with indivisible (integer) goods, most notably a polynomial-time...
On the Hardness of Approximating Label Cover (1999)
The Label-Cover problem was introduced in [ABSS93] and shown there to be quasiNP -hard to approximate to within a factor of 2 log 1\Gammaffi n for any constant ffi ? 0. This combinatorial graph...
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Namely, we prove that witnesses for membership in any NP language can be...
Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
We show that given oracle access to a subroutine which returns approximate closest vectors in a lattice, one may find in polynomial-time approximate shortest vectors in a lattice. The level of...
PCP characterizations of NP: Towards a polynomially-small error-probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given...
The current proof of the PCP Theorem (i.e., N P = PCP(log, O(1))) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the...
We introduce a new low-degree--test, a one that uses the restriction of low-degree polynomials to planes (i.e., affine sub-spaces of dimension 2), rather than the restriction to lines (i.e., affine...
A Combinatorial Consistency Lemma with application to proving the PCP Theorem (1997)
The current proof of the PCP Theorem (i.e., NP = PCP(log; O(1))) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the...
Interactive proofs and the hardness of approximating cliques (1996)
Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, Mario Szegedy
The contribution of this paper is two-fold. First, a connection is shown between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient...
Relating word and tree automata (1996)
Orna Kupferman, Shmuel Safra, Moshe Y. Vardi, Bell Laboratories, Tel Aviv
Abstract In the automata-theoretic approach to verification, we translate specifications to au-tomata. Complexity considerations motivate the distinction between different types of automata. Already...
Relating Word and Tree Automata (1996)
Orna Kupferman, Shmuel Safra, Moshe Y. Vardi
In the automata-theoretic approach to verification, we translate specifications to automata. Complexity considerations motivate the distinction between different types of automata. Already in the...
A Sub-Constant Error-Probability PCP Characterization of NP - PART II: The Consistency Test (1996)
This paper introduces a new consistency-test for a class of codes, referred to as geometric-codes, and proves the test to be of small error-probability. This consistency-test enables us to conclude a...
A Sub-Constant Error-Probability PCP Characterization of NP - PART I: The Main Proof (1996)
This paper establishes a new characterization of NP in terms of PCP, being the first such exact characterization to exhibit a sub-constant error-probability with constant number of accesses....
Interactive Proofs and the Hardness of Approximating Cliques (1995)
Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, Mario Szegedy
The contribution of this paper is two-fold. First, a connection is shown between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient...
A Well-Characterized Approximation Problem (1993)
Johan Håstad, Steven Phillips, Shmuel Safra
We consider the following NP optimization problem: Given a set of polynomials P i (x), i = 1 : : : s of degree at most 2 over GF [p] in n variables, find a root common to as many as possible of the...
Complexity of Automata on Infinite Objects (1989)
We investigate in this thesis problems concerning the complexity of translation among, and decision procedure for, different types of finite automata on infinite words (!- automata). An !-automaton...