Volume 2, 1995

• 
  Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs.
• 
  Detlef Sieling: New Lower Bounds and Hierarchy Results for Restricted Branching Programs.
• 
  Marek Karpinski, Alexander Zelikovsky: 1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems.
• 
  Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk: Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs.
• 
  Maciej Liskiewicz, Rüdiger Reischuk: The Sublogarithmic Alternating Space World.
• 
  Kenneth W. Regan, D. Sivakumar, Jin-yi Cai: Pseudorandom Generators, Measure Theory, and Natural Proofs.
• 
  Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, Walter Kern: The Nucleon of Cooperative Games and an Algorithm for Matching Games.
• 
  Nader H. Bshouty: Exact Learning Boolean Functions via the Monotone Theory.
• 
  Matthias Krause: A Note on Realizing Iterated Multiplication by Small Depth Threshold Circuits.
• 
  Pavel Pudlák, Jiri Sgall: An Upper Bound for a Communication Game Related to Time-Space Tradeoffs.
• 
  Roman Bacik, Sanjeev Mahajan: Semidefinite Programming and its Applications to NP Problems.
• 
  Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, Walter Kern: On the Complexity of Testing Membership in the Core of min-Cost Spanning Tree Games.
• 
  Oleg Verbitsky: The Parallel Repetition Conjecture for Trees is True.
• 
  Ulrich Faigle, Walter Kern, M. Streng: Note On the Computational Complexity of j-Radii of Polytopes in Rⁿ.
• 
  Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon: Oracles and Queries That Are Sufficient for Exact Learning.
• 
  Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, Walter Kern: On Approximately Fair Cost Allocation in Euclidean TSP Games.
• 
  Claudia Bertram-Kretzberg, Thomas Hofmeister: Multiple Product Modulo Arbitrary Numbers.
• 
  Jay Belanger, Jie Wang: Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions.
• 
  Jin-yi Cai, Alan L. Selman: Average Time Complexity Classes.
• 
  William Hurwood: Dynamic Fault Diagnosis.
• 
  Marek Karpinski, Rutger Verbeek: On Randomized Versus Deterministic Computation.
• 
  Marek Karpinski, Wojciech Rytter, Ayumi Shinohara: Pattern-Matching for Strings with Short Descriptions.
• 
  Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability.
• 
  Mihir Bellare, Oded Goldreich, Madhu Sudan: Free Bits, PCP and Non-Approximability - Towards Tight Results.
• 
  Günter Hotz, Gero Vierke, Björn Schieffer: Analytic Machines.
• 
  Claus-Peter Schnorr, Horst Helmut Hörner: Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction.
• 
  Frederic Green: Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate.
• 
  Eric Allender, Martin Strauss: Measure on P: Robustness of the Notion.
• 
  Oded Goldreich, Leonid A. Levin, Noam Nisan: On Constructing 1-1 One-Way Functions.
• 
  Marek Karpinski, Alexander Zelikovsky: New Approximation Algorithms for the Steiner Tree Problems.
• 
  Dorit Dor, Uri Zwick: Selecting the Median.
• 
  Nader H. Bshouty, Christino Tamon: On the Fourier spectrum of Monotone Functions.
• 
  Richard Beigel, David Eppstein: 3-Coloring in time O(1.3446ⁿ): A no-MIS Algorithm.
• 
  Christoph Meinel, Stephan Waack: Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems.
• 
  Richard Beigel: Closure Properties of GapP and #P.
• 
  Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries.
• 
  Richard Beigel, Howard Straubing: The Power of Local Self-Reductions.
• 
  Joe Kilian, Erez Petrank: An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions.
• 
  Tomoyuki Yamakami: Polynomial Time Samplable Distributions.
• 
  Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games on Graphs.
• 
  Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim: Optimal Bounds for the Approximation of Boolean Functions and Some Applications.
• 
  Beate Bollig, Ingo Wegener: Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams.
• 
  Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay: Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds.
• 
  Carsten Damm, Stasys Jukna, Jiri Sgall: Some Bounds on Multiparty Communication Complexity of Pointer Jumping.
• 
  Moni Naor, Omer Reingold: Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions.
• 
  Vince Grolmusz: On the Power of Circuits with Gates of Low L₁ Norms.
• 
  Martin Löbbing, Ingo Wegener: The Number of Knight's Tours Equals 33,439,123,484,294 - Counting with Binary Decision Diagrams.
• 
  Helmut Veith: Succinct Representation and Leaf Languages.
• 
  Anna Gál, Avi Wigderson: Boolean Complexity Classes vs. Their Arithmetic Analogs.
• 
  Oded Goldreich, Noam Nisan, Avi Wigderson: On Yao's XOR-Lemma.
• 
  Pascal Koiran: VC Dimension in Circuit Complexity.
• 
  Douglas R. Stinson: On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes.
• 
  Petr Slavík: Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems.
• 
  Farid M. Ablayev, Marek Karpinski: On the Power of Randomized Branching Programs.
• 
  Marek Karpinski, Angus Macintyre: VC Dimension of Sigmoidal and General Pfaffian Networks.
• 
  Oded Goldreich: Three XOR-Lemmas - An Exposition.
• 
  Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX.
• 
  Amnon Ta-Shma: On Extracting Randomness From Weak Random Sources.
• 
  Nader H. Bshouty: The Monotone Theory for the PAC-Model.
• 
  Nader H. Bshouty: A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries.
• 
  Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim: Hitting Sets Derandomize BPP.
• 
  Amir M. Ben-Amram, Zvi Galil: On Data Structure Tradeoffs and an Application to Union-Find.
• 
  Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees.

last updated on Sat May 18 06:05:28 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page