Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LEARNING THEORY:
Reports tagged with Learning theory:
TR96-030 | 31st March 1996
Meera Sitharam

Approximation from linear spaces and applications to complexity


We develop an analytic framework based on
linear approximation and point out how a number of complexity
related questions --
on circuit and communication
complexity lower bounds, as well as
pseudorandomness, learnability, and general combinatorics
of Boolean functions --
fit neatly into this framework. ... more >>>


TR98-075 | 9th December 1998
Adam Klivans, Dieter van Melkebeek

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
size oracle circuits with access to satisfiability. We show that every
language with ... more >>>


TR01-043 | 26th April 2001
Mikhail V. Vyugin, Vladimir Vyugin

Predictive complexity and information

A new notion of predictive complexity and corresponding amount of
information are considered.
Predictive complexity is a generalization of Kolmogorov complexity
which bounds the ability of any algorithm to predict elements of
a sequence of outcomes. We consider predictive complexity for a wide class
of bounded loss functions which ... more >>>


TR05-126 | 5th November 2005
Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

Comments: 2

For circuit classes R, the fundamental computational problem, Min-R,
asks for the minimum R-size of a boolean function presented as a truth
table. Prominent examples of this problem include Min-DNF, and
Min-Circuit (also called MCSP). We begin by presenting a new reduction
proving that Min-DNF is NP-complete. It is significantly ... more >>>


TR08-016 | 26th February 2008
Alexander Razborov, Alexander A. Sherstov

The Sign-Rank of AC^0

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries
is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0
for all i,j. We obtain the first exponential lower bound on the
sign-rank of a function in AC^0. Namely, let
f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).
We show that the matrix [f(x,y)]_{x,y} has ... more >>>


TR13-151 | 7th November 2013
Mark Bun, Justin Thaler

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

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


TR14-135 | 23rd October 2014
Noga Alon, Shay Moran, Amir Yehudayoff

Sign rank, VC dimension and spectral gaps

Revisions: 2

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>


TR15-009 | 16th January 2015
Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

Aggregate Pseudorandom Functions and Connections to Learning

Revisions: 1

In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries'' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values belonging to an exponential-sized interval, or the sum of all ... more >>>


TR16-075 | 9th May 2016
Mark Bun, Justin Thaler

Improved Bounds on the Sign-Rank of AC$^0$

Revisions: 1

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


TR16-121 | 4th August 2016
Mark Bun, Justin Thaler

Approximate Degree and the Complexity of Depth Three Circuits

Revisions: 1

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


TR19-027 | 1st March 2019
Mark Bun, Nikhil Mande, Justin Thaler

Sign-Rank Can Increase Under Intersection

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


TR19-041 | 7th March 2019
Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

Quantum hardness of learning shallow classical circuits

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>


TR20-185 | 1st December 2020
Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram

Quantum learning algorithms imply circuit lower bounds

Revisions: 1

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathrm{C}$ be a class of polynomial-size concepts, and suppose that $\mathrm{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 - \gamma$ by a time $T$ quantum algorithm. ... more >>>




ISSN 1433-8092 | Imprint