A proof of Green’s conjecture regarding the removal properties of sets of linear equations (2009)
A system of ℓ linear equations in p unknowns Mx = b is said to have the removal property if every set S ⊆ {1,..., n} which contains o(n p−ℓ) solutions of Mx = b can be turned into a set S ′...
The Effect of Induced Subgraphs on Quasi-Randomness (2009)
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P “behaves ” like a truly random one. In the...
On the Density of a Graph and its Blowup (2009)
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n, p) contains the smallest density of copies of Kt,t, the complete...
Artur Czumaj, Asaf Shapira, Christian Sohler
We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and...
Color-Critical Graphs Have Logarithmic Circumference (2009)
A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least log...
On the Density of a Graph and its Blowup (2009)
Shapira, Asaf, Yuster, Raphael
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n,p) contains the smallest density of copies of K_{t,t}, the...
The Effect of Induced Subgraphs on Quasi-Randomness (2009)
Shapira, Asaf, Yuster, Raphael
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P "behaves" like a truly random one. In the context...
Multigraphs (only) satisfy a weak triangle removal lemma (2009)
Shapira, Asaf, Yuster, Raphael
The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can be extended to...
All-Pairs Shortest Paths with a Sublinear Additive Error (2009)
We show that for every 0 ≤ p ≤ 1 there is an O(n 2.575−p/(7.4−2.3p) ) time algorithm that given a directed graph with small positive integer weights, estimates the length of the shortest path...
The Effect of Induced Subgraphs on Quasi-Randomness ∗ (2008)
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P “behaves ” like a truly random one. In the...
Can a Graph Have Distinct Regular Partitions? ∗ (2008)
Noga Alon, Asaf Shapira, Uri Stav
The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular partition of its vertex set. In this paper we address the following problem: can a graph...
Space Complexity vs. Query Complexity ∗ (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far”...
Can a Graph Have Distinct Regular Partitions? ∗ (2008)
Noga Alon, Asaf Shapira, Uri Stav
The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph...
A separation theorem in property testing (2008)
Consider the following seemingly rhetorical question: Is it crucial for a property-tester to know the error parameter ɛ in advance? Previous papers dealing with various testing problems, suggest...
Approximate Hypergraph Partitioning and Applications (2008)
Eldar Fischer, Arie Matsliah, Asaf Shapira
We show that any partition-problem of hypergraphs has an O(n) time approximate partitioning algorithm and an efficient property tester. This extends the results of Goldreich, Goldwasser and Ron who...
Approximate Hypergraph Partitioning and Applications (2008)
Eldar Fischer, Arie Matsliah, Asaf Shapira
Abstract We show that any partition-problem of hypergraphs has a sublinear O(n) time algorithm(where n is the number of vertices) with the following property: Given an input hypergraph H,which...
A Proof of Green's Conjecture Regarding the Removal Properties of Sets of Linear Equations (2008)
A system of \ell linear equations in p unknowns Mx=b is said to have the removal property if every set S \subseteq {1,...,n} which contains o(n^{p-\ell}) solutions of Mx=b can be turned into a set S'...
Testing hereditary properties of non-expanding bounded-degree graphs (2008)
Artur Czumaj, Asaf Shapira, Christian Sohler
We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and...
Space Complexity vs. Query Complexity (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Abstract. Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is...
Oded Lachish, Ilan Newman, Asaf Shapira
Abstract. Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is...
Behrend-type constructions for sets of linear equations (2008)
A linear equation on k unknowns is called a (k, h)-equation if it is of the form � k i=1 aixi = 0, with ai ∈ {−h,..., h} and � ai = 0. For a (k, h)-equation E, let rE(n) denote the size of...
A Note on Maximizing the Spread of Influence in Social Networks (2008)
Abstract. We consider the spread maximization problem that was defined by Domingos and Richardson [7, 22]. In this problem, we are given a social network represented as a graph and are required to...
The Effect of Induced Subgraphs on Quasi-Randomness (2008)
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P “behaves ” like a truly random one. In the...
Approximate Hypergraph Partitioning and Applications (2008)
Eldar Fischer, Arie Matsliah, Asaf Shapira
We show that any partition-problem of hypergraphs has an O(n) time approximate partitioning algorithm and an efficient property tester. This extends the results of Goldreich, Goldwasser and Ron who...
A separation theorem in property testing (2008)
Consider the following seemingly rhetorical question: Is it crucial for a property-tester to know the error parameter ɛ in advance? Previous papers dealing with various testing problems, suggest...
Testing the Expansion of a Graph (2008)
We study the problem of testing the expansion of graphs with bounded degree d in sublinear time. A graph is said to be an αexpander if every vertex set U ⊂ V of size at most 1|V | has a neigh-2...
Space Complexity vs. Query Complexity ∗ (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far”...
Can a Graph Have Distinct Regular Partitions? ∗ (2008)
Noga Alon, Asaf Shapira, Uri Stav
The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph...
Every Minor-Closed Property of Sparse Graphs is Testable (2008)
Benjamini, Itai, Schramm, Oded, Shapira, Asaf
Suppose $G$ is a graph with degrees bounded by $d$, and one needs to remove more than $\epsilon n$ of its edges in order to make it planar. We show that in this case the statistics of local...
Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1, d]. We say that Φ is ɛ-far from...
Let be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1; d]. We say that is -far from satisable,...
This work was carried out under the supervision of Prof. Noga Alon
Additive approximation for edge-deletion problems (2007)
Alon, Noga, Shapira, Asaf, Sudakov, Benny
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the...
An elementary construction of constant-degree expanders (2007)
Noga Alon, Oded Schwartz, Asaf Shapira
We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by [14] to give an iterative construction of...
Quasi-randomness and the distribution of copies of a fixed graph (2007)
We show that if a graph G has the property that all subsets of vertices of size n/4 contain the âcorrectâ number of triangles one would expect to find in a random graph G(n, 1 2), then G...
Every minor-closed property of sparse graphs is testable (2007)
Itai Benjamini, Oded Schramm, Asaf Shapira
Suppose G is a graph of bounded degree d, and one needs to remove ɛn of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of G is...
Every minor-closed property of sparse graphs is testable (2007)
Itai Benjamini, Oded Schramm, Asaf Shapira
Suppose G is a graph with degrees bounded by d, and one needs to remove more than ǫn of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around...
An elementary construction of constant-degree expanders (2007)
Noga Alon, Oded Schwartz, Asaf Shapira
We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by [14] to give an iterative construction of...
All-Pairs Bottleneck Paths in Vertex Weighted Graphs (2007)
Asaf Shapira, Raphael Yuster, Uri Zwick
Let G = (V, E, w) be a directed graph, where w: V → R is an arbitrary weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex...
All-Pairs Bottleneck Paths in Vertex Weighted Graphs (2007)
Asaf Shapira, Raphael Yuster, Uri Zwick
Let G = (V, E, w) be a directed graph, where w: V → R is an arbitrary weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex...
Every minor-closed property of sparse graphs is testable (2007)
Itai Benjamini, Oded Schramm, Asaf Shapira
Testing a property P of graphs in the bounded degree model is the following computational problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning testing dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
Thesis Prepared Under the Supervision of (2006)
The Raymond, Beverly Sackler, Faculty Exact Sciences, Asaf Shapira, Prof Noga Alon
ii
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
SHAPIRA: On an extremal hypergraph problem of Brown, Erdős and Sós (2005)
Let fr(n, v, e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi...
Every monotone graph property is testable (2005)
A graph property is called monotone if it is closed under removal of edges and vertices. Many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract...
Homomorphisms in graph property testing - A survey (2005)
on the occasion of his 60 th birthday
Linear equation, arithmetic progressions and hypergraph property testing (2005)
For a fixed k-uniform hypergraph D (k-graph for short, k ≥ 3), we say that a k-graph H) if it contains no copy (resp. induced copy) of D. Our goal in satisfies property PD (resp. P ∗ D this paper...
Linear equation, arithmetic progressions and hypergraph property testing (2005)
Abstract: For a fixed k-uniform hypergraph D (k-graph for short, k ≥ 3), we say that a k-graph H satisfies property PD (or property P ∗ D) if it contains no copy (or no induced copy) of D. Our...
Additive approximation for edge-deletion problems (2005)
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...
SHAPIRA: On an extremal hypergraph problem of Brown, Erdős and Sós (2005)
Let fr(n, v, e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi...
A characterization of the (natural) graph properties testable with one-sided error (2005)
The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property-testing. Our main result in this paper is a...
Additive approximation for edge-deletion problems (2005)
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...
Every monotone graph property is testable (2005)
A graph property is called monotone if it is closed under removal of edges and vertices. Many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract...
Homomorphisms in graph property testing - A survey (2005)
on the occasion of his 60 th birthday
Additive approximation for edge-deletion problems (2005)
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...
Linear equation, arithmetic progressions and hypergraph property testing (2005)
For a fixed k-uniform hypergraph D (k-graph for short, k ≥ 3), we say that a k-graph H) if it contains no copy (resp. induced copy) of D. Our goal in satisfies property PD (resp. P ∗ D this paper...
A characterization of the (natural) graph properties testable with one-sided error (2005)
The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property-testing. Our main result in this paper is a...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
Testing subgraphs in directed graphs (2003)
Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ɛn2 edges have to be deleted from it to make it H-free. We show that in this case G...
Testing subgraphs in directed graphs (2003)
Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ɛn2 edges have to be deleted from it to make it H-free. We show that in this case G...