July 2019
July in New Brunswick will be a little “complex” as Rutgers and DIMACS are hosting three different complexity-themed events that will be held July 15-20, 2019. These events culminate with the annual Computational Complexity Conference (CCC2019) and mark the official launch of the DIMACS Special Focus on Lower Bounds in Computational Complexity.
CCC is organized by the Computational Complexity Foundation and held annually at different host venues. In July, Rutgers will be local host for the roughly 100 participants attending CCC 2019.
CCC is focused on research at the forefront of computational complexity theory, studying the absolute and relative power of computational models under resource constraints. Computational models include deterministic, nondeterministic, randomized, and quantum models; uniform and nonuniform models; Boolean, algebraic, and continuous models. Resource constraints involve time, space, randomness, program size, input queries, communication, and entanglement; worst-case as well as average case. Other topics represented at the conference can include: probabilistic and interactive proof systems, inapproximability, proof complexity, descriptive complexity, and complexity-theoretic aspects of cryptography and machine learning, as well as results from other areas of computer science and mathematics motivated by computational complexity theory.
This year’s CCC has a total of 34 technical talks, including invited presentations by Ran Raz (Princeton) and Dor Minzer (Institute for Advanced Study). A Friday-evening rump provides a forum for short presentations announcing new results or presenting open problems to the community. Papers from CCC will be published in the open access venue Leibniz International Proceedings in Informatics (LIPIcs).
Leading up to CCC are two DIMACS-sponsored events targeting students or others who may be interested in learning more about complexity research. The first is the CoSP Workshop and School on Algorithms and Complexity organized by Michal Koucký and Martin Loebl (both of Charles University) in association with the long-standing REU partnership between DIMACS and Charles University. The CoSP Workshop and School on Algorithms and Complexity includes four tutorial talks over two days with time reserved each afternoon for informal discussion and collaboration. The presentations give participants an overview of hot research areas and recent advances without assuming extensive prior knowledge. On the first day, Eric Allender (Rutgers) discusses why complexity theorists care so much about the Minimum Circuit Size Problem (MCSP) and Alexandr Andoni (Columbia) talks about the importance of tools often studied in the context of sublinear algorithms in improving computational efficiency. On the second day, Mike Saks (Rutgers) talks about cases when approximating quadratic-time dynamic programming algorithms leads to subquadratic (but inexact) algorithms, and Sophie Spirkl (Rutgers) presents recent results and open problems in coloring graphs that do not contain certain subgraphs. This event is sponsored by the Combinatorial Structures and Processes (CoSP) project led by Charles University with funding from the EU’s Horizon 2020 program.
Between the CoSP Workshop and the CCC Conference lies the DIMACS Day of Complexity Tutorials. It features two half-day tutorials on topics that are thought to be especially exciting and relevant for the CCC community. In the morning, Mika Göös (IAS) discusses the use of lifting theorems to translate lower bounds for simple models of computation (such as decision trees) to lower bounds for more powerful models (such as communication protocols). In the afternoon, Omer Reingold (Stanford) talks about research that endeavors to show that randomized algorithms are not much more powerful than deterministic algorithms. In particular, he discusses recent progress toward showing that problems solvable by a randomized space-bounded algorithm are also solvable by a deterministic algorithm that only uses a constant factor more space (where space refers to memory). The tutorials will be targeted toward postdocs, graduate students, advanced undergraduates with prior work in complexity, or others who would like a cohesive introduction to the topics.
Presentations from the CoSP Workshop and the Day of Complexity Tutorials, as well as the two invited presentations at CCC will be videotaped and posted on the DIMACS YouTube channel.
These events are associated with the DIMACS Special Focus on Lower Bounds in Computational Complexity. To receive announcements about other events in the special focus, you can join the special focus mailing list.
Printable version of this story: [PDF]