Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Asaf Shapira:

TR18-007 | 9th January 2018
Lior Gishboliner, Asaf Shapira

A Generalized Turan Problem and its Applications

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

TR15-019 | 3rd February 2015
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing Near Spanning Trees with Few Local Inspections

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

TR13-059 | 9th April 2013
Lior Gishboliner, Asaf Shapira

Deterministic vs Non-deterministic Graph Property Testing

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

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

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

TR11-075 | 6th May 2011
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Testing Odd-Cycle-Freeness in Boolean Functions

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

TR11-013 | 3rd February 2011
Ronitt Rubinfeld, Asaf Shapira

Sublinear Time Algorithms

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.

more >>>

TR10-161 | 25th October 2010
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira

A Unified Framework for Testing Linear-Invariant Properties

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

TR08-010 | 17th January 2008
Itai Benjamini, Oded Schramm, Asaf Shapira

Every Minor-Closed Property of Sparse Graphs is Testable

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

TR07-118 | 27th November 2007
Asaf Nachmias, Asaf Shapira

Testing the Expansion of a Graph

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

TR07-083 | 23rd August 2007
Artur Czumaj, Asaf Shapira, Christian Sohler

Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs

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

TR06-119 | 13th September 2006
Noga Alon, Oded Schwartz, Asaf Shapira

An Elementary Construction of Constant-Degree Expanders

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

... more >>>

TR06-103 | 5th July 2006
Oded Lachish, Ilan Newman, Asaf Shapira

Space Complexity vs. Query Complexity

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

TR05-085 | 5th August 2005
Asaf Shapira, Noga Alon

Homomorphisms in Graph Property Testing - A Survey

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

ISSN 1433-8092 | Imprint