Discrete analysis

Programme theme

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.

Through the study of the influence of variables on Boolean functions, discrete harmonic analysis has started to play a crucial role in theoretical computer science. And at the same time it has become clear that many problems in theoretical computer science and combinatorial optimisation are actually geometric problems in "disguise". In other cases, the problems are so complex that the best available approximation algorithms were devised by embedding the underlying combinatorial structure into a familiar geometry (such as Euclidean space) so that it becomes "geometrically obvious" what to do.

The purpose of this programme is to bring together researchers in these diverse areas of mathematics, to encourage more interaction between these fields, and to provide an opportunity for UK mathematicians to engage with an important part of the mathematical computer science community.

Click here to download the programme's final scientific report

Preprints

Title	Year	Programme
An incidence theorem in higher dimensions Authors: Terence Tao, Jozsef Solymosi Download PDF	2010	DAN	21 October 2016
Sums of dilates in groups of prime order Authors: Alain Plagne Download PDF	2010	DAN	21 October 2016
A curved Brunn-Minkowski inequality on the discrete hypercube or: What is the Ricci curvature of the discrete hypercube? Authors: C Villani, Yann Ollivier Download PDF	2010	DAN	21 October 2016
Invariances in variance estimates Authors: Dario Cordero-Erausquin, Franck Barthe Download PDF	2010	DAN	21 October 2016
Hypercontractive measures, Talagrand's inequality, and influences Authors: Dario Cordero-Erausquin, Michel Ledoux Download PDF	2010	DAN	21 October 2016
Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width Authors: A Yeo, Gregory Gutin Download PDF	2010	DAN	21 October 2016
Combinatorial optimization over two random point sets Authors: Charles Bordenave, Franck Barthe Download PDF	2010	DAN	21 October 2016
A remark on the slicing problem Authors: Grigorios Paouris, Beatrice-Helen Vritsiou, A Giannopoulos Download PDF	2010	DAN	21 October 2016
Approximate Gaussian isoperimetry for $\it k$ sets Authors: Gideon Schechtman Download PDF	2010	DAN	21 October 2016
Stabilizing isomorphisms from l_p (l_2) into L_p [0, 1] Authors: R Levy, Gideon Schechtman Download PDF	2010	DAN	21 October 2016
Transversal multilinear Radon-like transforms: local and global estimates Authors: Neal Bez, S Gutierrez, Jonathan Bennett Download PDF	2010	DAN	21 October 2016
Global nonlinear Brascamp-Lieb inequalities Authors: Neal Bez, S Gutierrez, Jonathan Bennett Download PDF	2010	DAN	21 October 2016
On the logarithimic calculus and Sidorenko's conjecture Authors: Balazs Szegedy, JL Xiang Li Download PDF	2010	DAN	21 October 2016
On reverse hypercontractivity Authors: Krzysztof Oleszkiewicz, Arnab Sen, Elchanan Mossel Download PDF	2010	DAN	21 October 2016
Lower bounds for the average and smoothed number of Pareto optima Authors: N Goyal, Luis Rademacher Download PDF	2010	DAN	21 October 2016
The diminishing segment process Authors: P Kevei, V Vigh, Gergely Ambrus Download PDF	2010	DAN	21 October 2016
Maximal equilateral sets Authors: Konrad Swanepoel, R Villa Download PDF	2010	DAN	21 October 2016
Sets of unit vectors with small subset sums Authors: Konrad Swanepoel Download PDF	2010	DAN	21 October 2016
Two steps transportation problem Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016
The effective LVMM method in Lotka-Volterra systems Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016
An observation related to the method of Lemke-Hobson Authors: Ezio Marchi, M Maton Download PDF	2010	DAN	21 October 2016
A simple or deep mathematical problem? Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016
Average equilibrium points Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016
Temperature effect on collagen-like structure Authors: L Millan, Ezio Marchi Download PDF	2010	DAN	21 October 2016
A difference equation involving Fibonacci numbers Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016
Further remarks for difference equations Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016
Matricial Potentiation Authors: Ezio Marchi, M Matens Download PDF	2010	DAN	21 October 2016
On a relevant aspect in difference equations Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016
Representation of rational numbers through a Lissajou's geometric figure Authors: Ezio Marchi Download PDF	2010	DAN	21 October 2016

