Austrin, P (University of Toronto)
Wednesday 02 February 2011, 14:00-15:00

Applications of Discrete Analysis in Inapproximability of NP-hard Problems

During the past decade or so there have been dramatic developments in the interaction between analysis, combinatorial number theory and theoretical computer science: specifically between harmonic analysis and combinatorial number theory and between geometric functional analysis and the theory of algorithms.

Not only have discoveries in one area been used in others but, even more strikingly, there has emerged a commonality of methods and ideas among these apparently diverse areas of mathematics. The use of harmonic analysis in number theory is at least a century old, but in the recent works of Gowers, Green and Tao and others on the existence of arithmetic progressions in subsets of the integers, and in particular the sequence of primes, it has developed into an entire area: additive combinatorics. Classical inequalities of harmonic analysis, such as the isoperimetric inequality, have discrete analogues that are often more subtle than the continuous versions and have wide-ranging applications: for example the discrete isoperimetric inequality of Talagrand, which inspired his work on spin-glass models.

Read more at: http://www.newton.ac.uk/programmes/DAN/

Leader, I (University of Cambridge)
Tuesday 05 July 2011, 14:00-15:00

Positive projections

Klartag, B (Tel-Aviv)
Wednesday 22 June 2011, 15:30-16:30

The logarithmic Laplace transform in convex geometry

Maas, J (Bonn)
Wednesday 22 June 2011, 14:00-15:00

Gradient flows of the entropy for finite Markov chains

Gutin, G (Royal Holloway)
Tuesday 21 June 2011, 14:00-15:00

Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization

Naor, A (New York)
Wednesdayy 15 June 2011, 17:00-17:50

Applications of Discrete Analysis in Inapproximability of NP-hard Problems

Download our free app to listen on your phone