Tech Report # | Name of Report | Author(s) | |

83-001 | A Relativized Failure of the Berman-Hartmanis conjecture. | Stuart A. Kurtz | |

84-002 | A Simple Proof of the Lucas-Lehmer Primality Test | Jeffrey Shallit | |

84-003 | An Application of the Lenstra-Lenstra-Lovasz Algorithm to the Solution of a Diophantine Equation | Jeffrey Shallit | |

84-006 | An Exposition of Pollard's Algorithm for Quadratic Congruences | Jeffrey Shallit | |

84-008 | A Class of Functions Equvalent to Factoring | Eric Bach and Jeffery Shallit | |

85-001 | Random Polynomial Time Algorithms for Sums of Squares | Jeffrey Shallit | |

85-002 | Factorization of Polynomials by Transcendental Evaluation | Marc-Paul van der Hulst and Arjen K. Lenstra | |

84-001 | The Computational Complexity of Some Group-Theoretic Problems | Joan Boyar | |

85-005 | On Machine Inductive Inference of Approximations | James S. Royer | |

85-003 | Updating Distances in Dynamic Graphs | Shimon Even and Hillel Gazit | |

85-004 | On the Complexity of Some Word Problems Which Arise in Testing the Security of Protocols | Shimon Even | |

85-006 | How to Prove Representaion-Independent Independence Results | Stuart A. Kurtz, O'Donnell, Royer | |

86-007 | On The Length of Subgroup Chains in The Symmetric Group | Laszlo Babai | |

85-008 | A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem | Noga Alon. Laszlo Babai, and Alon Itai | |

85-009 | Computing Ears and Branchings in Parallel | Laszlo Babai | |

85-010 | A More Efficient Algorithm For Lattice Basis Reduction | C.P. Schnorr | |

85-011 | A Las-Vegas-Nc Algorithm for Finding Pointwise Set-Stabilizers in Permutation Groups With Restricted Composition Factors | Laszlo Babai | |

85-012 | Continuous Routing and Batch Routing on the Hypercube | Yukon Chang and Janos Simon | |

86-001 | Random oracles separate PSPACE from the polynomial time hierarchy | Laszlo Babai | |

86-002 | Inferring Sequences Produced by Pseudo-Random Number Generations | Joan Boyar | |

86-004 | Coloring Planar Graphs in Parallel | Joan Boyar and Howard Karloff | |

86-005 | An NC Algorithm for Brooks' Theorem | Howard J. Karloff | |

86-006 | Collapsing Degrees | Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer | |

86-007 | Progressions of Relatively Succinct Programs in Subrecursive Hierarchies | James S. Royer and John Case | |

86-10 | The Iterated Mod Problem | Howard J. Karloff and Walter L. Ruzzo | |

87-001 | Noncollapsing Degrees | Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer | |

87-002 | A Discrete Logarithm Implementaion of Zero-Knowledge Blobs | Joan F. Boyar, Mark W. Krentel, Stuart A. Kurtz | |

87-003 | Term-Rewriting Implementation of Equtional Logic Programming | Michael J. O'Donnell | |

87-004 | Survey of the Equational Logic Programming Project | Michael J. O'Donnell | |

87-005 | Lower bounds for the size of circuits of bounded depth in basis | Mark Alan Epstein | |

87-006 | A Generalization of Automatic Sequences | Jeffery Shallit | |

87-007 | Fast and rigorous factorization under the generalized Riemann hypothesis | Arjen K. Lenstra | |

87-008 | Algorithms in number theory | A.K.Lenstra and H.W. Lenstra, Jr. | |

87-009 | An Algol-68 Interpreter | Laszlo Csirmaz | |

87-10 | Two Methods for the Generation of Fractal Images | Jeffrey Shallit | |

87-011 | Chromatic Numbers of Random Hypergraphs and Associated Graphs | Eli Shamir | |

87-012 | On Connectionist Models | Jiawei Hong | |

