Lifting Theorems for Equality
From MaRDI portal
Recommendations
Cites work
- A composition theorem for randomized query complexity
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Amortized Communication Complexity
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Automata, Languages and Programming
- Boolean function complexity. Advances and frontiers.
- Communication Complexity
- Communication complexity towards lower bounds on circuit depth
- Communication lower bounds using directional derivatives
- Complexity measures and decision tree complexity: a survey.
- Deterministic communication vs. partition number
- Direct product via round-preserving compression
- Extension complexity of independent set polytopes
- Fourier analysis for probabilistic communication complexity
- Fractional Covers and Communication Complexity
- From expanders to hitting distributions and simulation theorems
- How to compress interactive communication
- scientific article; zbMATH DE number 5568623 (Why is no real title available?)
- scientific article; zbMATH DE number 549856 (Why is no real title available?)
- scientific article; zbMATH DE number 2038719 (Why is no real title available?)
- scientific article; zbMATH DE number 7204504 (Why is no real title available?)
- scientific article; zbMATH DE number 5485573 (Why is no real title available?)
- Improved direct product theorems for randomized query complexity
- Information Equals Amortized Communication
- Lifting Nullstellensatz to monotone span programs over any field
- Lower bounds for elimination via weak regularity
- Lower bounds on information complexity via zero-communication protocols and applications
- Monotone circuit lower bounds from resolution
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- New strong direct product results in communication complexity
- On Slepian-Wolf theorem with interaction
- On the ratio of optimal integral and fractional covers
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Rectangles Are Nonnegative Juntas
- Separation of the monotone NC hierarchy
- Simplified lower bounds on the multiparty communication complexity of disjointness
- Simulation beats richness: new data-structure lower bounds
- Spectral analysis of Boolean functions as a graph eigenvalue problem
- Structure of protocols for XOR functions
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- The Communication Complexity of Correlation
- The communication complexity of gap Hamming distance
- The direct sum of universal relations
- The multiparty communication complexity of set disjointness
- The pattern matrix method
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Towards a reverse Newman's theorem in interactive information complexity
- Worst-case interactive communication. I. Two messages are almost optimal
- Zero-information protocols and unambiguity in Arthur-Merlin communication (extended abtract)
Cited in
(9)- Lifting induction theorems
- Simulation theorems via pseudo-random properties
- Congruence Boolean Lifting Property
- MaxSAT Resolution and Subcube Sums
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Randomized versus deterministic decision tree size
- One-way communication complexity of partial XOR functions
- Relations between monotone complexity measures based on decision tree complexity
- The hardness of decision tree complexity
This page was built for publication: Lifting Theorems for Equality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090501)
