[iasmath-semru] [math-ias] Theoretical Computer Science/Discrete Math Seminars-Week of April 16, 2018

[Kristina Phillips]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540
 
Theoretical Computer Science/Discrete Math Seminars
Week of April 16, 2018
 
 
--------------
To view mathematics in titles and abstracts, please click on the talk's
link.
--------------
 
Monday, April 16
 
Computer Science/Discrete Mathematics Seminar I
Topic:                    Sums of Squares Over k-Subset Hypercubes
Speaker:                 Annie Raymond, University of Massachusetts, Amherst
Time/Room:          11:00am - 12:15pm/Simonyi Hall 101
Abstract Link:        http://www.math.ias.edu/seminars/abstract?event=128840
 
 
 
Tuesday, April 17
 
Computer Science/Discrete Mathematics Seminar II
Topic:                    A simple proof of a reverse Minkowski inequality
Speaker:                 Noah Stephens-Davidowitz, Visitor, School of
Mathematics
Time/Room:          10:30am - 12:30pm/Simonyi Hall 101
Abstract Link:        http://www.math.ias.edu/seminars/abstract?event=136796
 

 

 

1 Sums of Squares Over k-Subset Hypercubes 
   Annie Raymond 

Polynomial optimization over hypercubes has important applications in
combinatorial optimization. We develop a symmetry-reduction method that
finds sums of squares certificates for non-negative symmetric polynomials
over k-subset hypercubes that improves on a technique due to Gatermann and
Parrilo. For every symmetric polynomial that has a sos expression of a fixed
degree, our method finds a succinct sos expression whose size depends only
on the degree and not on the number of variables. Our results relate
naturally to Razborov's flag algebra calculus for solving problems in
extremal combinatorics. This leads to new results involving flags and their
power in finding sos certificates. This is joint work with James Saunderson,
Mohit Singh and Rekha Thomas.

http://www.math.ias.edu/seminars/abstract?event=128840

2 A simple proof of a reverse Minkowski inequality 
   Noah Stephens-Davidowitz 

We consider the following question: how many points with bounded norm can a
"non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean
an n-dimensional lattice with no surprisingly dense lower-dimensional
sublattices.
 
Dadush and Regev conjectured an upper bound on this quantity (which they
called a "reverse Minkowski-type inequality") and showed a number of
applications---from cryptography to Brownian motion on flat tori. In joint
work with Regev in 2016, we proved this conjecture via a rather tedious
proof using two heavy hammers from convex geometry.
 
Recently, Eldan showed how to remove the tedium from the proof, and even
more recently, Dadush showed how to remove the heavy hammers (to prove a
slightly different result). The resulting (still unpublished) streamlined
proof is quite nice, and we present it more-or-less in full.

http://www.math.ias.edu/seminars/abstract?event=136796




---------------------------------------

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu <http://www.math.ias.edu/> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/iasmathsemrutgers/attachments/20180410/10755bc7/attachment.html>