Time:  Thursdays 12:00pm  1:30pm 
MSB 3106 
Organizers:  Jesus De Loera 
Christopher O'Neill 
Spring Quarter 2018 
Apr 5, 2018  Christopher O'Neill  Computing the delta set of an affine semigroup: a status report 
UC Davis 
Abstract 
Paper 
Paper
An affine semigroup \(S\) is a subset of \(\mathbb Z_{\ge 0}^k\) that is closed under vector addition, and a factorization of \(a \in S\) is an expression of \(a\) as a sum of generators of \(S\). The delta set of \(a\) is a set of positive integers determined by the "missing factorization lengths" of \(a\), and the delta set of \(S\) is the union of the delta sets of its elements. Athough the delta set of any affine semigroup is finite, its definition as an infinite union makes explicit computation difficult. In this talk, we explore algebraic and geometric properties of the delta set, and survey the history of its computation for affine semigroups. The results presented here span the last 20 years, ranging from a first algorithm for a small class of semigroups that is impractical for even basic examples, to recent joint work with GarcíaSánchez and Webb expressing the delta set of any affine semigroup in terms of Gröbner bases, and include results from numerous undergraduate research projects.


Apr 10, 2018  Esha Datta  The efficient factorization of diagram algebras 
UC Davis 
Abstract
The discrete Fourier transform on a group \(G\) converts data associated with group elements to a basis on matrix representations of \(G\). This algorithm was famously made more efficient by the CooleyTukey fast Fourier transform (FFT), which has also been extended to groups. Two essential components of the FFT on groups are the efficient precomputation of matrix representations and the efficient factorization of group elements. Using a known factorization for the symmetric group as a model, we extend the factorization to two grouplike algebraic structures: the TemperleyLieb algebra and the Brauer algebra. The precomputation step is known for these algebras. Our main result is to provide an efficient factorization of a basis of each of these algebras into products of generators. This allows one to extend the FFT to both the TemperleyLieb and Brauer algebras.


Apr 19, 2018  Deborah Oliveros  Meissner polytopes and constructions of bodies of constant width 
UNAM 
Abstract
The Reuleaux triangle is perhaps one of the most famous figures of constant, in dimension 3 however the similar object, the Reuleaux tetrahedron is not longer a body of constant width. In 1911 it appeared for the first time in a catalogue of mathematical models (produced by Martin Schilling), the first nonrotational body of constant width defined by E. Meissner. Such body consists in a series of modifications of the Reuleaux tetrahedron. In this talk, we will discuss some families of ndimensional selfdual polytopes that may yield into examples of bodies of constant width in any dimension.


Apr 26, 2018  Lily Silverstein  Recent progress in random monomial ideals 
UC Davis 
Abstract 
Paper 
Paper
Faithful CACAO attendees have probably heard me talk about "Random Monomial Ideals" (with De Loera, Petrovic, Stasi and Wilburne).
This week I'll talk about a second paper, "Average Behavior of Minimal Free Resolutions of Monomial Ideals", written with Jesus De Loera and Robert Krone here at Davis, and Serkan Hosten of San Francisco State. We answer some conjectures from the first paper, in particular focusing on homological properties.
I'll also take some time to show off a new Macaulay2 software package for working with these random models.


May 3, 2018  No CACAO  
May 10, 2018  Thurston Lectures: No CACAO  
May 17, 2018  Jamie Haddock  Ph.D Exit Seminar: The minimum Euclideannorm point on a 
 MSB 1147   UC Davis  convex polytope: Wolfe's combinatorial algorithm is exponential 
Abstract 
Paper
The complexity of Philip Wolfe's method for the minimum Euclideannorm point problem over a convex polytope has remained unknown since he proposed the method in 1974. The method is important because it is used as a subroutine for one of the most practical algorithms for submodular function minimization. We present the first example that Wolfe's method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in stronglypolynomial time to the minimum norm point problem over a simplex.


