dblp.uni-trier.de www.uni-trier.de

Electronic Colloquium on Computational Complexity, Volume 2, 1995

Volume 2, 1995

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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sat May 16 23:57:48 2009 by Michael Ley (ley@uni-trier.de)