Complexity-Theoretic Hierarchies Induced by Fragments of Gödel’s T

We introduce two hierarchies of unknown ordinal height. The hierarchies are induced by natural fragments of a calculus based on finite types and Gödel’s T, and all the classes in the hierarchies are uniformly defined without referring to explicit bounds. Deterministic complexity classes like logspace, p, pspace, linspace and exp are captured by the hierarchies. Typical subrecursive classes are also captured, e.g. the small relational Grzegorczyk classes ? _* ⁰ , ? _* ¹ and ? _* ² .     

Minimal quadrature formulae for the spaces H 2 R and L 2 R . A unified interpolatory approach

We consider minimal quadrature formulae for the Hilbert spacesH ₂ ^R andL ₂ ^R consisting of functions which are analytical on the open disc with radiusR and centre at the origin; the inner products are the boundary contour integral forH ₂ ^R and the area integral over the disc forL ₂ ^R . Such formulae can be viewed as interpolatory, generalizing—in two ways—Markoff's idea to construct the classical Gaussian quadratur formulae. This can be done simultaneously for both spaces using the same Hermitian interpolating operator. The advantage of this approach to minimal formulae is that we get a nonlinear system of equations for the nodes of the minimal formulae alone, in contrast to the coupled system for nodes and weights which arises from the minimality conditions. The uncoupled system that we obtain is numerically solvable for reasonable numbers of nodes and numerical tests show that the resulting minimal formulae are very well suited for the integration of functions with boundary singularities.     

Complexity of presburger arithmetic with fixed quantifier dimension

It is shown that the decision problem for formulas in Presburger arithmetic with quantifier prefix [?₁?₂ … ? _m ?³] (form odd) and [?₁?₂ … ? _m ?³] (form even) is complete for the class Σ _m ^p of the polynomial-time hierarchy. Furthermore, the prefix type [????] is complete for Σ ₂ ^p , and the prefix type [??] is complete for NP. This improves results (and solves a problem left open) by Grädel [7].     

Ritz-Galerkin Verfahren für normale Operatoren im Hilbertraum

Interpreting the Ritz method as a procedure to compute elements of best approximation for the norm ‖z‖ _R ² =(Az, z), similar methods are obtained in substituting ‖ ‖ _g with ‖z‖ _g =‖g(A)z‖ for a suitable functiong in place of ‖ ‖ _R . Such methods are applicable to large classes of linear operators. Taking bounded or unbounded, normal operators forA and polynomials in the variablesw and \(\bar w\) forg it is demonstrated how to get some estimations of the error.     

The Equivalence of Sampling and Searching

In a sampling problem, we are given an input x∈{0,1} ⁿ , and asked to sample approximately from a probability distribution \(\mathcal{D}_{x}\) over \(\operatorname{poly} ( n ) \) -bit strings. In a search problem, we are given an input x∈{0,1} ⁿ , and asked to find a member of a nonempty set A _x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity to show that sampling and search problems are “essentially equivalent.” More precisely, for any sampling problem S, there exists a search problem R _S such that, if \(\mathcal{C}\) is any “reasonable” complexity class, then R _S is in the search version of \(\mathcal{C}\) if and only if S is in the sampling version. What makes this nontrivial is that the same R _S works for every  \(\mathcal{C}\) . As an application, we prove the surprising result that SampP=SampBQP if and only if FBPP=FBQP. In other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve.     

Two-Way Automata Versus Logarithmic Space

We strengthen a previously known connection between the size complexity of two-way finite automata ( ) and the space complexity of Turing machines (tms). Specifically, we prove that

every s-state has a poly(s)-state that agrees with it on all inputs of length ≤s if and only if NL?L/poly, and

every s-state has a poly(s)-state that agrees with it on all inputs of length ≤2 ^s if and only if NLL?LL/polylog.

Here, and are the deterministic and nondeterministic , NL and L/poly are the standard classes of languages recognizable in logarithmic space by nondeterministic tms and by deterministic tms with access to polynomially long advice, and NLL and LL/polylog are the corresponding complexity classes for space O(loglogn) and advice length poly(logn). Our arguments strengthen and extend an old theorem by Berman and Lingas and can be used to obtain variants of the above statements for other modes of computation or other combinations of bounds for the input length, the space usage, and the length of advice.     

A new PAC bound for intersection-closed concept classes