May 24, 2018  Shira Zerbib  Colorful coverings of polytopes  the hidden topological truth 
UMich  behind different colorful phenomena  
Abstract
The topological KKMS theorem, a powerful extension of the Brouwer's FixedPoint theorem, was proved by Shapley in 1973 in the context of game theory.
We prove a colorful and polytopal generalization of the KKMS Theorem, and show that our theorem implies some seemingly unrelated results in discrete geometry and combinatorics involving colorful settings. For example, we apply our theorem to provide a new proof of the Colorful Caratheodory Theorem due to Barany. We further apply our theorem to obtain a new upper bound on the piercing numbers in colorful dinterval families, extending results of Tardos, Kaiser and Alon for the noncolored case. Finally, we apply our theorem to questions regarding fair division. Joint with Florian Frick. 

May 31, 2018  Hemant Bhargava  Mixedformat matching auctions in platforms 
UC Davis 
Abstract 
Paper
Platforms create value by matching participants on alternate sides of the marketplace. While many platforms practice onetoone matching (e.g., Uber), others can conduct and monetize onetomany simultaneous matches (e.g., lead marketing platforms). Ideally, the choice between the two modes of matching should be made not ex ante, but rather based on the relative premium that participants perceive for exclusive matches and the nature of heterogeneity in these two sets of valuations. This paper studies the problem of designing an auction format for such platforms, i.e., a set of rules for allocation and pricing of matches. For the sake of practicality, we require deterministic auctions that incentivize truthful bidding, and we formulate the optimal incentivecompatible (IC) auction as a mixed integer mathematical program. Although the optimal IC auction is notoriously hard to solve, its value is that it leads to a heuristic design that is simple to implement, provides good revenue, and has speedy performance, all critical in practice. Specifically, we develop multiple relaxations of the optimal auction to obtain upper bounds on the (unknown) optimal revenue and, conversely, refinements that produce heuristic auctions whose optimal revenue is a lower bound. By demonstrating a tight gap between the two bounds for one such design, RM, we prove that it has excellent revenue performance and places low information and computational burden on the platform and participants.


June 7, 2018  Tommy Hogan  Some variations of Tverberg's number 
 MSB 1147   Dominic Yang  
UC Davis  
June 7, 2018  Robert Hildebrand  Strong models for your cuts 
 MSB 1147   Virginia Tech 
Abstract
Cutting planes are a fundamental tool for solving integer programs. We are always interested in how to obtain the best cuts for your program. We will discuss how your model can be designed better to produce strong cutting planes. In particular, when working with general integer variables, it is common to reformulate these variables into binary variables. As it turns out, the choice of reformulation can greatly affect the strength of the cutting planes that a solver will find. We will compare several options for doing this reformulation.

June 13, 2018  Anne Schilling  Unified theory for finite Markov chains 
 2:30pm   UC Davis 
Abstract 
Paper
We provide a unified framework to compute the stationary distribution of any finite irreducible Markov chain or equivalently of any irreducible random walk on a finite semigroup \(S\). Our methods use geometric finite semigroup theory via the KarnofskyRhodes and the McCammond expansions of finite semigroups with specified generators; this does not involve any linear algebra. The original Tsetlin library is obtained by applying the expansions to \(P(n)\), the set of all subsets of an \(n\) element set. Our setup generalizes previous groundbreaking work involving leftregular bands (or \(\mathscr R\)trivial bands) by Brown and Diaconis, extensions to \(\mathscr R\)trivial semigroups by Ayyer, Steinberg, Thiéry and the second author, and important recent work by Chung and Graham. The KarnofskyRhodes expansion of the right Cayley graph of \(S\) in terms of generators yields again a right Cayley graph. The McCammond expansion provides normal forms for elements in the expanded \(S\). Using our previous results with Silva based on work by Berstel, Perrin, Reutenauer, we construct (infinite) semaphore codes on which we can define Markov chains. These semaphore codes can be lumped using geometric semigroup theory. Using normal forms and associated Kleene expressions, they yield formulas for the stationary distribution of the finite Markov chain of the expanded \(S\) and the original \(S\). Analyzing the normal forms also provides an estimate on the mixing time. This is joint work with John Rhodes.

