All reports by Author Asaf Shapira:

__
TR18-007
| 9th January 2018
__

Lior Gishboliner, Asaf Shapira#### A Generalized Turan Problem and its Applications

__
TR15-019
| 3rd February 2015
__

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira#### Constructing Near Spanning Trees with Few Local Inspections

__
TR13-059
| 9th April 2013
__

Lior Gishboliner, Asaf Shapira#### Deterministic vs Non-deterministic Graph Property Testing

__
TR12-035
| 5th April 2012
__

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler#### Finding Cycles and Trees in Sublinear Time

Revisions: 1
,
Comments: 1

__
TR11-075
| 6th May 2011
__

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira#### Testing Odd-Cycle-Freeness in Boolean Functions

__
TR11-013
| 3rd February 2011
__

Ronitt Rubinfeld, Asaf Shapira#### Sublinear Time Algorithms

__
TR10-161
| 25th October 2010
__

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira#### A Unified Framework for Testing Linear-Invariant Properties

__
TR08-010
| 17th January 2008
__

Itai Benjamini, Oded Schramm, Asaf Shapira#### Every Minor-Closed Property of Sparse Graphs is Testable

__
TR07-118
| 27th November 2007
__

Asaf Nachmias, Asaf Shapira#### Testing the Expansion of a Graph

__
TR07-083
| 23rd August 2007
__

Artur Czumaj, Asaf Shapira, Christian Sohler#### Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs

__
TR06-119
| 13th September 2006
__

Noga Alon, Oded Schwartz, Asaf Shapira#### An Elementary Construction of Constant-Degree Expanders

__
TR06-103
| 5th July 2006
__

Oded Lachish, Ilan Newman, Asaf Shapira#### Space Complexity vs. Query Complexity

__
TR05-085
| 5th August 2005
__

Asaf Shapira, Noga Alon#### Homomorphisms in Graph Property Testing - A Survey

Lior Gishboliner, Asaf Shapira

Our first theorem in this papers is a hierarchy theorem for the query complexity of testing graph properties with $1$-sided error; more precisely, we show that for every super-polynomial $f$, there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$. No result of this type was previously known for ... more >>>

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

Lior Gishboliner, Asaf Shapira

A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P ... more >>>

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.

The complexity of these algorithms is related to the distance

of the graph from being ...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

Ronitt Rubinfeld, Asaf Shapira

Sublinear time algorithms represent a new paradigm

in computing, where an algorithm must give some sort

of an answer after inspecting only a very small portion

of the input. We discuss the types of answers that

one can hope to achieve in this setting.

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira

The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufman and Sudan (STOC 2008). Invariance with respect to F_2-linear transformations is arguably the most common symmetry exhibited by natural properties of Boolean ... more >>>

Itai Benjamini, Oded Schramm, Asaf Shapira

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>

Asaf Nachmias, Asaf Shapira

We study the problem of testing the expansion of

graphs with bounded degree d in sublinear time. A graph is said to

be an \alpha-expander if every vertex set U \subset V of size at

most |V|/2 has a neighborhood of size at least \alpha|U|.

We show that the algorithm ... more >>>

Artur Czumaj, Asaf Shapira, Christian Sohler

We study property testing in the model of bounded degree graphs. It

is well known that in this model many graph properties cannot be

tested with a constant number of queries and it seems reasonable to

conjecture that only few are testable with o(sqrt{n}) queries.

Therefore in this paper ...
more >>>

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, which we analyze using an elementary

combinatorial argument. The construction applies the replacement

product (only twice!) to turn the Cayley expanders of \cite{AR},

whose degree is polylog n, into constant degree

expanders.

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''

from satisfying it. The main focus of property testing is in

identifying large families of properties that can be ...
more >>>

Asaf Shapira, Noga Alon

Property-testers are fast randomized algorithms for distinguishing

between graphs (and other combinatorial structures) satisfying a

certain property, from those that are far from satisfying it. In

many cases one can design property-testers whose running time is in

fact {\em independent} of the size of the input. In this paper we

more >>>