 Award ID(s):
 2009011
 NSFPAR ID:
 10471250
 Publisher / Repository:
 Schloss Dagstuhl  LeibnizZentrum fur Informatik
 Date Published:
 Journal Name:
 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
 ISSN:
 18688969
 ISBN:
 9783959772631
 Format(s):
 Medium: X
 Location:
 Cambridge, MA
 Sponsoring Org:
 National Science Foundation
More Like this

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottomlevel gates. Let f be an m bit Boolean function and consider an n bit function F obtained by applying f to conjunctions of possibly overlapping subsets of n variables. If f has quantum query complexity Q ( f ) , we give an algorithm for evaluating F using O ~ ( Q ( f ) ⋅ n ) quantum queries. This improves on the bound of O ( Q ( f ) ⋅ n ) that follows by treating each conjunction independently, and our bound is tight for worstcase choices of f . Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of f .By recursively applying our composition theorems, we obtain a nearly optimal O ~ ( n 1 − 2 − d ) upper bound on the quantum query complexity and approximate degree of linearsize depth d AC 0 circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponentialtime algorithm was not known even for linearsize depth3 AC 0 circuits.As an additional consequence, we show that AC 0 ∘ ⊕ circuits of depth d + 1 require size Ω ~ ( n 1 / ( 1 − 2 − d ) ) ≥ ω ( n 1 + 2 − d ) to compute the Inner Product function even on average. The previous best size lower bound was Ω ( n 1 + 4 − ( d + 1 ) ) and only held in the worst case (Cheraghchi et al., JCSS 2018).more » « less

Bringmann, Karl ; Grohe, Martin ; Puppis, Gabriele ; Svensson, Ola (Ed.)We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)approximation in Õ(n^ω/t^{ω2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)approximation algorithms for the number of hcycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h2)},n)), the time to multiply n × n/(t^{1/(h2)}) by n/(t^{1/(h2)) × n matrices. Finally, we show that under popular finegrained hypotheses, this running time is optimal.more » « less

Kumar, Amit ; RonZewi, Noga (Ed.)Estimating the size of the union of a stream of sets S₁, S₂, …, S_M where each set is a subset of a known universe Ω is a fundamental problem in data streaming. This problem naturally generalizes the wellstudied 𝖥₀ estimation problem in the streaming literature, where each set contains a single element from the universe. We consider the general case when the sets S_i can be succinctly represented and allow efficient membership, cardinality, and sampling queries (called a Delphic family of sets). A notable example in this framework is the Klee’s Measure Problem (KMP), where every set S_i is an axisparallel rectangle in ddimensional spaces (Ω = [Δ]^d where [Δ] := {1, … ,Δ} and Δ ∈ ℕ). Recently, Meel, Chakraborty, and Vinodchandran (PODS21, PODS22) designed a streaming algorithm for (ε,δ)estimation of the size of the union of set streams over Delphic family with space and update time complexity O((log³Ω)/ε² ⋅ log 1/δ) and Õ((log⁴Ω)/ε² ⋅ log 1/(δ)), respectively. This work presents a new, samplingbased algorithm for estimating the size of the union of Delphic sets that has space and update time complexity Õ((log²Ω)/ε² ⋅ log 1/(δ)). This improves the space complexity bound by a logΩ factor and update time complexity bound by a log² Ω factor. A critical question is whether quadratic dependence of logΩ on space and update time complexities is necessary. Specifically, can we design a streaming algorithm for estimating the size of the union of sets over Delphic family with space and complexity linear in logΩ and update time poly(logΩ)? While this appears technically challenging, we show that establishing a lower bound of ω(logΩ) with poly(logΩ) update time is beyond the reach of current techniques. Specifically, we show that under certain hardtoprove computational complexity hypothesis, there is a streaming algorithm for the problem with optimal space complexity O(logΩ) and update time poly(log(Ω)). Thus, establishing a space lower bound of ω(logΩ) will lead to breakthrough complexity class separation results.more » « less

QR factorization is a key tool in mathematics, computer science, operations research, and engineering. This paper presents the roundofferrorfree (REF) QR factorization framework comprising integerpreserving versions of the standard and the thin QR factorizations and associated algorithms to compute them. Specifically, the standard REF QR factorization factors a given matrix $A \in \Z^{m \times n}$ as $A=QDR$, where $Q \in \Z^{m \times m}$ has pairwise orthogonal columns, $D$ is a diagonal matrix, and $R \in \Z^{m \times n}$ is an upper trapezoidal matrix; notably, the entries of $Q$ and $R$ are integral, while the entries of $D$ are reciprocals of integers. In the thin REF QR factorization, $Q \in \Z^{m \times n}$ also has pairwise orthogonal columns, and $R \in \Z^{n \times n}$ is also an upper triangular matrix. In contrast to traditional (i.e., floatingpoint) QR factorizations, every operation used to compute these factors is integral; thus, REF QR is guaranteed to be an exact orthogonal decomposition. Importantly, the bitlength of every entry in the REF QR factorizations (and within the algorithms to compute them) is bounded polynomially. Notable applications of our REF QR factorizations include finding exact least squares or exact basic solutions (i.e., a rational ndimensional vector $x$) to any given full column rank or rank deficient linear system $A x = b$, respectively. In addition, our exact factorizations can be used as a subroutine within exact and/or highprecision quadratic programming. Altogether, REF QR provides a framework to obtain exact orthogonal factorizations of any rational matrix (as any rational/decimal matrix can be easily transformed into an integral matrix).more » « less

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an
n dimensional convex body within multiplicative error ε usingÕ(n^{3}+ n^{2.5}/ε ) queries to a membership oracle andÕ(n^{5}+n^{4.5}/ε) additional arithmetic operations. For comparison, the best known classical algorithm usesÕ(n^{3.5}+n^{3}/ε^{2}) queries andÕ(n^{5.5}+n^{5}/ε^{2}) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of “Chebyshev cooling,” where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuousspace quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requiresΩ (√ n+1/ε) quantum membership queries, which rules out the possibility of exponential quantum speedup inn and shows optimality of our algorithm in 1/ε up to polylogarithmic factors.