Further talks

Modal title

Modal content

Date / Time

Speaker

Title

Location

11 September 2019
16:00-17:00

Christoph Hunkenschröder
École polytechnique Fédérale de Lausanne, Lausanne

Details

Title	A compact representation of the Voronoi Cell of a Lattice
Speaker, Affiliation	Christoph Hunkenschröder, École polytechnique Fédérale de Lausanne, Lausanne
Date, Time	11 September 2019, 16:00-17:00
Location	HG G 19.1
Abstract	In a seminal work, Micciancio & Voulgaris (2010) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using coefficients that are bounded by c in absolute value. Given such a basis, we get a polynomial space algorithm for CVP whose running time naturally depends on c. Thus, our main focus is the behavior of the smallest possible value of c, with the following results: There always exist c-compact bases, where c is bounded by n^2 for an n-dimensional lattice; there are lattices not admitting a c-compact basis with c growing sublinearly with the dimension; and every lattice with a zonotopal Voronoi cell has a 1-compact basis. I will introduce all terms used in this abstract during the talk. This is joint work with Gina Reuland and Matthias Schymura.

A compact representation of the Voronoi Cell of a Latticeread_more

15 November 2019
13:00-14:30

Tim Kunisky
Courant Institute of Mathematical Sciences at New York University, USA

Details

Title	Hardness of certification for random quadratic programming problems
Speaker, Affiliation	Tim Kunisky, Courant Institute of Mathematical Sciences at New York University, USA
Date, Time	15 November 2019, 13:00-14:30
Location	HG G 19.2
Abstract	I will describe recent results on the computational cost of certifying bounds on Gaussian random instances of a class of quadratic optimization problems. Unlike merely finding good feasible points, certification demands an easy-to-verify proof (like that furnished by the sum-of-squares hierarchy) of a bound on the objective function. I will present several forms of evidence that certifying bounds can be significantly harder than searching for good feasible points. First, I will show how to adapt the heuristic “low-degree method” for assessing the computational hardness of hypothesis testing problems to also suggest hardness of certification. Second, time permitting, I will outline a more concrete result confirming that the degree 4 sum-of-squares algorithm fails to certify tight bounds for a specific well-studied problem, that of optimizing the Hamiltonian of the Sherrington-Kirkpatrick model from statistical physics. (Based on joint work with Afonso Bandeira and Alex Wein.)

Hardness of certification for random quadratic programming problemsread_more

28 November 2019
15:00-16:00

Chun Lam Chan
École polytechnique Fédérale de Lausanne, Lausanne

Details

Title	Adaptive interpolation method for mutual information in inference on dense and sparse graphs
Speaker, Affiliation	Chun Lam Chan, École polytechnique Fédérale de Lausanne, Lausanne
Date, Time	28 November 2019, 15:00-16:00
Location	HG G 19.1
Abstract	Mutual information is often the central quantity when we study the fundamental limit in a Bayesian inference problem. The asymptotic mutual information is predicted to admit a single-letter variational expression derived from the replica or cavity method from statistical physics. Recently, adaptive interpolation method has been developed as a simple and versatile scheme to prove this prediction for various Bayesian inference problems defined on dense factor graphs. In this talk, I will present some new development of the adaptive interpolation; in particular, how to adopt the methods for models in community detection. I will discuss stochastic block models in the dense graph regime and censored block models in the sparse graph regime.

Adaptive interpolation method for mutual information in inference on dense and sparse graphsread_more

Notes: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archive: undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined