Hasso-Plattner-Institut
 
    • de
 

... on Complexity

You can find lists of our papers that focus on other topics: 

  • Trust and Security Engineering 
  • Future Internet technologies: Web 3.0
  • Next-generation Internet applications in:
    Web-University,  Telemedicine and other applications
  • Innovation method design thinking
  • Theoretical Computer Science: BDDs

These are our reviewed conference papers on Computational Complexity

  • J. Bern, C. Damm, Christoph Meinel
    The Electronic Colloquium on Computational Complexity: A Digital Library in Use
    Proc. ECDL'97, Pisa (Italien), LNCS 1324, 1997, pp. 405-421.
  • Christoph Meinel, A. Slobodová
    A Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams
    Proc. STACS '97, Lübeck (Germany), LNCS 1200, Springer-Verlag 1997, pp. 213-224.
  • Christoph Meinel, S. Waack
    The "log Rank" Conjecture for Modular Communication Complexity
    Proc. STACS'96, Grenoble (France), LNCS 1046, Springer-Verlag 1996, pp. 619-630.
  • Christoph Meinel, S. Waack
    Lower Bounds on the Majority Communication Complexity of Various Graph Accessibility Problems
    Proc. MFCS'95, Prague (Czechia), LNCS 969, Springer-Verlag 1995, pp. 299-308.
  • Christoph Meinel, S. Waack
    Lower Bounds on the Modular Communication Complexity of Various Graph Accessibility Problems
    Proc. LATIN'95, Valparaiso (Chile), LNCS 911, Springer-Verlag 1995, pp. 427-435.
  • Christoph Meinel, S. Waack
    Matrix Rank Arguments for Proving Lower Bounds on Branching Programs
    Proc. AMCoT, Madras (India), 1994.
  • Christoph Meinel, A. Slobodová
    On the Complexity of Constructing Optimal Ordered Binary Decision Diagrams
    Proc. MFCS'94, Kosice (Slovakia), LNCS 841, Springer-Verlag 1994, 515-524.
  • Christoph Meinel, S. Waack
    Separating Complexity Classes Related to Bounded Alternating omega-Branching Programs
    Proc. ISAAC'93, Hong Kong, LNCS 762, Springer-Verlag 1993, 379-388.
  • J. Gergov, Christoph Meinel
    Frontiers of Feasible and Probabilistic Feasible Boolean Manipulation with Branching Programs
    Proc. STACS'93, Würzburg (Germany), LNCS 665, Springer-Verlag 1993, 576-585.
  • J. Gergov, Christoph Meinel
    Analysis and Manipulation of Boolean Functions in Terms of Decision Graphs
    Proc. WG'92, Frankfurt a. M. (Germany), LNCS 657, Springer-Verlag 1993, 310-320.
  • C. Damm, M. Krause, Christoph Meinel, S. Waack
    Separating Counting Communication Complexity Classes
    Proc. STACS'92, Paris (France), LNCS 577, Springer-Verlag 1992, 281-292.
  • Christoph Meinel
    Circuit Characterizations of Logarithmic Space-Bounded Complexity Classes
    Proc. CSL'91, Berne (Switzerland), 1991.
  • Christoph Meinel, S. Waack
    Upper and Lower Bounds for Certain GRAPH-ACCESSIBILITY-PROBLEMs on Bounded Alternating omega-Branching Programs
    Proc. MFCS'91, Kazimierz Dolny (Poland), LNCS 520, Springer-Verlag 1991, 337-435.
  • G. Buntrock, C. Damm, U. Hertrampf, Christoph Meinel
    Structure and Importance of Logspace-MOD-Classes
    Proc. STACS'91, Hamburg (Germany), LNCS 480, Springer-Verlag 1991, 360-371.
  • C. Damm, M. Krause, Christoph Meinel, S. Waack
    Separating Logarithmic Space-Bounded Counting Classes
    Proc. Kleene'90, Varna (Bulgaria), 1990.
  • Christoph Meinel
    Restricted Branching Programs and Their Computational Power
    Proc. MFCS'90, LNCS 452, Springer-Verlag 1990, 61-75.
  • C. Damm, Christoph Meinel
    Separating Complexity Classes Related to Polynomial Size Omega-Decision Trees
    Proc. FCT'89, Szeged (Hungary), 1989.
  • M. Krause, Christoph Meinel, S. Waack
    Separating Complexity Classes Related to Certain Input Oblivious Logarithmic Space-Bounded Turing Machines
    Proc. 11th IFIP World Computer Congress'89, San Francisco (USA), Inf. Processing 89, G. X. Ritter (Ed.), North-Holland 1989, 287-292.
  • M. Krause, Christoph Meinel, S. Waack
    Separating Complexity Classes Related to Restricted Logarithmic Space-Bounded Turing Machines
    Proc. IEEE Structure in Complexity Theory, Eugene (USA), IEEE Computer Society Press 1989, 240-259.
  • Christoph Meinel
    Omega-Branching Programs of Bounded Width
    Proc. CSL'89, Kaiserslautern (Germany), LNCS 440, Springer-Verlag 1990, 242-253.
  • Christoph Meinel
    Switching Graphs and Their Complexity
    Proc. MFCS'89, Porabka (Poland), LNCS 379, Springer-Verlag 1989, 350-359.
  • M. Krause, Christoph Meinel, S. Waack
    Separating the Eraser Turing Machine Classes L_epsilon, NL_epsilon, co-NL_epsilon and P_epsilon
    Proc. MFCS'88, Karovy Vary (CSSR), LNCS 324, Springer-Verlag 1988, 405-413.
  • Christoph Meinel
    Omega-Branching Programs and log-space Turing Machine Complexity Classes
    Proc. Heyting'88, Varna (Bulgaria), 1988.
  • Christoph Meinel
    The Power of Polynomial Size Omega-Branching Programs
    Proc. STACS'88, Bordeaux (France), LNCS 294, Springer-Verlag 1988, 81-90.
  • Christoph Meinel
    The Power of Nondeterminism in Polynomial-Size Bounded-Width Branching Programs
    Proc. FCT'87, Kazan (Soviet Union), LNCS 278, Springer-Verlag 1987, 302-309.
  • Christoph Meinel
    p-Projection Reducibility and the Complexity Classes L (nonuniform) and NL (nonuniform)
    Proc. MFCS'86, Varna (Bulgaria), LNCS 233, Springer-Verlag 1986, 527-535.
  • Christoph Meinel
    Projection Complete Graph Problems and Branching Programs
    Proc. Gödel'86, Varna (Bulgaria), 1986.
  • Christoph Meinel
    A Functional Description of Synchronous Systems
    Proc. Parcella'84, Berlin (Germany), Mathem. Forschungen, Vol. 29, Akademie-Verlag, Berlin, 1985, 192-201.
  • Christoph Meinel
    Intelligent Environments - a Uniform Approach to a Theory of Parallel Processing
    Proc. Parcella'82, Berlin (Germany), Akademie-Verlag, Berlin, 1982.
  • Christoph Meinel
    The Importance of Plane Labyrinths
    Proc. Workshop on Algorithms and Computing Theory, Poznan (Poland), 1981, 36-39.
  • Christoph Meinel
    About the Posets [U_z , <=] and [L_z , <=] Induced by Codings of Environments
    Proc. FCT'81, Szeged (Hungary), LNCS 117, Springer-Verlag 1981, 445-452.