Winter Quarter 2018 
Jan 18, 2018  Jesus De Loera  Some combinatorial geometry problems I tried to solve, failed... 
UC Davis  but remain super cool  
Jan 25, 2018  Anastasia Chavez  An introduction to positroids and their representations 
UC Davis 
Abstract 
Book 
Book 
Paper 
Paper 
Paper
Positroids are a very wellbehaved family of matroids. Postnikov introduced several combinatorial families that provide equivalent representations of positroids. We will give an introduction to positroids, the various representations, and make the case for they are great to know about.


Feb 1, 2018  Jamie Haddock  Iterative projection methods for noisy and corrupted 
UC Davis  systems of linear equations  
Abstract 
Paper
Iterative linear solvers have gained recent popularity due to their computational efficiency and low memory footprint for largescale linear systems. We will discuss two classical methods, Motzkin's method (MM) and the Randomized Kaczmarz method (RK). MM is an iterative method that projects the current estimation onto the solution hyperplane corresponding to the most violated constraint. Although this leads to an optimal selection strategy for consistent systems, for noisy least squares problems, the strategy presents a tradeoff between convergence rate and solution accuracy. We analyze this method in the presence of noise. RK is a randomized iterative method that projects the current estimation onto the solution hyperplane corresponding to a randomly chosen constraint. We present RK methods which detect and discard corruptions in systems of linear equations, and present probabilistic guarantees that these methods discard all corruptions.


Feb 8, 2018  No CACAO  
Feb 15, 2018  No CACAO  
Feb 22, 2018  Tommy Hogan  \(4m3\) lattice points in a plane 
UC Davis 
Abstract 
Paper
Tverberg's theorem says that sufficiently many points in euclidean space can always be partitioned with intersecting convex hulls. In the 1970's Doignon proposed a variant of Tverberg's theorem where the points are required to have integer coordinates. We will focus on this variant throughout the talk, starting with the proof that any \(4m3\) (for \(m \geq 3\)) lattice points in the plane can be colored \(m\) colors so that there is a lattice point in the intersection of the convex hulls of the \(m\) colors. We will also discuss the analogous problem in higher dimensions.


Mar 1, 2018  Giulia Codenotti  On \(f\)vectors and \(h\)vectors of relative simplicial complexes 
Freie Universität Berlin 
Abstract 
Paper
A relative simplicial complex is the set theoretic difference of two simplicial complexes. Relative complexes have played important roles in recent advances in algebraic and geometric combinatorics, but many basic questions about their general combinatorial structure remain unanswered. I will start from the basic definitions, such as the notion of \(f\)vector and of shelling order, and introduce some of the questions and theorems concerning simplicial complexes, such as the KruskalKatona theorem, that have interesting analogues in the relative setting.


Mar 8, 2018  No CACAO  
Mar 15, 2018  No CACAO  
Mar 22, 2018  Hamilton Santhakumar  Representations of cone lattice points via Hilbert bases 
UC Davis 
Abstract 
Paper 
Paper
Caratheodory's theorem states that every point in a finitely generated \(n\)dimensional cone in \(\mathbb R^d\) can be represented as a nonnegative linear combination of at most \(n\) of it's generators. One can ask if a similar result holds for the integer version, i.e. if we only look at the integer points in the cone and demand representations as nonnegative integer linear combinations of the generators. This question will naturally lead us to special types of generators, called Hilbert bases. In the talk we will start by defining and looking at some basic properties of Hilbert bases. We will then discuss the best known upper bounds on the minimum number of Hilbert basis elements needed to represent integer elements in a cone.


Mar 22, 2018  Winfried Bruns  An algorithm for volumes of polytopes with applications to social choice 
 1:30pm   Universität Osnabrück 
