All reports by Author Eric Blais:

__
TR22-112
| 12th August 2022
__

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre#### Randomised Composition and Small-Bias Minimax

__
TR16-201
| 19th December 2016
__

Eric Blais, Yuichi Yoshida#### A Characterization of Constant-Sample Testable Properties

__
TR16-168
| 2nd November 2016
__

Eric Blais, Clement Canonne, Tom Gur#### Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

Revisions: 1

__
TR16-105
| 13th July 2016
__

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron#### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

__
TR14-144
| 30th October 2014
__

Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan#### Learning circuits with few negations

__
TR13-051
| 2nd April 2013
__

Eric Blais, Li-Yang Tan#### Approximating Boolean functions with depth-2 circuits

__
TR13-036
| 13th March 2013
__

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev#### Lower Bounds for Testing Properties of Functions on Hypergrid Domains

Revisions: 1

__
TR11-045
| 1st April 2011
__

Eric Blais, Joshua Brody, Kevin Matulef#### Property Testing Lower Bounds via Communication Complexity

Revisions: 1

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a linearised complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and moreover, $\mathrm{LR}$ is the largest possible measure with this property. In particular, ... more >>>

Eric Blais, Yuichi Yoshida

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.

Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ...
more >>>

Eric Blais, Clement Canonne, Tom Gur

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>

Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and ... more >>>

Eric Blais, Li-Yang Tan

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function.

In the first direction, our main positive results are the first non-trivial universal upper bounds on ...
more >>>

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.

Our lower bounds also apply to the more restricted setting ...
more >>>

Eric Blais, Joshua Brody, Kevin Matulef

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in ... more >>>