STOC 2016: 48th Annual Symposium on the Theory of Computing

Invited Speakers:

• Santosh Vempala, Georgia Institute of Technology
• Title: The Interplay of Sampling and Optimization in High Dimension
• Abstract: In the first part of this talk, we show how simulated annealing can be used for both logconcave sampling and convex optimization by varying parameter settings. The resulting algorithm for optimization can be viewed as an interior-point method needing only a membership oracle and achieving the same worst-case iteration complexity as the best possible barriers. In the second part, we present a faster sampling algorithm for polytopes which achieves subquadratic mixing time. The advantage of the algorithm, called geodesic gliding, comes from using non-Euclidean geometries where effects of the boundary are milder. Roughly speaking, geodesic gliding is an efficient discrete-time simulation of a stochastic differential equation on a Riemannian manifold whose metric is defined by the Hessian of a convex function. The talk is based on joint works with Ben Cousins, Adam Kalai, Yin Tat Lee and Laci Lovasz.
• Timothy M. Chan, University of Waterloo
• Title: Computational Geometry, from Low to High Dimensions
• Abstract: Abstract: Classical exact algorithms in computational geometry usually have run times that are exponential in the dimension. Recently, slightly subquadratic results have been found for some basic problems, such as offline orthogonal range search and offline Hamming nearest neighbor search, even when the dimension goes above logarithmic, surprisingly. I will survey these recent findings (including some work in progress and a new joint work with Josh Alman and Ryan Williams). Along the way, we will see how old geometric divide-and-conquer ideas (variants of range trees and kd trees) can help solve nongeometric problems, such as all-pairs shortest paths, Boolean matrix multiplication, and 0-1 integer linear programming. In the opposite direction, we will also see how nongeometric techniques (fast matrix multiplication, circuit complexity, probabilistic polynomials, and Chebyshev polynomials) can help computational geometry. The latter techniques also give new results on offline approximate nearest neighbor search.

Workshops and Tutorials:

• 1st Intl. Workshop on Geometry and Machine Learning
• Organizers: Jonathan Lenchner, Eli Packer, Jeff M. Phillips and Jinhui Xu
• Workshop webpage: http://sysrun.haifa.il.ibm.com/hrl/wogaml2016/org.shtml
• Abstract: Computational geometry plays a crucial and natural role in interacting with machine learning. Since geometric algorithms often come with quality guaranteed solutions, they are of ciritical importance in formalizing the effectiveness of various techniques and in developing new ones. On the other hand, problems in machine learning serve as important motivation for work central to geometric algorithms. This workshop is intended to provide a forum for those working in the fields of computational geometry, algorithms, machine learning and the various theoretical and algorithmic challenges to promote their interplay. As a joint STOC/SoCG workshop, we hope researchers who normally frequent only one of STOC or SoCG, but work in geometric algorithms for machine learning, will converge together sharing their insights and developments.


• Spanners: Graphs and Geometry:
• Organizers: Shiri Chechik, Michael Dinitz, and Virginia Vassilevska Williams
• Workshop website: http://www.cs.jhu.edu/~mdinitz/SpannerWorkshop/
• Abstract: Spanners, i.e. subgraphs which approximately preserve distances, have been studied in both graph and geometric settings for over 25 years. While there has been some limited interaction between researchers working in graph-theoretic settings and researchers working in geometric settings, work in the two communities has generally proceeded in parallel rather than in cooperation. The goal of this workshop is to bring together researchers interested in spanners (and other aspects of distance compression) in order to summarize and explore the state of the art, transition definitions and techniques between the communities, and explore questions about spanners and related objects that are of interest to both communities.


• Algorithms on topologically restricted graphs
• Organizers: Ken-ichi Kawarabayashi and Anastasios Sidiropoulos
• Workshop website: http://web.cse.ohio-state.edu/~tasos/topo_graphs_2016/
• Abstract: The workshop will focus on recent algorithmic advancements on problems on topologically restricted graphs, such as planar, surface-embedded, small treewidth, minor-free graphs, and graphs of small crossing number. The goal will be to emphasize developments that are of importance in the areas of fixed parameter tractability, approximation algorithms, topological graph theory, and metric embeddings. The program will attempt to highlight developments that are of importance in all of these areas, and emphasize technical connections between them.


• Geometric representations of graphs
• Organizers: Steven Chaplick and Piotr Micek
• Workshop website: http://geometricrepresentations16.tcs.uj.edu.pl/
• Abstract:The study of graphs via geometric representations is a classic topic in both computational geometry and the theory of computing. In ercent years, a lot of progress has been made in the study of geometric intersection graphs. Some notable solved problems include Scheinerman's conjecture, Erdos's problem on $\chi$-boundedness of segment graphs, and the hardness of the clique problem for segment graphs. This workshop aims to gather researchers working on these topics in order to exchange the ideas for further research. It will focus more on open problems and possible approaches rather than particular known results. Some potential topics include: computational complexity of hard geometric problems; algebraic approaches to topological drawings (e.g, Hanani-Tutte); constrained graph embedding problems; colorings of geometric intersection graphs; and approximation algorithms in geometric settings.


• Tutorial: Hardness of Learning
• Organizers: Amit Daniely
• Tutorial website: http://amitdaniely.com/stoc_2016_tutorial/hard_learn.html
• Abstract: Proving hardness of learning problems is a key challenge in Valiant's PAC learning model. As reductions from NP-hard problems do not seem to apply in this context, this area evolved somewhat separately. Traditionally, hardness of learning was proved under cryptographic assumptions. Such assumptions imply that it is hard to learn log-depth circuits, intersections of halfspaces, and more. More recently a new technique was developed for proving hardness of learning based on hardness on average of Constraint Satisfaction Problems like K-SAT and K-XOR. In particular, such assumptions imply that already very simple classes, like DNF formulas, are hard to learn. The tutorial will cover most central hardness of learning techniques and results, with emphasis on the aforementioned recent progress.

• Alexandr Andoni (Columbia University)
• Chandra Chekuri (University of Illinois at Urbana-Champaign)
• Suresh Venkatasubramanian (University of Utah)
• Yusu Wang (Ohio State University)

Workshop and tutorials attendance will be free. STOC and SoCG organizers will provide assistance with logistics including registration, meeting rooms, coffee breaks, wireless network, and a link to the web page of the event. Please feel free to contact the workshop committee at stocsocgworkshops@gmail.com if you have any questions.