Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We study the relation between the query complexity of adaptive and nonadaptive testers in the dense graph model. It has been known for a couple of decades that the query complexity of nonadaptive testers is at most quadratic in the query complexity of adaptive testers. We show that this general result is essentially tight; that is, there exist graph properties for which any nonadaptive tester must have query complexity that is almost quadratic in the query complexity of the best general (i.e., adaptive) tester. More generally, for every q: N→N such that q(n)≤n−−√ and constant c∈[1,2], we show a graph property that is testable in Θ(q(n)) queries, but its nonadaptive query complexity is Θ(q(n)c), omitting poly(log n) factors and ignoring the effect of the proximity parameter ϵ. Furthermore, the upper bounds hold for onesided error testers, and are at most quadratic in 1/ϵ. These results are obtained through the use of general reductions that transport properties of ordered structured (like bit strings) to those of unordered structures (like unlabeled graphs). The main features of these reductions are queryefficiency and preservation of distance to the properties. This method was initiated in our prior work (ECCC, TR20149), and we significantly extend itmore »

A graph G is called {\em selfordered} (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from G to any graph that is isomorphic to G. We say that G=(VE) is {\em robustly selfordered}if the size of the symmetric difference between E and the edgeset of the graph obtained by permuting V using any permutation :VV is proportional to the number of nonfixedpoints of . In this work, we initiate the study of the structure, construction and utility of robustly selfordered graphs. We show that robustly selfordered boundeddegree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense. Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomialtime (i.e., in time that is polylogarithmic in the size of the graph). We provide two very different constructions, in tools and structure. The first, a direct construction, is based on proving a sufficient condition for robust selfordering, which requires that an auxiliary graph, on {\em pairs} of vertices of the original graph, is expanding. In this case the original graph is (not only robustly selfordered but) also expanding. Themore »

Raz, Ran (Ed.)We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the wellstudied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proofcomplexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proofmore »

The object of study of this paper is the following multideterminantal algebraic variety, SINGn, m, which captures the symbolic determinant identity testing (SDIT) problem (a canonical version of the polynomial identity testing (PIT) problem), and plays a central role in algebra, algebraic geometry and computational complexity theory. SINGn, m is the set of all mtuples of n×n complex matrices which span only singular matrices. In other words, the determinant of any linear combination of the matrices in such a tuple vanishes. The algorithmic complexity of testing membership in SINGn, m is a central question in computational complexity. Having almost a trivial probabilistic algorithm, finding an efficient deterministic algorithm is a holy grail of derandomization, and to top it, will imply superpolynomial circuit lower bounds! A sequence of recent works suggests efficient deterministic “geodesic descent” algorithms for memberships in a general class of algebraic varieties, namely the null cones of (reductive) linear group actions. Can such algorithms be used for the problem above? Our main result is negative: SINGn, m is not the null cone of any such group action! This stands in stark contrast to a noncommutative analog of this variety (for which such algorithms work), and points to anmore »