For hyper-rectangles in $\mathbb{R}^{d}$ Auer (1997) proved a PAC bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ , where $\varepsilon$ and $\delta$ are the accuracy and confidence parameters. It is still an open question whether one can obtain the same bound for intersection-closed concept classes of VC-dimension $d$ in general. We present a step towards a solution of this problem showing on one hand a new PAC bound of $O(\frac{1}{\varepsilon}(d\log d + \log \frac{1}{\delta}))$ for arbitrary intersection-closed concept classes, complementing the well-known bounds $O(\frac{1}{\varepsilon}(\log \frac{1}{\delta}+d\log \frac{1}{\varepsilon}))$ and $O(\frac{d}{\varepsilon}\log \frac{1}{\delta})$ of Blumer et al. and (1989) and Haussler, Littlestone and Warmuth (1994). Our bound is established using the closure algorithm, that generates as its hypothesis the intersection of all concepts that are consistent with the positive training examples. On the other hand, we show that many intersection-closed concept classes including e.g. maximum intersection-closed classes satisfy an additional combinatorial property that allows a proof of the optimal bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ . For such improved bounds the choice of the learning algorithm is crucial, as there are consistent learning algorithms that need $\Omega(\frac{1}{\varepsilon}(d\log\frac{1}{\varepsilon} +\log\frac{1}{\delta}))$ examples to learn some particular maximum intersection-closed concept classes.     

DNF sparsification and a faster deterministic counting algorithm

Given a DNF formula f on n variables, the two natural size measures are the number of terms or size s(f) and the maximum width of a term w(f). It is folklore that small DNF formulas can be made narrow: if a formula has m terms, it can be ${\epsilon}$ -approximated by a formula with width ${{\rm log}(m/{\epsilon})}$ . We prove a converse, showing that narrow formulas can be sparsified. More precisely, any width w DNF irrespective of its size can be ${\epsilon}$ -approximated by a width w DNF with at most ${(w\, {\rm log}(1/{\epsilon}))^{O(w)}}$ terms. We combine our sparsification result with the work of Luby & Velickovic (1991, Algorithmica 16(4/5):415–433, 1996) to give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a DNF. Given a formula on n variables with poly(n) terms, we give a deterministic ${n^{\tilde{O}({\rm log}\, {\rm log} (n))}}$ time algorithm that computes an additive ${\epsilon}$ approximation to the fraction of satisfying assignments of f for ${\epsilon = 1/{\rm poly}({\rm log}\, n)}$ . The previous best result due to Luby and Velickovic from nearly two decades ago had a run time of ${n^{{\rm exp}(O(\sqrt{{\rm log}\, {\rm log} n}))}}$ (Luby & Velickovic 1991, in Algorithmica 16(4/5):415–433, 1996).     

A complexity perspective on entailment of parameterized linear constraints

Extending linear constraints by admitting parameters allows for more abstract problem modeling and reasoning. A lot of focus has been given to conducting research that demonstrates the usefulness of parameterized linear constraints and implementing tools that utilize their modeling strength. However, there is no approach that considers basic theoretical tools related to such constraints that allow for reasoning over them. Hence, in this paper we introduce satisfiability with respect to polyhedral sets and entailment for the class of parameterized linear constraints. In order to study the computational complexities of these problems, we relate them to classes of quantified linear implications. The problem of satisfiability with respect to polyhedral sets is then shown to be co- $\mathbb{NP}$ hard. The entailment problem is also shown to be co- $\mathbb{NP}$ hard in its general form. Nevertheless, we characterize some subclasses for which this problem is in ?. Furthermore, we examine a weakening and a strengthening extension of the entailment problem. The weak entailment problem is proved to be $\mathbb{NP}$ complete. On the other hand, the strong entailment problem is shown to be co- $\mathbb{NP}$ hard.     

On Uniformity and Circuit Lower Bounds

We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Our results can be divided into two parts:

