The Computational Complexity of Equivalence and Isomorphism Problems

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Lecture Notes in Computer Science

• Publication date

  2000-08-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/3-540-45303-2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A separation of syntactic and nonsyntactic (1,+k)-branching programs

  2000cited by this paper
• Uniform Generation of NP-Witnesses Using an NP-Oracle

  2000cited by this paper
• Equivalence Test and Ordering Transformation for Parity-OBDDs of Different Variable Ordering

  1998cited by this paper
• The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits

  1998cited by this paper
• Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract)

  1998cited by this paper
• On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions

  1998cited by this paper
• A probabilistic nonequivalence test for syntactic (1,+k)-branching programs

  1998cited by this paper
• The minimum equivalent DNF problem and shortest implicants

  1998cited by this paper
• Parity OBDDs Cannot be Handled Efficiently Enough

  1998cited by this paper
• The Satisfiability Problem for Probabilistic Ordered Branching Programs

  1998cited by this paper
• Randomization and Nondeterminism Are Comparable for Ordered Read-Once Branching Programs

  1997cited by this paper
• The minimization problem for Boolean formulas

  1997cited by this paper
• Another proof that bpp?ph (and more)

  1997cited by this paper
• On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagrams

  1997cited by this paper
• A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

  1997cited by this paper
• Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization

  1997cited by this paper
• Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams

  1997cited by this paper
• Reducing randomness via irrational numbers

  1997cited by this paper
• The Complexity of Generating and Checking Proffs of Membership

  1996cited by this paper
• Mod-2-OBDDs—A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams

  1996cited by this paper
• Introduction to the Theory of Computation

  1996cited by this paper
• On the Power of Randomized Branching Programs

  1996cited by this paper
• Partitioned ROBDDs-a compact, canonical and efficiently manipulable representation for Boolean functions

  1996cited by this paper
• Improving the Variable Ordering of OBDDs Is NP-Complete

  1996cited by this paper
• The Boolean isomorphism problem

  1996cited by this paper
• On Unique Satisfiability and the Threshold Behavior of Randomized Reductions

  1995cited by this paper
• On the Size of Binary Decision Diagrams Representing Boolean Functions

  1995cited by this paper
• Perlen der theoretischen Informatik

  1995cited by this paper
• Graph Driven BDDs - A New Data Structure for Boolean Functions

  1995cited by this paper
• Restricted branching programs and hardware verification

  1995cited by this paper
• Efficient algorithms for the transformation between different types of binary decision diagrams

  1994cited by this paper
• Oracles and Queries That Are Suucient for Exact Learning

  1994cited by this paper
• Efficient Boolean Manipulation With OBDD's can be Extended to FBDD's

  1994cited by this paper
• Oracles and queries that are sufficient for exact learning (extended abstract)

  1994cited by this paper
• Efficient data structures for Boolean functions

  1994cited by this paper
• On the Complexity of Constructing Optimal Ordered Binary Decision Diagrams

  1994cited by this paper
• Reduction of OBDDs in Linear Time

  1993cited by this paper
• A Logspace Algorithm for Tree Canonization

  1992cited by this paper
• IP = PSPACE

  1992cited by this paper
• Symbolic Boolean manipulation with ordered binary-decision diagrams

  1992cited by this paper
• A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications

  1992cited by this paper
• The history and status of the P versus NP question

  1992cited by this paper
• On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication

  1991cited by this paper
• Lower Bounds for Depth-Restricted Branching Programs

  1991cited by this paper
• PP is as Hard as the Polynomial-Time Hierarchy

  1991cited by this paper
• A Catalog of Complexity Classes

  1991cited by this paper
• Separating the eraser Turing machine classes I+, NIL,, co-N!+_ and P,

  1991cited by this paper
• Simulating BPP using a general weak random source

  1991cited by this paper
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

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

  1990cited by this paper
• The Effect of Null-Chains on the Complexity of Contact Schemes

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

  1989cited by this paper
• Graph-based Algorithm for Boolean Function Manipulation

  1989cited by this paper
• Boolean functions, invariance groups and parallel complexity

  1989cited by this paper
• Modified Branching Programs and Their Computational Power

  1989cited by this paper
• A personal communication

  1989cited by this paper
• What is Structural Complexity Theory

  1989cited by this paper
• Are There Interactive Protocols for CO-NP Languages?

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

  1988cited by this paper
• On the complexity of branching programs and decision trees for clique functions

  1988cited by this paper
