Works (20)

Updated: July 5th, 2023 15:40

2021 journal article

LOG-CONCAVE POLYNOMIALS, I: ENTROPY AND A DETERMINISTIC APPROXIMATION ALGORITHM FOR COUNTING BASES OF MATROIDS

DUKE MATHEMATICAL JOURNAL, 170(16), 3459–3504.

By: N. Anari*, S. Gharan* & C. Vinzant n

TL;DR: It is proved that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant, and a general framework for approximate counting in discrete problems, based on convex optimization is developed. (via Semantic Scholar)
Source: Web Of Science
Added: November 29, 2021

2021 article

Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests

STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, pp. 408–420.

By: N. Anari*, K. Liu*, S. Gharan*, C. Vinzant n & T. Vuong*

author keywords: Counting and Sampling; Near-Linear Time Algorithm; Random Walk; Exchange Property; Discrete Optimization
TL;DR: It is shown that the down-up random walk, started from an arbitrary point in the support, mixes in time O(klogk), and tight mixing time bounds are proved for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. (via Semantic Scholar)
UN Sustainable Development Goal Categories
15. Life on Land (OpenAlex)
Source: Web Of Science
Added: July 18, 2022

2021 article

Log-Concave Polynomials in Theory and Applications (Tutorial)

STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, pp. 12–12.

By: N. Anari* & C. Vinzant n

author keywords: Log-Concave Polynomials; Matroids; Approximate Counting; Approximate Sampling; High Dimensional Expanders
TL;DR: This tutorial will introduce the theory and applications of log-concave polynomials, survey some of the recent developments in this area, and survey the random cluster model in certain regimes. (via Semantic Scholar)
Source: Web Of Science
Added: July 18, 2022

2021 journal article

Positively hyperbolic varieties, tropicalization, and positroids

ADVANCES IN MATHEMATICS, 383.

By: F. Rincon*, C. Vinzant n & J. Yu*

author keywords: Stable polynomial; Hyperbolicity; Positroid; Positive Grassmannian; Non-crossing partition; M-convex
Source: Web Of Science
Added: May 24, 2021

2019 journal article

Computing complex and real tropical curves using monodromy

JOURNAL OF PURE AND APPLIED ALGEBRA, 223(12), 5232–5250.

By: D. Brake*, J. Hauenstein* & C. Vinzant n

TL;DR: Algorithms for computing the rays of a complex and real tropical curve defined by polynomials with constant coefficients based on homotopy continuation, monodromy loops, and Cauchy integrals are presented. (via Semantic Scholar)
Source: Web Of Science
Added: August 5, 2019

2019 article

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid

PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19), pp. 1–12.

By: N. Anari*, K. Liu*, S. Gharan* & C. Vinzant n

author keywords: Approximating Counting; Approximate Sampling; High-Dimensional Expanders; Geometry of Polynomials
TL;DR: It is shown 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, and an FPRAS is designed to count the number of bases of any matroid given by an independent set oracle. (via Semantic Scholar)
UN Sustainable Development Goal Categories
15. Life on Land (OpenAlex)
Source: Web Of Science
Added: April 27, 2020

2019 journal article

Low-Rank Sum-of-Squares Representations on Varieties of Minimal Degree

INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2019(1), 33–54.

Source: Web Of Science
Added: February 4, 2019

2018 article

Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids

2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), pp. 35–46.

By: N. Anari*, S. Gharan & C. Vinzant*

author keywords: matroid; deterministic counting; entropy; log-concave polynomial
Source: Web Of Science
Added: January 21, 2019

2015 conference paper

A small frame and a certificate of its injectivity

2015 International Conference on Sampling Theory and Applications (SAMPTA), 197–200.

By: C. Vinzant n

TL;DR: A complex frame of eleven vectors in 4-space is presented and it is proved that it defines injective measurements, which disproves a recent conjecture of Bandeira, Cahill, Mixon, and Nelson. (via Semantic Scholar)
Source: NC State University Libraries
Added: August 6, 2018

2015 journal article

An algebraic characterization of injectivity in phase retrieval

Applied and Computational Harmonic Analysis, 38(2), 346–356.

By: A. Conca*, D. Edidin*, M. Hering* & C. Vinzant*

author keywords: Phase retrieval; Algebraic geometry
TL;DR: It is shown that any vector is uniquely determined from 4 M − 4 generic measurements, and the set of frames defining non-injective measurements with the projection of a real variety is identified and bound its dimension. (via Semantic Scholar)
Source: Crossref
Added: February 24, 2020