87-013 | Providing Inequalities by Examples | Jiawei Hong | |

87-014 | Arthur-Merlin Games: A Randomized Proof System, and A Hierarchy of Complexity Classes | Laszlo Babai, Shlomo Moran | |

87-015 | A Characterization of Proof Speed-up | James S. Royer | |

87-016 | A Subset Coloring Algorithm and Its Applications to Computer Graphics | David Rubinstein, Jeffrey Shallit, and Mario Szegedy | |

87-017 | Infinite Products Associated with Counting Blocks in Binary Strings | J.P. Allouche and J. Shallit | |

87-018 | Analysis of an Infinite Product Algorithm | J.P. Allouche, J. Shallit, P. Hajnal | |

87-019 | Geometry of Numbers and Integer Programming (Summary) | C. P. Schnorr | |

87-020 | How Long Can a Euclidean Traveling Salesman Tour Be? | Howard J. Karloff | |

87-022 | Universal Traversal Sequences of Length n^O(log n) for Cliques | howard J. Karloff, Ramamohan Paturi, Janos Simon | |

88-001 | A Note on the Relative Complexity of Ok(N) and d(N) | Jeffrey Shallit | |

88-002 | The Rate of Convergence of the Modified Method of Characteristics for Linear Advection Equations in Once Dimension | Clint Dawson,Todd Dupont, Mary Wheeler | |

88-003 | |||

88-004 | An Lower bound on the Randomized Complexity of Graph Properties | Peter Hajnal | |

88-005 | An Algebraic Model for Bounding Threshold Circuit Depth | Joan Boyar,Gudmund Frandsen, Carl Sturtivant | |

88-006 | Remarks on Some Dynamical Problems of Controlling Redundant Manipulators | T. Shamir | |

88-007 | A Fast Planar Partition Algorithm Part I | Ketan Mulmuley | |

88-008 | Interactive proofs in finite groups | Laszlo Babai | |

88-009 | On Singularities of redundant robot arms | T. Shamir | |

88-013 | On the Enumeration Technique | Stuart A. Kurtz, Carl H. Smith | |

88-014 | Automatic, Transparent Parallelization of Logic Prograqms at Complie Time | Will Winsborough | |

88-15 | Source-Level Transforms for multiple Specialization of Horn Clauses (extended Abstract) | Will Winsborough | |

88-16 | Compact incremental Gaussian elimination over ZZ/2ZZ | A.K. Lenstra and M.S. Manasse | |

88-17 | Complexity Corresponds to Topology | Juris Hartmanis, Lane Hemachandra, Stuart A. Kurtz | |

88-18 | The Isomorphism Conjecture Fails Relative to a Generic Oracle | Stuart A. Kurtz | |

88-19 | Complexity of graph problems | Peter Hajnal | |

88-20 | |||

88-21 | On Levels in Arrangements and Voronoi diagrams | Ketan Mulmuley | |

88-22 | Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies | Joan Boyar, Katalin Friedl, Carsten Lund | |

89-01 | Some Problems and Results in the Theory of Actual Computable Functions (preliminary abstract) | Wolfgang Maass and Theodore A. Slaman | |

89-02 | On the Concrete Complexity of Zero-Knowledge Proofs | Joan Boyar, Rene Peralta | |

89-03 | Testing Confluence of Nonterminating, Overlapping Systems of Rewrite Rules | Yiyun Chen, Michael J. O'Donnell | |

89-04 | Linearity and Unprovability of Set Union Problem Strategies: I. Linearity of On Line Postorder | Martin Loebl and Jaroslav Nesetril | |

89-05 | Categorical Grammars Determined from Linguistic Data by Unification | Wojciech Buszkowski and Gerald Penn | |

89-06 | Smooth Particle Methods on Bounded Domains | Barry Merriman | |

89-07 | A Complexity Theoretic Failure of the Cantor-Bernstein Theorem | Stephen A. Fenner | |

