skip to main content

Search for: All records

Creators/Authors contains: "Thaler, Justin"

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 non-federal websites. Their policies may differ from this site.

  1. We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε -far from Π , while only probing a minuscule portion of their input.We investigate the complexity landscape of this model, showing that QMAPs can be e x p o n e n t i a l l y stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly d e c o m p o s a b l e . A consequence of this framework is a QMA algorithm to verify the Parity of an nmore »-bit string with O ( n 2 / 3 ) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.« less
    Free, publicly-accessible full text available October 13, 2023
  2. Free, publicly-accessible full text available July 1, 2023
  3. Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic in n. Given the sketch and a query item y, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y.
  4. The communication class UPP cc is a communication analog of the Turing Machine complexity class PP . It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem f , let f ∧ f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP cc ( f ) = O (log n ), and UPP cc ( f ∧ f ) = Θ (log 2 n ). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP cc , the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity n Omega Ω(log n ) . This matches an upper bound of (Klivans, O’Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm formore »PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.« less
  5. We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level 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 worst-case 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 linear-size 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 subexponential-time algorithm was not known even for linear-size depth-3 AC 0 circuits.As anmore »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).« less
  6. The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This article surveys what we know about approximate degree and illustrates some of its applications in theoretical computer science.