The communication complexity of enumeration, elimination, and selection

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

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 ODD_n^A
• Semirecursive Sets and Positive Reducibility
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Theory of semi-feasible algorithms

This page was built for publication: The communication complexity of enumeration, elimination, and selection