The polynomial method in circuit complexity

By R. Beigel. 1993

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “The lower bound for the classification accuracy using low-degree polynomials has been widely studied as the (approximate) threshold degree of a function or the sign-rank of a matrix [18, 21, 25, 41, 75, 81].”
Learning DNF in time 2 Õ(n 1/3 ) . (2001, background): “Since then, complexity theorists have used these and related properties of polynomial threshold functions to prove several important results in both circuit and structural complexity [3, 4, 7, 21, 45].”
New degree bounds for polynomial threshold functions (2003, background): “Polynomial threshold functions are an interesting and natural representation for Boolean functions which have many applications in complexity theory and learning theory, see, e.g., [2, 4, 5, 3 , 22, 14, 13].”
Automatic Security Evaluation and (Related-key) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES(L) and Other Bit-Oriented Block Ciphers (2014, background): “append ((str(t[0]) + ’ ’ + inX [0] + ’ + ’ +\ str(t[1]) + ’ ’ + inX [1] + ’ + ’ +\ str(t[2]) + ’ ’ + inX [2] + ’ + ’ +\ str(t[3]) + ’ ’ + inX [3] + ’ + ’ +\ str(t[4]) + ’ ’ + outY [0] + ’ + ’ +\ str(t[5]) + ’ ’ + outY [1] + ’ + ’ +\ str(t[6]) + ’ ’ + outY [2] + ’ + ’ +\ str(t[7]) + ’ ’ + outY [3] + ”
Complexity measures and decision tree complexity: a survey (2002, methodology): “The complexity measures discussed here also have interesting relations with circuit complexity [Weg87, Bei93, Bop97], parallel computing [CDR86, Sim83, Nis91, Weg87], communication complexity [NW95, BW99], and the construction of oracles in complexity theory [BI87, Tar89, FFKL93, FR98].”