Transcript Document

Classical mathematics
and new challenges
Theorems and Algorithms
László Lovász
Microsoft Research
One Microsoft Way, Redmond, WA 98052
[email protected]
Algorithmic vs. structural mathematics
ancient and classical algorithms
Geometric constructions
Euclidean algorithm
Newton’s method
Gaussian elimination
An example: diophantine approximation
and continued fractions
Given   , find rational approximation p / q
such that | p / q   |  / q and q  1/ .
m


n
| m  n  p || q  p | 
q  1/ 
  a0   
  a0 ?
 1 
1
 a1  

  a0
   a0 
1
  a0 
a1
continued fraction expansion
A mini-history of algorithms
30’s: Mathematical notion of algorithms
recursive functions, Λ-calculus, Turing-machines
Church, Turing, Post
algorithmic and logical undecidability
Church, Gödel
50’s, 60’s: Computers
the significance of running time
simple and complex problems
sorting
searching
arithmetic
…
Travelling Salesman
matching
network flows
factoring
…
late 60’s-80’s: Complexity theory
Time, space, information complexity
Nondeterminism, good characteriztion,
completeness
Polynomial hierarchy
Classification of many real-life problems
into P vs. NP-complete
Randomization, parallelism
P=NP?
90’s: Increasing sophistication
upper and lower bounds on complexity
algorithms
negative results
factoring
volume computation
semidefinite optimization
topology
algebraic geometry
coding theory
Higlights of the 90’s:
Approximation algorithms
positive and negative results
Probabilistic algorithms
Markov chains, high concentration, nibble methods,
phase transitions
Pseudorandom number generators
from art to science: theory and constructions
Approximation algorithms:
The Max Cut Problem
maximize
NP-hard
…Approximations?
Easy with 50% error
Erdős ~’65
???
NP-hard with 6% error
Arora-Lund-MotwaniSudan-Szegedy ’92
Hastad
(Interactive proof systems, PCP)
Polynomial with 12% error
Goemans-Williamson ’93
(semidefinite optimization)
Algorithms and probability
Randomized algorithms (making coin flips):
important applications (primality testing,
integration, optimization,
volume computation, simulation)
difficult to analyze
Algorithms with stochastic input:
even more important applications
even more difficult to analyze
Difficulty: after a few iterations, complicated functions
of the original random variables arise.
New methods in probability:
Strong concentration (Talagrand)
Laws of Large Numbers: sums of independent
random variables is strongly concentrated
General strong concentration: very general
“smooth” functions of independent
random variables are strongly concentrated
Nibble, martingales, rapidly mixing Markov chains,…
Example
O(q)?
3
a
,
a
,
a
,.
..

G
F
(
q
)
Want: Few vectors 1 2 3
such that:
- any 3 linearly independent
- every vector is a linear combination of 2
(was open for 30 years)
Every finite projective plane of order q
has a complete arc of size q polylog(q).
Kim-Vu
First idea: use algebraic construction (conics,…)
gives only about q
Second idea: choose a1 , a2 , a3 ,...
at random
?????
Solution:
Rödl nibble + strong concentration results
Driving forces for the next decade
New areas of applications
The study of very large structures
More tools from classical areas in mathematics
New areas of application:
interaction between discrete and continuous
Biology: genetic code
population dynamics
protein folding
Physics: elementary particles, quarks, etc.
(Feynman graphs)
statistical mechanics
(graph theory, discrete probability)
Economics: indivisibilities
(integer programming, game theory)
Computing: algorithms, complexity, databases, networks,
VLSI, ...
Very large structures
-internet
-VLSI
-databases
-genetic code
-brain
-animal
-ecosystem
-economy
-society
How to model them?
non-constant but stable
partly random
Very large structures: how to model them?
Graph minors
Robertson, Seymour, Thomas
If a graph does not contain a given minor,
then it is
essentially
up to a bounded number
of additional nodes
a 1-dimensional structure
of essentially
2-dimensional pieces.
embedable in a fixed surface
tree-decomposition
except for “fringes”
of bounded depth
Very large structures: how to model them?
Regularity Lemma
Szeméredi 74
The nodes of  graph can be partitioned
into a bounded number
of essentially equal parts
given >0 and k>1, # of parts
is between k and f(k, )
so that
difference at most 1
almost all bipartite graphs between 2 parts
are essentially random
(with different densities).
with k2 exceptions
for subsets X,Y of the two parts,
# of edges between X and Y
is p|X||Y|  n2
Very large structures
-internet
-VLSI
-databases
-genetic code
How to model them?
How to handle them
algorithmically?
-brain
heuristics/approximation
algorithms
-animal
linear time algorithms
-ecosystem
sublinear time algorithms
(sampling)
-economy
-society
A complexity theory of
linear time?
More and more tools from classical math
Example: Volume computation
Given: K 
n
, convex
Want: volume of K
by a membership oracle;
B(0,1)  K  B(0, n2 )
with relative error ε
in n
Not possible in polynomial time, even if ε=ncn.
Elekes, Bárány, Füredi
Possible in randomized polynomial time,
for arbitrarily small ε.
Dyer, Frieze, Kannan
Complexity:
For self-reducible problems,
counting  sampling
(Jerrum-Valiant-Vazirani)
Enough to sample
from convex bodies
vol ( K ) | K  S |

