DIMACS Technical Reports Published in 1997
Obtaining Reports
Most technical reports are available on-line and we encourage
down-loading from WWW browsers or FTP.
Reports that are not available
may be ordered by email to
tech@dimacs.rutgers.edu.
Be sure to include the numbers of the reports needed and your full
Postal Address.
Problems with Technical Reports?
We try to check on the accessibility of technical reports regularly, but
mistakes do happen. If you have trouble obtaining reports, please send email to
tech@dimacs.rutgers.edu identifying the
report you had trouble with. We will try to assist you in obtaining the report.
- 97-01
(abstract):
Improved Algorithms via Approximations of Probability
Distributions by Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan.
- 97-02
(abstract):
Demand Routing and Slotting on Ring Networks
by Tamra Carpenter, Steven Cosares, and Iraj Saniee.
- 97-03
(abstract):
Trees and Ehrenfeucht-Fraisse games
by Stevo Todorcevic; and Jouko Vaananen.
- 97-04
(abstract):
On a Global Optimization Problem in the Study of Information Discrepancy
by Weiwu Fang.
- 97-05
(abstract):
On linear ordering finitely-branching graphs and non-well-founded sets
by Alexei Lisitsa and Vladimir Sazonov.
- 97-06
(abstract):
Erdos and Renyi Conjecture
by Saharon Shelah.
- 97-07
(abstract):
On geometric graphs with no k pairwise parallel edges
by Pavel Valtr.
- 97-08
(abstract):
Shock Profiles for the Partially
Asymmetric Simple Exclusion Process
by B. Derrida, J. L. Lebowitz and E. R. Speer.
- 97-09
(abstract):
Phase Transitions in the Multicomponent Widom--Rowlinson Model
and in Hard Cubes on the BCC--Lattice
by P. Nielaba and J.L. Lebowitz.
- 97-10
(abstract):
Optimal Byzantine Quorum Systems
by Dahlia Malkhi, Michael Reiter and Avishai Wool.
- 97-11
(abstract):
On the density of subgraphs in a graph
with bounded independence number
by Pavel Valtr.
- 97-12
(abstract):
Threshold of Broadcast in Random Graphs
by Hui Chen.
- 97-13
(abstract):
Ramsey-Type Results for Geometric Graphs. II
by Gyula Karolyi, Janos Pach, Geza Toth, Pavel Valtr.
- 97-14
(abstract):
Computing Integral Points in Convex Semi-algebraic Sets
by Leonid Khachiyan and Lorant Porkolab.
- 97-15
(abstract):
Crowds: Anonymity for Web Transactions (revised)
by Michael K. Reiter and Aviel D. Rubin.
- 97-16
(abstract):
Optimization algorithms for
separable functions with tree-like adjacency of variables and their
application to the analysis of massive data sets
by Ilya Muchnik and Vadim Mottl.
- 97-17
(abstract):
Constructing big trees from short sequences
by Peter L. Erdos, Michael A. Steel, Laszlo A. Szekely and Tandy J. Warnow.
- 97-18
(abstract):
On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees
[Revised Version]
by Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li and John Tromp.
- 97-19
(abstract):
Asymptotics of the total chromatic number for multigraphs
by P. Mark Kayll.
- 97-20
(abstract):
Choiceless polynomial time
by Andreas Blass, Yuri Gurevich and Saharon Shelah.
- 97-21
(abstract):
Bounded Hyperset Theory and Web-like Data Bases
by Alexei Lisitsa and Vladimir Sazonov.
- 97-22
(abstract):
Graph drawings with no k pairwise crossing edges
by Pavel Valtr.
- 97-23
(abstract):
Extension of Piyavskii's Algorithm to
Continuous Global Optimization
by Robert J. Vanderbei.
- 97-24
(abstract):
Symmetrization of Binary Random Variables
by Abram Kagan, Colin Mallows, Larry Shepp, Robert J. Vanderbei and
Yehuda Vardi.
- 97-25
(abstract):
Linear Hashing
by Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen,
Erez Petrank and Gábor Tardos.
- 97-26
(abstract):
CBC MAC for Real-Time Data Sources
by Erez Petrank and Charles Rackoff.
- 97-27
(abstract):
Probabilistically Checkable Proofs with Zero Knowledge
by Joe Kilian, Erez Petrank and Gábor Tardos.
- 97-28
(abstract):
Identity Escrow
by Joe Kilian and Erez Petrank.
- 97-29
(abstract):
The chromatic numbers of random hypergraphs
by Michael Krivelevich and Benny Sudakov.
- 97-30
(abstract):
Shock Profiles for the Asymmetric Simple Exclusion Process
in One Dimension
by B. Derrida, J. L. Lebowitz and E. R. Speer.
- 97-31
(abstract):
Note on the Erdos-Szekeres theorem
by Geza Toth and Pavel Valtr.
- 97-32
(abstract):
Learning Boxes in High Dimension
by Amos Beimel and Eyal Kushilevitz.
- 97-33
(abstract):
On Local Register Allocation
by Martin Farach and Vincenzo Liberatore.
- 97-34
(abstract):
Horn Minimization by Iterative Decomposition
by Endre Boros, Ondrej Cepek and Alexander Kogan.
- 97-35
(abstract):
On the Limit Values of Probabilities for the First Order Properties of
Graphs
by Joel Spencer and Lubos Thoma.
- 97-36
(abstract):
FDOD Function and the Information Discrepancy Contained
in Multiple Probability Distributions
(Revised version)
by Weiwu Fang.
- 97-37
(abstract):
Affine Scaling Algorithms Fail for Semidefinite Programming
by Masakazu Muramatsu and Robert J. Vanderbei.
- 97-38
(abstract):
A Practical Algorithm for Finding Matrix Representations for Polycyclic
Groups
by Eddie H. Lo and Gretchen Ostheimer.
- 97-39
(abstract):
Chromatic-Index Critical Graphs of Even Order
by Stefan Grünewald and Eckhard Steffen.
- 97-40
(abstract):
The Complexity of Matrix Rank and Feasible
Systems of Linear Equations
by Eric Allender, Robert Beals, and Mitsunori Ogihara.
- 97-41
(abstract):
Reliable Communication over Partially Authenticated Networks
by Amos Beimel and Matthew Franklin.
- 97-42
(workshop program):
Proceedings of Third DIMACS Workshop on DNA Based Computers
(On line version not available, please order from AMS).
(published as
AMS-DIMACS Volume 48)
- 97-43
(workshop program):
Proceedings of DIMACS Workshop on Design and Formal
Verification of Security Protocols
(please order for CD-ROM version of the proceedings).
- 97-44
(abstract):
Practical Algorithms for Polycyclic Matrix Groups
by Gretchen Ostheimer.
- 97-45
(abstract):
Some Pointed Questions Concerning Asymptotic Lower Bounds
by Eric Allender.
- 97-46
(abstract):
Making Nondeterminism Unambiguous
by Klaus Reinhardt and Eric Allender.
- 97-47
(abstract):
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems
by Martin Mundhenk, Judy Goldsmith, Christopher Lusena and Eric Allender.
- 97-48
(abstract):
On TC^0, AC^0, and Arithmetic Circuits
by Manindra Agrawal, Eric Allender and Samir Datta.
- 97-49
(abstract):
Circuit Complexity before the Dawn of the New Millennium
by Eric Allender.
- 97-50
(abstract):
RUSPACE(log n) is contained in DSPACE(log^2 n / loglog n)
by Eric Allender and Klaus-Joern Lange.
- 97-51
(abstract):
The Permanent Requires Large Uniform Threshold Circuits
by Eric Allender.
- 97-52
(abstract):
Pairing Heaps Are Suboptimal
by Michael L. Fredman.
- 97-53
(abstract):
Rectangle Breaking in Grids
by Paul A. Dreyer, Jr. and Therese C. Biedl.
- 97-54
(abstract):
Special Year on Logic and Algorithms Tutorial Notes:
Expressive Powers of Logics
(Tutorial Lectures by Phokion Kolaitis)
by Phokion Kolaitis.
- 97-55
(abstract):
Special Year on Logic and Algorithms Tutorial Notes:
Descriptive Complexity
(Tutorial Lectures by Neil Immerman)
by Neil Immerman.
- 97-56
(abstract):
Special Year on Logic and Algorithms Tutorial Notes:
Random Finite Models
(Tutorial Lectures by James Lynch)
by James Lynch.
- 97-57
(abstract):
Special Year on Logic and Algorithms Tutorial Notes:
Complexity Issues in Automata-Theoretic Verification:
The COSPAN Approach to Deal with These Issues
(Tutorial Lectures by Robert Kurshan)
by Robert Kurshan and Sandeep Shukla.
- 97-58
(abstract):
On Minimally Imperfect Graphs with Circular Symmetry
by Gábor Bacsó, Endre Boros, Vladimir Gurvich,
Frédéric Maffray and Myriam Preissmann.
- 97-59
(abstract):
Chromatic Index Critical Graphs of Orders 11 and 12
by Gunnar Brinkmann and Eckhard Steffen.
- 97-60
(abstract):
Reductions in Circuit Complexity: An Isomorphism Theorem and a
Gap Theorem
by Manindra Agrawal, Eric Allender, and Steven Rudich.
- 97-61
(abstract):
Arithmetic Complexity, Kleene Closure, and Formal Power Series
by Eric Allender, V Arvind, and Meena Mahajan.
- 97-62
(abstract):
Graph Homomorphisms and Phase Transitions
by Graham R. Brightwell and Peter Winkler.
- 97-63
(abstract):
A Short Course in Computational Molecular Biology
by D. Durand, M. Farach, R. Ravi and M. Singh.
- 97-64
(abstract):
The Design and Implementation of a Java Playground
by Dahlia Malkhi, Michael Reiter and Avi Rubin.
- 97-65
(abstract):
Longest Common Consecutive Substring in Two Random Strings
by Sarmad Abbasi.
- 97-66
(abstract):
A Generalization of the Erdos-Szekeres
Theorem to Disjoint Convex Sets
by János Pach and Géza Tóth.
- 97-67
(abstract):
Linear Programming in Tomography, Probability, and Finance
by Larry Shepp.
- 97-68
(abstract):
A Modest Proposal for Preventing Internet Congestion
by Andrew Odlyzko.
- 97-69
(abstract):
Uniform Multipaging Reduces to Paging
by Vincenzo Liberatore.
- 97-70
(abstract):
The Maximum of a Random Walk and Its Application
to Rectangle Packing
by E. G. Coffman, Jr., Philippe Flajolet, Leopold Flatto and
Micha Hofri.
- 97-71
(abstract):
A few logs suffice to build (almost) all trees (I)
by P. L. Erdos, M. A. Steel, L. A. Szekely, and T. J. Warnow.
- 97-72
(abstract):
A few logs suffice to build (almost) all trees (II)
by P. L. Erdos, M. A. Steel, L. A. Szekely, and T. J. Warnow.
- 97-73
(abstract):
Three-dimensional Grid Drawings of Graphs
by János Pach, Torsten Thiele and Géza Tóth.
- 97-74
(abstract):
Upper semi-lattice of binary strings with the relation
``x is simple conditional to y''
by Andrei Muchnik, Andrei Romashchenko, Alexander Shen and
Nikolai Vereshagin.
- 97-75
(abstract):
On Automorphism Groups of Graphs and Distributive Lattices
by Stephan Foldes.
- 97-76
(abstract):
Cyclically 5-edge Connected Con-bicritical Critical Snarks
by Stefan Gruenewald and Eckhard Steffen.
- 97-77
(abstract):
Some Results Concerning the Ends of Minimal Cuts of Simple Graphs
by Ning Jia and Xiaofeng Jia.
- 97-78
(abstract):
Remarks on the equivalence problem for PL-sets
by Bhaskar DasGupta.
- 97-79
(abstract):
Equational Theories of Boolean Functions
by Oya Ekin, Stephan Foldes, Peter L. Hammer, and Lisa Hellerstein.
- 97-80
(abstract):
DIMACS Research and Education Institute (DREI '97)
Cryptography and Network Security
July 28 - August 15, 1997
Abstracts of Talks Presented
by Joan Feigenbaum.
- 97-81
(abstract):
On Arithmetic Branching Programs
by Amos Beimel and Anna Gál.
- 97-82
(abstract):
Diagnosing Double Regular Systems
by Endre Boros, Tonguc Unluyurt.
- 97-83
(abstract):
RNA Based Computing
by Laura F. Landweber.
Return to Tech Reports Page
DIMACS Homepage
Report problems concerning Technical Reports to: tech@dimacs.rutgers.edu
Contacting the Center
Document last modified on January 15, 1998.