89-09 | A Finite Difference Domain Decomposition Algorithm for Numerical Solution of the Heat Equation | Clint Dawson, Qiang Du, Todd F. Dupont | |

89-10 | Computing Irreducible Representations of Finite Groups | Laszlo Babai, Lajos Ronyai | |

90-01 | Perpetuities Reasoning captured and Automated: Gray's Mathematics Expressed in a Logic Program | Barnett W. Glickfeld | |

90-02 | A Characterization of P by Straight Line Programs of Polynomials, with Applications to Interactive Proofs and Toda's Theorem | Laszlo Babai, Lance Fortnow | |

90-03 | Non-Deterministic Exponential Time had Two-Prover Interactive Protocols | Laszlo Babai, Lance Fortnow, Carsten Lund | |

90-04 | Efficient, Perfect Polynomial Random Number Generators | S. Micali, Claus P. Schnorr | |

90-05 | Developing an Interactive Interface for Equational Logic Programs | Samuel A. Rebelsky, David J. Sherman | |

90-06 | A Priori estimates for mixed finite element methods for the wave equation | Lawrence Cowsar, Todd Dupont, Mary Wheeler | |

90-07 | Testing Confluence of Nonterminating Rewriting Systems | Yiyun Chen, Michael J. O'Donnell | |

90-08 | Infinite Terms and Infinite Rewritings | Yiyun Chen, Michael J. O'Donnell | |

90-09 | The Average Sensitivity of Functions in AC^0 | Carsten Lund | |

90-10 | Vertex-Transitive Graphs and Vertex-Transitive Maps | Laszlo Babai | |

90-11 | Interactive Proof Systems and Alternating Time-Space Complexity | Lance Fortnow, Carsten Lund | |

90-12 | An Abstract Machine for Efficient Implementation of Term Rewriting | David J. Sherman, Robert I. Strandh | |

90-13 | Preliminary Noted on Version 4.1 of the Equational Compiler | Linda Sellie and David J. Sherman | |

90-14 | BPP has Weak Subexponential Time Simulations unless EXPTIME has punishable Proofs | Laszlo Babai, Lance Fortnow, Noam Nisan, Avi Wigderson | |

90-15 | E-mail and the Unexpected Power of Interaction | Laszlo Babai | |

90-16 | Algebraic Methods for Interactive Proof Systems | CarstenLund, Lance Fortnow, Howard Karloff, Noam Nisan | |

90-17 | Maximum Diameter of Regulr Diagraphs | Jose A. R. Soares | |

90-18 | # P-completeness via Many-one reductions | Viktoria Zanko | |

90-19 | Sharing Common Subexpressions in EM code Programs | David J. Sherman | |

90-20 | An error estimate for a new scheme for the general variable coefficient linearized thermal pipeline equations | Philip T. Keenan | |

90-22 | On the Random-Self-Reducibility of Complete Sets | Joan Feigenbaum, Lance Fortnow | |

90-23 | On levels in arrandements and Voronoi diagrams, II: output sensitive and dynamic constructions | Ketan Mulmuley | |

90-24 | A Generalization of Dehn-Sommerville Relations to Simple Stratified Spaces | Ketan Mulmuley | |

90-25 | View Dependent Partitions | Ketan Mulmuley | |

90-26 | Proving Unorientable Equational Formulas | Yiyun Chen, Michael J. O'Donnell | |

90-27 | Nonterminating Rewritings with Head Boudedness | Yiyun Chen, Michael J. O'Donnell | |

90-28 | Lazy Directed Congruence Closure | David J. Sherman | |

90-29 | Partial Evaluation of Intermediate Code from Equational Programs | David J. Sherman and Robert I. Strandh | |

90-30 | PP is closed under truth-table reductions | Lance Fortnow and Nick Reingold | |

90-31 | An Efficient Algorithm For Hidden Surface Removal, II | Ketan Mulmuley | |

