Fetching the paper…
Reading the bibliography…
Proving super-polynomial size lower bounds for $\textsf{TC}^0$, the class of constant-depth, polynomial-size circuits of Majority gates, is a notorious open problem in complexity theory.
Theory of majority decision elements
Saburo Muroga, Iwao Toda, and Satoru Takasu · 1961
Earlier work this paper cites.
Rapid multiplication of rectangular matrices
Don Coppersmith · 1982
Earlier work this paper cites.
On constructing minimum spanning trees in k-dimensional spaces and related problems
Andrew Chi-Chih Yao · 1982
Earlier work this paper cites.
Probabilistic communication complexity
Ramamohan Paturi and Janos Simon · 1986
Earlier work this paper cites.
Unbiased bits from sources of weak randomness and probabilistic communication complexity
Benny Chor and Oded Goldreich · 1988
Earlier work this paper cites.
Andrew Chi-Chih Yao · 1990
Earlier work this paper cites.
Euclidean minimum spanning trees and bichromatic closest pairs
Pankaj K Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl · 1991
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.
Computing dominances in eˆn
Jiří Matoušek · 1991
Earlier work this paper cites.
Majority gates VS. general weighted threshold gates
Mikael Goldmann, Johan Håstad, and Alexander A. Razborov · 1992
Earlier work this paper cites.
Efficient partition trees
Jiří Matoušek · 1992
Earlier work this paper cites.
A linear lower bound for the size of threshold circuits
Hans Dietmar Groeger and György Turán · 1993
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 · 1993
Earlier work this paper cites.
nˆomega(log n) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
Alexander A. Razborov and Avi Wigderson · 1993
Earlier work this paper cites.
A uniform circuit lower bound for the permanent
Eric Allender and Vivek Gore · 1994
Earlier work this paper cites.
Approximating threshold circuits by rational functions
Ramamohan Paturi and Michael E. Saks · 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.
A note on the simulation of exponential threshold weights
Thomas Hofmeister · 1996
Earlier work this paper cites.
Size-depth tradeoffs for threshold circuits
Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks · 1997
Earlier work this paper cites.
Upper bounds for maxsat: Further improved
Nikhil Bansal and Venkatesh Raman · 1999
Earlier work this paper cites.
Parameterizing above guaranteed values: Maxsat and maxcut
Meena Mahajan and Venkatesh Raman · 1999
Earlier work this paper cites.
Faster exact solutions for MAX2SAT
Jens Gramm and Rolf Niedermeier · 2000
Earlier work this paper cites.
A new algorithm for MAX-2-SAT
Edward A. Hirsch · 2000
Earlier work this paper cites.
New upper bounds for maximum satisfiability
Rolf Niedermeier and Peter Rossmanith · 2000
Earlier work this paper cites.
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
Earlier work this paper cites.
A linear lower bound on the unbounded error probabilistic communication complexity
Jürgen Forster · 2002
Cited alongside, same era.
Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT
Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, and Peter Rossmanith · 2003
Cited alongside, same era.
Worst-case study of local search for max-k-sat
Edward A. Hirsch · 2003
Cited alongside, same era.
Faster algorithms for MAX CUT and MAX csp, with polynomial expected time for sparse instances
Alex D. Scott and Gregory B. Sorkin · 2003
Cited alongside, same era.
Improved exact algorithms for m ax \displaystyle{}_{\mbox{ax}} -s at \displaystyle{}_{\mbox{at}}
Jianer Chen and Iyad A. Kanj · 2004
Cited alongside, same era.
On the complexity of depth-2 circuits with threshold gates
Kazuyuki Amano and Akira Maruoka · 2005
New exact algorithms for the 2-constraint satisfaction problem
Alexander Golovnev and Konstantin Kutzkov · 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.
Nonuniform acc circuit lower bounds
Ryan Williams · 2014
Later among the works it cites.
Improved algorithms for sparse MAX-SAT and max-k-csp
Ruiwen Chen and Rahul Santhanam · 2015
Later among the works it cites.
Polynomial threshold functions and boolean threshold circuits
Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii · 2015
Later among the works it cites.
Local reductions
Hamid Jahanjou, Eric Miles, and Emanuele Viola · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
On the parameterized complexity of exact satisfiability problems
Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith · 2005
Cited alongside, same era.
Automated generation of simplification rules for SAT and MAXSAT
Alexander S. Kulikov · 2005
Cited alongside, same era.
An improved exponential-time algorithm for k -sat
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane · 2005
Cited alongside, same era.
A new algorithm for optimal 2-constraint satisfaction and its implications
Ryan Williams · 2005
Cited alongside, same era.
A duality between clause width and clause density for SAT
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi · 2006
Cited alongside, same era.
MAX-SAT for formulas with constant clause density can be solved faster than in o(s 2 \displaystyle{}^{\mbox{2}} ) time
Evgeny Dantsin and Alexander Wolpert · 2006
Cited alongside, same era.
Solving sparse instances of max SAT via width reduction and greedy restriction
Takayuki Sakai, Kazuhisa Seto, and Suguru Tamaki · 2015
Later among the works it cites.
Polynomial representations of threshold functions and algorithmic applications
Josh Alman, Timothy M. Chan, and R. Ryan Williams · 2016
Later among the works it cites.
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams · 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.
Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama · 2016
Later among the works it cites.
A satisfiability algorithm for depth two circuits with a sub-quadratic number of symmetric and threshold gates
Suguru Tamaki · 2016
Later among the works it cites.
Natural proofs versus derandomization
R. Ryan Williams · 2016
Later among the works it cites.
Probabilistic rank and matrix rigidity
Josh Alman and R. Ryan Williams · 2017
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.
Separate, measure and conquer: Faster polynomial-space algorithms for max 2-csp and counting dominating sets
Serge Gaspers and Gregory B. Sorkin · 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 R. Ryan Williams · 2017
Later among the works it cites.
Quantified derandomization of linear threshold circuits
Roei Tell · 2017
Later among the works it cites.
Tighter connections between formula-sat and shaving logs
Amir Abboud and Karl Bringmann · 2018
Closest in time.
More consequences of falsifying seth and the orthogonal vectors conjecture [full version]
Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof · 2018
Closest in time.
Fine-grained complexity meets IP = PSPACE
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy Rothblum, and Aviad Rubinstein · 2018
Closest in time.
On the hardness of approximate and exact (bichromatic) maximum inner product
Lijie Chen · 2018
Closest in time.
The landscape of communication complexity classes
Mika Göös, Toniann Pitassi, and Thomas Watson · 2018
Closest in time.
Hardness of approximate nearest neighbor search
Aviad Rubinstein · 2018
Closest in time.
R. Ryan Williams · 2018
Closest in time.
On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity
Ryan Williams · 2018
Closest in time.