| Time | Speaker/ Title/ Abstract/ VOD | Location |
| 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: / | NIMS 2 |
| 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: / | CAMP 1 |
| 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: / | CAMP 2 |
| 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) http://arxiv.org/abs/1501.01120
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 arxiv.org/1408.6841, 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: / | IBS |
| 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: / | NIMS 1 |
| 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: / | CAMP 3 |
| 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: / | CAMP 2 |
| 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: / | CAMP 1 |
| 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 http://sourceforge.net/p/pss5 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: / | NIMS 1 |
| 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: / | NIMS 2 |
| 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: / | IBS |
| 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: / | CAMP 3 |
| 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 |
