All reports by Author Mark Bun:

__
TR23-024
| 9th March 2023
__

Mark Bun, Nadezhda Voronova#### Approximate degree lower bounds for oracle identification problems

Revisions: 1

__
TR18-156
| 8th September 2018
__

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

Revisions: 2

__
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-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-166
| 8th December 2014
__

Mark Bun, Thomas Steinke#### Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

__
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

Mark Bun, Nadezhda Voronova

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function.

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

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

Mark Bun, Thomas Steinke

Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorithms for agnostically learning halfspaces, as well as pseudorandom generators for halfspaces. In this work, we investigate the limits of these techniques by proving inapproximability results for ... 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 >>>