All reports by Author Justin Thaler:

__
TR20-100
| 6th July 2020
__

Amit Chakrabarti, Prantar Ghosh, Justin Thaler#### Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

__
TR20-020
| 21st February 2020
__

Nikhil Mande, Justin Thaler, Shuchen Zhu#### Improved Approximate Degree Bounds For $k$-distinctness

__
TR19-121
| 17th September 2019
__

Alexander A. Sherstov, Justin Thaler#### Vanishing-Error Approximate Degree and QMA Complexity

__
TR19-082
| 2nd June 2019
__

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson#### Approximate degree, secret sharing, and concentration phenomena

__
TR19-062
| 18th April 2019
__

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler#### Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Revisions: 2

__
TR19-027
| 1st March 2019
__

Mark Bun, Nikhil Mande, Justin Thaler#### Sign-Rank Can Increase Under Intersection

__
TR18-156
| 8th September 2018
__

Mark Bun, Robin Kothari, Justin Thaler#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

Revisions: 1

__
TR18-143
| 16th August 2018
__

Mark Bun, Justin Thaler#### The Large-Error Approximate Degree of AC$^0$

__
TR17-169
| 24th October 2017
__

Mark Bun, Robin Kothari, Justin Thaler#### The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

__
TR17-051
| 16th March 2017
__

Mark Bun, Justin Thaler#### A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

__
TR16-140
| 9th September 2016
__

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan#### On SZK and PP

Revisions: 3

__
TR16-121
| 4th August 2016
__

Mark Bun, Justin Thaler#### Approximate Degree and the Complexity of Depth Three Circuits

Revisions: 1

__
TR16-075
| 9th May 2016
__

Mark Bun, Justin Thaler#### Improved Bounds on the Sign-Rank of AC$^0$

Revisions: 1

__
TR15-041
| 25th March 2015
__

Mark Bun, Justin Thaler#### Dual Polynomials for Collision and Element Distinctness

__
TR14-150
| 10th November 2014
__

Justin Thaler#### Lower Bounds for the Approximate Degree of Block-Composed Functions

Revisions: 3

__
TR14-090
| 11th July 2014
__

Justin Thaler#### Semi-Streaming Algorithms for Annotated Graph Streams

Revisions: 2

__
TR14-086
| 11th July 2014
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### Verifiable Stream Computation and Arthurâ€“Merlin Communication

__
TR13-180
| 17th December 2013
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### On Interactivity in Arthur-Merlin Communication and Stream Computation

Revisions: 1

__
TR13-151
| 7th November 2013
__

Mark Bun, Justin Thaler#### Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

__
TR13-032
| 26th February 2013
__

Mark Bun, Justin Thaler#### Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Revisions: 2

__
TR12-056
| 1st May 2012
__

Rocco Servedio, Li-Yang Tan, Justin Thaler#### Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions

Revisions: 1

__
TR12-022
| 14th March 2012
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler#### Annotations in Data Streams

Revisions: 1

__
TR11-105
| 22nd July 2011
__

Graham Cormode, Michael Mitzenmacher, Justin Thaler#### Streaming Graph Computations with a Helpful Advisor

Revisions: 1

__
TR10-159
| 28th October 2010
__

Graham Cormode, Justin Thaler, Ke Yi#### Verifying Computations with Streaming Interactive Proofs

Amit Chakrabarti, Prantar Ghosh, Justin Thaler

We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that ... more >>>

Nikhil Mande, Justin Thaler, Shuchen Zhu

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

Alexander A. Sherstov, Justin Thaler

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>>

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

This paper proves new limitations on the power of quantum computers to solve approximate counting---that is, multiplicatively estimating the size of a nonempty set $S\subseteq [N]$.

Given only a membership oracle for $S$, it is well known that approximate counting takes $\Theta(\sqrt{N/|S|})$ quantum queries. But what if a quantum algorithm ... more >>>

Mark Bun, Nikhil Mande, Justin Thaler

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 ... more >>>

Mark Bun, Robin Kothari, Justin Thaler

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a 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 ... more >>>

Mark Bun, Justin Thaler

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the Surjectivity function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ ... more >>>

Mark Bun, Robin Kothari, Justin Thaler

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. The approximate degree of $f$ is known to be a lower bound on the quantum query complexity of $f$ (Beals et al., FOCS 1998 and ... more >>>

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

Mark Bun, Justin Thaler

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the ... more >>>

Mark Bun, Justin Thaler

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within error $1/3$ in the $\ell_\infty$ norm. In an influential result, Aaronson and Shi (J. ACM 2004) proved tight $\tilde{\Omega}(n^{1/3})$ and $\tilde{\Omega}(n^{2/3})$ lower bounds on ... more >>>

Justin Thaler

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function $f$ on $N$ bits, define $F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$ to be the function on $M \cdot N$ bits obtained by block-composing $f$ with a specific DNF known ... more >>>

Justin Thaler

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>>

Mark Bun, Justin Thaler

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit ... more >>>

Mark Bun, Justin Thaler

The $\epsilon$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $\epsilon$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an ... more >>>

Rocco Servedio, Li-Yang Tan, Justin Thaler

We study the challenging problem of learning decision lists attribute-efficiently, giving both positive and negative results.

Our main positive result is a new tradeoff between the running time and mistake bound for learning length-$k$ decision lists over $n$ Boolean variables. When the allowed running time is relatively high, our new ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler

The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage of such algorithms can be further reduced by enlisting a more powerful ... more >>>

Graham Cormode, Michael Mitzenmacher, Justin Thaler

Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a ... more >>>

Graham Cormode, Justin Thaler, Ke Yi

Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a ... more >>>