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.
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)
open access via arxiv.org (repository)
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.
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
11. Sustainable Cities and Communities
(Web of Science)
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.
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.
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.
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.
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
11. Sustainable Cities and Communities
(Web of Science)
15. Life on Land
(OpenAlex)
Source: Web Of Science
Added: April 27, 2020
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.
author keywords: matroid; deterministic counting; entropy; log-concave polynomial
Source: Web Of Science
Added: January 21, 2019
2017 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
2015 conference paper
A small frame and a certificate of its injectivity
2015 International Conference on Sampling Theory and Applications (SAMPTA), 197–200.
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
Computing Hermitian determinantal representations of hyperbolic curves
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 25(8), 1327–1336.
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)
UN Sustainable Development Goal Categories
11. Sustainable Cities and Communities
(Web of Science)
Source: Web Of Science
Added: August 6, 2018
2014 journal article
An algebraic characterization of injectivity in phase retrieval
Applied and Computational Harmonic Analysis, 38(2), 346–356.
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
2014 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.
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
Hyperbolic polynomials, interlacers, and sums of squares
Mathematical Programming, 153(1), 223–245.
Source: Crossref
Added: December 11, 2020
2013 journal article
The entropic discriminant
Advances in Mathematics, 244, 678–707.
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.
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.
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.
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.
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.
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.