90-31B | Local expansion of Vertex-transitive graphs and random generation in finite groups | Laszlo Babai | |

90-32 | Gap-definable counting classes | Steve Fenner, Lance Fortnow, Stuart Kurtz | |

90-33 | Constructing Reliable Communication Networks of Small Weight Online | Barun Chandra, Sundar Vishwanathan | |

90-34 | Notions of resouce-bounded category and genericity | Stephen A. Fenner | |

91-01 | The Power of Interaction | Carsten Lund | |

91-02 | Computational Complexity in Finite Groups | Laszlo Babai | |

91-03 | Vertex-Transitive Graphs and Vertex-Transitive Maps | Laszlo Babai | |

91-04 | Tight lower bounds on genericity required to prevent one-way functions | Stephen A. Fenner | |

91-05 | Fast Mone Carlo Algorithms for Permutation Groups | Laszlo Babai, Gene Cooperman, Larry Finkelstein, Eugene Luks, and Akos Seress | |

91-06 | Checking Computations in Polylogarithmic Time | Laszlo Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy | |

91-07 | A Simple online algorithm for constructing Voronoi diagrams | Ketan Mulmuley | |

91-08 | Checking Computations in Polylogarithmic Time | Laszlo Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy | |

91-09 | Arithmetization: A New Method in Structural Complexity Theory | Laszlo Babai, Lance Fortnow | |

91-10 | Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols | Laszlo Babai, Lance Fortnow, Carsten Lund | |

91-11 | The edge-orbit Conjecture of Babai | Albert J. Goodman | |

91-12 | Subdirect Reducible Groups and Edge-Minimal Graphs with Given Automorphism Group | Laszlo Babai and Albert J. Goodman | |

91-13 | Lower bounds for the complexity of reliable Boolean circuits with noisy gates | Anna Gal | |

91-14 | Graphs with Given Automorphism Group and few Edge Orbits | Laszlo Babai, Albert J. Goodman, and Laszlo Lovasz | |

91-15 | Bounded round interactive proofs in finite groups | Laszlo Babai | |

91-16 | Nearly Linear Time Algorithms for Permutation Groups with a Small Base | Laszlo Babai, Gene Cooperman, Larry Finkelstein, and Akos Seress | |

91-17 | Symmetry and Complexity | Laszlo Babai, Robert Beals, and Pal Takacsi-Nagy | |

91-18 | Chains, Gaps, and Finite Extensions: Three Topics in Structural Complexity | Stephen A. Fenner | |

91-19 | Thermal Simulation of Pipeline Flow | Philip T. Keenan | |

91-20 | Approximate Representation Theory of Finite Groups | Laszlo Babai and Katalin Friedl | |

91-21 | Permutation groups without exponentially many orbita on the power set | Laszlo Babai and Laszlo Pyber | |

91-021 | The Internals of the Equational Programming System Version 3.1 | Robert Strandh | |

91-22 | Local expansion of symmetrical graphs | Laszlo Babai and Mario Szegedy | |

91-23 | On the diameter of permutation groups | Laszlo Babai and Akos Seress | |

91-24 | On Faithful Permutation Representations of Small Degree | Laszlo Babai and Albert J. Goodman | |

91-25 | Algebraic Aspects of Complexity Functions | Lide Li | |

91-26 | Does Randomization Help in On-Line Packing | Barun Chandra | |

91-27 | Promising Directions in Active Vision | Active Vision workshop Employees | |

91-28 | An Introduction to tours A Protocol for Demand-Driven Communication of Terms | Samuel A. Rebelsky | |

91-29 | An Approximation Algorithm for the Asymmetric Travelling Salesman Problem with Distances One and Two | Sundar Vishwanathan | |

91-30 | Gap-Definable Counting Classes | Steve Fenner, Lance Fortnow, Stuart Kurtz | |

