Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

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

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

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

Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, RĂ¼diger Reischuk

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

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

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