Complexity Of Computing Complex Zeros Of Structured Polynomial Systems
Peter Buergisser (TU Berlin)
3373 - 3384 of 18640 Results
Format results
Quantum Algorithms for Classical Sampling Problems
Dominik Wild Max Planck Institute of Quantum Optics
A Productization Property/Trick For H-Stable(And Hopefully Strongly Log-Concave) Polynomials
Leonid Gurvits (City College of New York)Gluon scattering in AdS from CFT
Pietro Ferrero University of Oxford
Sampling Matrices From Harish-Chandra-Itzykson-Zuber Densities
Colin McSwiggen (Courant Institute, New York University)Friendship in the Axiverse
David Cyncynates University of Washington
Continuous Maximum Entropy Distributions
Jonathan Leake (Weierstrass Institute Berlin)Discriminating between theories of the very early universe
Jerome Quintin University of Waterloo
Constrained Optimization On Riemannian Manifolds
Melanie Weber (Oxford, Mathematical Institute)Near Optimal Sample Complexity For Matrix And Tensor Normal Models Via Geodesic Convexity
Akshay Ramachandran (University of Amsterdam)Pivot Hamiltonians: a tale of symmetry, entanglement, and quantum criticality
Nathanan Tantivasadakarn California Institute of Technology (Caltech)
Complexity Of Computing Complex Zeros Of Structured Polynomial Systems
Peter Buergisser (TU Berlin)We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most d in n variables with only poly(n,d) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem. This is joint work with Felipe Cucker and Pierre Lairez, see arXiv:2010.10997.Quantum Algorithms for Classical Sampling Problems
Dominik Wild Max Planck Institute of Quantum Optics
Sampling from classical probability distributions is an important task with applications in a wide range of fields, including computational science, statistical physics, and machine learning. In this seminar, I will present a general strategy of solving sampling problems on a quantum computer. The entire probability distribution is encoded in a quantum state such that a measurement of the state yields an unbiased sample. I will discuss the complexity of preparing such states in the context of several toy models, where a polynomial quantum speedup is achieved. The speedup can be understood in terms of the properties of classical and quantum phase transitions, which establishes a connection between computational complexity and phases of matter. To conclude, I will comment on the prospects of applying this approach to challenging, real-world tasks.
Groups And Symmetries In Statistical Models
Anna Seigal (Harvard University)Groups and symmetries are at the heart of many problems in statistics and data analysis. I will focus on parameter estimation in statistical models via maximum likelihood estimation. We will see connections between maximum likelihood estimation, linear algebra, and invariant theory. The group or symmetric structure of a statistical model can be used to capture the existence and uniqueness of a maximum likelihood estimate, as well as to suggest suitable algorithms to find it. This talk is based on joint work with Carlos Améndola, Kathlén Kohn, Visu Makam, and Philipp Reichenbach.A Productization Property/Trick For H-Stable(And Hopefully Strongly Log-Concave) Polynomials
Leonid Gurvits (City College of New York)The simplest homogeneous polynomials with nonnegative coefficients are products of linear forms Prod_{A}(X) associated with nonnegative matrices A. We prove that for any H-Stable(homogeneous and stable) polynomial p with P(E) = 1, where E is the vector of all ones, it's value p(X) = Prod_{A(X)}(X), where A(X) is nonnegative matrix with unit row sums and the vector of column sums equal to the gradient of p at E. I will first explain some intuition, and history, behind the result; sketch the proof and present a few applications and generalizations of this "productization" property. (Joint work with Jonathan Leake).Gluon scattering in AdS from CFT
Pietro Ferrero University of Oxford
I will present a class of recently computed holographic correlators between half-BPS operators in a vast array of SCFTs with non-maximal superconformal symmetry in dimensions d=3,4,5,6. Via AdS/CFT, these four-point functions are dual to gluon scattering amplitudes in AdS. Exploiting the notion of MRV limit I will show that, at tree level, all such correlators are completely fixed by symmetries and consistency conditions. Our results encode a wealth of novel CFT data and exhibit various emergent structures, including Parisi-Sourlas supersymmetry, hidden conformal symmetry and color-kinematics duality. This talk will be based on https://arxiv.org/pdf/2103.15830.pdf.
Sampling Matrices From Harish-Chandra-Itzykson-Zuber Densities
Colin McSwiggen (Courant Institute, New York University)Exponential densities on unitary conjugation orbits of Hermitian matrices, known as Harish-Chandra-Itzykson-Zuber (HCIZ) densities, are important in various settings in physics and random matrix theory. However, the basic question of efficient sampling from these densities has remained open. We present two efficient algorithms to sample matrices from distributions that are close to the HCIZ distribution. Both algorithms exploit a natural self-reducible structure that arises from continuous symmetries of the underlying unitary orbit. We will also discuss applications to quantum inference and differentially private rank-k approximation.Friendship in the Axiverse
David Cyncynates University of Washington
A generic low-energy prediction of string theory is the existence of a large collection of axions, commonly known as a string axiverse. String axions can be distributed over many orders of magnitude in mass, and are expected to interact with one another through their joint potential. In this talk, I will show how non-linearities in this potential lead to a new type of resonant energy transfer between axions with nearby masses. This resonance generically transfers energy from axions with larger decay constants to those with smaller decay constants, leading to a multitude of signatures. These include enhanced direct detection prospects for a resonant pair comprising even a small subcomponent of dark matter, and boosted small-scale structure if the pair is the majority of DM. Near-future iterations of experiments such as ADMX and DM Radio will be sensitive to this scenario, as will astrophysical probes of DM substructure.
Continuous Maximum Entropy Distributions
Jonathan Leake (Weierstrass Institute Berlin)Maximum entropy distributions on discrete domains have been studied in a number of contexts over the past few decades. In particular, they have been used in deterministic algorithms for the approximation of the permanent, scaling problems for torus actions, applications of spanning tree sampling problems, and beyond. These applications are intimately linked to distributions on some finite support set, with a given expectation, and which maximize entropy. In this talk, we will discuss the generalization of maximum entropy distributions from finite discrete support sets to continuous manifolds. Such distributions arise in connection to a number of topics; for example, quantum entropy, interior point methods, matrix distributions studied in statistics, the isotropic constant, and low-rank matrix approximation. We will discuss a few of these applications, along with some of the computability issues which arise when moving from discrete support to continuous. We will also briefly discuss the connection between this generalization and the norm minimization techniques used for general scaling problems. This is joint work with Nisheeth Vishnoi.Discriminating between theories of the very early universe
Jerome Quintin University of Waterloo
There exist various scenarios for the very early universe that could potentially be the explanation for the observed properties of the cosmic microwave background. The current paradigm -- inflationary cosmology -- has rightfully received much attention, but it is not the only theoretically viable explanation. Indeed, several alternative scenarios exist, for example a contracting universe prior to a bounce or a slowly expanding emerging universe. It thus bares the question: how can we discriminate between the various theories, both from a theoretical and an observational point of view? A few pathways to answering this question are discussed in this talk.
Constrained Optimization On Riemannian Manifolds
Melanie Weber (Oxford, Mathematical Institute)Many applications involve non-Euclidean data, where exploiting Riemannian geometry can deliver algorithms that are computationally superior to standard nonlinear programming approaches. This observation has resulted in an increasing interest in Riemannian methods in the optimization and machine learning community. In this talk, we consider the problem of optimizing a function on a Riemannian manifold subject to convex constraints. We introduce Riemannian Frank-Wolfe (RFW) methods, a class of projection-free algorithms for constrained geodesically convex optimization. To understand the algorithm’s efficiency, we discuss (1) its iteration complexity, (2) the complexity of computing the Riemannian gradient, and (3) the complexity of the Riemannian “linear” oracle (RLO), a crucial subroutine at the heart of the algorithm. We complement our theoretical results with an empirical comparison of RFW against state-of-the-art Riemannian optimization methods. Joint work with Suvrit Sra (MIT).Near Optimal Sample Complexity For Matrix And Tensor Normal Models Via Geodesic Convexity
Akshay Ramachandran (University of Amsterdam)The matrix normal model, the family of Gaussian matrix-variate distributions whose covariance matrix is the Kronecker product of two lower dimensional factors, is frequently used to model matrix-variate data. The tensor normal model generalizes this family to Kronecker products of three or more factors. We study the estimation of the Kronecker factors of the covariance matrix in the matrix and tensor models. We show nonasymptotic bounds for the error achieved by the maximum likelihood estimator (MLE) in several natural metrics. In contrast to existing bounds, our results do not rely on the factors being well-conditioned or sparse. For the matrix normal model, all our bounds are minimax optimal up to logarithmic factors, and for the tensor normal model our bound for the largest factor and overall covariance matrix are minimax optimal up to constant factors provided there are enough samples for any estimator to obtain constant Frobenius error. In the same regimes as our sample complexity bounds, we show that an iterative procedure to compute the MLE known as the flip-flop algorithm converges linearly with high probability. Our main tool is geodesic strong convexity in the geometry on positive-definite matrices induced by the Fisher information metric. This strong convexity is determined by the expansion of certain random quantum channels. We also provide numerical evidence that combining the flip-flop algorithm with a simple shrinkage estimator can improve performance in the undersampled regime.Pivot Hamiltonians: a tale of symmetry, entanglement, and quantum criticality
Nathanan Tantivasadakarn California Institute of Technology (Caltech)
I will introduce the notion of Pivot Hamiltonians, a special class of Hamiltonians that can be used to "generate" both entanglement and symmetry. On the entanglement side, pivot Hamiltonians can be used to generate unitary operators that prepare symmetry-protected topological (SPT) phases by "rotating" the trivial phase into the SPT phase. This process can be iterated: the SPT can itself be used as a pivot to generate more SPTs, giving a rich web of dualities. Furthermore, a full rotation can have a trivial action in the bulk, but pump lower dimensional SPTs to the boundary, allowing the practical application of scalably preparing cluster states as SPT phases for measurement-based quantum computation. On the symmetry side, pivot Hamiltonians can naturally generate U(1) symmetries at the transition between the aforementioned trivial and SPT phases. The sign-problem free nature of the construction gives a systematic approach to realize quantum critical points between SPT phases in higher dimensions that can be numerically studied. As an example, I will discuss a quantum Monte Carlo study of a 2D lattice model where we find evidence of a direct transition consistent with a deconfined quantum critical point with emergent SO(5) symmetry.
This talk is based on arXiv:2107.04019, 2110.07599, 2110.09512