[math-ias] Theoretical Computer Science/Discrete Math Seminars -- Week of September 23, 2013

[Anthony V. Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Theoretical Computer Science/Discrete Math Seminars
Week of September 23, 2013




Monday, September 23

Computer Science/Discrete Mathematics Seminar I
Topic:         Using the DFS Algorithm for Finding Long Paths in
Random and Pseudo-Random Graphs
Speaker:     Michael Krivelevich, Tel Aviv University
Time/Room:     11:15am - 12:15pm/S-101
Abstract:    See below



Tuesday, September 24

Computer Science/Discrete Mathematics Seminar II
Topic:         Finite Field Restriction Estimates
Speaker:     Mark Lewko, Institute for Advanced Study; Member, School
of Mathematics
Time/Room:     11:15am - 12:15pm/S-101
Abstract:    See below

1    Using the DFS Algorithm for Finding Long Paths in Random and
Pseudo-Random Graphs
    Michael Krivelevich

The Depth First Search (DFS) algorithm is one of the most standard
graph exploration algorithms, used normally to find the connected
components of an input graph. Though perhaps less popular than its
sister algorithm, Breadth First Search (BFS), the DFS algorithm is
very simple and handy and has many nice properties; it is particularly
well suited for finding long paths. In this talk I will discuss how
basic properties of the DFS algorithm can be exploited to argue about
the (typical)
existence of long paths in random and pseudo-random graphs. Based
partly on a joint work with Benny Sudakov.



2    Finite Field Restriction Estimates
    Mark Lewko

The Kakeya and restriction conjectures are two of the central open
problems in Euclidean Fourier analysis (with the second logically
implying the first, and progress on the first typically implying
progress on the second). Both of these have formulations over finite
fields. In 2008 Dvir completely settled the finite field Kakeya
conjecture, however neither his result nor the proof method have yet
yielded any progress on the finite field restriction conjecture. In
this talk I will describe some recent progress on the finite field
restriction conjecture, improving the the exponents of Mockenhaupt and
Tao. The key new ingredient is the use of incidence / sum-product
estimates. [This will be a longer version of the talk I gave in the
Princeton CCI seminar on 9/13/2013]


Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu
-------------- next part --------------
A non-text attachment was scrubbed...
Name: doc.pdf
Type: application/pdf
Size: 2812 bytes
Desc: not available
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20130918/ad1d8d8f/attachment-0002.pdf>