A direct product theorem for two-party bounded-round public-coin communication complexity
From MaRDI portal
(Redirected from Publication:343852)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Recommendations
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- On public-coin zero-error randomized communication complexity
- Two-party direct-sum questions through the lens of multiparty communication complexity
- Communication Complexity in Algebraic Two-Party Protocols
- The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
- On the complexity of interactive proofs with bounded communication
- On the exact round complexity of self-composable two-party computation
- Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation
- Lower bounds on the multiparty communication complexity
Cites work
- scientific article; zbMATH DE number 1954386 (Why is no real title available?)
- scientific article; zbMATH DE number 2038719 (Why is no real title available?)
- scientific article; zbMATH DE number 1559552 (Why is no real title available?)
- scientific article; zbMATH DE number 5485573 (Why is no real title available?)
- A Parallel Repetition Theorem
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- A strong direct product theorem for disjointness
- A strong direct product theorem for quantum query complexity
- An information statistics approach to data stream and communication complexity
- An interactive information odometer and applications
- Communication Complexity
- Direct product via round-preserving compression
- Elements of Information Theory
- How to compress interactive communication
- Improved direct product theorems for randomized query complexity
- Information Equals Amortized Communication
- Information Equals Amortized Communication
- Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
- New strong direct product results in communication complexity
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- On the distributional complexity of disjointness
- Parallel repetition: simplification and the no-signaling case
- Products and Help Bits in Decision Trees
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Robustness of quantum Markov chains
- The communication complexity of pointer chasing
- Towards proving strong direct product theorems
Cited in
(16)- Lifting query complexity to time-space complexity for two-way finite automata
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- New strong direct product results in communication complexity
- The direct sum of universal relations
- Simulation theorems via pseudo-random properties
- Interactive Information Complexity
- A parallel repetition theorem for entangled projection games
- Interactive information complexity
- scientific article; zbMATH DE number 1559552 (Why is no real title available?)
- Certifying equality with limited interaction
- Superlinear lower bounds for multipass graph processing
- Towards a reverse Newman's theorem in interactive information complexity
- A strong direct product theorem for quantum query complexity
- The communication complexity of set intersection and multiple equality testing
- Lifting Theorems for Equality
- Direct product via round-preserving compression
This page was built for publication: A direct product theorem for two-party bounded-round public-coin communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q343852)
