Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

All reports by Author Rocco Servedio:

TR16-069 | 25th April 2016
Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

Degree and Sensitivity: tails of two distributions

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

TR15-065 | 18th April 2015
Benjamin Rossman, Rocco Servedio, Li-Yang Tan

An average-case depth hierarchy theorem for Boolean circuits

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

TR14-144 | 30th October 2014
Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

Learning circuits with few negations

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

TR13-173 | 28th November 2013
Anindya De, Rocco Servedio

Efficient deterministic approximate counting for low degree polynomial threshold functions

We give a deterministic algorithm for
approximately counting satisfying assignments of a degree-$d$ polynomial threshold function
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 >>>

TR13-172 | 1st December 2013
Anindya De, Ilias Diakonikolas, Rocco Servedio

Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

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

TR13-171 | 1st December 2013
Anindya De, Ilias Diakonikolas, Rocco Servedio

Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

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

TR13-096 | 25th June 2013
Dana Ron, Rocco Servedio

Exponentially improved algorithms and lower bounds for testing signed majorities

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

TR12-181 | 20th December 2012
Anindya De, Ilias Diakonikolas, Rocco Servedio

The Inverse Shapley Value Problem

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

TR12-155 | 15th November 2012
Clement Canonne, Dana Ron, Rocco Servedio

Testing probability distributions using conditional samples

Revisions: 1

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

TR12-152 | 7th November 2012
Anindya De, Ilias Diakonikolas, Rocco Servedio

Inverse Problems in Approximate Uniform Generation

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

TR12-144 | 6th November 2012
Rocco Servedio, Emanuele Viola

On a special case of rigidity

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

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

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

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

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

TR10-074 | 20th April 2010
Parikshit Gopalan, Rocco Servedio

Learning and Lower Bounds for AC$^0$ with Threshold Gates

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

TR10-022 | 23rd February 2010
Vitaly Feldman, Homin Lee, Rocco Servedio

Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

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

TR09-016 | 21st February 2009
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

Bounded Independence Fools Halfspaces

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

TR07-129 | 25th October 2007
Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

Learning Random Monotone DNF

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

TR07-128 | 10th November 2007
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

Testing Halfspaces

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 &#8901; x - &#952;). 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 >>>

TR07-077 | 7th August 2007
Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

Testing for Concise Representations

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

TR01-006 | 18th October 2000
Rocco Servedio

On Learning Monotone DNF under Product Distributions

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

ISSN 1433-8092 | Imprint