Monday, March 27, 2017 - 16:00 , Location: Skiles 006 , Ke Ye , University of Chicago , Organizer: Greg Blekherman
Abstract: Tensors are direct generalizations of matrices. They appear in almost every branch of mathematics and engineering. Three of the most important problems about tensors are: 1) compute the rank of a tensor 2) decompose a tensor into a sum of rank one tensors 3) Comon’s conjecture for symmetric tensors. In this talk, I will try to convince the audience that algebra can be used to study tensors. Examples for this purpose include structured matrix decomposition problem, bilinear complexity problem, tensor networks states, Hankel tensors and tensor eigenvalue problems. In these examples, I will explain how algebraic tools are used to answer the three problems mentioned above.
Series: Combinatorics Seminar
I will talk about the problem of computing the number of integer partitions into parts lying in some integer sequence. We prove that for certain classes of infinite sequences the number of associated partitions of an input N can be computed in time polynomial in its bit size, log N. Special cases include binary partitions (i.e. partitions into powers of two) that have a key connection with Cayley compositions and polytopes. Some questions related to algebraic differential equations for partition sequences will also be discussed. (This is joint work with Igor Pak.)
Monday, March 27, 2017 - 14:00 , Location: Skiles 006 , Roger Casals , MIT , Organizer: John Etnyre
In this talk we associate a combinatorial dg-algebra to a cubic planar graph. This algebra is defined by counting binary sequences, which we introduce, and we shall provide explicit computations. From there, we study the Legendrian surfaces behind these combinatorial constructions, including Legendrian surgeries and the count of Morse flow trees, and discuss the proof of the correspondence between augmentations and constructible sheaves for this class of Legendrians.
Series: IMPACT Distinguished Lecture
In the latent voter model, which models the spread of a technology through a social network, individuals who have just changed their choice have a latent period, which is exponential with rate λ during which they will not buy a new device. We study site and edge versions of this model on random graphs generated by a configuration model in which the degrees d(x) have 3 ≤ d(x) ≤ M. We show that if the number of vertices n → ∞ and log n << λn << n then the latent voter model has a quasi-stationary state in which each opinion has probability ≈ 1/2 and persists in this state for a time that is ≥ nm for any m <∞. Thus, even a very small latent period drastically changes the behavior of the voter model.
Friday, March 17, 2017 - 14:00 , Location: Skiles 006 , John Etnyre , Georgia Tech , Organizer: John Etnyre
This will be a 1.5 hour (maybe slightly longer) seminar.
Following up on the previous series of talks we will show how to construct Lagrangian Floer homology and discuss it properties.
Series: ACO Student Seminar
Optimization problems arising in decentralized multi-agent systems have gained significant attention in the context of cyber-physical, communication, power, and robotic networks combined with privacy preservation, distributed data mining and processing issues. The distributed nature of the problems is inherent due to partial knowledge of the problem data (i.e., a portion of the cost function or a subset of the constraints is known to different entities in the system), which necessitates costly communications among neighboring agents. In this talk, we present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems which can significantly reduce the number of inter-node communications. Our major contribution is the development of decentralized communication sliding methods, which can skip inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions.This is a joint work with Guanghui (George) Lan and Yi Zhou.
Friday, March 17, 2017 - 11:05 , Location: Skiles 006 , Erich Kaltofen , North Carolina State University , Organizer: Anton Leykin
Error-correcting decoding is generalized to multivariate sparse polynomial and rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (``outliers''). Our multivariate polynomial and rational function interpolation algorithm combines Zippel's symbolic sparse polynomial interpolation technique [Ph.D. Thesis MIT 1979] with the numeric algorithm by Kaltofen, Yang, and Zhi [Proc. SNC 2007], and removes outliers (``cleans up data'') by techniques from the Welch/Berlekamp decoder for Reed-Solomon codes. Our algorithms can build a sparse function model from a number of evaluations that is linear in the sparsity of the model, assuming that there are a constant number of ouliers and that the function probes can be randomly chosen.
Series: School of Mathematics Colloquium
We present algorithms for performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Our interpolation algorithms use as a substep an algorithm that originally is by R. Prony from the French Revolution (Year III, 1795) for interpolating exponential sums and which is rediscovered to decode digital error correcting BCH codes over finite fields (1960). Since Prony's algorithm is quite simple, we will give a complete description, as an alternative for Lagrange/Newton interpolation for sparse polynomials. When very few errors in the evaluations are permitted, multiple sparse interpolants are possible over finite fields or the complex numbers, but not over the real numbers. The problem is then a simple example of list-decoding in the sense of Guruswami-Sudan. Finally, we present a connection to the Erdoes-Turan Conjecture (Szemeredi's Theorem). This is joint work with Clement Pernet, Univ. Grenoble.