TimeSpeaker/ Title/ Abstract/ VODLocation
08:00 - 08:45 Shuttle Bus to NIMS [Refer to Handout]
Arrive at NIMS
09:00 - 10:00 IP1: The Euclidean Distance Degree of an Algebraic Variety
Giorgio Ottaviani (Università di Firenze),
Loading the live streaming player...
Given a real n*n symmetric matrix A, let us consider the distance function from A to the variety X of rank one symmetric matrices. The critical points of this function correspond to the eigenvectors of A, in particular they are all real. We study this setting when X is any algebraic variety. The critical points satisfy a remarkable duality property and their number is called the Euclidean Distance Degree of X, which is an orthogonal invariant. Chern classes may be used to compute these invariants, and pose some computational challenges. Many examples in tensor spaces arise from applications in computer vision and other areas, with a common geometric flavour. Other interesting examples and open problems arise from classical varieties, starting from conics.
Talk Material 1: /
KT 1
10:30 - 12:30 MS01: Semidefinite Optimization: Geometry, Algebra and Applications 1
João Gouveia (University of Coimbra), Elina Robeva (UC Berkeley), James Saunderson (Caltech), Rainer Sinn (Georgia Institute of Technology),
Psd-minimality and polytope ideals (João Gouveia)
A d-polytope is said to be psd minimal if it can be written as a projection of a slice of the cone of d+1 by d+1 positive semidefinite matrices, the smallest possible size for which this may happen. In this talk, we will introduce the concept of polytope ideal, an algebraic object that codifies the geometry of a polytope, and use it to derive obstructions and sufficient conditions for psd minimality. These will allow us to complete the classification of psd minimal 4-polytopes, providing examples that settle some open questions.
The Geometry of the Space of Matrices with Given psd Rank (Elina Robeva)
We study the boundary of the space of matrices with given psd rank. We give polynomial conditions in the entries of a matrix of rank 3 to lie in (the boundary of) the space of matrices of psd rank 2. Equivalent conditions can be given in terms of the geometry of the two nested polytopes corresponding to the matrix. We carry out the same study for general psd rank. We currently have conjectures that generalize our results for psd rank 3.
Sparse sum-of-squares certificates on finite abelian groups (James Saunderson)
We consider functions on finite abelian groups that are non-negative and also sparse in the Fourier basis. We investigate when such functions are sums of squares of functions with a small common Fourier support. We give a combinatorial condition for this based on finding chordal covers (with additional symmetry properties) of a graph that encodes the group and sparsity pattern of interest. These techniques allow us to resolve a conjecture of Laurent about non-negative quadratic functions on the hypercube, and to prove that a certain family of trigonometric cyclic polytopes (indexed by dimension) have significantly smaller SDP descriptions than LP descriptions.
Generic Spectrahedral Shadows (Rainer Sinn)
A generic spectrahedral shadow is a set given by a linear matrix inequality $S = \{ x\in R^n\vert \exists\; y\in R^p \colon \sum_{i=1}^n x_i A_i + \sum_{j=1}^p y_j B_j + C \geq 0 \}$, where $A_i, B_j, C$ are random real symmetric matrices. In other words, we consider a random instance of a feasible set of a semi-definite program. We study its boundary from an algebraic point of view, i.e. we characterize the polynomials that vanish on the boundaries of these convex sets and discuss the ranks of a generic boundary point. We point out connections to optimization by example.
Talk Material 2: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS02: Coding Theory 1
Elisa Gorla (University of Neuchatel), Yoonjin Lee (Ewha Womans University), Relinde Jurrius (University of Neuchâtel), Heide Gluesing-Luerssen (University of Kentucky),
Subspace codes from Ferrer diagrams (Elisa Gorla)
In 2009 Etzion and Silberstein proposed a construction for subspace codes, which can potentially produce subspace codes with larger cardinality than the known ones. The construction relies on the existence of large dimensional vector spaces of matrices with entries in a finite field, whose support is contained in a region shaped as a Ferrer diagram. Existence of such vector spaces of matrices was unclear, and in fact conjectured by Etzion and Silberstein in the same paper. In this talk, I discuss the conjecture of Etzion and Silberstein and establish that the conjecture is true in the practically relevant cases. Our proof is constructive, and combining our results with the multilevel construction we can produce examples of subspace codes with the largest known cardinality for the given parameters.
Self-dual codes and quasi-cyclic self-dual codes over finite fields and finite rings (Yoonjin Lee)
We present our recent development on constructions of self-dual codes and quasi-cyclic self-dual codes over finite fields and finite rings. We also discuss classification of extremal self-dual codes with an automorphism of prime order.
The extended rank weight enumerator (Relinde Jurrius)
Rank metric codes, as introduced by Gabidulin, are used in network coding. We will study the rank weight enumerator of such a code and some of its generalizations. This is motivated by similar results for codes with the Hamming metric. First, we define the extended rank weight enumerator: this polynomial gives the weight enumerator of all codes with the same generator matrix but defined over a finite extension of the original field. A second generalization is that we consider codes over a finite extension of an arbitrary field. This means we have to combine two generalizations that were studied before. One is a generalization of the case of Gabidulin codes to arbitrary characteristic as considered by Augot, Loidreau and Robert. The other is to use the notion of counting polynomials to define the (extended) rank weight enumerator, as considered for linear codes by Plesken and Bächler, since in this generality the set of codewords of a given rank weight is no longer finite. Joint work with Ruud Pellikaan.
A New Construction for Subspace Codes (Heide Gluesing-Luerssen)
In this talk a construction of subspace codes will be presented that combines suitable matrix representations of subspace codes and a rank-metric code in order to construct subspace codes of longer length. The distance of the resulting code, called linkage code, is the minimum of the constituent codes. The construction generalizes certain results in the literature, where partial spread codes are constructed with the aid of a suitable extension of spread codes. For certain parameters our construction also allows to construct optimal partial spreads. Finally, we discuss decodability of the linkage codes. We show that if the constituent codes are (lifted) Gabidulin codes, then the linkage codes can easily be decoded, and decoding essentially reduces to (parallel) decoding with respect to the constituent codes.
Talk Material 1: / Talk Material 3: /
10:30 - 12:30 MS03: Algorithms and Complexity in Polynomial Systems 1
Frank Sottile (Texas A&M University), Martin Helmer (University of Western Ontario), Pierre-Jean Spaenlehauer (Inria), Vissarion Fisikopoulos (Université libre de Bruxelles),
The Optimal Littlewood-Richardson Homotopy (Frank Sottile)
Numerical homotopy methods for solving systems of poly- nomial equations may follow far more paths than solutions, if the equations possess extra structure. Devising methods to handle such structure has long been a focus in the area, with the most well-known being the polyhedral ho- motopies for sparse systems of polynomials. This method is optimal for square systems which achieve the BKK poly- hedral bound. Algebraic geometry is a source of systems that have rich structure, and which may be overdetermined. A particular well-studied class of such systems comes from the Schubert calculus on the Grassmannian. With Vakil and Verschelde, we proposed the optimal Littlewood-Richardson homotopy for Schubert calculus which is based on Vakil's geometric Littlewood-Richardson rule. This is being implemented in Macaulay 2.My talk will sketch this background, explain the main features of this algorithm, and demonstrate our current implementation.
Algorithms for the Computation of Chern-Schwartz-Mac Pherson Classes and the Euler Characteristic (Martin Helmer)
Sparse resultants have been recently redefined as equations of toric cycles instead of the classical definition over toric varieties. This notion has better combinatorial and computational properties which should be useful in the design of algorithms for solving polynomial equations and the analy- sis of their complexity. In this talk, we will introduce these generalized resultants, and show some of their gen- eral properties. This is joint work with Gabriela Jeronimo and Martin Sombra.
Sparse Gröbner Bases: the Unmixed Case (Pierre-Jean Spaenlehauer)
We present analogs of Gröbner bases for semigroup alge- bras, and we propose variants of the F5 and FGLM algo- rithms to compute them. These algorithms provide tools to compute efficiently the solutions of sparse systems of equations when all the polynomials share the same monomial support (unmixed case). When these monomials correspond to the points with integer coordinates in a normal lattice polytope and under regularity assumptions, we prove com- plexity bounds which depend on combinatorial properties of this polytope. In particular, these results extend known bounds on the complexity of solving bilinear systems with Gröbner bases. Finally, on some families of sparse systems, our prototype ``proof-of-concept'' implementation shows large speed-ups compared to classical Gröbner bases software. Joint work with Jean-Charles Faugère and Jules Svartz.
The Newton Polytope of the Sparse Resultant (Vissarion Fisikopoulos)
The Newton polytope of a polynomial, characterizes the polynomial more precisely than total degree, thus offering the main representation in sparse elimination theory. The (sparse) resultant is a fundamental object in computational algebraic geometry. The talk is about the combinatorics of Newton polytopes of (sparse) resultants. These are known in the classical or Sylvester case and up to dimension 3. The results are by Gelfand, Kapranov, Zelevinsky and Sturmfels. We will discuss an extension of this work by studying the combinatorial characterization of 4-dimensional resultant polytopes, which show a greater diversity and in- volve computational and combinatorial challenges.
Talk Material 1: / Talk Material 2: / Talk Material 3: /
KT 1
10:30 - 12:30 MS04: Tropical Geometry 1
Anders Jensen (Aarhus University), Pascal Benchimol (EDF Lab), Yoav Len (University of Saarland), Yaroslav Shitov (The Higher School of Economics),
Starting Cones for Tropical Traversals (Anders Jensen)
The tropical variety of a prime polynomial ideal is a pure, connected polyhedral fan that may be computed by traversal. To start this traversal a single cone is required. So far no good method for finding a starting cone was known. In this talk we propose to find one by stably intersecting with coordinate hyperplanes until a tropical curve is obtained. The key idea is that doing stable inter- sections translates into doing Groebner basis computations over a field of rational functions. Using a recursive reformulation of Chan's tropical curve algorithm, finding a single ray in a curve is often easy. The tropical cone is then obtained by repeatedly finding such rays according to an already known heuristic strategy for tropical cone construction.
Long and Winding Central Paths (Pascal Benchimol)
We disprove a continuous analog of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with 3r+4 inequalities in di- mension 2r+2 where the central path has a total curvature which is exponential in r. Our method is to tropic- alize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. We show in particular that the tropical analogue of the analytic center is nothing but the tropical barycenter, i.e., the maximum of a tropical polyhedron. It follows that unlike in the classical case, the tropical central path may lie on the boundary of the tro- picalization of the feasible set, and may even coincide with a path of the tropical simplex method.
Counting Curves with Fixed j-invariant (Yoav Len)
I will discuss ongoing work with Dhruv Ranganathan to- wards a correspondence theorem between the number of algebraic and tropical elliptic curves on toric surfaces with fixed j-invariant satisfying point conditions. As an application, we present a new formula for elliptic curve counts on Hirzebruch surfaces.
Tropical Bounds for Extended Formulations of Polytopes (Yaroslav Shitov)
We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to develop a method of constructing real polytopes with large extension complexity.
Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS05: Geometry of Matrix Multiplication
Luca Chiantini (Univ. Siena), Christian Ikenmeyer (Texas A&M University), Peter Bürgisser (TU Berlin), JM Landsberg (Texas A&M University),
Geometric Methods for the Study of Symmetric Tensors (Luca Chiantini)
The geometry of the decomposition of symmetric tensors is strictly linked to the geometry of sets of points on the Veronese image of a projective space. We will introduce ideas on how the study of the Hilbert function on finite sets in P^n, via the Veronese embedding, produces information on some aspects of the decomposition of specific tensors, as the uniqueness of the decomposition itself (identifiability).
Well-Structured 3x3 Matrix Multiplication Algorithms over the Field with 2 Elements. (Christian Ikenmeyer)
Comon's conjecture states that for every symmetric tensor t of rank r there exists a decomposition of t into r sym- metric rank 1 tensors. Since the matrix multiplication ten- sor is not symmetric, we try to find tensor decompositions for 3x3 matrix multiplication that respect the tensor's sym- metry as closely as possible. This talk presents our results over the field with 2 elements.
Degeneration and Complexity of Bilinear Maps (Peter Bürgisser)
In the beginning of the nineties, Volker Strassen wrote three papers on the degeneration and complexity of bilinear maps. They were motivated by the problem of matrix multiplication and have a focus on asymptotic questions. These papers, which are not too well known, combine ideas from functional analysis (spectrum) and information theory (entropy) in a fascinating way. It turned out that they are of relevance for quantum information theory. The goal of my talk is to give an overview of Strassen's papers and to propose some new directions.
Geometry of Border Rank Algorithms for Matrix Multiplication (Joseph Landsberg)
A border rank algorithm for a tensor may be thought of as a jet of a curve in a Grassmannian. I will discuss these jets for the matrix multiplication tensor and how they can potentially be used to both prove lower bounds and find new explicit algorithms. This is joint work with M. Michalek and N. Ryder.
Talk Material 1: / Talk Material 2: /
10:30 - 12:30 MS06: Applications of Computational Algebraic Geometry to Theoretical Physics 1
Seung-Joo Lee (Virginia Tech), Rak-Kyeong Seong (Korea Institute for Advanced Study), Jonathan Hauenstein (University of Notre Dame),
Hypercharge flux in heterotic compactifications (Seung-Joo Lee)
I will talk about heterotic Calabi-Yau models with hypercharge flux breaking, where the visible E8 is directly broken to the standard model group by a non-flat gauge bundle. It is shown that the required alternative E8 embeddings of hypercharge, normalised as required for gauge unification, can actually be found. But for all except one of them we prove a no-go theorem, asserting that no suitable geometry leads to a standard model in this context.
Hilbert Series and moduli spaces of Supersymmetric Gauge Theories (Rak-Kyeong Seong)
Studying vacuum moduli spaces is an integral part of understanding various properties of supersymmetric gauge theories. Hilbert series are generating functions of gauge invariant operators and play a prominent role in characterizing the moduli space as an algebraic variety. An introduction to Hilbert series in the context of supersymmetric gauge theories is given, with examples from quiver gauge theories with toric Calabi-Yau moduli spaces as well as from a set of quiver theories of recent interest.
Numerical algebraic geometry and physics (Jon Hauenstein)
Many problems in theoretical physics can be addressed by taking a computational geometric viewpoint. We aim to develop numerical algebraic geometric tools based on this geometric viewpoint. Two specific tools, namely numerical elimination theory and numerical computation of the geometric genus, will be discussed in the context of solving problems in theoretical physics.
10:30 - 12:30 MS07: Algebraic Structure in Graphical Models 1
Piotr Zwiernik (UC Berkeley), Shaowei Lin (Institute for Infocomm Research), Venkat Chandrasekaran (California Institute of Technology), Yaokun Wu (Shanghai Jiao Tong University),
Brownian Motion Tree Models and Their Geometry (Piotr Zwiernik)
A Brownian motion tree model on a tree T is a special Gaussian model closely linked to the graphical model on T, where the inner nodes are not observed. In this talk, I will present various ways of estimation for this model class both when T is known and when it is not known. Some of these results date back to Felsenstein (1971), but I will show how a geometric and algebraic understanding can give additional insight into the estimation process. Finally, I will discuss how to apply these results for estimating a phylogenetic tree for fruit flies.
Lessons on Statistical Singularities from Deep Learning (Shaowei Lin)
Deep learning is a neural network technique that gained great prominence in recent years for recognizing faces (Facebook), translating speech (Microsoft) and identifying cat videos (Google). Before deep learning, neural networks were unpopular due to overfitting, problems with local minima and difficulty in choosing appropriate hyper- parameters for regularization. In fact, Sumio Watanabe and his collaborators showed that the optimal hyperparameters are dictated by the structure of singularities in the models, and neural networks in particular are highly singular models. In this talk, we discuss how deep learning over- comes these singularities using Monte Carlo methods such as contrastive divergence and minimum probability flow.
Sufficient Dimension Reduction and Modeling Responses Given Covariates: An Integrated Convex Optimization Approach (Venkat Chandrasekaran)
Sufficient dimension reduction aims to identify a low-di- mensional approximation of a collection of covariates that are most relevant for predicting a set of responses. However, in many contemporary settings, the conditional distribution of the responses given the covariates is also high-dimensional and requires many parameters for its specification. This leads to the challenge of developing techniques to fit concisely described statistical models to the conditional distribution of the responses given the covariates. We present an integrated convex optimization framework for simultaneously (a) obtaining a low-dimen- sional representation of a set of covariates that is sufficient for predicting the responses, and (b) fitting several types of structured low-dimensional models -- factor models, graphical models, latent-variable graphical models -- to the con- ditional distribution of the responses given the covariates. The algebraic aspects underlying sufficient dimension re- duction play a prominent role in our approach. (Joint work with Armeen Taeb)
Primitive Matrix Set (Yaokun Wu)
To understand a Markov Chain we need to study the products of one nonnegative matrix while to understand a nonhomogeneous Markov chain we are led to a study of the products of a set of nonnegative matrices. Many con- cepts in the theory of Markov chain allow for a generalization in the framework of nonhomogeneous Markov chain, though the theory around those generalized concepts may not be established as easy as in the homogeneous case. In this talk, we will introduce primitive matrix set, a nonhomogeneous version of the concept of primitive matrix in the context of Markov chain, and discuss several combi- natorial problems around it. This is joint work with Xinmao Wang and Ziqing Xiang.
Talk Material 1: / Talk Material 2: / Talk Material 4: /
KT 2
10:30 - 12:30 MS08: Combinatorial Phylogenetics 1
Seth Sullivant (North Carolina State University), Megan Owen (Lehman College, CUNY), Terrel Hodge (Western Michigan University), Momoko Hayamizu (Graduate University for Advanced Studies/Institute of Statistical Mathematics),
Statistically-Consistent k-mer Methods for Phylogenetic Tree Reconstruction (Seth Sullivant)
Reconstruction of phylogenetic trees from sequence data is a two step process: first sequences are aligned and then the alignment and a model of evolution are used to infer the phylogenetic tree. However, the computation of the multiple sequence alignment usually requires a rough "guide tree" to relating species to make the computation tractable. The most common method for reconstructing guide trees (used by both MUSCLE and CLUSTALW) are based on distances between the vectors of k-mer counts of sequences. We show that these standard k-mer methods are statistically inconsistent for standard models of evolution, and derive model-based corrections for k-mer methods which are statistically consistent. This is joint work with Elizabeth Allman and John Rhodes.
Multiple Principal Components Analysis in Tree Space (Megan Owen)
The space of metric phylogenetic trees, as constructed by Billera, Holmes, and Vogtmann, is a polyhedral cone complex.  This space is non-positively curved, so the geodesic (shortest path) between two trees is unique and a well-defined notion of a mean tree for a given set of trees.  Algorithms for finding a first principal component for a set of trees in this space have also been developed, but they cannot be used in an iterative fashion.  We present the first method for computing multiple principal components, and apply it to a variety of datasets.
Characterising fully labelled tree-like metric spaces without using the four-point condition (Momoko Hayamizu)
Motivated by current biological interest in cellular hierarchy, we examine fully-labelled tree-like metric spaces without relying on the four-point condition. Our key question is: Given a metric space, $M$, on $n$ points, how can we determine whether $M$ is precisely realised by a fully labelled positive-weighted tree, $T$, on the same $n$ vertices? We introduce a fourth-point condition that is necessary and sufficient to ensure the existence of $T$ whenever the pairwise distances in $M$ are all distinct. We then explore how to measure the fully labelled tree-likeness (i.e., spanning tree-likeness) of $M$. We also discuss the implications of our results for different problems and concepts such as metric TSP and median graph.
Talk Material 4: /
12:30 - 14:00 Lunch
Cafeteria 1, 2
14:00 - 15:00 IP02: Some Current Directions in Coding Theory
Judy Walker (University of Nebraska),
Loading the live streaming player...
The theory of error-correcting codes was launched in Shannon's landmark 1948 paper, in which he proved that reliable information transmission across a noisy channel was possible. The proof is non-constructive, and "Shannon's challenge", as it has come to be known, is to find efficient codes that can correct many errors and come equipped with efficient decoding algorithms. With the discovery of turbo codes, the rediscovery of low-density parity-check codes, and the introduction of polar codes, many argue that Shannon's challenge has been met. However, many challenges in coding theory remain, as new applications necessary for our modern world continue to raise new questions. We will survey the field, placing particular emphasis on areas in which algebraic-geometric techniques have been, or can be, fruitfully applied.
Talk Material 1: /
KT 1
15:30 - 17:30 CP01: Contributed Session I
Nikolai Krivulin (Saint Petersburg State University), Grey Violet (University of Konstanz), Tobias Friedl (Freie Universität Berlin), Jesse Drendel (Colorado State University),
Solving multidimensional optimization problems over tropical semifields (Nikolai Krivulin)
We consider multidimensional problems that are formulated in the framework of tropical mathematics to minimize or maximize functions defined on vectors of a finite-dimensional semimodule over an idempotent semifield. The objective functions can be linear or nonlinear; in the latter case they are defined using multiplicative conjugate transposition of vectors. Both unconstrained problems and problems with vector equality and inequality constraints are under consideration. We start with a brief overview of known problems and existing solution methods. Some of these problems can be solved directly in an explicit form under fairly general assumptions about the underlying semifield. For other problems, algorithmic solutions are known only in terms of particular semifields to have the form of iterative computational procedures, which produces a particular solution, or indicates that no solution exist. Furthermore, we examine new problems with nonlinear objective functions, including problems of Chebyshev approximation, problems of minimizing the span seminorm, and problems with evaluating the spectral radius of a matrix. To solve the problems, several techniques are proposed based on the reduction of the problem to a parameterized system of inequalities, the derivation sharp bounds for the objective function, and the application of extremal properties of the spectral radius. We use these technique to obtain direct exact solutions of the problems in a compact vector form, which is ready for further analysis and practical implementation. The solutions obtained are applied to solve optimization problems in Chebyshev approximation, project scheduling, location analysis and decision making.
Real algebraic geometry of root invariance: spaces of robust stability problems (Grey Violet)
Control theory and analysis meets us with different stability definitions – Schur, Hurwitz, hyperbolicity, D-stabilities etc. But even for such basic classes of problems as PI and PID-controller synthesis geometry of parametric stability problems is not well understood. Here provided a unified algebraic-geometric framework for polynomial and matrix stability problems. Author builds stratified filtered (infinite-dimensional) real closed space of stability problems for each stability definition and problem class. That construction provides natural proofs of various old and new geometric results. Author continues their work in algebraic geometry of robust stability theory that have led to a significant progress in old problems.
On real varieties invariant under a finite reflection group (Tobias Friedl)
Let G be a finite real reflection group. We prove that the non-emptiness of a real G-invariant variety can be tested on the union of certain flats of the reflection arrangement. The dimension of these flats only depends on the degree of the polynomials defining the variety, in particular it is independent of the dimension of the ambient space. As a special case we recover the degree principle for symmetric polynomials, which states that the non-emptiness of a real variety defined by symmetric polynomials of degree at most d can be checked on a set of dimension d (Timofte, 2003, Riener, 2012). This is joint work with Cordian Riener and Raman Sanyal.
Real algebraic geometry applied to evolutionary genetics (Jesse Drendel)
Many dynamical systems from evolutionary genetics are discrete-time maps which are semi-algebraic functions--that is, functions whose graphs are the real solution set to a finite system of polynomial equations and inequalities. Algorithms from real algebraic geometry like cylindrical decomposition and stratification are applied and specialized to these systems to get at the topology of their nullclines and bifurcation diagrams. This is joint work with Daniel Bates, Patrick Shipman, Simon Tavener, and Michael Antolin.
Talk Material 1: / Talk Material 3: /
15:30 - 17:30 MS09: Semidefinite Optimization: Geometry, Algebra and Applications 2
Kai Kellner (Goethe University Frankfurt), Annie Raymond (University of Washington), Greg Blekherman (Georgia Institute of Technology),
Deciding containment of projections of spectrahedra (Kai Kellner)
Spectrahedra, the feasible regions of semidefinite programs, form a rich class of convex bodies that properly contains that of polyhedra. While the class of polyhedra is closed under linear projections, the class of spectrahedra is not. A containment problem is the task to decide the set-theoretic inclusion of two given sets. We state and study a sufficient semidefinite criterion for containment of projected spectrahedra. Starting from a geometric viewpoint, we state connections to the theory of (completely) positive maps and real algebraic geometry. Usage of this triad allows to state several exactness results for the sufficient semidefinite criterion.
Exploiting Symmetry in the Tur\'an Semidefinite Program (Annie Raymond)
We invoke techniques devised by Gatermann and Parrilo (2004) to investigate the role of symmetry in certifying the non-negativity of density inequalities for $a$-clique-free graphs. We then reevaluate this strategy in light of Razborov's flag algebras.
Symmetry Reduction for Sums of Squares on the Hypercube (Greg Blekherman)
Let $p$ be a symmetric polynomial, i.e. a polynomial fixed under permutations of variables, and let $H$ be the discrete hypercube $\{0,1\}^n$. The question of whether $p$ is a sum of squares of polynomials of low degree on $H$ can be reduced to a univariate sum of squares problem. I will present this reduction and explain how some known results on the Lasserre sum of squares hierarchy on $H$ easily follow from it.
Talk Material 1: / Talk Material 3: /
15:30 - 17:30 MS10: Coding Theory 2
Eimear Byrne (University College Dublin), Daniele Bartoli (Ghent University), Amaro Barreal (Aalto University), Leo Storme (Ghent University),
Broadcasting with Coded-Side Information (Eimear Byrne)
The standard index coding problem [1], involves a single broadcaster and m receivers. The broadcaster has a vector x in F_q^n and each receiver has some components of x as its side information and demands a further component of x. It is the task of the sender to satisfy the demands of all receivers using a minimal number of transmissions. Several graph-theoretic bounds are known on this quantity. In the error-free model, the index coding problem has been shown to be equivalent to the network coding problem [2] and is strongly related to the caching problem. Error-correction in the index coding problem has been discussed in [3] for the Hamming metric. Here we consider two independent extensions of the problem. In this more general scenario, the demands and side information of the users and sender are linear encodings of an original data matrix X in F_q^{n x t}. This extension allows applications to more general wireless broadcast settings, such as relay networks. Error correction is considered for both the Hamming and rank metric and bounds are given on the minimal number of transmissions required. [1] Z. Bar-Yossef, Z. Birk, T. S. Jayram, and T. Kol, “Index coding with side information”, in Proc. 47th Annu. IEEE Symp. Found. Comput. Sci., 2006, pp. 197–206. [2] A. E. Rouayheb, A. Sprintson, and C. Georghiades, “On the index coding problem and its relation to network coding and matroid theory”, IEEE Trans. Inf. Theory, vol. 56, no. 7, pp. 3187–3195, Jul. 2010. [3] Son Hoang Dau, Skachek, V., and Yeow Meng Chee, “Index coding and error correction”, Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pp.1787–1791, July 31 2011-Aug. 5, 2011. [4] W. Heamers, “An upper bound for the shannon capacity of a graph”, Algebr. Methods Graph Theory, 25, 1978,pp. 267–272.
The covering problem for linear codes and algebraic curves over finite fields (Daniele Bartoli)
The covering radius of a linear code C is the least integer s such that the spheres of radius s around the codewords cover the whole space, and specifies the maximum number of errors that a complete decoder has to correct. The covering radius is a basic geometric parameter of a code, which is important in a number of respects. An important parameter is the so called covering density, that is the average number of codewords contained in a sphere with radius s. In this talk I will present constructions of MDS codes, quasi-perfect codes, and Near-MDS codes arising from Algebraic Geometry. In particular, for codimensions r as large as the 12th root of q, an infinite family of q-ary MDS codes, that is codes attaining the Singleton bound, having covering radius s=r-1 and length less than q +1, will be presented. An infinite family of quasi-perfect linear codes with covering radius s=2 and small covering density will also be described. Both these constructions are related with elliptic curves and they are based on the study of algebraic curves over finite fields. Finally, I will talk about an algebraic construction of an infinite family of non-extendable Near-MDS codes of dimension 3. This is a joint work with N. Anbar, M. Giulietti, I. Platoni, G. Zini.
On lattice-codes for physical layer network coding. (Amaro Barreal)
Distributed wireless communications has been the subject of intensive research in the past few years. The advantage of introducing helping relays to the communications process recently motivated the study of a novel technique known as physical layer network coding, where ideas from network coding are realized at the physical layer. In their award-winning paper, Nazer and Gastpar proposed the compute-and-forward protocol, which proved to be of interest for physical layer network coding. The main idea of this protocol is to exploit the natural effects of interference in a helpful way, rather than treating it as an undesirable and harmful phenomenon. As regards the coding techniques for compute-and-forward, nested lattice codes turned out to be particularly helpful, although no optimality results have been derived so far. In this talk, we introduce the basic notions of physical layer network coding and the compute-and-forward protocol and study various aspects of the latter. In particular, we focus on lattices arising in this scenario and how to design them for good performance.
Linear codes arising from finite incidence structures (Leo Storme)
Consider the finite projective space PG(N,q) of dimension N over the finite field Fq of order q. Via the incidence matrices of points and k-spaces of P G(N, q), it is possible to define the generator matrix of a linear code C, and the parity check matrix of its dual linear code. But also variations on this theme of using projective spaces to define linear codes occur. This includes functional codes and projective Reed-Muller codes [1, 2]. The linear codes investigated in [1, 2] are constructed using classical varieties from finite projective spaces. Via geometrical methods and via results from algebraic geometry, such as the Hasse-Weil bound and Bezout’s theorem, properties of these linear codes are derived. In this way, finite projective spaces, in combination with algebraic geometry, contribute in various ways to coding theory. In this talk, we present a number of these results, thereby also showing which geometrical ideas are used to obtain these results. [1] D. Bartoli and L. Storme, On the functional codes arising from the intersections of algebraic varieties of small degree with a non-singular quadric. Adv. Math. Commun., to appear. [2] D. Bartoli, A. Sboui, and L. Storme, Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Adv. Math. Commun., submitted.
Talk Material 2: /
15:30 - 17:30 MS11: Software and Applications in Numerical Algebraic Geometry 1
Daniel Brake (University of Notre Dame), Abraham Martin del Campo (IST Austria), Nickolas Hein (University of Nebraska at Kearney),
Advances in software in numerical algebraic geometry (Daniel Brake)
Algebraic geometry is quickly becoming one of the more computational branches of mathematics, with software applications for both symbolic and numerical methods. A variety of general solvers and specialized programs have been developed over the last few decades, with major advances in Numerical Algebraic Geometry in the most recent decade. The breadth and spectrum of available packages can assist to solve a wide range of problems in pure and applied mathematics, engineering, and science. An overview of current and ongoing developments in software implementations will be discussed.
Critical points via monodromy and local methods (Abraham Martin del Campo)
In statistics and other applications, it is a fundamental problem to find the best representative of a model that optimizes an objective function. For instance, in statistics one is usually interested in finding the point in the parameter space of a probability distribution that maximizes the Likelihood function. Another example is to find the best low rank approximation to a given data matrix set. This can be recast as finding the points in the (algebraic) variety of all matrices (with certain structure) that are closest to a general data point with respect to the euclidean distance. In this talk, I will introduce a project with Jose Rodriguez, where we developed an algorithm that uses Numerical Algebraic Geometry tools to find the critical points of a distance function.
A lifted square formulation for certifiable Schubert calculus (Nickolas Hein)
Classical determinantal formulations of Schubert problems are typically overdetermined, involving many more equations than variables. This is undesirable when using numerical nonlinear algebra to solve an instance of a Schubert problem as certification requires a square system. Using reduction to the diagonal, we previously gave the primal-dual (square) formulation for Schubert calculus, which allows for certification of solutions but requires far more variables than the local determinantal formulation. We describe a different square formulation given by lifting incidence conditions which involves fewer equations and variables. Frank Sottile is a coauthor on this project.
Talk Material 2: / Talk Material 3: /
KT 1
15:30 - 17:30 MS12: Tropical Geometry 2
Jan Draisma (Eindhoven University of Technology), Dustin Cartwright (University of Tennesse), Ralph Morrison (UC Berkeley), Diane Maclagan (University of Warwick),
Metric graphs with prescribed gonality (Jan Draisma)
We prove that in the moduli space of genus-g metric graphs the locus of graphs with gonality at most d has the classical dimension min{3g-3,2g+2d-5}. Here, gonality is geometric gonality rather than divisorial gonality, i.e., it is the minimal degree of a non-degenerate harmonic map to a tree that satisfies the Riemann-Hurwitz condition everywhere. Our theorem follows from a careful parameter count to establish the upper bound and a construction of sufficiently many graphs with gonality at most d to establish the lower bound. In particular, we give an elementary (combinatorial) proof of the fact that for each combinatorial type, there is an open cone in edge-length space where the metric graph has gonality equal to (g+2)/2 rounded upwards. This is joint work with Filip Cools.
On dual complexes of degenerations (Dustin Cartwright)
The dual complex of a degeneration records how the components of the special fiber intersect. It appears in tropical geometry as a parameterizing object for the tropicalization. While any graph appears as the dual complex of a degeneration of curves, the same is not true in higher dimensions. I will discuss some obstructions to realizing specified dual complexes.
Tropical Igusa Invariants (Ralph Morrison)
Elliptic curves over an algebraically closed field are classified up to isomorphism by the j-invariant. Faithfully tropicalizing an elliptic curve with bad reduction gives a balanced piecewise-linear graph with genus 1, whose distinguished cycle has length equal to negative the valuation of the j-invariant. We generalize this study to curves of genus 2, which are classified by three invariants called Igusa invariants. I will show that these valuations of these invariants give some, but not all, tropical information, and will discuss how different invariants are more natural from a tropical perspective. This is joint work with Maria Angelica Cueto and Hannah Markwig.
Tropical schemes (Diane Maclagan)
A "tropical ideal" is a homogeneous ideal in the semiring of tropical polynomials with the property that each graded piece determines a valuated matroid. Such objects should define tropical subschemes of tropical projective space. I will describe joint work with Felipe Rincon developing some of the properties of these ideals and their associated varieties.
Talk Material 1: / Talk Material 2: / Talk Material 4: /
15:30 - 17:30 MS13: Spectral Theory of Tensors and Tensor Rank 1
Nick Vannieuwenhoven (KU Leuven), Ke Ye (University of Chicago), JM Landsberg (Texas A&M University), Yang QI (Gipsa-Lab),
Truncating a generic tensor rank decomposition of small rank is not optimal (Nick Vannieuwenhoven)
The Schmidt-Eckart-Young theorem for matrices states that the optimal rank-r approximation to a matrix in the Euclidean topology is obtained by retaining the first r terms from the singular value decomposition of that matrix, i.e. by truncation. In this talk, we consider a generalization of this optimal truncation property to the complex tensor rank decomposition and establish a necessary orthogonality condition. We prove that the real algebraic variety on which this condition holds is of a dimension strictly less than the anticipated real dimension of the r-secant variety of the Segre variety. Consequently, we proved that this condition is not satisfied at least by an open set of positive Lebesgue measure. We prove, moreover, that for tensors of small rank this orthogonality condition can be satisfied on only a set of tensors of Lebesgue measure zero. As a corollary, it follows that the tensor rank decomposition cannot be computed by successively computing best rank-1 approximations.
Multiplicities of eigenvalues of tensors (Ke Ye)
Eigenvalues of tensors are generalizations of eigenvalues of matrices. I will define algebraic multiplicity (a.m.) and geometric multiplicity (g.m.) of an eigenvalue of a tensor. In the matrix case, it is well known that a.m. is greater than or equal to g.m.. I will introduce a conjectured inequality of a.m. and g.m. which generalizes the matrix case. I will present some evidences and I will discuss some results for multiplicities of eigenvalues of a generic tensor. This is a joint work with Shingling Hu.
Abelian tensors and compression generic tensors (JM Landsberg)
Two recent advances in the study of tensor rank and border rank are an analysis of abelian tensors (tensors satisfying Strassen's equations and a mild genericity condition) and compression generic tensors (the first explicit tensors of dimensions (m,m,m) that have border rank greater than 2m). I will describe these advances and their roles in the search for upper and lower bounds for the complexity of matrix multiplication. This is joint work with Mateusz Michalek.
Nonnegative Rank and Singular Vectors of a Nonnegative Tensor (Yang Qi)
We show that a best nonnegative rank-r approximation of a nonnegative tensor is almost always unique and that nonnegative tensors with nonunique best nonnegative rank-r approximation form a semialgebraic set contained in an algebraic hypersurface. We then establish a singular vector variant of the Perron--Frobenius Theorem for positive tensors and apply it to show that a best nonnegative rank-r approximation of a positive tensor can almost never be obtained by deflation. We show the subset of real tensors which admit more than one best rank one approximations is a hypersurface, and give a polynomial equation to ensure a tensor without satisfying this equation to have a unique best rank one approximation. This is joint work with Pierre Comon (Grenoble) and Lek-Heng Lim (Chicago).
Talk Material 1: / Talk Material 2: / Talk Material 4: /
15:30 - 17:30 MS14: Algebraic Structures arising in Systems Biology 1
Nikki Meshkat (Santa Clara University), Xiaoxian Tang (NIMS), Carsten Conradi (Hochschule für Technik und Wirtschaft Berlin), Casian Pantea (West Virginia University),
An algebraic approach to the structural (un-)identifiability problem in systems biology (Nikki Meshkat)
The problem of parameter identifiability for a mathematical model is about finding which unknown parameters can be determined from known data. If all of the parameters can be determined, uniquely or finitely, the model is said to be identifiable. Otherwise, the model is said to be unidentifiable. Many models in systems biology are unidentifiable and thus the question that arises is what should one do with an unidentifiable model? One approach is to find identifiable functions of the parameters and attempt to reparameterize the model over these identifiable functions. We will discuss some methods to find these identifiable functions of parameters using algebraic techniques.
Stability Analysis of Multistable Biological Regulatory Systems (Xiaoxian Tang)
We consider the problem of counting (stable) steady states of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations.
Polynomial inequalities and sign conditions for multistationarity in mass-action networks (Carsten Conradi)
Polynomial inequalities and sign conditions for multistationarity in mass-action networks Multistationarity -- the existence of at least two positive steady states -- is considered an important qualitative property of many dynamical systems used in quantitative biology. As parameter uncertainty is high, establishing multistationarity for mass action networks requires establishing the existence of at least two positive solutions of a parameterized family of polynomials. We consider systems with special structure defined in terms of the reaction network. For these systems the polynomial family can be transformed into a polynomial system that contains only polynomials that are either binomial or bi-linear. By incorporating sign conditions for multistationarity we obtain a semi-algebraic set that is independent of the system parameters. Its elements define parameter values where multistationarity occurs. A network in this special class is a mass-action network that describes enzyme-catalyzed protein phosphorylation in the presence of protein synthesis and degradation.
Some results on injectivity and multistationarity in networks of interacting elements (Casian Pantea)
We gather and develop some necessary and sufficient criteria for injectivity and multistationarity in vector fields associated with an interaction network under more or less general assumptions on the nature of the network and the reaction rates. The results are phrased in a linear algebraic and matrix-theoretic setting, and graph-theoretic corollaries are also mentioned.
Talk Material 1: /
15:30 - 17:30 MS15: Markov Bases and their Applications in Statistics 1
Akimichi Takemura (University of Tokyo), Tobias Windisch (OvGU Magdeburg), Despina Stasi (Illinois Institute of Technology), Uwe Nagel (University of Kentucky),
Some results and conjectures on complexity of Markov bases (Akimichi Takemura)
We give some results and conjectures concerning complexity of Markov bases, in particular when columns are deleted (i.e., structural zeros are introduced) or rows are deleted (i.e., some parameters of a toric model are restricted to zeros) from a configuration matrix.
Rapid mixing and Markov bases (Tobias Windisch)
In the past, research in algebraic statistics has mostly focused on determination of Markov bases whereas mixing times of the resulting Markov chains have not received significant attention. In this talk, we discuss the behaviour of Markov chains on lattice points of polytopes using Markov bases. We show that, in fixed dimension, these Markov chains cannot mix rapidly. We also present a way to adapt Markov bases so that the fastest mixing behaviour can be obtained.
Statistical models for robust node degrees in graphs (Despina Stasi)
The k-core of a graph is its largest subgraph such that all nodes have degree at least k in the subgraph. The shell index of a node, the largest core it belongs to, is a measure of importance of the node. We propose and discuss exponential random graph models based on the core decomposition of a graph. This talk is based on joint work with Vishesh Karwa, Michael J. Pelsmajer, Sonja Petrovic and Dane Wilburne.
Properties of ideals in an invariant ascending chain (Uwe Nagel)
Hillar and Sullivant developed a framework for studying ideals in a polynomial ring S in countably many variables that are invariant under the action of a monoid. In particular, they showed that each P-invariant ideal in S is generated by finitely many P-orbits if P is the mononoid of increasing functions. This gives rise to invariant ascending chains of ideals. In order to study properties of the ideals in such a chain we introduce a bigraded Hilbert series and show that it is rational. This is based on joint work with Tim Romer.
Talk Material 1: / Talk Material 2: / Talk Material 4: /
KT 2
17:30 - 19:20 Welcome Party
Barbecue Place
19:30 - 20:00 Shuttle from NIMS to Hotel Interciti and Lotte City Hotel
Return to Hotel
TimeSpeaker/ Title/ Abstract/ VODLocation
08:00 - 08:45 Shuttle Bus to NIMS
Arrive at NIMS
09:00 - 10:00 IP03: P–adic Integration and Number Theory
Minhyong Kim (University of Oxford (United Kingdom) and Ewha Women's University),
Loading the live streaming player...
We will give an introduction to the computation of line integrals in non-Archimedean geometry, together with applications to the solution of polynomial equations.
KT 1
10:30 - 12:30 CP02: Contributed Session II
Gerhard Pfister (TU Kaiserslautern), Tim Hodges (Colorado State University), Marco Compagnoni (Politecnico di Milano),
Algorithms To Compute the Gorenstein Adjoined Ideal of a Curve (Gerhard Pfister)
We present new algorithms for computing adjoint ideals of curves and thus, in the planar case, adjoint curves. Our main algorithm yields the Gorenstein adjoint ideal G  of a given curve as the intersection of local Gorenstein adjoint ideals. We present a modular version of the algorithm which first computes a number of the characteristic p counterparts of G  and then lifts these to characteristic zero. As a key ingredient, we establish an efficient crite- rion to verify the correctness of the lift.
Choosing Good Paths for Homotopy Continuation (Tim Hodges)
The core method of Numerical Algebraic Geometry is Homotopy Continuation. This numerical method fails at singularities, and is costly near singularities. We propose a heuristic method to choose a “good” path between t = 1 and t = 0 for Homotopy Continuation. This is joint work with Dan Bates and Eric Hanson.
The Algebro-Geometric Study of TOA-based Localization Problems (Marco Compagnoni)
Localizing a radiant source is a common issue to many scientific and technological research areas. E.g. localization based on range measurements stays at the core of tech- nologies like radar, sonar and wireless sensors networks. We deeply study the model for source localization based on the measurements of the time of arrival (TOAs) of the source signal, from the point of view of algebraic geometry. In the case of three receivers, we found un- expected connections between this problem and the geometry of Kummer’s and Cayley’s surfaces. Our work gives new insights also on the localization based on time differ- ences of arrival.
Talk Material 1: / Talk Material 2: / Talk Material 3: /
10:30 - 12:30 MS16: Nonnegative Rank
Hyenkyun Woo (Korea University of Technology and Education), Kaie Kubjas (Aalto University), Wotao Yin (UCLA), Serkan Hosten (San Francisco State University),
Nonnegative Matrix Factorization for Nonnegative Rank (Hyenkyun Woo)
Nonnegative matrix factorization (NMF) is a natural computable candidate for nonnegative rank. However, due to the inherent nonconvex structure of matrix factorization, it shows strong drawback in finding optimal solution without using appropriate regularization. In this talk, we introduce Linf-norm regularization based asymmetric NMF and its usefulness in characterization of nonnegative rank. The main advantage of Linf-norm is that we could control denseness, i.e., sparsity, of each factor matrices of NMF.
Nonnegative Rank Boundaries (Kaie Kubjas)
In this talk, I will describe results related to the boundary of the semialgebraic set of matrices of nonnegative rank at most r, where r<5. The boundary plays an important role in nonconvex optimization on this set. Also, if there exists a rational matrix whose nonnegative rank over rationals is higher than its nonnegative rank over reals, then it will be a matrix on the boundary. For r=3, we have complete characterization of the boundary. For r=4, we know some components of the boundary, but we do not know if the list is complete. Finally I will present some open problems. This talks is based on joint work with Rob H. Eggermont, Emil Horobet, Elina Robeva and Bernd Sturmfels.
Some Recent Development in Operator Splitting Methods (Wotao Yin)
Operator splitting methods are the backbone of many first-order algorithms, ranging from alternating projection, to primal-dual algorithms, and to alternating direction method of multipliers (ADMM). They are simple, versatile, and nearly state-of-the-art at solving problems with multiple constraint sets, smooth and nonsmooth objective functions. This talk gives a high-level overview of operator splitting based algorithms, their basic analysis, recent development in parallel and distributed computing, and their recent ap- plications in convex and nonconvex optimization through a couple of examples.
Boundary Stratification of Binary Tensors of Nonnegative Rank Two (Serkan Hosten)
We study the boundary stratification of the semi-algebraic set of real tensors with nonnegative rank two and describe the "faces" this set in the interior of the probability simplex. We also elaborate on the implications of this stratification on the maximum likelihood estimation and the EM algorithm.
Talk Material 2: / Talk Material 4: /
KT 1
10:30 - 12:30 MS17: Coding Theory 3
Anton Betten (Colorado State University), Thomas Westerbäck (Aalto University), Alberto Ravagnani (University of Neuchâtel), Jon-Lark Kim (Sogang University),
The Grassmann Graph (Anton Betten)
The Grassmann graph is the discrete analogue of the Grassmannian from algebraic geometry. The elements of the graph are the subspaces of a fixed dimenion of a vector space over a finite field. Adjacency between subspaces is given whenever two subspaces intersect in a codi- mension one subspace. This graph is nice in the sense that it has interesting properties. For applications, the problem of choosing vectices in this graph subject to certain conditions is important. In finite geometry, one is interested in subspaces that are maximally apart from each other. This can be expressed in terms of the distance function in the graph. One object of study are spreads, which are useful for constructing interesting geometric structures such as translation planes. Special cases of spreads are semifield spreads, which have arisen recently in network coding. The talk is aimed at increasing the mutual understanding between these different fields.
On the Combinatorics of Repair Localities for Distributed Storage (Thomas Westerbäck)
Network coding techniques have rather recently been used for large scaled distributed storage, with applications to data centers, cloud storage systems, peer-to-peer systems and more. Important parameters for such distributed storage co- des are storage efficiently, repair efficiently and reliability. However, there is a trade-off between these parameters. Several distributed storage codes that support different local repair of the codewords symbol are being investigated. In this talk we will present how tools from algebraic combinatorics is connected to different repair localities and how these tools can be used in order to get new results in the area.
Rank-metric Codes: Duality and MacWilliams Identities (Alberto Ravagnani)
In this talk we focus on rank-metric codes from an alge- braic perspective. There exist two families of rank-metric codes, namely, Gabidulin and Delsarte codes. We prove that the duality theory of Delsarte codes extends the duality theory of Gabidulin codes. Moreover, we show how one can derive MacWilliams identities for Delsarte codes (and hence for Gabidulin codes) employing an elementary combinatorial argument.
Dimensions of Magic Squares and Magic Square Codes (Jon-Lark Kim)
Magic squares have a long history and intrigued many peo- ple including Fermat, Euler, Franklin, etc. Recently, Hou, Lecuona, Mullen, and Sellers in [1] have studied the di- mension of the vector space of magic squares over a field F except for the field of characteristic 2 or 3. In other words, if the characteristic of F is 2 or 3, exactly which n and k make M_{n,k}(1) nonempty, where M_{n,k}(1) de- notes the set of all n*n matrices over F whose row sums, column sums, k diagonal sums, and k antidiagonal sums are all 1. We solve this in [2] and describe how to solve it in this talk. Then we consider the codes obtained from these magic squares, called magic square codes. We give some open problems on magic square codes. References:[1] X.-d. Hou, A.G. Lecuona, G.L. Mullen, J.A. Sellers, On the dimension of the space of magic squares over a field, Linear Algebra and its Applications 438 (2013) 3463--3475.[2] W. Jung, J.-L. Kim, Y. Kim, K. Lee, The dimension of magic squares over fields of characteristics two and three, Linear Algebra and its Applications 472 (2015) 118--134.
Talk Material 1: / Talk Material 2: / Talk Material 4: /
10:30 - 12:30 MS18: Group Actions in Algebraic Geometry and Commutative Algebra
Kangjin Han (DGIST), Luke Oeding (Auburn University), David Swinarski (Fordham University), Jose Rodriguez (University of Notre Dame),
On singularities of third secant variety of Veronese embeddings (Kangjin Han)
In this talk, we report on singularities of third secant varieties of Veronese embedding v_d(\mathbb{P}^n), which corresponds to the variety of symmetric tensors of border rank at most three in (\mathbb{C}^{n+1})^{\otimes d} and consider its application.
Symmetrization of principal minors (Luke Oeding)
We analyze the Symmetrized Principal Minor Problem, that is to find the ideal of relations among the principal minors of matrices (arbitrary square, symmetric and skew symmetric) that have the additional property that all principal minors of equal size are equal. We show how this can be viewed as the symmetrization of the principal minor problem. We show how a special isomorphism (a non-linear change of coordinates to cycle sums) simplifies computation. I will report on our study for three cases, arbitrary square, symmetric and skew symmetric matrices. This is joint work with Huajun Huang.
Flattening stratifications and curves with automorphisms (David Swinarski)
Flattening stratifications have been a standard tool in algebraic geometry since the 1960s. A Grobner basis method for computing flattening stratifications was published by Nabeshima in 2010. I will discuss an application of flattening stratifications to finding equations of algebraic curves with automorphisms.
Galois groups via numerical algebraic geometry (Jose Rodriguez)
Galois groups are an important part of number theory and algebraic geometry. To a parameterized system of polynomial equations one can associate a Galois group whenever the system has k (finitely many) nonsingular solutions generically. The Galois group of a parameterized system is a subgroup of the symmetric group on k symbols. Using random monodromy loops it has been shown how to compute the Galois group when it is of maximal cardinality. In this talk we show how to compute Galois groups that are not of maximal cardinality. We conclude with an implementation using Bertini.m2, an interface to the numerical algebraic geometry software Bertini through Macaulay2.
Talk Material 1: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS19: Tensor Decomposition: Ideals meet Applications 1
Ke Ye (University of Chicago), Jaroslaw Buczynski (University of Warsaw), Ignat Domanov (KU Leuven), Insong Choe (Konkuk University),
Fast(est) Algorithms for Structured Matrices via Tensor Decomposition (Ke Ye)
It is well-known that the asymptotic complexity of matrix-matrix product and matrix inversion is given by the rank of a 3-tensor, recently shown to be at most O(n^2.3728639) by Le Gall. This approach is attractive as a rank decomposition of that 3-tensor gives an explicit algorithm that is guaranteed to be fastest possible and its tensor nuclear norm (according to Grothendieck and Schatten, not the mean of matrix nuclear norms obtained from flattening the tensor into matrices) quantifies the optimal numerical stability. There is also an alternative ap- proach due to Cohn and Umans that relies on embedding matrices into group algebras. We will see that the tensor decomposition and group algebra approaches, when com- bined, allow one to systematically discover fast(est) algorithms. We will determine the exact (as opposed to asymptotic) tensor ranks, and correspondingly the fastest algorithms, for products of Circulant, Toeplitz, Hankel, and other structured matrices. This is joint work with Ke Ye (Chicago).
The Hackbusch Conjecture on Tensor Formats (Jaroslaw Buczynski)
We prove a conjecture of W. Hackbusch about tensor net- work states related to a perfect binary tree and a train track tree. Tensor network states are used to present seemingly complicated tensors in a relatively simple and efficient manner. Each such presentation is described by a binary tree and a collection of vector spaces, one for each vertex of the tree. A problem suggested by Wolfgang Hackbusch and Joseph Landsberg is to compare the com- plexities of encodings, if one presents the same tensor with respect to two different trees. We answer this question when the two trees are extremal cases: the most "spread" tree (perfect binary tree), and the "deepest" binary tree (train track tree). The corresponding tensor formats are called hierarchical formats (HF) and tensor train (TT) for- mats, respectively.(joint work with Weronika Buczynska, Mateusz Michalek)
On Generic Uniqueness of Structured Matrix Factorizations. Applications to Tensor Decompositions and Blind Source Separation (Ignat Domanov)
On Generic Uniqueness of Structured Matrix Factorizations. Applications to Tensor Decompositions and Blind Source Separation. The task of Blind Source Separation (BSS) is to recover unknown sources from their observed mixtures. Similarly, in Data Analysis (DA) one tries to split observed data into meaningful, interpretable components. In general, if the noise is neglected, the BSS and DA problems can be for- mulated as a structured matrix factorization problem: given a matrix X, find structured matrices M and S such that X=MS, where the rows of S and X represent unknown source signals and their observed linear mixtures, respectively. In practice it is assumed that the equationX=MS has a solution and one wants to know whether it is unique before trying to compute it. We con- sider the case where the source signals can be modeled as points on a unirational variety (that is, the entries of the source signals are fixed (multivariate) polynomials or rational functions evaluated at some points). We present an easy to verify conditions which guarantee that the factori- zation X=MS is unique with probability one. We apply this result to prove the generic uniqueness of: 1. array re- sponse matrix in direction of arrival estimation; 2. mixing matrix in independent component analysis; 3. a number of tensor decompositions (canonical polyadic decomposition, decomposition in multilinear rank-(L,L,1) terms, coupled tensor decomposition).Joint work with: Lieven De Lathauwer, Mikael Sorensen
Maximal Subbundles over a Curve and Related Secant Varieties (Insong Choe)
Classically, Lange and Narasimhan studied minimal sections of a ruled surface using the secant varieties of the base curve. We discuss how to generalize this framework to the setting of arbitrary vector bundles, symplectic bundles, and orthogonal bundles over a curve. It turns out that there are related secant varieties of Segre bundles, Veronese bundles, and Grassmannian bundles, respectively. We also explain the relation between the number of maximal sub- bundles and the secant order. This talk is based on a series of joint works with George H. Hitching.
Talk Material 1: / Talk Material 2: / Talk Material 4: /
KT 2
10:30 - 12:30 MS20: Applications of Computational Algebraic Geometry to Theoretical Physics 2
Yang-Hui He (City University, London, Nankai University, China and Merton College, Oxford University), Michael Stillman (Cornell University), Cyril Matti (City University, London),
Gauge Theory &Calabi-Yau Spaces: Physics, Mathematics and Computation (Yang-Hui He)
The fruitful interaction between the physics of gauge theo- ries and the mathematics of Calabi-Yau manifolds, espe- cially in the context of string theory, has blossomed over the last 2 decades. We will discuss a few aspects of how, with the aid of modern computational algebraic geometry, the gauge theory of particle physics has been harnessing the rich structure of Calabi-Yau spaces to construct worlds akin to ours and vice versa, how such explorations have led to new mathematics.
Applications of Computational Algebraic Geometry to Vacuum Moduli Spaces of Supersymmetric Models in Physics (Michael Stillman)
Given a supersymmetric potential function, such as one for the MSSM (minimal super-symmetric extension of the standard model of particlephysics), there is a naturally as- sociated affine algebraic variety, which is (essentially) the moduli space of possible vacua of the theory. In this talk we describe the structure of some of these moduli spaces, including the Electro-weak sector of the MSSM, which were obtained with the help of computational algebraic ge- ometry and Macaulay2. We consider theories where one allows for more than 3 generations of particles. Since nature seems to have chosen 3 generations, theories for which this number of generations is forced would be ideal. Although it does not appear that 3 generations is forced here, we see how the geometry varies with different num- bers of generations of particles. We will assume no knowl- edge of physics during this talk. We will briefly describe the physics needed, and then we will describe the algebraic geometric and computational methods and results which allow the structure to become apparent. This talk is based on the recently published, as well as more recent work. Joint work with: Yang-Hui He (Oxford and City University London, UK), Vishnu Jejjala (University of the Witwatersrand, Johannesburg, South Africa), Cyril Matti (City University, London, UK), Brent Nelson (Northeastern University, USA)
Algebraic Geometry and the Vacuum of Supersymmetric Gauge Theories (Cyril Matti)
Based on recent developments in understanding the vac- uum moduli space of supersymmetric gauge theories, this talk will present the role of algebraic geometry to obtain information on the vacuum structure. The presentation will describe geometric properties that naturally arise from the solution of F-flatness and D-flatness conditions in the context of electroweak supersymmetric theories, and the in sight that can be gathered from algebraic geometry towards developing a selection mechanism for theoretical model building.
Talk Material 1: / Talk Material 3: /
10:30 - 12:30 MS21: Maximum Likelihood Degrees and Critical Points 1
Xiaoxian Tang (NIMS), Jose Rodriguez (University of Notre Dame), Serkan Hosten (San Francisco State University), Elizabeth Gross (San Jose State University),
Data-Discriminants of Likelihood Equations (Xiaoxian Tang)
Maximum likelihood estimation (MLE) is a fundamental computational problem in statistics. An algebraic approach is to solve a very structured parameterized polynomial system called likelihood equations. The only solutions of the likelihood equations that are statistically meaningful are the positive solutions. In order to classify the data according to the number of real/positive solutions, we define the data-discriminant for the likelihood equations. We develop an algebraic probability 1 algorithm for computing data-discriminants. Experimental results show that, for the benchmarks we have tried, the algebraic probability 1 algorithm is more efficient than the standard elimination algorithm. Based on the computational results, we propose the real root classification conjecture for the 3 by 3 symmetric matrix model. Joint work with Jose Israel Rodriguez
Maximum Likelihood for Dual Varieties (Jose Israel Rodriguez)
Maximum likelihood estimation (MLE) is a fundamental computational problem in statistics. In particular, MLE for statistical models with discrete data can studied from an algebraic statistics viewpoint. In this talk, we review such a viewpoint and give a formulation for maximum likelihood estimation in terms of dual varieties. With this description, the dual likelihood equations are defined. We show that solutions to the dual likelihood equations yields solutions for MLE.
ML Degree of Toric Models in Algebraic Statistics (Serkan Hosten)
The ML Degree of a toric variety is the Euler characteristic of a hypersurface associated to the log-likelihood function in that toric variety. Despite this general result, computing the ML degree of specific toric varieties is a challenge. We will report on progress for computing the ML degree of toric and related varieties that appear in algebraic statistics, such as hierarchical log-linear models.
Sampling zeros, model zeros, and the maximum likelihood degree (Elizabeth Gross)
Given a statistical model, the maximum likelihood degree is the number of complex solutions to the likelihood equations for generic data, or equivalently, the degree of the likelihood locus. In this talk, we consider discrete algebraic statistical models and explore the solutions to the likelihood equations when the data are no longer generic, but instead contain zeros. In this case, with the help of numerical algebraic geometry, we see that the solutions partition into two clusters, solutions to the likelihood equations for sampling zeros and solutions that lie on the coordinate hyperplanes. Using this fact, we show how the problem of finding critical points to the likelihood function can be partitioned into smaller and computationally easier problems involving sampling and model zeros. This is joint work with Jose Rodriguez.
Talk Material 2: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS22: Pairings in Cryptography I
Sorina Ionica (University of Bordeaux), Peter Schwabe (Radboud University),
Fast Scalar Multiplication in Pairing Groups (Sorina Ionica)
When implementing a pairing-based protocol, there are two main operations to perform: scalar multiplications of points on the elliptic curve and pairings. Achieving optimal performance means choosing the elliptic curve in such a way that both primitive operations will be fast. The GLV and GLS methods offer significant speed up over basic algorithms for scalar multiplication. It is thus natural to investigate the existence of pairing-friendly curves for which GLV/GLS algorithms are available. In this talk, we review recent developments on the GLV/GLS algorithm and present a new approach for constructing GLV/GLS pairing-friendly curves.
PandA: Pairings and Arithmetic (Peter Schwabe)
Research on pairing-based cryptography is mainly divided into two lines. On the one hand research into cryptographic protocols that use pairings and on the other hand research into the mathematical and algorithmic foundations that enable those protocols. There are of course examples where these two lines of research find together, but too often they are progressing independently. In this talk I will present PandA, a framework that aims at bringing these two lines of research together by offering an easy way to implement protocols through an easy-to-use API that also allows to easily integrate advances in pairing computation and operations in the related groups.
Talk Material 1: / Talk Material 2: /
12:30 - 14:00 Lunch
Cafeteria 1, 2
14:00 - 15:00 IP4: Applications of Numerical Algebraic Geometry
Jonathan Hauenstein (University of Notre Dame),
Loading the live streaming player...
In broad terms, numerical algebraic geometry follows a computational geometric approach to solving systems of polynomial equations. This geometric approach has facilitated solving numerous problems in science and engineering throughout the past several decades. In this talk, I will survey some recent applications involving the use of numerical algebraic geometry including tensor decomposition, steady-state solutions to differential equations, and mechanism synthesis in kinematics.
KT 1
15:30 - 17:30 MS23: Real Algebraic Geometry and Optimization 1
Raman Sanyal (Freie Univertitaet Berlin), Mohab Safey el Din (Université Pierre et Marie Curie), Yoshiyuki Sekiguchi (Tokyo University of Marine Science and Technology), Martina Juhnke-Kubit (University of Osnabrück),
Theta ranks of matroids (Raman Sanyal)
For a finite point configuration V, the Theta rank is the minimal degree required to represent any nonnegative linear function on V as a sums of squares. In general, this invariant is difficult to compute and little is known about configurations of bounded Theta rank. For configurations arising from matroids, the Theta rank is monotone with respect to taking minors and hence furnish excluded minors for matroids of bounded Theta rank. In this talk, I will discuss results and problems regarding excluded minor characterizations for Theta rank and relations to other geometric and algebraic properties. This is joint work with Francesco Grande.
Exact algorithm for polynomial optimization (Mohab Safey El Din)
In some critical applications, polynomial optimization problems arise with large coefficients (e.g. more than 200 bits as input) which make the use of numerical routines extremely difficult for solving these problems.  In this talk, I will present an algorithm for solving exactly polynomial optimization problems. Its complexity is essentially cubic the worst-case output size. Its practical performances allow to tackle problems that are out of reach of the current state-of-the-art.
Optimality conditions of polynomial optimization (Yoshiyuki Sekiguchi)
In optimization theory, there are various kinds of optimality conditions. They guarantee good behaviors of algorithms and are also used to give necessary condition for a nonnegative polynomial to be a sum of squares (SOS). In this talk, we study how optimality conditions of polynomial optimizations affect the generated semidefinite programs and sos-representability of objective functions.
Gap vectors of real projective varieties (Martina Juhnke-Kubitzke)
Given a totally real, non-degenerate, projective variety $X\subseteq \PP^m$ and a generic set of points $\Gamma\subseteq X(\RR)$, we consider the cone  $P$ of nonnegative quadratic forms on $X$ and the cone $\Sigma$ of sums of squares of linear forms. We examine the dimensions of the faces $P(\Gamma)$ and $\Sigma(\Gamma)$ consisting of forms in $P$ and $\Sigma$, which vanish on $\Gamma$. As the cardinality of the set $\Gamma$ varies in $1,2,\dots,\codim(X)$, the difference between the dimensions of $P(\Gamma)$ and $\Sigma(\Gamma)$ defines a numerical invariant of $X$, the so-called gap vector of $X$.  We study fundamental properties of this vector and provide a formula relating the components of the gap vector of $X$ and the quadratic deficiencies of $X$ and its generic projections. Using it, we prove that gap vectors are weakly increasing, obtain upper bounds for their rate of growth and prove that these upper bounds are eventually achieved for all varieties. Moreover, we give a characterization of the varieties with the simplest gap vectors.
Talk Material 3: /
15:30 - 17:30 MS24: Coding Theory and Cryptography 1
Kirill Morozov (Kyushu University), Moon Sung Lee (Seoul National University), Daniel Smith (University of Louisville), Jon-Lark Kim (Sogang University),
Code-Based Designated Confirmer Signatures (Kirill Morozov)
We present the first code-based designated confirmer sig- nature scheme using the ``Signature of an Encryption'' paradigm by El Aimani. As main ingredients, we use an IND-CPA variant of the McEliece public-key encryption and the cryptographic protocols presented by Jain, Krenn, Pietrzak and Tentes at Asiacrypt 2012. A novel technique which we propose is the zero-knowledge proof that a given McEliece ciphertext does not contain a given plaintext, which may be of independent interest.
Recent Developments of Fully Homomorphic Encryptions (Moon Sung Lee)
Fully Homomorphic Encryption (FHE) is an encryption scheme which allows arbitrary computations on encrypted data without decrypting. In spite of significant improvements, FHEs are considered to be far from practical for most applications due to their slow performance and large ciphertext size. In this talk, we introduce recent improvements on the performance of FHEs. We conclude this talk by introducing several applications of FHEs.
Solving Systems of Equations using Differential Techniques (Daniel Smith)
We will discuss some of the tools available to speed up multivariate nonlinear equation solving via differential structure. We will also discuss the limits of these techniques, and methods of proving the existence or non existence of such structure in multivariate public key cryptosystems.
Secret Sharing Schemes Based on Additive Codes (Jon-Lark Kim)
A secret sharing scheme (SSS) is a method of distributing a secret to a finite set of participants such that only pre- defined subsets of the participants can recover the secret. The secret sharing schemes based on linear codes have been studied by many researchers. There are limited classes of linear codes over fields whose access structures can be computed from the weight enumerators of the line- ar codes. Hence it is natural to ask whether additive codes can be used to construct SSSs. This talk is the first attempt to study SSSs from the viewpoint of additive codes. We describe the structure theorem in terms of additive co- des, in particular over GF(4). We compare the perform- ances of SSSs based on linear codes and additive codes.
Talk Material 1: / Talk Material 2: / Talk Material 4: /
15:30 - 17:30 MS25: Software and Applications in Numerical Algebraic Geometry 2
Frank Sottile (Texas A&M University), Maria Isabel Herrero (University of Buenos Aires - CONICET), Gregorio Malajovich (Universidade Federal do Rio de Janeiro),
Generalized Witness Sets (Frank Sottile)
The fundamental data structure in numerical algebraic ge- ometry is that of a witness set, which is considered to be an instantiation of Weil's notion of a generic point. Reinterpreting a witness set in terms of duality of the intersection pairing in intersection theory leads to a generalization of the notion that makes sense on many spaces and leads to a general notion of a witness set. This gen- eral notion for products of projective spaces becomes that of a multihomogeneous witness set. My talk will explain the general theory, but focus on multihomogeneous witness sets and sketch some algorithms based on this notion. This is joint work with Leykin and Hauenstein.
Algorithms for Solving Sparse Polynomial Systems (Maria Isabel Herrero)
Polynomial system solving is a fundamental problem both from a practical and a theoretical point of view. Considering its applications, it is of special interest the study of sparse polynomial systems, that is, systems given by polynomials that involve monomials in prefixed sets. Bernstein's theorem, which is considered the basis of the study of sparse polynomial systems, led to the development of sparse elimination theory. A wide variety of effective numerical and symbolic algorithms for solving sparse systems have been developed. In joint works with Gabriela Jeronimo and Juan Sabia, we presented new probabilistic algorithms that, combining symbolic methods with techni- ques from numerical algebraic geometry, have complexity bounds depending on geometric-combinatorial invariants as- sociated with the support set of the input polynomials. I will present an overview of these results and explain how we use numerical tools such as witness sets in the sym- bolic context.
Computing Mixed Volume and All Mixed Cells (Gregorio Malajovich)
The mixed volume counts the roots of generic sparse pol- ynomial systems. Mixed cells are used to provide starting systems for homotopy algorithms that can find all those roots, and track no unnecessary path. Up to now, algo- rithms for that task were of enumerative type, with no general non-exponential complexity bound. A geometric al- gorithm was introduced in my paper, "Computing mixed volume and all mixed cells in quermassintegral time," with complexity bounds in terms of a certain quermassintegral. This algorithm was implemented as part of pss5 (Polynomial System Solver version 5) which may be avail- able in at the time of the conference.
Talk Material 1: / Talk Material 2: / Talk Material 3: /
KT 1
15:30 - 17:30 MS26: Tropical Geometry 3
Timo de Wolff (Texas A&M University), Yue Ren (TU Kaiserslautern), Emmanuel Tsukerman (UC Berkeley), Simon Hampe (University of Warwick),
Roots of Trinomials from the Viewpoint of Amoeba Theory (Timo de Wolff)
The behavior of norms of roots of univariate complex trinomials for fixed support with respect to the choice of coefficients is a classical late 19th and early 20th century problem. Although algebraically characterized by P. Bohl in 1908, the geometry and topology of the corresponding parameter space of coefficients has not been revealed yet. We provide such a characterization for the space of trinomials by reinterpreting the problem in terms of amoeba theory. The roots of given norm are parameterized in terms of a hypotrochoid curve along slices of the space of trinomials. Multiple roots of this norm appear exactly as the singularities of this curve. Our main result states that the set of all trinomials with identical support and certain roots of identical norm can be deformation retracted to a torus knot and thus are connected but not simply connected. These results are joint work with Thorsten Theobald.
Tropical computations over valued fields with classical Computer algebra (Yue Ren)
Computing tropical varieties over the field of Puiseux series in t over the complex numbers is a well-solved problem, see the works of Bogart, Jensen, Speyer, Sturmfels and Thomas. Either, we are in the so-called constant coefficient case, in which we can pretend that we are working over the complex numbers, or we are in the general case, in which we can pretend that t is a variable in our polynomial ring and then work over the complex numbers anyways. However, if the valued field does not play along as nicely as $\mathbb{C}\{\!\{t\}\!\}$, say the field of $p$-adic numbers $\mathbb{Q}_p$, we are quickly entering a domain in which the classical tools of computer algebra seem insufficient for our problem at hand. This lead to a series of works, most notably by Andrew Chan and Diane Maclagan, which successfully generalize the classical theory of computer algebra to valued fields, taking the valuation into account. In this talk, I will present an alternative approach. Generalizing the trick for Puiseux series to arbitrary valued fields, it turns out that the classical toolbox of computer algebra is sufficient for determining tropical varieties over, say, $\mathbb{Q}_p$ after all. I will talk about the central ideas behind the approach, touch upon the theoretical challenges that arise during it and showcase some examples using SINGULAR. This is joint work with Thomas Markwig.
Tropical spectral theory of tensors (Emmanuel Tsukerman)
We introduce and study tropical eigenpairs of tensors, a generalization of the tropical spectral theory of matrices. We show the existence and uniqueness of an eigenvalue. We associate to a tensor a directed hypergraph and define a new type of cycle on such a hypergraph, which we call an H-cycle. The eigenvalue of a tensor turns out to be equal to the minimal normalized weighted length of H-cycles of the associated hypergraph. We show that the eigenvalue can be computed efficiently via a linear program.
Tropical convexity and tropical linear spaces (Simon Hampe)
In the world of tropical arithmetic, addition is replaced by the maximum (or minimum, depending on your personal taste) and multiplication is replaced by ordinary addition. Develin and Sturmfels first defined the notion of "tropical convexity" in this setting. It simply means being closed under tropical linear combinations. One can then define a notion of tropical polytopes and many well-known facts from "normal" polyhedral geometry are also true in the tropical setting. In tropical algebraic geometry, one replaces algebraic varieties with weighted polyhedral complexes (their "tropicalizations"), which can be studied with combinatorial and polyhedral methods. Matroidal fans play an important role in this setting. They are polyhedral fans that are defined (in various, equivalent ways that we likely will not bother with in this talk) via matroids. Furthermore, they occur as tropicalizations of linear spaces, which led to them being called "tropical linear spaces". We will give another motivation for this terminology: We will see that, among tropical fans, matroidal fans are exactly the tropically convex ones, i.e. the ones that are closed under tropical linear combinations.
Talk Material 2: / Talk Material 3: / Talk Material 4: /
15:30 - 17:30 MS27: Spectral Theory of Tensors and Tensor Rank 2
Mitsuhiro Miyazaki (Kyoto University of Education), Luke Oeding (Auburn University), Elina Robeva (UC Berkeley), Youngho Woo (NIMS),
About typical ranks of real tensors (Mitsuhiro Miyazaki)
Let $m$, $n$ and $p$ be integers larger than 1. Suppose that an $m\times n\times p$ tensor $T$ with entries in real number field is chosen randomly. If $r$ is an integer such that the probability of $\rank T=r$ is positive, then $r$ is called a typical rank of $m\times n\times p$ tensors over the real number field. We consider when there are plural typical ranks and give a criterion in the case when $p$ is large compared to $m$ and $n$. This is joint work with Toshio Sumi and Toshio Sakata.
Frame Decomposable Tensors (Luke Oeding)
A frame decomposable tensor is a natural generalization of an ODECO tensor, studied recently by Robeva. I will explain this generalization and our initial progress toward giving an algebraic characterization of the variety of frame decomposable tensors of a given rank, degree and number of variables. This is work in progress with Elina Robeva and Bernd Sturmfels.
Orthogonally decomposable tensors (Elina Robeva)
Orthogonal decomposition of tensors is a generalization of the spectral theorem decomposition for symmetric matrices and the singular value decomposition for nonsymmetric matrices. Unlike in the matrix case, not all tensors are orthogonally decomposable. On the other hand, all such tensors have eigenvectors corresponding to the vectors in their orthogonal decomposition and using the tensor power method one can find these eigenvectors and hence recover the orthogonal decomposition efficiently. We discuss the spectral properties of orthogonally decomposable tensors as well as the variety of such tensors. We also discuss generalizations of the notion of orthogonally decomposable tensors that allow the tensor rank to be larger.
Waring rank of some polynomials and Strassen additive conjecture (Youngho Woo)
We will introduce a new notion “e-computablity” of rank of polynomials and give a large family of examples which are e-computable. This is a generalization of the method to computing rank of monomials developed by Carlini, Catalisano and Geramitta. We verify the Strassen additive conjecture for such forms. This is a joint work with E.Carlini, M.Catalisano, L.Chiantini and A.Geramitta.
Talk Material 1: / Talk Material 3: /
15:30 - 17:30 MS28: Algebraic Structures arising in Systems Biology 2
Mercedes Soledad Perez Millan (University of Buenos Aires), Elisenda Feliu (University of Copenhagen), Carsten Wiuf (University of Copenhagen), Bernd Sturmfels (UC Berkeley (USA) / NIMS),
Steady States of MESSI biological systems (Mercedes Perez Millan)
Many processes within cells involve some kind of post-translational modification of proteins. We introduce here a general framework for biological systems that describe Modifications of type Enzyme-Substrate or Swap with Intermediates, which we call MESSI systems. Examples of MESSI systems are the sequential distributive or processive multisite phosphorylation networks, phosphorylation cascades, and the bacterial EnvZ/OmpR network. Assuming mass-action kinetics, we simplify the study of steady states and conservation laws of these systems by explicit elimination of intermediate complexes (inspired by [Feliu and Wiuf 2013, Thomson and Gunawardena 2009]). We also describe an important subclass of MESSI systems with toric steady states. This is joint work with Alicia Dickenstein.
Model reduction and multistationarity (Elisenda Feliu)
In general, the complexity of determining whether a reaction network exhibits multistationarity grows with network size. Methods to infer the existence of multistationarity from that of a smaller, but related, network are thus useful. Furthermore, such methods might provide tools to understand how the steady states of a system change under model reduction. In this talk I will discuss several scenarios where comparison of the steady states can be done and multistationarity of a big network can be inferred from smaller networks. I will especially focus on the comparison of steady states between a network and a reduced network obtained by linear elimination of species concentrations. The content of the talk is joint work with Daniele Cappelletti, Meritxell Sáez and Carsten Wiuf.
The relationship between stochastic networks and complex balanced deterministic networks (Carsten Wiuf)
Models of systems of biochemical reactions go back more than 100 years in biology. Standard deterministic models are based on systems of polynomial ODEs and standard stochastic models are based on discrete Markov processes. In this talk, we study a particular relationship between these two types of models. For some time it has been known that ODE models with a certain algebraic property (complex balanced steady state) give rise to stochastic models with Poisson-type stationary distributions (describing the long term behavior of the system). In this talk I study the reverse of this statement: if the stationary distribution is Poisson-type, is the deterministic system complex balanced? This work is joint with Daniele Cappelletti.
Rational Design of Antibiotic Treatment Plans (Bernd Sturmfels)
We present work with Portia Mira, Kristina Crona, Devin Greene, Juan Meza and Miriam Barlow, aimed at developing antibiotic treatment plans that can reverse the evolution of antibiotic resistance. The Barlow lab at UC Merced generated adaptive landscapes for 16 genotypes of the TEM beta-lactamase that vary from the wild type genotype TEM-1 through all combinations of four amino acid substitutions, and determined the growth rate of each genotype when treated with each of 15 beta-lactam antibiotics. Using growth rates for fitness in two models from population genetics, we computed the probability of each amino acid substitution in each beta-lactam treatment, and we searched through the 15 treatments for substitution paths leading from each of the 16 genotypes back to TEM-1. We identified treatment paths with the highest probabilities of returning TEM to the wild type state, thus offering promise for reversing the evolution of resistance to antibiotics. This lecture highlights the mathematics in this project.
Talk Material 1: / Talk Material 4: /
15:30 - 17:30 MS29: Algebraic Structure in Graphical Models 2
Po-Ling Loh (University of Pennsylvania), Gautam Dasarathy (Carnegie Mellon University), Seth Sullivant (North Carolina State University), Sung-Ho Kim (KAIST),
On Model Misspecification and KL Separation for Gaussian Graphical Models (Po-Ling Loh)
We study the problem of bounding the KL divergence between two multivariate Gaussian distributions in terms of the Hamming distance between the edge sets of the corresponding graphical models. We show that the KL divergence is bounded below by a constant when the graphs differ by at least one edge; furthermore, this is essentially the tightest possible bound we may obtain, since classes of graphs exist for which the edge discrepancy increases but the KL divergence remains bounded above by a constant. As a natural corollary to our KL lower bound, we also establish a sample size requirement for correct model selection via maximum likelihood estimation. Our results rigorize the notion that it is essential to estimate the edge structure of a Gaussian graphical model accurately in order to approximate the true distribution to close precision. This is joint work with Varun Jog.
On the Data Requirement for Learning the Tree of Life from Multiple Genes (Gautam Dasarathy)
Inferring the "tree of life" from genetic data is an important problem in evolutionary biology. It has been customary to think about this problem as one of learning the evolutionary history of a single gene. However, individual genes might have evolutionary histories that are (topologically) distinct from each other and, of course, from the underlying tree of life. In this talk, I will discuss a probabilistic model of evolution that takes this into account and allows us to model the scenario using a mixture of graphical models. I will then outline our recent theoretical explorations into questions such as reliable algorithms for learning the tree of life from several genes and the tradeoffs between the quality and the quantity of data required for such algorithms to succeed.
The Maximum Likelihood Threshold of a Graph (Seth Sullivant)
The maximum likelihood threshold of a graph is the smallest number of data points that guarantees that maximum likelihood estimates exist almost surely in the Gaussian graphical model associated to the graph. We show that this graph parameter is connected to the theory of combinatorial rigidity. In particular, if the edge set of a graph G is an independent set in the n−1-dimensional generic rigidity matroid, then the maximum likelihood threshold of G is less than or equal to n. This connection allows us to prove many results about the maximum likelihood threshold. This is joint work with Elizabeth Gross.
Selection of Shrinkage Parameter for High-Dimensional VAR Models under a Bayesian Framework (Sung-Ho Kim)
In this talk, we will present a Bayesian approach for modelling a high-dimensional vector autoregressive (VAR) model using small data. A main idea behind the approach is that we apply shrinkage estimation for estimating coefficients of the model where the shrinkage index is regarded as a hyper-parameter of the prior distribution of the coefficients. For selecting an optimal value of the shrinkage index, we use a new score function that is asymptotically related to the mean squared error of the coefficient estimates. The selection is carried out by applying a variation of cross-validation. The proposed approach is shown to compare favorably with methods in literature and is applied to gene plant expression data and fMRI data.
Talk Material 1: / Talk Material 4: /
KT 2
15:30 - 17:30 MS30: Class Groups of Global Fields
Hwanyup Jung (Chungbuk National University), Jungyun Lee (Ewha Womans University), Yoonjin Lee (Ewha Womans University), Yuichiro Taguchi (Kyushu University),
The Statistics of the Number of Rational Points in the Hyperelliptic Ensemble over Finite Fields (Hwanyup Jung)
We will give a talk on the distribution of the numbers of F_{q^r}-rational points of hyperelliptic curves over a finite field F_q in odd and even characteristic. This extends the result of Kurlberg and Rudnick in odd characteristic case and of Entin in even characteristic case. This is joint work with Prof. Bae.
Indivisibility of Class Numbers of Real Quadratic Function Fields (Jungyun Lee)
We study on indivisibility of the class numbers of real quadratic function fields. We find an explicit expression for a lower bound of the density of real quadratic function fields whose class numbers are not divisible by a given prime. We point out that the explicit lower bound of such a density we found only depends on the prime and the degrees of the discriminants of real quadratic function fields. (This is joint work with Yoonjin Lee.)
Construction of All Cubic Function Fields of a Given Discriminant (Yoonjin Lee)
We present a method for generating all cubic function fields of a given discriminant D, where D is a square-free polynomial over a finite field of characteristic at least 5. We also provide a count of all these fields according to their splitting at infinity. When D' = D/(-3) is the discriminant of a real quadratic function field, this method makes use of the infrastructure of this field. This infrastructure method was first proposed by D. Shanks for cubic number fields in an unpublished manuscript from the late 1980s. While the mathematical ingredients of our construction are largely classical, our algorithm has the major computational advantage of finding very small minimal polynomials for the fields in question. (This is joint work with M. Jacobson, R. Scheidler and H. Williams)
On the Hecke Fields of Galois Representations (Yuichiro Taguchi)
It is known that, in many cases, the field (known as the Hecke field) generated by all Hecke eigenvalues of an elliptic modular newform is in fact generated by its p-th the Hecke eigenvalue for a single prime number p. We present some results on the density of such primes in a more general situation in terms of Galois representations. They are applied to the study of the fields of rationality of certain automorphic representations. This is joint work with Dohoon Choi..
Talk Material 1: / Talk Material 4: /
18:00 - 19:30 Poster Session & Reception
CAMP Lounge
19:30 - 20:00 Shuttle from NIMS to Hotel Interciti and Lotte City Hotel
Return to Hotel
TimeSpeaker/ Title/ Abstract/ VODLocation
08:00 - 08:45 Shuttle Bus to NIMS
Arrive at NIMS
09:00 - 10:00 IP05: Algebraic Codes and Invariance
Madhu Sudan (Microsoft),
Loading the live streaming player...
Algebraic error-correcting codes hold a central place in coding theory due to three, potentially unrelated, features. The most well-known feature is perhaps the combinatorial aspect: (1) Algebraic code pack Hamming space extremely densely, often outperform random error-correcting codes. Less well-known are the (2) Multiplicative property: Algebraic codes come endowed with a product operation where products of codewords remain far from each other and (3) Symmetries: Many algebraic codes are endowed with a rich group of symmetries that enable powerful uses of these codes. In this talk I will briefly review algebraic codes and the first two properties, before turning to the third part and talk about recent works highlighting the role of symmetries in (mathematical) uses of error-correcting codes.
KT 1
10:30 - 12:30 MS31: Real Algebraic Geometry and Optimization 2
Daniel Plaumann (University of Konstanz), Bernard Mourrain (INRIA Sophia Antipolis), Anne Shiu (Texas A&M University), Bruce Reznick (University of Illinois),
Growth rates of real polynomials (Daniel Plaumann)
The simplest measure for the growth rate of a real polynomial in several variables is its total degree. However, this may be inappropriate when restricting to a subvariety or semi-algebraic set. We construct suitable compactifications of semi-algebraic sets to obtain refined notions of degree. This works especially well in a toric setup, relating to results of Mondal, Netzer and Vinzant. We also discuss applications to the moment problem in functional analysis. (Joint work with Claus Scheiderer)
Exact relaxation for polynomial optimization on semi-algebraic sets (Bernard Mourrain)
To compute the infimum of a real polynomial function f on a closed basic semi-algebraic set S, Lasserre relaxation consists in constructing a hierarchy of Semi-Definite Programmes, which converges to the infimum. If the hierarchy is exact, that is, the optimum is reached in a finite number of steps, it can also be used to compute the minimizers when they exists. Exact relaxations are known in special cases, e.g. archimedian, constraints with Boundary Hessian Condition, regular constraints. We show that exact SDP hierarchies can be constructed in general, in order to compute the minimum and the defining ideal of the minimizer points or to detect that there is no solution to the optimization problem. For that purpose, we analyze the properties of the critical varieties associated to the optimization problem, namely the  Fritz John variety and the Karush-Kuhn-Tucker variety. We show that the exactness of the relaxation depends only on the real points which satisfy these constraints. The approach provides a uniform treatment of different optimization problems considered previously. We illustrate it on some  examples, including  optimization on smooth real algebraic varieties, real radical computation.
Polynomial systems arising from biochemical reaction networks (Anne Shiu)
A chemical reaction network gives rise to a parametrized family of polynomial systems of ODEs by way of mass-action kinetics.  An important question is the following: which reaction networks admit multiple steady states, that is, which of these polynomial systems have multiple positive solutions? There is no complete answer to this question, but over the last 40 years various criteria have been developed that can answer this question in certain cases. This talk surveys these developments and highlights some open questions.
On the number of zeros of a real psd ternary form without indefinite factors (Bruce Reznick)
In 1980, Choi, Lam and the speaker proved that if a psd ternary sextic has more than 10 zeros, then it has a square indefinite factor, infinitely many zeros and is sos. We discuss the situation in higher degree, including examples of Harris. This is, in part, joint work with Greg Blekherman.
Talk Material 1: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS32: Coding Theory 4
Edgar Martinez-Moro (University of Valladolid), Lingfei Jin (Fudan University), Felice Manganiello (Clemson University), Shuhong Gao (Clemson University),
Combinatorics of the fan associated to a linear code (Edgar Martinez-Moro)
We will show how the fan associated to a code with respect to a degree compatible ordering (defined in a combinatorial way) contains a great information about the code (note the resemblance with toric ideals). Some applications to the code equivalence problem and to the computation of generalized Hamming weights will be shown.
New binary codes from rational function fields (Lingfei Jin)
Since the birth of coding theory, it has been always a great challenge to construct good binary codes. In this talk,we present an algebraic construction of binary codes through rational function field. We make use of a certain multiplicative group of rational functions for our construction. In particular, the point at infinity can be employed to our construction to get codes of length up to q+1, where q is the ground field size. As a result, several new binary constant weight codes are found and many new binary nonlinear codes are given.
On communication over networks via skew polynomials (Felice Manganiello)
In this seminar we will explore network communication schemes based on particular mathematical structures. It has been proven that linear network coding is enough to achieve the capacity of multicast networks. We are going to talk about the generalization of linear coding to a technique based on matroids. We then focus on the ring of skew polynomials, study the matroid structure behind their zero locus and see the benefit of applying this matroid to multicast networks. This is a joint work with Frank Kschischang and Siyu Liu.
Fast Decoding of Linear Codes from Expander Graphs (Shuhong Gao)
Expander graphs are highly connected finite graphs. A d-regular graph with good expansion property and a code of length d (called an inner code) give a good linear code, called an expander code or a Tanner code. The code properties can be based on edge expansion or vertex expansion of graphs. On edge expansion, Lubotsky, Phillips and Sarnak (1988) give explicit construction of infinite families of Ramanujan graphs, and it is shown by Sipser and Spielman (1996), Zemor (2001), and Roth and Skachek (2006) that the expander codes from these graphs are asymptotically good and can be decoded in linear time. This talk focuses on codes based on vertex expansion where one needs bipartite (c,d)-regular graphs and an inner code of length d. Capalbo, Reingold, Vadhan and Wigderson (2002) give explicit construction of infinite families of bipartite graphs with any desired vertex expansion. For decoding algorithms, the progress is little slow. When the vertex expansion is greater than 3/4, Sipser and Spielman (1996) gives a linear time decoding algorithm, later Feldman et al (2007) shows how to use linear programming to lower the expansion to 2/3 + 1/(2c) (with polynomial time), and recently Viderman (2013) gives a linear time decoding algorithm for all expansion greater than 2/3. In this talk, we show how to decode in linear time for any expansion, assuming that the inner code has certain minimum distance depending only on the vertex expansion (though the relative minimum distance of the inner code can still approach zero when d is large). This is joint work with Michael Dowling.
Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS33: Algorithms and Complexity in Polynomial Systems 2
Chee Yap (New York University), Michael Burr (Clemson University), James Davenport (University of Bath), Carlos D'Andrea (Universitat de Barcelona),
Root Finding for Analytic and Harmonic Functions (Chee Yap)
Subdivision methods has turned out to be extremely effective for algebraic roots. In this talk we discuss some recent progress in extending such methods to finding roots of analytic and harmonic functions.
Continuous Amortization: Intrinsic Complexity for Subdivision-based Algorithms (Michael Burr)
Continuous amortization was recently introduced as a technique to compute the complexity of subdivision-based algorithms. This technique has been successfully applied to algorithms which compute approximations to polynomial solutions. The result of the continuous amortization computation is a expression which is based on the intrinsic complexity of the input instance. In practice, these expressions are state-of-the art and adaptive to the input data. In this talk, I will present recent advances in the continuous amortization technique, including the development of the theory as well its application to particular subdivision-based algorithms for solutions to polynomials.
More than one equation constraint in Cylindrical Algebraic Decomposition (James H. Davenport)
If a formula for which we want a quantifier-free form is of (or can be written in) the form "(f=0) and rest" then we have known since McCallum's 1999 work how to construct a better Cylindrical Algebraic Decomposition. Here we extend this to allow any number of such equations, provided that the polynomials are primitive in their main variables. We also make use of these constraints to simplify the lifting phase. This gives dramatic savings in cell counts. We discuss the challenge posed by the primitivity restriction.
Sparse resultants of toric cycles (Carlos D'Andrea)
Sparse resultants have been recently redefined as equations of toric cycles instead of the classical definition over toric varieties. This notion has better combinatorial and computational properties which should be useful in the design of algorithms for solving polynomial equations and the analysis of their complexity. In this talk, we will introduce these generalized resultants, and show some of their general properties. This is joint work with Gabriela Jeronimo and Martin Sombra.
Talk Material 1: / Talk Material 3: / Talk Material 4: /
KT 1
10:30 - 12:30 MS34: On the Geometry and Topology of (Co)Ame`bas and Beyond
Frank Sottile (Texas A&M University), Diane Maclagan (University of Warwick), June Huh (Princeton University), Farid Madani (Universitat Regensburg),
Higher Convexity for Complements of Tropical Varieties (Frank Sottile)
Gromov generalized the notion of convexity for open sub- sets of R^n with hypesurface boundary, defining k-con- vexity, or higher convexity and Henriques applied the same notion to complements of amoebas. He conjectured that the complement of an amoeba of a variety of codimension k+1 is k-convex. I will discuss work with Mounir Nisse in which we study the higher convexity of complements of tropical varieties, establishing a form a Henriques' conjecture in some cases.
Realizability of Tropical Varieties (Diane Maclagan)
Tropical varieties can be realized as the limits of complex amoebae, or as "non-archimedean amoebae" (images of va- rieties over a valued field under the valuation map). In this talk I will explain why the set of polyhedral com- plexes that can be obtained in these two ways is the same; every tropical variety that is realizable over an algebraically closed field of characteristic zero and value group R is ap- proximable by complex varieties.
A Tropical Approach to a Hodge Conjecture for Positive Currents (June Huh)
Demailly showed that the Hodge conjecture is equivalent to the statement that any closed (p,p)-dimensional current with rational cohomology class can be approximated by lin- ear combinations of algebraic subvarieties, and asked whether any positive closed (p,p)-dimensional current with rational cohomology class can be approximated by positive linear combinations of algebraic subvarieties. Using tropical geometric ideas, we construct a positive closed (p,p)-dimen- sional current on a smooth projective variety that does not satisfy the latter statement. This is a joint work with Farhad Babaee.
Volume of Amoebas (Farid Madani)
I report on recent progress concerning (co)amaeba volumes and their geometrical implications. After introducing (co)amoebas of analytic varieties and giving the relationship between their volumes, I give some results about the alge- braicity of an analytic variety. This is based on joint work with Mounir Nisse.
Talk Material 1: / Talk Material 2: / Talk Material 4: /
10:30 - 12:30 MS35: Tensor Decomposition : Ideals meet Applications 2
Andrzej Cichocki (Riken Brain Science Institute Japan), Kristian Ranestad (University of Oslo), Hirotachi Abo (University of Idaho), Elisa Postinghel (University of Leuven),
Tensor Factorizations and Tensor Networks for Big Data Analytics and their Potential Applications (Andrzej Cichocki)
Big data such as multimedia data and medical/biological (EEG/MEG, fMRI, DTI) data analysis requires novel technologies to efficiently process and analyze large quantities of data within tolerable elapsed times. We believe that a such technology for multidimensional big data analytics could be at least partially based on emerging low-multi-linear-rank approximations and (randomized) distributed tensor/matrix factorizations and tensor network models. Current applications in many areas of science and technology such as computational neuroscience, bioinformatics and pattern/image recognition generate massive amounts of data with multiple aspects and high dimensionality and tensors decompositions with low-rank approximations can provide an approximate representation for a massive multidimensional data. Tensor decompositions and tensor networks allow us to discover meaningful hidden structures of complex data and perform generalizations by capturing multi-linear and multi-aspect relationships. The challenge is to analyze intractably large-scale optimization problems to perform dimensionality reduction, feature extraction, classification, and clustering and anomaly detection. We discuss several very large-scale optimization problems related to GEVD (generalized eigenvalue decomposition), SVD, PCA, CCA (canonical correlation analysis) and solving huge systems of linear equations, with potential applications in machine learning and signal processing applications. We will also discuss tensor factorization models and associated algorithms for several neuroscience applications including Brain Computer Interface (BCI), 3D MRI denoising, tensor completion and early detection of Alzheimer disease.
Varieties of sums of powers of bihomogeneous forms (Kristian Ranestad)
I shall present work in collaboration with Nelly Villamizar and Matteo Gallet. We describe the variety of presentations of a (2,2) form and a (3,3) form in C[x_0,x_1][y_0,y_1] as sums of powers of decomposable (1,1) -forms .
Varieties of completely decomposable forms and their secants (Hirotachi Abo)
Every d-form can be expressed as a linear combination of completely decomposable forms (or products of d linear forms). The minimum number of completely decomposable d-forms that sum up to a d-form is called the rank of the d-form. In this talk, I will discuss the problem of finding the least positive integer s such that a general ternary form has rank less than of equal to s.
On Strassen's Conjecture (Elisa Postinghel)
In 1973 Strassen conjectured that additivity holds for bilinear maps, namely that the computational complexity of simultaneously executing two bilinear maps is the same as the sum of the complexities of the individual bilinear maps. In complexity theory, of particular interest is the bilinear map representing matrix multiplication. I will rephrase Strassen's conjecture in terms of tensor rank and show that it holds for three-factor tensors, whenever the dimension of one of the involved vector spaces is at most two. This is joint work with J. Buczynski.
Talk Material 2: / Talk Material 3: / Talk Material 4: /
KT 2
10:30 - 12:30 MS36: Algebraic Structures arising in Systems Biology 3
Heather Harrington (University of Oxford), Bernadette Stolz (Mathematical Institute, University of Oxford), Carina Curto (Pennsylvania State University), Nora Youngs (Harvey Mudd College),
Parameter-free methods distinguish Wnt pathway models and guide design of experiments (Heather Harrington)
We focus on a specific signaling pathway of gene regulation and present different approaches for analysing models from systems biology. The focus of these techniques will be a set of models of the Wnt signaling pathway, which is involved in development, adult tissue cells and cancer. We propose a new mechanistic model that includes spatial localization, compare this model and existing models from the literature to data. We apply statistical and algebraic approaches-- focusing on both parameter-dependent and parameter-independent methods to compare and reject models. We apply chemical reaction network theory, computational algebraic geometry, combinatorics and statistics to study the Wnt signaling system, enabling us to inform design of experiments and reject a competing Wnt model. The techniques are applicable to other problems in systems biology. This is joint work with Adam L MacLean, Zvi Rosen, and Helen M Byrne.
Persistent Homology in the Study of Cancer Gene Expression (Bernadette Stolz)
The amount and complexity of gene expression data has increased rapidly in recent years with the improved availability of biological tools. Analysing high-dimensional data has therefore become a major challenge. A method from the field of computational topology known as persistent homology has been used to study shapes in large data sets such as point clouds. We apply methods from computational topology known as Vietoris-Rips filtration and lazy witness filtration to explore breast cancer gene expression data in gene space and sample space. Since the lazy witness filtration relies on the choice of a small subset landmark points in sample space we make investigations on the selection process of the landmarks. We nd that the Vietoris-Rips ltration can distinguish between data sets including completely healthy patients as controls and data sets including controls in the form of samples from non-tumour tissue taken from tumour patients. We also find patient clusters that correspond well to clusters found with standard techniques. Finally, combining our results for the lazy witness filtration with results from a previous study, we give a suggestion for the biological interpretation of topological features in sample space.
Convex neural codes (Carina Curto)
Cracking the neural code is one of the central challenges of neuroscience. Typically, this has been understood as finding the relationship between single neurons and the stimuli they represent. More generally, neural activity must also reflect relationships between stimuli, such as proximity between locations in an environment. Convex codes, comprised of activity patterns for neurons with classical receptive fields, may be the brain's solution to this problem. These codes have been observed in many areas, including sensory cortices and the hippocampus. What makes a code convex? Using algebra, we can uncover intrinsic signatures of convexity and dimension in neural codes. I will report on some recent results by multiple authors, including participants in a 2014 AMS Math Research Community.
Maps between neural codes (Nora Youngs)
Neurons represent external stimuli via neural codes, and the brain infers properties of a stimulus space using only the intrinsic structure of the neural code. We define the neural ring, an algebraic object that encodes the combinatorial data of a neural code. Neural rings can be expressed in a `canonical form' that translates to a minimal description of code's structure. This provides information about structure in the stimulus space. We investigate how certain natural changes to the code affect its structural properties and how these changes are reflected in the canonical algebraic structure.
Talk Material 1: /
10:30 - 12:30 MS37: Markov Bases and their Applications in Statistics 2
Abraham Martin del Campo (IST Austria), Satoshi Aoki (Kagoshima University), Mitsunori Ogawa (University of Tokyo), David Kahle (Baylor University),
Conditions for the toric homogenous Markov Chain models to have square-free quadratic Groebner basis (Abraham Martin del Campo)
A Markov chain is a stochastic process that takes values over a finite set of states, where the probability of the chain to be at state S at time T+1 only depends on the state of the chain at time T. We consider the toric homogeneous Markov chain model, where the transition probabilities do not depend on time. In this joint work with Akimichi Takemura and Ruriko Yoshida, we study conditions that ensure for a square-free quadratic Groebner basis for the toric ideal associate with the model. This has potential applications in other areas, e.g. in phylogenetics, the discrete Markov chain model embedded in the Kimura three parameter model.
Markov chain Monte Carlo methods for the Box-Behnken designs and centrally symmetric configurations (Satoshi Aoki)
We consider Markov chain Monte Carlo methods for calculating conditional p values of statistical models for count data arising in Box-Behnken designs. The statistical model we consider is a discrete version of the firstorder model in the response surface methodology. For our models, the Markov basis, a key notion to construct a connected Markov chain on a given sample space, is characterized as generators of the toric ideals for the centrally symmetric configurations of root system Dn. We show the structure of the Grobner bases for these cases. A numerical example for an imaginary data set is given. This is a joint work with Satoshi Aoki, Takayuki Hibi and Hidefumi Ohsugi.
Goodness-of-fit testing for random graph model with community structure (Mitsunori Ogawa)
In the analysis of complex networks the community structure is an important aspect and there are many algorithms to detect the communities from an observed network. This talk concerns with some simple statistical models taking into account the effect of the given community structure. Our model is a log-linear type model obtained by adding some parameters to the beta model of random graphs. We discuss the goodness-of-fit test for the model by using Markov bases techniques.
Applied Algebraic Statistics in R with algstat (David Kahle)
The real-world application of Markov bases techniques typically involves a potpourri of mathematical and statistical software. In this talk we give an overview of and introduction to algstat, an R package that can fit many types of models enabled by Markov and related bases by leveraging back-end connections to 4ti2, LattE, and custom C++ implementations of important algorithms. algstat is a collaborative project developed jointly with Luis Garcia-Puente and Ruriko Yoshida.
Talk Material 1: / Talk Material 4: /
10:30 - 12:30 MS38: Pairings in Cryptography 2
Koray Karabina (Florida Atlantic University), Mehdi Tibouchi (NTT Secure Platform Laboratories), Para Lee (Ewha Womans University),
Fault Attacks on Pairings (Koray Karabina)
Fault attacks on cryptographic protocols have been studied for about two decades and faults have been considered in the context of pairing-based cryptography for more than a decade. I present a survey of mathematical techniques for injecting faults on pairing-based cryptographic primitives and discuss effectiveness of fault attacks on specific pairing-based protocols.
Using Groebner Basis Techniques to Construct Optimal Structure Preserving Signatures (Mehdi Tibouchi)
A pairing-based digital signature scheme is said to be structure-preserving when messages, signatures and verification keys all consist of tuples of source group ele- ments, and when signature verification is carried out by checking group memberships and given pairing product equations. Since they operate entirely on group elements, structure-preserving signatures (SPS) compose well with other pairing-based primitives (such as Groth-Sahai non-interactive zero-knowledge proofs), and as such, they are a useful tool in the construction of pairing-based protocols secure in the standard model. As a relatively low-level building block, however, they need to be quite efficient to yield practical cryptographic schemes. In this talk, we will discuss recent results on the efficiency of SPS, and partic- ularly describe how Groebner basis computations and other commutative algebra techniques were used both to establish lower bounds on secure SPS (e.g. show that if the number of group elements in signatures is lower than a certain bound, forgeries are possible) and also construct optimal SPS schemes, matching those lower bounds.
Constructing Complete Families of Pairing-Friendly Curves Using the Method of Indeterminate Coefficients (Para Lee)
The problem of constructing pairing-friendly elliptic curves having small rho-values has received a lot of attention. To solve this problem, we propose a method to find poly- nomials which parameterize a complete family of pairing-friendly elliptic curves by the method of indeterminate coefficients, In this talk, we introduce some new families of parameters for pairing-friendly curves with improved rho-values and present some explicit curves as numerical examples.
Talk Material 2: / Talk Material 3: /
12:30 - 13:00 Lunch
Cafeteria 1, 2
13:10 - 19:00 Excursion
Participants : Meeting at KT 1 at 13:10
Non-participants : Shuttle to Lotte–KAIST–Interciti will leave at 13:30

Return to Hotel
Gyeryongsan National Park
19:00 - 21:00 Banquet
Interciti Lavender Hall (Interciti 4th Floor)

Interciti Hotel
TimeSpeaker/ Title/ Abstract/ VODLocation
08:00 - 08:45 Shuttle Bus to NIMS
Arrive at NIMS
09:00 - 10:00 IP06: Algebraic Vision
Rekha Thomas (University of Washington),
Loading the live streaming player...
Reconstructing a 3-dimensional scene from 2-dimensional images of it is a fundamental problem in computer vision. Real solutions to systems of polynomials play a key role in solving this problem. In this talk I will explain recent work that attempts to bring in tools from algebraic geometry and polynomial optimization to some of the foundational problems in 3D computer vision with a particular focus on the most basic problem of reconstruction from two images.
Talk Material 1: /
KT 1
10:30 - 12:30 MS39: Polynomial Optimization and Moments 1
Igor Klep (The University of Auckland), Dennis Amelunxen (City University of Hong-Kong), Sabine Burgdorf (CWI, Amsterdam), Lihong Zhi (Academia Sinica),
Spectrahedra, the Matrix Cube Problem, Dilations, and Coin Tossing (Igor Klep)
Linear matrix inequalities (LMIs) are common in many areas: control theory, mathematical optimization, statistics, etc. Given real symmetric matrices $A_0,\ldots, A_g$ consider the linear matrix inequality \[L(x)=A_0+A_1 x_1+\cdots + A_g x_g\succeq0, \] where ``$\succeq0$'' means positive semidefinite. The solutions set to this LMI is called a {\em spectrahedron} and is a convex semialgebraic subset of $\R^g$. We study the question whether inclusion holds between two spectrahedra. Most of our results concern the case where the included spectrahedron is a cube, an NP-hard problem introduced and studied by Ben-Tal and Nemirovski, who identified a tractable ``free'' relaxation of the original problem. This relaxation is obtained by considering the inclusion problem for the corresponding \emph{free spectrahedra}. A central issue is: how close is spectrahedral inclusion to its free relaxation? Clearly, inclusion of free spectrahedra implies the inclusion of the corresponding spectrahedra. This talk treats the converse. We show inclusion of spectrahedra implies the inclusion of the corresponding free spectrahedra up to a scaling factor $t$. For the cube, we compute the tight bound $t_{\text{cube}}$ with an elegant scalar optimization formula. When the size of the $A$'s is $d\times d$ and $d$ is even, then \[ t_{\text{cube}}=\sqrt{\pi} \ {\Gamma\left(\frac{1}{2} +\frac{d}{4}\right)} \ \Gamma\left(1+\frac{d}{4}\right)^{-1}. \] Critical to our proofs is dilating a tuple of matrices $X$ lying in a free spectrahedron $\cS$ to a \emph{commuting} tuple $\tX$ of self-adjoint operators in $t \cS$. This is based on joint work with Bill Helton, Scott McCullough and Markus Schweighofer.
On the stochastic profile of the semidefinite cone (Dennis Amelunxen)
This talk is about certain probabilities associated with the cone of positive semidefinite matrices, and how they can be answered through the theory of (conic) integral geometry. Among these are questions about the expected rank of the solution of a random semidefinite program (SDP), and questions about random determinantal hypersurfaces. We will also speak about connections to random matrix theory and how integral geometry can give this classical theory an interesting new twist.
The completely positive semidefinite cone (Sabine Burgdorf)
The completely positive semidefinite cone $\mathcal{CS}_+^n$ is a generalization of the completely positive cone, consisting of all the $n\times n$ symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size instead of Gram representations by nonnegative vectors. This cone can be used, e.g., to characterize the set of bipartite quantum correlations as projection of an affine section of it. We will give an overview on the known structure, including a polyhedral approximation of its interior as well as a description of its closure. (joint work with M. Laurent and T. Piovesan)
Optimizing a parameteric linear function over a non-compact real algebraic variety (Lihong Zhi)
We consider the problem of optimizing a parametric linear function over a non-compact real trace of an algebraic set V . Our aim is to compute the optimal value function (depending on the parameters). Our goal is to compute a representing polynomial which defines a hypersurface containing the graph of the opposite of the optimal value function. Rostalski and Sturmfels showed that when V is irreducible and smooth with a compact real trace, then the least degree representing polynomial is given by the defining polynomial of the irreducible hypersurface dual to the projective closure of the V . First, we generalize this approach to non-compact situations. We prove that the graph of the opposite of the optimal value function is still contained in the affine cone over a dual variety similar to the one considered in compact case. We also show that Rostalski and Sturmfels’ conclusion is still true when the recession cone of the closure of the convex hull of a non-compact algebraic variety is pointed. For some special parameters' values, the representing polynomials of the dual variety can be identically zero, which gives no information on the optimal value. We design a dedicated algorithm that identifies those regions of the parameters’ space and computes for each of these regions a new polynomial defining the optimal value over the considered region.
Talk Material 1: /
KT 1
10:30 - 12:30 MS40: Coding Theory and Cryptography 2
Tanja Lange (Technische Universiteit Eindhoven), Daniel Bernstein (University of Illinois at Chicago and Technische Universiteit Eindhoven), Jooyoung Lee (Sejong University), Rama Krishna Bandi (Indian Institute of Technology Roorkee),
Twisted Hessian curves (Tanja Lange)
This talk presents new speed records for arithmetic on a large family of elliptic curves with cofactor 3: specifically, 8.77 field multiplications per bit for 256-bit variable-base single-scalar multiplication when curve parameters are chosen properly. This is faster than the best results known for cofactor 1, showing for the first time that points of order 3 are useful for performance and narrowing the gap to the speeds of curves with cofactor 4. This is joint work with Daniel J. Bernstein, Chitchanok Chuengsatiansup, and David Kohel.
Computational algebraic number theory tackles lattice-based cryptography (Daniel Bernstein)
Peikert: "Because finding short vectors in high-dimensional lattices has been a notoriously hard algorithmic question for hundreds of years---even when one allows for the power of quantum algorithms ...---we have solid and unique evidence that lattice-based cryptoschemes are secure." Evidently this means that we should trust, e.g., a fully homomorphic lattice-based cryptosystem introduced by Smart and Vercauteren in 2009. As the authors wrote: "Determining the private key given only the public key is an instance of a classical and well studied problem in algorithmic number theory." However, a recent paper of Campbell, Groves, and Shepherd claims to break a lattice-based cryptosystem named Soliloquy in quantum polynomial time. It seems reasonably clear that a non-quantum version of the same algorithm works in subexponential time, and also breaks several other lattice-based cryptosystems, including the Smart--Vercauteren system. Furthermore, it is not clear that there are any relevant dividing lines between these systems and many other lattice-based cryptosystems, including the classic NTRU cryptosystem. This talk will explain the basic ideas behind the attacks.
Encryption based on card shuffling (Jooyoung Lee)
In this talk, we present a new encryption scheme suitable for encryption of data of small size. This scheme, called "partition-and-mix", generalizes the swap-or-not shuffle introduced by Hoang et. al. at Crypto 2012, providing better efficiency in terms of the number of rounds. We introduce two methods of instantiating the partition-and-mix shuffle, one by using (almost) independent permutation families and the other one using Hamming codes.
A class of constacyclic codes over $F_{p^r} +uF_{p^r} +vF_{p^r} +uvF_{p^r}$ (Rama Krishna Bandi)
a joint work with Srinivasulu B, Mahehshanand Bhaintwal Cyclic codes are well studied algebraic codes because of their rich algebraic structure and their ease in encoding and decoding. The structure of such cyclic codes is well known over finite chain rings. Constacyclic codes are the important generalization of cyclic codes. Let $\lambda$ be a unit in a finite ring $\mathcal{R}$. Then the constacyclic codes of length $n$ over $\mathcal{R}$ are identified as ideals of $\frac{\mathcal{R}[x]}{\langle x^n - \lambda \rangle}$. There has been a lot interest on constacyclic codes over finite rings such as $\mathbb{F}_2+u\mathbb{F}_2$, $u^2=0$ $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$, $u^2=0$; $\frac{\mathbb{F}_p[u]}{\langle u^{m} \rangle}$, $u^{m+1}=0$. Recently, Yildiz et. al have studied $(1+v)-$constacyclic codes over $\mathbb{F}_2+u\mathbb{F}_2+v\mathbb{F}_2+uv\mathbb{F}_2$, $u^2=0$. In this work, they have mainly focused on constacyclic codes of odd length. In Kai et. al have considered $(1+u)-$constacylic codes of arbitrary length. However they have not given the complete structure of $(1+u)-$constacylic codes of length $2^k$ over $\mathbb{F}_2+u\mathbb{F}_2+v\mathbb{F}_2+uv\mathbb{F}_2$, $u^2=0$. Later, Hai et. al have studied $(1-uv)-$constacyclic codes of odd length over $\mathbb{F}_p+u\mathbb{F}_p+v\mathbb{F}_p+uv\mathbb{F}_p$, $u^2=0$. In all these aforemention papers the authors have not considered constacyclic codes of length $p^k$, $k \geq 1$. In this paper, we study $(\alpha + \beta u)-$constacyclic codes of length $n=p^k$, $k \geq 1$ over the ring $R=\R$, $u^2=v^2=0$, $p$ is a prime, $r \geq 0$ and $\alpha$, $\beta$ are elements in $\F$. We give the complete structure of constacyclic codes of length $n$ over $R$. We determine the cardinality of $(\alpha + \beta u)-$constacyclic codes and a mass formula for number of $(\alpha + \beta u)-$constacyclic codes. We have obtained the structure of the duals of $(\alpha + \beta u)-$constacyclic codes and also characterized the self-orthonal and self-dual $(\alpha + \beta u)-$constacyclic codes. We give the mass formula for number of self-dual $(\alpha + \beta u)-$constacyclic codes of length $n$ over $R$.
Talk Material 1: / Talk Material 3: /
10:30 - 12:30 MS41: Software and Applications in Numerical Algebraic Geometry 3
Daniel Bates (Colorado State University), Brent Davis (Colorado State University), Alan Liddell (University of Notre Dame), Heather Harrington (University of Oxford),
Numerical techniques for studying parameter spaces (Daniel Bates)
Some problems from systems biology, magnetism, kinematics, and elsewhere can be pitched as parametrized polynomial systems. There is often then the question of how to find points of interest within the parameter space, i.e., points (curves, etc.) where the dimension or multiplicity of the solution set changes, points above which there are a certain number of positive, real solutions, etc. In this talk, I will survey a few recent approaches and applications in the hopes of generating interest in developing new, practical approaches to these sorts of problems.
Numerical algebraic geometry for analysis of phylogenetic trees (Brent Davis)
A current problem in quartet-based supertree reconstruction is they become inaccurate when individual quartets are not constructed correctly. Using tools from numerical algebraic geometry, we propose a phylogenetic reconstruction algorithm, called the nearest point method, which uses the Euclidean distance to the nearest point on the Jukes Cantor quartet model to select the tree of best fit. The nearest point method is used with two schemes, which we define as the relative distance and data-dependent p-value scheme, to screen for and exclude quartets. Our simulation involves employing the software package Paramotopy. Paramotopy was used to solve the 1,600 optimization problems used in our analysis. Using the p-value scheme, we show that we can achieve global accuracy of 100% over our sample space considered by rejecting 30% of the data. In addition, we can achieve 100% local accuracy in problem regions where long-branch attraction occurs while still retaining 34% of the local data. This is joint work with Joseph Rusinko (Wintrop University).
Numerically certifying the completeness of real solution sets to polynomial systems (Alan Liddell )
The computation of real solutions to a system of polynomial equations presents unique challenges. Since real solutions are often the solutions sought after in applications, one may wish to know if one has computed the complete set of solutions for a given system. Confidence in numerical methods would be greatly boosted if the completeness of such sets could be readily guaranteed. In this work, we develop an algorithm certifying that a given set of solutions, including real isolated and positive-dimensional solution components, constitutes a complete real solution set.
Numerical nonlinear algebra for biology (Heather Harrington)
I will present three approaches using numerical algebraic geometry (NAG) that addresses problems that are often encountered in mathematical and systems biology. (1) Whether a system has multiple positive steady states is a particularly important problem in biology. We present a method using numerical algebraic geometry that explores the parameter landscape and apply it to biological systems. (2) Given steady state data and a model, can we recover parameter values? We present an NAG algorithm that provides a parameter estimate from data. (3) Given multiple competing hypotheses (models) and data, how can we determine which model best describes the data? Building upon the algorithm developed in (2) we can naturally extend this NAG approach. The focus of the talk will be on the applications and insight such methods bring to biological questions.
Talk Material 1: / Talk Material 3: / Talk Material 4: /
KT 2
10:30 - 12:30 MS42: Combinatorial Methods in Algebraic Geometry 1
Alicia Dickenstein (University of Buenos Aires), Atsushi Ito (Kyoto University), Diane Maclagan (University of Warwick), Benjamin Nill (Stockholm University),
Higher order selfdual toric varieties (Alicia Dickenstein)
The notion of higher order dual varieties of a projective variety is a natural generalization of the classical notion of projective duality. We give different combinatorial, algebraic and computational characterizations of those equivariant projective toric embeddings that satisfy higher order selfduality. This is joint work with Ragni Piene.
Gauss maps of toric varieties (Atsushi Ito)
In this talk, I will explain Gauss maps of (not necessarily normal) projective toric varieties. This is a joint work with Katsuhisa Furukawa.
Tree compactifications of the moduli space of genus 0 curves (Diane Maclagan)
The moduli space M_{0,n} of smooth genus zero curves with n marked points has a standard compactification by the Deligne-Mumford module space of stable genus zero curves with n marked points. The compactification can be constructed as the closure of M_{0,n} inside a toric variety. The fan of the toric variety is moduli space of phylogenetic trees (or genus zero tropical curves). I will discuss joint work with Dustin Cartwright to construct other compactifications of M_{0,n} by varying the toric variety.
Finiteness of mutation-equivalence classes of Fano polygons (Benjamin Nill)
Fano polygons correspond to singular toric Del Pezzo surfaces. In this talk I will present a finiteness result for mutation-equivalence classes of Fano polygons with bounded residual singularities. Mutations of Fano polygons were recently introduced in the context of mirror symmetry of Fano manifolds. I will explain how our results generalize well-known facts on lattice polygons and what their significance is for a potential classification of non-toric Del Pezzo surfaces. This is joint work with Alexander Kasprzyk and Thomas Prince.
Talk Material 2: / Talk Material 3: /
10:30 - 12:30 MS43: Symbolic Combinatorics 1
Cyril Banderier (Universite Paris Nord, Paris), Shaoshi Chen (Academy of Mathematics and Systems Science, Chinese Academy of Sciences), Shishuo Fu (Chongqing University), Tomack Gilmore (University of Vienna),
Combinatorics and asymptotics: beyond the D-finite world. (Cyril Banderier)
Asymptotics of recurrences is often the key to get the typical properties of combinatorial structures, and thus the complexity of many algorithms relying on these structures. The associated generating function often follows a linear differential equation: we are here in the so-called "D-finite" world. For the matters of asymptotics, this case of linear recurrences (with polynomial coefficients) is well covered by the "Analytic Combinatorics" book of Flajolet and Sedgewick (though the computations of constants is still a challenge, related to the theory of Kontsevich-Zagier periods and evaluation of G-functions and E-functions). At the border of this D-finite world, lie the "algebraic-differential functions": let dz^m be the m-th derivative of F(z), the function is said "algebraic-differential" if there a exists a polynomail P such that P(z,F,F',dz^m F)=0. We will give examples of such functions (motivated by some combinatorial problems), and show how a symbolic combinatorics approach can help for automatic asymptotics of their coefficients. (joint works with Michael Drmota and Hsien-Kuei Hwang)
A Modified Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms (Shaoshi Chen)
The Abramov-Petkovsek reduction computes an additive decomposition of a hypergeometric term, which extends the functionality of the Gosper algorithm for indefinite hypergeometric summation. We modify the Abramov-Petkovsek reduction so as to decompose a hypergeometric term as the sum of a summable term and a non-summable one. The outputs of the Abramov-Petkovsek reduction and our modified version share the same required properties. The modified reduction does not solve any auxiliary linear difference equation explicitly. It is also more efficient than the original reduction according to computational experiments. Based on this reduction, we design a new algorithm to compute minimal telescopers for bivariate hypergeometric terms. The new algorithm can avoid the costly computation of certificates.
q-Orthogonal Polynomial and Lacunary Partition Functions (Shishuo Fu)
In this note, we utilize orthogonality of the Little $q$-Jacobi Polynomial to derive the "expansion" of two $q$-series, which consequently gives rise to two identities that was first studied by Andrews et al and Corson et al using the arithmetic of $\mathbb{Q}[\sqrt{6}]$ and $\mathbb{Q}[\sqrt{2}]$ respectively.
Interactions of triangular holes in two dimensional dimer systems. (Tomack Gilmore)
In 2008 Mihai Ciucu conjectured that the asymptotic interaction between gaps in dimer systems on the hexagonal lattice are governed (up to a multiplicative constant) by Coulomb's law of electrostatics. Gaps in such dimer systems correspond to triangular holes in rhombus tilings of the planar unit triangular lattice. Viewed from this perspective, a host of combinatorial techniques may be employed in order to derive asymptotic expressions for interactions between triangular holes within a sea of unit rhombi. The original conjecture of Ciucu remains wide open, although it has been shown to hold for two fairly general classes of gaps. In this talk I will discuss how the symbolic computation packages RATE, HYP and fastZeil were used to derive recent results that provide further evidence in support of Ciucu's electrostatic program.
Talk Material 2: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS44: Algebraic Vision 1
Irina Kogan (North Carolina State University), Anton Leykin (Georgia Tech), Joe Kileel (University of California, Berkeley), Manolis Tsakiris (Johns Hopkins University),
Curves Under Projections (Irina Kogan)
Matching an object in three-dimensional space with its planar image is one of the fundamental problems in computer vision. This problem is intimately related with the group-equivalence problem:identifying whether or not two planar objects are congruent with respect to a given group of transformations. We will show how this relationship can be exploited for solving object-image correspondence problem for curves and also examine interesting relationships between invariants of space curves and invariants of their planar images. This talk is based on joint works with J. Burdis, H. Hong and P. Olver.
Homotopy Continuation and Vision (Anton Leykin)
We consider an application of methods of numerical algebraic geometry to minimal problems in computer vision. The conclusion is that the underlying numerical homotopy continuation solvers give a promising alternative to polynomial solvers based on symbolic techniques such as Groebner bases.
The Calibrated Trifocal Variety (Joe Kileel)
The calibrated trifocal variety is the moduli space of projective configurations of three cameras with known calibration matrices. This talk will present results from our study of the CTV, including equations in its defining prime ideal and a summary of numerical experiments quantifying non-uniqueness in the associated 3D reconstruction problem.
From Motion Segmentation to Descending Filtrations of Subspace Arrangements (Manolis Tsakiris)
The problem of segmenting a dynamic scene with multiple rigid body motions is of prominent interest in the computer vision community. Under the affine projection model, the 2D trajectories from a rigid body motion lie in an affine subspace. Therefore, the motion segmentation problem reduces to the problem of clustering point trajectories according to their rigid body motion, and finding the number of rigid body motions. This problem can be posed as that of decomposing the algebraic variety of a subspace arrangement into its constituent irreducible components or equivalently, computing the primary components of the vanishing ideal of the underlying subspace arrangement. We present a recent methodology for achieving this task in the absence of knowledge of the number of subspaces or their dimensions, by means of descending filtrations of subspace arrangements. Finally, we briefly discuss some open challenging algebraic-geometric questions associated to the alternative two-view perspective geometry model.​
Talk Material 1: /
10:30 - 12:30 MS45: Algebraic Structure in Graphical Models 3
James Saunderson (Caltech), Elina Robeva (UC Berkeley), Caroline Uhler (Institute of Science and Technology Austria), Jinfang Wang (Chiba University),
A convex optimization approach to Gaussian latent tree models (James Saunderson)
This talk is about the marginal distribution on the leaf-indexed variables of a Gaussian tree model (where the latent variables are not necessarily scalar). Such Gaussian latent tree models refine the classical factor analysis model by allowing for additional hierarchical structure among the latent variables. In such models the marginal covariance among the leaf-indexed variables can be characterized in terms of a structured matrix decomposition, with the ranks of parts of the decomposition corresponding to the dimensions of the latent variables. From this characterization we develop convex optimization-based methods that aim to recover the model parameters, the latent variable dimensions, and the combinatorial structure of the tree, from statistics of only the observed leaf-indexed variables. We give simple sufficient conditions on an underlying Gaussian latent tree model under which our method can recover all of these structures from the exact marginal covariance among the leaf-indexed variables. This is joint work with Pablo Parrilo (MIT) and Alan Willsky (MIT)
Superresolution without Separation (Elina Robeva)
This talk provides a theoretical analysis of diffraction-limited superresolution, demonstrating that arbitrarily close point sources can be resolved in ideal situations. Precisely, we assume that the incoming signal is a linear combination of M shifted copies of a known waveform with unknown shifts and amplitudes, and one only observes a finite collection of evaluations of this signal. We characterize properties of the base waveform such that the exact translations and amplitudes can be recovered from 2M +1 observations. This recovery is achieved by solving a weighted version of basis pursuit over a continuous dictionary. Our methods combine classical polynomial interpolation techniques with contemporary tools from compressed sensing.
Parameter estimation for linear Gaussian covariance models (Caroline Uhler)
Linear Gaussian covariance models are Gaussian models with linear constraints on the covariance matrix. Such models arise in many applications, such as stochastic processes from repeated time series data, Brownian motion tree models used for phylogenetic analyses and network tomography models used for analyzing the connections in the Internet. Maximum likelihood estimation in this model class leads to a non-convex optimization problem that typically has many local maxima. However, I will explain that the log-likelihood function is in fact concave over a large region of the positive definite cone. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution I will show that running any hill-climbing method in this region leads to the MLE with high probability. This is joint work with Piotr Zwiernik and Donald Richards.
Formalization of probabilistic conditional independence using Coq/SSReflect (Jinfang Wang)
Probabilistic conditional independence (PCI) is a key concept is many areas of science including statistical theories for causal inference. Many axiomatic approaches have been taken in the literature for manipulating PCI, including, but not limited to, Dawid (1979, 2001), Pearl and Paz (1987), Studeny (2005) and Wang (2010). The universal algebraic approach, called Cain algebra, of Wang (2010) (Ann Inst. Stat. Math. 62: 747–773), differs from the others in that all PCI relations are represented in purely equational forms. In this talk I will show how to formalize the Cain algebra using Coq/SSReflect, an interactive theorem prover for mechanically (and sometimes automatically) checking the correctness of mathematical assertions. The Curry-Howard isomorphism expresses a direct relationship between computer programs and mathematical proofs. According to this theory, propositions are types and proofs are programs. Thus, looking for PCI relations is equivalent to looking for the corresponding computer programs. Our formal approach to PCI based on Coq/ SSReflect opens the possibility for automatically proving the correctness of a set of PCI relations given another set of PCI relations.
Talk Material 1: / Talk Material 2: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS46: Combinatorial Phylogenetics 2
Ruriko Yoshida (University of Kentucky), Ruth Davidson (University of Illinois, Urbana-Champaign), Jeremy Sumner (University of Tasmania), Andrew Francis (University of Western Sydney),
Normalizing kernels in the Billera-Holmes-Vogtmann treespace (Ruriko Yoshida)
The KDETrees algorithm introduced in Weyenberg, et. al, 2014 is an adaptation of classical kernel density estimation to the metric space of phylogenetic trees defined by Billera, et. al., 2001. In this talk, we will describes an improvement to KDETrees, whereby the kernel normalizing constants, are estimated through the use of the holonomic gradient methods (HGM). Since we are interested primarily in using the estimator of the distribution of trees for outlier detection at this time, knowledge of the proportionality constant for the distribution is not of significant importance. However, if an adaptive bandwidth scheme is to be used, then it is important to know how the normalizing constant associated with the kernel function for each tree $T_i$ in the input varies with the selected bandwidth. In the case of Euclidean $k$-space with the usual metric, this choice of kernel function corresponds to a spherically symmetric multivariate Normal distribution centered on the point $T_i$, and the kernel normalization constant is well-known. However, when applied to the Billera-Holmes-Velleman tree-space with the geodesic metric, no such closed form solution is apparent. Marumo, Oaku, and Takemura (2014) provided a non-stochastic and algebraic approach, holonomic gradient method (HGM) for calculating the normalizing constant for a Multivariate Normal distribution truncated to the first (positive) orthant. Since the BHV treespace is a simplical complex of positive Euclidean orthants, it is possible to use the HGM to obtain approximations to the kernel normalizing constants. We have applied this improved version of KDETrees to the genome data on apicomplexa as well as the genome data on coelacanths, lungfishes, and tetrapods. This is joint work with G. Weyenberg and D. Howe.
Using Phylogenetic Invariants in Coalescent-Based Methods (Ruth Davidson)
Phylogenetic invariants are polynomial relationships in probabilities associated to models of evolutionary processes.  Thus invariants can give algebraic encodings of tree shapes representing specific evolutionary histories. Phylogenetic invariants were first introduced in the biology community in 1987. Their study has led to many beautiful results in algebraic geometry and provided interesting links between this classical field of mathematics and discrete optimization problems.  In practice, a biologist may consume a combination of techniques when making trees, and methods for large datasets-those which include large numbers of species and/or large numbers of data samples from various loci in the genome from each species-often combine distinct methods for sub-problems into a pipeline.  We investigate ways to exploit theoretical results about phylogenetic invariants when working with biological data, both to improve existing pipelines for tree-estimation and to develop new coalescent-based methods using invariants.  This is joint work with Siavash Mirarab and Tandy Warnow.
Phylogenetic invariants from group characters (Jeremy Sumner)
Joint work with Peter Jarvis, John Rhodes, and Elizabeth Allman I will discuss the construction of existence theorems for phylogenetic invariants using group theoretical arguments alone. In particular, I will present an argument from symmetry that reduces the derivation of phylogenetic invariants on tripod trees to calculations on the characters of the symmetric and general linear groups; specifically the much-celebrated Schur functions together with their associated multiplications. The key conceptual tool will be the recognition that phylogenetic invariants (and the polynomial ideals thereof) have additional structure as a vector space equipped with the action of some discrete or continuous symmetry group, e.g. leaf permutations in the former case and the action of Markov matrices in the later.
Tree-based phylogenetic networks (Andrew Francis)
A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. In this talk I will present a precise and easily tested criterion that efficiently determines whether or not any given network can be realized in this way. The proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based. I will also talk about a number of interesting consequences, and some further relevant questions and observations. Joint work with Mike Steel.
Talk Material 1: / Talk Material 3: /
12:30 - 13:00 Lunch
Cafeteria 1, 2
14:00 - 15:00 IP07: Challenges in the Development of Open Source Computer Algebra Systems
Wolfram Decker (Universität Kaiserslautern),
Loading the live streaming player...
Computer algebra is facing new challenges as mathematicians are inventing new and more abstract tools to answer difficult problems and connect apparently remote fields of mathematics. On the mathematical side, while we wish to provide cutting-edge techniques for application areas such as commutative algebra, algebraic geometry, arithmetic algebraic geometry, singularity theory, and many more, the implementation of an advanced and more abstract computational machinery often depends on a long chain of more specialized algorithms and efficient data structures at various levels. On the software development side, for cross-border approaches to solving mathematical problems, the efficient interaction of systems specializing in different areas is indispensable; handling complex examples or large classes of examples often requires a considerably enhanced performance. Whereas the interaction of systems is based on a systematic software modularization and the design of mutual interfaces, a new level of computational performance is reached via parallelization, which opens up the full power of multi-core computers, or clusters of computers. In my talk, I will report on the ongoing collaboration of groups of developers of several well-known open source computer algebra systems, including ({\sc{GAP}}, which pays particular emphasis to group theory, {\sc{Singular}}, a system for applications in algebraic geometry and singularity theory, and {\sc{Polymake}}, a software for polyhedral geometry. In presenting computational tools relying on this collaboration, and some of the mathematical challenges which lead us to develop such tools, I will in particular highlight the {\sc{Homalg}} project which provides an abstract structure and algorithms for abelian categories, aiming at concrete applications ranging from linear control theory to commutative algebra and algebraic geometry. I will also comment on progress in the design of parallel algorithms for basic tasks in commutative algebra and algebraic geometry such as primary decomposition, normalization, finding adjoint curves, or parametrizing rational curves.
Talk Material 1: /
KT 1
15:30 - 17:30 MS47: Polynomial Optimization and Moments 2
Bruce Reznick (University of Illinois), Chu Wang (Chinese Academy of Sciences), Mohab Safey el Din (Université Pierre et Marie Curie), Amir Ali Ahmadi (Princeton University),
Waring Rank and the Underlying Field (Bruce Reznick)
The Waring rank of a binary form depends on the degree. Sylvester's 1851 Algorithm and 1864 Theorem assure that the rank over $\mathbb R$ and $\mathbb C$ are often different. A few years ago we gave a quintic which has three different ranks. We shall show (with simple examples) that they exist in all degrees $\ge 5$. This becomes a problem in algebraic number theory.
Lifts of Non-compact Convex Sets and Cone Factorizations (Chu Wang)
In this paper we generalize the factorization theorem of Gouveia, Parrilo and Thomas to a broader class of convex sets. Given a general convex set, we define a slack operator associated to the set and its polar according to whether the convex set is full dimensional, whether it is a translated cone and whether it contains lines. We strengthen the condition of a cone lift by requiring not only the convex set is the image of an affine slice of a given closed convex cone, but also its recession cone is the image of the linear slice of the closed convex cone. We show that the generalized lift of a convex set can also be characterized by the cone factorization of a properly defined slack operator.
Exact Algorithm and Complexity for Linear Matrix Inequalities. (Mohab Safey el Din)
Most of algorithms for solving Linear Matrix Inequalities (LMI) are based on interior point methods. They consist in following the so-called central path and are numerical by nature. For some critical applications, numerical path-tracking may fail and one needs exact algorithms for LMI. However, the state-of-the-art for solving LMI exactly is not satisfactory since it is based on general algorithms that do not exploit the special structure of feasible sets of LMIs. In this talk, we will design a dedicated exact algorithm for solving exactly LMIs. It exploits properties of LMIs and their feasible sets and this is reflected in its complexity. Its practical performances allow to tackle problems that are out of reach of other exact algorithms. Joint work with D. Henrion and S. Naldi.
DSOS and SDSOS Techniques for Polynomial Optimization (Amir Ali Ahmadi)
"DSOS and SDSOS optimization" techniques are more scalable alternatives to sum of squares (SOS) optimization which instead of semidefinite programming rely on linear and second order cone programming. They have been successfully used (for example) to find a stabilizing controller for a model of a humanoid robot with 30 state variables, and can handle quartic polynomial optimization problems with 50-70 variables in the order of a few minutes. In this talk, we review the theoretical and numerical aspects of these algorithms and present new directions for improving their approximation quality iteratively. Joint work with Anirudha Majumdar (MIT) and separately with Sanjeeb Dash (IBM).
Talk Material 1: /
KT 1
15:30 - 17:30 MS48: Verified Solutions of Algebraic Systems
Chee Yap (New York University), Anton Leykin (Georgia Tech), Nan Li (Tianjin University), Angelos Mantzaflaris (RICAM, Austrian Academy of Sciences),
Subdivision Atlases for Non-Euclideans Spaces (Chee Yap)
Many computational problems in algebraic geometry are challenging because of high dimensionality and non-linearity. Another challenge arises when the underlying space $X$ is non-Euclidean. In robot path planning, non-Euclidean configuration spaces arise naturally: $X=\RR^3\times SO(3)$ for a rigid 3D robot, and $X=\RR^2\times T^k$ (where $T^k$ is the $k$-torus) for a flexible 2D spider robot with $k$ links. We consider the recent concept of {\bf resolution-exact algorithms} which are well-suited to problems such as path planning, with inherent uncertainty in the input data. Resolution-exact algorithms can be efficiently and practically constructed using the subdivision paradigm, using certified numerical computation. But how do we extend the subdivision paradigm from Euclidean space $\RR^d$ to the non-Euclidean $X$? We cannot simply embed $SE(3)$ in $\RR^6$, or $\RR^2\times T^k$ in $\RR^{2+k}$, since their topology is different. For a metric space $X$, we introduce the concept of a \dt{subdivision atlas} of $X$. Such atlases allow us to carry out subdivision on $X$. This talk describes ongoing work to construct and implement such algorithms.
A polynomial homotopy random walk (Anton Leykin)
Given a one parameter family of polynomial systems with complex coefficients, we develop a new way of tracking an initial system-solution pair to a solution of a target system. The core idea can be implemented in either certified or heuristic mode leading to practical advantages in scenarios where high-precision arithmetic can not be avoided by classical methods. (Work in progress.)
Verification for Isolated Singular Solutions of Algebraic Systems (Nan Li)
It is well known that it is an ill-posed problem to certify whether a polynomial system has an isolated singular solution, since arbitrary small perturbations of coefficients may change the answer from yes to no (an isolated singular solution may change into a cluster of regular solutions). In this talk we will present a symbolic-numeric algorithm for computing verified error bounds with the property that a slightly perturbed system is proved to have an isolated singular solution within the computed bounds.
Dual methods for verifying singular zeros of polynomial systems (Angelos Mantzaflaris)
Singular zeros of systems of polynomial equations constitute a bottleneck when it comes to computing, since several methods relying on the regularity of the \emph{Jacobian matrix} of the system do not apply when the latter has a non-trivial kernel. We present a method for extracting the, so called, \emph{dual basis} of the singularity in an efficient way, which can be carried out numerically, starting from an approximation of the zero in question. Then we use standard verification methods, based on interval arithmetic and fixed point theorems, in order to certify that there exists a unique perturbed system with a singular root in the domain. This is joint work with Bernard Mourrain.
Talk Material 1: /
15:30 - 17:30 MS49: Computational Approach to GIT and Moduli Theory 1
Dawei Chen (Boston College), Anand Deopurkar (Columbia University), Patricio Gallardo (University of Georgia), Maksym Fedorchuk (Boston College),
Linear series on ribbons (Dawei Chen)
A ribbon is a double structure on P^1. The geometry of ribbons is closely related to that of smooth curves. In this talk we focus on linear series on ribbons. In particular, we give an explicit determinantal description for the Brill-Noether loci and prove Clifford theorem on ribbons. We also discuss some open questions of Brill-Noether type that might be resolved by computational methods.
Equations, syzygies, and the geometry of canonical curves (Anand Deopurkar)
Exploring the relation between the geometry of an algebraic variety and the algebra of its defining equations lies at the heart of algebraic geometry. In the case of algebraic curves, this idea manifests in a conjecture due to Mark Green and in a proposed program to study the moduli of curves due to Sean Keel and Gavril Farkas. In this talk, I will describe some recent progress in this direction and some of the resulting computational challenges (based on joint work with Maksym Fedorchuk and David Swinarski).
On geometric invariant theory for hypersurfaces (Patricio Gallardo)
Geometric Invariant Theory (or GIT) is a method for constructing moduli spaces of varieties or pairs in algebraic geometry. In particular, for hypersurfaces in projective space there is a combinatorial algorithm that allows one, in principle, to completely describe the varieties parametrized by the GIT quotient. We will discuss the implementation of this algorithm and the geometric analysis of its output.
GIT semistability of the gradient of a homogeneous form (Maksym Fedorchuk)
Given a homogeneous form F of degree d in n variables, we let the gradient point of F to be the linear span of all first partials of F, considered as a point in the Grassmannian of n-dimensional subspaces of the vector space of degree d-1 forms. I will prove that F is GIT-semistable with respect to a natural SL(n) action if and only if its gradient point is GIT-semistable. This answers a question of Alper. Time permitting I will explain the motivation behind this result coming from recent work of Alper and Isaev.
Talk Material 1: /
15:30 - 17:30 MS50: Symbolic Combinatorics 2
Qing-Hu Hou (Nankai University), Arthur Yang (Nankai University), Eric Rowland (University of Liège), Rika Yatchak (Johannes Kepler University),
Congruences of Truncated Hypergeometric Series and Zeilberger's Algorithm (Qinghu Hou)
In this talk, we show how to use Zeilberger's algorithm to derive congruences of truncated hypergeometric series. We also use the extended Zeilberger's algorithm to derive new congruences from old ones. With these methods, we obtain many congruences of truncated hypergeometric series.
Computer aided proof for two problems on real-rootedness (Arthur Libo Yang)
In this talk we present two results on the real-rootedness of combinatorial polynomials. The first result concerns the real-rootedness of the generalized Narayana polynomials for finite Weyl groups, which was conjectured by Reiner and Welker and first proved by Br\"{a}nd\'{e}n via the multiplier sequences. We give an alternative proof based on the recurrence relations satisfied by the generalized Narayana polynomials. The second result concerns the real-rootedness of two variations of the Boros-Moll polynomials, which was conjectured by Br\"{a}nd\'{e}n and later proved by Chen, Dou and Yang based on the recurrence relations satisfied by the Boros-Moll sequences. In both cases, the recurrence relations are proved with the aid of mathematics packages.
Computing congruences for combinatorial sequences (Eric Rowland)
In the last decade there have been several studies concerning congruence properties of combinatorial sequences. Of course the Catalan and Motzkin numbers received much of this attention, and several forbidden residues for these sequences have been identified. For example, in 2008 Eu, Liu, and Yeh proved that no Motzkin number is divisible by 8. The proofs have mostly relied on methods particular to each sequence. However, by realizing a sequence as the diagonal of a rational power series in multiple variables, we can compute congruence information modulo prime powers completely automatically, using polynomial arithmetic. This method lets us prove many known and new results in a uniform way, with little human effort. Joint work with Reem Yassawi.
Walks in the Quarter Plane with Multiple Steps (Rika Yatchak)
We extend the classification of nearest neighbor walks in the quarter plane to models in which steps can occur with multiplicity. Our study leads to a small number of infinite families that completely characterize all models whose associated group is D4, D6, or D8. These families cover all the models with multiplicities 0,1,2, or 3, which were experimentally found to be D-finite-- with three noteworthy exceptions.
Talk Material 2: / Talk Material 3: / Talk Material 4: /
15:30 - 17:30 MS51: Algebraic Vision 2
David Dynerman (UC - Berkeley), Luke Oeding (Auburn University), Roland Angst (Max Planck Institute for Informatics), Hon Leung Lee (University of Washington),
Detecting 3D molecular symmetries from 2D cryo-EM images (David Dynerman)
Cryo-electron microscopy (cryo-EM) is used to generate 3D models of proteins in order to understand their biological function. In cryo-EM reconstruction a 3D model is produced from many noisy 2D images. Many proteins in nature exhibit symmetry, which is a rotation of 3D space that leaves the protein unchanged. Understanding the collection of all symmetries of a protein is important in understanding its biological function. Furthermore, knowing these symmetries is a necessary ingredient for computing the protein's 3D structure using cryo-EM. In this talk we will present an algorithm to determine the collection of all 3D symmetries of a molecule directly from 2D cryo-EM images, without performing full 3D reconstruction. This work is joint with Shamgar Gurevich and Yoel Shkolnisky.
The Quadrifocal Variety (Luke Oeding)
Multi-view Geometry is a branch of Computer Vision. It considers several cameras in general position as a collection of projection maps. I will review this construction from an Algebraic Geometry perspective and show how multi-focal tensors are constructed as equivariant projections of the Grassmannian. A basic question about multi-focal tensors is to give a complete algebraic description in terms of a polynomial defining ideal. I will explain my computation of the ideal of the quadrifocal variety (up to degree 6) which use the representation theory of $\GL(3)^{\times 4}$ acting on the polynomial ring on the space of $3 \times 3 \times 3 \times 3$ tensors. Further analysis gives a lower bound for the number of minimal generators. I conjecture that the ideal of the quadrifocal variety is minimally generated in degree at most 6.
Radial Distortion Self-Calibration (Roland Angst)
In computer vision, multiple-view geometry addresses the problem of jointly inferring the 3D structure of the scene and the position of the camera from 2D image point correspondences. Approximating a real camera with a pinhole camera model leads to algebraic constraints between the coordinates of corresponding image points. Those constraints are captured by multi-view tensors (e.g. fundamental matrix, trifocal and quadrifocal tensor) which can be computed from 2D point correspondences with tools from algebraic geometry. In my talk, I will provide a short introduction to multiple-view geometry and present an extension to handle images which are captured with cameras with imperfect lenses that introduce severe radial distortion. We will see how geometric intuition can guide us to find an algebraic solution to infer unknown camera and distortion parameters.
Orthogonally Invariant Varieties in Vision (Hon-Leung Lee)
Finding the closest fundamental matrix and the closest essential matrix are two crucial minimization problems in computer vision. We provide a framework, based on "transfer principles" and singular value decomposition, to understand the geometric picture behind these problems. Generally, given any problem of finding the closest matrix in an orthogonally invariant set, our framework is helpful in computing and counting the real smooth critical points of the problem, as well as finding the minimizers. We will also discuss the connections of this theory to the notion of Euclidean distance degree of a variety. This is joint work with D. Drusvyatskiy and R. Thomas.
Talk Material 1: /
15:30 - 17:30 MS52: Maximum Likelihood Degrees and Critical Points 2
June Huh (Princeton University), Hwangrae Lee (POSTECH), Pierre-Jean Spaenlehauer (Inria), Mohab Safey el Din (Université Pierre et Marie Curie),
The likelihood correspondence and the maximum likelihood degree of the reciprocal linear forms (June Huh)
The critical points of a product of powers of polynomial functions are parametrized by a “likelihood correspondence”. In the special case of linear polynomials, one can recover the Poincaré polynomial of the associated complex hyperplane arrangement complement from the homology class of this variety in its natural embedding. We prove an analogous formula for the reciprocal plane, that is, the image of the arrangement complement under the reciprocal map, by computing its Chern-Schwartz-MacPherson class. Joint work with Graham Denham.
Euclidean Distance Degrees of Multiple Root Loci (Hwangrae Lee)
Univariate polynomials of a fixed degree form a projective space, and polynomials having a root of fixed multiplicity form a projective subvariety. We determine the Euclidean distance degree for such a variety, in both special and generic coordinates, and we present an algorithm for solving the ED problem exactly. This is joint work with Bernd Sturmfels.
Exact solutions in Structured Low-Rank Approximation (Pierre-Jean Spaenlehauer)
Structured low-rank approximation is the problem of minimizing a weighted Frobenius distance to a given matrix among all matrices of fixed rank in a linear space of matrices. We study the critical points of this optimization problem from the viewpoint of exact algebraic algorithms and algebraic geometry. In particular, an indicator of the complexity of Gröbner bases algorithms and homotopy methods is the algebraic degree of this problem. This corresponds to the Euclidean Distance degree of a linear section of a determinantal variety. Using algebraic geometry, we present bounds on this degree in several cases. A particular focus lies on Hankel matrices, Sylvester matrices and generic linear spaces. Joint work with Giorgio Ottaviani and Bernd Sturmfels.
On the Degree of Generalized Polar Varieties (Mohab Safey EI Din)
We consider the critical points of the restriction of a polynomial function to an algebraic set. These critical points are solutions of the defining equations of the considered algebraic set and minors of some jacobian matrix. This system defines a so-called generalized polar variety. Intrinsic estimates of the degree of this variety are of first importance. We essentially relate this degree to the degrees of the polar classes of the algebraic set under consideration. We also show how to obtain an algorithm that computes the critical locus in time which is polynomial in its cardinality. Joint work with Pierre-Jean Spaenlehauer.
Talk Material 3: /
15:30 - 17:30 MS53: Core Algorithms in Algebraic Geometry 1
Hans Schoenemann (TU Kaiserslautern), Shuhong Gao (Clemson University), Janko Boehm (TU Kaiserslautern), Michael Stillman (Cornell University),
Parallelization and primary decomposition (Hans Schoenemann)
Primary decomposition is an ambitious example which demonstrate a bunch of algorithms, mainly based on Groebner bases. Groebner bases can be combined like a "black box" into higher level algorithms or itself modified to return the desired result. Classicaly all these algorithms are sequential but allow paralleliziation at several levels. Experience with coarse grain paralleliziation (at the level of processes) will be discussed, leaving the fine grain paralleliziation (at the level of threads) to the "black box" Groebner base computation.
Criteria for Groebner bases (Shuhong Gao)
Buchberger (1965) gives the first criterion for Groebner bases that leads to Buchberger's algorithm for computing Groebner bases. Faugere (2002) introduces signatures and rewritten rules to detect useless S-pairs, and his F5 algorithm is significantly much faster than Buchberger's algorithm. In the last ten years or so, there has been extensive effort trying to modify F5 in order to have simpler algorithms that work for arbitrary sequence of polynomials (not necessarily homogeneous) and have rigorous proofs for correctness and finite termination. In 2011, together with Frank Volny IV and Mingsheng Wang (see, we give a simple criterion for strong Groebner bases that contain Groebner bases for both ideals and the related syzygy modules. This criterion detects all useless J-pairs (similar to S-pairs) without any reduction. In this talk, we shall explain how our criterion gives a simple way of understanding signature-based algorithms, especially how it can be used to explain all the rewritten rules that are phrased in various forms in the literature from the last few years.
Modular Techniques in Computational Algebraic Geometry (Janko Boehm)
Computations over the rational numbers often suffer from intermediate coefficient growth. One approach to this problem is to determine the result modulo a number of primes and then lift to the rationals. This method is guaranteed to work if we use a sufficiently large set of good primes. In many applications, however, there is no efficient way of excluding bad primes. We develop a new technique for rational reconstruction which will nevertheless return the correct result, provided the number of good primes in the set is large enough. We discuss applications of this technique in computational algebraic geometry.
Integral bases of planes curves in small characteristic (Michael Stillman)
"Integral closures of plane curves have nice structure in characteristic zero, or large characteristic, and there are fast algorithms for computing a (local) integral basis in those cases, e.g. by using Puiseux expansions (van Hoeij, 1990's). These methods break down for small characteristic, which is an important case for coding theory. We describe a new method, utilizing the Frobenius action (in a manner different from Leonard's QthPower algorithm), of computing local integral bases, and therefore integral closures in the small characteristic case. These algorithms have been implemented in Macaulay2, and appear to be quite efficient in practice. (joint with Mark van Hoeij, Florida State Univ)"
Talk Material 1: / Talk Material 2: / Talk Material 3: /
KT 2
17:30 - 19:00 SIAG Business Meeting
18:00 - 19:00 Shuttle from NIMS to Hotel Interciti and Lotte City Hotel
Return to Hotel
19:45 - 21:30 Dinner for the attendance of SIAG meeting
TimeSpeaker/ Title/ Abstract/ VODLocation
08:00 - 08:45 Shuttle Bus to NIMS
Arrive at NIMS
09:00 - 10:00 IP08: Progress Report on Geometric Complexity Theory
Ketan Mulmuley (University of Chicago),
Loading the live streaming player...
Geometric complexity theory is an approach to the fundamental lower bound problems of complexity theory via algebraic geometry and representation theory. This talk will give an overview of some progress in this field.
KT 1
10:30 - 12:30 CP03: Contributed Session III
Yang QI (Gipsa-Lab), Liam Solus (University of Kentucky),
Uniqueness of Best Rank One Tensor Approximations (Yang QI)
It is important to find the best rank one approximations of a tensor in many areas. In this talk, we study singular vector tuples of a tensor because roughly speaking they are the critical points of the distance function. By this approach we show any tensor outside of a hypersurface has a unique best rank one approximation, and give a defining equation of this hypersurface.
A Polyhedral Description of Extremal Positive Semidefinite Matrices for Series-Parallel Graphs (Liam Solus)
Given a graph G on p vertices we consider the cone of concentration matrices associated to G, i.e. the cone of all p × p positive semidefinite matrices with zeros in entries corresponding to the nonedges of G. Due to its applications in PSD-completion problems and maximum-likelihood estimation, the geometry of this cone is of general interest. A natural pursuit in this geometric investigation is to characterize the possible ranks of the extremal rays of this cone. Two other well studied convex bodies associated to G are the cut polytope and its positive semidefinite relaxation, the elliptope of G. Via an application of standard spectrahedral duality we will see that the dual to the elliptope of G is the trace two affine section of the cone of concentration matrices. Using the geometric relationship between these four convex bodies we will see that, in the case of series parallel graphs, all possible extremal ranks of the cone of concentration matrices are given by the constants b where v general implications of these results will then be discussed. This talk is based on joint work with Caroline Uhler and Ruriko Yoshida. T x = b is a facet-supporting hyperplane of the cut polytope of G. The more
Talk Material 1: /
10:30 - 12:30 MS54: Polynomial Optimization and Moments 3
Wang Lin (Academia Sinica), Zhengfeng Yang (East China Normal University), Sunyoung Kim (Ewha W. University), Cordian Riener (Aalto University),
Safety verification of nonlinear hybrid systems via Darboux functions. (Wang Lin)
The task of safety verification of nonlinear hybrid systems can be formulated as computing Darboux functions, which satisfy several multivariate inequalities. In general, searching such Darboux functions is equivalent to solving semi-algebraic systems with parameters. Instead of applying Cylindrical Algebraic Decomposition(CAD) methods,here we present a new method, based on symbolic-numeric computation, to compute Darboux functions for verifying safety property of hybrid systems. A sampling-based method is applied to relax the problem of computing Darboux functions as a special quadratically constrained quadratic program, which can be exactly solved by applying an alternating iterative projection algorithm. In addition, our approach is also applicable to safety verification for non-polynomial hybrid systems. We also demonstrate the practical performance of our algorithms on several benchmark examples.
Sparse multivariate function recovery from values with noise and outlier errors (Zhengfang Yang)
Error-correcting decoding is generalized to multivariate sparse rational function recovery from evaluations that can be numerically inaccurate and where several evaluations can have severe errors("outliers"). Here we present an algorithm that can interpolate a sparse multivariate rational function from evaluations where the error rate is 1/q for any q>2. Our multivariate polynomial and rational function interpolation algorithm combines Zippel's symbolic sparse polynomial interpolation technique with the numeric algorithm, and removes outliers("cleans up data") through techniques from error correcting codes. Our multivariate algorithm can build a sparse model from a number of evaluations that is linear in the sparsity of the model. This is joint work with Erich L. Kaltofen
Lagrangian Doubly Nonnegative Relaxations of Polynomial Optimization Problems (Sunyoung Kim)
We consider the polynomial optimization problem: Given a real valued function f_0 defined on R^n and a subset S of R^n, find an x^* in S that minimizes f_0 over S, i.e. such that f_0(x) >= f_0(x^*) for all x in S. If the feasible region is described in terms of inequalities S = { x in R^n | f_p(x)<=0 (p=1,...,m), x_i is integer for i=1,...,r} for some r in {0,...,n}, where f_p : R^n -> R, (p=1,....,n), then a general optimization problem can be written as (P) minimize f_0(x) subject to x in S. We propose a Lagrangian-conic relaxation of POP (P) and discuss theoretical properties of the relaxation. In particular, the simplified Lagrangian-doubly nonnegative relaxation of POP (P) is derived for developing efficient numerical algorithms. Numerical results will be shown to demonstrate the efficiency of the proposed numerical algorithm.
Quadrature formulae and Polynomial Optimization (Cordian Riener)
It is well-known that for each positive Borel measure on $\R^n$ and each fixed degree $d$, one can find finitely many nodes in $\R^n$ and corresponding nonnegative weights such that the integral of a polynomial of degree at most $d$ equals the corresponding weighted sum of point evaluations. The data consisting of the nodes and corresponding weights is called a quadrature formula. We interpret the problem of finding such a formula for a given measure as a polynomial optimization problem. This allows us to give upper bounds on the number of nodes needed. This is joint work with Markus Schweighofer.
Talk Material 4: /
KT 1
10:30 - 12:30 MS55: Applications of Polynomial Systems Solving in Cryptology 1
Maike Massierer (Inria Nancy), Koh-ichi Nagao (Kanto Gakuin Univ.), Elisa Gorla (University of Neuchatel), Frank Quedenfeld (TU Braunschweig),
Index Calculus in the Trace Zero Variety (Maike Massierer)
The trace zero variety associated to an elliptic curve is an abelian variety defined over a finite field $\mathbb{F}_q$. Its $\mathbb{F}_q$-rational points yield a finite group, the trace zero subgroup of the Picard group of the original curve. This group has been proposed for use in cryptographic systems based on the discrete logarithm problem by Frey and for use in pairing-based cryptographic systems by Rubin and Silverberg. In order to investigate the hardness of the discrete logarithm problem in trace zero varieties, we propose an index calculus algorithm, following the approach of Gaudry for index calculus in abelian varieties of small dimension. In practice, the bottleneck of this computation is the solution of a large number of polynomial systems. In this talk, we discuss how these systems arise, which properties they have, and how efficiently they can be solved using standard Gröbner basis software.
Equation systems coming from Weil descent and the elliptic curve discrete logarithm problem (Koh-ichi Nagao)
Faug\`ere et al. show that the decomposition problem of a point of elliptic curve over binary field $\mathbb{F}_{2^n}$ reduces to solving low degree equations system over $\mathbb{F}_2$ coming from Weil descent. Using this method, the discrete logarithm problem of elliptic curve over $\mathbb{F}_{2^n}$ reduces to linear constrains, i.e., solving equations system using linear algebra of monomial modulo field equations, and its complexity is expected to be subexponential of input size $n$. However, it is a pity that at least using linear constrains, it is exponential. Petit et al. show that assuming first fall degree assumption, from which the complexity of solving low degree equations system using Gr\"obner basis computation is subexponential, its total complexity is heuristically subexponential. In this talk, we give the precise estimation of first fall degree and revise the results of Petit et al. and show that the discrete logarithm problem of elliptic curve over small characteristic field $\mathbb{F}_{p^n}$ ($p$ is not restricted by $2$) is subexponential of input size $n$ under first fall degree assumption.
Optimal representations for trace zero subgroups (Elisa Gorla)
The trace zero subgroup is a subgroup of the divisor class group of a (hyper)elliptic curve, defined over a finite field. Being able to represent the elements of this group as compactly (i.e., using as few field elements) as possible is relevant in the framework of elliptic curve cryptography. In this talk, I will introduce the trace zero subgroup relative to a field extension of even degree, and give an optimal representation for its elements. This is the first optimal representation for the elements of this group.
Solving Sparse Polynomial Systems and Applications in (Lightweight) Cryptography (Frank Quedenfeld)
In cryptography a symmetric primitive can be represented by a huge nonlinear system of equations. Depending on the modeling of the primitive one can derive various systems of equations which need different solving techniques and are differently hard to solve. Therefore we represent a modeling technique for symmetric primitives and a solver based on Elimination of Linear variables (ElimLin). ElimLin is a well known part of modern groebner basis algorithms. The solver can handle sparse, quadratic systems of equations with up to 10^6 monomials, variables and equations. We use it to attack two lightweight ciphers, namely Trivium and Katan.
Talk Material 1: / Talk Material 2: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS56: Core Algorithms in Algebraic Geometry 2
Anton Leykin (Georgia Tech), Santiago Laplagne (U de Buenos Aires), Wolfram Decker (Universität Kaiserslautern), Anders Jensen (Aarhus University),
Homotopy continuation vs. Groebner bases for parametric systems (Anton Leykin)
"Given a parametric system of polynomial equations with finitely many solutions for a generic choice of parameters, one may consider finding these solutions either symbolically via GB methods or numerically via polynomial homotopy continuation. In both cases one generic instance is solved and the solution is stored and used to solve another generic instance. This talk will showcase both approaches in application to minimal problems in computer vision (see a related talk in ""Algebraic Vision"" minisymposium) and several experimental implementations of the corresponding algorithms in Macaulay2."
Computing integral bases via localization and Hensel Lifting (Santiago Laplagne)
We present a new algorithm for computing integral bases in algebraic function fields, or equivalently for constructing the normalization of a plane curve. Our basic strategy makes use of localization and, then, completion at each singularity of the curve. In this way, we are reduced to finding integral bases at the branches of the singularities. To solve the latter task, we work with suitably truncated Puiseux expansions. In contrast to a previous algorithm by van Hoeij, which also relies on Puiseux expansions, we use Hensel's lemma as a key ingredient. This allows us to compute factors corresponding to groups of conjugate Puiseux expansions, without actually computing the individual expansions. In this way, we make substantially less use of the Newton-Puiseux algorithm. In addition, our algorithm is inherently parallel. As a result, it outperforms in most cases any other algorithm known to us by far. Typical applications are the computation of adjoint ideals and, based on this, the computation of Riemann-Roch spaces and the parametrization of rational curves. Joint work with Janko Boehm, Wolfram Decker and Gerhardd Pfister.
Groebner Bases over Algebraic Number Fields (Wolfram Decker)
Although Buchberger's algorithm, in theory, allows us to compute Groebner bases over any field, in practice, however, the computational efficiency depends on the ground field. In this lecture, we present a new modular method to compute a Groebner basis over a simple algebraic extension of the rationals.
Tropical homotopy continuation (Anders N. Jensen)
One way to compute the mixed volume of a set of lattice polytopes is to translate the polytopes into polynomials with random coefficients. By the BKK theorem, solving this system will give the mixed volume as this number is the number of solutions to the system. In this talk we will tropicalise the process by introducing the tropical homotopy continuation method. It is a combinatorial process working on tropical hyperplanes whose coefficients are changed continuously. If we tropicalise the entire regeneration process of numerical algebraic geometry, we get a method for solving n generic tropical equations in n variables. In particular, the numerical method for computing the mixed volume now is a combinatorial one. It can be used as a preprocessing step before doing an actual numerical polyhedral homotopy. We report on experiments with the implementation.
Talk Material 2: / Talk Material 3: /
KT 2
10:30 - 12:30 MS57: Combinatorial Methods in Algebraic Geometry 2
Luke Oeding (Auburn University), Elisa Postinghel (University of Leuven), Greg Smith (Queens University), Bernd Sturmfels (UC Berkeley (USA) / NIMS),
Staircase flattenings and the border rank of monomials (Luke Oeding)
The polynomial Waring problem is to write a polynomial as linear combination of powers of linear forms in the minimal possible way. The minimal number of summands is called the rank of the polynomial. The solution in the case of monomials was given in 2012 by Carlini--Catalisano--Geramita, and independently shortly thereafter by Buczynska--Buczynski--Teitler. If the polynomial in question can be expressed as a limit of polynomials of rank r, we say that it has border rank r. In this talk I will provide the solution to the border rank problem for monomials. Upper bounds on border rank were known since Landsberg-Teitler, 2010 and earlier. Our method to provide lower bounds (which agree with the upper bounds) is to provide polynomial certificates. The construction of these certificates relies on Young tableaux combinatorics and a refined version of the Pieri rule that I will describe. This is work in progress with Kangjin Han (DGIST).
On the effective cone of $\mathbb{P}^n$ blown-up at $n+3$ points (Elisa Postinghel)
We give the facets of the effective, movable and ample cones of divisors on the $n$-projective space blown-up at $n+3$ general points. These are obtained from the description of the base locus of linear systems of hypersurfaces of $\mathbb{P}^n$ of fixed degree interpolating $n+3$ general points with assigned multiplicities. This also yields a combinatorial formula for the expected dimension of such linear systems, completing a conjecture in the commutative algebra setting due to Froeberg and Iarrobino. This is joint work with M.C. Brambilla and O. Dumitrescu
Toric Vector Bundles (Greg Smith)
How do the properties of line bundles extend to vector bundles? After reviewing the basic features of toric vector bundles, we will introduce a collection of convex polytopes associated to a toric vector bundle. Lattice points in these polytopes correspond to generators for the space of global sections and edges are related to jets. These polyhedral tools also lead to new bundles with an intriguing mix of positivity properties. This talk is based on joint work with Sandra Di Rocco and Kelly Jabbusch.
Exponential Varieties (Bernd Sturmfels )
Exponential varieties arise from exponential families in statistics. These real algebraic varieties have strong positivity and convexity properties, generalizing those of toric varieties and their moment maps. Another special class, including Gaussian graphical models, are varieties of inverses of symmetric matrices satisfying linear constraints. We present a general theory of exponential varieties, with focus on those defined by hyperbolic polynomials. This is joint work with Mateusz Michalek, Caroline Uhler and Piotr Zwiernik.
Talk Material 2: / Talk Material 3: / Talk Material 4: /
10:30 - 12:30 MS58: Geometric Complexity Theory
Christian Ikenmeyer (Texas A&M University), Joseph Landsberg (Texas A&M University), Michael Walter (Stanford), Hwangrae Lee (POSTECH),
Permanent versus determinant: not via saturations of monoids of representations (Christian Ikenmeyer)
Let Det_n denote the closure of the GL_{n^2}(C)-orbit of the determinant polynomial det_n with respect to linear substitution. The highest weights (partitions) of irreducible GL_{n^2}(C)-representations occurring in the coordinate ring of Det_n form a finitely generated monoid S(Det_n). We prove that the saturation of S(Det_n) contains all partitions lambda with length at most n and size divisible by n. This implies that representation theoretic obstructions for the permanent versus determinant problem must be holes of the monoid S(Det_n). This is joint work with Peter Bürgisser and Jesko Hüttenhain
An exponential lower bound for permanent v. determinant assuming symmetry and a possible new path towards Valiant's conjecture. (Joseph Landsberg)
Recently Grenet's expression for the 3x3 permanent as a size 7 determinant was shown to be optimal by Alper Bogart and Velasco. Motivated by this result, N. Ressayre and I undertook a study of the geometry of Grenet's expression for the mxm permanent as a size 2^m-1 determinant. We show his expressions are optimal among algorithms admitting symmetry. Thus if one could show any expression for the permanent as a determinant admits a slightly larger expression with symmetry, one could prove Valiant's conjecture.
Moment Polytopes of Finite-Dimensional Representations and their Computational Complexity (Michael Walter)
In recent work, we have given a general description of the moment polytope associated with a finite-dimensional unitary representation of a compact, connected Lie group. Apart from being computationally straightforward to use, it has some interesting theoretical implications, such as on the computational complexity of the corresponding membership problem. I will discuss our results in the context of the Kronecker polytopes, which feature in the quantum marginal problem in physics and in the geometric complexity theory program in computer science.
Power sum decompositions of elementary symmetric polynomials (Hwangrae Lee)
Concerning the Waring problem, an easiest class next to monomials would be elementary symmetric polynomials. In this talk I will give decompositions of them, which sometime admits the lower rank obtained by the apolarity lemma. These decompositions are given over the real field, hence we see that the real rank of a hyperbolic polynomial can be the same with the complex rank.
Talk Material 1: /
10:30 - 12:30 MS59: Aspects of Grassmann Manifolds With a view towards Applications
Joachim Rosenthal (University of Zurich), Hirotachi Abo (University of Idaho), Clayton Shonkwiler (Colorado State University), Ke Ye (University of Chicago),
How Grassmannians are relevant in Coding Theory (Joachim Rosenthal)
In this overview talk we explain how different concepts in coding theory are closely related to geometric questions of Grassmannians.
On Grassmann secant varieties of Grassmann varieties (Hirotachi Abo)
This talk concerns a problem of finding the smallest positive integer $s(m,k,n)$ such that $(m+1)$ generic skew symmetric $(k+1)$-forms in $(n+1)$ variables as linear combinations of the same $s(m,n,k)$ decomposable symmetric $(k+1)$-forms. This problem is analogous to Waringʼs problem for forms and can be naturally translated into a classical problem in algebraic geometry. In this talk, I will go through some basics of algebraic geometry, describe how objects in algebraic geometry can be associated to systems of skew-symmetric forms, and discuss algebro-geometric approaches to establish the existence of triples $(m,n,k)$, where $s(m,n,k)$ is more than expected.
The Geometry of Polygon Spaces (Clayton Shonkwiler)
An equilateral polygon in Euclidean 3-space is a piecewise-linear closed loop consisting of equal-length steps. Such polygons provide the standard idealized model of ring polymers like viral DNA, so there is a keen interest both in analyzing the geometric probability theory of random polygons and in developing fast sampling algorithms and dynamic simulation techniques. I will describe some of the most exciting recent developments in this field, which are based on an understanding of moduli spaces of equilateral polygons as symplectic reductions of complex Grassmannians or of products of spheres. The symplectic theory was largely inspired by a corresponding story in algebraic geometry, where polygon spaces are realized as GIT quotients of Grassmannians or of products of the projective line. Aside from an approach to correcting numerical drift which I will discuss, the potential applications of this algebraic picture are largely unexplored. This talk describes joint work with Jason Cantarella (University of Georgia) and Tetsuo Deguchi and Erica Uehara (Ochanomizu University).
Schubert varieties and the distance between linear subspaces of different dimensions (Ke Ye)
The distance between linear subspaces of the same dimension is well known. It is determined by the Riemannian geometry of Grassmannians. In practice, we always want to compare linear subspaces of different dimensions. Based on the Geometry of Grassmannians and Schubert varieties, we find a natural way to compare the distance between linear subspaces of different dimensions. In fact, there are two candidates for the distance between linear subspaces of different dimensions, but in this talk we will show that they are the same. We will also present an explicit formula for the distance between linear subspaces of different dimensions, which involves only the SVD of a matrix. At the end of the talk, we will ask some open problems related to this topic. This is joint work with Lek-Heng Lim (Chicago).
Talk Material 1: / Talk Material 2: / Talk Material 3: /
10:30 - 12:30 MS60: Maximum Likelihood Degrees and Critical Points 3
Fatemeh Mohammadi (Osnabruck), Caroline Uhler (Institute of Science and Technology Austria), Piotr Zwiernik (UC Berkeley), Paolo Lella (University of Trento),
A family of quasisymmetry models (Fatemeh Mohammadi)
We present a one-parameter family of models for square contingency tables that interpolates between the classical quasisymmetry model and its Pearsonian analogue. Algebraically, this corresponds to deformations of toric ideals associated with graphs. Moreover we show that these models belong to a broader class of $\phi$-divergence QS models. Measures of divergence quantify the distance between two probability distribution. Our discussion of the statistical issues centers around maximum likelihood estimation. Joint work with Maria Kateri and Bernd Sturmfels.
Exponential varieties and hyperbolic polynomials (Part I) (Caroline Uhler)
Exponential varieties arise from exponential families in statistics. These real algebraic varieties have strong positivity and convexity properties, generalizing those of toric varieties and their moment maps. Another special class, including Gaussian graphical models, are varieties of inverses of symmetric matrices satisfying linear constraints. We develop a general theory of exponential varieties, with focus on those defined by hyperbolic polynomials. Joint work with Mateusz Michałek, Bernd Sturmfels, and Piotr Zwiernik.
Exponential varieties and hyperbolic polynomials (Part II) (Piotr Zwiernik)
Exponential varieties arise from exponential families in statistics. These real algebraic varieties have strong positivity and convexity properties, generalizing those of toric varieties and their moment maps. Another special class, including Gaussian graphical models, are varieties of inverses of symmetric matrices satisfying linear constraints. We develop a general theory of exponential varieties, with focus on those defined by hyperbolic polynomials. Joint work with Mateusz Michałek, Bernd Sturmfels, and Caroline Uhler.
The maximum likelihood degree of Fermat hypersurfaces (Paolo Lella)
We study the critical points of the likelihood function over the Fermat hypersurface. This is a nice example of how algebro-geometric tools can contribute to the problem of maximum likelihood estimation. In particular, using a flat degeneration we show that the ML degree of the Fermat hypersurface can be determined considering special data on the model. Then, we exploit symmetries subdividing the problem into parallel subtasks and we develop algorithmic methods that allow to compute the ML degree in many cases. Joint work with Daniele Agostini, Davide Alberelli and Francesco Grande.
Talk Material 2: / Talk Material 4: /
12:30 - 13:00 Lunch
Cafeteria 1, 2
14:00 - 16:00 MS61: Computational Approach to GIT and Moduli Theory 2
David Swinarski (Fordham University), HyunBin Loh (POSTECH), Dao Phuong Bac (GAIA-POSTECH),
GIT calculations from the state polytope point of view (David Swinarski)
In several recent papers by Byun, Fedorchuk-Smyth, Gallardo, and others, geometric invariant theory stability is proved by verifying stability with respect to a finite list of 1-parameter subgroups. We discuss these results from the point of view of state polytopes.
The converse of a theorem by Bayer and Stillman (Hyunbin Loh)
Let $I$ be an ideal in a polynomial ring $S$ and $\tau$ be a monomial order on $S$. By the upper-semicontinuity of graded Betti numbers, we have $reg(in_\tau(I)) \ge reg(I)$. However in general coordinates and when $\tau$ is the graded reverse lexicographic order(rlex), Bayer and Stillman showed that $reg(in_{rlex}(I))=reg(I)$ \cite{BaSt}. This implies that rlex is an optimal order for the computation of Gr\"obner bases. We show that the graded reverse lexicographic order is the unique monomial order $\tau$ satisfying $reg(gin_\tau(I)) = reg(I)$ for all ideals $I$. This implies that rlex is the unique optimal order regarding degree complexity. We also show that if $gin_{\tau_1}(I) = gin_{\tau_2}(I)$ for all $I$, then $\tau_1 = \tau_2$.
Stability revisited (Dao Phuong Bac)
Let G be a linear algebraic group acting on the vector space V via representation ρ ∶ G → GL(V ) defined over an algebraically closed field k, and let v ∈ V be any nonzero vector. In this talk, I present some recent results (joint with D. Hyeon) regarding the relationship between the notion of generic stability (stability with respect to general maximal tori) for v and stability with respect to the center of G in the case that G is reductive. These observations are inspired from the recent fact that all nonzero vectors v are generically stable due to Donghoon Hyeon when G is a semisimple group.
Talk Material 1: / Talk Material 2: / Talk Material 3: /
14:00 - 16:00 MS62: Parametrization of Rational Curves in Projective Space
Ron Goldman (Rice University), XIAOHONG JIA (Chinese Academy of Sciences), David Cox (Amherst College), David Cox (Amherst College),
Explicit $\mu$-Bases for Low Degree Rational Curves (Ron Goldman)
$\mu$-bases for rational curves are important in Computer Aided Geometric Design because we can use μ-bases to find compact representations for the implicit equation of a rational planar curve. Moreover, $\mu$-bases for rational curves in arbitrary dimensions can be applied to locate and analyze their singularities. There are fast algorithms for computing $\mu$-bases for rational curves based mainly on Gaussian Elimination. However, we do not know what the $\mu$-bases look like before we run the algorithm; this drawback prevents us from finding closed formulas for the singularities or the implicit equation for rational curves. In this talk we derive explicit formulas for the $\mu$-bases of conic sections and planar rational cubic curves. Using the μ-bases for planar rational cubic curves, we find explicit formulas for their implicit equations and double points. We also extend the explicit formula for the $\mu$-bases of conic sections to $\mu$-bases for rational curves of degree $n$ in $n$–dimensions.
Set-theoretic generators of rational space curves (Xiaohong Jia)
We show how to calculate three low degree set-theoretic generators (i.e., algebraic surfaces) for all rational space curves of low degree (degree 6) as well as for all higher degree rational space curves where at least one element of their $\mu$-basis has degree 1 from a $\mu$-basis of the parametrization. In addition to having low degree, at least two of these surface generators are always ruled surfaces. Whenever possible we also show how to compute two set-theoretic complete intersection generators for these rational space curves from a $\mu$ -basis of their parametrization.
Strata of rational space curves (David A. Cox)
A rational space curve has a degree and a $\mu$-type. This talk, based on joint work with Tony Iarrobino, will describe the structure of the set of all parametrizations with given degree and $\mu$-type, what we call $\mu$-strata. I will compute the dimension of the strata and describe how they fit together. I will also present results about non-proper parametrizations and rational normal scrolls.
Rees algebras of rational plane curves (David A. Cox)
A rational plane curve is parametrized by homogeneous polynomials $a,b,c$ of the same degree. These generate an ideal $I$ in the polynomial ring $R$ of the parameters. The moving curve ideal defined in geometric modeling gives the defining equations of the Rees algebra of I from commutative algebra. This talk will survey known results and discuss the work of Kustin, Polini and Ulrich in degree 6 and Madsen in degree 7.
Talk Material 3: / Talk Material 4: /
KT 1
14:00 - 16:00 MS63: Applications of Polynomial Systems Solving in Cryptology 2
Pablo A. Parrilo (Massachusetts Institute of Technology), Tim Hodges (Colorado State University), Igor Semaev (University of Bergen), Bo-Yin Yang (Academia Sinica),
Chordal Structure and Polynomial Systems (Pablo A. Parrilo)
Techniques based on chordal structure and bounded treewidth have been extensively studied in linear algebra, graphical models, constraint satisfaction, database theory, and many other areas. It is natural then to analyze to what extent chordality might also help to solve systems of polynomial equations. To this end, we propose a new technique, which we refer to as chordal elimination, that relies in elimination theory and Gröbner bases. By maintaining the graphical structure of the input polynomial system in all computations, chordal elimination can outperform standard Gröbner basis algorithms in many cases. Besides the theoretical developments, in this talk we will illustrate the suitability of our methods in examples arising from graph colorings, cryptography, sensor localization and differential equations. Based on joint work with Diego Cifuentes (MIT).
Weil-Descent, First-Fall Degree and Complexity of Grobner basis Algorithms (Tim Hodges)
We describe some recent results concerning the first fall degree of systems of polynomial equations arising from Weil Descent and their connections to heuristic estimates of the complexity of Grobner basis algorithms on such systems.
New results in the linear cryptanalysis of DES (Igor Semaev)
In 1993-1994 Matsui introduced linear cryptanalysis for block ciphers. It is based on a notion of linear approximation. At Crypto '94 he showed how to break DES with two best approximations by using 2^{43} known plain-text/cipher-text blocks. Heuristically he estimated the success probability of his attack to be 0.85. Though several extensions of linear cryptanalysis using multiple linear approximations were published since then, most of them do not provide success probability estimates. In particular, no such estimates are known for adaptations of Matsui's Algorithm 2 which is of most importance. In this paper we present a new algorithm to find a round block cipher key by using several linear approximations based on solving a system of Multiple Right Hand Side (MRHS) linear equations in key bits. We are able to predict the success probability of the algorithm. For instance, with 10 best approximations and 2^{43} known plain-text/cipher-text blocks and with the same complexity the success probability of the attack on 16-round DES is 0.8925. The suggested theory was validated by computer experiments with 8-round DES.
Enumerations and Groebner Bases methods on generic multivariate polynomial systems (Bo-Yin Yang)
For at least one decade, the de facto standard for cryptographers for measuring the complexity of solving equations in general has been the F4/F5 algorithms. However, in the last few years, there are papers pointing out circumstances where these may not be best to estimate the complexity of a cryptosystem. We will discuss some state of the art methods in various situations, including brute-force. We will also investigate how much of a difference does the use of these alternative methods make.
Talk Material 3: /
14:00 - 16:00 MS64: Recent developments in Geometric and algebraic Methods in Economics
Yoshinori Shiozawa (Osaka City University), Marco Grazzi (University of Bologna), Masashi Morioka (Ritsumeikan University),
Subtropical Convex Geometry as the Ricardian Theory of International Trade. (Yoshinori Shiozawa)
The Ricardian theory of international trade is one of the oldest theories in economics. Nonetheless, it is by no means trivial and continues to attract curiosity of many modern economists. The subtropical geometry is just a tropical geometry based on min-times or max-times semirings. A set of wage rate vectors and a set of price vectors, when restricted to those related to efficient pro- ductions are convex in the subtropical sense. Together with world production frontier, these three sets give three kinds of cell complexes in different spaces. They are iso- morphic by natural correspondences between them. This makes it possible to analyze one kind of complexes by ex- amining another kind of complexes. McKenzie-Minabe dia- gram sheds lights on connections between mixed sub- divisions of a product of simplices and the production frontier cell complexes. Underlying this relationship is the natural isomorphism between tropical algebra and sub- stropical algebra. A logarithmic map of coefficients inter- venes in a natural way. Almost all discussions in the trade theory thus can be translated into the language of subtropical geometry. Indeed, the Ricardian trade theory is just a concrete instance of the subtropical geometry. It provides a natural connection between various fields of mathematics including subtropical geometry, tropical mat- roids, Minkowski sum, cephoids(i.e. Minkowski sum of co-framed simplices), Caley trick, mixed subdivisions and transportation problem. Most of these connections are not yet widely recognized.
Production Theory and Zonotopes: Accounting for Firm Heterogeneity and Technical Change (Marco Grazzi)
In this talk we will present a new framework to assess firm level heterogeneity and to study the rate and direction of technical change. Building on the analysis of revealed short-run production functions by Hildenbrand in 1981, we propose the (normalized) volume of the zonotope composed by vectors-firms in a narrowly defined industry as an in- dicator of inter-firm heterogeneity. Moreover, the angles that the main diagonal of the zonotope form with the axes provides a measure of the rates and directions of technical change over time. The proposed framework can easily ac- count for n-inputs and m-outputs and, crucially, the meas- ures of heterogeneity and technical change do not require many of the standard assumptions from production theory.
Polynomial Equation Systems that Arise from Divisible Good Auctions (Mariann Ollar)
The theoretical study of divisible good auctions for non-symmetrically informed bidders becomes challenging as without symmetric equilibrium the solutions for the characterizing polynomial equation system are analytically intractable. Algorithmic Polynomial Equation Solvers prove to be quite successful and find finitely many solutions. The project aims to uncover algebraic properties of the equation systems so as to count the number of solutions and the distance between the solutions. Our findings are relevant from a market design perspective and provide under- standing for situations with asymmetrically informed bidders. (joint with David Dynerman)
Stability of Multi-Sector Quantity Adjustment Process with Sales Forecasting by Moving Average (MASASHI MORIOKA)
We present multi-sector models of pure quantity adjust- ment process in the sense that prices of goods are kept constant for the periods under consideration. In these models each firm decides amounts of production of finished goods and orders for raw materials. The signals used by firms for these decisions are (1) current levels of its inventory stock (both of input and output) and (2) sales forecast by moving average of its past sales. Through the derivation of a series of stability conditions, it is proved that averaging in sales forecast has a powerful stabilizing effect in comparison with the case in which each firm follows static (myopic) expectation. However, this stabilizing effect depends not only on the spectrum radius of input matrix but also on the whole structure of input coefficient matrix in somewhat complicated manner. Thus, inter- dependence between sectors is itself one of important factors influencing stability of the process.
Talk Material 1: / Talk Material 2: /
14:00 - 16:00 MS65: Holonomic Functions and Holonomic Gradient Method
Christoph Koutschan (Austrian Academy of Sciences), Raimundas Vidunas (The Univesity of Tokyo), Tomonari Sei (Keio University), Yoshiaki Goto (Kobe University),
Computer-Algebra-Based MIMO Performance Analysis (Christoph Koutschan)
The solutions of linear systems of partial differential equations and/or recurrence equations are---under mild additional conditions---called ``holonomic''. Holonomic functions have attained considerable attention because their closure properties allow for an algorithmic treatment and proof theory, implemented in computer algebra systems, and because many functions appearing in applications fall into this class. We consider the performance evaluation and analysis of multiple-input/multiple-output (MIMO) wireless communication systems, where important quantities of interest turn out to be holonomic, but difficult to evaluate numerically. We demonstrate how the holonomic gradient method can overcome this problem. This is joint work with Constantin Siriteanu, Takao Onoye, and Akimichi Takemura.
Difference-differential relations for the PDF of the largest root of the Wishart distribution (Raimundas Vidunas)
The distribution of the largest root of the random matrices in the Wishart distribution is important, for example, in application to wireless communication with multiple antennas and receivers. We derive the holonomic systems for the largest root of 2x2 and 3x3 matrices in a complex case of the Wishart distribution. The holonomic systems for the mean and standard deviation of the largest root are derived as well, and a few explicit formulas are obtained.
Computation of alternative multivariate t-distributions by the holonomic gradient method (Tomonari Sei)
The alternative multivariate t-distribution is defined by a component-wise scale mixture of the multivariate normal distributions. In this talk, we derive the Pfaffian system of the distribution with respect to the mean and concentration parameters. Numerical results on the holonomic gradient method are reported. This is a joint work with Kazuki Nakamoto.
Hypergeometric Functions and Contingency Tables (Yoshiaki Goto)
The normalizing constants of contingency tables are related to hypergeometric functions. To study the normalizing constants, we can use some properties of the hypergeometric functions. In this talk, I would like to show some examples in which properties of the hypergeometric functions are applied to problems of statistics.
Talk Material 1: / Talk Material 2: /
KT 2
16:30 - 17:30 IP09: Hodge Theory and Combinatorics
June Huh (Princeton University),
A conjecture of Read predicts that the coefficients of the chromatic polynomial of any graph form a log-concave sequence. A related conjecture of Welsh predicts that the number of linearly independent subsets of varying sizes form a log-concave sequence for any configuration of vectors in a vector space. All known proofs use Hodge theory for projective varieties, and the more general conjecture of Rota for possibly ‘nonrealizable’ configurations is still open. In this talk, I will argue that two main results of Hodge theory, the Hard Lefschetz theorem and the Hodge-Riemann relations, continue to hold in a realm that goes far beyond that of Kahler geometry. This cohomology theory gives strong restrictions on numerical invariants of tropical varieties, and in particular those of graphs and matroids. Joint work with Karim Adiprasito and Eric Katz.
Talk Material 1: /
KT 1
18:00 - 18:45 Shuttle from NIMS to Hotel Interciti and Lotte City Hotel
Return to Hotel
Schedule by Room
Date / TimeKT 1 (Building 1, 2F)
Mon 09:00-10:00IP01: The Euclidean Distance Degree of an Algebraic Variety
Giorgio Ottavani
Mon 10:30-12:30MS03: Algorithms and Complexity in Polynomial Systems 1
Frank Sottile / Martin Helmer / Pierre-Jean Spaenlehauer / Vissarion Fisikopoulos
Mon 14:00-15:00IP02: Some Current Directions in Coding Theory
Judy Walker
Mon 15:30-17:30MS11: Software and Applications in Numerical Algebraic Geometry 1
Daniel Brake / Abraham Martin del Campo / Nickolas Hein
Tue 09:00-10:00IP03: P–adic Integration and Number Theory
Minhyong Kim
Tue 10:30-12:30MS16: Nonnegative Rank
Hyenkyun Woo / Kaie Kubjas / Wotao Yin / Serkan Hosten
Tue 14:00-15:00IP04: Applications of Numerical Algebraic Geometry
Jonathan Hauenstein
Tue 15:30-17:30MS25: Software and Applications in Numerical Algebraic Geometry 2
Frank Sottile / Maria Isabel Herrero / Gregorio Malajovich
Wed 09:00-10:00IP05: Algebraic Codes and Invariance
Madhu Sudan
Wed 10:30-12:30MS33: Algorithms and Complexity in Polynomial Systems 2
Chee Yap / Michael Burr / James Davenport / Carlos D'Andrea
Thu 09:00-10:00IP06: Algebraic Vision
Rekha Thomas
Thu 10:30-12:30MS39: Polynomial Optimization and Moments 1
Igor Klep / Dennis Amelunxen / Sabine Burgdorf / Lihong Zhi
Thu 14:00-15:00IP07: Challenges in the Development of Open Source Computer Algebra Systems
Wolfram Decker
Thu 15:30-17:30MS47: Polynomial Optimization and Moments 2
Bruce Reznick / Chu Wang / Mohab Safey el Din / Amir Ali Ahmadi
Fri 09:00-10:00IP08: Progress report on Geometric Complexity Theory
Ketan Mulmuley
Fri 10:30-12:30MS54: Polynomial Optimization and Moments 3
Wang Lin / Zhengfeng Yang / Sunyoung Kim / Cordian Riener
Fri 14:00-16:00MS62: Parametrization of Rational Curves in Projective Space
Ron Goldman / XIAOHONG JIA / David Cox
Fri 16:30-17:30IP09: Hodge Theory and Combinatorics
June Huh
Date / TimeKT 2 (Building 1, 2F)
Mon 10:30-12:30MS07: Algebraic Structure in Graphical Models 1
Piotr Zwiernik / Shaowei Lin / Venkat Chandrasekaran / Yaokun Wu
Mon 15:30-17:30MS15: Markov Bases and their Applications in Statistics 1
Akimichi Takemura / Tobias Windisch / Despina Stasi / Uwe Nagel
Tue 10:30-12:30MS19: Tensor Decomposition: Ideals meet Applications 1
Ke Ye / Jaroslaw Buczynski / Ignat Domanov / Insong Choe
Tue 15:30-17:30MS29: Algebraic Structure in Graphical Models 2
Po-Ling Loh / Gautam Dasarathy / Seth Sullivant / Sung-Ho Kim
Wed 10:30-12:30MS35: Tensor Decomposition: Ideals meet Applications 2
Andrzej Cichocki / Kristian Ranestad / Hirotachi Abo / Elisa Postinghel
Thu 10:30-12:30MS41: Software and Applications in Numerical Algebraic Geometry 3
Daniel Bates / Brent Davis / Alan Liddell / Heather Harrington
Thu 15:30-17:30MS53: Core Algorithms in Algebraic Geometry 1
Hans Schoenemann / Shuhong Gao / Janko Boehm / Michael Stillman
Fri 10:30-12:30MS56: Core Algorithms in Algebraic Geometry 2
Anton Leykin / Santiago Laplagne / Wolfram Decker / Anders Jensen
Fri 14:00-16:00MS65: Holonomic Functions and Holonomic Gradient Method
Christoph Koutschan / Raimundas Vidunas / Tomonari Sei / Yoshiaki Goto
Date / TimeIBS (Building 1, 3F)
Mon 10:30-12:30MS06: Applications of Computational Algebraic Geometry to TheoreticalPhysics 1
Seung-Joo Lee / Rak-Kyeong Seong / Jonathan Hauenstein
Mon 15:30-17:30MS14: Algebraic Structures Arising in Systems Biology 1
Nikki Meshkat / Xiaoxian Tang / Carsten Conradi / Casian Pantea
Tue 10:30-12:30MS20: Applications of Computational Algebraic Geometry to Theoretical Physics 2
Burt Ovrut / Yang-Hui He / Michael Stillman / Cyril Matti
Tue 15:30-17:30MS28: Algebraic Structures Arising in Systems Biology 2
Mercedes Soledad Perez Millan / Elisenda Feliu / Carsten Wiuf / Bernd Sturmfels
Wed 10:30-12:30MS36: Algebraic Structures Arising in Systems Biology 3
Heather Harrington / Bernadette Stolz / Carina Curto / Nora Youngs
Thu 10:30-12:30MS44: Algebraic Vision 1
Irina Kogan / Anton Leykin / Joe Kileel / Manolis Tsakiris
Thu 15:30-17:30MS51: Algebraic Vision 2
David Dynerman / Luke Oeding / Roland Angst / Hon Leung Lee
Fri 10:30-12:30MS58: Geometric Complexity Theory
Christian Ikenmeyer / Joseph Landsberg / Michael Walter
Fri 14:00-16:00MS64: Recent Developments in Geometric and Algebraic Methods in Economics
Yoshinori Shiozawa / Marco Grazzi / Mariann Ollar / Masashi Morioka
Date / TimeCAMP 1 (Building 2, 2F)
Mon 10:30-12:30MS02: Coding Theory 1
Elisa Gorla / Yoonjin Lee / Relinde Jurrius / Heide Gluesing-Luerssen
Mon 15:30-17:30MS10: Coding Theory 2
Eimear Byrne / Daniele Bartoli / Amaro Barreal / Leo Storme
Tue 10:30-12:30MS17: Coding Theory 3
Anton Betten / Thomas Westerbäck / Alberto Ravagnani / Jon-Lark Kim
Tue 15:30-17:30MS24: Coding Theory and Cryptography 1
Kirill Morozov / Moon Sung Lee / Daniel Smith / Jon-Lark Kim
Wed 10:30-12:30MS32: Coding Theory 4
Edgar Martinez-Moro / Lingfei Jin / Felice Manganiello / Shuhong Gao
Thu 10:30-12:30MS40: Coding Theory and Cryptography 2
Tanja Lange / Daniel Bernstein / Jooyoung Lee / Rama Krishna Bandi
Thu 15:30-17:30MS52: Maximum Likelihood Degrees and Critical Points 2
June Huh / Hwangrae Lee / Pierre-Jean Spaenlehauer / Mohab Safey el Din
Fri 10:30-12:30MS55: Applications of Polynomial Systems Solving in Cryptology 1
Sebastian Kochinke / Koh-ichi Nagao / Elisa Gorla / Frank Quedenfeld
Fri 14:00-16:00MS62: Applications of Polynomial Systems Solving in Cryptology 2
Pablo A. Parrilo / Tim Hodges / Igor Semaev / Bo-Yin Yang
Date / TimeCAMP 2 (Building 2, 2F)
Mon 10:30-12:30MS01: Semidefinite Optimization: Geometry, Algebra and Applications 1
João Gouveia / Elina Robeva / Anthony Man-Cho So / Rainer Sinn
Mon 15:30-17:30MS09: Semidefinite Optimization: Geometry, Algebra and Applications 2
Pablo A. Parrilo / Kai Kellner / Annie Raymond / Greg Blekherman
Tue 10:30-12:30MS18: Group Actions in Algebraic Geometry and Commutative Algebra
Kangjin Han / Luke Oeding / David Swinarski /Jose Rodriguez
Tue 15:30-17:30MS23: Real Algebraic Geometry and Optimization 1
Raman Sanyal / Mohab Safey el Din / Yoshiyuki Sekiguchi / Martina Juhnke-Kubit
Wed 10:30-12:30MS31: Real Algebraic Geometry and Optimization 2
Daniel Plaumann / Bernard Mourrain / Anne Shiu / Bruce Reznick
Thu 10:30-12:30MS42: Combinatorial Methods in Algebraic Geometry 1
Alicia Dickenstein / Atsushi Ito / Diane Maclagan / Benjamin Nill
Thu 15:30-17:30MS49: Computational Approach to GIT and Moduli Theory 1
Dawei Chen / Anand Deopurkar / Patricio Gallardo / Maksym Fedorchuk
Fri 10:30-12:30MS57: Combinatorial Methods in Algebraic Geometry 2
Luke Oeding / Elisa Postinghel / Greg Smith / Bernd Sturmfels
Fri 14:00-16:00MS61: Computational Approach to GIT and Moduli Theory 2
David Swinarski / Hyunbin Loh / Dao Phuong Bac
Date / TimeCAMP 3 (Building 2, 2F)
Mon 10:30-12:30MS08: Combinatorial Phylogenetics 1
Seth Sullivant / Megan Owen / Terrel Hodge / Momoko Hayamizu
Mon 15:30-17:30CP01: Contributed Session I
Nikolai Krivulin / Grey Violet / Tobias Friedl / Jesse Drendel
Tue 10:30-12:30MS22: Pairings in Cryptography I
Soo Kyung Eom / Sorina Ionica / Peter Schwabe
Tue 15:30-17:30MS30: Class Groups of Global Fields
Hwanyup Jung / Jungyun Lee / Yoonjin Lee / Yuichiro Taguchi
Wed 10:30-12:30MS38: Pairings in Cryptography 2
Koray Karabina / Mehdi Tibouchi / Para Lee
Thu 10:30-12:30MS46: Combinatorial Phylogenetics 2
Ruriko Yoshida / Andrew Francis / Jeremy Sumner / Ruth Davidson
Fri 10:30-12:30CP03: Contributed Session III
Yang QI / Liam Solus
Date / TimeNIMS 1 (Building 3, 3F)
Mon 10:30-12:30MS04: Tropical Geometry 1
Anders Jensen / Pascal Benchimol / Simon Hampe / Yaroslav Shitov
Mon 15:30-17:30MS12: Tropical Geometry 2
Jan Draisma / Dustin Cartwright / Ralph Morrison / Diane Maclagan
Tue 10:30-12:30MS21: Maximum Likelihood Degrees and Critical Points 1
Xiaoxian Tang / Jose Rodriguez / Serkan Hosten / Elizabeth Gross
Tue 15:30-17:30MS26: Tropical Geometry 3
Timo de Wolff / Yue Ren / Emmanuel Tsukerman / Yoav Len
Wed 10:30-12:30MS34: On the Geometry and Topology Of (Co)Ame`bas and beyond
Frank Sottile / Diane Maclagan / June Huh / Farid Madani
Thu 10:30-12:30MS43: Symbolic Combinatorics 1
Cyril Banderier / Shaoshi Chen / Shishuo Fu / Tomack Gilmorel
Thu 15:30-17:30MS50: Symbolic Combinatorics 2
Qing-Hu Hou / Arthur Yang / Eric Rowland / Rika Yatchak
Fri 10:30-12:30MS60: Maximum Likelihood Degrees and Critical Points 3
Fatemeh Mohammadi / Caroline Uhler / Piotr Zwiernik / Paolo Lella
Date / TimeNIMS 2 (Building 3, 3F)
Mon 10:30-12:30MS05: Geometry of Matrix Multiplication
Luca Chiantini / Christian Ikenmeyer / Peter Bürgisser / JM Landsberg
Mon 15:30-17:30MS13: Spectral Theory of Tensors and Tensor Rank 1
Nick Vannieuwenhoven / Ke Ye / Joseph Landsberg / Lek-Heng Lim
Tue 10:30-12:30CP02: Contributed Session II
Gerhard Pfister / Tim Hodges / Marco Compagnoni
Tue 15:30-17:30MS27: Spectral Theory of Tensors and Tensor Rank 2
Mitsuhiro Miyazaki / Luke Oeding / Elina Robeva / Youngho Woo
Wed 10:30-12:30MS37: Markov Bases and their Applications in Statistics 2
Abraham Martin del Campo / Satoshi Aoki / Mitsunori Ogawa / David Kahle
Thu 15:30-17:30MS48: Verified Solutions of Algebraic System
Chee Yap / Anton Leykin / Nan Li / Angelos Mantzaflaris
Fri 10:30-12:30MS59: Aspects of Grassmann Manifolds with a view towards Applications
Joachim Rosenthal / Hirotachi Abo / Clayton Shonkwiler / Lek-Heng Lim