Warren D. Smith's Works

NECI, Princeton NJ

The list is in chronological order, so if you're interested in recent work, start at the end! Other lists on my webpage give journal articles, but I recommend this list since it is a superset with hyperlinks to the electronic papers.

Numbers 1-60 were NEC Research Institute Technical Reports during 1991-2001 but continue beyond. I also intend to link comments, referee reports, updates, errata, etc.

    • TITLE: Inverse of the Square Wave Matrix
    • ps file (6 pages); (pdf);
    • AUTHORS:
      • David J. Grabiner, Harvard
      • Warren D.Smith
      • Sushanta Srivastava, AT&T
    • DATE: 06/10/91

    • TITLE: A Characterization of Inscribable Polyhedra; Resolution of a Question of J. Steiner
    • abstract; get TeX file;
    • AUTHORS:
      • Igor Rivin, NECI
      • Warren D.Smith
    • DATE: 06/20/91

    • TITLE: Taking the Fuzz Out of Fuzzy Logic
    • nofuzz.ps (4 pages);
    • AUTHORS:
      • Warren D. Smith
    • DATE: 07/24/91

    • TITLE: Combinatorial Structure of Delaunay Triangulations of the Plane (Extended Abstract)
    • abstract;
    • AUTHORS:
      • Michael B. Dillencourt, University of Calif. at Irvine
      • Igor Rivin, NEC
      • Warren D.Smith
    • DATE: 11/06/91

    • TITLE: 4-connected Planar Graphs are Inscribable
    • abstract;
    • AUTHORS:
      • Michael B. Dillencourt, University of Calif. at Irvine
      • Warren D. Smith
    • DATE: 12/10/91

    • TITLE: Accurate Circle Configurations and Numerical Conformal Mapping in Polynomial Time
    • abstract; braegger.ps (7 pages)
    • AUTHORS:
      • Warren D.Smith
    • DATE: 12/30/91

    • TITLE: Best Play for Imperfect Players and Game Tree Search - (with pseudocode appendix by C. Garrett.)
    • bpip1.ps (41 pages).)
    • AUTHORS:
      • Eric Baum, NECI
      • Warren D. Smith
    • DATE: 10/05/92

    • TITLE: Two disproofs of the Gilbert-Pollak Steiner ratio conjecture in $d$-space for $d \ge 3$ (Now coauthored with D-Z. Du and titled ``Three disproofs'':
    • short description; dugp3.ps (8 pages)
    • AUTHORS:
      • Warren D. Smith
    • DATE: 10/13/92

    • TITLE: On the Steiner Ratio in 3-space
    • abstract; Get the ps file (15 pages)
    • AUTHORS:
      • Warren D.Smith
      • J. MacGregor Smith, Univ. Mass.. at Amherst
    • DATE: 12/01/92 It turns out that the "sausage" point set we discuss in this paper was invented previously; [H.S.M.Coxeter: The simplicial helix and the equation tan Ntheta = N tan theta, Canad. Math. Bull. 28,4 (1985) 385-393] ascribes it to Buckminster Fuller and says it could have architectural applications as a "strong and attractive pillar." These people had no idea of its properties relating to Steiner trees.

    • TITLE: Graph-Theoretical Conditions for Inscribability and Delaunay Realizability
    • abstract; Get the ps file (15 pages)
    • AUTHORS:
      • M. B. Dillencourt, Univ. of California at Irvine
      • W. D. Smith
    • DATE: 12/23/92

    • TITLE: Approximation of Staircases by Staircases
    • AUTHORS:
      • W. D. Smith
    • DATE: 12/31/92

    • TITLE: A Simple Method for Resolving Degeneracies in Delaunay Triangulations
    • abstract; Get the ps file (12 pages)
    • AUTHORS:
      • M. B. Dillencourt, Info & CS Dept., U. California at Irvine
      • W. D. Smith
    • DATE: 01/20/93

    • TITLE: The Uniqueness of the Minimum and Maximum Functions for AND and OR in Fuzzy Logic
    • uniqfuzz.ps (5 pages);
    • AUTHORS:
      • W.D. Smith
      • K.K. Thornber, NECI
    • DATE: 02/26/93

    • TITLE: Shallow Excluded Minors and Improved Graph Decompositions
    • get ps file
    • AUTHORS:
      • S. Plotkin, Stanford University
      • S. Rao, NECI
      • W.D.Smith
    • DATE: 02/28/94

    • TITLE: The drag on a sphere moving through a blackbody radiation bath
    • spheredrag.ps (5 pages)
    • AUTHORS:
      • W. D. Smith
    • DATE: 2/11/95

    • TITLE: An opinionated, but reasonably short, summary of the Mini DIMACS Workshop on DNA based computers, (held at Princeton University on April 4 1995)
    • workshop.summary.ps (4 pages)
    • AUTHORS:
      • W. D. Smith
    • DATE: 04/05/95

    • TITLE: Best Play for Imperfect Players and Game Tree Search - part II, experiments
    • bpip2.ps (39 pages)
    • AUTHORS:
      • Warren D. Smith
      • Eric B. Baum, NECI
      • Charles Garrett, NECI
      • Rico Tudor, Pattern Recognition Systems Inc.
    • DATE: 9/19/95

    • TITLE: Best Play for Imperfect Players and Game Tree Search - part I, theory
    • AUTHORS:
      • Eric B. Baum, NECI
      • Warren D. Smith
    • DATE: 9/25/95

    • TITLE: Computational complexity of synthetic chemistry - Basic facts
    • abstract; ps file (8 pages);
    • AUTHORS:
      • W.D. Smith, NECI
    • DATE: April 18, 1997

    • TITLE: On Carmichael Numbers with 3 Factors and the Strong Pseudoprime Test
    • abstract; carm3.ps (5 pages)
    • AUTHORS:
      • W.D. Smith, NECI
    • DATE: August 13, 1997

    • TITLE: Propagating Distributions Up Directed Acyclic Graphs
    • AUTHORS:
      • Eric B. Baum, NECI
      • Warren D. Smith
    • DATE: 12/22/97

    • TITLE: A lower bound for the simplexity of the N-cube via hyperbolic volumes
    • abstract
    • get ps file
    • AUTHORS:
      • Warren D. Smith
    • DATE: 6/5/98

    • TITLE: Classical reversible computation with zero Lyapunov exponent
    • abstract;
    • ps file (9 pages);
    • AUTHOR: Warren D.Smith
    • DATE: 10/01/98 (revised Feb. 1999)

    • TITLE: Nuclear powered and reactionless rockets
    • abstract;
    • ps file;
    • update;
    • (7 pages);
    • AUTHOR: Warren D.Smith
    • DATE: 02/02/99

    • TITLE: Finding the maximum of a polynomial time computable bounded smooth function on an interval is NP-complete
    • abstract;
    • ps file (2 pages);
    • AUTHOR: Warren D.Smith
    • DATE: 02/05/99

    • TITLE: History of ``Church's theses'' and a manifesto on converting physics into a rigorous algorithmic discipline
    • abstract;
    • ps file (8 pages);
    • AUTHOR: Warren D.Smith
    • DATE: 02/26/99

    • TITLE: The relative volumes of wires and components in a computer
    • abstract;
    • ps file (4 pages);
    • AUTHOR: Warren D.Smith
    • DATE: June 1999

    • TITLE: Argument against quantum computers (or against certain decoherence models)
    • abstract;
    • ps file (4 pages);
    • AUTHOR: Warren D.Smith
    • DATE: 03/28/03

    • TITLE: New lower bounds for the maximal determinant problem
    • This is math.CO/0304410 on the xxx.lanl.gov preprint server. (20 pages.)
    • AUTHORS: William P. Orrick, Bruce Solomon, Roland Dowdeswell, Warren D. Smith
    • DATE: 04/25/03

    • TITLE: Pythagorean triples, rational angles, and space-filling simplices
    • abstract;
    • ps file (17 pages); and pdf;
    • AUTHOR: Warren D.Smith
    • DATE: 12/27/03, revised 01/02/04

    • TITLE: Candidate incentives under different voting systems, and the self-reinforcing deterioration of US democracy
    • abstract;
    • ps file (19 pages); and pdf;
    • AUTHOR: Warren D.Smith
    • DATE: 08/27/04

    • TITLE: Sinkhorn ratings, and new strongly polynomial time algorithms for Sinkhorn balancing, Perron eigenvectors, and Markov chains
    • abstract;
    • ps file (17 pages); and pdf;
    • DATE: June 2005

    • TITLE: Cryptographic election protocols for reweighted range voting & reweighted transferable vote voting
    • abstract;
    • ps file (5 pages); and pdf;
    • DATE: Sept 2005

    • TITLE: Three Voting Protocols: ThreeBallot, VAV, and Twin,
    • AUTHORS: Ronald L. Rivest, Warren D. Smith
    • abstract;
    • pdf updated late June;
    • May also be available on Rivest's page here.
    • DATE: April 2007

    • TITLE: The Best Rank-Order Voting System versus Range Voting (Part I of a 3-part paper)
    • AUTHOR: Warren D. Smith
    • paper in HTML (about 63 pages; how many pages depends on how small you set text font size)
    • DATE: January 2009

    • TITLE: Best Rank-Order Voting Systems versus Range Voting II: N≥4 candidates under the Random Normal Elections Model (RNEM) (Part II of a 3-part paper)
    • AUTHOR: Warren D. Smith
    • paper in HTML (about 18 pages)
    • DATE: January 2009

    • TITLE: Best voting systems in D-dimensional politics models (Part III of a 3-part paper)
    • AUTHOR: Warren D. Smith
    • paper in HTML (about 15 pages)
    • DATE: January 2009

    • TITLE: Utility, social utility, democracy, and altruistic and moral behavior from unexploitability, Darwinian evolution, and tribes
    • AUTHOR: Warren D. Smith
    • paper in HTML (about 7 pages)
    • DATE: February 2009

    • TITLE: Range voting's superiority versus every tie-avoiding monotone majority-top-respecting rank-order(equalities permitted) voting method
    • AUTHOR: Warren D. Smith
    • paper in HTML (about 6 pages)
    • DATE: June 2009