Browse

ftp://dimacs.rutgers.edu (342)

	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-52.ps, 19930113 DIMACS Technical Report 92-52 December 1992 A Tight Bound for Edge Guards in Monotone Polygons by Iliana Bjorling-Sachs1 Department of Computer Science Rutgers University New Brunswick, New Jersey 08903 Diane L. Souvaine2;3 Department of Computer Science Rutgers University New Brunswick, New Jersey
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-60.ps, 19930113 The Power of Adaptiveness and Additional Queries in Random-Self-Reductions Joan Feigenbaum Lance Fortnowy Carsten Lundz Daniel Spielmanx AT&T Bell Laboratories, Room 2C-473, 600 Mountain Avenue, Murray Hill, NJ 07974-0636. Email: jf@research.att.com yUniversity of Chicago, Computer Science Department,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-54.ps, 19930201 DIMACS Technical Report 92-54 December 1992 Combinatorial Complexity of Signed Discs by Diane L. Souvaine1;2 Department of Computer Science Rutgers University New Brunswick, New Jersey 08903 Chee-Keng Yap3 Department of Computer Science New York University New York, New York 10012 1Permanent Member
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-03.ps, 19930311 DIMACS Technical Report January 1993 k-Neighborhood Covering and Independence Problems by Shiow-Fen Hwang Department of Computer Science Fen Chia University Taichung 40724, Taiwan Republic of China Gerard J. Chang 1 Department of Applied Mathematics National Chiao Tung University Hsinchu 30050, Taiwan
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-47A.ps, 19930311
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-53.ps, 19930311
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-43.ps, 19930311 Locally Random Reductions in Interactive Complexity Theory Joan Feigenbaum AT&T Bell Labs, Rm 2C-473 600 Mountain Avenue Murray Hill, NJ 07974-0636 USA jf@research.att.com 1
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-44.ps, 19930311 5 T. Tsuchiya and M. Muramatsu. Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems. Technical Report 423, The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo, 106, Japan, January 1992. R. Vanderbei, M. Meketon, and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-51.ps, 19930311 DIMACS Technical Report 92-51 March 1993 Weighted Multidimensional Search and its Application to Convex Optimization by Richa Agarwala and David Fern andez-Baca1;2 Department of Computer Science Iowa State University Ames, Iowa 50011 1Visiting Member 2Supported in part by the National Science Foundation
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-08.ps, 19930312 DIMACS Technical Report 93-8 February 1993 Hilbert Series of Group Representations and Gr obner Bases for Generic Modules by Shmuel Onn 1 DIMACS Rutgers University Piscataway, New Jersey 08855-1179 E-mail: onn@dimacs.rutgers.edu 1Research was supported by the Mittag-Leffler Institute, by the
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-13.ps, 19930312 Combinatorial Optimization and Computations in the Ring of Polynomials Alexander I. Barvinok * Version of March 12, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-11.ps, 19930312 DIMACS Technical Report March 1993 The L(2,1)-Labeling Problem on Graphs by Gerard J. Chang 1 ;2 and David Kuo 1 Department of Applied Mathematics National Chiao Tung University Hsinchu 30050, Taiwan Republic of China E-mail: gjchang@cc.nctu.edu.tw 1Supported in part by the National Science Council of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-12.ps, 19930312 DIMACS Technical Report 93-12 March 1993 A Tight Bound for Edge Guards in Rectilinear Monotone Polygons by Iliana Bjorling-Sachs1 Department of Computer Science Rutgers University New Brunswick, New Jersey 08903 1Supported by DIMACS research assistantship DIMACS is a cooperative project of Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-05.ps, 19930312 Monotone Gray Codes and the Middle Levels Problem Carla D. Savage Department of Computer Science North Carolina State University Raleigh, North Carolina 27695-8206 cds@adm.csc.ncsu.edu Peter Winkler Bellcore 445 South St. Morristown, New Jersey 07962-1910 pw@bellcore.com Research supported by National
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-07.ps, 19930312 On Computing Algebraic Functions using Logarithms and Exponentials Dima Grigoriev1, Michael Singer2, and Andrew Yao3
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-10.ps, 19930312 Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions Anne Condon University of Wisconsin Computer Sciences Department 1210 West Dayton Street Madison, WI 57306 USA condon@cs.wisc.edu Joan Feigenbaum AT&T Bell Laboratories Room 2C473 600 Mountain Avenue Murray
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-01.ps, 19930312 A Randomized Algorithm for Finding Maximum with O((log n)2) Polynomial Tests Hing F. Ting1 and Andrew C. Yao2
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-06.ps, 19930316 Optimal Compression of Propositional Horn Knowledge Bases: Complexity and Approximation1 Peter L. Hammer2 and Alexander Kogan2;3 January 19, 1993 1The authors gratefully acknowledge the partial support of AFOSR (Grants 89-0512B and F49620-93-1-0041) and ONR (Grants N00014-92-J1375 and N00014-92-J4083).
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-15.ps, 19930316 Enumerating Consecutive and Nested Partitions for Graphs F. K. Hwang AT&T Bell Laboratories Murray Hill, New Jersey 07974 G. J. Chang* Department of Applied Mathematics National Chiao Tung University Hsinchu, 30050 Taiwan, ROC 1. Introduction Hwang and Mallows studied the numbers of nested and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-16.ps, 19930322 DIMACS Technical Report 93-16 March 1993 1 by Adam L. Buchsbaum;2;3 Dept. of Computer Science Princeton University Princeton, NJ 8544 alb@cs.princeton.edu Robert E. Tarjan4;5 Dept. of Computer Science Princeton University Princeton, NJ 08544 and NEC Research Institute 4 Independence Way Princeton, NJ
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1992/92-55.ps, 19930322 Nonpolyhedral relaxations of graph-bisection problems Svatopluk Poljak Department of Applied Mathematics Charles University Malostransk e n. 25, 118 00 Praha 1 Czechoslovakia and Franz Rendl y Technische Universit at Graz Institut f ur Mathematik Kopernikusgasse 24, A-8010 Graz, Austria March 22, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-17.ps, 19930326 ON THE STRUCTURE OF CO-CRITICAL GRAPHS by Anna Galluccio, (IASI-CNR, Rome) Mikl os Simonovits* and G abor Simonyi * (Mathematical Institute of the Hungarian Academy of Sciences) * Supported by DIMACS and OTKA
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-19.ps, 19930329 INDEFINITE TRUST REGION SUBPROBLEMS AND NONSYMMETRIC EIGENVALUE PERTURBATIONS Ronald J. Stern Department of Mathematics and Statistics Concordia University Montreal, Quebec H4B 1R6, Canada and Henry Wolkowicz University of Waterloo Department of Combinatorics and Optimization Waterloo, Ontario N2L 3G1,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-04.ps, 19930329 DIMACS Technical Report 93-04 March 1993 A Polynomial-Time Algorithm for the Phylogeny Problem when the Number of Character States is Fixed by Richa Agarwala1 and David Fern andez-Baca;2;3 Department of Computer Science Iowa State University Ames, Iowa 50011 1Supported in part a College of Liberal Arts
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-18.ps, 19930329 CONVEX RELAXATIONS OF 0-1 QUADRATIC PROGRAMMING Svatopluk Poljak Institute of Mathematics Academia Sinica Nankang, Taipei, Taiwan 11529 and Henry Wolkowiczy University of Waterloo Department of Combinatorics and Optimization Waterloo, Ontario N2L 3G1, Canada e-mail henry@orion.uwaterloo.ca March 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-14.ps, 19930405 DIMACS Technical Report 93-14 April 1993 Testing Simple Polygons1 by Esther M. Arkin;2 Dept. of Applied Mathematics State University of New York Stony Brook, NY 11794-3600 Patrice Belleville School of Computing Science Simon Fraser University Burnaby, BC, Canada V5A 1S6 Joseph S.B. Mitchell3 Dept. of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-22.ps, 19930408 DIMACS Technical Report 93-22 April 1993 A Robust Model for Finding Optimal Evolutionary Trees by Martin Farach1 Sampath Kannan;2 Tandy Warnow;3 DIMACS U. of Arizona Sandia National Labs 1DIMACS, Box 1179, Rutgers University, Piscataway, NJ 08855; (908) 932-5928; farach@dimacs.rutgers.edu; Supported by
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-23.ps, 19930412 DIMACS Technical Report 93-23 April 1993 Consecutive Cuts and Paths, and Bounds on k-Terminal Reliability by Heidi J. Strayer Computer Science University of Waterloo Waterloo, Ontario, CANADA hjs@caddac.uwaterloo.ca Charles J. Colbourn1;2 Combinatorics and Optimization University of Waterloo Waterloo,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-24.ps, 19930415 DIMACS Technical Report April 1993 Weighted Independent Perfect Domination on Cocomparability Graphs by Gerard J. Chang 1 ;2 Department of Applied Mathematics National Chiao Tung University Hsinchu 30050, Taiwan Republic of China Email: gjchang@cc.nctu.edu.tw C. Pandu Rangan and Satyan R. Coorg 3
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-26.ps, 19930420 The Russian Option: Reduced Regret Larry Shepp A. N. Shiryaev* AT&T Bell Laboratories Murray Hill, New Jersey 07974 April 20, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-25.ps, 19930420 A Dual Russian Option for Selling Short L. A. Shepp A. N. Shiryaev* AT&T Bell Laboratories Murray Hill, New Jersey 07974 April 20, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-02.ps, 19930420 1. Introduction Let M be a matroid on a finite set. Let M(M) denote the set of oriented matroids whose underlying matroid is M. We define an equivalence relation on M(M) in terms of reorientations" of oriented matroids. The object of this paper is to characterize the set R(M) of reorientation classes
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-02/93-02A.ps, 19930420 PROJECTIVE ORIENTATIONS OF MATROIDS by Israel M. Gelfand123 Department of Mathematics Rutgers University New Brunswick, NJ 08903 USA Grigori L. Rybnikov1 3 4 Research Institute for System Studies Russian Academy of Science 23 Avtozavodskaya, Moscow 109280 Russia Email: rybnikov@systud.msk.su David A.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-27.ps, 19930427 DIMACS Technical Report 93-27 April 1993 Non{Stanley Bounds for Network Reliability by Jason I. Brown 1 Department of Mathematics and Statistics York University, North York, Canada Charles J. Colbourn2;3 Department of Combinatorics and Optimization University of Waterloo, Waterloo, Canada 1Research
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-28.ps, 19930427 DIMACS Technical Report 93-28 April 1993 Some Open Problems on Reliability Polynomials by Charles J. Colbourn1;2 Combinatorics and Optimization University of Waterloo Waterloo, Ontario, CANADA cjcolbou@math.uwaterloo.ca 1Special Year Visitor to DIMACS, whose support is gratefully acknowledged 2Research
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-30.ps, 19930510 DIMACS Technical Report 93-30 May 1993 by Adam L. Buchsbaum1;2 Dept. of Computer Science Princeton University Rajamani Sundar3 Dept. of Computer Science and Automation Indian Institute of Science Robert E. Tarjan4;5 Dept. of Computer Science Princeton University and NEC Research Institute 1Affiliated
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-31.ps, 19930519 DIMACS Technical Report 93-31 May 1993 Constructing Language Instances Based on Partial Information by Laura A. Sanchis1 ;2 Department of Computer Science Colgate University Hamilton, NY 13346 1Supported in part by DIMACS. 2Supported in part by NSF grant CCR-9101974. DIMACS is a cooperative project of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-33.ps, 19930607 DIMACS Technical Report 93-33 June 1993 INVERSE PROBLEMS IN ADDITIVE NUMBER THEORY by Melvyn B. Nathanson 1 Department of Mathematics Lehman College (CUNY) Bronx, New York 10468 1This book was written while I was a long-term visitor at DIMACS. I am grateful to DIMACS for its hospitality. This work was
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-35.ps, 19930610 DIMACS Technical Report 93-35 June 1993 Entropy splitting hypergraphs by G abor Simonyi1 DIMACS Center Rutgers University Piscataway, NJ 08855-1179, U.S.A. and Mathematical Institute of the Hungarian Academy of Sciences H-1364 Budapest, P.O.B. 127, Hungary 1Research supported by DIMACS DIMACS is a
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-36.ps, 19930617 Abstracts of the DIMACS Workshop on Parallel Algorithms for Unstructured and Dynamic Problems June 2{4, 1993 1 Wednesday, June 2, 9-10 Adaptive Problems and High Performance Fortran Compilers Joel Saltz University of Maryland Over the past few years, we have developed methods that make it possible for a
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-29.ps, 19930618 DIMACS Technical Report 93-29 May 1993 Combinatorial Optimization: A Survey by Martin Gr otschel Konrad-Zuse-Zentrum f ur Informationstechnik Heilbronner Str. 10 D-1000 Berlin 31, Germany, and Technische Universit at Berlin Strasse des 17. Juni 136 D-1000 Berlin 12, Germany L aszl o Lov asz 1 Dept. of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-38.ps, 19930701 Parallel Processing of Discrete Optimization Problems Grama Y. Ananth and Vipin Kumar Department of Computer Science, University of Minnesota Minneapolis, MN 55455 ananth@cs.umn.edu and kumar@cs.umn.edu and Panos Pardalos Department of Industrial and Systems Engineering University of Florida
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-39.ps, 19930701 The Simplex Algorithm with a New Primal and Dual Pivot Rule Hsin-Der CHEN , Panos M. PARDALOS and Michael A. SAUNDERSy June 14, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-37.ps, 19930701 DIMACS Technical Report 93{37 June 1993 Quasi-Acyclic Propositional Horn Knowledge Bases: Optimal Compression1 by Peter L. Hammer2 RUTCOR ffl Rutgers University P.O. Box 5062 ffl New Brunswick, NJ 08903-5062 e-mail: hammer@rutcor.rutgers.edu and Alexander Kogan2 RUTCOR and Graduate School of Management
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-41.ps, 19930706 DIMACS Technical Report 93{41 ON EDGE BIJECTIONS OF GRAPHS by A.K. Kelmans 1 RUTCOR, Rutgers University New Brunswick, NJ 08903, USA 1The author gratefully acknowledges the partial support of the National Science Foundation under Grant NSF{STC91{19999 to Rutgers University and the DIMACS Center DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-40.ps, 19930706 DIMACS Technical Report 93-40 June 1993 On Lattice-Free Polytopes 1 by Michel Deza LIENS-CNRS Ecole Normale Sup erieure 45 Rue d'Ulm 75005 Paris FRANCE Shmuel Onn DIMACS Rutgers University Piscataway, NJ 08855-1179 onn@dimacs.rutgers.edu 1Research was supported by the Center for Discrete Mathematics and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-42.ps, 19930707 On a Covering Property of Maximal Sperner Families* P eter L. Erd}os and Niall Graham AMS Subject Classifications (1991): 05 D 05, 06 A 07 Key words: Sperner family, ranked poset, monotone Boolean function
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-43.ps, 19930719 DIMACS Technical Report 93-43 July 1993 Relationships Among PL, #L, and the Determinant by Eric Allender1;2 Department of Computer Science Rutgers University New Brunswick, NJ 08903 Mitsunori Ogiwara3 Department of Computer Science University of Electro-Communications Chofu-shi, Tokyo 182, JAPAN
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-46.ps, 19930810 DIMACS Technical Report 93-46 August 1993 Fast Comparison of Evolutionary Trees by Martin Farach1;2 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903 Mikkel Thorup3;4 Dept. of Computing Oxford University Oxford, England 1Permanent Member 2Supported by DIMACS (Center for
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-45.ps, 19930810 DIMACS Technical Report 93-45 August 1993 An Efficient Algorithm for Dynamic Text Indexing by Ming Gu1 Dept. of Computer Science Yale University New Haven, CT 06520 and Dept. of Mathematics UC Berkeley Martin Farach2 ;3 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903 Richard
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-52.ps, 19930811 The Z4-Linearity of Kerdock, Preparata, Goethals and Related Codes A. Roger Hammons, Jr.* Hughes Aircraft Company 8433 Fallbrook Avenue, Canoga Park, CA 91304 U.S.A. P. Vijay Kumar* Communication Science Institute, EE-Systems University of Southern California, Los Angeles, CA 90089 U.S.A. A. R.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-51.ps, 19930811 OPERATING MANUAL FOR GOSSET: A GENERAL- PURPOSE PROGRAM FOR CONSTRUCTING EXPERIMENTAL DESIGNS (SECOND EDITION). R. H. Hardin N. J. A. Sloane Mathematical Sciences Research Center AT&T Bell Laboratories Murray Hill, New Jersey 07974 USA
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-48.ps, 19930811 Covering Arrays and Intersecting Codes N. J. A. Sloane Mathematical Sciences Research Center AT&T Bell Laboratories Murray Hill, New Jersey 07974 September 18, 1992
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-47.ps, 19930811 A New Approach to the Construction of Optimal Designs R. H. Hardin N. J. A. Sloane AT&T Bell Laboratories Murray Hill, New Jersey 07974 USA September 28, 1992
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-54.ps, 19930811 References B. W. Char et al., Maple V language reference manual, Springer-Verlag, NY, 1991. H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, Springer-Verlag, NY, Fourth edition, 1984. L. E. Dickson, History of the theory of numbers, Chelsea, NY, 1966,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-50.ps, 19930811 P. Sol e, A quaternary cyclic code, and a family of quadriphase sequences with low correlation properties, Lect. Notes Computer Science, 388 (1989), 19301. M. Yamada, Distance-regular digraphs of girth 4 over an extension ring of Z=4Z, Graphs and Combinatorics, 6 (1990), 38194. 8
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-49.ps, 19930811 The Nordstrom-Robinson Code is the Binary Image of the Octacode G. David Forney, Jr. Motorola Codex Mansfield, MA 02048 USA N. J. A. Sloane Mathematical Sciences Research Center AT&T Bell Laboratories Murray Hill, New Jersey 07974 USA Mitchell D. Trott Department of Electrical Engineering and Computer
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-53.ps, 19930811 Quaternary Constructions for the Binary Single-Error-Correcting Codes of Julin, Best and Others J. H. Conway Mathematics Department Princeton University Princeton, NJ 08544 N. J. A. Sloane Mathematical Science Research Center AT&T Bell Laboratories Murray Hill, NJ 07974 February 22, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-59.ps, 19930817 Can Visibility Graphs Be Represented Compactly Pankaj K. Agarwaly Noga Alonz Boris Aronovx Subhash Suri{ August 16, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-56.ps, 19930817 A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk John Hershbergery Subhash Suriz August 16, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-57.ps, 19930817 Finding a Shortest Diagonal of a Simple Polygon in Linear Time John Hershberger DEC/SRC 130 Lytton Avenue, Palo Alto, California 94301 Subhash Suri Bellcore 445 South Street, Morristown, New Jersey 07960 August 16, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-58.ps, 19930817 Matrix Searching with the Shortest Path Metric John Hershberger DEC/SRC 130 Lytton Avenue, Palo Alto, California 94301 Subhash Suri Bellcore 445 South Street, Morristown, New Jersey 07960 August 16, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-61c.ps, 19930830 44 B.6.5.2.2.1. Set a0:= b, and a0:= a. B.6.5.2.2.2. Set P := P
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-61b.ps, 19930830 21 Main Theorem 6.1 Given a grammar G, a finite set Ein of parse tree pairs, and the universal parser U obtained by any one of the various LL or LR techniques, we can decide if there exists a determinization P of U , and a finite set Eout of parse tree pairs such that (Ein
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-60a.ps, 19930830 DIMACS Technical Report 93-60 August 1993 Shortcutting Planar Digraphs by Mikkel Thorup1;2;3 Programming Research Group of Oxford University 8{11 Keble Road Oxford OX1 3QD United Kingdom 1DIMACS visitor 92/93. 2Supported by the Danish Technical Research Council and the Danish Research Academy. 3Moving
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-61a.ps, 19930830 DIMACS Technical Report 93-61 August 1993 Controlled Grammatic Ambiguity by Mikkel Thorup1;2;3 Programming Research Group of Oxford University 8{11 Keble Road Oxford OX1 3QD United Kingdom e-mail: thorup@prg.ox.ac.uk 1DIMACS visitor 92/93. 2Supported by the Danish Technical Research Council and the
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-55.ps, 19930830 D4 : X = 1 3 " 1 2 2 1 ; Y = 1p2 " 2 1 1 2 A(2)6 : X = 1 12 2 64 4 2 4 2 1 6 4 6 8 3 75 ; Y = 1p7 2 64 4 2 1 2 4 2 1 2 4 3 75 ; E8 : X = 1 2 2 6664 2 1 1 1 2 1 1 2 1 1 1 2 3 7775 ; Y = 2 6664 2 1 1 1 2 1 1 2 1 1 1 2 3 7775 ;
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-62.ps, 19930907 Minors and the Chromatic Index of r-graphs K. Kilakos B. Shepherd Dept de Math ematique et d'Informatique, Mathematics and Operational Research, Universit e du Queb ec a Montr eal, London School of Economics, Canada. U.K.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-63.ps, 19930907 Note on a Conjecture of Toft T.R. Jensen F.B. Shepherd Dept. of Mathematics and Computer Sc. Mathematics and Operational Research Odense University London School of Economics Odense, Denmark London, U.K.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-65.ps, 19930927 Instance-Hiding Proof Systems Donald Beaver The Pennsylvania State University University Park, PA 16802 USA beaver@cse.psu.edu Joan Feigenbaum AT&T Bell Laboratories Murray Hill, NJ 07974-0636 USA jf@research.att.com Rafail Ostrovskyy University of California at Berkeley and International Computer
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-64.ps, 19931104 DIMACS Technical Report 93-64 October 1993 On Enumeration of Near to Best Solutions in Discrete and Dynamic Programming by Joseph V. Romanovsky1 Mathematical Faculty St. Petersburg University St. Petersburg, 198904, Russia 1Special Year Visitor to DIMACS, whose support is gratefully acknowledged DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-68.ps, 19931105 DIMACS Technical Report 93-68 November 1993 Generalization of the Tetrad Representation Theorem by Glenn Shafer Graduate School of Management, Rutgers University 81 New Street, Newark, NJ 07102 Alexander Kogan Graduate School of Management, Rutgers University 81 New Street, Newark, NJ 07102 and RUTCOR,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-66.ps, 19931105 dvitps ERROR: revesz.dvi @ dimacs.rutgers.edu Certain fonts that you requested in your dvi file could not be found on the system. In order to print your document, other fonts that are installed were substituted for these missing fonts. Below is a list of the substitutions that were made.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-70.ps, 19931105 Eigenvalues and Expansion of Regular Graphs Nabil Kahale DIMACS Rutgers University, Piscataway, NJ 8855
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-72.ps, 19931115 Symmetric Quasi-Definite Matrices Robert J. Vanderbei DIMACS 93-72 Rutgers University New Brunswick, NJ 08903
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-75.ps, 19931115 Interior-Point Methods for Max-Min Eigenvalue Problems Franz Rendl Robert J. Vanderbei y Henry Wolkowicz z DIMACS Rutgers University New Brunswick, NJ 08903 November 8, 1993 Technical Report 93-75
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-74.ps, 19931115 Brownian Bandits Avi Mandelbaum Robert J. Vanderbei y DIMACS Rutgers University New Brunswick, NJ 08903 November 8, 1993 Technical Report 93-74
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-71.ps, 19931115 A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees Philip N. Klein Robert E. Tarjany October 12, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-73.ps, 19931115 Affine-Scaling Trajectories Associated with a Semi-Infinite Linear Program Robert J. Vanderbei DIMACS Rutgers University New Brunswick, NJ 08903 November 8, 1993 Technical Report 93-73
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-77.ps, 19931116 1 DIMACS Technical Report 93-77 November 1993 An analog of Freiman's theorem in groups by Imre Z. Ruzsa 1 Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127, H-1364 Hungary 1Paper was finished while author was visiting DIMACS. Support by DIMACS is gratefully acknowledged.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-79.ps, 19931116 DIMACS Technical Report 93-79 November 1993 Random Debaters and the Hardness of Approximating Stochastic Functions by Anne Condon1 Computer Sciences Department University of Wisconsin Madison, WI 57306 condon@cs.wisc.edu Joan Feigenbaum2 AT&T Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-78.ps, 19931116 On reducing the cut ratio to the multicut problem Nabil Kahale
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-76.ps, 19931119 BIPARTITE DIMENSIONS AND BIPARTITE DEGREES OF GRAPHS1 Peter C. Fishburn AT&T Bell Laboratories, Murray Hill, NJ 07974 Peter L. Hammer2 Rutgers University, New Brunswick, NJ 08903 DRAFT, June 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-84.ps, 19931206 DIMACS Technical Report 93-84 December 1993 NOTES ON THE KOLAKOSKI SEQUENCE by Va<=sek Chv atal1 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903 1Permanent Member DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-83.ps, 19931206 Isoperimetric Inequalities and Eigenvalues Nabil Kahale
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-88.ps, 19940107 On Lattices Equivalent to Their Duals J. H. Conway Mathematics Department Princeton University Princeton, NJ 08544 USA N. J. A. Sloane Mathematical Sciences Research Center AT&T Bell Laboratories Murray Hill, New Jersey 07974 USA December 13, 1993
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-93.ps, 19940110 0-1 Law 1 On the Very Weak 0-1 Law for Random Graphs with Orders Saharon Shelah The Hebrew University, Math Institute Rutgers University, Math Department
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-89.ps, 19940110 DIMACS Technical Report 93-89 December 1993 Optimization Methods for Computing Global Minima of Nonconvex Potential Energy Functions by Panos M. Pardalos1 Department of Industrial and Systems Engineering University of Florida, Gainesville, FL 32611 Email: pardalos@math.ufl.edu David Shalloway Section of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-92.ps, 19940110 D I M A C S NSF ANNUAL REPORT - FY 1994 COVER PAGE i Contents Cover Page i 1 Summary of Research 1 1.1 Research Accomplishments : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.1.1 Special Year 1992-93 - Combinatorial Optimization : : : : : : : : : : : : : : : 1 1.1.2 Special Year
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-03.ps, 19940128 DIMACS Technical Report 94-3 January 1994 Independence of Solution Sets and Minimal Asymptotic Bases by Paul Erd}os 1 Melvyn B. Nathanson 2 Prasad Tetali 3 1Mathematical Institute, Hungarian Academy of Sciences, Budapest, Hungary 2Department of Mathematics, Lehman College (CUNY), Bronx, NY 10468. This
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-02.ps, 19940128 DIMACS Technical Report 94-2 January 1994 Ballot numbers, alternating products, and the Erd}os-Heilbronn conjecture by Melvyn B. Nathanson 1 Department of Mathematics Lehman College (CUNY) Bronx, New York 10468 e-mail: nathansn@dimacs.rutgers.edu 1This research was supported in part by grants from the
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-01.ps, 19940128 DIMACS Technical Report 94-1 January 1994 Inverse Theorems for Subset Sums 1 by Melvyn B. Nathanson 2 Department of Mathematics Lehman College (CUNY) Bronx, New York 10468 e-mail: nathansn@dimacs.rutgers.edu 11991 Mathematics Subject Classification. Primary 11B13,11B75,11P99. Key words and phrases.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-69.ps, 19940220 DIMACS Technical Report 93-69 October 1993 Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem by Laura A. Sanchis1 ;2 Department of Computer Science Colgate University Hamilton, NY 13346 Arun Jagota Department of Mathematical Sciences Memphis State
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-10.ps, 19940418 DIMACS Technical Report 94{10 April 1994 A Weak Version of the Blum, Shub & Smale model by Pascal Koiran1 DIMACS Rutgers University e-mail: koiran@dimacs.rutgers.edu 1Most of this work was performed while the author was with LIP, Ecole Normale Sup erieure de Lyon, France. Support by an INRIA fellowship
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-06.ps, 19940418 TOURNAMENT CERTIFICATES Peter Fishburn, Jeong Han Kim, and Prasad Tetali Mathematical Sciences Research Center AT&T Bell Laboratories, Murray Hill, NJ 07974 February, 1994
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-07.ps, 19940418 14 Lemmas 4.1, and 4.6. Therefore we may iteratively repeat the above step generating F6, ..., etc., until for some j the constructed S(Fj)-path contains all vertices of G. This shows that G contains a Hamiltonian path which concludes the proof of Theorem 2. 2 References C.Delobel and R.G.Casey.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-08.ps, 19940418 DIMACS Technical Report 94{8 April 1994 Computing over the Reals with Addition and Order: Higher Complexity Classes1 by Felipe Cucker;2 Universitat Pompeu Fabra Balmes 132, Barcelona 08008 SPAIN e-mail: cucker@upf.es Pascal Koiran3 DIMACS, Rutgers University Piscataway, NJ 08855 USA e-mail:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-04.ps, 19940418 A Local Rule Based Theory of Virus Shell Assembly Bonnie Berger y Peter W. Shorz Lisa Tucker-Kelloggy Jonathan Kingx Mathematics Department and yLaboratory for Computer Science and xBiology Department, Massachusetts Institute of Technology, Cambridge, MA 02139; and zAT&T Bell Laboratories, Murray Hill,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-11.ps, 19940418 DIMACS Technical Report 94-11 April 1994 by William Steiger 1;2 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 8903 Ileana Streinu 3 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903 1 Permanent Member 2 Research Supported in Part by NSF grant
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-09.ps, 19940418 DIMACS Technical Report 94-9 March 1994 Decompositions of Partially Defined Boolean Functions 1 by Endre Boros ;2 RUTCOR, Rutgers University New Brunswick, NJ 08904 Vladimir Gurvich 3 RUTCOR, Rutgers University New Brunswick, NJ 08904 Peter L. Hammer 2 RUTCOR, Rutgers University New Brunswick, NJ 08903
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-05.ps, 19940418 Self-Affine Tiles in Rn Jeffrey C. Lagarias AT&T Bell Laboratories Murray Hill, New Jersey 07974 Yang Wang Georgia Institute of Technology Atlanta, GA 30332
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-19.ps, 19940504 DIMACS Technical Report 94-19 April 1994 COORDINATION COMPLEXITY OF PARALLEL PRICE-DIRECTIVE DECOMPOSITION by Michael D. Grigoriadis1 and Leonid G. Khachiyan1 Department of Computer Science Rutgers University New Brunswick, NJ 08903 * Research supported by the National Science Foundation under grant
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-20.ps, 19940504 DIMACS TECHNICAL REPORT 94-20 April 1994 DIMACS Workshop on Parallel Processing of Discrete Optimization Problems April 28{29, 1994 Organizers P.M. Pardalos 1 (Department of Industrial and Systems Engineering, University of Florida) M.G.C. Resende (AT &T Bell Laboratories, Murray Hill) K.G. Ramakrishnan
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-17.ps, 19940504 DIMACS Technical Report 94-17 April 1994 Normal Numbers and Sources for BPP by Martin Strauss1;2 Department of Mathematics Rutgers University New Brunswick, NJ 08903 1Affiliated Graduate Student Member 2Research supported by NSF grant CCR-9204874. DIMACS is a cooperative project of Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-18.ps, 19940504 DIMACS Technical Report 94-18 April 1994 Measure on Small Complexity Classes, with Applications for BPP by Eric Allender1;2 Department of Computer Science Rutgers University New Brunswick, NJ 08903 Martin Strauss3;4 Department of Mathematics Rutgers University New Brunswick, NJ 08903 1Permanent Member
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-16.ps, 19940504 DIMACS Technical Report 94-16 April 15, 1994 A SUBLINEAR-TIME RANDOMIZED APPROXIMATION ALGORITHM FOR MATRIX GAMES* by Michael D. Grigoriadis1 and Leonid G. Khachiyan1 Department of Computer Science Rutgers University New Brunswick, NJ 08903 * Research supported by the National Science Foundation under
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-27.ps, 19940531 DIMACS Technical Report 94-27 May 1994 The Parallel Implementation of N-body Algorithms by Pangfeng Liu1;2;3 DIMACS center Rutgers University Piscataway, New Jersey 08855-1179 1Post-doctoral fellow 2ONR Grant N00014-93-1-0944, NSF/DARPA grant CCR-89-08285, DARPA contract DABT 63- 91-C-0031 3DIMACS NSF
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-29.ps, 19940531 DIMACS Technical Report 94-29 December 10, 1993 An NC algorithm for depth-first search of graphs of bounded genus by Justin R. Smith1 Department Of Mathematics and Computer Science Drexel University Philadelphia, PA 19104 Email: jsmith@mcs.drexel.edu Olga Rayskina2 Department Of Mathematics and Computer
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-32.ps, 19940601 DIMACS Technical Report 94-32 June 1994 Perfect Graphs are Kernel Solvable by Endre Boros1;2 Vladimir Gurvich3 1Permanent Member 2RUTCOR, Rutgers University, P.O. Box 5062, New Brunswick, NJ 08903 3RUTCOR, Rutgers University, P.O. Box 5062, New Brunswick, NJ 08903; on leave from the International
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-31.ps, 19940601 ON THE COMPLEXITY OF SOME BASIC PROBLEMS IN COMPUTATIONAL CONVEXITY: II. Volume and mixed volumes Peter Gritzmann and Victor Klee Introduction This paper is the second part of a broader survey of computational convexity, an area of mathematics that has crystallized around a variety of results, problems
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-14.ps, 19940601 11 J. Balc azar, Self-Reducibility, Journal of Computer and System Sciences 41 (1990) 367-388. S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proc. 19th ACM Symposium on Theory of Computing, 1987, pp. 12331. J. Goldsmith, L. Hemachandra, D. Joseph, and P. Young,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-28.ps, 19940602 DIMACS Technical Report 94-28 June 1994 Noncommutative symmetric functions by I.M. Gelfand , D. Krob, A. Lascoux, B. Leclerc, V.S. Retakh and J.-Y.Thibon DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore. DIMACS is an NSF Science and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-28T.ps, 19940602 NONCOMMUTATIVE SYMMETRIC FUNCTIONS I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V.S. Retakh and J.-Y. Thibon April 28, 1994 Israel M. Gelfand Department of Mathematics Rutgers University New Brunswick, N.J. 08903 U.S.A. Daniel Krob Laboratoire d'Informatique Th eorique et Programmation Universit e
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-34.ps, 19940608 DIMACS Technical Report 94-34 June 1994 Upper and Lower Bounds for Selection on the Mesh by Anne Condon 1 Dept. of Computer Science University of Wisconsin-Madison Madison, WI 53706 condon@cs.wisc.edu Lata Narayanan2;3 Dept. of Computer Science Concordia University Montreal, Canada H3G 1M8
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-35.ps, 19940616 DIMACS Technical Report 94-35 June 1994 1 by Noga Alon 2 Nabil Kahale 3 1 A preliminary version of this paper appeared in the Proc. of the 26 th ACM STOC, ACM Press (1994), 346-355. 2 Institute for Advanced Study, Princeton, NJ 8540, USA and Department of Mathematics, Tel Aviv University, Tel Aviv,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-37.ps, 19940622 DIMACS Technical Report 94-37 June 1994 Algorithms for Quantum Computation: Discrete Log and Factoring by Peter W. Shor1 AT&T Bell Labs Room 2D-149 600 Mountain Ave. Murray Hill, NJ 07974 1Permanent Member DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-36.ps, 19940629 DIMACS Technical Report 94-36 June 1994 A Comprehensive Manual for NETPAD Users with Exercises on Discrete Mathematics by Yanxi Liu1 1Supported in part by DIMACS DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore. DIMACS is an NSF Science and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-39.ps, 19940630 DIMACS Technical Report 94-39 June 1994 by Nabil Kahale 1 1 DIMACS, Rutgers University, Piscataway, NJ 8855. Email: kahale@dimacs.rutgers.edu. A part of this work was done while the author was at the Massachusetts Institute of Technology. DIMACS is a cooperative project of Rutgers University, Princeton
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-82.ps, 19940706 DIMACS Technical Report 93-82 May 1994 A Geometric Approach for Denoting and Intersecting TR Subgroups of the Euclidean Group by Yanxi Liu1 1Supported in part by DIMACS DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore. DIMACS is an NSF
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-38.ps, 19940718 DIMACS Technical Report 94-38 July 1994 Distributed Scheduling Algorithms to Improve the Performance of Parallel Data Transfers1 by Dannie Durand;2 Ravi Jain3 Bellcore 445 South Street Morristown, New Jersey 07960 David Tseytlin4 1Presented at Workshop on I/O in Parallel Computer Systems at the
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-40.ps, 19940726 Dominating Sets in Planar Graphs1 Lesley R. Matheson2 Robert E. Tarjan2;3 May, 1994
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-42.ps, 19940808 DIMACS Technical Report 94-42 August 1994 Essential and Redundant Rules in Horn Knowledge Basesa by Peter L. Hammer;b and Alexander Koganb;c aThe authors gratefully acknowledge the partial support of AFOSR (Grant F49620-93-1-0041) and ONR (Grants N00014-92-J1375 and N00014-92-J4083). bRUTCOR, Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-44A.ps, 19940823 DIMACS Workshop Interconnection Networks and Mapping and Scheduling Parallel Computations ADDRESS LIST OF PARTICIPANTS February 7-9, 1994 DIMACS Rutgers University Piscataway, New Jersey 08903 (1) Dharma P. Agrawal Department of Electrical & Computer Engineering North Carolina State University Raleigh,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-45.ps, 19940923 11 A. Shamir. IP = PSPACE, J. ACM, 39 (1992), pp. 86977. 10 6 Acknowledgements We thank Sampath Kannan, Noam Nisan, and Ronitt Rubinfeld for early discussions about the relationship between self-correction and random-self-reducibility. The third author wishes to thank his advisor Alan
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-47.ps, 19940927 Weighted search in the plane Richa Agarwala and David Fern andez-Bacay
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-46.ps, 19940927 DIMACS Technical Report 94-46 September 1994 Computing the Medial Axis Transform in Parallel with O(1) scan operations by Afonso Ferreira1;2 CNRS - LIP ENS Lyon { 69364 Lyon C edex 07 France St ephane Ub eda3 TSI Universit e Jean-Monnet Saint Etienne France 1Visiting Member, partially supported by
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-49.ps, 19941020 DIMACS Technical Report 94-49 October 1994 Issues in parallel computing with hypercube multiprocessors by Afonso Ferreira1;2;3 CNRS - LIP CNRS-URA nffi 1398 ENS Lyon { 69364 Lyon C edex 07 France ferreira@lip.ens-lyon.fr 1Visiting Member, partially supported by Dimacs NSF grant STC{91{199999 and the NJ
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-50.ps, 19941103 DIMACS Technical Report 94-50 November 1994 Restricted consensus method and quadratic implicates of pure Horn functions. by Ond<=rej <=Cepek 1 ;2 RUTCOR Rutgers University P.O.Box 5062 New Brunswick, New Jersey 08903 email : cepek@rutcor.rutgers.edu 1Affiliated Graduate Student Member 2This work was
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-51.ps, 19941115 Fast and Simple Algorithms for Perfect Phylogeny and Triangulating Colored Graphs Richa Agarwala and David Fern andez-Bacay
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-51Cover.ps, 19941115 DIMACS Technical Report 94-51 November 1994 Fast and Simple Algorithms for Perfect Phylogeny and Triangulating Colored Graphs by Richa Agarwala1 and David Fern andez-Baca;2 1DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), Rutgers University, Piscataway, NJ 08855
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-52.ps, 19941207 DIMACS Technical Report 94-52 December 1994 Constructing Piecewise Linear Homeomorphisms by Diane L. Souvaine1;2 Rutgers University New Brunswick, New Jersey 08903 dls@cs.rutgers.edu Rephael Wenger3 Ohio State University Columbus, OH 43210, U.S.A. wenger@cis.ohio-state.edu 1Permanent Member 2Supported
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-47R.ps, 19941214 Weighted search in the plane Richa Agarwala and David Fern andez-Bacay
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-56.ps, 19941220 DIMACS Technical Report 94-56 December 1994 A Linear-Time Algorithm for Network Decomposition by Lenore J. Cowen1 ;2 Department of Mathematical Sciences Johns Hopkins University Baltimore, MD 21218 1DIMACS postdoctoral visitor, 1994. 2Visit supported by an NSF Postdoctoral Fellowship. DIMACS is a
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-55.ps, 19950105 DIMACS Technical Report 94-55 December 1994 Lines, line-point incidences and crossing families in dense sets1 by Pavel Valtr Department of Applied Mathematics, Charles University, Malostransk e n am. 25, 118 00 Praha 1, Czech Republic e-mail: valtr@kam.ms.mff.cuni.cz and Graduiertenkolleg
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-22.ps, 19950109 DIMACS Technical Report 94-22 January 1995 by Larry Shafer 1 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 8903 William Steiger 2;3 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08544 1 Research Supported in Part by a Research Experiences for
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-13.ps, 19950131 Combinatorial Bases in Systems of Simplices and Chambers Tatiana V. Alekseyevskaya Rutgers University Center for Mathematics, Science, and Computer Education SERC Building, Room 239 Busch Campus, Piscataway New Jersey 08855-1179 USA Email: tanyagel@.math.rutgers.edu May 12, 1994 1
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-03.ps, 19950306 DIMACS Technical Report 95{03 Parallel Best-First Branch-and-Bound in Discrete Optimization: a Framework1 by Ricardo Corr^ea2 LMC { IMAG 46, av. F elix Viallet, 38031 Grenoble Cedex, France Ricardo.Correa@imag.fr Afonso Ferreira3 CNRS { LIP { ENS-Lyon 46, all ee d'Italie, 69364 Lyon Cedex 07, France
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-01.ps, 19950309 DIMACS Technical Report 95-01 January 1995 Analysis of approximate algorithms for constrained and unconstrained edge-coloring of bipartite graphs by Ravi Jain1;2;3 Applied Research Bellcore John Werth Dept of Computer Sciences Univ. of Texas at Austin 1Permanent Member 2Part of this research was
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-02R.ps, 19950320 DIMACS Technical Report 95-02R March 1995 An Exact duality Theory for Semidefinite Programming and its Complexity Implications by Motakuri Ramana1 Center for Applied Optimization 303 Weil Hall, Dept. of ISE University of Florida Gainesville, FL 32611 1This work was partly conducted while the author was
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-05.ps, 19950328 DIMACS Technical Report 95-05 March 1995 FINDING CUTS IN THE TSP (A preliminary report) by David Applegate1 AT&T Bell Laboratories Murray Hill, New Jersey 07974 Robert Bixby2 Dept. of Comp. & Applied Math. Rice University Houston, Texas 77005 Va<=sek Chv atal3 Dept. of Computer Science Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-07.ps, 19950417 DIMACS Technical Report 95-7 April 1995 Directed Rectangle-Visibility Graphs have Unbounded Dimension by Kathleen Romanik1 DIMACS Center for Discrete Mathematics and Theoretical Computer Science Rutgers, The State University of New Jersey P.O. Box 1179, Piscataway, NJ 08855-1179
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-08.ps, 19950418 DIMACS Technical Report 95-08 April 1995 Optimization under Ordinal Scales: When is a Greedy Solution Optimal by Aleksandar Peke<=c1;2 Deptartment of Mathematics Rutgers University New Brunswick, New Jersey 08903 1Affiliated Graduate Student Member, DIMACS Graduate Assistant 2The author gratefully
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-09.ps, 19950419 DIMACS Technical Report 95-09 April 1995 Computationally Manageable Combinatorial Auctions1 by Michael H. Rothkopf;2 School of Business and Rutgers Center for Operations Research Rutgers University Aleksandar Peke<=c3 Department of Mathematics Rutgers University Ronald M. Harstad Faculty of Management
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-06.ps, 19950421 DIMACS Technical Report 95-6 April 1995 Relation between Protein Structure, Sequence Homology and Composition of Amino Acids by Eddy N. Mayoraz1 RUTCOR{Rutgers University's Center for Operations Research, P.O. Box 5062, New Brunswick, NJ 08903-5062 Inna Dubchak2 Department of Chemistry, University of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-10.ps, 19950421 DIMACS Technical Report 95-10 April 1995 A Winning Strategy for the Ramsey Graph Game by Aleksandar Peke<=c1;2 Department of Mathematics Rutgers University New Brunswick, New Jersey 08903 1Affiliated Graduate Student Member, DIMACS Graduate Assistant 2The author gratefully acknowledges the support of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-04.ps, 19950501 12 J. Shavlik, G. Towell, and M. Noordewier. Using artificial neural networks to refine existing biological knowledge. International Journal of Human Genome Research, 1:81107, 1992. R. Staden. Computer methods to locate signals in nucleic acid sequences. Nucleic Acids Research,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-12.ps, 19950530 DIMACS Technical Report 95-12 May 1995 Equivalence between sorting and priority queues (extended abstract) by Mikkel Thorup1 Dept. of Computer Science University of Copenhagen Universitetsparken 1 2100 Kbh. O Denmark mthorup@diku.dk 1DIMACS Visitor, Summer 1995 DIMACS is a cooperative project of Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-13.ps, 19950601 DIMACS Technical Report 95-13 May 1995 APPROXIMATE MINIMUM-COST MULTICOMMODITY FLOWS IN ~O(" 2KNM) TIME2;3 by Michael D. Grigoriadis1 and Leonid G. Khachiyan1 Department of Computer Science Hill Center { Busch Rutgers University New Brunswick, NJ 08903 1 Permanent Member 2 Research supported by NSF
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-11.ps, 19950605 DIMACS Technical Report 95-11 May 1995 Airdisks and AirRAID: Modeling and scheduling periodic wireless data broadcast (Extended Abstract)1 by Ravi Jain;2;3 Applied Research Bellcore John Werth Dept of Computer Sciences Univ. of Texas at Austin 1An earlier version of this paper was accepted for
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-16.ps, 19950612 DIMACS Technical Report 95-16 June 1995 Bipartite Steinhaus Graphs by Bhaskar DasGupta1 2 Martin F urer3 ;4 1DIMACS Rutgers University Piscataway, NJ 08855 Email: bhaskar@dimacs.rutgers.edu 2Research supported in part by NSF grant CCR-92-00270 3Department of Computer Science & Engineering The
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-15.ps, 19950614 DIMACS Technical Report 95-15 June 1995 LINK: A Combinatorics and Graph Theory Workbench for Applications and Research by Jon Berry1, Nathaniel Dean;2, Patricia Fasel;3, Mark Goldberg4, Elizabeth Johnson;5, John MacCuish;6, Gregory Shannon;7, and Steven Skiena;8 1DIMACS (berryj@dimacs.rutgers.edu) 2AT&T
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-17.ps, 19950619 DIMACS Technical Report 95-17 June 1995 Sample Complexity for Learning Recurrent Perceptron Mappings by Bhaskar Dasgupta ;y Eduardo D. Sontag z;x DIMACS Rutgers University New Brunswick, NJ 08903 bhaskar@dimacs.rutgers.edu yThis research was supported in part by US Air Force Grant AFOSR-94-0293
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-14.ps, 19950623 DIMACS Technical Report 95-14 June 1995 RESOLUTION SEARCH by Va<=sek Chv atal1 Dept. of Computer Science Rutgers University New Brumswick, New Jersey 08903 1Permanent Member. Supported by ONR grant N00014{92{J{1375 DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-21.ps, 19950706 DIMACS Technical Report 95-21 July 1995 A Game-Theoretic Classification of Interactive Complexity Classes by Joan Feigenbaum1 AT&T Bell Labs, Room 2C-473 600 Mountain Avenue Murray Hill, NJ 07974 jf@research.att.com Daphne Koller2 UC Berkeley Computer Science Division Berkeley, CA 94720
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-22.ps, 19950706 DIMACS Technical Report 95-22 July 1995 The Use of Coding Theory in Computational Complexity by Joan Feigenbaum1 AT&T Bell Labs, Room 2C-473 600 Mountain Avenue Murray Hill, NJ 07974 jf@research.att.com 1Permanent Member of DIMACS DIMACS is a cooperative project of Rutgers University, Princeton
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-23.ps, 19950713 DIMACS Technical Report 94-23 July 1995 Rook Placements and Cellular Decomposition of Partition Varieties by Kequan Ding1;2 DIMACS, Rutgers University New Brunswick, New Jersey 08903 Institute for Advanced Study Princeton, NJ 08540 1Partially supported by NSF Grant STC 91-19999, and New Jersey
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-25.ps, 19950713 DIMACS Technical Report 94-25 July 1995 On Garsia-Remmel Problem of Rook Equivalence by Kequan Ding1;2 DIMACS, Rutgers University, New Brunswick, New Jersey 08903 Institute for Advanced Study, Princeton, NJ 08540 Paul Terwilliger3 Department of Mathematics, University of Wisconsin, Madison, WI 53706
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-24.ps, 19950713 DIMACS Technical Report 94-24 July 1995 Rook Placements and Generalized Partition Varieties by Kequan Ding1;2 DIMACS, Rutgers University, New Brunswick, New Jersey 08903 Institute for Advanced Study, Princeton, NJ 08540 1Partially supported by NSF Grant STC 91-19999, and New Jersey Commission on Science
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-23.ps, 19950721 DIMACS Technical Report 95-23 July 1995 Balanced Graphs and Network Flows by Stephen G. Penrice1 Dept. of Mathematics S.U.N.Y. College at Cortland Cortland, New York 13045 1Received Support as a DIMACS Research/Education Postdoctoral Fellow from Aug. 1, 1994 to July 31, 1995. DIMACS is a cooperative
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-24.ps, 19950724 DIMACS Technical Report 95-24 July 1995 Clique-like Dominating Sets by Stephen G. Penrice1 Dept. of Mathematics S.U.N.Y. College at Cortland Cortland, New York 13045 1Received Support as a DIMACS Research/Education Postdoctoral Fellow from Aug. 1, 1994 to July 31, 1995. DIMACS is a cooperative project
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-25.ps, 19950724 DIMACS Technical Report 95-25 July 1995 Coloring with Defects by Lenore J. Cowen1 Dept. of Math. Sciences Johns Hopkins University Baltimore, MD 21218 C. Esther Jesurum2 Applied Math & Lab for CS Massachusetts Institute of Technology Cambridge, MA 02139 1DIMACS postdoctoral visitor, 1994. Visit
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-26.ps, 19950724 DIMACS Technical Report 95-26 July 1995 Defective Coloring of Toroidal Graphs and Graphs of Bounded Genus by Lenore J. Cowen1 Dept. of Math. Sciences Johns Hopkins University Baltimore, MD 21218 Wayne D. Goddard 2 Dept. of Computer Science University of Natal, Durban 4000, South Africa. 1DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-29.ps, 19950725 DIMACS Technical Report 95-29 July 1995 Some New Graph Labeling Problems: A Preliminary Report by Stephen G. Penrice1 Dept. of Mathematics S.U.N.Y. College at Cortland Cortland, New York 13045 1Received Support as a DIMACS Research/Education Postdoctoral Fellow from Aug. 1, 1994 to July 31, 1995. DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-27.ps, 19950726 DIMACS Technical Report 95-27 July 1995 A Formal Framework for Evaluating Heuristic Programs 1 by Lenore Cowen2 Joan Feigenbaum3 Sampath Kannan4 1Most of this work first appeared in an AT&T Bell Laboratories Technical Memorandum on December 1, 1994. 2DIMACS postdoctoral visitor, 1994. Visit supported by
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-31.ps, 19950807 DIMACS Technical Report 95-31 August 1995 Improved construction of negation-limited circuits by Robert Beals1 ;2 ;3 1DIMACS Postdoc 2School of Mathematics Institute For Advanced Study Olden Lane Princeton, New Jersey, 08540 3Research supported by: NSF Mathematical Sciences Posdoctoral Fellowship,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-35.ps, 19950807 DIMACS Technical Report 95-35 August 1995 Constructive Training Methods for Feedforward Neural Networks with Binary Weights by Eddy Mayoraz1 RUTCOR{Rutgers University's Center for Operations Research, P.O. Box 5062, New Brunswick, NJ 08903-5062, mayoraz@rutcor.rutgers.edu Fr ed eric Aviolat Operations
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-34.ps, 19950807 DIMACS Technical Report 95-34 August 1995 Path Optimization for Graph Partitioning Problems by Jonathan W. Berry 1 DIMACS Center Mark K. Goldberg 2 Department of Computer Science Rensselaer Polytechnic Institute 1this author did most of his work for this paper as a PhD student in the Department of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-30.ps, 19950807 DIMACS Technical Report 95-30 August 1995 Algorithms for matrix groups and the Tits alternative by Robert Beals1 ;2 ;3 1DIMACS Postdoc 2School of Mathematics Institute For Advanced Study Olden Lane Princeton, New Jersey, 08540 3Research supported by: NSF Mathematical Sciences Posdoctoral Fellowship,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-32.ps, 19950808 DIMACS Technical Report 95-32 August 1995 Multiplicative equations over commuting matrices by L aszl o Babai1, Robert Beals;2 ;3 ;4, Jin-yi Cai;5, G abor Ivanyos;6, Eugene M. Luks;7 1Department of Computer Science, University of Chicago, Chicago, Illinois 60637 and E otv os University, Budapest, Hungary
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-33.ps, 19950808 9 Mal'cev, A. J. (1958), Homomorphisms onto finite groups, Ivanov. Gos. Ped. Inst. U<=cen. Zap. Vol 18, 49-60. Segal, Daniel (1983). Polycyclic Groups. Cambridge, England: Cambridge University Press. Sims, Charles C. (1994). Computation with finitely presented groups. Cambridge,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-28.ps, 19950809 DIMACS Technical Report 95-28 August 1995 A Biologically Meaningful Model for Comparing Molecular Phylogenies 1 by Boris Mirkin;2 DIMACS Rutgers University P.O.Box 1179 Piscataway NJ 08855-1179 and CEMI of Russian Academy of the Sciences, Moscow, Russia Ilya Muchnik3 RUTCOR, Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-36.ps, 19950809 DIMACS Technical Report 95-36 August 1995 Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles) by Vineet Bafna1 DIMACS Center Rutgers University Piscataway, NJ08855 Babu Narayanan 2 DIMACS Center Rutgers University Piscataway, NJ08854 R. Ravi3 DIMACS Princeton
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-42.ps, 19950905 DIMACS Technical Report 95-42 September 1995 Geometric Probing and Testing - A Survey by Kathleen Romanik1 DIMACS Center for Discrete Mathematics and Theoretical Computer Science Rutgers University P.O. Box 1179, Piscataway, NJ 08855-1179 romanik@dimacs.rutgers.edu 1DIMACS University-Industry Research
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-40.ps, 19950918 DIMACS Technical Report 95-40 August 1995 Localizing a Robot with Minimum Travel1 by Gregory Dudek;2 Research Centre for Intelligent Machines and School of Computer Science McGill University, Montr eal, Qu ebec, Canada H3A 2A7 dudek@cim.mcgill.ca Kathleen Romanik3;4 DIMACS Center for Discrete
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-46.ps, 19950919 DIMACS Technical Report 95-46 September 1995 On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) by Richa Agarwala1 DIMACS Vineet Bafna2 DIMACS Martin Farach3. Rutgers University Babu Narayanan4 DIMACS Mike Paterson5 University of Warwick Mikkel Thorup6 University of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-45.ps, 19950921 DIMACS Technical Report 95-45 September 1995 On Point Covers Of Multiple Intervals And Axis-parallel Rectangles by Gyula K arolyi1 DIMACS Center Rutgers University Piscataway, NJ 08854 karolyi@dimacs.rutgers.edu and G abor Tardos2 Mathematical Institute of the Hungarian Academy of Sciences Pf. 127,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-43.ps, 19950926 DIMACS Technical Report 95-43 September 1995 Steiner Minimal Trees in Simple Polygons by Pawel Winter1 Dept. of Computer Science University of Copenhagen Universitetsparken 1 DK-2100 Copenhagen O Denmark 1This research was completed during a visit at DIMACS and RUTCOR, Rutgers Univ., New Brunswick, NJ,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-44.ps, 19951002 12 B.Korte, L. Lov asz and R. Schrader, Greedoids, Springer (1991). G.N. Lance, and W.T. Williams (1967) A general theory of classificatory sorting strategies: 1. Hierarchical Systems, Comp. Journal 9, 373-380. V. Levit (1995) Oracle-defined quasi-convex set functions are exponentially
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-41.ps, 19951010 DIMACS Technical Report 95-41 A semidefinite bound for mixing rates of Markov chains by Nabil Kahale Computer Science Division, University of California, Berkeley, CA 94720. This work was partly done while the author was at the Massachusetts Institute of Technology, at the Institute for Mathematics and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-47cover.ps, 19951019 DIMACS Technical Report 95-47 May 31, 1995 Higher Dimensional Representations of Graphs by Andreas Buja AT&T Bell Laboratories Murray Hill, New Jersey 07974 Nathaniel Dean1 AT&T Bell Laboratories Murray Hill, New Jersey 07974 Michael L. Littman Dept. of Computer Science Brown University Providence, RI
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-47.ps, 19951019 DIMACS Technical Report 95-47 May 31, 1995 Higher Dimensional Representations of Graphs by Andreas Buja AT&T Bell Laboratories Murray Hill, New Jersey 07974 Nathaniel Dean1 AT&T Bell Laboratories Murray Hill, New Jersey 07974 Michael L. Littman Dept. of Computer Science Brown University Providence, RI
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-49.ps, 19951026 DIMACS Technical Report 95-49 October 1995 Ramsey{Type Results for Geometric Graphs by Gyula K arolyi 1 ;2 Institute for Advanced Study Princeton J anos Pach 3 City College, CUNY and Courant Institute, NYU G eza T oth Courant Institute, NYU 1 DIMACS Postdoctoral Fellow. 2 Supported by NSF grant
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-48.ps, 19951026 DIMACS Technical Report 95-48 October 1995 Proceedings of Phylogeny Workshop held at Princeton University February 6 - 8, 1995 Host: Simon Tavar e University of Southern California DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore. DIMACS is
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-52.ps, 19951213 DIMACS Technical Report 95-52 October 1995 In the random graph G(n; p); p = n a: if has probability O(n ") for every " > then it has probability O(e n" ) for some " > Saharon Shelah Institute of Mathematics The Hebrew University Jerusalem, Israel Rutgers University Department of Mathematics New
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-51.ps, 19951213 DIMACS Technical Report 95-51 October 1995 Finite Canonization Saharon Shelah Institute of Mathematics The Hebrew University Jerusalem, Israel Rutgers University Department of Mathematics New Brunswick, NJ 08903, USA DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-50.ps, 19951213 DIMACS Technical Report 95-50 October 1995 Zero one laws for graphs with edge probabilities decaying with distance by Saharon Shelah1 ;2 Institute of Mathematics, TheHebrew University of Jerusalem, Jerusalem 91904, Israel and Department of Mathematics, Rutgers University, New Brunswick NJ 08903, USA
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-53.ps, 19951213 DIMACS Technical Report 95-53 October 1995 Very weak zero one law for random graphs with order and random binary functions by Saharon Shelah1;2 Institute of Mathematics, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel and Department of Mathematics, Rutgers University, New Brunswick, NJ
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-54.ps, 19960116 DIMACS Technical Report 95-54 December 1995 On a Metric Generalization of Ramsey's Theorem by Paul Erd}os1, Andr as Hajnal2 and J anos Pach1;3 1Mathematical Institute of the Hungarian Academy of Sciences, Budapest. Partially supported by OTKA-4269. 2DIMACS, Rutgers University, Piscataway, NJ. Partially
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-55.ps, 19960116 DIMACS Technical Report 95-55 December 1995 Asymptotically Good Covers in Hypergraphs Extended Abstract of the Dissertation by P. Mark Kayll1;2 Department of Mathematical Sciences The University of Montana Missoula, Montana 59812-1032 kayll@charlo.math.umt.edu 1Author was a DIMACS affiliated graduate
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-56.ps, 19960118 DIMACS Technical Report 95-56 December 1995 Relational expressive power of local generic queries by Oleg V. Belegradek Department of Mathematics Kemerovo State University Kemerovo, Russia 650000 beleg@kaskad.kemerovo.su Alexei P. Stolboushkin1 Department of Mathematics UCLA Los Angeles, CA 90024-1555
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-01.ps.gz, 19960131 DIMACS Technical Report 96-01 January 1996 On Order-Generic Queries by Oleg V. Belegradek Department of Mathematics Kemerovo State University Kemerovo, Russia 650043 beleg@kaskad.kemerovo.su Alexei P. Stolboushkin1 Department of Mathematics UCLA Los Angeles, CA 90024-1555 aps@math.ucla.edu Michael A.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-02.ps.gz, 19960205 2 be converted to a stream-cipher via one of the usual block-chaining methods). We use the public-key encryption algorithm as a keyed hash function in a variation on the 3-round LubyRackoff block cipher construction . (This simplest version of the cipher is secure against known plaintext attacks
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-03.ps.gz, 19960207 DIMACS Technical Report 96-03 February 1996 Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds by Eric Allender1;2 Dept. of Computer Science Rutgers University Piscataway, NJ 08855-1179 allender@cs.rutgers.edu Jia Jiao3;4 Dept. of Computer Science Rutgers University Piscataway,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-06.ps.gz, 19960208 DIMACS Technical Report 96{06 Purely Functional Representations of Catenable Sorted Lists. by Haim Kaplan1 ;2 Robert E. Tarjan3;4 1Affiliated Graduate Student Member 2Department of Computer Science, Princeton University, Princeton, NJ 08544 USA. Research supported by by the NSF, Grant No. CCR-8920505,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-41.ps, 19960212 Contents 1 Executive Summary 2 2 Introduction: DIMACS Mission and Goals 4 2.1 Overview of Research Activity . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Overview of Education and Knowledge Transfer . . . . . . . . . . . . . . . . . 6 3 Project Summary 7 4 Research 8 4.1 Research
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-60b.ps, 19960222 14 Clearly, any division of a 2-sided area by a single X-dipath with end-vertices in @X divides the area into two 2-sided areas. Consider any area Y in X=D which is incident with @X. Thus @Y @X
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-04.ps.gz, 19960227 DIMACS Technical Report 96-04 February 1996 An Isomorphism Theorem for Circuit Complexity by Manindra Agrawal1 Institut f ur Informatik Oberer Eselsberg D 89069 Ulm Germany manindra@informatik.uni-ulm.de Eric Allender2;3 Dept. of Computer Science Rutgers University P.O. Box 1179 Piscataway, NJ
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-05.ps.gz, 19960227 DIMACS Technical Report 96-05 February 1996 Subpolytopes of Cyclic Polytopes by Tibor Bisztriczky1 Department of Mathematics University of Calgary Calgary, Alta. T2N 1N4 Canada tbisztri@math.ucalgary.ca and Gyula K arolyi2;3 School of Mathematics Institute for Advanced Study Princeton, NJ 08540 U.S.A.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-07.ps.gz, 19960409 DIMACS Technical Report 96-07 March 1996 An algorithm for finding many disjoint monochromatic edges in a complete 2-colored geometric graph by Gyula K arolyi1 ;2 Institute for Advanced Study J anos Pach3 City College, CUNY G abor Tardos4 University of Toronto G eza T oth5 Courant Institute, NYU 1DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-10.ps.gz, 19960409 DIMACS Technical Report 96- Szemer edi's Regularity Lemma and its applications in graph theory by J anos Koml os Mikl os Simonovits Rutgers University Hungarian Academy of Sciences DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore. DIMACS is
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-44.ps, 19960418 DIMACS Technical Report Workshop on Interconnection Networks and Mapping and Scheduling Parallel Computations February 7-9, 1994 DIMACS Rutgers University Piscataway, New Jersey 08903 USA Copyright c 1994 DIMACS is the National Science Foundation science and technology center for discrete mathematics
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-08.ps.gz, 19960513 DIMACS Technical Report 96-08 May 1996
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-09.ps.gz, 19960513 DIMACS Technical Report 96-09 April 1996 Continuous Characterizations of the Maximum Clique Problem by Luana E. Gibbons Donald W. Hearn1 Panos M. Pardalos Motakuri V. Ramana Center for Applied Optimization Dept of Industrial and Systems Engineering University of Florida, Gainesville, FL 32611 1Support
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/PolicyPapers/gw.ps, 19960528 Theory of Computing: A Scientific Perspective1 (preliminary version) Oded Goldreich2 Avi Wigderson3 May 22, 1996 1Available from URL http://theory.lcs.mit.edu/ oded/toc-sp.html 2Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel. E-mail:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/PolicyPapers/ahonsf.ps, 19960528 Theory of Computing: Goals and Directions Alfred V. Aho Columbia University David S. Johnson AT & T Richard M. Karp (Chair) University of Washington S. Rao Kosaraju Johns Hopkins University Catherine C. McGeoch Amherst Colloge Christos H. Papadimitriou University of California at Berkeley Pavel Pevzner
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-11.ps.gz, 19960628 dvitps ERROR: techrpt.dvi @ dimacs.rutgers.edu Certain fonts that you requested in your dvi file could not be found on the system. In order to print your document, other fonts that are installed were substituted for these missing fonts. Below is a list of the substitutions that were made.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-18.ps.gz, 19960701 DIMACS Technical Report 96-18 June 1996 On the Complexity of Semidefinite Programs by Lorant Porkolab1;2 RUTCOR Rutgers University New Brunswick, New Jersey 08903-5062 porkolab@rutcor.rutgers.edu and Leonid Khachiyan3;4 Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-16.ps.gz, 19960701 DIMACS Technical Report 96-16 June, 1996 On Coherence, Random-Self-Reducibility, and Self-Correction by Joan Feigenbaum1 AT&T Research 600 Mountain Avenue Murray Hill, NJ 07974 jf@research.att.com Lance Fortnow2 Computer Science Department University of Chicago Chicago, IL 60637 fortnow@cs.uchicago.edu
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-21.ps.gz, 19960708 DIMACS Technical Report 96-21 July 1996 Verification of Fair Transition Systems1 by Orna Kupferman Bell Laboratories 600 Mountain Avenue Murray Hill NJ 07974, U.S.A. Email: ok@research.att.com Moshe Y. Vardi Department of Computer Science Rice University Houston TX 77251-1892, U.S.A. Email:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-23.ps.gz, 19960708 DIMACS Technical Report 96-23 July 1996 Integer NC1 is equal to Boolean NC1 by Stephen Bloch 1 Math/Computer Science Dept. Adelphi University Garden City, NY 11415 1Visiting Researcher at DIMACS DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-13.ps.gz, 19960708 DIMACS Technical Report 96-13 July 1996 Independent Spanning Trees with Small Stretch Factors by Fred Annexstein Department of ECECS University of Cincinnati Cincinnati, OH 45221 fred.annexstein@uc.edu Ken Berman Department of ECECS University of Cincinnati Cincinnati, OH 45221 ken.berman@uc.edu Ram
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-19.ps.gz, 19960708 DIMACS Technical Report 96-19 July 1996 The number of nucleotide sites needed to accurately reconstruct large evolutionary trees1 by Mike Steel Biomathematics Research Centre, University of Canterbury Christchurch, New Zealand L aszl o A. Sz ekely Department of Computer Science, E otv os University 1088
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-24.ps.gz, 19960708 DIMACS Technical Report 96-24 July 1996 Elimination of Constants from Machines over Algebraically Closed Fields by Pascal Koiran1 LIP, Ecole Normale Sup erieure de Lyon { CNRS 46 all ee d'Italie, 69364 Lyon Cedex 07 France email: koiran@lip.ens-lyon.fr DIMACS is a partnership of Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-20.ps.gz, 19960708 DIMACS Technical Report 96-20 July 1996 Asymptotics of the total chromatic number for simple graphs by P. Mark Kayll1 Department of Mathematical Sciences The University of Montana Missoula, MT 59812-1032 kayll@charlo.math.umt.edu 1Author was an unofficial DIMACS visitor during the preliminary stages of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-12.ps.gz, 19960715 DIMACS Technical Report 96-12 July 1996 k-Weak Orders: Recognition and a Tolerance Result by Ann N. Trenk1 Department of Mathematics Wellesley College Wellesley, MA 02181 USA DIMACS is a partnership of Rutgers University, Princeton University, AT&T Research, Bellcore, and Bell Laboratories. DIMACS is an
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-25.ps.gz, 19960715 DIMACS Technical Report 96-25 July 1996 Closed-form Analytic Maps in One and Two Dimensions Can Simulate Turing Machines by Pascal Koiran1 Ecole Normale Sup erieure de Lyon koiran@lip.ens-lyon.fr Cristopher Moore Santa Fe Institute moore@santafe.edu DIMACS is a partnership of Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-22.ps.gz, 19960717 DIMACS Technical Report 96{22 July 1996 A Correctness Proof for Pipelining in RISC Architectures by E: B orger and S: Mazzanti Dipartimento di Informatica Corso Italia, 40 56125 Pisa, Italy boerger, mazzanti@di.unipi.it Fax +39(0)50-887226, Tel.-887230 DIMACS is a cooperative project of Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-14.ps.gz, 19960717 DIMACS Technical Report 96-14 July 1996 Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations by Mikkel Thorup1 Department of Computer Science, University of Copenhagen Universitetsparken 1, DK-2100 Copenhagen East, Denmark mthorup@diku.dk,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-27.ps.gz, 19960730 DIMACS Technical Report 96-27 July 1996 Hilbert's Nullstellensatz is in the Polynomial Hierarchy by Pascal Koiran1 LIP, Ecole Normale Sup erieure de Lyon { CNRS 46 all ee d'Italie, 69364 Lyon Cedex 07 France email: koiran@lip.ens-lyon.fr DIMACS is a partnership of Rutgers University, Princeton
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-29.ps.gz, 19960731 DIMACS Technical Report 96-29 July 1996 Constant Ratio Approximations of Feedback Vertex Sets in Weighted Undirected Graphs 1 by Vineet Bafna;2;3 (bafna@dimacs.rutgers.edu) DIMACS Center, Piscataway, NJ 08855 USA Piotr Berman (berman@cse.psu.edu) Dept. of Computer Science and Engineering The
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-31.ps.gz, 19960731 DIMACS Technical Report 96-31 July 1996 Packing of induced stars in a graph by Alexander K. Kelmans1 RUTCOR, Rutgers University New Brunswick, New Jersey 08903 and Department of Mathematics University of Puerto Rico P.O. Box 23355 San Juan, PR 00931{3355 DIMACS is a partnership of Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-30.ps.gz, 19960731 DIMACS Technical Report 96-30 July 1996 Computing similarity between RNA strings 1 by V. Bafna;2 DIMACS Center P.O. Box 1179 Piscataway, NJ 08855 bafna@dimacs.rutgers.edu S. Muthukrishnan Dept. of Computer Science Univ. of Warwick Coventry, CV47AL, UK muthu@dcs.warwick.ac.uk R. Ravi Graduate School of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-33.ps.gz, 19960805 DIMACS Technical Report 96-33 August 1996 Stable Families of Coalitions and Normal Hypergraphs1 by E. Boros RUTCOR Rutgers University, P.O.Box 5062 New Brunswick, NJ 08903 (boros@rutcor.rutgers.edu) V. Gurvich2 DIMACS & RUTCOR Rutgers University, P.O.Box 5062 New Brunswick, NJ 08903
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-34.ps.gz, 19960805 DIMACS Technical Report 96-34 August 1996 Stable Effectivity Functions and Perfect Graphs 1 by E. Boros RUTCOR Rutgers University, P.O.Box 5062 New Brunswick, NJ 08903 (boros@rutcor.rutgers.edu) V. Gurvich2 DIMACS & RUTCOR Rutgers University, P.O.Box 5062 New Brunswick, NJ 08903
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-32.ps.gz, 19960805 DIMACS Technical Report 96-32 August 1996 A Circular Graph - Counterexample to the Duchet Kernel Conjecture by A. Apartsin Product Computer Ltd. Haifa, 35709, Israel E. Ferapontova Technion - Israel Institute of Technology, Dep. of Math. Haifa, 32000, Israel V. Gurvich1 DIMACS & RUTCOR Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-35.ps.gz, 19960805 DIMACS Technical Report 96-35 August 1996 Dual Graphs on Surfaces1 by V. Gurvich2 DIMACS & RUTCOR Rutgers University, P.O.Box 5062 New Brunswick, NJ 08903 (gurvich@rutcor.rutgers.edu) DIMACS is a partnership of Rutgers University, Princeton University, AT&T Research, Bellcore, and Bell Laboratories.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-37.ps, 19960813 DIMACS Technical Report 95-37 September 1995 Improved Approximation Guarantees for Packing and Covering Integer Programs1 by Aravind Srinivasan2;3 Department of Information Systems and Computer Science National University of Singapore Lower Kent Ridge Road Singapore 119260 Republic of Singapore DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-26.ps.gz, 19960814 DIMACS Technical Report 96-26 Explicit OR-Dispersers with Polylogarithmic Degree1 by Michael Saks;2 Aravind Srinivasan;3 Shiyu Zhou;4 1The first and third authors were supported in part by NSF grant CCR-9215293. The second author was supported in part by grant 93-6-6 of the Alfred P. Sloan Foundation to
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-36.ps.gz, 19960814 DIMACS Technical Report 96-36 August 1996 Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times by E. G. Coffman, Jr. Bell Laboratories Lucent Technologies Murray Hill, NJ 07974 Nabil Kahale AT&T Research Laboratories Murray Hill, NJ 07974 F. T. Leighton Dept. of Math. and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-28.ps.gz, 19960909 DIMACS Technical Report 96-28 September 1996 Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy by Denis Th erien1 School of Computer Science, McGill University 3480 University Montr eal, Qu ebec H3A 2A7, Canada denis@opus.cs.mcgill.ca Thomas Wilke2 DIMACS,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-37.ps.gz, 19960909 DIMACS Technical Report 96-37 September 1996 Superpolynomial Lower Bounds for Monotone Span Programs1 by L aszl o Babai2 Anna G al3 Avi Wigderson4 DIMACS is a partnership of Rutgers University, Princeton University, AT&T Research, Bellcore, and Bell Laboratories. DIMACS is an NSF Science and Technology
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-38.ps.gz, 19960911 DIMACS Technical Report 96-38 September 1996 How good are branching rules in DPLL by Ming Ouyang Department of Computer Science Rutgers University New Brunswick, New Jersey 08903 DIMACS is a partnership of Rutgers University, Princeton University, AT&T Research, Bellcore, and Bell Laboratories. DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-41.ps.gz, 19960913 DIMACS Technical Report 96-41 September 1996 A corrected version of the Duchet Kernel Conjecture1 by E. Boros RUTCOR Rutgers University, P.O. Box 5062 New Brunswick, NJ 08903 (boros@rutcor.rutgers.edu) V. Gurvich DIMACS & RUTCOR Rutgers University, P.O. Box 5062 New Brunswick, NJ 08903
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-40.ps.gz, 19960916 DIMACS Technical Report 96-40 September 1996 Sparse Hard Sets for P by Dieter van Melkebeek1 Department of Computer Science The University of Chicago Chicago, IL 60637 Mitsunori Ogihara Department of Computer Science University of Rochester Rochester, NY 14627 1Visitor supported by a DIMACS Graduate
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-39.ps.gz, 19960916 DIMACS Technical Report 96-39 September 1996 Deterministic and Randomized Bounded Truth-table Reductions of P, NL, and L to Sparse Sets by Dieter van Melkebeek1;2 Department of Computer Science The University of Chicago Chicago, IL 60637 1Visitor supported by a DIMACS Graduate Study Fellowship. 2Most of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-43.ps.gz, 19960924 DIMACS Technical Report 96-43 September 1996 Local quartet splits of a binary tree infer all quartet splits via one dyadic inference rule1 by P eter L. Erd}os Mathematical Institute of the Hungarian Academy of Sciences Budapest P.O.Box 127, Hungary-1364 E-mail: elp@math-inst.hu Michael A. Steel
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-42.ps.gz, 19960925 DIMACS Technical Report 96-42 September 1996 Numerical study of a non-equilibrium interface model by Balakrishna Subramanian Department of Physics Rutgers University Piscataway, NJ 08855, USA (sbala@physics.rutgers.edu) G.T. Barkema Institute for Advanced Study Olden Lane, Princeton, NJ 08540, USA
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-17.ps.gz, 19961007 DIMACS Technical Report 96-17 October 1996 Decentralized Trust Management by Matt Blaze Joan Feigenbaum1 Jack Lacy AT&T Laboratories Murray Hill, NJ 07974 fmab,jf,lacyg@research.att.com 1Permanent Member of DIMACS DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Labs,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-47.ps.gz, 19961022 DIMACS Technical Report 96-47 October 1996 On independent domination number of graphs with given minimum degree by N. I. Glebov1 Institute of Mathematics 630090 Novosibirsk, Russia A. V. Kostochka2 Institute of Mathematics 630090 Novosibirsk, Russia DIMACS is a partnership of Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-48.ps.gz, 19961029 DIMACS Technical Report 96-48 October 1996 Optimal Suffix Tree Construction with Large Alphabets by Martin Farach1;2 Rutgers University 1Permanent Member 2Department of Computer Science, Rutgers University, Piscataway, NJ 08855, USA. (farach@cs.rutgers.edu, http://www.cs.rutgers.edu/ farach). Supported
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-50.ps.gz, 19961107 DIMACS Technical Report 96-50 November 1996 Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited. by Stephen J. Bellantoni1 1Much of this work was done while the author was visiting the University of Toronto Department of Computer Science and DIMACS (Center for Discrete Mathematics and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-18r.ps.gz, 19961107 DIMACS Technical Report 96-18 June 1996 Revised: October 1996 On the Complexity of Semidefinite Programs by Lorant Porkolab1;2 RUTCOR Rutgers University New Brunswick, New Jersey 08903-5062 porkolab@rutcor.rutgers.edu and Leonid Khachiyan3;4 Dept. of Computer Science Rutgers University New Brunswick,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-49.ps.gz, 19961107 DIMACS Technical Report 96-49 November 1996 Ranking Arithmetic Proofs by Implicit Ramification1 by Stephen J. Bellantoni 1Much of this work was carried out while the author was a visiting researcher at DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science. DIMACS is a partnership
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-33.ps, 19961112 DIMACS Technical Report 94-33 November 1994 Optimal Space Distributed Order-Preserving Lists1 by Michael Saks Department of Mathematics Rutgers University New Brunswick, NJ 08903 Fotios Zaharoglou Department of Computer Science and Engineering University of California San Diego La Jolla, California
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-45.ps.gz, 19961125 DIMACS Technical Report 96-45 A Lower Bound for Randomized Algebraic Decision Trees by Dima Grigoriev 1 Marek Karpinski 2 Friedhelm Meyer auf der Heide 3 Roman Smolensky 4 1Dept. of Computer Science and Mathematics, Penn State University, University Park. Research partially supported by NSF Grant
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-44.ps.gz, 19961125 DIMACS Technical Report 96-44 Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks by Marek Karpinski 1 Dept. of Computer Science University of Bonn 53117 Bonn Angus Macintyre 2 Mathematical Institute University of Oxford Oxford OX1 3LB DIMACS is a partnership of Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-46.ps.gz, 19961125 DIMACS Technical Report 96-46 On the Power of Randomized Branching Programs by Farid Ablayev 1 Marek Karpinski 2 1Dept. of Computer Science, University of Bonn. Visiting from University of Kazan. Research partially supported by the Volkswagen-Stiftung and the Basic Research Grant 96-01-01962 Email:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-15.ps.gz, 19961202 DIMACS Technical Report 96-15 June, 1996 Workshop Summary: Computational and Complexity Issues in Automated Verification by Robert Brayton EECS Department University of California Berkeley, CA 94720 brayton@ic.eecs.berkeley.edu Allen Emerson Computer Science Department University of Texas Austin, TX
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-51.ps.gz, 19961206 DIMACS Technical Report 96-51 December 1996 Signi cantly Lower Entropy Estimates for Natural DNA Sequences by David M. Loewenstern 1 Department of Computer Science Rutgers University New Brunswick, New Jersey 8903 Email: loewenst@paul.rutgers.edu Peter N. Yianilos NEC Research Institute, 4 Independence
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-52.ps.gz, 19961206 DIMACS Technical Report 96-52 December 1996 Randomized (n 2 ) Lower Bound for Knapsack by Dima Grigoriev 1 Marek Karpinski 2 1Dept. of Computer Science and Mathematics, Penn State University, University Park. Research partially supported by NSF Grant CCR-9424358. Email: dima@cse.psu.edu 2Dept. of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-54.ps.gz, 19961216 DIMACS Technical Report 96-54 December 1996 Correctness of Constructing Optimal Alphabetic Trees Revisited by Marek Karpinski 1 Lawrence L. Larmore 2 Wojciech Rytter ;3 1Dept. of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley. Research
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-56.ps.gz, 19961219 DIMACS Technical Report 96-56 December 1996 Vapnik-Chervonenkis Dimension of Recurrent Neural Networks by Pascal Koiran Laboratoire de l'Informatique du Parall elisme Ecole Normale Sup erieure de Lyon { CNRS 46 all ee d'Italie, 69364 Lyon Cedex 07 France koiran@lip.ens-lyon.fr Eduardo D. Sontagy
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-55.ps.gz, 19961219 DIMACS Technical Report 96-55 On galleries with no bad points1 by Pavel Valtr;2 DIMACS Center, Rutgers University P.O.Box 1179, Piscataway, NJ 08855, U.S.A. e-mail: valtr@dimacs.rutgers.edu Department of Applied Mathematics, Charles University Malostransk e n am. 25, 118 00 Praha 1, Czech Republic
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-53.ps.gz, 19970103 DIMACS Technical Report 96-53 January 1997 On the Design of Optimization Criteria for Multiple Sequence Alignment by Dannie Durand1;2 Computational Biology Group University of Pennsylvania Philadelphia, PA 19104-6228 and DIMACS Rutgers University Piscataway, NJ 08855-1179 durand@saul.cis.upenn.edu
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-01.ps.gz, 19970117 DIMACS Technical Report 97-01 Improved Algorithms via Approximations of Probability Distributions1 by Suresh Chari;2 Dept. of Computer Science Cornell University Ithaca, NY 14853, USA Pankaj Rohatgi3 IBM T. J. Watson Research Center Hawthorne, NY 10532, USA Aravind Srinivasan4 ;5 Dept. of Information
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-04.ps.gz, 19970205 DIMACS Technical Report 97-04 February 1997 On a Global Optimization Problem in the Study of Information Discrepancy 1 by Weiwu FANG DIMACS Center, Rutgers University IAM-CAS and APORC2 1This work has been partially supported by Chinese National Science Foundation under Grant 79370082 2IAM-CAS:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-03.ps.gz, 19970205 DIMACS Technical Report 97-03 February 1997 Trees and Ehrenfeucht-Fra ss e games by Stevo Todor<=cevi c1 Department of Mathematics University of Toronto Toronto, Canada Jouko V a an anen 2 Department of Mathematics University of Helsinki Helsinki, Finland 1Partially supported by grants from SFS and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-60.ps.gz, 19970207 DIMACS Technical Report 96-60 DIMACS SPECIAL YEAR IN MATHEMATICAL SUPPORT FOR MOLECULAR BIOLOGY ANNUAL REPORT JANUARY 1996 DIMACS is a partnership of Rutgers University, Princeton University, AT&T Research, Bellcore, and Bell Laboratories. DIMACS is an NSF Science and Technology Center, funded under
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-06.ps.gz, 19970210 ERDOS AND R ENYI CONJECTURE Saharon Shelah Institute of Mathematics The Hebrew University Jerusalem, Israel Rutgers University Department of Mathematics New Brunswick, NJ USA
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-59.ps.gz, 19970211 DIMACS Technical Report 96-59 December 1996 Approximating Dense Cases of Covering Problems by Marek Karpinski1 Alexander Zelikovsky2 1Dept. of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley. Research partially done while visiting Dept. of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-02.ps.gz, 19970213 DIMACS Technical Report 97-02 January 1997 Demand Routing and Slotting on Ring Networks by Tamra J. Carpenter1 Bellcore 445 South Street Morristown, New Jersey 07960 Steven Cosares Dept. of Mathematics Dowling College Oakdale, New York 11769 Iraj Saniee2 Bellcore 445 South Street Morristown, New Jersey
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-47file.ps, 19970218 Higher Dimensional Representations of Graphs Andreas Buja and Nathaniel Dean AT&T Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974 Michael L. Littman Dept. of Computer Science Brown University Providence, RI 02912 Deborah Swayne Bellcore 445 South Street Morristown, NJ 07960-1910 May 31, 1995
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-57.ps.gz, 19970224 DIMACS Technical Report 96-57 February 1997 On the Size of Set Systems on Not Containing Weak (r; )-Systems by Vojt<=ech R odl1 Department of Mathematics and Computer Science Emory University Atlanta, Georgia 30322 Lubo<=s Thoma 2 DIMACS, Rutgers University P.O.Box 1179 Piscataway, NJ 08855 - 1179
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-58.ps.gz, 19970224 DIMACS Technical Report 97-58 February 1997 On Perfect Matchings and Hamiltonian Cycles in Sums of Random Trees by Alan Frieze1 Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA15213 Micha l Karo nski2 Department of Mathematics and Computer Science Emory University, Atlanta,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-05.ps.gz, 19970225 DIMACS Technical Report 97-05 February 1997 On Linear Ordering of Strongly Extensional Finitely-Branching Graphs and Non-Well-Founded Sets 1 by Alexei Lisitsa2;3 Vladimir Sazonov4;5 1A version of this paper is submitted to the conference LFCS'97. 2Permanent Member: Program Systems Institute of Russian
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-61.ps.gz, 19970227 D I M A C S Center for Discrete Mathematics and Theoretical Computer Science ANNUAL REPORT - December 1996 DIMACS Center ffl Rutgers University ffl P.O. Box 1179 ffl Piscataway, NJ 08855-1179 ffl USA TEL: 908-445-5928 ffl FAX: 908-445-5932 ffl EMAIL: center@dimacs.rutgers.edu WWW:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-08.ps.gz, 19970307 DIMACS Technical Report 97-08 March 1997 Shock Profiles for the Partially Asymmetric Simple Exclusion Process by B. Derrida Laboratoire de Physique Statistique Ecole Normale Sup erieure 24 rue Lhomond, 75005 Paris, France email derrida@lps.ens.fr J. L. Lebowitz 1 E. R. Speer 1 Institut des Hautes Etudes
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-09.ps.gz, 19970314 DIMACS Technical Report 97-09 March 1997 Phase Transitions in the Multicomponent Widom{Rowlinson Model and in Hard Cubes on the BCC{Lattice by P. Nielaba Institut f ur Physik Universit at Mainz. D-55099 Mainz, Germany J.L. Lebowitz1 I.H.E.S. 35, Route de Chartres F-91440 Bures{Sur{Yvette, France
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-07.ps.gz, 19970315 DIMACS Technical Report 97-07 March 1997 On geometric graphs with no k pairwise parallel edges1 by Pavel Valtr2 DIMACS Center, Rutgers University P.O.Box 1179, Piscataway, NJ 08855, U.S.A. e-mail: valtr@dimacs.rutgers.edu Department of Applied Mathematics, Charles University Malostransk e n am. 25, 118
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-11.ps.gz, 19970321 DIMACS Technical Report 97-11 March 1997 On the density of subgraphs in a graph with bounded independence number1 by Pavel Valtr2 DIMACS Center, Rutgers University P.O.Box 1179, Piscataway, NJ 08855, U.S.A. e-mail: valtr@dimacs.rutgers.edu Department of Applied Mathematics, Charles University
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-12.ps.gz, 19970402 DIMACS Technical Report 97-12 April 1997 Threshold of Broadcast in Random Graphs by Hui Chen 1 DIMACS 2 Rutgers University Piscataway, NJ 08855 email: chenhui@dimacs.rutgers.edu 1The work of the author is supported by DIMACS through NSF grant. Part of the work was done when the author was at Carnegie
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-13.ps.gz, 19970407 DIMACS Technical Report 97-13 April 1997 Ramsey{Type Results for Geometric Graphs. II by Gyula K arolyi1 E otv os University, Budapest and ETH Z urich J anos Pach2 City College, CUNY and Courant Institute, NYU G eza T oth3 Courant Institute, NYU Pavel Valtr4 ;5 DIMACS Center, Rutgers University and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-10.ps.gz, 19970409 DIMACS Technical Report 97-10 April 1997 Optimal Byzantine Quorum Systems by Dahlia Malkhi AT&T Labs { Research, Murray Hill, NJ 07974 dalia@research.att.com Michael Reiter AT&T Labs { Research, Murray Hill, NJ 07974 reiter@research.att.com Avishai Wool1 Bell Laboratories, Lucent Technologies, Murray
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-14.ps.gz, 19970415 DIMACS Technical Report 97-14 April 1997 Computing Integral Points in Convex Semi-algebraic Sets1 by Leonid Khachiyan2 Department of Computer Science Rutgers University New Brunswick, New Jersey 08903 leonid@cs.rutgers.edu and Lorant Porkolab3 RUTCOR Rutgers University New Brunswick, New Jersey
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-15.ps.gz, 19970416 DIMACS Technical Report 97-15 April 1997 Crowds: Anonymity for Web Transactions (Preliminary Announcement) by Michael K. Reiter1 Aviel D. Rubin;2 AT&T Labs\|Research, Murray Hill, New Jersey, USA freiter,rubing@research.att.com 1Permanent Member 2Permanent Member DIMACS is a partnership of Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-16.ps.gz, 19970424 DIMACS Technical Report 97-16 April 1997 Optimization algorithms for separable functions with tree-like adjacency of variables and their application to the analysis of massive data sets by Ilya Muchnik DIMACS, Rutgers University P.O. Box 5062, New Brunswick, NJ 08903-5062, USA muchnik@dimacs.rutgers.edu
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-17.ps.gz, 19970506 Constructing Big Trees from Short Sequences P eter L. Erd}os Michael A. Steel L aszl o A. Sz ekely and Tandy J. Warnow 1 Mathematical Institute of the Hungarian Academy of Sciences. E-mail: elp@math-inst.hu 2 Biomathematics Research Centre, University of Canterbury. E-mail: m.steel@math.canterbury.ac.nz
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-18.ps.gz, 19970512 DIMACS Technical Report 97-18 May 1997 On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees1 by Bhaskar DasGupta;2;3 Xin He4 Tao Jiang5 Ming Li6 John Tromp7 1The results reported here have also appeared in Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, pp. 427-436,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-19.ps.gz, 19970522 DIMACS Technical Report 97-19 May 1997 Asymptotics of the total chromatic number for multigraphs by P. Mark Kayll Department of Mathematical Sciences The University of Montana Missoula, MT 59812-1032, USA kayll@charlo.math.umt.edu This note is a companion to DIMACS Technical Report 96-20. DIMACS is a
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-20.ps.gz, 19970529 Choiceless Polynomial Time Andreas Blass, Yuri Gurevich and Saharon Shelah
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-21.ps.gz, 19970609 DIMACS Technical Report 97-21 June 1997 Bounded Hyperset Theory and Web-like Data Bases 1 by Alexei Lisitsa2;3 Vladimir Sazonov4;5 1This paper is accompanying to DIMACS TR-97-05. To be presented in Kurt G odel Colloquium", Vienna, 25{29 August, 1997, and in the Workshop Logic and Algorithms\|One Year
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-22.ps.gz, 19970611 DIMACS Technical Report 97-22 June 1997 Graph drawings with no k pairwise crossing edges1 by Pavel Valtr2 DIMACS Center, Rutgers University P.O.Box 1179, Piscataway, NJ 08855, U.S.A. e-mail: valtr@dimacs.rutgers.edu Department of Applied Mathematics, Charles University Malostransk e n am. 25, 118 00
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-15vs1.ps.gz, 19970619 DIMACS Technical Report 97-15 April 1997 (Revised June 1997) Crowds: Anonymity for Web Transactions by Michael K. Reiter1 Aviel D. Rubin2 AT&T Labs\|Research, Murray Hill, New Jersey, USA freiter,rubing@research.att.com 1Permanent Member 2Permanent Member DIMACS is a partnership of Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-29.ps.gz, 19970702 DIMACS Technical Report 97-29 July 1997 The Chromatic Numbers of Random Hypergraphs by Michael Krivelevich 1 Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel. Email: krivelev@math.tau.ac.il. Benny Sudakov 2 Department of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-25.ps.gz, 19970703 DIMACS Technical Report 97-25 July 1997 Linear Hashing by Noga Alon 1 ;2 Martin Dietzfelbinger 3 ;4 Peter Bro Miltersen 5 ;6 Erez Petrank7 ;8 ;9 G abor Tardos 10 ;11 1Dept. of Math., Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel and Institute for Advanced Study, Princeton, NJ
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-27.ps.gz, 19970703 DIMACS Technical Report 97-27 July 1997 Probabilistically Checkable Proofs with Zero Knowledge by Joe Kilian 1;2 Erez Petrank 3 ;4 ;5 G abor Tardos 6 1Permanemt Member 2NEC Research Institute. E-mail: joe@research.nj.nec.com 3DIMACS post-doctoral fellow 4DIMACS Center, P.O.Box 1179, Piscataway, NJ
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-28.ps.gz, 19970703 DIMACS Technical Report 97-28 July 1997 Identity Escrow by Joe Kilian1 NEC Research Institute E-mail: joe@research.nj.nec.com Erez Petrank 2 DIMACS Center, P.O.Box 1179, Piscataway, NJ 08855. Email: erez@dimacs.rutgers.edu. 1Permanent Member 2DIMACS post-doctoral fellow DIMACS is a partnership of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-26.ps.gz, 19970703 DIMACS Technical Report 97-26 July 1997 CBC MAC for Real-Time Data Sources by Erez Petrank 1 DIMACS Center, P. O. Box 1179, Piscataway, NJ 08855-1179. Email: erez@dimacs.rutgers.edu 2 Charles Rackoff Dept. of Computer Science, University of Toronto, Toronto, Ontario, Canada M5B 3g4. Email:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-23.ps.gz, 19970708 DIMACS Technical Report 97-23 June 1997 Extension of Piyavskii's Algorithm to Continuous Global Optimization by Robert J. Vanderbei1;2 Statistics and Operations Research Princeton University Princeton, NJ 08544 E-mail:rvdb@princeton.edu 1Permanent Member 2Research supported by the NSF through grant
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-32.ps.gz, 19970711 DIMACS Technical Report 97-32 July 1997 Learning Boxes in High Dimension1 by Amos Beimel2 DIMACS Center, Rutgers University, P.O. Box 1179, Piscataway, NJ 08855. Eyal Kushilevitz3 Dept. of Computer Science, Technion, Haifa 32000, Israel. 1A preliminary version of this paper appeared in the proceedings
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-31.ps.gz, 19970711 DIMACS Technical Report 97-31 July 1997 Note on the Erd}os-Szekeres theorem by G eza T oth1;2 DIMACS Center, Rutgers University and Courant Institute, NYU e-mail: toth@cims.nyu.edu Pavel Valtr3;4 DIMACS Center, Rutgers University and Charles University, Prague e-mail: valtr@kam.mff.cuni.cz 1Postdoctoral
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-30.ps.gz, 19970712 DIMACS Technical Report 97-30 July 1997 Shock Profiles for the Asymmetric Simple Exclusion Process in One Dimension by B. Derrida 1 J. L. Lebowitz 2;3 E. R. Speer 3 1 Laboratoire de Physique Statistique, Ecole Normale Sup erieure, 24 rue Lhomond, 75005 Paris, France; email derrida@lps.ens.fr. 2
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-34.ps.gz, 19970714 DIMACS Technical Report 97-34 July 1997 Horn Minimization by Iterative Decomposition1 by Endre Boros;2;3 Ond<=rej <=Cepek4 Alexander Kogan5;6 1The authors gratefully acknowledge the partial support by the Office of Naval Research (grants N00014-92-J1375 and N00014-92-J4083). The first author also
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-24.ps.gz, 19970715 DIMACS Technical Report 97-24 June 1997 Symmetrization of Binary Random Variables2 by Abram Kagan University of Maryland, College Park, MD Colin Mallows AT&T Laboratories, Floram Park, NJ Larry Shepp Rutgers University, New Brunswick, NJ1 Robert J. Vanderbei Princeton University, Princeton, NJ1 Yehuda
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-33.ps.gz, 19970717 DIMACS Technical Report 97-33 July 1997 On Local Register Allocation by Martin Farach1;2 Rutgers University and Bell Labs Vincenzo Liberatore3 ;4 Rutgers University 1Permanent Member 2Department of Computer Science, Hill Center, Rutgers University, New Brunswick, NJ 08903 and Information Sciences
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-15new.ps.gz, 19970801 DIMACS Technical Report 97-15 April 1997 (Revised August 1997) Crowds: Anonymity for Web Transactions by Michael K. Reiter1 Aviel D. Rubin2 AT&T Labs\|Research, Murray Hill, New Jersey, USA freiter,rubing@research.att.com 1Permanent Member 2Permanent Member DIMACS is a partnership of Rutgers University,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-38.ps.gz, 19970812 DIMACS Technical Report 97-38 August 1997 A Practical Algorithm for Finding Matrix Representations for Polycyclic Groups by Eddie H. Lo National Security Agency Fort Meade, MD Gretchen Ostheimer Dept. of Mathematics Tufts University Medford, MA 02155 DIMACS is a cooperative project of Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-39.ps.gz, 19970902 DIMACS Technical Report 97-39 September 1997 Chromatic-Index Critical Graphs of Even Order by Stefan Gr unewald B urgermeisterweg 10 32825 Blomberg, Germany Eckhard Steffen1 Program in Applied and Computational Mathematics Fine Hall, Washington Road Princeton University Princeton, New Jersey 08544
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-41.ps.gz, 19970905 DIMACS Technical Report 97-41 August 1997 Reliable Communication over Partially Authenticated Networks1 by Amos Beimel2 Matthew Franklin3 1An extended abstract of this paper will appear in the proceedings of the WDAG '97 conference, 1997. 2DIMACS, Piscataway, NJ. E-mail: beimel@dimacs.rutgers.edu. 3AT&T
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-40.ps.gz, 19970908 DIMACS Technical Report 97-40 September 1997 The complexity of matrix rank and feasible systems of linear equations1 by Eric Allender2;3 Dept. of Computer Science Rutgers University Piscataway, New Jersey 08855 allender@cs.rutgers.edu. Robert Beals4 Department of Mathematics University of Arizona
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-45.ps.gz, 19970909 DIMACS Technical Report 97-45 September 1997 Some Pointed Questions Concerning Asymptotic Lower Bounds1 by Eric Allender2;3 1A version of this paper originally appeared in the Computational Complexity Column in the Bulletin of the EATCS 62, June, 1997, pp. 96{103 2Permanent Member 3Supported in part by
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-50.ps.gz, 19970909 DIMACS Technical Report 97-50 RUSPACE(log n) DSPACE(log2 n= log log n)1 by Eric Allender2;3 Department of Computer Science Rutgers University Piscataway, NJ 08855 USA allender@cs.rutgers.edu Klaus-J orn Lange4 Wilhelm-Schickard Institut f ur Informatik Universit at T ubingen Sand 13 D-72076 T ubingen
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-58.ps.gz, 19970909 DIMACS Technical Report 97-58 September 1997 On Minimally Imperfect Graphs with Circular Symmetry1 by G abor Bacs o;2 Endre Boros3 Vladimir Gurvich4 Fr ed eric Maffray5 Myriam Preissmann6 1The second and third authors gratefully acknowledge the partial support by DIMACS and by the National Science
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-55.ps.gz, 19970909 DIMACS Technical Report 97-55 September 1997 Special Year on Logic and Algorithms Tutorial Notes: Descriptive Complexity (Tutorial Lectures by Neil Immerman) by Eric Allender1 (Editor, SYLA Tutorial Notes) Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903 1Permanent Member
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-56.ps.gz, 19970909 DIMACS Technical Report 97-56 September 1997 Special Year on Logic and Algorithms Tutorial Notes: Random Finite Models (Tutorial Lectures by James Lynch) by Eric Allender1 (Editor, SYLA Tutorial Notes) Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903 1Permanent Member DIMACS
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-46.ps.gz, 19970909 DIMACS Technical Report 97-46 September 1997 Making Nondeterminism Unambiguous1 by Klaus Reinhardt2 Wilhelm-Schickard Institut f ur Informatik Universit at T ubingen Sand 13, D-72076 T ubingen, Germany e-mail: reinhard@informatik.uni-tuebingen.de Eric Allender3;4 Department of Computer Science, Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-54.ps.gz, 19970909 DIMACS Technical Report 97-54 September 1997 Special Year on Logic and Algorithms Tutorial Notes: Expressive Powers of Logics (Tutorial Lectures by Phokion Kolaitis) by Eric Allender1 (Editor, SYLA Tutorial Notes) Dept. of Computer Science Rutgers University New Brunswick, New Jersey 08903 1Permanent
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-49.ps.gz, 19970909 DIMACS Technical Report 97-49 Circuit Complexity before the Dawn of the New Millennium1 by Eric Allender2;3 Department of Computer Science Rutgers University Piscataway, NJ 08855 USA allender@cs.rutgers.edu http://www.cs.rutgers.edu/ allender 1An earlier version of this paper appeared in Proc. 16th
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-57.ps.gz, 19970909 DIMACS Technical Report 97-57 September 1997 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 Eric Allender1 (Editor, SYLA Tutorial Notes) Dept. of Computer
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-47.ps.gz, 19970909 DIMACS Technical Report 97-47 September 1997 Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems1 by Martin Mundhenk 2 Universit at Trier FB IV { Informatik D-54286 Trier, Germany mundhenk@ti.uni-trier.de Judy Goldsmith 3 Dept. of Computer Science University of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-48.ps.gz, 19970909 DIMACS Technical Report 97-48 September 1997 On TC0, AC0, and Arithmetic Circuits1 by Manindra Agrawal2 Department of Computer Science Indian Institute of Technology Kanpur 208016, India manindra@iitk.ernet.in Eric Allender3;4 Department of Computer Science Rutgers University Piscataway, NJ 08855, USA
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-53.ps.gz, 19970909 DIMACS Technical Report 97-53 September 1997 Rectangle Breaking in Grids by Paul A. Dreyer, Jr. 1 Therese C. Biedl 2 1Department of Mathematics, Rutgers University, Hill Center, Busch Campus, New Brunswick, NJ 08903, e-mail: pdreyer@dimacs.rutgers.edu. The author would like to thank the Office of Naval
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-51.ps.gz, 19970909 DIMACS Technical Report 97-51 September 1997 The Permanent Requires Large Uniform Threshold Circuits1 by Eric Allender2;3 Department of Computer Science Rutgers University P.O. Box 1179 Piscataway, NJ 08855-1179 allender@cs.rutgers.edu. 1A preliminary version of this work appeared in Proc. 2nd
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-60.ps.gz, 19970911 DIMACS Technical Report 97-60 Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.1 by Manindra Agrawal2 Department of Computer Science Indian Institute of Technology Kanpur 208016, India manindra@iitk.ernet.in Eric Allender3;4 Department of Computer Science Rutgers University
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-61.ps.gz, 19970912 DIMACS Technical Report 97-61 September 1997 Arithmetic Complexity, Kleene Closure, and Formal Power Series by Eric Allender1;2 Department of Computer Science Rutgers University Hill Center, Busch Campus Piscataway, NJ 08855 allender@cs.rutgers.edu V Arvind The Institute of Mathematical Sciences C.I.T.
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-52.ps.gz, 19970915 DIMACS Technical Report 97-52 September 1997 Pairing Heaps are Sub-optimal by Michael L. Fredman1 Dept. of Computer Science Rutgers University New Brunswick, NJ 08903 1Permanent Member DIMACS is a partnership of Rutgers University, Princeton University, AT&T Labs, Bellcore, and Bell Labs. DIMACS is an
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-36.ps.gz, 19970917 DIMACS Technical Report 97-36 August 1997 FDOD Function and the Information Discrepancy Contained in Multiple Probability Distributions 1 by Weiwu Fang2 DIMACS Center, Rutgers University IAM-CAS and APORC 1This work has been supported by DIMACS Center, the Chinese NSF under the grant 79370082, and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-59.ps.gz, 19970917 DIMACS Technical Report 97-59 September 1997 Chromatic Index Critical Graphs of Orders 11 and 12 by Gunnar Brinkmann Fakult at f ur Mathematik Postfach 100131 33501 Bielefeld, Germany Eckhard Steffen1 Program in Applied and Computational Mathematics Fine Hall, Washington Road Princeton University
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-35.ps.gz, 19970919 DIMACS Technical Report 97-35 September 1997 On the Limit Values of Probabilities for the First Order Properties of Graphs by Joel Spencer Courant Institute New York University 251 Mercer St. New York NY 10012 Lubo<=s Thoma1 DIMACS, P.O. Box 1179 Rutgers University Piscataway, NJ 08855 1The second
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-64.ps.gz, 19970919 DIMACS Technical Report 97-64 September 1997 The Design and Implementation of a Java Playground by Dahlia Malkhi Michael Reiter Avi Rubin AT&T Labs\|Research, Florham Park, New Jersey, USA fdalia,reiter,rubing@research.att.com DIMACS is a partnership of Rutgers University, Princeton University, AT&T
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-44.ps.gz, 19970924 DIMACS Technical Report 97-44 September 1997 Practical Algorithms for Polycyclic Matrix Groups by Gretchen Ostheimer Dept. of Mathematics Tufts University Medford, MA 02155 DIMACS is a partnership of Rutgers University, Princeton University, AT&T Labs, Bellcore, and Bell Labs. DIMACS is an NSF Science
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-37.ps.gz, 19971007 DIMACS Technical Report 97-37 October 1997 Primal-Dual Affine-Scaling Algorithms Fail For Semidefinite Programming by Masakazu Muramatsu1 Sophia University 7-1 Kioi-cho, Chiyoda-ku, Tokyo, 102 Japan Robert J. Vanderbei2 ;3 Princeton University Princeton, NJ 08544 1This work was done while the author was
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-63.ps.gz, 19971012 DIMACS Technical Report 97-63 October 1997 A Short Course in Computational Molecular Biology1 by D. Durand2 Computational Biology Group, University of Pennsylvania DIMACS, Rutgers University durandd@dimacs.rutgers.edu, http://www.cs.princeton.edu/ durand M. Farach3 Department of Computer Science Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-65.ps.gz, 19971014 DIMACS Technical Report 97-65 October 1997 Longest Common Consecutive Substring in two Random Strings (Preliminary Version) by Sarmad Abbasi1 Dept. of Computer Science Rutgers University Piscataway, New Jersey 08855 email: sabbasi@paul.rutgers.edu 1This work was done while the author was supported by
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-66.ps.gz, 19971015 DIMACS Technical Report 97-66 October 1997 A generalization of the Erd}os-Szekeres theorem to disjoint convex sets by J anos Pach1 Courant Institute, NYU and Hungarian Academy of Sciences G eza T oth2 DIMACS Center, Rutgers University and Hungarian Academy of Sciences 1Supported by NSF grant
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-67.ps.gz, 19971015 DIMACS Technical Report 97-67 October 1997 Linear Programming in Tomography, Probability, and Finance A contribution to the Second Conference on Discrete Tomography Szeged, August, 1997 by Larry Shepp1 Rutgers University, New Brunswick, New Jersey 1Permanent Member DIMACS is a partnership of Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-69.ps.gz, 19971017 DIMACS Technical Report 97-69 October 1997 Uniform Multipaging Reduces to Paging by Vincenzo Liberatore1;2 Department of Computer Science, Hill Center, Rutgers University, New Brunswick, NJ 08903. E-mail: liberato@cs.rutgers.edu. URL: http://www.cs.rutgers.edu/ liberato/. 1Affiliated Graduate Student
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-68.ps.gz, 19971017 DIMACS Technical Report 97-68 October 1997 A Modest Proposal for Preventing Internet Congestion by Andrew Odlyzko AT&T Labs - Research amo@research.att.com DIMACS is a partnership of Rutgers University, Princeton University, AT&T Labs, Bellcore, and Bell Labs. DIMACS is an NSF Science and Technology
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-71.ps.gz, 19971028 DIMACS Technical Report 97-71 October 1997 A few logs suffice to build (almost) all trees (I) by P eter L. Erd}os Mathematical Institute of the Hungarian Academy of Sciences Budapest P.O.Box 127, Hungary-1364 E-mail: elp@math-inst.hu Michael A. Steel Biomathematics Research Centre University of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-70.ps.gz, 19971028 DIMACS Technical Report 97-70 October 1997 The Maximum of a Random Walk and Its Application to Rectangle Packing by E. G. Coffman1 Jr., Philippe Flajolet2;4 Leopold Flatto1 Micha Hofri3;5 1Bell Labs, Lucent Technologies, 700 Mountain Ave., Murray Hill, NJ 07974. 2INRIA Rocquencourt, F-78153 Le Chesney,
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-72.ps.gz, 19971028 DIMACS Technical Report 97-72 October 1997 A few logs suffice to build (almost) all trees (II) by P eter L. Erd}os Mathematical Institute of the Hungarian Academy of Sciences Budapest P.O.Box 127, Hungary-1364 E-mail: elp@math-inst.hu Michael A. Steel Biomathematics Research Centre University of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-73.ps.gz, 19971031 DIMACS Technical Report 97-73 October 1997 Three-dimensional grid drawings of graphs by J anos Pach1 Courant Institute, NYU and Hungarian Academy of Sciences Torsten Thiele2 Courant Institute, NYU and FU Berlin G eza T oth3 Courant Institute, NYU and DIMACS Center, Rutgers University 1Supported by NSF
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-75.ps.gz, 19971114 DIMACS Technical Report 97-75 November 1997 On Automorphism Groups of Graphs and Distributive Lattices by Stephan Foldes RUTCOR Rutgers University New Brunswick, NJ 08903 sfoldes@rutcor.rutgers.edu DIMACS is a partnership of Rutgers University, Princeton University, AT&T LabsResearch, Bell Labs and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-62.ps.gz, 19971126 DIMACS Technical Report 97-62 November 1997 Graph Homomorphisms and Phase Transitions by Graham R. Brightwell 1 London School of Economics and Political Science Houghton St. London WC2A 2AE England Peter Winkler2 Bell Laboratories 2C-379 Lucent Technologies 700 Mountain Ave. 1Author's net address:
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-76.ps.gz, 19971126 DIMACS Technical Report 97-76 November 1997 Cyclically 5-edge connected non-bicritical critical snarks by Stefan Gr unewald B urgermeisterweg 10 32825 Blomberg, Germany Eckhard Steffen1 Program in Applied and Computational Mathematics Fine Hall, Washington Road Princeton University Princeton, New Jersey
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-78.ps.gz, 19971204 DIMACS Technical Report 97-78 December 1997 Remarks on the equivalence problem for PL-sets by Bhaskar DasGupta1;2 Department of Computer Science Rutgers University Camden, NJ 08102 Email: bhaskar@crab.rutgers.edu 1Visitor, DIMACS Center 2This result is part of an ongoing research with Prof. Eduardo
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-77.ps.gz, 19971208 DIMACS Technical Report 97-77 December 1997 Some Results Concerning the Ends of Minimal Cuts of Simple Graphs by Ning Jia P.O. Box 9441, Fudan University Shanghai, 200433 P.R.China Xiaofeng Jia Mathematics Department Shanxi Mining Institute Taiyuan, Shanxi P.R.China, 030024 DIMACS is a partnership of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-81.ps.gz, 19971214 DIMACS Technical Report 97-81 December 1997 On Arithmetic Branching Programs by Amos Beimel1 Anna G al2 1Division of Engineering and Applied Sciences, Harvard University, ESL, 40 Oxford st., Cambridge, MA 02138. Email: beimel@deas.harvard.edu. Supported by grants ONR-M00014-96-1-0550 and
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-74.ps.gz, 19971216 DIMACS Technical Report 97-74 Upper semi-lattice of binary strings with the relation x is simple conditional to y" by Andrei Muchnik Institute of New Technologies, 10 Nizhnyaya Radischewskaya Moscow, Russia 109004 e-mail: amuchnik@int.glasnet.ru Andrei Romashchenko Nikolai Vereshagin1 Dept. of
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-82.ps.gz, 19971219 DIMACS Technical Report 97-82 December 1997 Diagnosing Double Regular Systems by Endre Boros1;2 RUTCOR Rutgers University New Brunswick, New Jersey Tongu c Unl uyurt3;4 RUTCOR Rutgers University New Brunswick, New Jersey 1Permanent Member 2This research was partially supported by the ONR (Grants
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-79.ps.gz, 19971230 DIMACS Technical Report 97-79 December 1997 Equational Theories of Boolean Functions by Oya Ekin1;2;3 Stephan Foldes 4 ;5 ;6 Peter L. Hammer7 ;8 ;9 Lisa Hellerstein10;11 1Affiliated Student Member 2Partially supported by ONR (grants N0001492J1375 and N0001492J4083) and DIMACS. 3Address: RUTCOR, Rutgers
	ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-80.ps.gz, 19980115 DIMACS Technical Report 97-80 January 1998 DIMACS Research and Education Institute (DREI '97) Cryptography and Network Security July 28 - August 15, 1997 Abstracts of Talks Presented by Joan Feigenbaum Research Program Director AT&T Labs - Research DIMACS is a partnership of Rutgers University,