Rectangles are nonnegative juntas
From MaRDI portal
Recommendations
Cites work
- A separation of NP and conp in multiparty communication complexity
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- A strong direct product theorem for disjointness
- Algebrization: a new barrier in complexity theory
- Analysis of Boolean Functions
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Arthur-Merlin streaming complexity
- Boolean function complexity. Advances and frontiers.
- Communication Complexity
- Communication lower bounds using directional derivatives
- Composition theorems in communication complexity
- Deterministic communication vs. partition number
- Disjointness is hard in the multiparty number-on-the-forehead model
- En route to the log-rank conjecture: new reductions and equivalent formulations
- Error-bounded probabilistic computations between MA and AM
- scientific article; zbMATH DE number 6687761 (Why is no real title available?)
- scientific article; zbMATH DE number 6696541 (Why is no real title available?)
- scientific article; zbMATH DE number 5605137 (Why is no real title available?)
- scientific article; zbMATH DE number 5568623 (Why is no real title available?)
- scientific article; zbMATH DE number 7204504 (Why is no real title available?)
- scientific article; zbMATH DE number 5937218 (Why is no real title available?)
- scientific article; zbMATH DE number 6789270 (Why is no real title available?)
- scientific article; zbMATH DE number 6292622 (Why is no real title available?)
- Information complexity versus corruption and applications to orthogonality and gap-Hamming
- Lower Bounds for Quantum Communication Complexity
- Lower bounds on information complexity via zero-communication protocols and applications
- Nonnegative rank vs. binary rank
- On the distributional complexity of disjointness
- PP-lowness and a simple definition of AWPP
- Private vs. common random bits in communication complexity
- Probabilistic communication complexity
- Problems and results in extremal combinatorics. I.
- Quantum communication complexity of symmetric predicates
- Quantum computing, postselection, and probabilistic polynomial-time
- Rectangles Are Nonnegative Juntas
- Separating AC\(^0\) from depth-2 majority circuits
- Separation of the monotone NC hierarchy
- Simplified lower bounds on the multiparty communication complexity of disjointness
- The communication complexity of addition
- The communication complexity of gap Hamming distance
- The landscape of communication complexity classes
- The multiparty communication complexity of set disjointness
- The pattern matrix method
- The Sign-Rank of AC^0
- The unbounded-error communication complexity of symmetric functions
- Threshold Computation and Cryptographic Security
- Towards proving strong direct product theorems
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Zero-information protocols and unambiguity in Arthur-Merlin communication
Cited in
(36)- Random oracles and non-uniformity
- The landscape of communication complexity classes
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- Communication complexity with small advantage
- On derandomized composition of Boolean functions
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- On the binary and Boolean rank of regular matrices
- Unifying presampling via concentration bounds
- Dimension-free bounds and structural results in communication complexity
- Deterministic communication vs. partition number
- Extension complexity of independent set polytopes
- Communication complexity of statistical distance
- From expanders to hitting distributions and simulation theorems
- Sunflowers and quasi-sunflowers from randomness extractors
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- The Untold Story of $$\mathsf {SBP}$$
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
- Query-to-communication lifting for BPP using inner product
- scientific article; zbMATH DE number 7564405 (Why is no real title available?)
- Quantum lower bounds for approximate counting via Laurent polynomials
- Query-to-communication lifting for BPP
- Monotone circuit lower bounds from resolution
- The layer complexity of Arthur-Merlin-like communication
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Query-to-communication lifting using low-discrepancy gadgets
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- MaxSAT Resolution and Subcube Sums
- Rectangles Are Nonnegative Juntas
- scientific article; zbMATH DE number 7758330 (Why is no real title available?)
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- Lifting dichotomies
- Lifting dichotomies
- Searching for falsified clause in random ( n)-CNFs is hard for randomized communication
This page was built for publication: Rectangles are nonnegative juntas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890971)
