
Past attractions
FALL 2007
 September 5, 2007, Boris Aronov, Polytechnic University, Brooklyn
A generali
zation of magic squares with applications to digital halftoning
 September 19, 2007 Boris Bukh, Princeton University
Nontrivial solutions to a
symmetric linear equation in integers
 October 3, 2007 Peter Brass, City College, CUNY
Searching a target in a grid graph
 October 10, 2007, Maria Chudnovsky, Columbia University
Even pairs in Berge graphs
 October 17, 2007, Alfred Inselberg, Tel Aviv University
Multidimensional visualization and its applications
 October 24, 2007, Dan Ismailescu, Hofstra University
Circumscribed polygons of small area
 October 31, 2007, PoShen Loh, Princeton University
Avoiding small subgraphs in Achlioptas processes
 November 7, 2007, Joel Spencer, Courant Institute, NYU
The ErdosRenyi phase transition
 December 12, 2007, Student Presentations
Ben Baumer, Pete Terlecky
 December 19, 2007, Adrian Dumitrescu, University of Wisconsin, Milwaukee
On distinct distances among points
SPRING 2007
 February 14, 2007, Jon Lenchner, IBM T.J. Watson Research Center, Yorktown Heights
New proof of a theorem of Csima and Sawyer concerning ordinary points in line arrangements
 March 7, 2007, Daniel Stefankovic, University of Rochester
Adaptive annealing: A nearoptimal connection between sampling and counting
 March 28, 2007, Jan Vondrak, Princeton University
Embedding trees in pseudorandom graphs
 April 11, 2007, Imre Barany, Renyi Institute, Budapest and University College London
Paths with no small angle
 April 12, 2007, Thursday 4:15pm, Assaf Naor, Courant Institute, NYU
The story of the Sparsest Cut Problem (in rm. 9204!)
 April 25, 2007, Panagiotis Cheilaris, CUNY Graduate Center
Conflictfree coloring for geometric hypergraph
 May 2, 2007, Jacob Fox, Princeton University
Induced Ramseytype theorems
 May 9, 2007, Ferran Hurtado, Univ. Politecnica de Catalunya,
Squares!
FALL 2006
 September 13, 2006 Raghavan Dhandapani, Courant Institute, NYU
Greedy embeddings of planar triangulations
 September 20, 2006 Geza Toth, Renyi Institute, Hungarian Academy
Drawing graphs with few slopes
 September 21, Thursday, 4:15pm!!! Benny Sudakov, Princeton University and IAS
Additive approximation for edgedeletion problems, at the CUNY Graduate Center, 365 Fifth Ave., rm 9204/9205!!!
 September 27, 2006 Boris Bukh, Princeton University
Induced subgraphs of Ramsey graphs with many distinct degrees
 October 11, 2006 Rados Radoicic, Baruch College, CUNY
The discharging method and its applications for graph drawing
 October 12, Thursday, 4:15pm!!!Maria Chudnovsky, Columbia University and Clay Math. Institute
Testing for a theta
 October 18, 2006 John Iacono, Polytechnic University, Brooklyn
Necklaces, convolutions, and X+Y
 November 1, 2006 Amitai Perlstein, Technion, Haifa
SylvesterGallai type theorems for pseudoparabolas
 November 8, 2006 Olivier Bernardi, Centre de Recerca Matematica, Barcelona
Bijective decomposition of treerooted maps
 November 29, 2006 Amit Agarwal, Princeton University
Undecidable statements and the zeroone law in random geometric graphs
SPRING
2006
 February 8, 2006 PoShen Loh, Princeton University
Independent transversals in locally sparse graphs
 February 15, 2006 Nir Y Ailon, Princeton University
Ranking and clustering: aggregating inconsistent information
 February 22, 2006, at 3 p.m. in room 1314 Courant Institute!!! Shakhar Smorodinsky, Courant Institute, NYU
The kset problem
 February 22, 2006 Tudor Zamfirescu, Universitat Dortmund
