A short list of equalities induces large sign-rank

Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

The Sign-Rank of AC^0
Separation of unbounded-error models in multi-party communication complexity
Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
Separating AC\(^0\) from depth-2 majority circuits

Cites work

A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
Addition is exponentially harder than counting for shallow monotone circuits
An invariance principle for polytopes
Analysis of Boolean Functions
Average-case lower bounds and satisfiability algorithms for small threshold circuits
Bootstrapping results for threshold circuits ``just beyond known lower bounds
Communication complexities of symmetric XOR functions
Communication Complexity
Computing Boolean functions by polynomials and threshold circuits
Efficient quantum protocols for XOR functions
Harmonic Analysis of Polynomial Threshold Functions
scientific article; zbMATH DE number 2081103 (Why is no real title available?)
scientific article; zbMATH DE number 7250148 (Why is no real title available?)
scientific article; zbMATH DE number 3314813 (Why is no real title available?)
scientific article; zbMATH DE number 3385535 (Why is no real title available?)
Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
Learning intersections and thresholds of halfspaces
Majority gates vs. general weighted threshold gates
Mathematical Foundations of Computer Science 2005
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
On small depth threshold circuits
On the computational power of Boolean decision lists
On the power of statistical zero knowledge
On the Power of Threshold Circuits with Small Weights
Perceptrons, PP, and the polynomial hierarchy
Polynomial threshold functions and Boolean threshold circuits
Probabilistic communication complexity
Probabilistic rank and matrix rigidity
Probability and Computing
Quantified derandomization of linear threshold circuits
Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
Simulating Threshold Circuits by Majority Circuits
Spectral analysis of Boolean functions as a graph eigenvalue problem
Structure of protocols for XOR functions
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
The landscape of communication complexity classes
The large-error approximate degree of \(\mathrm{AC}^0\)
The Log-Approximate-Rank Conjecture Is False
The pattern matrix method
The Sign-Rank of AC^0
The unbounded-error communication complexity of symmetric functions
Threshold circuits of bounded depth
Toward attribute efficient learning of decision lists and parities

Cited in

(4)

Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
Sign-rank can increase under intersection
Sign-rank can increase under intersection
Linear threshold functions in decision lists, decision trees, and depth-2 circuits

This page was built for publication: A short list of equalities induces large sign-rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5087014)