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 | |