Pushing bodies through holes
 March 1, 2006 Geza Toth, Renyi Institute, Budapest
Degenerate crossing numbers of graphs
 March 15, 2006 Jonathan Lenchner, IBM T.J. Watson Research Center, Yorktown Heights
Ordinary points in the Euclidean and projective planes
 March 22, 2006 Rados Radoicic, Rutgers University, New Brunswick
Old and new directions in Ramsey theory on integers
 April 26, 2006 Pankaj K. Agarwal, Duke University, Durham
Robust shape fitting via peeling and grating coresets
 May 3, 2006 Peter Brass, City College, CUNY
Problems and results on data structures
FALL
2005
 September 14, 2005 Jacob Fox, MIT, Cambridge
A bipartite analogue of Dilworth's theorem
 September 21, 2005 Andres Varon, CUNY Graduate Center
On the empty hexagon theorem
 September 28, 2005 Raghavan
Dhandapani, Courant Institute, NYU
The
halving line problem
 October 5, 2005 Joel Ratsaby, Ben Gurion University of the Negev
On the combinatorial complexity of constrained VapnikChervonenkis classes
 October 19, 2005 Arman Artuc,
CUNY Graduate Center
Simultaneous
embeddings of planar graphs
 October 26, 2005 Edgar Troudt,
CUNY Graduate Center
Geometric graphs have arbitrarily large geometric thickness
 November 2, 2005 Panos Hilaris,
CUNY Graduate Center
Some remarks on online conflictfree coloring for intervals
 November 16, 2005 Amitava Bhattacharya,
University of Illinois at Chicago
The alternating cone of a 2colored graph
 November 30, 2005 Jan Vondrak,
Microsoft, Redmond
Ramseytype results for the hypercube
 December 7, 2005 Marisa Debowsky,
Courant Institute, NYU
A characterization of projectiveplanar signed graphs
SPRING 2005
 March 2, 2005 Jacob Fox,
M.I.T., Cambridge
Independence in Euclidean Ramsey Theory
 March 9, 2005 David Galvin,
Institute for Advanced Study, Princeton
Entropy and graph homomorphisms
 March 16, 2005 Tibor Szabo,
ETH Zurich
Random walk on oriented hypercubes
 March 23, 2005 Adrian Dumitrescu,
University of Wisconsin, Milwaukee
Sliding disks in the plane
 May 4, 2005 Jan Vondrak,
M.I.T., Cambridge
Boosted sampling and minimum spanning trees
 May 11, 2005 Gabor Tardos,
Renyi Institute, Budapest
T.B.A.
FALL
2004
 September 22, 2004 Joshua Cooper,
Courant Institute, NYU
Generalized de Bruijn Cycles
 September 29  October 2, 2004 Graph Drawing 04,
Steinman Hall, City College, CUNY
12th International Symposium on Graph Drawing
 October 20, 2004 Raghavan Dhandapani,
Courant Institute, NYU
On Edge Guarding a Planar Graph
 October 27, 2004 John Iacono,
Polytechnic University, Brooklyn
O(loglogn)competitive Binary Search Trees
 November 3, 2004 Rados Radoicic,
Rutgers University, New Brunswick
Iterative Processes in the Plane
 November 17, 2004 Shakhar Smorodinsky,
ETH Zurich and New York University
OnLine ConflictFree Coloring
SPRING
2003
 February 5, 2003 Amit Chakrabarti,
Institute for Advanced Study, Princeton
Informational complexity and lower bounds in communication
complexity
 February 19, 2003 Peter Brass,
City College, CUNY
On testing congruence of higherdimensional point sets
 March 5, 2003 James Abello,
DIMACS, Rutgers University
Massive graph mining
 March 19, 2003 Geza Toth,
Renyi Institute, Budapest
Conflictfree coloring
 March 26, 2003 Amotz BarNoy,
Brooklyn College and Graduate Center
The windows scheduling problem
 April 2, 2003 Laura HeinrichLitan,