Workshops

DANW01

Seminars

Wednesday 19th January 2011
14:00 to 15:00	Guillaume Aubrun Université Claude Bernard Lyon 1 Maximal inequality for high-dimensional cubes	Room 1

Friday 21st January 2011
14:00 to 15:00	Terence Tao University of California, Los Angeles TBA	Room 1

Wednesday 26th January 2011
14:00 to 15:00	Jordan's theorem on finite linear groups and its approximate Analogues	Room 1
15:15 to 16:15	Jozsef Solymosi University of British Columbia On geometric incidences	Room 1

Friday 28th January 2011
14:00 to 15:00	Terence Tao University of California, Los Angeles On Gromov's theorem on groups of polynominal growth and related topics	Room 1

Monday 31st January 2011
14:00 to 15:00	On a conjecture of Snevily	Room 1

Tuesday 1st February 2011
14:00 to 15:00	On Vinogradov's mean value theorem	Room 1

Wednesday 2nd February 2011
14:00 to 15:00	Per Austrin University of Toronto Applications of Discrete Analysis in Inapproximability of NP-hard Problems	Room 1

Friday 4th February 2011
11:00 to 12:00	Kenneth Falconer University of St Andrews Self-affine sets and measures	Room 1

Wednesday 9th February 2011
14:00 to 15:00	Plunnecke-type product set estimates in groups	Room 1
15:15 to 16:15	Sergei Konyagin Steklov Mathematical Institute, Russian Academy of Sciences Multiplicative translates of subgroups in residue classes	Room 1

Friday 11th February 2011
14:00 to 15:00	Johan Håstad KTH - Royal Institute of Technology Linear threshold predicates and approximation resistance	Room 1

Saturday 12th February 2011
14:00 to 15:00	Michael Bateman University of California, Los Angeles 3 terms arithmetic progressions in finite fields (IV)	Room 1

Wednesday 16th February 2011
14:00 to 15:00	Artem Zvavitch Kent State University Some remarks on Mahler's conjecture for convex bodies	Room 1

Friday 18th February 2011
14:00 to 15:00	Krzysztof Oleszkiewicz Uniwersytet Warszawski The Khinchine inequalities with optimal constants via ultra log-concavity	Room 1

Monday 21st February 2011
14:00 to 15:00	Olivier Guedon Université de Marne-la-Vallée Concentration inequalities for log-concave measures	Room 1

Wednesday 23rd February 2011
14:00 to 15:00	Mark Rudelson University of Missouri Row products of random matrices	Room 1
15:15 to 16:15	Alain Plagne Centre de Physique Théorique de l’Ecole Polytechnique (CPHT) From coding theory to Davenport constant	Room 1

Wednesday 2nd March 2011
14:00 to 15:00	Vertices of high degree in the preferential attachment tree	Room 1
15:15 to 16:15	Gergely Ambrus Alfréd Rényi Institute of Mathematics,Hungarian Academy of Sciences Polarisation problems	Room 1

Wednesday 9th March 2011
14:00 to 15:00	Harald Andres Helfgott University of Bristol/Ecole Normale Superieure Finding primes deterministically	Room 1
15:15 to 16:15	Arnab Sen University of Cambridge A new definition of influences of Boolean functions	Room 1

Wednesday 16th March 2011
14:00 to 15:00	Charles Bordenave Université de Toulouse Spectrum of large non-hermitian random matrices	Room 1
15:15 to 16:15	Gilles Lancien Université de Franche-Comté Coarse Lipschitz embeddings and asymptotic structure of Banach Spaces	Room 1

Tuesday 5th April 2011
14:00 to 15:00	Avi Wigderson Institute for Advanced Study, Princeton Arithmetic complexity and the sum of squares problem (I)	Room 1
15:15 to 16:15	David Ellis University of Cambridge Triangle-intersecting families of graphs	Room 1

Thursday 7th April 2011
14:00 to 15:00	Stefan Ingi Valdimarsson University of Iceland Multilinear Kakeya type inequalities and factorization	Room 1
15:15 to 16:15	Avi Wigderson Institute for Advanced Study, Princeton Arithmetic complexity and the sum of squares problem (II)	Room 1

Tuesday 12th April 2011
13:45 to 14:45	Avi Wigderson Institute for Advanced Study, Princeton Explicit Euclidean Sections, Codes over the Reals and Expanders	Room 1

