Source author record

Warren D. Smith

Warren D. Smith appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Information Theory math.IT math.MG math.NT math.PR math.ST Statistics Theory

Catalog footprint

What is connected

6works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Lower bounds on maximal determinants of binary matrices via the probabilistic method

Let $D(n)$ be the maximal determinant for $n \times n$ $\{\pm 1\}$-matrices, and ${\mathcal R}(n) = D(n)/n^{n/2}$ be the ratio of $D(n)$ to the Hadamard upper bound. We give several new lower bounds on ${\mathcal R}(n)$ in terms of $d$, where $n = h+d$, $h$ is the order of a Hadamard matrix, and $h$ is maximal subject to $h \le n$. A relatively simple bound is \[{\mathcal R}(n) \ge \left(\frac{2}{πe}\right)^{d/2} \left(1 - d^2\left(\fracπ{2h}\right)^{1/2}\right) \;\text{ for all }\; n \ge 1.\] An asymptotically sharper bound is \[{\mathcal R}(n) \ge \left(\frac{2}{πe}\right)^{d/2} \exp\left(d\left(\fracπ{2h}\right)^{1/2} + \; O\left(\frac{d^{5/3}}{h^{2/3}}\right)\right).\] We also show that \[{\mathcal R}(n) \ge \left(\frac{2}{πe}\right)^{d/2}\] if $n \ge n_0$ and $n_0$ is sufficiently large, the threshold $n_0$ being independent of $d$, or for all $n\ge 1$ if $0 \le d \le 3$ (which would follow from the Hadamard conjecture). The proofs depend on the probabilistic method, and generalise previous results that were restricted to the cases $d=0$ and $d=1$.

preprint2016arXiv

Probabilistic lower bounds on maximal determinants of binary matrices

Let ${\mathcal D}(n)$ be the maximal determinant for $n \times n$ $\{\pm 1\}$-matrices, and $\mathcal R(n) = {\mathcal D}(n)/n^{n/2}$ be the ratio of ${\mathcal D}(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on ${\mathcal D}(n)$ and $\mathcal R(n)$ in terms of $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h \le n$. For example, $\mathcal R(n) > (πe/2)^{-d/2}$ if $1 \le d \le 3$, and $\mathcal R(n) > (πe/2)^{-d/2}(1 - d^2(π/(2h))^{1/2})$ if $d > 3$. By a recent result of Livinskyi, $d^2/h^{1/2} \to 0$ as $n \to \infty$, so the second bound is close to $(πe/2)^{-d/2}$ for large $n$. Previous lower bounds tended to zero as $n \to \infty$ with $d$ fixed, except in the cases $d \in \{0,1\}$. For $d \ge 2$, our bounds are better for all sufficiently large $n$. If the Hadamard conjecture is true, then $d \le 3$, so the first bound above shows that $\mathcal R(n)$ is bounded below by a positive constant $(πe/2)^{-3/2} > 0.1133$.

preprint2013arXiv

Lower bounds on maximal determinants of +-1 matrices via the probabilistic method

We show that the maximal determinant D(n) for $n \times n$ ${\pm 1}$-matrices satisfies $R(n) := D(n)/n^{n/2} \ge κ_d > 0$. Here $n^{n/2}$ is the Hadamard upper bound, and $κ_d$ depends only on $d := n-h$, where $h$ is the maximal order of a Hadamard matrix with $h \le n$. Previous lower bounds on R(n) depend on both $d$ and $n$. Our bounds are improvements, for all sufficiently large $n$, if $d > 1$. We give various lower bounds on R(n) that depend only on $d$. For example, $R(n) \ge 0.07 (0.352)^d > 3^{-(d+3)}$. For any fixed $d \ge 0$ we have $R(n) \ge (2/(πe))^{d/2}$ for all sufficiently large $n$ (and conjecturally for all positive $n$). If the Hadamard conjecture is true, then $d \le 3$ and $κ_d \ge (2/(πe))^{d/2} > 1/9$.

preprint2010arXiv

Testing Closeness of Discrete Distributions

Given samples from two distributions over an $n$-element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in $n$, specifically, $O(n^{2/3}ε^{-8/3}\log n)$, independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than $\max\{ε^{4/3}n^{-1/3}/32, εn^{-1/2}/4\}$) or large (more than $ε$) in $\ell_1$ distance. This result can be compared to the lower bound of $Ω(n^{2/3}ε^{-2/3})$ for this problem given by Valiant. Our algorithm has applications to the problem of testing whether a given Markov process is rapidly mixing. We present sublinear for several variants of this problem as well.

preprint2009arXiv

Linear-time nearest point algorithms for Coxeter lattices

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^*$, $E_7^*$ and $E_8^*$. We consider the problem of finding a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexity $O(n\log{n})$ and the other with worst case complexity O(n) where $n$ is the dimension of the lattice. We show that for the particular lattices $A_n$ and $A_n^*$ the algorithms reduce to simple nearest point algorithms that already exist in the literature.

preprint1992arXiv

A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere

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 of these consequences is a combinatorial characterization of convex polyhedra in $\E^3$ all of whose vertices lie on the unit sphere. That resolves a problem posed by Jakob Steiner in 1832.