1. Lower bounds against medium-uniform circuits. Informally, a circuit class is “medium uniform” if it can be generated by an algorithmic process that is somewhat complex (stronger than LOGTIME) but not infeasible. Using a new kind of indirect diagonalization argument, we prove several new unconditional lower bounds against medium-uniform circuit classes, including: ? For all k, P is not contained in P-uniform SIZE(n ^k ). That is, for all k, there is a language \({L_k \in {\textsf P}}\) that does not have O(n ^k )-size circuits constructible in polynomial time. This improves Kannan’s lower bound from 1982 that NP is not in P-uniform SIZE(n ^k ) for any fixed k. ? For all k, NP is not in \({{\textsf P}^{\textsf NP}_{||}-{\textsf {uniform SIZE}}(n^k)}\) .This also improves Kannan’s theorem, but in a different way: the uniformity condition on the circuits is stronger than that on the language itself. ? For all k, LOGSPACE does not have LOGSPACE-uniform branching programs of size n ^k .
2. Eliminating non-uniformity and (non-uniform) circuit lower bounds. We complement these results by showing how to convert any potential simulation of LOGTIME-uniform NC ¹ in ACC ⁰/poly or TC ⁰/poly into a medium-uniform simulation using small advice. This lemma can be used to simplify the proof that faster SAT algorithms imply NEXP circuit lower bounds and leads to the following new connection: ? Consider the following task: given a TC ⁰ circuit C of n ^O(1) size, output yes when C is unsatisfiable, and output no when C has at least 2 ^n-2 satisfying assignments. (Behavior on other inputs can be arbitrary.) Clearly, this problem can be solved efficiently using randomness. If this problem can be solved deterministically in 2 ^n-ω(log n) time, then \({{\textsf{NEXP}} \not \subset {\textsf{TC}}^0/{\rm poly}}\) .

Another application is to derandomize randomized TC ⁰ simulations of NC ¹ on almost all inputs: ?Suppose \({{\textsf{NC}}^1 \subseteq {\textsf{BPTC}}^0}\) . Then, for every ε > 0 and every language L in NC ¹, there is a LOGTIME?uniform TC ⁰ circuit family of polynomial size recognizing a language L′ such that L and L′ differ on at most \({2^{n^{\epsilon}}}\) inputs of length n, for all n.     

On the power of unambiguity in log-space

We report progress on the NL versus UL problem.

We show that counting the number of s-t paths in graphs where the number of s-v paths for any v is bounded by a polynomial can be done in FUL: the unambiguous log-space function class. Several new upper bounds follow from this including ${{{ReachFewL} \subseteq {UL}}}$ and ${{{LFew} \subseteq {UL}^{FewL}}}$

We investigate the complexity of min-uniqueness—a central notion in studying the NL versus UL problem. In this regard we revisit the class OptL[log n] and introduce UOptL[log n], an unambiguous version of OptL[log n]. We investigate the relation between UOptL[log n] and other existing complexity classes.

We consider the unambiguous hierarchies over UL and UOptL[log n]. We show that the hierarchy over UOptL[log n] collapses. This implies that ${{{ULH} \subseteq {L}^{{promiseUL}}}}$ thus collapsing the UL hierarchy.

We show that the reachability problem over graphs embedded on 3 pages is complete for NL. This contrasts with the reachability problem over graphs embedded on 2 pages, which is log-space equivalent to the reachability problem in planar graphs and hence is in UL.

     

Pseudorandom generators for combinatorial checkerboards

We define a combinatorial checkerboard to be a function f : {1, . . . , m} ^d → {1,?1} of the form ${f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)}$ for some functions f _i : {1, . . . , m} → {1,?1}. This is a variant of combinatorial rectangles, which can be defined in the same way but using {0, 1} instead of {1,?1}. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case m = 2. We construct a pseudorandom generator that ${\epsilon}$ -fools all combinatorial checkerboards with seed length ${O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2} \frac{1}{\epsilon}\bigr)}$ . Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length ${O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)}$ . Our seed length is better except when ${\frac{1}{\epsilon}\geq d^{\omega(\log d)}}$ .     

Moment inequalities for random variables in computational geometry

LetX ₁,...,X _n be independent identically distributedR ^d -valued random vectors, and letA _n =A(X ₁,...,X _n ) be a subset of {X ₁,...,X _n }, invariant under permutations of the data, and possessing the inclusion property (X ₁ ∈A _n impliesX ₁ ∈A _i for alli≤n). For example, the convex hull, the collection of all maximal vectors, the set of isolated points and other structures satisfy these conditions. LetN _n be the cardinality ofA _n . We show that for allp≥1, there exists a universal constantC _p >0 such thatE(N _n ^p )≤C _p max (1,E ^p ) where . This complements Jensen's lower bound for thep-th moment:E(N _n ^p )≥E ^p (N _n ). The inequality is applied to the expected time analysis of algorithms in computational geometry. We also give necessary and sufficient conditions onE(N _n ) for linear expected time behaviour of divide-and-conquer methods for findingA _n .     

Non-determinism and weak constraints in Datalog

