Rectangles Are Nonnegative Juntas
From MaRDI portal
Publication:5890971
DOI10.1137/15M103145XzbMath1353.68130MaRDI QIDQ5890971
No author found.
Publication date: 28 October 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
The Untold Story of $$\mathsf {SBP}$$, Random oracles and non-uniformity, The landscape of communication complexity classes, Deterministic Communication vs. Partition Number, Communication complexity with small advantage, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), Unnamed Item, On the binary and Boolean rank of regular matrices, Query-to-Communication Lifting for BPP, Unnamed Item, Extension Complexity of Independent Set Polytopes, Unifying presampling via concentration bounds, Dimension-free bounds and structural results in communication complexity, Unnamed Item, From Expanders to Hitting Distributions and Simulation Theorems, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On derandomized composition of Boolean functions, Nondeterministic and randomized Boolean hierarchies in communication complexity, Query-To-Communication Lifting for BPP Using Inner Product, Unnamed Item, Communication Complexity of Statistical Distance, Query-to-Communication Lifting Using Low-Discrepancy Gadgets, Unnamed Item, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, MaxSAT Resolution and Subcube Sums
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- The communication complexity of addition
- Probabilistic communication complexity
- Disjointness is hard in the multiparty number-on-the-forehead model
- Boolean function complexity. Advances and frontiers.
- Private vs. common random bits in communication complexity
- On the distributional complexity of disjointness
- PP-lowness and a simple definition of AWPP
- Problems and results in extremal combinatorics. I.
- Towards proving strong direct product theorems
- Separation of the monotone NC hierarchy
- Arthur-Merlin streaming complexity
- The unbounded-error communication complexity of symmetric functions
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- Error-bounded probabilistic computations between MA and AM
- A strong direct product theorem for disjointness
- Algebrization
- The Sign-Rank of AC$^0$
- Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- The Pattern Matrix Method
- Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
- Composition Theorems in Communication Complexity
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Threshold Computation and Cryptographic Security
- Deterministic Communication vs. Partition Number
- The Landscape of Communication Complexity Classes.
- Quantum communication complexity of symmetric predicates
- Communication Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Analysis of Boolean Functions
- En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
- Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound
- The multiparty communication complexity of set disjointness
- Quantum computing, postselection, and probabilistic polynomial-time
- Lower Bounds for Quantum Communication Complexity
- Communication Lower Bounds Using Directional Derivatives
- Rectangles Are Nonnegative Juntas
