Mikhail Khovanov, Greg Kuperberg
We compare two natural bases for the invariant space of a tensor product of irreducible representations of A2, or sl(3). One basis is the web basis, defined from a skein theory called the...
Denseness and Zariski denseness of Jones braid representations (2009)
Using various tools from representation theory and group theory, but without using hard classification theorems such as the classification of finite simple groups, we show that the Jones...
How hard is it to approximate the Jones polynomial? (2009)
Freedman, Kitaev, and Wang [arXiv:quant-ph/0001071], and later Aharonov, Jones, and Landau [arXiv:quant-ph/0511096], established a quantum algorithm to "additively" approximate the Jones polynomial...
ANALOGUES OF THE JORDAN–HÖLDER THEOREM FOR TRANSITIVE G-SETS (2009)
Greg Kuperberg, Richard Lyons, E. Zieve
Abstract. Let G be a transitive group of permutations of a finite set Ω, and suppose that some element of G has at most two orbits on Ω. We prove that any two maximal chains of groups between G...
A generalization of Filliman duality (2008)
Abstract. Filliman duality expresses (the characteristic measure of) a convex polytope P containing the origin as an alternating sum of simplices that share supporting hyperplanes with P. The terms...
Circumscribing Constant-Width Bodies with (2008)
Abstract. Makeev conjectured that every constant-width body is inscribed in the dual di erence body of a regular simplex. We prove that homologically, there are an odd numberofsuch circumscribing...
Circumscribing Constant-Width Bodies with (2008)
Abstract. Makeev conjectured that every constant-width body is inscribed in the dual difference body of a regular simplex. We prove that homologically, there are an odd number of such circumscribing...
Analogues of the Jordan-Holder theorem for transitive G-sets (2007)
Kuperberg, Greg, Zieve, Michael
Let G be a transitive group of permutations of a finite set X, and suppose that some element of G has at most two orbits on X. We prove that any two maximal chains of groups between G and a...
We consider Kasteleyn and Kasteleyn-Percus matrices, which arise in enumerating matchings of planar graphs, up to matrix operations on their rows and columns.
Detrimental Decoherence (2007)
Gil Kalai, Dorit Aharonov, Michael Ben-or, Greg Kuperberg
We propose and discuss two conjectures on the nature of informa-tion leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as...
From the Mahler conjecture to Gauss linking integrals (2006)
We establish a version of the bottleneck conjecture, which in turn implies a partial solution to the Mahler conjecture on the product $v(K) = (\Vol K)(\Vol K^\circ)$ of the volume of a symmetric...
Quantum Versus Classical Proofs and Advice (2006)
Aaronson, Scott, Kuperberg, Greg
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum...
Quantum versus classical proofs and advice (2006)
Scott Aaronson, Greg Kuperberg, S. Aaronson, G. Kuperberg
Abstract: This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA. We prove three results about this question. First, we give a...
Quantum versus classical proofs and advice (2006)
Scott Aaronson, Greg Kuperberg
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA. We prove three results about this question. First, we give a “quantum...
In this article, we show that a linear combination $X$ of $n$ independent, unbiased Bernoulli random variables $\{X_k\}$ can match the first $2n$ moments of a random variable $Y$ which is uniform on...
Numerical cubature from Archimedes' hat-box theorem (2004)
Archimedes' hat-box theorem states that uniform measure on a sphere projects to uniform measure on an interval. This fact can be used to derive Simpson's rule. We present various constructions of,...
Numerical cubature using error-correcting codes (2004)
We present a construction for improving numerical cubature formulas with equal weights and a convolution structure, in particular equal-weight product formulas, using linear error-correcting codes....
The second hull of a knotted curve (2003)
Cantarella, Jason., Kuperberg, Greg., Kusner, Robert Barnard., Sullivan, John Matthew.
American Journal of Mathematics - Volume 125, Number 6, December 2003
Lattice packings with gap defects are not completely saturated (2003)
Kuperberg, Greg, Kuperberg, Krystyna, Kuperberg, Wlodzimierz
We show that a honeycomb circle packing in $\R^2$ with a linear gap defect cannot be completely saturated, no matter how narrow the gap is. The result is motivated by an open problem of G. Fejes...
A subexponential-time quantum algorithm for the dihedral hidden subgroup problem (2003)
We present a quantum algorithm for the dihedral hidden subgroup problem with time and query complexity $O(\exp(C\sqrt{\log N}))$. In this problem an oracle computes a function $f$ on the dihedral...
Symmetry classes of alternating-sign matrices under one roof (2002)
In a previous article, we derived the alternating-sign matrix (ASM) theorem from the Izergin-Korepin determinant for a partition function for square ice with domain wall boundary. Here we show that...
Scholarly mathematical communication at a crossroads (2002)
This essay was invited for publication in Nieuw Archief voor Wiskunde; it will also appear in translation in the SMF Gazette and in the DMV Mitteilungen. I discuss the recent trends in scholarly...
Finite, connected, semisimple, rigid tensor categories are linear (2002)
Fusion categories are fundamental objects in quantum algebra, but their definition is narrow in some respects. By definition a fusion category must be k-linear for some field k, and every simple...
What is a virtual link? (2002)
Several authors have recently studied virtual knots and links because they admit invariants arising from R-matrices. We prove that every virtual link is uniquely represented by a link L in S X I, a...
The Second Hull of a Knotted Curve (2002)
Cantarella, Jason, Kuperberg, Greg, Kusner, Rob, Sullivan, John M
The convex hull of a set K in space consists of points which are, in a certain sense, "surrounded" by K. When K is a closed curve, we define its higher hulls, consisting of points which are "multiply...
Fat 4-polytopes and fatter 3-spheres (2002)
Eppstein, David, Kuperberg, Greg, Ziegler, Günter M.
We introduce the fatness parameter of a 4-dimensional polytope P, defined as \phi(P)=(f_1+f_2)/(f_0+f_3). It arises in an important open problem in 4-dimensional combinatorial geometry: Is the...
The capacity of hybrid quantum memory (2002)
The general stable quantum memory unit is a hybrid consisting of a classical digit with a quantum digit (qudit) assigned to each classical state. The shape of the memory is the vector of sizes of...
A tracial quantum central limit theorem (2002)
We prove a central limit theorem for non-commutative random variables in a von Neumann algebra with a tracial state: Any non-commutative polynomial of averages of i.i.d. samples converges to a...
We consider Kasteleyn and Kasteleyn-Percus matrices, which arise in enumerating matchings of planar graphs, up to matrix operations on their rows and columns.
A generalization of Filliman duality (2001)
Filliman duality expresses (the characteristic measure of) a convex polytope P containing the origin as an alternating sum of simplices that share supporting hyperplanes with P. The terms in the...
We consider Kasteleyn and Kasteleyn-Percus matrices, which arise in enumerating matchings of planar graphs, up to matrix operations on their rows and columns. If such a matrix is defined over a...
Symmetry classes of alternating-sign matrices under one roof (2000)
In a previous article [math.CO/9712207], we derived the alternating-sign matrix (ASM) theorem from the Izergin-Korepin determinant for a partition function for square ice with domain wall boundary....
Perturbative 3-manifold invariants by cut-and-paste topology (1999)
Kuperberg, Greg, Thurston, Dylan P.
We give a purely topological definition of the perturbative quantum invariants of links and 3-manifolds associated with Chern-Simons field theory. Our definition is as close as possible to one given...
Random words, quantum statistics, central limits, random matrices (1999)
Recently Tracy and Widom conjectured [math.CO/9904042] and Johansson proved [math.CO/9906120] that the expected shape \lambda of the semi-standard tableau produced by a random word in k letters is...
The notion of a completely saturated packing [Fejes Toth, Kuperberg and Kuperberg, Highly saturated packings and reduced coverings, Monats. Math. 125 (1998) 127-145] is a sharper version of maximum...
Circumscribing Constant-Width Bodies with Polytopes (1999)
Makeev conjectured that every constant-width body is inscribed in the dual difference body of a regular simplex. We prove that homologically, there are an odd number of such circumscribing bodies in...
The bottleneck conjecture (1998)
The Mahler volume of a centrally symmetric convex body K is defined as M(K)= (Vol K)(Vol K^dual). Mahler conjectured that this volume is minimized when K is a cube. We introduce the bottleneck...
An exploration of the permanent-determinant method (1998)
The permanent-determinant method and its generalization, the Hafnian-Pfaffian method, are methods to enumerate perfect matchings of plane graphs that was discovered by P. W. Kasteleyn. We present...
Circumscribing constant-width bodies with polytopes (1998)
Makeev conjectured that every constant-width body is inscribed in the dual difference body of a regular simplex. We prove that homologically, there are an odd number of such circumscribing bodies in...
Another low-technology estimate in convex geometry (1998)
We give a short argument that for some C > 0, every n-dimensional Banach ball K admits a 256-round subquotient of dimension at least C n/(log n). This is a weak version of Milman's quotient of...
Generalized counterexamples to the Seifert conjecture (1998)
Kuperberg, Greg, Kuperberg, Krystyna
Using the theory of plugs and the self-insertion construction due to the second author, we prove that a foliation of any codimension of any manifold can be modified in a real analytic or...
An Exploration of the Permanent-Determinant Method (1998)
The permanent-determinant method and its generalization, the HafnianPfa #an method, are methods to enumerate perfect matchings of plane graphs that were discovered by P. W. Kasteleyn. We present...
Web bases for sl(3) are not dual canonical (1997)
Khovanov, Mikhail, Kuperberg, Greg
We compare two natural bases for the invariant space of a tensor product of irreducible representations of A_2, or sl(3). One basis is the web basis, defined from a skein theory called the...
Non-involutory Hopf algebras and 3-manifold invariants (1997)
We present a definition of an invariant #(M,H), defined for every finite-dimensional Hopf algebra (or Hopf superalgebra or Hopf object) H and for every closed, framed 3-manifold M. When H is a...
Detecting knot invertibility (1997)
We discuss the consequences of the possibility that Vassiliev invariants do not detect knot invertibility as well as the fact that quantum Lie group invariants are known not to do so. On the other...
Quadrisecants of knots and links (1997)
We show that every non-trivial tame knot or link in R^3 has a quadrisecant, i.e. four collinear points. The quadrisecant must be topologically non-trivial in a precise sense. As an application, we...
Another homogeneous, non-bihomogeneous Peano continuum (1997)
K. Kuperberg found a locally connected, finite-dimensional continuum which is homogeneous but not bihomogeneous. We give a similar but simpler example. Like previous constructions, the example is...
Another proof of the alternating sign matrix conjecture (1997)
Robbins conjectured, and Zeilberger recently proved, that there are 1!4!7!...(3n-2)!/n!/(n+1)!/.../(2n-1)! alternating sign matrices of order n. We give a new proof of this result using an analysis...
Spiders for rank 2 Lie algebras (1997)
A spider is an axiomatization of the representation theory of a group, quantum group, Lie algebra, or other group or group-like object. We define certain combinatorial spiders by generators and...
Tewodros Amdeberhan, Shalosh B. Ekhad, Greg Kuperberg
[P] have conjectured the following determinant identity:
Jaeger's Higman-Sims state model and the B_2 spider (1996)
Jaeger [Geom. Dedicata 44 (1992), 23-52] discovered a remarkable checkerboard state model based on the Higman-Sims graph that yields a value of the Kauffman polynomial, which is a quantum invariant...
Polyhedral Sets and Combinatorics (1996)
Jim Propp, Scott Axelrod, John Baez, Beifang Chen, Timothy Chow, Ezra Getzler, ...
17> = 1, where F i = the number of i-faces of P . We can prove this by defining a suitable valuation (additive function) on a large class of subsets of R n . A polyhedral set in R n is (1) a union...
Highly saturated packings and reduced coverings (1995)
Tóth, Gabor Fejes, Kuperberg, Greg, Kuperberg, Włodzimierz
We introduce and study certain notions which might serve as substitutes for maximum density packings and minimum density coverings. A body is a compact connected set which is the closure of its...
Asymptotically optimal covering designs (1995)
Gordon, Daniel, Kuperberg, Greg, Patashnik, Oren, Spencer, Joel
A (v,k,t) covering design, or covering, is a family of k-subsets, called blocks, chosen from a v-set, such that each t-subset is contained in at least one of the blocks. The number of blocks is the...
Four symmetry classes of plane partitions under one roof (1995)
In previous paper, the author applied the permanent-determinant method of Kasteleyn and its non-bipartite generalization, the Hafnian-Pfaffian method, to obtain a determinant or a Pfaffian that...
A volume-preserving counterexample to the Seifert conjecture (1995)
We prove that every 3-manifold possesses a $C^1$, volume-preserving flow with no fixed points and no closed trajectories. The main construction is a volume-preserving version of the Schweitzer plug....
New constructions for covering designs (1995)
Gordon, Daniel, Kuperberg, Greg, Patashnik, Oren
A $(v,k,t)$ {\em covering design}, or {\em covering}, is a family of $k$-subsets, called blocks, chosen from a $v$-set, such that each $t$-subset is contained in at least one of the blocks. The...
New Constructions for Covering Designs (1995)
Daniel M. Gordon, Greg Kuperberg, Oren Patashnik
A (v,k,t) covering design, or covering, is a family of k-subsets, called blocks, chosen from a v-set, such that each t-subset is contained in at least one of the blocks. The number of blocks is the...
Self-complementary plane partitions by Proctor's minuscule method (1994)
A method of Proctor [European J. Combin. 5 (1984), no. 4, 331-350] realizes the set of arbitrary plane partitions in a box and the set of symmetric plane partitions as bases of linear representations...
Symmetries of plane partitions and the permanent-determinant method (1994)
In the paper [J. Combin. Theory Ser. A 43 (1986), 103--113], Stanley gives formulas for the number of plane partitions in each of ten symmetry classes. This paper together with results by Andrews [J....
Average kissing numbers for non-congruent sphere packings (1994)
Kuperberg, Greg, Schramm, Oded
The Koebe circle packing theorem states that every finite planar graph can be realized as the nerve of a packing of (non-congruent) circles in R^3. We investigate the average kissing number of finite...
Average Kissing Numbers for Non-Congruent Sphere Packings (1994)
Introduction Let P be a packing of n (round) balls in R 3 . (A packing of round balls, also known as a sphere packing, is a collection of round balls with disjoint interiors.) The balls may have...
A low-technology estimate in convex geometry (1992)
Let $K$ be an $n$-dimensional symmetric convex body with $n \ge 4$ and let $K\dual$ be its polar body. We present an elementary proof of the fact that $$(\Vol K)(\Vol K\dual)\ge \frac{b_n^2}{(\log_2...
The quantum G_2 link invariant (1991)
We derive an inductive, combinatorial definition of a polynomial-valued regular isotopy invariant of links and tangled graphs. We show that the invariant equals the Reshetikhin-Turaev invariant...
Alternating sign matrices and domino tilings (1991)
Elkies, Noam, Kuperberg, Greg, Larsen, Michael, Propp, James
We introduce a family of planar regions, called Aztec diamonds, and study the ways in which these regions can be tiled by dominoes. Our main result is a generating function that not only gives the...
Involutory Hopf algebras and 3-manifold invariants (1990)
We establish a 3-manifold invariant for each finite-dimensional, involutory Hopf algebra. If the Hopf algebra is the group algebra of a group $G$, the invariant counts homomorphisms from the...
An Exploration of the Permanent-Determinant Method
The permanent-determinant method and its generalization, the HafnianPfaffian method, are methods to enumerate perfect matchings of plane graphs that were discovered by P. W. Kasteleyn. We present...