Fetching the paper…
Reading the bibliography…
Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity.
Schwankung von polynomen zwischen gitterpunkten
Hartmut Ehlich and Karl Zeller · 1964
Earlier work this paper cites.
A comparison of uniform approximations on an interval and a finite subset thereof
Theodore J Rivlin and Elliott W Cheney · 1966
Earlier work this paper cites.
Threshold Logic and its Applications
S. Muroga · 1971
Earlier work this paper cites.
Constant depth reducibility
A. K. Chandra, L. Stockmeyer, and U. Vishkin · 1984
Earlier work this paper cites.
Complexity classes in communication complexity theory (preliminary version)
László Babai, Peter Frankl, and Janos Simon · 1986
Earlier work this paper cites.
Probabilistic communication complexity
Ramamohan Paturi and Janos Simon · 1986
Earlier work this paper cites.
Perceptrons - an introduction to computational geometry
Marvin Minsky and Seymour Papert · 1987
Earlier work this paper cites.
The complexity of computations by networks
N. Pippenger · 1987
Earlier work this paper cites.
Harmonic analysis of polynomial threshold functions
Jehoshua Bruck · 1990
Earlier work this paper cites.
Andrew Chi-Chih Yao · 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.
On the power of thrshold circuits with small weights
K. I. Siu and J. Bruck · 1991
Earlier work this paper cites.
Majority gates VS. general weighted threshold gates
Mikael Goldmann, Johan Håstad, and Alexander A. Razborov · 1992
Cited alongside, same era.
On small depth threshold circuits
Alexander A. Razborov · 1992
Cited alongside, same era.
Threshold circuits of bounded depth
A. Hajnal, W. Maas, P. Pudlák, M. Szegedy, and G. Turán · 1993
Cited alongside, same era.
Perceptrons, PP, and the polynomial hierarchy
Richard Beigel · 1994
Cited alongside, same era.
On the size of weights for threshold gates
Johan Håstad · 1994
Cited alongside, same era.
A note on the simulation of exponential threshold weights
Thomas Hofmeister · 1996
Cited alongside, same era.
On the computational power of depth-2 circuits with threshold and modulo gates
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
Later among the works it cites.
Complexity of depth-2 circuits with threshold gates
Kazuyuki Amano and Akira Maruoka · 2005
Later among the works it cites.
On computation and communication with small bias
Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf · 2007
Later among the works it cites.
Exact threshold circuits
Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii · 2010
Later among the works it cites.
The sign-rank of AC 0 {}^{\mbox{0}}
Alexander A. Razborov and Alexander A. Sherstov · 2010
Later among the works it cites.
The pattern matrix method
Alexander A. Sherstov · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Matthias Krause and Pavel Pudlák · 1997
Cited alongside, same era.
Communication complexity
Eyal Kushilevitz and Noam Nisan · 1997
Cited alongside, same era.
Simulating threshold circuits by majority circuits
Mikael Goldmann and Marek Karpinski · 1998
Cited alongside, same era.
Computing boolean functions by polynomials and threshold circuits
Matthias Krause and Pavel Pudlák · 1998
Cited alongside, same era.
A linear lower bound on the unbounded error probabilistic communication complexity
Jürgen Forster · 2001
Cited alongside, same era.
Polynomial threshold functions and boolean threshold circuits
Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii · 2015
Later among the works it cites.
Improved bounds on the sign-rank of acˆ0
Mark Bun and Justin Thaler · 2016
Later among the works it cites.
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.
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.
Dual polynomials and communication complexity of XOR functions
Arkadev Chattopadhyay and Nikhil S. Mande · 2017
Closest in time.