Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GRAPH PROPERTIES:
Reports tagged with Graph Properties:
TR01-010 | 25th January 2001
Oded Goldreich, Luca Trevisan

#### Three Theorems regarding Testing Graph Properties.

Revisions: 1

Property testing is a relaxation of decision problems
in which it is required to distinguish {\sc yes}-instances
(i.e., objects having a predetermined property) from instances
that are far from any {\sc yes}-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation. ... more >>>

TR08-039 | 7th April 2008
Oded Goldreich, Dana Ron

#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

In this paper we consider two refined questions regarding
the query complexity of testing graph properties
The first question refers to the relation between adaptive
and non-adaptive testers, whereas the second question refers to
testability within complexity that
is inversely proportional to ... more >>>

TR08-041 | 10th April 2008
Oded Goldreich, Dana Ron

#### On Proximity Oblivious Testing

We initiate a systematic study of a special type of property testers.
These testers consist of repeating a basic test
for a number of times that depends on the proximity parameters,
whereas the basic test is oblivious of the proximity parameter.
We refer to such basic ... more >>>

TR08-097 | 14th November 2008
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

#### Hierarchy Theorems for Property Testing

Revisions: 1

Referring to the query complexity of property testing,
we prove the existence of a rich hierarchy of corresponding
complexity classes. That is, for any relevant function $q$,
we prove the existence of properties that have testing
complexity Theta(q).
Such results are proven in three standard
domains often considered in property ... more >>>

TR09-083 | 24th September 2009
Dana Ron, Mira Gonen, Yuval Shavitt

#### Counting Stars and Other Small Subgraphs in Sublinear Time

Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... more >>>

TR10-082 | 11th May 2010
Oded Goldreich

#### Introduction to Testing Graph Properties

of testing graph properties, while focusing on the main models
and issues involved. No attempt is made to provide a
comprehensive survey of this study, and specific results
are often mentioned merely as illustrations of general ... more >>>

TR13-109 | 11th August 2013
Oded Goldreich, Dana Ron

#### On Sample-Based Testers

Revisions: 1

The standard definition of property testing endows the tester with the ability to make arbitrary queries to elements''
of the tested object.
In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.
While sample-based testers were defined by
Goldreich, Goldwasser, and Ron ({\em JACM}\/ ... more >>>

TR16-053 | 6th April 2016
Jiawei Gao, Russell Impagliazzo

#### Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>

TR18-045 | 6th March 2018
Oded Goldreich, Dana Ron

#### The Subgraph Testing Model

Revisions: 2

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.
The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.
The tester is ... more >>>

TR19-102 | 10th August 2019
Oded Goldreich

#### Testing Isomorphism in the Bounded-Degree Graph Model

Revisions: 1

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.
We essentially determine the query complexity of these testing problems in the special case of ... more >>>

TR21-122 | 24th August 2021
Sabyasachi Basu, Akash Kumar, C. Seshadhri

#### The complexity of testing all properties of planar graphs, and the role of isomorphism

Consider property testing on bounded degree graphs and let $\varepsilon > 0$ denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on $\varepsilon$. Recent advances in testing minor-freeness have proven that ... more >>>

TR22-135 | 18th September 2022
Rahul Chugh, Supartha Poddar, Swagato Sanyal

#### Decision Tree Complexity versus Block Sensitivity and Degree

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>

ISSN 1433-8092 | Imprint