A direct product theorem for two-party bounded-round public-coin communication complexity
DOI10.1007/S00453-015-0100-0zbMATH Open1353.68085OpenAlexW2277697754MaRDI QIDQ343852FDOQ343852
Authors: Rahul Jain, Attila Pereszlényi, Penghui Yao 
Publication date: 29 November 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0100-0
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
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)
Cites Work
- Elements of Information Theory
- Robustness of quantum Markov chains
- Communication Complexity
- An information statistics approach to data stream and communication complexity
- A Parallel Repetition Theorem
- On the distributional complexity of disjointness
- Towards proving strong direct product theorems
- New strong direct product results in communication complexity
- How to compress interactive communication
- A strong direct product theorem for disjointness
- An interactive information odometer and applications
- Information Equals Amortized Communication
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- Parallel repetition: simplification and the no-signaling case
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- A strong direct product theorem for quantum query complexity
- Products and Help Bits in Decision Trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
- Title not available (Why is that?)
- Direct product via round-preserving compression
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Information Equals Amortized Communication
- The communication complexity of pointer chasing
- Improved direct product theorems for randomized query complexity
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
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
- Title not available (Why is that?)
- 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)
