Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LEARNING ALGORITHMS:
Reports tagged with learning algorithms:
TR15-191 | 26th November 2015
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

#### Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most
n^{1+\epsilon_d} ... more >>>

TR17-023 | 15th February 2017
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

#### The Power of Natural Properties as Oracles

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).
We obtain new circuit lower bounds, as well as some hardness results for the relativized version ... more >>>

TR17-046 | 8th March 2017
Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk

#### Learning Residual Alternating Automata

Residuality plays an essential role for learning finite automata.
While residual deterministic and nondeterministic
automata have been understood quite well, fundamental
questions concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman have initiated
a systematic study of residual AFAs and proposed an algorithm called AL*
-an extension of ... more >>>

TR17-098 | 28th May 2017
Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

#### Understanding Deep Neural Networks with Rectified Linear Units

Revisions: 2

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give the first-ever polynomial time (in the size of data) algorithm to train to global optimality a ReLU DNN with one hidden layer, assuming the input dimension and number ... more >>>

TR19-168 | 20th November 2019
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

#### Beyond Natural Proofs: Hardness Magnification and Locality

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... more >>>

TR20-018 | 18th February 2020
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

#### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... more >>>

TR21-009 | 1st February 2021
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

#### One-way Functions and Partial MCSP

Revisions: 3 , Comments: 1

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

TR21-116 | 10th August 2021
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

#### Quantum Meets the Minimum Circuit Size Problem

Revisions: 1

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory---its hardness is mysterious, and a better understanding of its hardness can have ... more >>>

TR21-155 | 13th November 2021
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

#### Learning generalized depth-three arithmetic circuits in the non-degenerate case

Revisions: 1

Consider a homogeneous degree $d$ polynomial $f = T_1 + \cdots + T_s$, $T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m})$ where $g_i$'s are homogeneous $m$-variate degree $d$ polynomials and $\ell_{i,j}$'s are linear polynomials in $n$ variables. We design a (randomized) learning algorithm that given black-box access to $f$, computes black-boxes for ... more >>>

TR21-171 | 2nd December 2021
Bruno Pasqualotto Cavalar, Zhenjian Lu

#### Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite having been studied for nearly three decades, the first superlinear lower bound against comparator circuits was proved only recently by Gál and Robere (ITCS 2020), who established ... more >>>

TR22-098 | 12th July 2022
We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive ... more >>>