Technische Universitat Braunschweig
Nearest neighbor search in high dimensions
 April 9, 2003 Rom Pinchasi ,
M.I.T. Cambridge, MA
The number of directions determined by n points in space
 April 15, 2003 ON TUESDAY!!! Bilal Khan,
CUNY Graduate Center
Whitehead's graph: automorphic conjugacy
in the free group of rank 2
 May 7, 2003 Adrian Dumitrescu,
University of Wisconsin
Monotone paths in line arrangements with a small number of
directions
FALL
2002
 September 18, 2002 Peter Brass,
City College, CUNY
Geometry with
coins
 September 25, 2002 Micha Sharir,
Tel Aviv University
Incidences and
related problems
 October 9, 2002 Geza Toth,
Renyi Institute, Budapest
An ErdosSzekeres
type problem in the plane
 October 23, 2002 Stefan Burr,
City College, CUNY
Equal sums of
cubes
 October 30, 2002 Rados Radoicic,
MIT, Cambridge
Graphs
drawn with at most 3 crossings per edge
 November 13, 2002 Joseph Malkevitch,
York College, CUNY
Robot
arms, polygons, and rigidity
 November 20, 2002 Sergio Cabello,
Universiteit Utrecht
Testing homotopy for paths in the plane
 December 4, 2002 Anupam Gupta,
Bell Laboratories
Algorithmic applications of metric embeddings
SPRING
2002
 February 6, 2002 Jozsef Balogh
AT&T
Monoton
graph properties
 February 13, 2002 Sanjoy Dasgupta
AT&T
An algorithm for clustering highdimensional data
 February 28, 2002, 4p.m. in room 9204 (special date
and place!) Noga Alon
Tel Aviv University and I.A.S., Princeton
Testing graph properties
 March 6, 2002 Ayman Khalfalah
Rutgers University
Ramseytype problems in combinatorial number theory
 March 13, 2002 Zoltan Furedi
University of Illinois and Hungarian Academy of Sciences
Identifying codes
 March 20, 2002 Martin Anthony
London School of Economics
Combinatorial measures of expressive power in
computational learning theory
 April 3, 2002 Peter Brass
Freie Universitat Berlin
On finding symmetries and related algorithmic problems
 April 10, 2002 Yi Zhao
Rutgers University
Proof of a tiling conjecture of Komlos
 April 17, 2002 Amit Chakrabarti
Princeton University
Minorclosed graph properties are evasive
FALL 2001
 October 10, 2001 Micha Sharir
Tel Aviv University
Union of geometric
objects
 October 24, 2001 Rados Radoicic
M.I.T., Cambridge, MA
The chromatic
number of 3space
 November 7, 2001 Herve Bronnimann
Polytechnic University, Brooklyn
Enumerating
pseudotriangulations
 November 21, 2001, 5:30pm (!) Nick Wormald Melbourne
University, Australia
Models of
random regular graphs
 November 28, 2001 Mario Szegedy
Rutgers University, New Brunswick
Quantum lower
bounds by dualization
 December 12, 2001, 5:30pm (!)
Roy Meshulam Institute for Advanced Study, Princeton
Group algebras,
expanders and codes
SPRING 2001
 January 31, 2001 Igor Shparlinski
Macquarie University, Sydney
Set
proportionality testing
 February 7, 2001 Igor Pak
M.I.T., Cambridge, MA
Invariants
of ribbon tiles
 February 14, 2001 Jim Cox and Dan
Karron Brooklyn College, CUNY and Computer Aided Surgery,
Inc.
Topological
zone organization of scalar volume data
 February 21, 2001 Gary Gordon
Lafayette College and DIMACS
The beta
invariant and antimatroids
 March 7, 2001 Clifford Smyth
Rutgers University, New Brunswick
Equilateral
sets
 March 21, 2001 Jozsef Solymosi
ETH Zurich
Square triples
in dense grids
 March 28, 2001 Jesus De Loera
UC Davis, CA
Counting
network flows
 May 2, 2001 Ariel Halpert
