A characterization of Hash P by arithmetic straight line programs

No abstract is available for this paper.

• Publication year

  1990

• Venue

  Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science

• Publication date

  1990-10-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FSCS.1990.89521
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Nondeterministic exponential time has two-prover interactive protocols

  1990cited by this paper
• Counting Classes: Thresholds, Parity, Mods, and Fewness

  1990cited by this paper
• Algebraic methods for interactive proof systems

  1990cited by this paper
• Designing programs that check their work

  1989cited by this paper
• The Knowledge Complexity of Interactive Proof Systems

  1989cited by this paper
• On the computational power of PP and (+)P

  1989cited by this paper
• Circuit Definitions of Nondeterministic Complexity Classes

  1988cited by this paper
• Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes

  1988cited by this paper
• Proofs that yield nothing but their validity and a methodology of cryptographic protocol design

  1986cited by this paper
• NP is as easy as detecting unique solutions

  1985cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Computers and In stractability: A Guide to the Theory of NP-Completeness. W. H Freeman, San Fran

  1979cited by this paper

• Interactive Proofs

  2017cites this paper
• List of publications in reverse chronological order with clickable links

  2014cites this paper
• Arithmetization: a New Method in Structural Complexity Theory

  2010cites this paper
• The Complexity of Equivalence Relations

  2008cites this paper
• Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently while Concealing it

  1998cites this paper
• On Satisfiability

  1996cites this paper
• ! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% * %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - )% " %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1996cites this paper
• On superlinear lower bounds in complexity theory

  1995cites this paper
• Program result-checking: a theory of testing meets a test of theory

  1994cites this paper
• On the Interactive Complexity of Graph Reliability

  1994cites this paper
• Simple Characterizations of P(#P) and Complete Problems

  1994cites this paper
• Representing Boolean functions as polynomials modulo composite numbers

  1992cites this paper
• Is BP.+P a Probabilistic Class?

  1991cites this paper
• Languages that are easier than their proofs

  1991cites this paper
• Arithmetization: A new method in structural complexity theory

  1991cites this paper