Wednesday 13th April 2011
13:45 to 14:45	Alain Pajor Université de Marne-la-Vallée On the Log-Concave Ensemble of random matrices	Room 1

Thursday 14th April 2011
13:45 to 14:45	Endre Szemeredi Rutgers, The State University of New Jersey Long Arithmetic Progressions in Sumsets	Room 1

Thursday 21st April 2011
14:00 to 15:00	Mark Jerrum Queen Mary University of London The ferromagnetic Potts model: phase transition, gadgets and computational complexity	Room 2

Wednesday 27th April 2011
14:00 to 15:00	Misha Rudnev University of Bristol On various sum-product inequalities	Room 1
15:15 to 16:15	Luis Alexis Rademacher Ohio State University Randomized algorithms for the approximation of matrices	Room 1

Tuesday 3rd May 2011
14:00 to 15:00	Michael Bateman University of California, Los Angeles 3-terms arithmetic progressions in finite fields (I)	Room 1

Wednesday 4th May 2011
13:45 to 14:45	Shachar Lovett Institute for Advanced Study, Princeton Correlation testing for affine invariant properties on $F_p^n$	Room 1

Friday 6th May 2011
14:00 to 15:00	Nets Hawk Katz Indiana University 3 terns arithmetic progressions in finite fields (II)	Admin Office [UNAVAILABLE]

Monday 9th May 2011
14:00 to 15:00	Nets Hawk Katz Indiana University 3-terms arithmetic progressions in finite fields (III)	Room 1

Tuesday 10th May 2011
14:00 to 15:00	Sergey Bobkov University of Minnesota Rates of convergence in the entropic central limit theorem	Room 1

Thursday 12th May 2011
14:00 to 15:00	Michael Bateman University of California, Los Angeles 3-terms arithmetic progressions in finite fields (IV)	Room 1

Wednesday 18th May 2011
14:00 to 15:00	Yann Ollivier Université Paris Saclay Discrete Ricci curvature with applications	Room 1

Thursday 19th May 2011
14:00 to 15:00	Yann Ollivier Université Paris Saclay A curved Brunn-Minkowski inequality in the discrete cube	Room 2

Tuesday 24th May 2011
14:00 to 15:00	Konstantin Makarychev IBM Research How to Play Unique Games Against a Semi-Random Adversary	Room 1

Wednesday 25th May 2011
14:00 to 15:00	Konrad Swanepoel London School of Economics Favourite distances in high dimensions	Room 1
15:15 to 16:15	Konstantin Makarychev IBM Research Vertex Sparsifiers and Lipschitz Extendability	Room 1

Tuesday 31st May 2011
14:00 to 15:00	Alexander Volberg Michigan State University Singular integrals in bad neighborhoods I: Singular integrals for Geometric Measure Theory	Room 1

Wednesday 1st June 2011
14:00 to 15:00	Shin-ichi Ohta Kyoto University Ricci curvature of Finsler manifolds, towards applications in the geometry of Banach spaces	Room 1
15:15 to 16:15	Mark Braverman University of Toronto Computability and Complexity of Julia Sets	Room 1

Monday 6th June 2011
14:00 to 15:00	Alexander Volberg Michigan State University Singular integrals in bad neighborhoods II: Stochastic Optimal Control and sharp estimates of Singular Integrals	Room 1

Tuesday 7th June 2011
14:00 to 15:00	Emanuel Milman Technion - Israel Institute of Technology Isoperimetric and concentration inequalities - equivalence and applications	Room 1

Friday 10th June 2011
14:00 to 15:00	Stochastic completeness for random walks and jump processes	Room 1

Tuesday 14th June 2011
14:00 to 15:00	Hamed Hatami McGill University Is asymptotic extremal graph theory of dense graphs trivial?	Room 1

Wednesday 15th June 2011
15:30 to 16:30	Mokshay Madiman Stanford University Towards an entropy-based sumset calculus for additive combinatorics and convex geometry	Room 2
17:00 to 17:50	Assaf Naor New York University Quantitative geometry and efficient classification procedures	Room 1

Tuesday 21st June 2011
14:00 to 15:00	Gregory Gutin Royal Holloway, University of London Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization	Room 2