• The complexity of Boolean functions

  1987cited by this paper
• A Lower Bound for Read-Once-Only Branching Programs

  1987cited by this paper
• Probabilistic Complexity Classes and Lowness

  1987cited by this paper
• Graph Isomorphism is in the Low Hierarchy

  1987cited by this paper
• Does co-NP Have Short Interactive Proofs?

  1987cited by this paper
• Complexity and Structure

  1986cited by this paper
• Private coins versus public coins in interactive proof systems

  1986cited by this paper
• Random Generation of Combinatorial Structures from a Uniform Distribution

  1986cited by this paper
• On Approximation Algorithms for #P

  1985cited by this paper
• Trading group theory for randomness

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

  1985cited by this paper
• An Exponential Lower Bound for One-Time-Only Branching Programs

  1984cited by this paper
• Algebraic coding theory

  1984cited by this paper
• BPP and the Polynomial Hierarchy

  1983cited by this paper
• A complexity theoretic approach to randomness

  1983cited by this paper
• Two remarks on the power of counting

  1983cited by this paper
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

  1983cited by this paper
• On the Unique Satisfiability Problem

  1982cited by this paper
• Group-Theoretic Algorithms and Graph Isomorphism

  1982cited by this paper
• Fast Probabilistic Algorithms for Verification of Polynomial Identities

  1980cited by this paper
• Equivalence of Free Boolean Graphs can be Decided Probabilistically in Polynomial Time

  1980cited by this paper
• Universal Classes of Hash Functions

  1979cited by this paper
• A polynomial algorithm in linear programming

  1979cited by this paper
• Probabilistic algorithms for sparse polynomials

  1979cited by this paper
• Introduction to Automata Theory, Languages and Computation

  1979cited by this paper
• The Complexity of Equivalence and Containment for Free Single Variable Program Schemes

  1978cited by this paper
• NP-Complete Decision Problems for Binary Quadratics

  1978cited by this paper
• Probabilistic Machines Can Use Less Running Time

  1977cited by this paper
• A fast algorithm for the string editing problem and decision graph complexity

  1976cited by this paper
• The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space

  1972cited by this paper
• COUNTING THEOREMS AND THEIR APPLICATIONS TO CLASSIFICATION OF SWITCHING FUNCTIONS

  1971cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper
• Factoring polynomials over large finite fields*

  1970cited by this paper
• On Asymptotic Estimates in Switching and Automata Theory

  1966cited by this paper
• The Recognition Problem for the Set of Perfect Squares

  1966cited by this paper
• Representation of switching circuits by binary-decision programs

  1959cited by this paper
• The synthesis of two-terminal switching circuits

  1949cited by this paper
• Sur les types des propositions composées

  1940cited by this paper
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen

  1937cited by this paper

• Non-isomorphic CNF Generation

  2021cites this paper
• Complexity-based partitioning of CSFI problem instances with Transformers

  2021cites this paper
• Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

  2020cites this paper
• Edge criticality in secure graph domination

  2015cites this paper
• The Complexity of some exact and approximate isomorphism problems[HBNI Th80]

  2014cites this paper
• Instruction Sequence Based Non-uniform Complexity Classes

  2013cites this paper
• On the Isomorphism Problem for Decision Trees and Decision Lists

  2013cites this paper
• Ju l 2 01 3 Instruction Sequence Based Non-uniform Complexity Classes

  2013cites this paper
• Strong isomorphism reductions in complexity theory

  2011cites this paper
• Equilibria problems on games: Complexity versus succinctness

  2011cites this paper
• Complexity classes of equivalence problems revisited

  2009influential citation
• Overview of Cryptanalysis Techniques in Multivariate Public Key Cryptography

  2009cites this paper
• The Complexity of Equivalence Relations

  2008cites this paper
• Integrated Project Member of the FET Proactive Initiative Complex Systems DELIS-TR-404 Equilibria problems on Games: Complexity versus succintnes

  2006cites this paper
• Pure Nash Equilibria in Games with a Large Number of Actions

  2005cites this paper
• On the Computational Complexity of the Forcing Chromatic Number

  2004cites this paper
• Approximate Algorithms for Minimization of Binary Decision Diagrams on the Basis of Linear Transformations of Variables

  2004cites this paper
• The Complexity of Boolean Constraint Isomorphism

  2003cites this paper
• Application of BDDs in Boolean matching techniques for formal logic combinational verification

  2001cites this paper
• Permutation Independent Comparison of Pseudo Boolean Functions

  2000cites this paper