Computer Science - Computational Complexity Publications (50)


Computer Science - Computational Complexity Publications

We introduce a "workable" notion of degree for non-homogeneous polynomial ideals and formulate and prove ideal theoretic B\'ezout Inequalities for the sum of two ideals in terms of this notion of degree and the degree of generators. We compute probabilistically the degree of an equidimensional ideal. Read More

This paper investigates the algorithmic dimension spectra of lines in the Euclidean plane. Given any line L with slope a and vertical intercept b, the dimension spectrum sp(L) is the set of all effective Hausdorff dimensions of individual points on L. We draw on Kolmogorov complexity and geometrical arguments to show that if the effective Hausdorff dimension dim(a, b) is equal to the effective packing dimension Dim(a, b), then sp(L) contains a unit interval. Read More

How many quantum queries are required to determine the coefficients of a degree-$d$ polynomial in $n$ variables? We present and analyze quantum algorithms for this multivariate polynomial interpolation problem over the fields $\mathbb{F}_q$, $\mathbb{R}$, and $\mathbb{C}$. We show that $k_{\mathbb{C}}$ and $2k_{\mathbb{C}}$ queries suffice to achieve probability $1$ for $\mathbb{C}$ and $\mathbb{R}$, respectively, where $k_{\mathbb{C}}=\smash{\lceil\frac{1}{n+1}{n+d\choose d}\rceil}$ except for $d=2$ and four other special cases. For $\mathbb{F}_q$, we show that $\smash{\lceil\frac{d}{n+d}{n+d\choose d}\rceil}$ queries suffice to achieve probability approaching $1$ for large field order $q$. Read More

We prove that the set of all solutions for twisted word equations with regular constraints is an EDT0L language and can be computed in PSPACE. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide (in PSPACE) whether or not the solution set is finite, which was an open problem. Read More

We initiate a complexity theoretic study of the language based graph reachability problem (L-REACH) : Fix a language L. Given a graph whose edges are labeled with alphabet symbols of the language L and two special vertices s and t, test if there is path P from s to t in the graph such that the concatenation of the symbols seen from s to t in the path P forms a string in the language L. We study variants of this problem with different graph classes and different language classes and obtain complexity theoretic characterizations for all of them. Read More

In this paper we propose augmented interval Markov chains (AIMCs): a generalisation of the familiar interval Markov chains (IMCs) where uncertain transition probabilities are in addition allowed to depend on one another. This new model preserves the flexibility afforded by IMCs for describing stochastic systems where the parameters are unclear, for example due to measurement error, but also allows us to specify transitions with probabilities known to be identical, thereby lending further expressivity. The focus of this paper is reachability in AIMCs. Read More

Let $M$ be a real $r\times c$ matrix and let $k$ be a positive integer. In the column subset selection problem (CSSP), we need to minimize the quantity $\|M-SA\|$, where $A$ can be an arbitrary $k\times c$ matrix, and $S$ runs over all $r\times k$ submatrices of $M$. This problem and its applications in numerical linear algebra are being discussed for several decades, but its algorithmic complexity remained an open issue. Read More

We consider the problem of finding a homomorphism from an input digraph G to a fixed digraph H. We show that if H admits a weak-near-unanimity polymorphism $\phi$ then deciding whether G admits a homomorphism to H (HOM(H)) is polynomial time solvable. This confirms the conjecture of Bulatov, Jeavons, and Krokhin, in the form postulated by Maroti and McKenzie, and consequently implies the validity of the celebrated dichotomy conjecture due to Feder and Vardi. Read More

Boolean satisfiability (SAT) is a fundamental problem in computer science, which is one of the first proven $\mathbf{NP}$-complete problems. Although there is no known theoretically polynomial time algorithm for SAT, many heuristic SAT methods have been developed for practical problems. For the sake of efficiency, various techniques were explored, from discrete to continuous methods, from sequential to parallel programmings, from constrained to unconstrained optimizations, from deterministic to stochastic studies. Read More

We extend the framework by Kawamura and Cook for investigating computational complexity for operators occurring in analysis. This model is based on second-order complexity theory for functions on the Baire space, which is lifted to metric spaces by means of representations. Time is measured in terms of the length of the input encodings and the required output precision. Read More

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide whether or not a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the Surjective H-Colouring problem, which imposes the homomorphism to be vertex-surjective. Read More

