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

Electronic Colloquium on Computational Complexity, Volume 4, 1997

Volume 4, 1997

  1. Marco Cesati, Luca Trevisan:
    On the Efficiency of Polynomial Time Approximation Schemes.
    Electronic Edition (link) BibTeX
  2. Richard Beigel, Alexis Maciel:
    Upper and Lower Bounds for Some Depth-3 Circuit Classes.
    Electronic Edition (link) BibTeX
  3. Sanjeev Arora, Madhu Sudan:
    Improved low-degree testing and its applications.
    Electronic Edition (link) BibTeX
  4. Marek Karpinski, Alexander Zelikovsky:
    Approximating Dense Cases of Covering Problems.
    Electronic Edition (link) BibTeX
  5. Moni Naor, Omer Reingold:
    On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited.
    Electronic Edition (link) BibTeX
  6. Marco Cesati, Miriam Di Ianni:
    Parameterized Parallel Complexity.
    Electronic Edition (link) BibTeX
  7. Stasys Jukna:
    Exponential Lower Bounds for Semantic Resolution.
    Electronic Edition (link) BibTeX
  8. Noam Nisan, Ziv Bar-Yossef:
    Pointer Jumping Requires Concurrent Read.
    Electronic Edition (link) BibTeX
  9. Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey Shallit:
    The Computational Complexity of Some Problems of Linear Algebra.
    Electronic Edition (link) BibTeX
  10. Marcos A. Kiwi:
    Testing and Weight Distributions of Dual Codes.
    Electronic Edition (link) BibTeX
  11. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan:
    Weak Random Sources, Hitting Sets, and BPP Simulations.
    Electronic Edition (link) BibTeX
  12. Luca Trevisan:
    On Local versus Global Satisfiability.
    Electronic Edition (link) BibTeX
  13. Bernd Borchert, Dietrich Kuske, Frank Stephan:
    On Existentially First-Order Definable Languages and their Relation to NP.
    Electronic Edition (link) BibTeX
  14. Klaus Reinhardt, Eric Allender:
    Making Nondeterminism Unambiguous.
    Electronic Edition (link) BibTeX
  15. Jan Krajícek:
    Interpolation by a Game.
    Electronic Edition (link) BibTeX
  16. Manindra Agrawal, Eric Allender, Samir Datta:
    On TC0, AC0, and Arithmetic Circuits.
    Electronic Edition (link) BibTeX
  17. Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky:
    An Approximation Algorithm for the Bandwidth Problem on Dense Graphs.
    Electronic Edition (link) BibTeX
  18. Oded Goldreich, Shafi Goldwasser, Shai Halevi:
    Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.
    Electronic Edition (link) BibTeX
  19. Martin Sauerhoff:
    A Lower Bound for Randomized Read-k-Times Branching Programs.
    Electronic Edition (link) BibTeX
  20. Oded Goldreich:
    A Sample of Samplers - A Computational Perspective on Sampling (survey).
    Electronic Edition (link) BibTeX
  21. Farid M. Ablayev:
    Randomization and nondeterminsm are incomparable for ordered read-once branching programs.
    Electronic Edition (link) BibTeX
  22. Gunnar Andersson, Lars Engebretsen:
    Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat.
    Electronic Edition (link) BibTeX
  23. Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener:
    On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.
    Electronic Edition (link) BibTeX
  24. Marek Karpinski:
    Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.
    Electronic Edition (link) BibTeX
  25. Harald Hempel, Gerd Wechsung:
    The Operators min and max on the Polynomial Hierarchy.
    Electronic Edition (link) BibTeX
  26. Jochen Meßner, Jacobo Torán:
    Optimal proof systems for Propositional Logic and complete sets.
    Electronic Edition (link) BibTeX
  27. Johannes Merkle, Ralph Werchner:
    On the Security of Server aided RSA protocols.
    Electronic Edition (link) BibTeX
  28. Scott E. Decatur, Oded Goldreich, Dana Ron:
    Computational Sample Complexity.
    Electronic Edition (link) BibTeX
  29. Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger:
    On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations.
    Electronic Edition (link) BibTeX
  30. Martin Sauerhoff:
    On Nondeterminism versus Randomness for Read-Once Branching Programs.
    Electronic Edition (link) BibTeX
  31. Oded Goldreich, Shafi Goldwasser:
    On the Limits of Non-Approximability of Lattice Problems.
    Electronic Edition (link) BibTeX
  32. Jan Johannsen:
    Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes.
    Electronic Edition (link) BibTeX
  33. Meena Mahajan, Venkatesh Raman:
    Parametrizing Above Guaranteed Values: MaxSat and MaxCut.
    Electronic Edition (link) BibTeX
  34. Jui-Lin Lee:
    Counting in Uniform TC0.
    Electronic Edition (link) BibTeX
  35. Richard Chang:
    Bounded Queries, Approximations and the Boolean Hierarchy.
    Electronic Edition (link) BibTeX
  36. Meena Mahajan, V. Vinay:
    Determinant: Combinatorics, Algorithms, and Complexity.
    Electronic Edition (link) BibTeX
  37. Johan Håstad:
    Some optimal inapproximability results.
    Electronic Edition (link) BibTeX
  38. Johan Håstad:
    Clique is hard to approximate within n1-epsilon.
    Electronic Edition (link) BibTeX
  39. Pierluigi Crescenzi, Luca Trevisan:
    MAX NP-Completeness Made Easy.
    Electronic Edition (link) BibTeX
  40. Dorit Dor, Shay Halperin, Uri Zwick:
    All Pairs Almost Shortest Paths.
    Electronic Edition (link) BibTeX
  41. Marek Karpinski, Juergen Wirtgen:
    On Approximation Hardness of the Bandwidth Problem.
    Electronic Edition (link) BibTeX
  42. Russell Impagliazzo, Pavel Pudlák, Jiri Sgall:
    Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm.
    Electronic Edition (link) BibTeX
  43. Bruno Codenotti, Pavel Pudlák, Giovanni Resta:
    Some structural properties of low rank matrices related to computational complexity.
    Electronic Edition (link) BibTeX
  44. David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
    Searching constant width mazes captures the AC0 hierarchy.
    Electronic Edition (link) BibTeX
  45. Oded Goldreich, David Zuckerman:
    Another proof that BPP subseteq PH (and more). .
    Electronic Edition (link) BibTeX
  46. Alexander Barg:
    Complexity Issues in Coding Theory.
    Electronic Edition (link) BibTeX
  47. Miklós Ajtai:
    The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions.
    Electronic Edition (link) BibTeX
  48. Søren Riis, Meera Sitharam:
    Non-constant Degree Lower Bounds imply linear Degree Lower Bounds.
    Electronic Edition (link) BibTeX
  49. Wolfgang Maass, Michael Schmitt:
    On the Complexity of Learning for Spiking Neurons with Temporal Coding.
    Electronic Edition (link) BibTeX
  50. Stanislav Zák:
    A subexponential lower bound for branching programs restricted with regard to some semantic aspects.
    Electronic Edition (link) BibTeX
  51. Wolfgang Maass, Pekka Orponen:
    On the Effect of Analog Noise in Discrete-Time Analog Computations.
    Electronic Edition (link) BibTeX
  52. Wolfgang Maass, Eduardo D. Sontag:
    Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages.
    Electronic Edition (link) BibTeX
  53. Alexander E. Andreev, Juri L. Baskakov, Andrea E. F. Clementi, José D. P. Rolim:
    Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs.
    Electronic Edition (link) BibTeX
  54. Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
    Arthur-Merlin Games in Boolean Decision Trees.
    Electronic Edition (link) BibTeX
  55. Bruce E. Litow:
    A Decision Method for the Rational Sequence Problem.
    Electronic Edition (link) BibTeX
  56. Oded Goldreich:
    Combinatorial Property Testing (a survey). .
    Electronic Edition (link) BibTeX
  57. Petr Savický:
    Complexity and Probability of some Boolean Formulas.
    Electronic Edition (link) BibTeX
  58. Oded Goldreich:
    Notes on Levin's Theory of Average-Case Complexity.
    Electronic Edition (link) BibTeX
  59. Jin-yi Cai, Ajay Nerurkar:
    Approximating the SVP to within a factor (1 + 1/dimepsilon) is NP-hard under randomized reductions.
    Electronic Edition (link) BibTeX
  60. Manindra Agrawal, Thomas Thierauf:
    The Satisfiability Problem for Probabilistic Ordered Branching Programs.
    Electronic Edition (link) BibTeX
  61. Eli Biham, Dan Boneh, Omer Reingold:
    Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring.
    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)