DIMACS Technical Reports Published in 1996

Obtaining Reports

Problems with Technical Reports?

• 96-01 (abstract): On Order-Generic Queries by Oleg V. Belegradek, Alexei P. Stolboushkin, and Michael A. Taitslin
• 96-02 (abstract): Master-Key Cryptosystems by Matt Blaze, Joan Feigenbaum, and F. T. Leighton
• 96-03 (abstract): Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds by Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay
• 96-04 (abstract): An Isomorphism Theorem for Circuit Complexity by Manindra Agrawal and Eric Allender
• 96-05 (abstract): Subpolytopes of Cyclic Polytopes by Tibor Bisztriczky, Gyula Karolyi
• 96-06 (abstract): Purely Functional Representations of Catenable Sorted Lists by Haim Kaplan and Robert E. Tarjan
• 96-07 (abstract): An algorithm for finding many disjoint monochromatic edges in a complete 2-colored geometric graph by Gyula Karolyi, Janos Pach, Gabor Tardos and Geza Toth
• 96-08 (abstract): Abstract Deducibility and Domain Theory by Vladimir Yu.Sazonov and Dmitri I.Sviridenko
• 96-09 (abstract): Continuous Characterizations of the Maximum Clique Problem by Luana E. Gibbons, Donald W. Hearn, Panos M. Pardalos, Motakuri V. Ramana
• 96-10 (abstract): Szemeredi's Regularity Lemma and its applications in graph theory by Janos Komlos, Miklos Simonovits
• 96-11 (abstract): A Decision Problem Involving Tournaments by Gregory L. Cherlin, Brenda J. Latka
• 96-12 (abstract): k-Weak Orders: Recognition and a Tolerance Result by Ann N. Trenk.
• 96-13 (abstract): Independent Spanning Trees with Small Stretch Factors by Fred Annexstein, Ken Berman, and Ram Swaminathan.
• 96-14 (abstract): Sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operatations by Mikkel Thorup.
• 96-15 (abstract): Workshop Summary: Computational and Complexity Issues in Automated Verification by R. Brayton, A. Emerson, and J. Feigenbaum.
• 96-16 (abstract): On Coherence, Random-Self-Reducibility, and Self-Correction by Joan Feigenbaum, Lance Fortnow, Sophie Laplante, and Ashish Naik.
• 96-17 (abstract): Decentralized Trust Management by Matt Blaze, Joan Feigenbaum, and Jack Lacy.
• 96-18 (abstract): On the Complexity of Semidefinite Programs (revised) by Lorant Porkolab and Leonid Khachiyan.
• 96-19 (abstract): The number of nucleotide sites needed to accurately reconstruct large evolutionary trees by Mike Steel, Laszlo A. Szekely, Peter L. Erdos.
• 96-20 (abstract): Asymptotics of the total chromatic number for simple graphs by P. Mark Kayll.
• 96-21 (abstract): Verification of Fair Transition Systems by Orna Kupferman, Moshe Y. Vardi.
• 96-22 (abstract): A Correctness Proof for Pipelining in RISC Architecture by E. Boerger and S. Mazzanti.
• 96-23 (abstract): Integer NC^1 is equal to Boolean NC^1 by Stephen Bloch.
• 96-24 (abstract): Elimination of Constants from Machines over Algebraically Closed Fields by Pascal Koiran.
• 96-25 (abstract): Closed-form Analytic Maps in One and Two Dimensions Can Simulate Turing Machines by Pascal Koiran and Cristopher Moore.
• 96-26 (abstract): Explicit OR-Dispersers with Polylogarithmic Degree by Michael Saks, Aravind Srinivasan, Shiyu Zhou.
• 96-27 (abstract): Hilbert's Nullstellensatz is in the Polynomial Hierarchy by Pascal Koiran.
• 96-28 (abstract): Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy by Denis Therien, Thomas Wilke.
• 96-29 (abstract): Constant Ratio Approximations of Feedback Vertex Sets in Weighted Undirected Graphs by Vineet Bafna, Piotr Berman and Toshihiro Fujito.
• 96-30 (abstract): Computing similarity between RNA strings by V. Bafna, S. Muthukrishnan and R. Ravi.
• 96-31 (abstract): Packing of induced stars in a graph by Alexander K. Kelmans.
• 96-32 (abstract): A Circular Graph - Counterexample to the Duchet Kernel Conjecture by A. Apartsin, E. Ferapontova, V. Gurvich.
• 96-33 (abstract): Stable Families of Coalitions and Normal Hypergraphs by E. Boros, V. Gurvich, A. Vasin.
• 96-34 (abstract): Stable Effectivity Functions and Perfect Graphs by E. Boros, V. Gurvich.
• 96-35 (abstract): Dual Graphs on Surfaces by Vladimir Gurvich.
• 96-36 (abstract): Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times by E. G. Coffman, Jr., Nabil Kahale and F. T. Leighton.
• 96-37 (abstract): Superpolynomial Lower Bounds for Monotone Span Programs by Laszlo Babai, Anna Gal, Avi Wigderson.
• 96-38 (abstract): How good are branching rules in DPLL? by Ming Ouyang.
• 96-39 (abstract): Deterministic and Randomized Bounded Truth-table Reductions of P, NL, and L to Sparse Sets by Dieter van Melkebeek.
• 96-40 (abstract): Sparse Hard Sets for P by Dieter van Melkebeek, Mitsunori Ogihara.
• 96-41 (abstract): A corrected version of the Duchet Kernel Conjecture by E. Boros, V. Gurvich.
• 96-42 (abstract): Numerical study of a non-equilibrium interface model by Balakrishna Subramanian, G.T. Barkema, J.L. Lebowitz, E.R. Speer.
• 96-43 (abstract): Local quartet splits of a binary tree infer all quartet splits via one dyadic inference rule by Peter L. Erdos, Michael A. Steel, Laszlo A. Szekely, Tandy J. Warnow.
• 96-44 (abstract): Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks by Marek Karpinski, Angus Macintyre.
• 96-45 (abstract): A Lower Bound for Randomized Algebraic Decision Trees by Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky.
• 96-46 (abstract): On the Power of Randomized Branching Programs by Farid Ablayev, Marek Karpinski.
• 96-47 (abstract): On independent domination number of graphs with given minimum degree by N. I. Glebov, A. V. Kostochka.
• 96-48 (abstract): Optimal Suffix Tree Construction with Large Alphabets by Martin Farach.
• 96-49 (abstract): Ranking Arithmetic Proofs by Implicit Ramification by Stephen J. Bellantoni.
• 96-50 (abstract): Ranking Primitive Recursions: the Low Grzegorczyk Classes Revisited (Temporary removed by request of the author. Please refer to: S. Bellantoni and K. H. Niggl, "Ranking Primitive Recursions: The Low Grzygorczyk Hierarchy Revisited", SIAM Journal of Computing, to appear.) by Stephen J. Bellantoni.
• 96-51 (abstract): Significantly Lower Entropy Estimates for Natural DNA Sequences by David Loewenstern and Peter N. Yianilos.
• 96-52 (abstract): Randomized Omega (n^2) Lower Bound for Knapsack by Dima Grigoriev, Marek Karpinski.
• 96-53 (abstract): On the Design of Optimization Criteria for Multiple Sequence Alignment by Dannie Durand and Martin Farach.
• 96-54 (abstract): Correctness of Constructing Optimal Alphabetic Trees Revisited by Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter.
• 96-55 (abstract): On galleries with no bad points by Pavel Valtr.
• 96-56 (abstract): Vapnik-Chervonenkis Dimension of Recurrent Neural Networks by Pascal Koiran and Eduardo D. Sontag.
• 96-57 (abstract): On the Size of Set Systems on [n] Not Containing Weak (r, \Delta)-Systems by Vojtech Rodl and Lubos Thoma.
• 96-58 (abstract): On Perfect Matchings and Hamiltonian Cycles in Sums of Random Trees by Alan Frieze, Michal Karonski, and Lubos Thoma.
• 96-59 (abstract): Approximating Dense Cases of Covering Problems by Marek Karpinski, Alexander Zelikovsky.
• 96-60 DIMACS SPECIAL YEAR IN MATHEMATICAL SUPPORT FOR MOLECULAR BIOLOGY ANNUAL REPORT JANUARY 1996
• 96-61 DIMACS ANNUAL REPORT -DECEMBER 1996

Return to Tech Reports Page

DIMACS Homepage