The \emph{Orbit Problem} consists of determining, given a linear transformation $A$ on $\mathbb{Q}^d$, together with vectors $x$ and $y$, whether the orbit of $x$ under repeated applications of $A$ can ever reach $y$. This problem was famously shown to be decidable by Kannan and Lipton in the 1980s. In this paper, we are concerned with the problem of synthesising suitable \emph{invariants} $\mathcal{P} \subseteq \mathbb{R}^d$, \emph{i. Read More

In the context of two-party interactive quantum communication protocols, we study a recently defined notion of quantum information cost (QIC), which possesses most of the important properties of its classical analogue. Although this definition has the advantage to be valid for fully quantum inputs and tasks, its interpretation for classical tasks remained rather obscure. Also, the link between this new notion and other notions of information cost for quantum protocols that had previously appeared in the literature was not clear, if existent at all. Read More

In the \probrFix problem, we are given a graph $G$, a (non-proper) vertex-coloring $c : V(G) \to [r]$, and a positive integer $k$. The goal is to decide whether a proper $r$-coloring $c'$ is obtainable from $c$ by recoloring at most $k$ vertices of $G$. Recently, Junosza-Szaniawski, Liedloff, and Rz{\k{a}}{\. Read More

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity. Read More

A basic problem in information theory is the following: Let $\mathbf{P} = (\mathbf{X}, \mathbf{Y})$ be an arbitrary distribution where the marginals $\mathbf{X}$ and $\mathbf{Y}$ are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples $\{x_i\}_{i \ge 1}$ and Bob gets samples $\{y_i\}_{i \ge 1}$ and for all $i$, $(x_i, y_i) \sim \mathbf{P}$. What joint distributions $\mathbf{Q}$ can be simulated by Alice and Bob without any interaction? Classical works in information theory by G{\'a}cs-K{\"o}rner and Wyner answer this question when at least one of $\mathbf{P}$ or $\mathbf{Q}$ is the distribution on $\{0,1\} \times \{0,1\}$ where each marginal is unbiased and identical. Read More

Questions of noise stability play an important role in hardness of approximation in computer science as well as in the theory of voting. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of $\mathbb{R}^n$ for $n \geq 1$ to $k$ parts with given Gaussian measures $\mu_1,\ldots,\mu_k$. We call a partition $\epsilon$-optimal, if its noise stability is optimal up to an additive $\epsilon$. Read More

Two main techniques have been used so far to solve the #P-hard problem #SAT. The first one, used in practice, is based on an extension of DPLL for model counting called exhaustive DPLL. The second approach, more theoretical, exploits the structure of the input to compute the number of satisfying assignments by usually using a dynamic programming scheme on a decomposition of the formula. Read More

Several variants of linear logic have been proposed to characterize complexity classes in the proofs-as-programs correspondence. Light linear logic (LLL) ensures a polynomial bound on reduction time, and characterizes in this way polynomial time (Ptime). In this paper we study the complexity of linear logic proof-nets and propose three semantic criteria based on context semantics: stratification, dependence control and nesting. Read More

We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences, and ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and on conjunctive queries. We show that rewritability into FO and into monadic Datalog (MDLog) are decidable, and that rewritability into Datalog is decidable when the original query satisfies a certain condition related to equality. We establish 2NExpTime-completeness for all studied problems except rewritability into MDLog for which there remains a gap between 2NExpTime and 3ExpTime. Read More

The Church-Rosser theorem in the type-free lambda-calculus is well investigated both for beta-equality and beta-reduction. We provide a new proof of the theorem for beta-equality with no use of parallel reductions, but simply with Takahashi's translation (Gross-Knuth strategy). Based on this, upper bounds for reduction sequences on the theorem are obtained as the fourth level of the Grzegorczyk hierarchy. Read More

The TTE approach to Computable Analysis is the study of so-called representations (encodings for continuous objects such as reals, functions, and sets) with respect to the notions of computability they induce. A rich variety of such representations had been devised over the past decades, particularly regarding closed subsets of Euclidean space plus subclasses thereof (like compact subsets). In addition, they had been compared and classified with respect to both non-uniform computability of single sets and uniform computability of operators on sets. Read More

We prove the computational intractability of rotating and placing $n$ square tiles into a $1 \times n$ array such that adjacent tiles are compatible--either equal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes, as in jigsaw puzzles. Beyond basic NP-hardness, we prove that it is NP-hard even to approximately maximize the number of placed tiles (allowing blanks), while satisfying the compatibility constraint between nonblank tiles, within a factor of 0.9999999851. Read More

Semidefinite programs (SDPs) are a framework for exact or approximate optimization that have widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs. These are based on new limitations on the sum-of-squares (SoS) hierarchy in approximating two particularly important sets in quantum information theory, where previously no $\omega(1)$-round integrality gaps were known: the set of separable (i. Read More

Consider a universal Turing machine that produces a partial or total function (or a binary stream), based on the answers to the binary queries that it makes during the computation. We study the probability that the machine will produce a computable function when it is given a random stream of bits as the answers to its queries. Surprisingly, we find that these probabilities are the entire class of real numbers in (0, 1) that can be written as the difference of two halting probabilities relative to the halting problem. Read More

In studies of social dynamics, cohesion refers to a group's tendency to stay in unity, which -- as argued in sociometry -- arises from the network topology of interpersonal ties between members of the group. We follow this idea and propose a game-based model of cohesion that not only relies on the social network, but also reflects individuals' social needs. In particular, our model is a type of cooperative games where players may gain popularity by strategically forming groups. Read More

Previous work of the author [39] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC$^0$ formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence $\Phi$ of quantifier-rank $k$ is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence $\Psi$ of quantifier-rank $k^{O(1)}$. Read More

In theoretical quantum computer science, understanding where and how computational speed-ups occur while applying quantum properties is a primary goal. In this paper, we study such problem under the framework of Quantum Query Model and prove the significance of $L_1$-norm in the simulation of a given quantum algorithm. This result is presented by upper-bounds for the quotient between optimal classical complexity and the complexity of the given quantum algorithm. Read More

A path in a vertex-colored graph $G$ is \emph{vertex rainbow} if all of its internal vertices have a distinct color. The graph $G$ is said to be \emph{rainbow vertex connected} if there is a vertex rainbow path between every pair of its vertices. Similarly, the graph $G$ is \emph{strongly rainbow vertex connected} if there is a shortest path which is vertex rainbow between every pair of its vertices. Read More

While the solution counting problem for propositional satisfiability (#SAT) has received renewed attention in recent years, this research trend has not affected other AI solving paradigms like answer set programming (ASP). Although ASP solvers are designed to enumerate all solutions, and counting can therefore be easily done, the involved materialization of all solutions is a clear bottleneck for the counting problem of ASP (#ASP). In this paper we propose dynamic programming-based #ASP algorithms that exploit the structure of the underlying (ground) ASP program. Read More

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. Read More

We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson '09]}, and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov '16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordstrom '08]. Read More

We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically cheap functions that are expensive for NUOBDDs and vice versa by improving the previous gap. Read More

We show that any classical communication protocol that can approximately simulate the result of applying an arbitrary measurement (held by one party) to a quantum state of n qubits (held by another) must transmit at least 2^n bits, up to constant factors. The argument is based on a lower bound on the classical communication complexity of a distributed variant of the Fourier sampling problem. We obtain two optimal quantum-classical separations as corollaries. Read More

This paper investigates second-order representations in the sense of Kawamura and Cook for spaces of integrable functions that regularly show up in analysis. It builds upon prior work about the space of continuous functions on the unit interval: Kawamura and Cook introduced a representation inducing the right complexity classes and proved that it is the weakest second-order representation such that evaluation is polynomial-time computable. The first part of this paper provides a similar representation for the space of integrable functions on a bounded subset of Euclidean space: The weakest representation rendering integration over boxes is polynomial-time computable. Read More

We prove the existence of binary codes of positive rate that can correct an arbitrary pattern of $p$ fraction of deletions, for any $p < 1$, when the bit positions to delete are picked obliviously of the codeword. Formally, we prove that for every $p < 1$, there exists $\mathcal{R} > 0$ and a code family with a randomized encoder $\mathsf{Enc}: \{0,1\}^{\mathcal{R} n} \to \{0,1\}^n$ and (deterministic) decoder $\mathsf{Dec}: \{0,1\}^{(1-p)n} \to \{0,1\}^{\mathcal{R} n}$ such that for all deletion patterns $\tau$ with $pn$ deletions and all messages $m \in \{0,1\}^{\mathcal{R} n}$, ${\textbf{Pr}} [ \mathsf{Dec}(\tau(\mathsf{Enc}(m))) \neq m ] \le o(1)$, where the probability is over the randomness of the encoder (which is private to the encoder and not known to the decoder). The oblivious model is a significant generalization of the random deletion channel where each bit is deleted independently with probability $p$. Read More

The paper examines hierarchies for nondeterministic and deterministic ordered read-$k$-times Branching programs. The currently known hierarchies for deterministic $k$-OBDD models of Branching programs for $ k=o(n^{1/2}/\log^{3/2}n)$ are proved by B. Bollig, M. Read More

The rise of internet has resulted in an explosion of data consisting of millions of articles, images, songs, and videos. Most of this data is high dimensional and sparse. The need to perform an efficient search for similar objects in such high dimensional big datasets is becoming increasingly common. Read More

We show that the conjugacy problem in a wreath product $A \wr B$ is uniform-$\mathsf{TC}^0$-Turing-reducible to the conjugacy problem in the factors $A$ and $B$ and the power problem in $B$. Moreover, if $B$ is torsion free, the power problem for $B$ can be replaced by the slightly weaker cyclic submonoid membership problem for $B$, which itself turns out to be uniform-$\mathsf{TC}^0$-Turing-reducible to conjugacy problem in $A \wr B$ if $A$ is non-abelian. Furthermore, under certain natural conditions, we give a uniform $\mathsf{TC}^0$ Turing reduction from the power problem in $A \wr B$ to the power problems of $A$ and $B$. Read More

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible. First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the the Quantum AI group at Google. Read More

This short note describes a connection between algorithmic dimensions of individual points and classical pointwise dimensions of measures. Read More

We study the problem of approximately evaluating the independent set polynomial of bounded-degree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hard-core model with activity lambda on graphs G of max degree D. For lambda>0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at lambda_c(D)=(D-1)^(D-1)/(D-2)^D, which coincides with the tree uniqueness phase transition from statistical physics. For lambda<0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Read More

We consider a family of quantum spin systems which includes as special cases the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error E using a classical randomized algorithm with runtime polynomial in 1/E, system size, and inverse temperature. As a consequence we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. Read More

We show in this article that uncomputability is also a relative property of subrecursive classes built on a recursive relative incompressible function, which acts as a higher-order "yardstick" of irreducible information for the respective subrecursive class. We define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function and for the halting probability (or Chaitin's constant) Omega; respectively the Busy Beaver Plus (BBP) function and a time-bounded halting probability. Therefore, we prove that the computable BBP function defined on any Turing submachine is neither computable nor compressible by any program running on this submachine. Read More

We consider the task of verifying the correctness of quantum computation for a restricted class of circuits which contain at most two basis changes. This contains circuits giving rise to the second level of the Fourier Hierarchy, the lowest level for which there is an established quantum advantage. We show that, when the circuit has an outcome with probability at least the inverse of some polynomial in the circuit size, the outcome can be checked in polynomial time with bounded error by a completely classical verifier. Read More

We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier NP-hardness results by H{\aa}stad~\cite{H90}. The hardness proof also implies an algebraic universality result. Read More

We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that: (1) intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class, (2) not every intersection graph of rays is an intersection graph of downward rays, and (3) not every intersection graph of rays is an outer segment graph. The first result answers an open problem posed by Cabello and Jej\v{c}i\v{c}. Read More

In the (deletion-channel) trace reconstruction problem, there is an unknown $n$-bit source string $x$. An algorithm is given access to independent traces of $x$, where a trace is formed by deleting each bit of~$x$ independently with probability~$\delta$. The goal of the algorithm is to recover~$x$ exactly (with high probability), while minimizing samples (number of traces) and running time. Read More

We consider the following multiplication-based tests to check if a given function $f: \mathbb{F}_q^n\to \mathbb{F}_q$ is the evaluation of a degree-$d$ polynomial over $\mathbb{F}_q$ for $q$ prime. * $\mathrm{Test}_{e,k}$: Pick $P_1,\ldots,P_k$ independent random degree-$e$ polynomials and accept iff the function $fP_1\cdots P_k$ is the evaluation of a degree-$(d+ek)$ polynomial. We prove the robust soundness of the above tests for large values of $e$, answering a question of Dinur and Guruswami (FOCS 2013). Read More