This paper introduces a simple and powerful extension of stratified DATALOG which permits to express various DB-complexity classes. The new language, called DATALOG^¬s,c,p , extends DATALOG with stratified negation, a non-deterministic construct, calledchoice, and a weak form of constraints, calledpreference rules, that is, constraints that should be respected but, if they cannot be eventually enforced, they only invalidate the portions of the program which they are concerned with. Although DATALOG with stratified negation is not able to express all polynomial time queries,²⁰⁾ the introduction of the non-deterministic constructchoice permits to express, exactly, the ‘deterministic fragment’ of the class of DB-queriesP, under the non-deterministic semantics,NP, under the possible semantics, and coNP, under the certain semantics. The introduction of preference rules, further increases the expressive power of the language, and permits to express the complexity classes Σ ₂ ^p , under the possibility semantics, and Π ₂ ^p , under the certainty semantics.     

On the hilbert transform of bounded bandlimited signals

In this paper we analyze the Hilbert transform and existence of the analytical signal for the space B _?? ^?? of bandlimited signals that are bounded on the real axis. Originally, the theory was developed for signals in L ²(?) and then extended to larger signal spaces. While it is well known that the common integral representation of the Hilbert transform may diverge for some signals in B _?? ^?? and that the Hilbert transform is not a bounded operator on B _?? ^?? , it is nevertheless possible to define the Hilbert transform for the space B _?? ^?? . We use a definition that is based on the H ¹-BMO(?) duality. This abstract definition, which can be used for general bounded signals, gives no constructive procedure to compute the Hilbert transform. However, for the practically important special case of bounded bandlimited signals, we can provide such an explicit procedure by giving a closed-form expression for the Hilbert transform. Further, it is shown that the Hilbert transform of a signal in B _?? ^?? is still bandlimited but not necessarily bounded. With these results we continue the work of [1, 2].     

Polynomial Kernelizations for MIN F+Π1 and MAX NP

It has been observed in many places that constant-factor approximable problems often admit polynomial or even linear problem kernels for their decision versions, e.g., Vertex Cover, Feedback Vertex Set, and Triangle Packing. While there exist examples like Bin Packing, which does not admit any kernel unless P = NP, there apparently is a strong relation between these two polynomial-time techniques. We add to this picture by showing that the natural decision versions of all problems in two prominent classes of constant-factor approximable problems, namely MIN F⁺Π₁ and MAX NP, admit polynomial problem kernels. Problems in MAX SNP, a subclass of MAX NP, are shown to admit kernels with a linear base set, e.g., the set of vertices of a graph. This extends results of Cai and Chen (J. Comput. Syst. Sci. 54(3): 465–474, 1997), stating that the standard parameterizations of problems in MAX SNP and MIN F⁺Π₁ are fixed-parameter tractable, and complements recent research on problems that do not admit polynomial kernelizations (Bodlaender et al. in J. Comput. Syst. Sci. 75(8): 423–434, 2009).     

Lower bounds for polynomial evaluation and interpolation problems

We show that there is a set of pointsp ₁,p ₂,...,p _n such that any arithmetic circuit of depthd for polynomial evaluation (or interpolation) at these points has size $$\Omega \left( {\frac{{n\log n}}{{\log (2 + d/\log n}}} \right).$$ Moreover, for circuits of sub-logarithmic depthd, we obtain a lower bound of Ω(dn ^1+1/d ) on its size.     

Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm

Let ${\mathcal{B}}$ be a centrally symmetric convex polygon of ?² and ‖p?q‖ be the distance between two points p,q∈?² in the normed plane whose unit ball is ${\mathcal{B}}$ . For a set T of n points (terminals) in ?², a ${\mathcal{B}}$ -network on T is a network N(T)=(V,E) with the property that its edges are parallel to the directions of ${\mathcal{B}}$ and for every pair of terminals t _i and t _j , the network N(T) contains a shortest ${\mathcal{B}}$ -path between them, i.e., a path of length ‖t _i ?t _j ‖. A minimum ${\mathcal{B}}$ -network on T is a ${\mathcal{B}}$ -network of minimum possible length. The problem of finding minimum ${\mathcal{B}}$ -networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) in the case when the unit ball ${\mathcal{B}}$ is a square (and hence the distance ‖p?q‖ is the l ₁ or the l _∞-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (Symposium on Computational Geometry, pp. 393–402, 2009) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4, 3, and 2) for the minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for the minimum ${\mathcal{B}}$ -network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (Chepoi et al. in Theor. Comput. Sci. 390:56–69, 2008, and APPROX-RANDOM, pp. 40–51, 2005) and subsequently used in other factor 2 approximation algorithms for the minimum Manhattan problem.     

