Fetching the paper…
Reading the bibliography…
We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over $\mathbb{R}$) of functions from some "simple" class ${\cal C}$.
Theory of majority decision elements
S. Muroga, I. Toda, and S. Takasu · 1961
Earlier work this paper cites.
Threshold Logic
R. O. Winder · 1962
Earlier work this paper cites.
Computing partitions with applications to the knapsack problem
Ellis Horowitz and Sartaj Sahni · 1974
Earlier work this paper cites.
Graph-theoretic arguments in low-level complexity
L. G. Valiant · 1977
Earlier work this paper cites.
Separating nondeterministic time complexity classes
Joel Seiferas, Michael Fischer, and Albert Meyer · 1978
Earlier work this paper cites.
A Turing machine time hierarchy
Stanislav Žák · 1983
Earlier work this paper cites.
Non-uniform automata over groups
David A. Mix Barrington, Howard Straubing, and Denis Thérien · 1990
Earlier work this paper cites.
On the power of small-depth threshold circuits
Johan Håstad and Mikael Goldmann · 1991
Earlier work this paper cites.
PP is as hard as the polynomial-time hierarchy
S. Toda · 1991
Earlier work this paper cites.
Threshold circuits of bounded depth
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán · 1993
Earlier work this paper cites.
The communication complexity of threshold gates
Noam Nisan · 1994
Earlier work this paper cites.
Lower bounds on threshold and related circuits via communication complexity
Vwani P. Roychowdhury, Alon Orlitsky, and Kai-Yeung Siu · 1994
Earlier work this paper cites.
On the correlation of symmetric functions
Jin-yi Cai, Frederic Green, and Thomas Thierauf · 1996
Earlier work this paper cites.
Bounds for the computational power and learning complexity of analog neural nets
Wolfgang Maass · 1997
Earlier work this paper cites.
Super-polynomial versus half-exponential circuit size in the exponential hierarchy
Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe · 1999
Earlier work this paper cites.
The correlation between parity and quadratic polynomials mod3
Frederic Green · 2004
Earlier work this paper cites.
C.R. Acad. Sci. Paris Ser. I
Estimation of certain exponential sums arising in complexity theory · 2005
Earlier work this paper cites.
A lower bound on the size of series-parallel graphs dense in long paths
Chris Calabro · 2008
Cited alongside, same era.
Set partitioning via inclusion-exclusion
Andreas Björklund, Thore Husfeldt, and Mikko Koivisto · 2009
Cited alongside, same era.
Circuit lower bounds for Merlin–Arthur classes
Rahul Santhanam · 2009
Cited alongside, same era.
Guest column: correlation bounds for polynomials over {0, 1}
Emanuele Viola · 2009
Cited alongside, same era.
Weights of exact threshold functions
László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, and Xiaoming Sun · 2010
Cited alongside, same era.
Exact threshold circuits
Kristoffer Arnsfelt Hansen and Vladimir V Podolskii · 2010
Cited alongside, same era.
Average-case lower bounds and satisfiability algorithms for small threshold circuits
Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan · 2016
Later among the works it cites.
Deterministic APSP, Orthogonal Vectors, and more: Quickly derandomizing Razborov-Smolensky
Timothy M. Chan and Ryan Williams · 2016
Later among the works it cites.
The power of depth for feedforward neural networks
Ronen Eldan and Ohad Shamir · 2016
Later among the works it cites.
Higher-order fourier analysis and applications
Hamed Hatami, Pooya Hatami, and Shachar Lovett · 2016
Later among the works it cites.
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
Daniel M. Kane and Ryan Williams · 2016
Later among the works it cites.
A satisfiability algorithm for depth two circuits with a sub-quadratic number of symmetric and threshold gates
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Ryan Williams · 2011
Cited alongside, same era.
On the correlation between parity and modular polynomials
Anna Gál and Vladimir Trifonov · 2012
Cited alongside, same era.
On medium-uniformity and circuit lower bounds
Rahul Santhanam and Ryan Williams · 2013
Cited alongside, same era.
Improving exhaustive search implies superpolynomial lower bounds
Ryan Williams · 2013
Cited alongside, same era.
Short PCPs with projection queries
Eli Ben-Sasson and Emanuele Viola · 2014
Cited alongside, same era.
Real Analysis in Computer Science: A collection of open problems, Simons Institute, 2014
Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O’Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer · 2014
Cited alongside, same era.
Suguru Tamaki · 2016
Later among the works it cites.
benefits of depth in neural networks
Matus Telgarsky · 2016
Later among the works it cites.
Weights at the bottom matter when the top is heavy
Arkadev Chattopadhyay and Nikhil S. Mande · 2017
Later among the works it cites.
Depth separation for neural networks
Amit Daniely · 2017
Later among the works it cites.
Personal communication, 2017
Shachar Lovett · 2017
Later among the works it cites.
Beating brute force for systems of polynomial equations over finite fields
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, and Huacheng Yu · 2017
Later among the works it cites.
Lower bounds over Boolean inputs for deep neural networks with ReLU gates
Anirbit Mukherjee and Amitabh Basu · 2017
Later among the works it cites.
Circuit lower bounds for nondeterministic quasi-polytime: An easy witness lemma for NP and NQP
Cody Murray and Ryan Williams · 2017
Later among the works it cites.
Depth-width tradeoffs in approximating natural functions with neural networks
Itay Safran and Ohad Shamir · 2017
Later among the works it cites.
Proving that prBPP=prP is as hard as “almost” proving that P ≠ \neq NP
Roei Tell · 2018
Closest in time.
Counting solutions to polynomial systems via reductions
Ryan Williams · 2018
Closest in time.