Solving Polynomial Equations (Simons Institute, 2014)
2014-10-13..2014-10-16
Berkeley, United States
[Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Hyperbolic Polynomials and Hyperbolic Programming, Connections Between Algorithm Design and Complexity Theory, Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019), Rigorous Evidence for Information-Computation Trade-offs, Semidefinite Optimization, Approximation and Applications 2014]
| title | author | length |
|---|---|---|
| Solvability of Systems of Polynomial Equations over Finite Fields | Neeraj Kayal | 01h 03m |
Claim: for any fixed number of variables N there is a deterministic algorithm that decides solvability over F_p in time polynomial in input size but with a… | ||
| A Complexity Theory for Constructible Functions and Sheaves | Saugata Basu | 01h 08m |
Claims a singly exponential bound and an explicit algorithm for the derived direct image of a constructible sheaf under a polynomial map: given a… | ||
| Sign Conditions for Injectivity of Generalized Polynomial Maps with Applications to Chemical ... | Anne Shiu | 01h 04m |
Gives a concrete theorem: a parametrized family of generalized polynomial maps (including mass-action ODEs) is injective for all rate constants exactly when… | ||
| Identifiability of Viscoelastic Mechanical Systems | Nikki Meshkat | 27m |
Claim: a spring–dashpot network is locally identifiable iff the number of non‑monic coefficients equals the number of parameters, and global identifiability… | ||
| Matrix Completion for the Independence Model | Kaie Kubjas | 25m |
Given observed entries first use 2×2 minors to fill entries and collapse connected blocks into single entries by summing them the partial matrix is completable… | ||
| Polynomial Systems Arising in the Study of Biochemical Reaction Networks | Alicia Dickenstein | 31m |
Mass-action kinetics produce autonomous polynomial ODEs whose reaction graph forces conservation relations and integer-exponent monomials; for many enzymatic… | ||
| Advances in Numerical Algebraic Geometry with Applications | Charles Wampler | 01h 08m |
Robonaut 2 has 42 DOF with a 12‑DOF hand driven by ~16 tendons, requiring an open wrist whose kinematics reduce to polynomial systems; forward/inverse problems… | ||
| Numerical Algebraic Geometry for Maximum Likelihood Estimation | Jose Rodríguez | 25m |
Connects maximum likelihood estimation to conormal and dual varieties and gives a concrete computational recipe: form likelihood equations, clear denominators… | ||
| Computing Tropical Curves Using Homotopy Continuation | Anton Leykin | 30m |
Numeric method computes tropical curves by tracing amoeba tentacles with homotopy continuation, sampling parallel log-slices, and recovering primitive integer… | ||
| Generalized Mixed Volume of Polynomial Systems | Matthew Niemerg | 31m |
Defines a generalized mixed volume computed by introducing replacement variables for repeated subexpressions and then randomizing coefficients on the fixed… | ||
| Arithmetic Nullstellensätze and Applications | Teresa Krick | 01h 00m |
Gives explicit arithmetic Nullstellensatz bounds: for at most n+1 polynomials with degrees dj and heights hj over Z or K(t) produces α∈A\{0} and Gi∈A[X] with… | ||
| Characterization of the Affine Solutions of Sparse Polynomial Systems | María Isabel Herrero | 26m |
Gives a combinatorial characterization of affine components of sparse polynomial systems and a probabilistic symbolic algorithm that computes geometric… | ||
| Bertini_real: Software for Real Algebraic Sets | Daniel Brake | 28m |
Bertini_real is a compiled tool that uses the Bertini homotopy engine with adaptive multiple precision and calls MATLAB for iso-singular deflation to produce… | ||
| Certifying Solutions to Overdetermined and Singular Polynomial Systems over Q | Agnes Szanto | 31m |
A practical algorithm certifies exact rational roots of overdetermined and isosingular polynomial systems by combining homotopy-computed approximations with a… | ||
| On the Critical Point Method and Deciding Connectivity Queries in Real Algebraic Sets | Mohab Safey El Din | 01h 05m |
Algorithms use critical point method and polar varieties to reduce connectivity queries to solving explicit Lagrange/determinantal systems and building a… | ||
| Real Algebraic Geometry in Computational Game Theory | Peter Bro Miltersen | 25m |
Proves a worst-case convergence bound for Howard's policy-iteration on concurrent reachability games, showing iterations are bounded by a… | ||
| On the Intersection of a Sparse Curve and a Low-degree Curve: A Polynomial Version of the Lost Theor | Sébastien Tavenas | 26m |
Proves a concrete polynomial bound in d and t on the number of real solutions (and real connected components) of a system f(x,y)=0 with deg(f) ≤ d and g(x,y)… | ||
| Descartes' Rule of Signs for Polynomial Systems Supported on Circuits | Frédéric Bihan | 30m |
Generalizes Descartes' rule to multivariate polynomial systems supported on circuits by giving an explicit procedure: form the Gale dual matrix from the… | ||
| Reconstruction of Algebraic-exponential Data from Moments and Solving a Generalized Lowner-John Prob | Jean-Bernard Lasserre | 55m |
Claims exact recovery of algebraic–exponential functions from a finite moment sequence up to order 2d by checking a rank condition on the moment matrix and… | ||
| Chordal Structure and Polynomial Systems | Pablo Parrilo | 33m |
Proposes a chordal elimination algorithm that preserves sparsity by eliminating variables along a perfect elimination order, computes elimination ideals for… | ||
| Families of Anticommuting Matrices and the Sum of Squares Problem | Pavel Hrubeš | 30m |
Question asks how many squares K write sum_{i=1}^n x_i^2 y_i^2 as sum of K bilinear squares; trivial bounds give n ≤ s(n) ≤ n^2 and best known constructive… | ||
| Degree of Central Curve in Quadratic Programming | Serkan Hosten | 30m |
Degree of the complex central curve for generic quadratic programs equals the mixed-volume count given by the polytope support formula: degree = sum_{k=0}^d… | ||
| A Taxonomy of Fixed Point Computation Problems for Algebraically-Defined Functions, and their Comput | Kousha Etessami | 01h 10m |
Algorithms target least fixed points of max/min probabilistic polynomial systems (branching MDP Bellman equations). Strategy decomposes SCCs, removes… | ||
| On the Complexity of Solving Bivariate Systems | Éric Schost | 26m |
Algorithm computes a squarefree eliminant and rational parametrization for two bivariate polynomials with integer coefficients in near-optimal bit complexity ≈… | ||
| Recent Progress on Computing Groebner Bases | Shuhong Gao | 25m |
Defines a module-level framework that turns Buchberger S-pair work into signature-based checks: a subset G generates a strong Gröbner basis for the module… | ||
| Mixed Volume Computation in (another) Mixed Volume Time | Gregorio Malajovich | 35m |
Presents a randomized algorithm that replaces exhaustive combinatorics with a geometry-driven bound proportional to mixed volumes, using Legendre transforms… | ||
| Solving Polynomial Equations in Smoothed Polynomial Time | Peter Bürgisser | 01h 00m |
Shows that adaptive linear homotopy with Newton steps and randomized start sampling has a provable smooth‑analysis bound: the expected continuation cost… | ||
| A Theory of Complexity, Condition and Roundoff | Felipe Cucker | 27m |
Defines a finite-precision BSS machine that rounds every intermediate real to x(1+δ) with |δ| ≤ u and fixes precision k = log2(1/u). Proposes input size =… | ||
| Some Results and Questions as to the Complexity of the (Eigenvalue, Eigenvector) Problem | Michael Shub | 29m |
Proposes a homotopy continuation method that tracks all eigenpairs and proves with probability one it finds approximate zeros in Smale sense for Gaussian… | ||
| Comparing the Theory and Practice of Spectral Algorithms to Combinatorial Flow Algorithms for ... | Dorit Hochbaum | 59m |
Dorit Hochbaum, UC Berkeley
Spectral Algorithms: From Theory to Practice
http://simons.berkeley.edu/talks/dorit-hochbaum-2014-10-30 | ||
| nothing matches | ||