Abstract
We discuss a fast algorithm for the computation of the volume of rational polytopes with few (nonsimplicial) facets. It is based on a recursive approach, originally suggested by Lasserre, that uses descent in the face lattice. For efficient computations in high dimensions it needs a sophisticated implementation that has now been realized in Normaliz.
Probabilities in social choice that are based on the Impartial Anonymous Culture can often be interpreted as volumes of rational polytopes. For 4 candidates these polytopes have dimension 24, and the computation is a challenge. Before the new algorithm had been implemented, Normaliz had to use triangulations and, where possible, symmetrization, which involves integration over rational polytopes. Descent in the face lattice makes all these computations very easy and gives access to many more that hitherto had been inaccessible. 
Spring Quarter 2017 
Apr 04, 2017  Jesus De Loera  Jesus' favorite problems (but only the mathematical ones!) 
UC Davis 
Abstract
Jesus will present from his private collection of favorite open math problems he hopes to see someone young energetic and hardworking solve them before his forthcoming retirement (in about 15 years). The selection will include some old classics, and new hits, carefully chosen and handpicked to make a balanced fragrant and relaxing mix of topics, from Combinatorics, Algebra, Convexity, Algorithms, to many other unexpected mathematical subjects.


Apr 11, 2017  Lily Silverstein  Face vectors of simplicial complexes 
UC Davis 
Abstract
No background is necessary for this talk! We will define two fundamental combinatorial objects: simplicial complexes and their associated \(f\)vectors. Via the KruskalKatona theorem, we will give a complete answer to the question "when is an integer vector the face vector of some simplicial complex?" We will also talk about the relationship between \(f\)vectors and Hilbert functions. Time permitting, some connections to commutative algebra will be discussed, such as the StanleyReisner ring of a simplicial complex.
Since this talk is intended in part to help me prepare for my qualifying exam, please come ready to interrupt me and put me on the spot with challenging questions!! 

Apr 18, 2017  Gabriel Goh  Convex optimization for very few dimensions 
UC Davis 
Abstract 
Paper
Motivated by a problem of achieving fairness in machine learning, I will discuss a novel extension to cutting plane algorithms which allows inexact gradient queries. In this talk I hope to show  though the problems of optimizing a problem in a few dimensions seems trivial  getting it right is both useful and interesting!


Apr 25, 2017  Tommy Hogan  Low dimensional integer Tverberg numbers 
UC Davis 
Abstract 
Paper 1 
Paper 2
Radon's Theorem (1921) states that any set of \(d+2\) points in \(\mathbb R^d\) can be partitioned into two sets whose convex hulls intersect. We call \(d+2\) the Radon number of \(\mathbb R^d\) since it is the smallest number with that property. In 1977, G. Sierksma introduced the notion of an integer Radon number. The integer Radon number \(R(\mathbb Z^d)\) is the smallest number such that any set of \(R(\mathbb Z^d)\) points in \(\mathbb Z^d\) can be partitioned into two sets \(A,B\) with the convex hulls of \(A\) and \(B\) intersecting at an integer lattice point. It is known that \(R(\mathbb Z) = 3\) and \(R(\mathbb Z^2) = 6\), but determining the exact value of \(R(\mathbb Z^3)\) is an open question. In this talk I will give proofs of the current known bounds: \(10 < R(\mathbb Z^3) < 18\).


May 02, 2017  Christopher O'Neill  Random numerical monoids 
UC Davis 
Abstract
I will present the status of an ongoing project on random numerical monoids, joint with Jesus De Loera and Dane Wilburne.


May 09, 2017  Lily Silverstein  The probabilistic method in combinatorics 
UC Davis 
Abstract
Your friend returns from traveling abroad with an unusual deck of playing cards. She tells you, "I know the cards come in different colors, and each card has a positive whole number. I don't know which colors and numbers show upor even how many cards are in the deck! All I know is that if you pick a card at random, you have a 25% chance of picking a red one, a 25% chance of picking a blue one, and the expected value on the card will be 3.5."
Now consider the following claims: (1) The cards come in at least three colors. (2) The deck has at least one card with a 4 or higher on it. (3) The deck has at least one card with a 1, 2, or 3 on it. These statements about the deck are either true or falsethere is nothing probabilistic about them. Yet they can all be proven from your friend's probabilistic information. (Why??) This is a very tiny example of the probabilistic method  a technique that uses probability to prove deterministic statements!! I'll talk about two theorems from graph theory/combinatorics that were famously proved by the probabilistic method. We'll go through the details of those proofs as well as review some basic tools in probability theory, and how they can be applied to combinatorial problems. And there will be chocolate!! 