Wednesday 22nd June 2011
14:00 to 15:00	Jan Maas Rheinische Friedrich-Wilhelms-Universität Bonn Gradient flows of the entropy for finite Markov chains	Room 2
15:30 to 16:30	Bo'az Klartag Tel Aviv University The logarithmic Laplace transform in convex geometry	Room 2

Tuesday 5th July 2011
14:00 to 15:00	Imre Leader University of Cambridge Positive projections	Room 1

Organisers

Keith Ball University College London
Franck Barthe Université de Toulouse
Ben Green University of Cambridge
Assaf Naor New York University

Speakers

Gergely Ambrus Alfréd Rényi Institute of Mathematics,Hungarian Academy of Sciences
Guillaume Aubrun Université Claude Bernard Lyon 1
Per Austrin University of Toronto
Michael Bateman University of California, Los Angeles
Sergey Bobkov University of Minnesota
Charles Bordenave Université de Toulouse
Mark Braverman University of Toronto
David Ellis University of Cambridge
Kenneth Falconer University of St Andrews
Olivier Guedon Université de Marne-la-Vallée
Gregory Gutin Royal Holloway, University of London
Hamed Hatami McGill University
Harald Andres Helfgott University of Bristol/Ecole Normale Superieure
Johan Håstad KTH - Royal Institute of Technology
Mark Jerrum Queen Mary University of London
Nets Hawk Katz Indiana University
Bo'az Klartag Tel Aviv University
Sergei Konyagin Steklov Mathematical Institute, Russian Academy of Sciences
Gilles Lancien Université de Franche-Comté
Imre Leader University of Cambridge
Shachar Lovett Institute for Advanced Study, Princeton
Jan Maas Rheinische Friedrich-Wilhelms-Universität Bonn
Mokshay Madiman Stanford University
Konstantin Makarychev IBM Research
Emanuel Milman Technion - Israel Institute of Technology
Assaf Naor New York University
Shin-ichi Ohta Kyoto University
Krzysztof Oleszkiewicz Uniwersytet Warszawski
Yann Ollivier Université Paris Saclay
Alain Pajor Université de Marne-la-Vallée
Alain Plagne Centre de Physique Théorique de l’Ecole Polytechnique (CPHT)
Luis Alexis Rademacher Ohio State University
Mark Rudelson University of Missouri
Misha Rudnev University of Bristol
Arnab Sen University of Cambridge
Jozsef Solymosi University of British Columbia
Konrad Swanepoel London School of Economics
Endre Szemeredi Rutgers, The State University of New Jersey
Terence Tao University of California, Los Angeles
Stefan Ingi Valdimarsson University of Iceland
Alexander Volberg Michigan State University
Avi Wigderson Institute for Advanced Study, Princeton
Artem Zvavitch Kent State University

Show All

Programme theme

Preprints

An incidence theorem in higher dimensions

Sums of dilates in groups of prime order

A curved Brunn-Minkowski inequality on the discrete hypercube or: What is the Ricci curvature of the discrete hypercube?

Invariances in variance estimates

Hypercontractive measures, Talagrand's inequality, and influences

Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

Combinatorial optimization over two random point sets

A remark on the slicing problem

Approximate Gaussian isoperimetry for $\it k$ sets

Stabilizing isomorphisms from l_p (l_2) into L_p [0, 1]

Transversal multilinear Radon-like transforms: local and global estimates

Global nonlinear Brascamp-Lieb inequalities

On the logarithimic calculus and Sidorenko's conjecture

On reverse hypercontractivity

Lower bounds for the average and smoothed number of Pareto optima

The diminishing segment process

Maximal equilateral sets

Sets of unit vectors with small subset sums

Two steps transportation problem

The effective LVMM method in Lotka-Volterra systems

An observation related to the method of Lemke-Hobson

A simple or deep mathematical problem?

Average equilibrium points

Temperature effect on collagen-like structure

A difference equation involving Fibonacci numbers

Further remarks for difference equations

Matricial Potentiation

On a relevant aspect in difference equations

Representation of rational numbers through a Lissajou's geometric figure

Workshops

Embedding workshop

Discrete harmonic analysis

Groups and additive combinatorics

Closing conference CANCELLED

Seminars

Organisers

Speakers

Supported By

Register for updates