A short list of equalities induces large sign-rank

DOI10.1137/19M1271348zbMATH Open1502.68124OpenAlexW4282834582MaRDI QIDQ5087014FDOQ5087014

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

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

zbMATH Keywords

approximation theorycommunication complexitysign-rankBoolean threshold circuits

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Analysis of Boolean Functions
• Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
• Communication Complexity
• Harmonic Analysis of Polynomial Threshold Functions
• Probability and Computing
• Majority gates vs. general weighted threshold gates
• Threshold circuits of bounded depth
• The Pattern Matrix Method
• The Sign-Rank of AC$^0$
• Probabilistic communication complexity
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2005
• Computing Boolean functions by polynomials and threshold circuits
• Perceptrons, PP, and the polynomial hierarchy
• Title not available (Why is that?)
• On the Power of Threshold Circuits with Small Weights
• Learning intersections and thresholds of halfspaces
• On the computational power of Boolean decision lists
• Simulating Threshold Circuits by Majority Circuits
• On small depth threshold circuits
• An invariance principle for polytopes
• Title not available (Why is that?)
• Communication complexities of symmetric XOR functions
• Spectral analysis of Boolean functions as a graph eigenvalue problem
• A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
• On the Power of Statistical Zero Knowledge
• Efficient quantum protocols for XOR functions
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• The unbounded-error communication complexity of symmetric functions
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• The landscape of communication complexity classes
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• Structure of Protocols for XOR Functions
• Probabilistic rank and matrix rigidity
• Polynomial threshold functions and Boolean threshold circuits
• Bootstrapping results for threshold circuits “just beyond” known lower bounds
• Quantified derandomization of linear threshold circuits
• Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
• The Log-Approximate-Rank Conjecture Is False
• Improved Bounds on the Sign-Rank of AC^0
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• Addition is exponentially harder than counting for shallow monotone circuits
• A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• 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)