May 16, 2017   Unscheduled   
May 23, 2017  Michael Savageau  Scaling issues in the enumeration of polytopes 
UC Davis 
Abstract
An informal introduction to a problem involving scaling in the enumeration of polytopes will be presented. An open discussion will follow.


May 30, 2017  Julio Deride  Ph.D Exit Seminar: Stochastic equilibrium problems 
 2:10am   
May 30, 2017  Yuan Zhou  Ph.D Exit Seminar: Infinitedimensional relaxations of mixedinteger 
 3:10am   UC Davis  optimization problems 
May 31, 2017  Shuyang Ling  Ph.D Exit Seminar: Bilinear inverse problems: theory, algorithms, 
 4:10am   UC Davis  and applications in imaging science and signal processing 
Abstract
Bilinear inverse problem pervades many areas of science and technology, including signal processing, imaging processing, and wireless communications. However, they are notoriously illposed since they are often closely related to nonconvex optimization. Solving nonconvex optimization is not an easy task because one may easily get trapped in local minima. We will discuss several important examples of bilinear inverse problems which can be solved efficiently and reliably with both convex and nonconvex approaches. One example brings compressive sensing, selfcalibration, and biconvex optimization together with applications in array selfcalibration. We will propose a novel method called SparseLift to exploit the sparsity in this bilinear model and provide explicit theoretical guarantees; the other one focuses on the wellknown blind deconvolution. We will present a nonconvex algorithm which guarantees the exact recovery with the advantage of robustness and being computationally efficient. Moreover, our framework is extended to solve a more intricate but related problem: the joint blind deconvolution and demixing problem. Several applications in imaging processing and wireless communication will be discussed.


June 06, 2017  Lily Silverstein  Probabilistic and statistical methods in commutative algebra 
UC Davis 
Abstract
Regular CACAO attendees may have seen Professor De Loera or myself speak about our "Random Monomial Ideals" project. This week I will discuss some of our results, but with an emphasis on the commutative algebra context  why do we care about monomial ideals?  and on future research directions.
This is a rehearsal of my qualifying exam talk, so please come prepared to ask questions, challenge every claim, and share any and all suggestions for improvement! 
Winter Quarter 2017 
Jan 11, 2017  Organizational meeting  
Jan 18, 2017  Jesus De Loera  Tverberg's theorem over lattices and other discrete sets 
UC Davis  
Jan 25, 2017  Faculty Interviews: No CACAO  
Feb 01, 2017  Faculty Interviews: No CACAO  
Feb 08, 2017  Gitta Kutyniok  A mathematical framework for feature selection in realworld data 
 3:10pm   Techn. Univ. Berlin 
Abstract
A fundamental challenge in data science is the selection of discriminative features from a relatively small collection of sample pairs. A major difficulty is often that the relevant variables only arise as hidden factors in the actual raw data vectors.
One example are mass spectrometry data of the human proteome, where the desired molecular concentrations of proteins are intrinsically encoded by means of Gaussianshaped peaks. In this talk, we will develop a mathematical framework including in particular nonlinear observations, arbitrary convex signal structures as well as strictly convex loss functions, which allows us to show that successful feature selection is still possible when the applied estimator does not have any knowledge of the underlying data representation and only takes the raw samples as input. Guarantees of such type are especially appealing for practical purposes, since in many applications even standard methods, e.g. the Lasso or logistic regression, yield surprisingly good outcomes. 
Feb 15, 2017  Federico Castillo  A commutative algebra problem regarding matroids 
UC Davis 
Abstract
Neil White conjectured that the toric ideal of any polymatroid is generated by quadrics. What does this even mean? And why do I care? I'll answer this from scratch. I will give an overview of the current status of the problem and propose some ideas to tackle the problem. Hopefully this will inspire people to work (with me and Chris!!) on special cases of it.