Query-Efficient Locally Decodable Codes of Subexponential Length

A k-query locally decodable code (LDC) C : Σ ⁿ → Γ ^N encodes each message x into a codeword C(x) such that each symbol of x can be probabilistically recovered by querying only k coordinates of C(x), even after a constant fraction of the coordinates has been corrupted. Yekhanin (in J ACM 55:1–16, 2008) constructed a 3-query LDC of subexponential length, N = exp(exp(O(log n/log log n))), under the assumption that there are infinitely many Mersenne primes. Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) constructed a 3-query LDC of length ${N_{2}={\rm exp}({\rm exp} (O(\sqrt{\log n\log\log n})))}$ with no assumption, and a 2 ^r -query LDC of length ${N_{r}={\rm exp}({\rm exp}(O(\sqrt[r]{\log n(\log \log n)^{r-1}})))}$ , for every integer r ≥ 2. Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010) gave a composition method in Efremenko’s framework and constructed a 3 · 2 ^r-2-query LDC of length N _r , for every integer r ≥ 4, which improved the query complexity of Efremenko’s LDC of the same length by a factor of 3/4. The main ingredient of Efremenko’s construction is the Grolmusz construction for super-polynomial size set-systems with restricted intersections, over ${\mathbb{Z}_m}$ , where m possesses a certain “good” algebraic property (related to the “algebraic niceness” property of Yekhanin in J ACM 55:1–16, 2008). Efremenko constructed a 3-query LDC based on m = 511 and left as an open problem to find other numbers that offer the same property for LDC constructions. In this paper, we develop the algebraic theory behind the constructions of Yekhanin (in J ACM 55:1–16, 2008) and Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009), in an attempt to understand the “algebraic niceness” phenomenon in ${\mathbb{Z}_m}$ . We show that every integer m =  pq = 2 ^t ?1, where p, q, and t are prime, possesses the same good algebraic property as m = 511 that allows savings in query complexity. We identify 50 numbers of this form by computer search, which together with 511, are then applied to gain improvements on query complexity via Itoh and Suzuki’s composition method. More precisely, we construct a ${3^{\lceil r/2\rceil}}$ -query LDC for every positive integer r < 104 and a ${\left\lfloor (3/4)^{51} \cdot 2^{r}\right\rfloor}$ -query LDC for every integer r ≥ 104, both of length N _r , improving the 2 ^r queries used by Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) and 3 · 2 ^r-2 queries used by Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010). We also obtain new efficient private information retrieval (PIR) schemes from the new query-efficient LDCs.     

Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields

In this paper, we give the first construction of a pseudorandom generator, with seed length O(log n), for CC⁰[p], the class of constant-depth circuits with unbounded fan-in MOD _p gates, for some prime p. More accurately, the seed length of our generator is O(log n) for any constant error ${\epsilon > 0}$ . In fact, we obtain our generator by fooling distributions generated by low-degree polynomials, over ${\mathbb{F}_p}$ , when evaluated on the Boolean cube. This result significantly extends previous constructions that either required a long seed (Luby et al. 1993) or could only fool the distribution generated by linear functions over ${\mathbb{F}_p}$ , when evaluated on the Boolean cube (Lovett et al. 2009; Meka & Zuckerman 2009). En route of constructing our PRG, we prove two structural results for low-degree polynomials over finite fields that can be of independent interest.

1. Let f be an n-variate degree d polynomial over ${\mathbb{F}_p}$ . Then, for every ${\epsilon > 0}$ , there exists a subset ${S \subset [n]}$ , whose size depends only on d and ${\epsilon}$ , such that ${\sum_{\alpha \in \mathbb{F}_p^n: \alpha \ne 0, \alpha_S=0}|\hat{f}(\alpha)|^2 \leq \epsilon}$ . Namely, there is a constant size subset S such that the total weight of the nonzero Fourier coefficients that do not involve any variable from S is small.
2. Let f be an n-variate degree d polynomial over ${\mathbb{F}_p}$ . If the distribution of f when applied to uniform zero–one bits is ${\epsilon}$ -far (in statistical distance) from its distribution when applied to biased bits, then for every ${\delta > 0}$ , f can be approximated over zero–one bits, up to error δ, by a function of a small number (depending only on ${\epsilon,\delta}$ and d) of lower degree polynomials.