CUNY Graduate Center
Sums over
kterm compositions
 May 4 (Friday) 2001 The GoodmanPollack
Twothirdsofacentury Fest at Courant Institute, 251 Mercer
Street, Rm. 109
Featuring
G. Kalai (Jerusalem), R. Wenger (Columbus), L. Lovasz (Microsoft),
P. Agarwal (Duke)
FALL 2000
 September 13, 2000 Dan Ismailescu
Courant Institute, NYU,
Minimizer
graphs for a class of extremal problems
 September 20, 2000 Florian Lengyel
CUNY Graduate Center,
New proof
of a theorem on recurrence relations
 September 27, 2000 Michael Krivelevich
Tel Aviv University,
Graph
coloring in expected polynomial time
 October 11, 2000 Bill Steiger
Rutgers University,
Depth
 October 18, 2000 Joe Malkevitch
CUNY York College,
Pancakes,
parallel computation, and genome rearrangement
 October 25, 2000 Rom Pinchasi
Hebrew University, Jerusalem,
New results
about circles in the plane
 November 1, 2000 Bernardo Abrego and
Silvia Fernandez Merchant Rutgers University, New Brunswick,
Unit distances
among vertices of a convex polygon
 November 8, 2000 Gabor Tardos
Renyi Institute, Budapest,
ksets in
2 and 3 dimensions
 December 6, 2000 Bruce Reed
CNRS, Paris,
Graph colouring
via the probabilistic method
SPRING
2000
 May 10, 2000 Peter Brass
Freie Universitat, Berlin,
Matching
point patterns
 May 3, 2000 Katherine St. John,
Lehman College, CUNY,
Games on
random structures
 April 12, 2000 Geza Toth,
M. I. T.,
New bounds
on crossing numbers
 April 5, 2000 Bernardo Abrego and
Silvia Fernandez Merchant, Rutgers University, New Brunswick
On the structure
of point sets containing many similar copies of a given pattern
 March 29, 2000 Alex Samorodnitsky,
Institute for Advanced Study, Princeton,
On
the optimum of Delsarte's linear program
 March 8, 2000 Benny Sudakov,
Princeton University,
Acyclic
edge colorings of graphs
 March 1, 2000 Eldar Fischer,
NEC Research Institute, Princeton,
Graph embedding
problems  Methods and applications
 February 23, 2000 Joel Spencer,
Courant Institute, New York University,
Random
processes
 February 16, 2000 Alexander K. Kelmans,
DIMACS, Rutgers University, NJ
Optimal
packing of induced stars in a graph
 February 9, 2000 Rom Pinchasi,
Hebrew University, Jerusalem
Application
of allowable sequences to plane geometry
FALL 1999
 December 8, 1999 Ron Holzman,
M.I.T. and Technion (Haifa)
The majority
action on infinite graphs: strings and puppets
 November 17, 1999 Stefan Burr,
City College, CUNY
The Ramsey arrow
and the polynomial hierarchy
 November 10, 1999 Gabor Tardos,
DIMACS and Hungarian Academy of Science
Linear hash
functions
 November 3, 1999 Bilal Khan,
CUNY Graduate Center
Graphs, free
groups, and the Hanna Neumann Conjecture
 October 27, 1999 Gary Bloom,
City College, CUNY
Some encouraging
new negative results on graceful graphs
 October 20, 1999 Richard Pollack,
Courant Institute, NYU
ETR and some
elementary geometric problems
 October 6, 1999 Michael Anshel,
City College, CUNY
Constructing public
key cryptosystems via combinatorial group theory
 September 29, 1999 Mario Szegedy,
Institute for Advanced Study, Princeton
Testing first
order graph properties
 September 22, 1999 Dan Ismailescu,
Courant Institute, NYU
Illuminating
a convex polygon by floodlights
 September 15, 1999 Ariel Halpert,
CUNY Graduate Center
Cellular
telephone networks and random maps in hypergraphs