vol ( B)
|S|
*
*
*
*
* *
**
*
must be exponential
in n
Complexity:
For self-reducible problems,
counting  sampling
(Jerrum-Valiant-Vazirani)
K0  B
Enough to sample
from convex bodies
vol( K 0 )
vol( K1 )
by sampling
vol( K1 )
vol( K 2 )
by sampling
…
K1  B  21/ n K
K2  B  22/ n K
Complexity:
For self-reducible problems,
counting  sampling
(Jerrum-Valiant-Vazirani)
Enough to sample
from convex bodies
Algorithmic results:
Use rapidly mixing
Markov chains
(Broder; Jerrum-Sinclair)
Enough to estimate
the mixing rate
of random walk
on lattice in K
Complexity:
For self-reducible problems,
counting  sampling
(Jerrum-Valiant-Vazirani)
Enough to sample
from convex bodies
Algorithmic results:
Use rapidly mixing
Markov chains
(Broder; Jerrum-Sinclair)
Enough to estimate
the mixing rate
of random walk
on lattice in K
Probability:
use eigenvalue gap
Graph theory (expanders):
use conductance to
estimate eigenvalue gap
Alon, Jerrum-Sinclair
K”
K’
F
voln 1 ( F ) vol( K )
vol( K ') vol( K ")
Complexity:
For self-reducible problems,
counting  sampling
(Jerrum-Valiant-Vazirani)
Enough to sample
from convex bodies
Algorithmic results:
Use rapidly mixing
Markov chains
(Broder; Jerrum-Sinclair)
Enough to estimate
the mixing rate
of random walk
on lattice in K
Probability:
use eigenvalue gap
Graph theory (expanders):
use conductance to
estimate eigenvalue gap
Alon, Jerrum-Sinclair
Enough to prove
isoperimetric inequality
for subsets of K
Differential geometry:
Isoperimetric inequality
Dyer
Frieze
Kannan
1989
O* (n27 )
Differential equations:
bounds on Poincaré
constant
Paine-Weinberger
bisection method,
improved
isoperimetric inequality
LL-Simonovits 1990
O* (n16 )
Log-concave functions:
reduction to integration
Applegate-Kannan 1992
O* (n10 )
Convex geometry:
Ball walk
LL 1992
O* (n10 )
Statistics:
Optimization:
Functional analysis:
isotropic position of
convex bodies
Better error handling
Dyer-Frieze 1993
Better prepocessing
LL-Simonovits 1995
*
8
*
7
*
5
O (n )
O (n )
O (n
achieving
isotropic position
Kannan-LL-Simonovits 1998
)
*
Geometry:
projective (Hilbert)
distance
O
affine invariant
isoperimetric inequality
analysis of hit-and-run walk
LL 1999
Differential equations:
log-Sobolev inequality
elimination of “start
penalty” for lattice walk
Frieze-Kannan 1999
log-Cheeger inequality
elimination of “start
penalty” for ball walk
Kannan-LL 1999
Scientific computing:
non-reversible chains
mix better; lifting
Diaconis-Holmes-Neal
Feng-LL-Pak
walk with inertia
Aspnes-Kannan-LL
( n5 )
O* (n5 )
O* (n3 )??
More and more tools from classical math
Linear algebra : eigenvalues
semidefinite optimization
higher incidence matrices
homology theory
Geometry :
geometric representations
convexity
Analysis:
generating functions
Fourier analysis, quantum computing
Number theory: cryptography
Topology, group theory, algebraic geometry,
special functions, differential equations,…