Fetching the paper…
Reading the bibliography…
In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze.
On the number of real roots of a random algebraic equation III
J. Littlewood and C. Offord · 1943
Earlier work this paper cites.
A logical calculus of the ideas immanent in nervous activity
Warren S. McCulloch and Walter Pitts · 1943
Earlier work this paper cites.
On a lemma of Littlewood and Offord
P. Erdős · 1945
Earlier work this paper cites.
On the characterization of threshold functions
Chao-Kong Chow · 1961
Earlier work this paper cites.
Realizations of linear functions by formulas using +,*,-
B. A. Subbotovskaya · 1961
Earlier work this paper cites.
Threshold Logic
R. O. Winder · 1962
Earlier work this paper cites.
Perceptrons: An Introduction to Computational Geometry
Marvin Minsky and Seymour Papert · 1969
Earlier work this paper cites.
Threshold Logic and its Applications
S. Muroga · 1971
Earlier work this paper cites.
Parity, circuits, and the polynomial-time hierarchy
Merrick L. Furst, James B. Saxe, and Michael Sipser · 1984
Earlier work this paper cites.
Deterministic simulation of probabilistic constant depth circuits (preliminary version)
Miklós Ajtai and Avi Wigderson · 1985
Earlier work this paper cites.
Separating the polynomial-time hierarchy by oracles (preliminary version)
Andrew Chi-Chih Yao · 1985
Earlier work this paper cites.
Almost optimal lower bounds for small depth circuits
Johan Håstad · 1986
Earlier work this paper cites.
On a method for obtaining more than quadratic effective lower bounds for the complexity of π \pi -schemes
Alexander E. Andreev · 1987
Earlier work this paper cites.
Decision trees and downward closures
Russell Impagliazzo and Moni Naor · 1988
Earlier work this paper cites.
On linear decision trees computing boolean functions
Hans Dietmar Gröger and György Turán · 1991
Earlier work this paper cites.
Simple construction of almost k k -wise independent random variables
Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta · 1992
Earlier work this paper cites.
Majority gates vs. general weighted threshold gates
Mikael Goldmann, Johan Hastad, and Alexander Razborov · 1992
Cited alongside, same era.
A linear lower bound for the size of threshold circuits
Hans Dietmar Gröger and György Turán · 1993
Cited alongside, same era.
Threshold circuits of bounded depth
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán · 1993
Cited alongside, same era.
Shrinkage of de morgan formulae under restriction
Mike Paterson and Uri Zwick · 1993
Cited alongside, same era.
The communication complexity of threshold gates
Noam Nisan · 1994
Cited alongside, same era.
Approximating threshold circuits by rational functions
Ramamohan Paturi and Michael E. Saks · 1994
Cited alongside, same era.
The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1
Donald E. Knuth · 2011
Later among the works it cites.
The chow parameters problem
Ryan O’Donnell and Rocco A. Servedio · 2011
Later among the works it cites.
Pseudorandomness from shrinkage
Russell Impagliazzo, Raghu Meka, and David Zuckerman · 2012
Later among the works it cites.
Polynomial threshold functions and boolean threshold circuits
Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii · 2013
Later among the works it cites.
A satisfiability algorithm for sparse depth two threshold circuits
Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider · 2013
Later among the works it cites.
Average-case lower bounds for formula size
Ilan Komargodski and Ran Raz · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Lower bounds on threshold and related circuits via communication complexity
Vwani P. Roychowdhury, Alon Orlitsky, and Kai-Yeung Siu · 1994
Cited alongside, same era.
Neural models and spectral models
Vwani P. Roychowdhury, Alon Orlitsky, and Kai-Yeung Siu · 1994
Cited alongside, same era.
Size-depth tradeoffs for threshold circuits
Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks · 1997
Cited alongside, same era.
The shrinkage exponent of De Morgan formulae is 2
Johan Håstad · 1998
Cited alongside, same era.
Relations between communication complexity, linear arrangements, and computational complexity
Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon · 2001
Cited alongside, same era.
On the complexity of depth-2 circuits with threshold gates
Kazuyuki Amano and Akira Maruoka · 2005
Cited alongside, same era.
Improved average-case lower bounds for demorgan formula size
Ilan Komargodski, Ran Raz, and Avishay Tal · 2013
Later among the works it cites.
A satisfiability algorithm and average-case hardness for formulas over the full binary basis
Kazuhisa Seto and Suguru Tamaki · 2013
Later among the works it cites.
An improved deterministic #SAT algorithm for small De Morgan formulas
Ruiwen Chen, Valentine Kabanets, and Nitin Saurabh · 2014
Later among the works it cites.
On the correlation of parity and small-depth circuits
Johan Håstad · 2014
Later among the works it cites.
New algorithms and lower bounds for circuits with linear threshold gates
Ryan Williams · 2014
Later among the works it cites.
More applications of the polynomial method to algorithm design
Amir Abboud, Ryan Williams, and Huacheng Yu · 2015
Closest in time.
Mining circuit lower bound proofs for meta-algorithms
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman · 2015
Closest in time.
Improved algorithms for sparse MAX-SAT and MAX-k-CSP
Ruiwen Chen and Rahul Santhanam · 2015
Closest in time.
An average-case depth hierarchy theorem for boolean circuits
Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan · 2015
Closest in time.