92-01 | Connecting Formal Semantics to Constructive Intuitions | Stuart A. Kurtz, John C. Mitchell and Michael J. O'Donnell | |

92-02 | On the diameter of random Cayley graphs of the symmetric group | L. Babai and G. L. Hetyei | |

92-03 | I/O Trees I/O Support for Equational Logic Programming | Samuel A. Rebelsky | |

92-04 | A New Lower Bound Theorem for Read Only Once Branching Programs and Its Applications | Janos Simon and Mario Szegedy | |

92-05 | Approximating Euclidean Distances by Small Degree Graphs | Jose Soares | |

92-06 | Observing Self-Stabilization | Chengdian Lin and Janos Simon | |

92-07 | Electronic Journals scholarly invariants in a changing medium | M. J. O'Donnell | |

92-08 | An Oracle Relative to which the Isomorphism Conjecture Holds | Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz | |

92-09 | New Sparseness Results on Graph Spanners | Barun Chandra, Gautam Das, Giri Narasimhan, Jose Soares | |

92-10 | On the Abstract Group of Automorphisms | Laszlo Babai and Albert J. Goodman | |

92-11 | Short Presentations for Finite Groups | L. Babai, A.J. Goodman, W.M. Kantor, E.M. Luks, P.P. Palfy | |

92-12 | Graph Spanners: a Survey | Jose Soares | |

92-13 | Gap-Definability as a Closure Property | Stephen Fenner, Lance Fortnow, Lide Li | |

92-14 | Graph Spanners | Jose Soares | |

92-15 | Noniterative Domain Decomposition for Second Order Hyperbolic Problems | Clint N. Dawsom and Todd F. Dupont | |

92-16 | Computing the Composition Factors of Primitive Groups | Laszlo Babai, Eugene M. Luks, Akos Seress | |

92-17 | Deciding finiteness of matrix groups in deterministic polynomial time | Laszlo Babai, Robert Beals, and Daniel Rockmore | |

92-18 | Several Procedures for Operator-Based Averaging for Elliptic Equations | Clint N. Dawson and Todd F. Dupont | |

92-19 | How Required Compression Depends on the Thermodynamics of Rich Gas Flow | Todd F Dupont and Henry H. Rachford, Jr. | |

92-20 | Drop Formation in a One-Dimensional Approximation of the Navier-Stokes Equation | Jens Eggers and Todd F. Dupont | |

92-21 | Reducing the Rank of Lower Triangular All-Ones Matrices | Peter Kimmel and Amber Settle | |

92-22 | Color and Geometry as Cues for Indexing | Markus A. Stricker | |

92-23 | Tree Pattern Matching for Strongly Sequential Systems | Jiefei Hong | |

92-24 | Inline Algorithms for Graph Problems | Sundar Vishwanathan | |

92-25 | Oracles, Proofs and Checking | Lance Fortnow | |

92-26 | An Oracle Builder's Toolkit | Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li | |

92-27 | A Simple Proof of Representing OR Function as a Polynomial Modulo Prime Numbers | Shi-Chun Tsai | |

92-28 | Lower Bounds on Representing Boolean Functions as Polynomials in Zn | Shi-Chun Tsai | |

