Combinatorics Seminar

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
Non-trivial 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, Po-Shen Loh, Princeton University
Avoiding small subgraphs in Achlioptas processes
November 7, 2007, Joel Spencer, Courant Institute, NYU
The Erdos-Renyi 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 near-optimal 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
Conflict-free coloring for geometric hypergraph
May 2, 2007, Jacob Fox, Princeton University
Induced Ramsey-type 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 edge-deletion 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
Sylvester-Gallai type theorems for pseudoparabolas
November 8, 2006 Olivier Bernardi, Centre de Recerca Matematica, Barcelona
Bijective decomposition of tree-rooted maps
November 29, 2006 Amit Agarwal, Princeton University
Undecidable statements and the zero-one law in random geometric graphs

SPRING 2006

February 8, 2006 Po-Shen 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 k-set 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 Vapnik-Chervonenkis 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 conflict-free coloring for intervals
November 16, 2005 Amitava Bhattacharya, University of Illinois at Chicago
The alternating cone of a 2-colored graph
November 30, 2005 Jan Vondrak, Microsoft, Redmond
Ramsey-type results for the hypercube
December 7, 2005 Marisa Debowsky, Courant Institute, NYU
A characterization of projective-planar 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
On-Line Conflict-Free 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 higher-dimensional point sets
March 5, 2003 James Abello, DIMACS, Rutgers University
Massive graph mining
March 19, 2003 Geza Toth, Renyi Institute, Budapest
Conflict-free coloring
March 26, 2003 Amotz Bar-Noy, Brooklyn College and Graduate Center
The windows scheduling problem
April 2, 2003 Laura Heinrich-Litan, 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 Erdos-Szekeres 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 high-dimensional 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
Ramsey-type 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
Minor-closed 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 3-space
November 7, 2001 Herve Bronnimann Polytechnic University, Brooklyn
Enumerating pseudo-triangulations
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 k-term compositions
May 4 (Friday) 2001 The Goodman-Pollack Two-thirds-of-a-century 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,
k-sets 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

	Graduate Center, CUNY Combinatorics Seminar
	The combinatorics seminar covers a wide range of topics in combinatorics and graph theory with particular emphasis on algorithms and areas related to computer science. Many of the speakers are CUNY and NYU visitors, postdocs, and graduate students. A seminar talk may cover original research or report on an interesting paper. The seminar is run by Janos Pach The seminar meets on Wednesdays at 6:30 p.m. in room 6417 of the new building of the Graduate Center, 365 Fifth Avenue (at the corner of 34th Street), New York. it can be easily approached by subway, using the B,D,F,N,Q,R, or 6 trains.
	Upcoming events February 6, 2008, Florian Lengyel, CUNY Graduate Center Probabilistic and enumerative combinatorics of almost injective functions and random matchings in hypergraphs February 13, 2008, Dan Cranston, DIMACS and Bell Labs Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem February 27, 2008, Esther Ezra, Duke University On the union of cylinders March 12, 2008, Geza Toth, Renyi Institute The Erdos-Szekeres theorem with forbidden order types March 19, 2008, Gabor Kun, Simon Fraser University, Burnaby Cops and robbers in random graphs April 2, 2008, Micha Sharir, Tel Aviv University and NYU Weak epsilon nets, Davenport-Schinzel sequences, and other recent surprizes April 9, 2008, Wal Wallis, Southern Illinois University, Carnondale Properly separated permutations April 30, 2008, Visualization Day at City College, CUNY 140th St. at Convent Av., 10 a.m. Details May 14, 2008, Alexey Glazyrin, University of Texas, Brownsville Anti-Durer conjecture for nonconvex polytopes
	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 Non-trivial 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, Po-Shen Loh, Princeton University Avoiding small subgraphs in Achlioptas processes November 7, 2007, Joel Spencer, Courant Institute, NYU The Erdos-Renyi 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 near-optimal 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 Conflict-free coloring for geometric hypergraph May 2, 2007, Jacob Fox, Princeton University Induced Ramsey-type 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 edge-deletion 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 Sylvester-Gallai type theorems for pseudoparabolas November 8, 2006 Olivier Bernardi, Centre de Recerca Matematica, Barcelona Bijective decomposition of tree-rooted maps November 29, 2006 Amit Agarwal, Princeton University Undecidable statements and the zero-one law in random geometric graphs SPRING 2006 February 8, 2006 Po-Shen 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 k-set 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 Vapnik-Chervonenkis 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 conflict-free coloring for intervals November 16, 2005 Amitava Bhattacharya, University of Illinois at Chicago The alternating cone of a 2-colored graph November 30, 2005 Jan Vondrak, Microsoft, Redmond Ramsey-type results for the hypercube December 7, 2005 Marisa Debowsky, Courant Institute, NYU A characterization of projective-planar 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 On-Line Conflict-Free 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 higher-dimensional point sets March 5, 2003 James Abello, DIMACS, Rutgers University Massive graph mining March 19, 2003 Geza Toth, Renyi Institute, Budapest Conflict-free coloring March 26, 2003 Amotz Bar-Noy, Brooklyn College and Graduate Center The windows scheduling problem April 2, 2003 Laura Heinrich-Litan, 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 Erdos-Szekeres 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 high-dimensional 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 Ramsey-type 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 Minor-closed 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 3-space November 7, 2001 Herve Bronnimann Polytechnic University, Brooklyn Enumerating pseudo-triangulations 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 k-term compositions May 4 (Friday) 2001 The Goodman-Pollack Two-thirds-of-a-century 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, k-sets 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