2015 journal article

Computing Hermitian determinantal representations of hyperbolic curves

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 25(8), 1327–1336.

By: D. Plaumann*, R. Sinn*, D. Speyer* & C. Vinzant n

author keywords: Hyperbolic polynomials; determinantal representations; interlacing; Hermitian matrices of linear forms
TL;DR: An algorithm is presented that reduces a large part of the problem to linear algebra and its numerical implementation is discussed, which is computationally intensive but effective. (via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018

2015 journal article

Hyperbolic polynomials, interlacers, and sums of squares

Mathematical Programming, 153(1), 223–245.

By: M. Kummer*, D. Plaumann* & C. Vinzant*

Source: Crossref
Added: December 11, 2020

2015 journal article

Quartic spectrahedra

MATHEMATICAL PROGRAMMING, 151(2), 585–612.

Source: Web Of Science
Added: August 6, 2018

2013 journal article

Determinantal representations of hyperbolic plane curves: An elementary approach

Journal of Symbolic Computation, 57, 48–60.

By: D. Plaumann* & C. Vinzant*

author keywords: Hyperbolic polynomials; Determinantal representations; Interlacing; Hermitian matrices of linear forms
TL;DR: By allowing for Hermitian matrices instead, this work shows that a matrix of linear forms is definite if and only if its co-maximal minors interlace its determinant and extends a classical construction of determinantal representations of Dixon from 1902. (via Semantic Scholar)
Source: Crossref
Added: August 28, 2020

2013 journal article

The entropic discriminant

Advances in Mathematics, 244, 678–707.

By: R. Sanyal*, B. Sturmfels* & C. Vinzant*

author keywords: Matroid; Discriminant; Hyperplane arrangement; Ramification locus; Fully real system
UN Sustainable Development Goal Categories
10. Reduced Inequalities (OpenAlex)
Source: Crossref
Added: August 28, 2020

2012 journal article

Real radical initial ideals

Journal of Algebra, 352(1), 392–407.

By: C. Vinzant*

author keywords: Real algebraic geometry; Tropical geometry; Initial ideals; Semialgebraic sets; Preorders; Quadractic modules
Source: Crossref
Added: December 11, 2020

2012 journal article

The Central Curve in Linear Programming

Foundations of Computational Mathematics, 12(4), 509–540.

By: J. De Loera*, B. Sturmfels* & C. Vinzant*

author keywords: Linear programming; Central path; Hyperplane arrangement; Interior-point methods; Complementary slackness; Matroid; Tutte polynomial; Hyperbolic polynomial; Gauss map; Degree; Curvature; Total curvature; Projective variety; Grobner basis; Prime ideal
Source: Crossref
Added: August 28, 2020

2011 journal article

Edges of the Barvinok–Novik Orbitope

Discrete & Computational Geometry, 46(3), 479–487.

By: C. Vinzant*

author keywords: Moment curve; Toeplitz operator; Orbitope; Convex hull of a curve
TL;DR: Results of Smilansky prove tightness for k=2 and prove the conjecture that for all k the Barvinok–Novik orbitope is tight. (via Semantic Scholar)
Source: Crossref
Added: January 5, 2021

2011 journal article

Quartic curves and their bitangents

Journal of Symbolic Computation, 46(6), 712–733.

By: D. Plaumann*, B. Sturmfels* & C. Vinzant*

author keywords: Plane curves; Bitangents; Determinantal representations; Sums of squares; Semidefinite programming; Gale duality
TL;DR: Interwoven is an exposition of much of the 19th century theory of plane quartics, which expresses Vinnikov quartics as spectrahedra and positive Quartics as Gram matrices and explores the geometry of Gram spectahedra. (via Semantic Scholar)
Source: Crossref
Added: August 28, 2020

2009 journal article

Lower bounds for optimal alignments of binary sequences

Discrete Applied Mathematics, 157(15), 3341–3346.

By: C. Vinzant*

author keywords: Sequence alignment; Parametric analysis; Computational biology
TL;DR: The maximum number of distinct optimal alignment summaries over all pairs of length n sequences is @Q(n^2^/^3), thereby disproving the ''n conjecture''. (via Semantic Scholar)
Source: Crossref
Added: January 5, 2021

Citation Index includes data from a number of different sources. If you have questions about the sources of data in the Citation Index or need a set of data which is free to re-distribute, please contact us.

Certain data included herein are derived from the Web of Science© and InCites© (2024) of Clarivate Analytics. All rights reserved. You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.