Linear-time nearest point algorithms for Coxeter lattices (2009)
McKilliam, Robby G., Smith, Warren D., Clarkson, I. Vaughan L.
The Coxeter lattices, which we denote $A_{n/m}$, are a family of lattices containing many of the important lattices in low dimensions. This includes $A_n$, $E_7$, $E_8$ and their duals $A_n^*$,...
Warren D. Smith, Gregory B. Williams, Ramon Berguer, John T. Anderson
team projects to provide students with practice in interdisciplinary team problem solving. LabVIEW, with its rapid prototyping and interactive capabilities, provides valuable support for these...
Testing that distributions are close (2008)
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n 2/3 ɛ −4 log n)...
Geometric Separator Theorems & Applications (2007)
Warren D. Smith, Nicholas C. Wormald
We find a large number of "geometric separator theorems" such as: I: Given N disjoint isooriented squares in the plane, there exists a rectangle with 2N=3 squares inside, 2N=3 squares...
Definite integration and summation are P-hard (2007)
Leonid Gurvits, Warren D. Smith
We show that the common symbolic manipulation tasks of computing multiple partial derivatives, definite integration, and definite summation, are #P-hard, i.e., at least as hard as counting the...
Inverse of the Square Wave Matrix (2007)
David Grabiner, Warren D. Smith, Sushanta Srivastava
The N \Theta N matrix A, whose ijth element A i;j , 1 i; j N , is defined by A i;j = (\Gamma1) dj=ie+1 ; is called the "square wave matrix." The ith row of A represents a \Sigma1- valued...
DRAFT WDS's article template (2007)
Abstract | WDS's L A T E X test sample article driving his style le. A lot of T E X stu seems not to work in L A
Notes on reversible computation (2007)
Abstract--- Erasing a bit requires the dissipation of kBT ln 2 worth of energy, if T is the temperature of the heat bath surrounding one's computer and kB 1:381 \Theta 10 \Gamma23 Joules/Kelvin...
Warren D. Smith, Nicholas C. Wormald
Abstract--- We have a 4-step method for producing "separator theorems " about geometrical objects en masse. Examples: I: Given N disjoint iso-oriented squares in the plane, there...
Warren Smith Wds, Range Voting, Warren D. Smith
The \range voting" system is as follows. In a c- candidate election, you select a vector of c real numbers, each of absolute value 1, as your vote. E.g. you could vote (+1; 1; +:3; :9; +1) in a...
Facilitates Interdisciplinary (2007)
Team Projects In, Warren D. Smith, Gregory B. Williams, Ramon Berguer, John T. Anderson
This paper describes our experience with using LabVIEW for these interdisciplinary graduate BME class projects
D. Smith, Just Me, Warren D. Smith
IEVS: Computer simulation and comparison of different election methods
Three Voting Protocols: ThreeBallot, VAV, and Twin (2007)
Ronald L. Rivest, Warren D. Smith
We present three new paper-based voting methods with interesting security properties. Our goal is to achieve the same security properties as recently proposed cryptographic voting protocols, but...
Three Voting Protocols: ThreeBallot, VAV, and Twin (2007)
Ronald L. Rivest, Warren D. Smith
We present three new paper-based voting methods with interesting security properties. Our goal is to achieve the same security properties as recently proposed cryptographic voting protocols, but...
1. AES is weak. 2. Linear time secure cryptography (2007)
The two most famous cryptosystems DES and AES had both been broken by both brute-force (EFF) and linear cryptanalysis (M.Matsui), and by a timing attack (D.J.Bernstein), respectively. We describe a...
The world is on the verge of a dramatic shift in security relations in Northeast Asia. With a rising China and a Japan emerging as a normal military power by revising the pacifist clause of its...
Thesis (M.A. in National Security Affairs)--Naval Postgraduate School, June 2006.
Abstract — Tien D. Kieu, in 10 papers posted to the quant-ph section of the xxx.lanl.gov preprint archive [some of which were also published in printed journals such as Proc. Royal Soc. A 460...
Mathematical definition of “intelligence” (and consequences) (2006)
In §9 we propose an abstract mathematical definition of, and practical way to measure, “intelligence.” Before that is much motivating discussion and arguments why it is a good definition, and...
Smith, Warren D., Naval Postgraduate School (U.S.)
The world is on the verge of a dramatic shift in security relations in Northeast Asia. With a "rising China" and a Japan emerging as a "normal" military power by revising the pacifist clause of its...
New lower bounds for the maximal determinant problem (2003)
Orrick, William P., Solomon, Bruce, Dowdeswell, Roland, Smith, Warren D.
We report new world records for the maximal determinant of an n-by-n matrix with entries +/-1. Using various techniques, we beat existing records for n=22, 23, 27, 29, 31, 33, 34, 35, 39, 45, 47, 53,...
Pythagorean triples, rational angles, and space-filling simplices (2003)
The ancient Greeks posed and solved the problem of finding all right triangles with rational sidelengths. There are 4 natural nonEuclidean generalizations of this problem. We solve them all. The...
Reconstructing sets from interpoint distances (2002)
Paul Lemke, Steven S. Skiena, Warren D. Smith
Which point sets realize a given distance multiset? Interesting cases include the "turnpike problem " where the points lie on a line, the "beltway problem " where...
Voting Schemes Based on Candidate-Orderings Or (2001)
Discrete Choices Considered, Warren D. Smith
We give a family of scenarios in which any voting system in which each voter's vote is based purely on his perceived ordering of the 3 candidates, is entirely helpless { must regard the election...
Testing that distributions are close (2000)
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n
Testing that distributions are close (2000)
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n
Charge Quantization, the Topology of the Universe, and the Hopeful Abolition of Monopoles (2000)
| Why do all electrons have the same charge and why do all protons have exactly the opposite charge? Dirac's attempt to provide an answer led him to propose the existence of magnetic monopoles....
Complexity of Minimization (2000)
An important problem in numerical analysis is trying to minimize (or maximize) a real function F (x1 , x2 , ..., xd ) of d real variables. We investigate (and survey) its computational complexity...
Testing that distributions are close (2000)
Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n 2/3 ɛ −4 log n)...
Alpha-electric and Nuclear-electric rockets (1999)
In an earlier report, I pointed out that a bilayer film, one of whose sides was made of ff-emitting radioactive atoms, would act as a "rocket." A 3-stage alpha rocket could reach, e.g.,...
The Relative Volumes of Wires and Components in a Computer (1999)
In a computer with a fixed number of "components" of fixed sizes and a fixed "wiring diagram," what wire thicknesses will result in maximum performance ? For a model of neurons,...
Criticism of Onsager's reciprocal relations (1999)
Onsager's second kind of "reciprocal relations" state that oe( ~ H) = oe T (\Gamma ~ H) where oe is the 3 \Theta 3 conductance matrix, ~ H is an externally applied magnetic field, and...
Nuclear Powered and Reactionless Rockets (1999)
Warren Smith Wds, Warren D. Smith
We consider using emissions from radioactive atoms as the "exhaust" of a "rocket" for space propulsion. The "alpha rocket" consists of a thin film of alpha emitting...
The energy-time uncertainty principle (1999)
This paper contains a simple but powerful statement and proof of the Energy-Time uncertainty principle.
Church's Thesis Meets Quantum Mechanics (1999)
"Church's thesis" is the notion that any "reasonable physical system" may be "simulated" by a Turing machine. The "strong" Church's thesis adds...
Classical reversible computation with zero Lyapunov exponent (1999)
Lyapunov Exponent, Warren D. Smith
In 1982, Edward Fredkin invented a way to build a time-reversible universal computer using frictionless "billiard balls" rolling on a table top, and in which ball "bounces"...
Church's thesis meets the N-body problem (1999)
THIS IS A REVISION-IN-PROGRESS! NOT QUITE FINAL YET! "Church's thesis" is at the foundation of computer science. It is pointed out that with any particular set of physical laws,...
Plane mechanisms and the "downhill principle" Manuscript (1998)
Abstract--- PRELIMINARY-- comments desirable. We survey and redo the whole mathematical area of "planar mechanisms: " machines made of rigid parts constrained to lie in a plane and...
The Energy-Time Uncertainty Principle (1998)
This paper contains a simple but powerful statement and proof of the Energy-Time uncertainty principle. Keywords --- Energy-Time uncertainty principle. Maximum rate of time evolution. Schrodinger...
Improved Approximation Schemes for Geometrical Graphs Via Spanners and Banyans (1998)
Satish B. Rao, Warren D. Smith
We give deterministic and randomized algorithms to find a Euclidean traveling salesman tour (TST) of length within (1 + 1=s) times optimal. They run in O(N log N) time and O(N) space for constant...
Geometric Separator Theorems (1998)
Warren D. Smith, Nicholas C. Wormald
We have a 4-step method for producing "separator theorems" about geometrical objects en masse. Examples: I: Given N disjoint iso-oriented squares in the plane, there exists a rectangle with...
Taking the Fuzz Out of Fuzzy Logic (1998)
This paper gives an algorithm which, given any boolean function F whose n arguments are known probabilities, will deduce the tightest possible upper and lower bounds (assuming nothing is known about...
Geometric Separator Theorems (1998)
Warren D. Smith, Nicholas C. Wormald
We have a 4-step method for producing "separator theorems" about geometrical objects en masse. Examples: I: Given N disjoint iso-oriented squares in the plane, there exists a rectangle with...
Approximating Geometrical Graphs Via Spanners and Banyans (1998)
Satish B. Rao, Warren D. Smith
The main result of this paper is an improvement of Arora's method to find (1+ ffl) approximations for geometric NP-hard problems including the Euclidean Traveling Salesman Problem and the...
Propagating Distributions Up Directed Acyclic Graphs (1998)
In a previous paper, the authors considered game trees as graphical models. Adopting an evaluation function that returned a probability distribution over values likely to be taken at a given...
A Lower Bound for the Simplexity of the N-Cube via Hyperbolic Volumes (1998)
Warren D. Smith, Warren D. Smith
Let T (n) denote the number of n-simplices in a minimum cardinality decomposition of the n-cube into n-simplices. For n 1 we show that T (n) H(n), where H(n) is the ratio of the hyperbolic volume of...
Applications of Geometric Separator Theorems (1998)
Warren D. Smith, Nicholas C. Wormald
The companion paper "Geometric separator theorems" proved a large number of separator theorems about geometrical objects. We now find geometric separator theorems about geometrical graphs,...
Definite integration and summation are #P-hard (1998)
Leonid Gurvits, Warren D. Smith
Abstract — We show that the common symbolic manipulation tasks of computing multiple partial derivatives, definite integration, and definite summation, are #P-hard, i.e., at least as hard as...
A Bayesian approach to relevance in game playing (1997)
The point of game tree search is to insulate oneself from errors in the evaluation function. The standard approach is to grow a full width tree as deep as time allows, and then value the tree as if...
A Simple Method for Completing Degenerate Delaunay Tessellations (1997)
Michael B. Dillencourt, Warren D. Smith
We characterize the conditions under which completing a Delaunay tessellation produces a configuration that is a nondegenerate Delaunay triangulation of an arbitrarily small perturbation of the...
Molecular Tinkertoys and How to Assemble Them (1997)
We propose a systematic method of synthesizing robust macromolecules of any desired shape with precise and total structural control. It involves assembly of 3D objects from a few fundamental and...
On Carmichael numbers with 3 factors and the strong pseudoprime test (1997)
The well known "strong pseudoprime test" has its highest probability of error (ß 1=4) when the numbers being tested are certain Carmichael numbers with 3 prime factors. We present a...
Hash Functions for Binary and Ternary Words (1996)
We describe a simple integer-valued "hash" function h(x), where x is a binary word of some fixed length. This hash function has the properties that 1. h(x) may be computed in O(n) steps...
Experiments with a Bayesian game player (1996)
Warren D. Smith, Eric B. Baum, Charles Garrett, Rico Tudor
. In [7] we proposed a Bayesian algorithm for game playing that we will call BP. BP maintains a probabilistic model of its uncertainty and uses it to grow its search tree in the most relevant...
DNA computers in vitro and vivo (1995)
Abstract-- We show how DNA molecules and stan-dard lab techniques may be used to create a nondeterministic Turing machine. This is the first scheme that shows how to make a universal computer with...
Graph-Theoretical Conditions for Inscribability and Delaunay Realizability (1995)
Michael B. Dillencourt, Warren D. Smith
We present new graph-theoretical conditions for polyhedra of inscribable type and Delaunay triangulations. We establish several sufficient conditions of the following general form: if a polyhedron...
A Linear-Time Algorithm For Testing The Inscribability Of Trivalent Polyhedra (1995)
Michael B. Dillencourt, Warren D. Smith
We present an algorithm for testing the inscribability of a trivalent polyhedron or, equivalently, testing the circumscribability of a simplicial polyhedron. Our algorithm, which runs in linear time...
Best Play for Imperfect Players and Game Tree Search; part I - theory (1995)
1 . The point of game tree search is to insulate oneself from errors in the evaluation function. The standard approach is to grow a full width tree as deep as time allows, and then value the tree as...
Best Play for Imperfect Players and Game Tree Search; part II - experiments (1995)
Warren D. Smith, Eric B. Baum, Charles Garrett
. In part 1 we proposed the BPIP algorithm for game playing. BPIP maintains a probabilistic model of its uncertainty and uses it to grow its search tree in the most relevant directions, and to value...
Fundamental Physical Limits on Computation (1995)
Current (May 1995) revision of 1992 report. We consider limitations on the performance of computers arising from thermodynamics and the laws of physics. We provide upper bounds on three quantities:...
Shallow excluded minors and improved graph decompositions (1994)
Serge Plotkin, Satish Rao, Warren D. Smith
In this paper we introduce the notion of the limited-depth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that...
Values of the Merging Function and Algorithm Design as a Game (1994)
Warren D. Smith, Kevin J. Lang
Finding algorithms that are optimal for worst case input is equivalent to solving a 2-player game of perfect information. The merging game arises when finding the minimum number M(m;n) of comparisons...
Accurate Circle Configurations and Numerical Conformal Mapping in Polynomial Time (1994)
According to a remarkable reinterpretation of a theorem of E.M. Andreev (1970) by W.P. Thurston (ß1982), there is a unique (up to inversive transformations) packing of interior-disjoint circles in...
Rating Systems for Gameplayers, and Learning (1994)
This report studies rating systems: systems that produce quantitative measures, called "ratings, " of the ability of players in a league, based on game results. By "quantitative",...
Shallow Excluded Minors and Improved Graph Decompositions (1994)
Serge Plotkin, Satish Rao, Warren D. Smith
In this paper we introduce the notion of the limiteddepth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that...
Three disproofs of the Gilbert-Pollak conjecture on Steiner ratio in three or more dimensions (1994)
The Gilbert-Pollak conjecture, posed in 1968, was the most important conjecture in the area of "Steiner trees." The "Steiner minimal tree" (SMT) of a point set P is the shortest...
A Test Suite for Chess Programs (1993)
Kevin J. Lang, Warren D. Smith
We describe a suite of ß 5500 test positions for testing chess playing programs. They are available as pub/wds/ChessTest.tar.Z by anonymous ftp to external.NJ.NEC.COM. Almost all of these positions...
Optimal shapes for Gears (1993)
Gear theory is re-examined and we find optimal shapes for gears. As optimality criteria, we allow: (1) minimal frictional losses (highest efficiency) assuming linear law of friction or (2) uniform...
Hodgson, Craig D., Rivin, Igor, Smith, Warren D.
We describe a characterization of convex polyhedra in $\h^3$ in terms of their dihedral angles, developed by Rivin. We also describe some geometric and combinatorial consequences of that theory. One...
Approximation of Staircases By Staircases (1992)
Warren D. Smith, Han La Poutre
The simplest nontrivial monotone functions are "staircases." The problem arises: what is the best approximation of some monotone function f(x) by a staircase with M jumps? In particular:...
On the Steiner ratio in 3-space (1992)
Warren D. Smith, J. Macgregor Smith
The "Steiner minimal tree" (SMT) of a point set P is the shortest network of "wires" which will suffice to "electrically" interconnect P . The "minimum spanning...
Abstract--- We explore the question of counting, and estimating the number and the fraction of, inscribable graphs. In particular we will concern ourselves with the number of inscribable and...
A high current density pulse-mode proton source:--preliminary study. (1968)
Thesis (M.S.)--University of New Mexico.
An investigation of electric rate structures /--by James A. Lyles, Warren D. Smith. (1927)
Lyles, James A., Smith, Warren D.
Thesis (B.S.)--Massachusetts Institute of Technology, Dept. of Business and Engineering Administration, 1927.
56 p., [21] leaves of plates (some folded) :