All reports by Author Rocco Servedio:

__
TR18-145
| 13th August 2018
__

Ryan O'Donnell, Rocco Servedio, Li-Yang Tan#### Fooling Polytopes

__
TR18-100
| 18th May 2018
__

Eshan Chattopadhyay, Anindya De, Rocco Servedio#### Simple and efficient pseudorandom generators from Gaussian processes

Revisions: 1

__
TR17-068
| 20th April 2017
__

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie#### Settling the query complexity of non-adaptive junta testing

__
TR16-069
| 25th April 2016
__

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson#### Degree and Sensitivity: tails of two distributions

__
TR15-131
| 10th August 2015
__

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson#### Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

__
TR15-123
| 31st July 2015
__

Xi Chen, Igor Carboni Oliveira, Rocco Servedio#### Addition is exponentially harder than counting for shallow monotone circuits

__
TR15-065
| 18th April 2015
__

Benjamin Rossman, Rocco Servedio, Li-Yang Tan#### An average-case depth hierarchy theorem for Boolean circuits

__
TR14-144
| 30th October 2014
__

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

__
TR13-173
| 28th November 2013
__

Anindya De, Rocco Servedio#### Efficient deterministic approximate counting for low degree polynomial threshold functions

__
TR13-172
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

__
TR13-171
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

__
TR13-096
| 25th June 2013
__

Dana Ron, Rocco Servedio#### Exponentially improved algorithms and lower bounds for testing signed majorities

__
TR12-181
| 20th December 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### The Inverse Shapley Value Problem

__
TR12-155
| 15th November 2012
__

Clement Canonne, Dana Ron, Rocco Servedio#### Testing probability distributions using conditional samples

Revisions: 1

__
TR12-152
| 7th November 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Inverse Problems in Approximate Uniform Generation

__
TR12-144
| 6th November 2012
__

Rocco Servedio, Emanuele Viola#### On a special case of rigidity

__
TR12-072
| 5th June 2012
__

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio#### Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

__
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

__
TR10-074
| 20th April 2010
__

Parikshit Gopalan, Rocco Servedio#### Learning and Lower Bounds for AC$^0$ with Threshold Gates

__
TR10-022
| 23rd February 2010
__

Vitaly Feldman, Homin Lee, Rocco Servedio#### Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

__
TR09-016
| 21st February 2009
__

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola#### Bounded Independence Fools Halfspaces

__
TR07-129
| 25th October 2007
__

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan#### Learning Random Monotone DNF

__
TR07-128
| 10th November 2007
__

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio#### Testing Halfspaces

__
TR07-077
| 7th August 2007
__

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan#### Testing for Concise Representations

__
TR01-006
| 18th October 2000
__

Rocco Servedio#### On Learning Monotone DNF under Product Distributions

Ryan O'Donnell, Rocco Servedio, Li-Yang Tan

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \log n$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program.

more >>>Eshan Chattopadhyay, Anindya De, Rocco Servedio

We show that a very simple pseudorandom generator fools intersections of $k$ linear threshold functions (LTFs) and arbitrary functions of $k$ LTFs over $n$-dimensional Gaussian space.

The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of ... more >>>

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

We prove that any non-adaptive algorithm that tests whether an unknown

Boolean function $f\colon \{0, 1\}^n\to\{0, 1\} $ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / \epsilon)$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower ...
more >>>

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

The sensitivity of a Boolean function $f$ is the maximum, over all inputs $x$, of the number of sensitive coordinates of $x$ (namely the number of Hamming neighbors of $x$ with different $f$-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-$s$ Boolean function ... more >>>

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>>

Xi Chen, Igor Carboni Oliveira, Rocco Servedio

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>

Benjamin Rossman, Rocco Servedio, Li-Yang Tan

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a linear-size depth-$d$ formula, which is such that any depth-$(d-1)$ ... 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 >>>

Anindya De, Rocco Servedio

We give a deterministic algorithm for

approximately counting satisfying assignments of a degree-$d$ polynomial threshold function

(PTF).

Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$

and a parameter $\epsilon > 0$, our algorithm approximates

$

\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]

$

to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates

\[

\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]

\]

to within an additive $\pm \eps$ in ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates \[

\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1] \]

to within an additive $\pm \eps$. For any constant ...
more >>>

Dana Ron, Rocco Servedio

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form

$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley ... more >>>

Clement Canonne, Dana Ron, Rocco Servedio

We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. \footnote{Independently from our work, Chakraborty et al. [CFGM13] also considered this framework. We discuss their work in Subsection 1.4.} This is an oracle that takes as ... more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We initiate the study of \emph{inverse} problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $\C$ of Boolean functions ... more >>>

Rocco Servedio, Emanuele Viola

We highlight the special case of Valiant's rigidity

problem in which the low-rank matrices are truth-tables

of sparse polynomials. We show that progress on this

special case entails that Inner Product is not computable

by small $\acz$ circuits with one layer of parity gates

close to the inputs. We then ...
more >>>

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... 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 >>>

Parikshit Gopalan, Rocco Servedio

In 2002 Jackson et al. [JKS02] asked whether AC0 circuits augmented with a threshold gate at the output can be efficiently learned from uniform random examples. We answer this question affirmatively by showing that such circuits have fairly strong Fourier concentration; hence the low-degree algorithm of Linial, Mansour and Nisan ... more >>>

Vitaly Feldman, Homin Lee, Rocco Servedio

Much work has been done on learning various classes of ``simple'' monotone functions under the uniform distribution. In this paper we give the first unconditional lower bounds for learning problems of this sort by showing that polynomial-time algorithms cannot learn constant-depth monotone Boolean formulas under the uniform distribution in the ... more >>>

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

We give an algorithm that with high probability properly learns random monotone t(n)-term

DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ...
more >>>

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

Rocco Servedio

We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF

formulae can be PAC learned in polynomial time under the uniform

distribution. This is an exponential improvement over previous

algorithms in this model, which could learn monotone

$o(\log^2 n)$-term DNF, and is the first efficient algorithm

for ...
more >>>