Breaking the Minsky--Papert Barrier for Constant-Depth Circuits (Q4554070): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Quantum lower bounds for the collision and the element distinctness problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3002756 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Any AND-OR Formula of Size <i>N</i> Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer / rank
 
Normal rank
Property / cites work
 
Property / cites work: The expressive power of voting polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$ / rank
 
Normal rank
Property / cites work
 
Property / cites work: Perceptrons, PP, and the polynomial hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: PP is closed under intersection / rank
 
Normal rank
Property / cites work
 
Property / cites work: Harmonic Analysis of Polynomial Threshold Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Dual lower bounds for approximate degree and Markov-Bernstein inequalities / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hardness Amplification and the Approximate Degree of Constant-Depth Circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3002797 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3002823 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Majority gates vs. general weighted threshold gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4320535 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4228473 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Size of Weights for Threshold Gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4449183 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning intersections and thresholds of halfspaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3093360 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Unconditional lower bounds for learning intersections of halfspaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the computational power of Boolean decision lists / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the computational power of depth-2 circuits with threshold and modulo gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing Boolean functions by polynomials and threshold circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Communication Complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Disjointness is hard in the multiparty number-on-the-forehead model / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5595902 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the degree of Boolean functions as real polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: New degree bounds for polynomial threshold functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximating threshold circuits by rational functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Perceptrons of Large Weight / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Uniform Lower Bound on Weights of Perceptrons / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Sign-Rank of AC$^0$ / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5365063 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Separating ${AC}^0$ from Depth-2 Majority Circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Pattern Matrix Method / rank
 
Normal rank
Property / cites work
 
Property / cites work: Strong Direct Product Theorems for Quantum Communication and Query Complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3191590 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Intersection of Two Halfspaces Has High Threshold Degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3191588 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Communication Lower Bounds Using Directional Derivatives / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Multiparty Communication Complexity of Set Disjointness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3633949 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Rational approximation techniques for analysis of neural networks / rank
 
Normal rank

Revision as of 06:30, 17 July 2024

scientific article; zbMATH DE number 6974574
Language Label Description Also known as
English
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
scientific article; zbMATH DE number 6974574

    Statements

    Breaking the Minsky--Papert Barrier for Constant-Depth Circuits (English)
    0 references
    7 November 2018
    0 references
    polynomial representations of Boolean functions
    0 references
    polynomial threshold functions
    0 references
    threshold degree
    0 references
    computational learning theory
    0 references
    communication complexity theory
    0 references
    polynomial approximation theory
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references