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

Copyright © Mon Nov 2 21:34:16 2009 by Michael Ley (ley@uni-trier.de)