One help-bit doesn't help

No abstract is available for this paper.

• Publication year

  1998

• Venue

  Symposium on the Theory of Computing

• Publication date

  1998-05-23

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/276698.276720
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximable sets

  1995cited by this paper
• Recursion Theoretic Properties of Frequency Computation and Bounded Queries

  1995cited by this paper
• Amortized Communication Complexity

  1995cited by this paper
• Super-logarithmic depth lower bounds via the direct sum in communication complexity

  1995cited by this paper
• Frequency computation and bounded queries

  1995cited by this paper
• Products and help bits in decision trees

  1994cited by this paper
• Terse, Superterse, and Verbose Sets

  1993cited by this paper
• Frequency computations and the cardinality theorem

  1992cited by this paper
• A proof of Beigel's cardinality conjecture

  1992cited by this paper
• Quantifying the Amount of Verboseness

  1992cited by this paper
• Some connections between bounded query classes and nonuniform complexity

  1990cited by this paper
• On the extended direct sum conjecture

  1989cited by this paper
• Bounded query classes and the difference hierarchy

  1989cited by this paper
• Lower bounds for constant depth circuits in the presence of help bits

  1989cited by this paper
• Polynomial Terse Sets

  1988cited by this paper
• Enumerative counting is hard

  1988cited by this paper
• Query-limited reducibilities

  1988cited by this paper
• A Structural Theorem that Depends Quantitatively on the Complexity of SAT

  1987cited by this paper
• Meshes with multiple buses

  1986cited by this paper
• On the Validity of the Direct Sum Conjecture

  1986cited by this paper
• M. J. Fischer: On the Complexity of 2-Output Boolean Networks

  1981cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Realizing Boolean Functions on Disjoint sets of Variables

  1974cited by this paper
• The Theory of Automata, a Survey

  1961cited by this paper

• The Value of Help Bits in Randomized and Average-Case Complexity

  2014cites this paper
• Choosing, Agreeing, and Eliminating in Communication Complexity

  2010cites this paper
• The Computational Power of a Family of Decision Forests

  2001cites this paper
• The communication complexity of enumeration, elimination, and selection

  2000cites this paper