Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with graph property testing:
TR06-089 | 16th July 2006
Sofya Raskhodnikova, Adam Smith

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

We show that in the bounded degree model for graph property testing,
adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>

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

TR19-083 | 4th June 2019
Lior Gishboliner, Asaf Shapira

Testing Graphs against an Unknown Distribution

Revisions: 1

The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property $\mathcal{P}$ is said ... more >>>

TR20-190 | 29th November 2020
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

Erasure-Resilient Sublinear-Time Graph Algorithms

We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected ... more >>>

ISSN 1433-8092 | Imprint