The East Annex
Proceedings CFP
| Synopsis
| Organizers
| Application
| Hotel
| Roommates
| Directions, transportation
| Dining
| Internet
| Contact
| Talks
| Schedule
| Abstracts
| Pictures
An international conference on Combinatorics, Groups, Algorithms, and Complexity will be held at the Ohio State University, Columbus, Ohio on March 21-25, 2010 (Sunday-Thursday).
A volume of follow-up papers to the conference will be published. All participants are welcome to contribute, as are those who had wished to attend but could not make it. To recognize Laci's commitment to free online publishing, we have made arrangements to publish the volume as a special issue of the open access online journal Discrete Mathematics and Theoretical Computer Science. A special advantage of this arrangement for conference proceedings and Festschrifts is that each paper is published soon after its acceptance in final form; fast authors don't need to wait for their less industrious colleagues.
The editorial board of the special issue consists of
Target dates
Submissions are requested by October 1, 2010. Papers are expected to appear starting January 2011.
Authors are requested to send advance notification to the conference email address regarding their intention to contribute (please include the authors' names, a tentative title, a tentative abstract, the expected length of the paper, and the expected date of submission), whereupon we shall send the submission instructions and further information.
A powerful web of interconnections between the areas in the title has been built over the past decades, with a transformative effect on each area.
Problems of combinatorial optimization, especially problems for graphs (cliques, coloring, matchings, paths, cuts, etc.) have for decades been among the central subjects of study both in the theory of algorithms and in complexity theory; in return, complexity theory has provided fundamental new insights into the nature of these problems. This interaction was critical at the genesis of the P vs NP problem four decades ago, underwent a second revolution in the wake of interactive proofs and the modern theory of approximation algorithms, and continues to this date with the study of the striking effects of the Unique Games Conjecture on the landscape of approximation algorithms in combinatorial optimization.
Combinatorial models of computation (circuits, branching programs, communication complexity, etc.) have given rise to some of the most exciting developments in complexity theory, and continue to pose some of the most daunting challenges. Probabilistic and extremal combinatorics have provided many of the basic tools for theoretical computer science, and conversely, work driven by questions of complexity theory has contributed to progress on central questions in combinatorics (e.g. on explicit Ramsey constructions).
While this conference continues to explore the interactions between combinatorics and theoretical computer science, it will be the first conference to highlight the role of group theory in this web.
Cayley graphs and vertex-transitive graphs have for a long time provided a link between combinatorics and group theory; they have also been studied in the context of interconnection networks and serve as a fertile ground to study the mixing rate of random walks, an area of intense study in the theory of computing for its connection to approximate counting; group theoretic expander constructions are household tools in complexity theory and have helped infuse new blood into the classical theory of error-correcting codes, itself noted for its deep connections to group theory; the construction of zig-zag products of graphs, motivated in part by the notion of semidirect products of groups, has lead to a recent breakthrough in space complexity; complexity theoretic thinking has taken root in computational group theory; a complexity theoretic study of groups has served as one of the motivations behind interactive proofs; interactive and holographic proofs have spawned new areas of coding theory (locally testable and locally correctable codes) and contributed to the rise of a new paradigm in decision tree complexity (property testing); discrete Fourier transform, a group theoretic concept, has been central to the study of the complexity of Boolean functions as well as to holographic proofs; Weil's character sum estimates serve as powerful derandomization tools; groups continue to serve as models for the comparison of complexity classes; group theory was found to be at the heart of the graph isomorphism problem, one of the few classical combinatorial search problems of unsettled complexity status; combinatorial methods and asymptotic thinking, to no small extent inspired by algoritmic questions, are partly responsible for the rise of the area of asymptotic group theory; the probabilistic method and the study of random structures, both pioneered by Paul Erdős in combinatorics, have become standard tools in algorithms and complexity theory and have impacted asymptotic group theory; group representations have recently been connected to fast matrix multiplication; the unitary group is the central medium of computation in quantum computing, an area where the hidden subgroup problem has emerged to a prominent status - just to name a few of the connections.
The meeting will bring together scholars and students in the areas in the title. It is our hope that the conference will inspire new links and further cross-fertilization.
Not coincidentally, the meeting will take place during the year of Laci Babai's 60th birthday.
Application is now closed. No more travel stipends are available.
The conference hotel is Hampton Inn & Suites Columbus - Downtown, 501 North High Street, Columbus, Ohio 43215. Tel: +1-614-559-2000. Campus is accessible by a 10-minute bus ride.
A block of rooms has been reserved for conference participants. The conference rate is USD 110 per night for single rooms and USD 120 per night for double rooms, plus 16.75% tax. To get the conference rate, you must reserve your room by February 18, 2010. When making your reservation, mention the conference code, "CGAC conference."
Check below for conference transportation.
Hop on the plane; get off at Port Columbus International Airport (CMH), Columbus, Ohio, the 52nd busiest airport in the United States. Take a cab. The ride to the hotel costs approximately 20 dollars and takes about 15 minutes.
All lectures are held on the Ohio State University campus, East Annex building (building 004 on the map, adjacent to the Math Tower, building 007), 209 W 18th Avenue, first floor, lecture halls EA 160 and EA 170.
Travel between hotel and campus: Take the #2 bus along N. High Street ($1.75 per ride). The "2" is usually combined with a letter, e.g., you will see buses 2G, 2X, etc. All these buses are ok. (The letter indicates where the bus will turn around, e.g., 2G at Graceland, 2X at Crossroads; these don't affect the trip between the hotel and campus.)
From the hotel: take the northbound bus on N. High Street, get off at 17th Avenue. Walk across the street, walk West on 17th or 18th Avenue to the East Annex (about 3 minutes).
Back to the hotel: catch the southbound bus on N. High Street, get off at the hotel, near Nationwide. The ride takes about 10 minutes.
During weekdays, buses are frequent (every 8-10 minutes between 8am and 6pm, every 12-20 minutes between 6pm and 8pm, and less frequently until midight).
On Sunday only, a charter bus will be provided for the conference participants, leaving the hotel at 8:05am and at 8:35am and leaving from East Annex at 6:05pm and 6:35pm. The city buses also operate on Sunday, about every half hour. There will be a charter bus after the Tuesday evening reception, leaving the Math Tower at 9:20pm and at 9:50pm.
Driving: from the hotel, drive North on N. High Street to campus, turn left on Woody Hayes Dr, then left on Tuttle Park Place. There is a public garage to your left, across from the Stadium (building 088 in the map). Parking for a day costs about $15.
The East Annex
East Annex has wireless internet access. You will find your code in the folder that will be waiting for you at the hotel desk. You are requested to fill out a form which will be distributed at the Welcome reception Saturday evening and during the coffee breaks.
There are several decent restaurants on N. High Street at a few minutes walk from the East Annex, frequented by students and faculty. Fancier dining establishments can be found near the hotel, along the Short North segment of N. High Street just North of the hotel and in downtown, just South of the hotel.
Email: babai59 @ math.ohio-state.edu (oops! the 59 is wrong! to be eligible, you have to guess the right number ;)
Last updated: October 28, 2010