A Short List of Equalities Induces Large Sign-Rank
From MaRDI portal
Publication:5087014
DOI10.1137/19M1271348zbMath1502.68124OpenAlexW4282834582MaRDI QIDQ5087014
Nikhil S. Mande, Arkadev Chattopadhyay
Publication date: 8 July 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1271348
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic communication complexity
- Learning intersections and thresholds of halfspaces
- On the computational power of Boolean decision lists
- Majority gates vs. general weighted threshold gates
- Computing Boolean functions by polynomials and threshold circuits
- Perceptrons, PP, and the polynomial hierarchy
- The landscape of communication complexity classes
- Threshold circuits of bounded depth
- Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- The unbounded-error communication complexity of symmetric functions
- Polynomial threshold functions and Boolean threshold circuits
- The Sign-Rank of AC$^0$
- The Pattern Matrix Method
- Harmonic Analysis of Polynomial Threshold Functions
- On the Power of Threshold Circuits with Small Weights
- Simulating Threshold Circuits by Majority Circuits
- Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
- Spectral analysis of Boolean functions as a graph eigenvalue problem
- Improved Bounds on the Sign-Rank of AC^0
- Structure of Protocols for XOR Functions
- Communication Complexity
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
- Probabilistic rank and matrix rigidity
- Addition is exponentially harder than counting for shallow monotone circuits
- On small depth threshold circuits
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
- On the Power of Statistical Zero Knowledge
- The Log-Approximate-Rank Conjecture Is False
- Analysis of Boolean Functions
- Bootstrapping results for threshold circuits “just beyond” known lower bounds
- Quantified derandomization of linear threshold circuits
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Efficient quantum protocols for XOR functions
- An invariance principle for polytopes
- Probability and Computing
- Mathematical Foundations of Computer Science 2005
- A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
This page was built for publication: A Short List of Equalities Induces Large Sign-Rank
