Exposition on the entropy method and the occupancy method
- Series
- Graph Theory Working Seminar
- Time
- Wednesday, November 28, 2018 - 16:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Prasad Tetali – Georgia Tech
In this talk I will describe those linear subspaces of $\mathbf{R}^d$ which can be formed by taking the linear span of lattice points in a half-open parallelepiped. I will draw some connections between this problem and Keith Ball's cube slicing theorem, which states that the volume of any slice of the unit cube $[0,1]^d$ by a codimension-$k$ subspace is at most $2^{k/2}$.
Please Note: This is a part of GT MAP seminar. See gtmap.gatech.edu for more information.
Recently there has been an outburst of parallelization techniques to speed up optimization algorithms, particularly in applications in statistical learning and structured linear programs. Motivated by these developments, we seek for theoretical explanations of provable improvements (or the lack thereof) in performance obtained by parallelizing optimization algorithms. In 1994, Nemirovski proved that for low-dimensional optimization problems there is a very limited improvement that could be obtained by parallelization, and furthermore conjectured that no acceleration should be achievable by these means. In this talk, I will present new results showing that in high-dimensional settings no acceleration can be obtained by parallelization, providing strong evidence towards Nemirovski's conjecture. This is joint work with Jelena Diakonikolas (UC Berkeley).
Please Note: This should be unpublished. Againx3