More recent technical reports are available on-line and we encourage
downloading 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.
91-1
Connectivity of Consecutive-d Digraphs (II)
D.Z. Du, D.F. Hsu, G.W. Peck
91-2
Rudimentary Reductions Revisited
Allender, Gore
91-5
The Cell Structures of Certain Lattices
Conway, Sloane
91-6
On the Success Probability of the Two Provers in One-Round
Proof Systems
Feige
91-7
Scaling Matrices to Prescribed Row and Column Maxima
Rothblum, H. Schneider, M.H. Schneider
91-8
Stable Marriages: Substituting Linearity for Discreteness
Roth, Rothblum, VandeVate
91-9
A Discounted-Cost Continuous-Time Flexible Manufacturing and
Operator Scheduling Model Solved by Deconvexification Over Time
Eaves, Rothblum
91-10
Optimality of Monotone Assemblies for Coherent Systems
Composed of Series Modules
Hwang, Rothblum
91-11
Approximation of the Spectral Radius, Corresponding
Eigenvector and Second Largest Modulus of an Eigenvalue for Square
Nonnegative Irreducible Matrices
Gross, Rothblum
91-12
Taylor Expansions of Eigenvalue of Perturbed Matrices with
Applications to Spectral Radii of Nonnegative Matrices
Haviv, Ritov, Rothblum
91-13
Dynamic Recomputation Can't Extend the Optimality-Range of
Priority Indices
Rothblum, Rothkopf
91-14
Recent Results on Some no-so-Recent Hypergraph Matching and
Covering Problems
Kahn
91-15
On the Role of Discrete Bid Levels in Oral Auctions
Rothkopf, Harstad
91-16
Applications of a New Space Partitioning Technique
Agarwal, Sharir
91-17
The Modulus of Polynomials with Zeros on the Unit Circle -
A Problem of Erdos
Beck
91-18
Workshop on Applications of Combinatorial Optimization in
Science and Technology COST
91-19
Flat Polynomials on the Unit Circle-Note on a Problem of Littlewood
Beck
91-20
Quasi-random 2 Coloring of Point Sets
Beck
91-21
An Algorithmic Approach to the Lovasz Local Lemma. I.
Beck
91-22
The Reversing Number of a Digraph
Barthelemy, Hudry, Isaak, Roberts, Tesman
91-23
On Complexity of Subset Interconnection Designs
Du
91-24
Fast Approximation Schemes for Convex Programs with Many
Blocks and Coupling Constraints
Grigoriadis, Khachiyan
Scanned File
91-25
Generalization of the Komogorov-Smirnov Goodness-of Fit Test,
Using Group Invariance
Feltz, Goldin
91-26
Transitions in Geometric Minimum Spanning Trees
Monma, Suri
91-27
Relations Between Spectral and Classification Properties of Multigraphs
Bolla
91-28
Scalings of Matrices Satisfying Line-Product Constraints and
Generalizations
Rothblum, and Zenios
91-29
On a Triangulation of the 3-ball and the Solid Torus
Bohus, Jockusch, Lee, and Prabhu
91-30
A New All-Pairs Shortest-Path Algorithm
Catherine C. McGeoch
91-31
Cycles of Length 0 Modulo 4 in Graphs
Dean, Lesniak, Saito
91-32
Cycles Modulo 3
Dean, Toft, Kaneko, Ota
91-33
Quo Vadis, Graph Theory?
Roberts
91-34
On Heuristics for Steiner Minimum Trees
Ding-Zhu Du
91-35
Improved Performance Guarantee of Randomized On-Line Graph Coloring
Magnus M. Halldorsson
91-36
Workshop Summery: Structural Complexity and Cryptography
Eric Allender, Jin-yi Cai, Joan Feigenbaum
91-37
Order Analogues and Betti Polynomials
Lynne Butler
91-38
Note: On the Last New Vertex Visited by a Random Walk
Lovasz, Winkler
91-39
A Digital Signature Scheme and a Public-Key Cryptosystems 1
based on Elliptic Curves over Z
Ueli M. Maurer
91-40
Rounds in Communication Complexity Revisited
Noam Nisan, Avi Wigderson
91-41
How to Compute the Volume
Laszlo Lovasz
91-42
PSPACE is Provable by Two Provers in One Round
Jin-Yi Cai, Anne Condon, Richard J. Lipton
91-43
Probabilistic Behavior of Shortest Paths Over Unbounded Regions
Andrew Chi-Chih Yao
91-44
Most Reliable Double Loop Networks in Survival Reliability
X.D. Hu, F.K. Hwang, Wen-Ch'ing Winnie Li
91-45
A Competitive Algorithm for the Counterfeit Coin Problem
X.D. Hu, F.K. Hwang
91-46
Cutting Numbers for the Forward Loop Backward Hop Network
X.D. Hu, F.K. Hwang
91-47
Generalization of an Engineering Principle
F.K. Hwang, U.G. Rothblum
91-48
Renewal Proposal to National Scientific Foundation Science and
Technology Centers
91-49
Search Problems in the Decision Tree Model
Laszlo Lovasz, Moni Naor, Ilan Newman, Avi Wigderson
91-50
Program Checkers for Probability Generation
Sampath Kannan, Andrew Yao
91-51
Combinatorial Geometry
Janos Pach, Pankaj K. Agarwal
91-52
Interactive Proofs with Space Bounded Provers
Ronitt Rubinfeld
91-53
Greedily Solvable Transportation Networks and Edge-Guided
Vertex Elimination
Ilan Adler, Ron Shami
91-54
Complexity and Algorithms for Reasoning about Time:
A Graph-Theoretic Approach
Martin C. Golumbic, Ron Shamir
91-55
Checking Weak Programs: The Case of Small Dimensional Linear Programming
Hugo Krawczyk
91-56
Graph Entropy and Formula Complexity
Jaikumar Radhakrishnan
91-57
On the Optimal Strongly Connected Orientations of City Street
Graphs IV: Four East-West Avenues or North-South Streets
Fred S. Roberts, Yonghua Xu
91-58
On the Indicator Function of the Plurality Function
Fred S. Roberts
91-59
Limitations on Conclusions Using Scales of Measurement
Fred S. Roberts
91-60
On the Composition of Zero-Knowledge Proof Systems
Oded Goldreich, Hugo Krawczyk
91-61
Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive
Two-Processor Scheduling
E.G. Coffman, M.R. Garey
91-62
3-Choosable Complete Bipartite Graphs
N.V.R. Mahadev, Fred S. Roberts, Prakash Santhanakrishnan
91-63
Complexity Results for POMSET Languages
Joan Feigenbaum, Jeremy A. Kahn, Carsten Lund
91-64
Difference Sets Without k-th Powers
A. Balog, J. Pelikan, J. Pintz, E. Szemeredi
91-65
Singularity Probabilities for Random Plus or Minus 1 Matrices
Jeff Kahn, Janos Komlos, Endre Szemeredi
91-66
On a Problem in Additive Number Theory
A. Sarkozy, E. Szemeredi
91-67
Nonnegative Ranks, Decompositions and Factorizations of Nonnegative Matrices
Joel E. Cohen, Uriel G. Rothblum, RUTCOR
91-68
Using A Characterization of Feasibility of Transportation
n Problems to Establish the Pairwise Connectedness of R with
Respect to Partial Orders
Uriel G. Rothblum, RUTCOR
91-69
Monotone Optimal Multi-Partitions Using Schur Convexity with
Respect to Partial Orders
Frank K. Hwang, Uriel G. Rothblum, RUTCOR, Larry Shepp
91-70
Majorization and Schur Convexity with Respect to Partial Orders
Frank K. Hwang, Uriel Rothblum, RUTCOR
91-71
Covering With Latin Transversals
Noga Alon, Joel Spencer, Prasad Tetali
91-72
Three Thresholds for a Liar
Joel Spencer, Peter Winkler
91-73
Approximate Solution of Matrix Games in Parallel
M.D. Grigoriadis, L.G. Khachiyan
91-74
Proper and Unit Tolerance Graphs
K.P. Bogart, G. Isaak, L. Langley, P.C. Fishburn
91-75
Almost-Everywhere Complexity Hierarchies for Nondeterministic Time
Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer
91-76
Geometric Transversal Theory
Jacob E. Goodman, Richard Pollack, Rephael Wenger
91-77
On the Running Time of the Adleman-Pomerance-Rumely Primality Test
J. Pelikan, J. Pintz, Endre Szemeredi
91-78
Self-Testing/Correcting for Polynomials and the Approximate Functions
Peter Gemmell, Richard Lipton, Ronitt Rubinfeld,
Madhu Sudan, Avi Wigderson
Return to Tech Reports Page
DIMACS Homepage