The communication complexity of enumeration, elimination, and selection
From MaRDI portal
Publication:5956009
DOI10.1006/jcss.2001.1761zbMath0989.68058OpenAlexW2105010107MaRDI QIDQ5956009
Andris Ambainis, William I. Gasarch, Bala Kalyanasundaram, Harry Buhrman, Leen Torenvliet
Publication date: 11 April 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/1151
Related Items
The communication complexity of functions with large outputs, The choice and agreement problems of a random function, Parallel Repetition of the Odd Cycle Game, Choosing, agreeing, and eliminating in communication complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- Relations between communication complexity classes
- On the direct sum conjecture
- A note on enumerative counting
- On self-reducibility and weak P-selectivity
- The complexity of optimization problems
- Reductions on NP and p-selective sets
- Bounded queries to SAT and the Boolean hierarchy
- On the distributional complexity of disjointness
- Realizing Boolean functions on disjoint sets of variables
- On the direct sum conjecture in the straight line model
- Communication complexity and combinatorial lattice theory
- Terse, superterse, and verbose sets
- Bounded queries in recursion theory
- ``Global graph problems tend to be intractable
- Enumerative counting is hard
- Quantifying the amount of verboseness
- Graph minors. XIII: The disjoint paths problem
- Approximable sets
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- On membership comparable sets
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- On the density of families of sets
- The Probabilistic Communication Complexity of Set Intersection
- A proof of Beigel's cardinality conjecture
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- A cardinality version of Beigel's nonspeedup theorem
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Amortized Communication Complexity
- Polynomial-Time Membership Comparable Sets
- Communication Complexity
- The complexity of ODDnA
- Semirecursive Sets and Positive Reducibility
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Theory of semi-feasible algorithms