Feb 22, 2017  Jamie Haddock  Convergence results for Wolfe's method 
UC Davis 
Abstract 
Paper
Wolfe's method is a combinatorial method for solving the minimum norm problem over polytopes. The minimum norm problem is that of finding the point in a convex body which lies closest to the origin. This problem arises in submodular function optimization and is intimately related to linear programming. I will describe the minimum norm problem for polytopes and describe Wolfe's method. I will discuss the few results known regarding its finiteness and convergence properties. If time permits, I will also present our recent results regarding the connection between this problem and linear programming.


Mar 01, 2017  No CACAO  
Mar 08, 2017  Tommy Hogan  Computing Nash equilibria of games 
UC Davis 
Abstract 
Book
Computation of equilibria in games leads to systems of polynomial equations. For 2 player games these equations are linear, for \(n > 2\) they are multilinear. We derive these equations for some simple games, and look at some of the challenges related to computing Nash equilibria. We then consider a general \(n\)player game where each player has a collection of pure strategies to which they allocate a probability distribution. Although we don't know how to compute equilibria in general, we can get a sharp bound on the number of "totally mixed Nash equilibria" of a game based on it's complexity. Furthermore, this bound has a neat combinatorial description!


Mar 15, 2017  No CACAO 
Fall Quarter 2016 
Sep 27, 2016  Christopher O'Neill  Invariants of nonunique factorization 
UC Davis 
Abstract 
Slides 
Paper
Nonunique factorization in commutative monoids is often studied using factorization invariants, which assign to each monoid element a quantity determined by the factorization structure. In this talk, we introduce several factorization invariants, together with motivating examples. For each invariant, we explore recent results in the setting of numerical monoids (additive submonoids of the natural numbers) demonstrating remarkably similar periodic behavior for sufficiently large monoid elements.


Oct 04, 2016  Dane Wilburne  Statistical network modeling 
IIT 
Abstract 
Slides 
Paper
In this talk, we investigate the ways in which algebraic and geometric thinking can be used to study problems in the statistical theory of networks. We focus on the problems of parameter estimation and goodnessoffit testing for networks, and illustrate the basic ideas using two running examples: the ErdosRenyi and Beta models for random graphs.


Oct 11, 2016  Dan Romik  Differential equations and exact solutions in the moving sofa problem 
UC Davis 
Abstract 
Paper 
Simulation
The moving sofa problem, posed by L. Moser in 1966, asks for the planar shape of maximal area that can move around a rightangled corner in a hallway of unit width, and is conjectured to have as its solution a complicated shape derived by Gerver in 1992. We extend Gerver's techniques by deriving a family of six differential equations arising from the areamaximization property. We then use this result to derive a new shape that we propose as a possible solution to the "ambidextrous moving sofa problem," a variant of the problem previously studied by Conway and others in which the shape is required to be able to negotiate a rightangle turn both to the left and to the right. Unlike Gerver's construction, our new shape can be expressed in closed form, and its boundary is a piecewise algebraic curve. Its area is equal to \(X+\arctan Y\), where \(X\) and \(Y\) are solutions to the cubic equations \(x^2(x+3)=8\) and \(x(4x^2+3)=1\), respectively.


Oct 17, 2016  Daniel Bernstein  \(l^\infty\) optimization in tropical geometry and phylogenetics 
 11:00am   NCSU 
Abstract 
Slides 
Paper
In phylogenetics, one often seeks to reconstruct a tree that represents the evolutionary history among a collection of species. In the distancebased approach to this problem, one views their data as a point in a highdimensional space and seeks to find the nearest element in a certain polyhedral complex. Motivated by this situation, we investigate uniqueness issues that arise in finding \(l^\infty\) nearest points in 1) linear spaces and 2) Bergman fans of matroids. In this talk, I will explain how the oriented matroid underlying a linear space induces a polyhedral decomposition of the ambient space based on the dimension of the set of \(l^\infty\) nearest points. A corollary is that \(l^\infty\) nearest neighbors in a linear space are unique if and only if the linear space's underlying matroid is uniform. I will also discuss some of our results about Bergman fans of matroids. In particular, the set of \(l^\infty\) nearest points in a Bergman fan of a matroid is a tropical polytope and I will show how one can compute its tropical vertices. This is joint work with Colby Long.

