@article{anari_gharan_vinzant_2021, title={LOG-CONCAVE POLYNOMIALS, I: ENTROPY AND A DETERMINISTIC APPROXIMATION ALGORITHM FOR COUNTING BASES OF MATROIDS}, volume={170}, ISSN={["1547-7398"]}, DOI={10.1215/00127094-2020-0091}, abstractNote={We give a deterministic polynomial time $2^{O(r)}$-approximation algorithm for the number of bases of a given matroid of rank $r$ and the number of common bases of any two matroids of rank $r$. To the best of our knowledge, this is the first nontrivial deterministic approximation algorithm that works for arbitrary matroids. Based on a lower bound of Azar, Broder, and Frieze [ABF94] this is almost the best possible result assuming oracle access to independent sets of the matroid. 
There are two main ingredients in our result: For the first, we build upon recent results of Adiprasito, Huh, and Katz [AHK15] and Huh and Wang [HW17] on combinatorial hodge theory to derive a connection between matroids and log-concave polynomials. We expect that several new applications in approximation algorithms will be derived from this connection in future. Formally, we prove that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant. For the second ingredient, we develop a general framework for approximate counting in discrete problems, based on convex optimization. The connection goes through subadditivity of the entropy. For matroids, we prove that an approximate superadditivity of the entropy holds by relying on the log-concavity of the corresponding polynomials.}, number={16}, journal={DUKE MATHEMATICAL JOURNAL}, author={Anari, Nima and Gharan, Shayan Oveis and Vinzant, Cynthia}, year={2021}, month={Nov}, pages={3459–3504} }
 @article{anari_liu_gharan_vinzant_vuong_2021, title={Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests}, ISSN={["0737-8017"]}, DOI={10.1145/3406325.3451091}, abstractNote={We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. For a matroid of rank k on a ground set of n elements, or more generally distributions associated with log-concave polynomials of homogeneous degree k on n variables, we show that the down-up random walk, started from an arbitrary point in the support, mixes in time O(klogk). Our bound has no dependence on n or the starting point, unlike the previous analyses of Anari et al. (STOC 2019), Cryan et al. (FOCS 2019), and is tight up to constant factors. The main new ingredient is a property we call approximate exchange, a generalization of well-studied exchange properties for matroids and valuated matroids, which may be of independent interest. In particular, given a distribution µ over size-k subsets of [n], our approximate exchange property implies that a simple local search algorithm gives a kO(k)-approximation of maxS µ(S) when µ is generated by a log-concave polynomial, and that greedy gives the same approximation ratio when µ is strongly Rayleigh. As an application, we show how to leverage down-up random walks to approximately sample random forests or random spanning trees in a graph with n edges in time O(nlog2 n). The best known result for sampling random forest was a FPAUS with high polynomial runtime recently found by Anari et al. (STOC 2019), Cryan et al. (FOCS 2019). For spanning tree, we improve on the almost-linear time algorithm by Schild (STOC 2018). Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time for these problems. Our algorithms can be naturally extended to support approximately sampling from random forests of size between k1 and k2 in time O(n log2 n), for fixed parameters k1, k2.}, journal={STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING}, author={Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis and Vinzant, Cynthia and Vuong, Thuy-Duong}, year={2021}, pages={408–420} }
 @article{anari_vinzant_2021, title={Log-Concave Polynomials in Theory and Applications (Tutorial)}, ISSN={["0737-8017"]}, DOI={10.1145/3406325.3465351}, abstractNote={Log-concave polynomials give rise to discrete probability distributions with several nice properties. In particular, log-concavity of the generating polynomial guarantees the existence of efficient algorithms for approximately sampling from a distribution and finding the size of its support. This class of distributions contains several important examples, including uniform measures over bases or independent sets of matroids, determinantal point processes and strongly Rayleigh measures, measures defined by mixed volumes in Mikowski sums, the random cluster model in certain regimes, and more. In this tutorial, we will introduce the theory and applications of log-concave polynomials and survey some of the recent developments in this area.}, journal={STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING}, author={Anari, Nima and Vinzant, Cynthia}, year={2021}, pages={12–12} }
 @article{rincon_vinzant_yu_2021, title={Positively hyperbolic varieties, tropicalization, and positroids}, volume={383}, ISSN={["1090-2082"]}, DOI={10.1016/j.aim.2021.107677}, abstractNote={A variety of codimension c in complex affine space is positively hyperbolic if the imaginary part of any point in it does not lie in any positive linear subspace of dimension c. Positively hyperbolic hypersurfaces are defined by stable polynomials. We characterize these varieties using sign variations, and show that they are equivalently defined by being hyperbolic with respect to the positive part of the Grassmannian, in the sense of Shamovich and Vinnikov. Positively hyperbolic projective varieties have tropicalizations that are locally subfans of the type A hyperplane arrangement defined by xi=xj, in which the maximal cones satisfy a non-crossing condition. This gives new proofs of results of Choe–Oxley–Sokal–Wagner and Brändén on Newton polytopes and tropicalizations of stable polynomials. We settle the question of which tropical varieties can be obtained as tropicalizations of positively hyperbolic varieties in the case of tropical toric varieties, constant-coefficient tropical curves, and Bergman fans. Along the way, we give a new characterization of positroids in terms of a non-crossing condition on their Bergman fans.}, journal={ADVANCES IN MATHEMATICS}, author={Rincon, Felipe and Vinzant, Cynthia and Yu, Josephine}, year={2021}, month={Jun} }
 @article{brake_hauenstein_vinzant_2019, title={Computing complex and real tropical curves using monodromy}, volume={223}, ISSN={["1873-1376"]}, DOI={10.1016/j.jpaa.2019.03.019}, abstractNote={Tropical varieties capture combinatorial information about how coordinates of points in a classical variety approach zero or infinity. We present algorithms for computing the rays of a complex and real tropical curve defined by polynomials with constant coefficients. These algorithms rely on homotopy continuation, monodromy loops, and Cauchy integrals. Several examples are presented which are computed using an implementation that builds on the numerical algebraic geometry software Bertini.}, number={12}, journal={JOURNAL OF PURE AND APPLIED ALGEBRA}, author={Brake, Danielle A. and Hauenstein, Jonathan D. and Vinzant, Cynthia}, year={2019}, month={Dec}, pages={5232–5250} }
 @article{anari_liu_gharan_vinzant_2019, title={Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid}, ISSN={["0737-8017"]}, DOI={10.1145/3313276.3316385}, abstractNote={We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where 0<q<1. Consequently, we can sample random spanning forests in a graph and estimate the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has edge expansion at least 1. Our algorithm and proof build on the recent results of Dinur, Kaufman, Mass and Oppenheim who show that a high dimensional walk on a weighted simplicial complex mixes rapidly if for every link of the complex, the corresponding localized random walk on the 1-skeleton is a strong spectral expander. One of our key observations is that a weighted simplicial complex X is a 0-local spectral expander if and only if a naturally associated generating polynomial pX is strongly log-concave. More generally, to every pure simplicial complex with positive weights on its maximal faces, we can associate to X a multiaffine homogeneous polynomial pX such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of pX.}, journal={PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19)}, author={Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis and Vinzant, Cynthia}, year={2019}, pages={1–12} }
 @article{blekherman_plaumann_sinn_vinzant_2019, title={Low-Rank Sum-of-Squares Representations on Varieties of Minimal Degree}, volume={2019}, ISSN={["1687-0247"]}, DOI={10.1093/imrn/rnx113}, abstractNote={A celebrated result by Hilbert says that every real nonnegative ternary quartic is a sum of three squares. We show more generally that every nonnegative quadratic form on a real projective variety $X$ of minimal degree is a sum of $\dim(X)+1$ squares of linear forms. This strengthens one direction of a recent result due to Blekherman, Smith, and Velasco. Our upper bound is the best possible, and it implies the existence of low-rank factorizations of positive semidefinite bivariate matrix polynomials and representations of biforms as sums of few squares. We determine the number of equivalence classes of sum-of-squares representations of general quadratic forms on surfaces of minimal degree, generalizing the count for ternary quartics by Powers, Reznick, Scheiderer, and Sottile.}, number={1}, journal={INTERNATIONAL MATHEMATICS RESEARCH NOTICES}, author={Blekherman, Grigoriy and Plaumann, Daniel and Sinn, Rainer and Vinzant, Cynthia}, year={2019}, month={Jan}, pages={33–54} }
 @article{anari_gharan_vinzant_2018, title={Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids}, ISSN={["0272-5428"]}, DOI={10.1109/FOCS.2018.00013}, abstractNote={We give a deterministic polynomial time 2^O(r)-approximation algorithm for the number of bases of a given matroid of rank r and the number of common bases of any two matroids of rank r. To the best of our knowledge, this is the first nontrivial deterministic approximation algorithm that works for arbitrary matroids. Based on a lower bound of Azar, Broder, and Frieze this is almost the best possible assuming oracle access to independent sets of the matroid. There are two main ingredients in our result: For the first, we build upon recent results of Adiprasito, Huh, and Katz and Huh and Wang on combinatorial hodge theory to derive a connection between matroids and log-concave polynomials. We expect that several new applications in approximation algorithms will be derived from this connection in future. Formally, we prove that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant. For the second ingredient, we develop a general framework for approximate counting in discrete problems, based on convex optimization. The connection goes through subadditivity of the entropy. For matroids, we prove that an approximate superadditivity of the entropy holds by relying on the log-concavity of the corresponding polynomials.}, journal={2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS)}, author={Anari, Nima and Gharan, Shayan Oveis and Vinzant, Cynthia}, year={2018}, pages={35–46} }
 @inproceedings{vinzant_2015, title={A small frame and a certificate of its injectivity}, DOI={10.1109/sampta.2015.7148879}, abstractNote={We present a complex frame of eleven vectors in 4-space and prove that it defines injective measurements. That is, any rank-one 4 × 4 Hermitian matrix is uniquely determined by its values as a Hermitian form on this collection of eleven vectors. This disproves a recent conjecture of Bandeira, Cahill, Mixon, and Nelson. We use algebraic computations and certificates in order to prove injectivity.}, booktitle={2015 International Conference on Sampling Theory and Applications (SAMPTA)}, author={Vinzant, C.}, year={2015}, pages={197–200} }
 @article{conca_edidin_hering_vinzant_2015, title={An algebraic characterization of injectivity in phase retrieval}, volume={38}, ISSN={1063-5203}, url={http://dx.doi.org/10.1016/J.ACHA.2014.06.005}, DOI={10.1016/J.ACHA.2014.06.005}, abstractNote={A complex frame is a collection of vectors that span $\mathbb{C}^M$ and define measurements, called intensity measurements, on vectors in $\mathbb{C}^M$. In purely mathematical terms, the problem of phase retrieval is to recover a complex vector from its intensity measurements, namely the modulus of its inner product with these frame vectors. We show that any vector is uniquely determined (up to a global phase factor) from $4M-4$ generic measurements. To prove this, we identify the set of frames defining non-injective measurements with the projection of a real variety and bound its dimension.}, number={2}, journal={Applied and Computational Harmonic Analysis}, publisher={Elsevier BV}, author={Conca, Aldo and Edidin, Dan and Hering, Milena and Vinzant, Cynthia}, year={2015}, month={Mar}, pages={346–356} }
 @article{plaumann_sinn_speyer_vinzant_2015, title={Computing Hermitian determinantal representations of hyperbolic curves}, volume={25}, ISSN={["1793-6500"]}, DOI={10.1142/s0218196715500435}, abstractNote={ Every real hyperbolic form in three variables can be realized as the determinant of a linear net of Hermitian matrices containing a positive definite matrix. Such representations are an algebraic certificate for the hyperbolicity of the polynomial and their existence has been proved in several different ways. However, the resulting algorithms for computing determinantal representations are computationally intensive. In this note, we present an algorithm that reduces a large part of the problem to linear algebra and discuss its numerical implementation. }, number={8}, journal={INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION}, author={Plaumann, Daniel and Sinn, Rainer and Speyer, David E. and Vinzant, Cynthia}, year={2015}, month={Dec}, pages={1327–1336} }
 @article{kummer_plaumann_vinzant_2015, title={Hyperbolic polynomials, interlacers, and sums of squares}, volume={153}, ISSN={0025-5610 1436-4646}, url={http://dx.doi.org/10.1007/S10107-013-0736-Y}, DOI={10.1007/S10107-013-0736-Y}, abstractNote={Hyperbolic polynomials are real polynomials whose real hypersurfaces are maximally nested ovaloids, the innermost of which is convex. These polynomials appear in many areas of mathematics, including optimization, combinatorics and differential equations. Here we investigate the special connection between a hyperbolic polynomial and the set of polynomials that interlace it. This set of interlacers is a convex cone, which we write as a linear slice of the cone of nonnegative polynomials. In particular, this allows us to realize any hyperbolicity cone as a slice of the cone of nonnegative polynomials. Using a sums of squares relaxation, we then approximate a hyperbolicity cone by the projection of a spectrahedron. A multiaffine example coming from the Vámos matroid shows that this relaxation is not always exact. Using this theory, we characterize the real stable multiaffine polynomials that have a definite determinantal representation and construct one when it exists.}, number={1}, journal={Mathematical Programming}, publisher={Springer Science and Business Media LLC}, author={Kummer, Mario and Plaumann, Daniel and Vinzant, Cynthia}, year={2015}, month={Oct}, pages={223–245} }
 @article{ottem_ranestad_sturmfels_vinzant_2015, title={Quartic spectrahedra}, volume={151}, ISSN={["1436-4646"]}, DOI={10.1007/s10107-014-0844-3}, abstractNote={Quartic spectrahedra in 3-space form a semialgebraic set of dimension 24. This set is stratified by the location of the ten nodes of the corresponding real quartic surface. There are twenty maximal strata, identified recently by Degtyarev and Itenberg, via the global Torelli Theorem for real K3 surfaces. We here give a new proof that is self-contained and algorithmic. This involves extending Cayley’s characterization of quartic symmetroids, by the property that the branch locus of the projection from a node consists of two cubic curves. This paper represents a first step towards the classification of all spectrahedra of a given degree and dimension.}, number={2}, journal={MATHEMATICAL PROGRAMMING}, author={Ottem, John Christian and Ranestad, Kristian and Sturmfels, Bernd and Vinzant, Cynthia}, year={2015}, month={Jul}, pages={585–612} }
 @article{plaumann_vinzant_2013, title={Determinantal representations of hyperbolic plane curves: An elementary approach}, volume={57}, ISSN={0747-7171}, url={http://dx.doi.org/10.1016/J.JSC.2013.05.004}, DOI={10.1016/J.JSC.2013.05.004}, abstractNote={If a real symmetric matrix of linear forms is positive definite at some point, then its determinant is a hyperbolic hypersurface. In 2007, Helton and Vinnikov proved a converse in three variables, namely that every hyperbolic plane curve has a definite real symmetric determinantal representation. The goal of this paper is to give a more concrete proof of a slightly weaker statement. Here we show that every hyperbolic plane curve has a definite determinantal representation with Hermitian matrices. We do this by relating the definiteness of a matrix to the real topology of its minors and extending a construction of Dixon from 1902. Like Helton and Vinnikov's theorem, this implies that every hyperbolic region in the plane is defined by a linear matrix inequality.}, journal={Journal of Symbolic Computation}, publisher={Elsevier BV}, author={Plaumann, Daniel and Vinzant, Cynthia}, year={2013}, month={Oct}, pages={48–60} }
 @article{sanyal_sturmfels_vinzant_2013, title={The entropic discriminant}, volume={244}, ISSN={0001-8708}, url={http://dx.doi.org/10.1016/J.AIM.2013.05.019}, DOI={10.1016/J.AIM.2013.05.019}, abstractNote={The entropic discriminant is a non-negative polynomial associated to a matrix. It arises in contexts ranging from statistics and linear programming to singularity theory and algebraic geometry. It describes the complex branch locus of the polar map of a real hyperplane arrangement, and it vanishes when the equations defining the analytic center of a linear program have a complex double root. We study the geometry of the entropic discriminant, and we express its degree in terms of the characteristic polynomial of the underlying matroid. Singularities of reciprocal linear spaces play a key role. In the corank-one case, the entropic discriminant admits a sum of squares representation derived from the discriminant of a characteristic polynomial of a symmetric matrix.}, journal={Advances in Mathematics}, publisher={Elsevier BV}, author={Sanyal, Raman and Sturmfels, Bernd and Vinzant, Cynthia}, year={2013}, month={Sep}, pages={678–707} }
 @article{vinzant_2012, title={Real radical initial ideals}, volume={352}, ISSN={0021-8693}, url={http://dx.doi.org/10.1016/j.jalgebra.2011.11.028}, DOI={10.1016/j.jalgebra.2011.11.028}, abstractNote={We explore the consequences of an ideal I⊂R[x1,…,xn] having a real radical initial ideal, both for the geometry of the real variety of I and as an application to sums of squares representations of polynomials. We show that if inw(I) is real radical for a vector w in the tropical variety, then w is in the logarithmic set of the real variety. We also give algebraic sufficient conditions for w to be in the logarithmic limit set of a more general semialgebraic set. If in addition w∈(R>0)n, then the corresponding quadratic module is stable. In particular, if inw(I) is real radical for some w∈(R>0)n then ∑R[x1,…,xn]2+I is stable. This provides a method for checking the conditions for stability given by Powers and Scheiderer (2001) [PS].}, number={1}, journal={Journal of Algebra}, publisher={Elsevier BV}, author={Vinzant, Cynthia}, year={2012}, month={Feb}, pages={392–407} }
 @article{de loera_sturmfels_vinzant_2012, title={The Central Curve in Linear Programming}, volume={12}, ISSN={1615-3375 1615-3383}, url={http://dx.doi.org/10.1007/S10208-012-9127-7}, DOI={10.1007/S10208-012-9127-7}, abstractNote={The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal of the central curve, thereby answering a question of Bayer and Lagarias. These invariants, along with the degree of the Gauss image of the curve, are expressed in terms of the matroid of the input matrix. Extending work of Dedieu, Malajovich and Shub, this yields an instance-specific bound on the total curvature of the central path, a quantity relevant for interior point methods. The global geometry of central curves is studied in detail.}, number={4}, journal={Foundations of Computational Mathematics}, publisher={Springer Science and Business Media LLC}, author={De Loera, Jesús A. and Sturmfels, Bernd and Vinzant, Cynthia}, year={2012}, month={Jun}, pages={509–540} }
 @article{vinzant_2011, title={Edges of the Barvinok–Novik Orbitope}, volume={46}, ISSN={0179-5376 1432-0444}, url={http://dx.doi.org/10.1007/S00454-011-9351-Y}, DOI={10.1007/S00454-011-9351-Y}, abstractNote={Here we study the kth symmetric trigonometric moment curve and its convex hull, the Barvinok–Novik orbitope. In 2008, Barvinok and Novik introduced these objects and showed that there is some threshold so that for two points on $\mathbb {S}^{1}$ with arclength below this threshold the line segment between their lifts to the curve forms an edge on the Barvinok–Novik orbitope, and for points with arclength above this threshold their lifts do not form an edge. They also gave a lower bound for this threshold and conjectured that this bound is tight. Results of Smilansky prove tightness for k=2. Here we prove this conjecture for all k.}, number={3}, journal={Discrete & Computational Geometry}, publisher={Springer Science and Business Media LLC}, author={Vinzant, Cynthia}, year={2011}, month={May}, pages={479–487} }
 @article{plaumann_sturmfels_vinzant_2011, title={Quartic curves and their bitangents}, volume={46}, ISSN={0747-7171}, url={http://dx.doi.org/10.1016/j.jsc.2011.01.007}, DOI={10.1016/j.jsc.2011.01.007}, abstractNote={A smooth quartic curve in the complex projective plane has 36 inequivalent representations as a symmetric determinant of linear forms and 63 representations as a sum of three squares. These correspond to Cayley octads and Steiner complexes respectively. We present exact algorithms for computing these objects from the 28 bitangents. This expresses Vinnikov quartics as spectrahedra and positive quartics as Gram matrices. We explore the geometry of Gram spectrahedra and we find equations for the variety of Cayley octads. Interwoven is an exposition of much of the 19th century theory of plane quartics.}, number={6}, journal={Journal of Symbolic Computation}, publisher={Elsevier BV}, author={Plaumann, Daniel and Sturmfels, Bernd and Vinzant, Cynthia}, year={2011}, month={Jun}, pages={712–733} }
 @article{vinzant_2009, title={Lower bounds for optimal alignments of binary sequences}, volume={157}, ISSN={0166-218X}, url={http://dx.doi.org/10.1016/j.dam.2009.06.028}, DOI={10.1016/j.dam.2009.06.028}, abstractNote={In parametric sequence alignment, optimal alignments of two sequences are computed as a function of the penalties for mismatches and spaces, producing many different optimal alignments. Here we give a 3/(2^{7/3}\pi^{2/3})n^{2/3} +O(n^{1/3} \log n) lower bound on the maximum number of distinct optimal alignment summaries of length-n binary sequences. This shows that the upper bound given by Gusfield et. al. is tight over all alphabets, thereby disproving the "square root of n conjecture". Thus the maximum number of distinct optimal alignment summaries (i.e. vertices of the alignment polytope) over all pairs of length-n sequences is Theta(n^{2/3}).}, number={15}, journal={Discrete Applied Mathematics}, publisher={Elsevier BV}, author={Vinzant, Cynthia}, year={2009}, month={Aug}, pages={3341–3346} }