93-01 | Transparent (holographic( Proofs | Laszlo Babai | |

93-02 | Low degree test | Katalin Friendl and Zsolt Hatsagi | |

93-03 | On PP-Low Classes | Lide Li | |

93-04 | Efficient Algorithms for Token Management for One-bit Delay Rings with Priorities | Lide Li and Janos Simon | |

93-05 | Constructing Sparse Spanners for Most Graphs in Higher Dimensions | Barun Chandra | |

93-06 | Tours, A System for Lazy Term-Based Communication | Samuel A. Rebelsky | |

93-07 | Direct Memory Access Parsing | Charles Eugene Martin | |

93-08 | A Generic Separation | Lance Fortnow | |

93-09 | A Note on Step Satisfied Boolean Formulas | Peter Kimmel | |

93-10 | Algorithms for Finite Groups | Robert M. Beals | |

93-11 | Electronic Journals scholarly invariants iin a changing medium | M. J. O'Donnell | |

93-12 | On the Counting Functions | Lide Li | |

93-13 | On Slightly superlinear transparent proofs | Laszlo Babai and Katalin Friedl | |

93-14 | Seperability and One-Way Functions | Lance Fortnow and John Rpgers | |

93-15 | Transparent Proofs and Limits to Approximation | Laszlo Babai | |

93-16 | Optimality and Domination in Repeated Games with bounded Players | Lance Fortnow and Duke Whang | |

93-17 | Fault tolerant circuits and probabilistically checkable proofs | Anna Gal and Mario Szegedy | |

93-18 | t-Particle Random Walks and Recycle Random Bits in Parallel (extended Abstract) | Katalin Friedl and Shi-Chun Tsai | |

94-01 | A Note on Self-Correction vs. Random-Self-Reducibility (Preliminary Version) | Joan Feigenbaum, Lance Fortnow | |

94-02 | Relativity Recursive Reals and Real Functions | Chun-Kuen Ho | |

94-03 | A Kolomogorov Complexity proof of Hastad's switching lemma | Sophie Lapante | |

94-04 | Simultaneous Messages vs. Communication | Laszlo Babai and Peter Kimmel | |

94-05 | The Capacity and the Sensitivity of Color Histogram Indexing | Markus Stricker and Michael Swain | |

94-06 | Beyond Recursive Real Functions | Chun-Kuen Ho | |

94-08 | Transparent Proofs and Limits to Approximtion | Laszlo Babai | |

94-08 | Two results on the Bit Extraction Problem (extended Abstract) | Shi-Chun Tsai and Katalin Friedl | |

94-09 | Resource-Bounded Instance Complexity | Lance Fortnow and Martin Kummer | |

94-10 | Automorphism groups, isomorphism, reconstruction | Laszlo Babai | |

94-11 | Decomposition of Matrix Groups and Algebras | Katalin Friedl | |

94-12 | Semi-unbounded fan-in circuits: Boolean vs. arithmetic | Anna Gal | |

94-13 | Run-Time and Compile-Time Improvements to Equational Programs | David J. Sherman | |

94-14 | Beyond P^NP=NEXP | Stephen Fenner and Lance Fortnow | |

94-15 | Introduction: Logic and Logic Programming Languages | Michael J. O'Donnell | |

94-16 | Equational Logic Programming | Michael J. O'Donnell | |

94-17 | Intuitive Counterexamples for Constructive Fallacies | James Lipton and Michael J. O'Donnell | |

94-18 | Fault tolerant circuits and probabilistically checkable proofs | Anna Gal and Mario Szegedy | |

94-19 | A Note on adaptiveness and advice in coherence | Lance Fortnow and Sophie Laplante | |

94-20 | The Isomorphism Conjecture Holds and One-way Functions Exist Relative to an Oracle | John Rogers | |

94-21 | Beating A Finite Automaton in the Big Match | Lance Fortnow and Peter Kimmel | |

94-22 | Simultaneous Messages vs. Communication | Laszlo Babai, Peter G. Kimmel, Satyanarayana V. Lokam | |

94-23 | Multiplicative equations over commuting matrices | Laszlo Babai, Robert Beals, Jin-yi Cai, Gabor Ivanyos, Eugene Luks | |

94-24 | Approximation and Online Algorithms for Graph Problems | Barun Chandra | |

94-25 | Convergence in Recursive Analysis | Chun-Kuen Ho | |

95-01 | Measure, Category, and Learning Theory | Lance Fortnow, Rusins Freivalds, William Gasarch, Martin Kummer, Stuart Kurtz, Carl Smith, Frank Stephan | |

95-09 | A Simple function that requires exponential size read-once branching programs | Anna Gal | |