Oct 18, 2016  David Rolnick  From machine learning to brains and back again 
MIT 
Abstract 
Slides
Recent work in deep learning, combined with cuttingedge microscope technology, has made it possible to reconstruct networks of neurons in the brain with unprecedented accuracy and scale. I will discuss algorithms involved in mapping the brain and why traditional deep learning may not be enough. I will also show how understanding the "connectome" (the brain's neural network) can lead to new insights in artificial neural networks.


Oct 25, 2016  Jamie Haddock  Wolfe's algorithm for computing the point of minimum norm in a polytope 
UC Davis 
Abstract 
Paper 
Slides
Wolfe's algorithm is a terminating method for finding the point of smallest Euclidean norm in a polytope, the convex hull of a finite set of points. It is known that this problem can be solved in polynomial time, and additionally, the numerical convergence behavior of Wolfe's method has been analyzed. However, the method is combinatorial in nature, with each iteration acting on a subset of the points, and the number of iterations is not known to be polynomial in the size of the input data. We will discuss the performance of this method on a certain class of polytopes and examine some experimental results.


Nov 01, 2016  Christopher O'Neill  What is a free resolution? 
UC Davis 
Abstract 
Book
The goal of this talk is to build intuition on what free resolutions are and what information they encode. We will examine free resolutions in the setting of polynomial rings from a highly combinatorial perspective, focusing specifically on monomial ideals whose free resolutions can be easily constructed by hand. No prior experience with free resolutions will be assumed for this talk.


Nov 08, 2016  Lily Silverstein  Monomial ideals 
UC Davis 
Abstract 
Book
I will explain a beautiful connection between some algebraic properties of monomial ideals and combinatorics on hypergraphs. This connection is the basis for several results in an exciting TOP SECRET project that you can only hear about by attending Tuesday's seminar.


Nov 14, 2016  Mahdi Ghamkhari  A convex relaxation approach to solve the strategic bidding problem 
 11:30am   UC Davis  in electricity markets 
Abstract 
Paper 
Slides
Strategic bidding problems in electricity markets are complex bilevel optimization problems that are hard to solve. The stateoftheart approach to solve such problems is to reformulate them as mixedinteger linear programs (MILPs). However, the computational time of such MILP reformulations grows dramatically, once the network size increases, scheduling horizon increases, or randomness is taken into consideration. We propose effective and customized convex programming tools to solve the strategic bidding problem in nodal electricity markets. Our approach is inspired by the Schmudgen's Positivstellensatz Theorem in semialgebraic geometry; and results in obtaining close to optimal bidding solutions, besides having a huge advantage on reducing computation time. While the computation time of the stateoftheart MILP approach grows exponentially when we increase the scheduling horizon or the number of random scenarios, the computation time of our approach increases rather linearly.


Nov 15, 2016  Jesus De Loera  100 years of Helly's theorem: A jewel of applied geometry 
UC Davis  
Nov 22, 2016  Thanksgiving break: No CACAO  
Nov 28, 2016  Winfried Bruns  Convex hull computation in Normaliz 
 12:10pm   Universität Osnabrück 
Abstract 
Software
Normaliz is a versatile package for computations in discrete convex geometry: it computes lattice points in polyhedra, or, from a different perspective, solves linear diophantine systems of inequalities, equations and congruences.
Recently it has been included in benchmarks of convex hull computation (or vertex enumeration), and has often outperformed dedicated systems, especially on large problems. We will present Normaliz' approach to convex hulls. The main tool is pyramid decomposition whose development was sparked off by the more difficult task of computing triangulations. Pyramid decomposition allows "localization" and helps to break the often forbidding complexity of pure FourierMotzkin elimination. Furthermore it is parallelization friendly. Based on: W. Bruns, B. Ichim and C. Söger, The power of pyramid decomposition in Normaliz, J. Symb. Comp. 74 (2016), 513536. 