SIGACT research highlights – call for nominations
TL;DR: Know of a great recent paper that should be highlighted to the theory community and beyond? Email a nomination to sigact.highlights.nominations@outlook.com by October 19th.
The goal of the SIGACT Research Highlights Committee is to help promote
top computer science theory research via identifying results that are of
high quality and broad appeal to the general computer science audience.
These results would then be recommended for consideration for the CACM Research Highlights section as well as other general-audience computer science research outlets.
Nomination and Selection Process:
The committee solicits two types of nominations:
1) Conference nominations. Each year, the committee will ask the PC
chairs of theoretical computer science conferences to send a selection
of up to three top papers from these conferences (selected based on both
their technical merit and breadth of interest to non-theory audience)
and forwarding them to the committee for considerations.
2) Community nominations. The committee will accept nominations from the members of the community. Each such nomination should summarize the contribution of the nominated paper and also argue why this paper is
suitable for broader outreach. The nomination should be no more than a
page in length and can be submitted at any time by emailing it to
sigact.highlights.nominations@outlook.com. Self-nominations are
discouraged.
The nomination deadline is Monday, October 19, 2020 .
Committee:
The SIGACT Research Highlights Committee currently comprises the
following members:
Boaz Barak, Harvard University
Irit Dinur, Weizmann Institute of Science
Aleksander Mądry, Massachusetts Institute of Technology (chair)
Jelani Nelson, University of California, Berkeley
Highlights of Algorithms (HALG) -free – Aug 31- Sep 2
[Guest post by Yossi Azar]
The 5th Highlights of Algorithms conference (HALG 2020) will take place Aug 31- Sep 2, 2020. http://highlightsofalgorithms.org/
The Highlights of Algorithms conference is a forum for presenting the highlights of recent developments in algorithms and for discussing potential further advances in this area. The conference will provide a broad picture of the latest research in algorithms through a series of invited talks, as well as short talks.
Invited talks includes top algorithmic surveys and papers from FOCS/STOC/SODA/COLT/PODC/SPAA/ITCS/PODS (2019-20)
PROGRAM
The conference will take place online on Mon, Aug 31-Wed, Sep 2 from 12:00 noon until 19:30 CEST (Europe time) http://highlightsofalgorithms.org/programme
The short contributed talk are on Sep 1-2, 9:45-11:30 CEST http://highlightsofalgorithms.org/shorttalks
REGISTRATION
Registration is free but mandatory
Please register on our webpage: https://highlightsofalgorithms2020.ethz.ch/registration
Ryan O’Donnell’s “TCS Toolkit” and other resources
When I was in grad school a common advice for beginning grad students was to leaf through the (paper) STOC or FOCS proceedings to see papers that you are interested in. This is still a decent advice (and requires less physical strength these days 🙂 ) but papers are not always the best source for people starting out. More often than we’d like to, the author of the 10th paper on a topic writes it to the audience of people that read (in fact probably wrote) the previous 9 papers.
Talks often do a better job of giving an overview of the field, and one great resource is the videos from the Simons Institute. If you want to get more in-depth information about a particular topic, it’s hard to beat the extended surveys in Foundations and Trends in TCS, as well as the related areas such as Machine Learning and Information Theory.
But if you are not yet sure what topic you’re interested in, or perhaps not even sure if you want to go to grad school, but you just know that you are interested in theory, there is now a new great resource. As I learned from Twitter, Ryan O’Donnell has just finished his TCS Toolkit course. All 99(!) lectures are on YouTube.
The topics are the following (these links are to the handwritten notes, for the lecture videos see YouTube channel):
1. Course Overview, and How to TCS
3. Factorials and Binomial Coefficients
7. Fast Multiplication with the DFT
8. Analysis of Boolean Functions
15.1. Cheeger’s Inequality (Spectral Graph Theory bonus)
21. LP Hierarchies and Proof Systems
p.s. For giving a high level taste of theory to beginning undergraduates, a great resource is Aaronson’s Quantum Computing since Democritus or Wigderson’s Math and Computation if they’re more math inclined.
CFP: Symposium on Simplicity in Algorithms (SOSA)
[Guest post by Valerie King. TL;DR SOSA 21 will take place jointly with SODA 21. To submit register by August 12, paper deadline August 19.]
Call for Papers: Registration deadline August 12, 2020
3rd SIAM Symposium on Simplicity in Algorithms (SOSA)
January 11-12, 2021
Alexandria, Virginia, U.S.
(Held jointly with SODA 2021)
Symposium on Simplicity in Algorithms (SOSA) is a conference in theoretical computer science dedicated to advancing algorithms research by promoting simplicity and elegance in the design and analysis of algorithms. The benefits of simplicity are manifold: simpler algorithms manifest a better understanding of the problem at hand; they are more likely to be implemented and trusted by practitioners; they can serve as benchmarks, as an initialization step, or as the basis for a “state of the art” algorithm; they are more easily taught and are more likely to be included in algorithms textbooks; and they attract a broader set of researchers to difficult algorithmic problems.
Papers in all areas of algorithms research are sought. An ideal submission will advance our understanding of an algorithmic problem by, for example, introducing a simpler algorithm, presenting a simpler analysis of an existing algorithm, or offering insights that generally simplify our understanding of important algorithms or computational problems.
We are especially interested in papers that make material more accessible to a wider audience, such as undergraduates, or for more specialized topics, general algorithms researchers.
Submissions should contain novel ideas or attractive insights, but they are not expected to prove novel theorems. That is, the results themselves can be known, but their presentation must be new. Conference website is https://www.siam.org/conferences/cm/conference/sosa21
Program Committee
Aaron Bernstein, Rutgers University, U.S.
Allan Borodin, University of Toronto, Canada
Timothy Chan, University of Illinois at Urbana-Champaign, U.S.
Edith Cohen, Google Research, U.S. and Tel Aviv University, Israel
Vincent Cohen-Addad, Google Research, Zürich, Switzerland
Sanjoy Dasgupta, University of California, San Diego, U.S.
Michael Elkin, Ben-Gurion University of the Negev, Israel
Funda Ergun, NSF and University of Indiana, Bloomington, U.S.
Mike Fellows, University of Bergen, Norway
Arnold Filtser, Columbia University, U.S.
Kasper Green Larsen, Aarhus University, Denmark
Andrew Goldberg, Amazon, U.S.
John Iacono, Université libre de Bruxelles, Belgium
Russell Impagliazzo, University of California, San Diego, U.S.
Giuseppe Italiano, LUISS Guido Carli, Rome, Italy
Michael Kapralov, École Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Anna Karlin, University of Washington, Seattle, U.S.
Valerie King, University of Victoria, Canada (Co-chair)
Hung Le, University of Victoria, Canada and University of Massachusetts at Amherst, U.S. (Co-chair)
Daniel Lokshtanov, University of California, Santa Barbara, U.S.
S. Cenk Sahinalp, NIH and University of Indiana, Bloomington, U.S.
Jared Saia, University of New Mexico, U.S.
Shay Solomon, Tel Aviv University, Israel
Mario Szegedy, Alibaba and Rutgers University, U.S.
Robert Tarjan, Princeton University, U.S.
Seeun William Umboh, University of Sydney, Australia
Qin Zhang, University of Indiana, Bloomington, U.S.
Uri Zwick, Tel Aviv University, Israel
Steering Committee
Michael A. Bender, Stony Brook University, U.S.
David Karger, Massachusetts Institute of Technology, U.S.
Tsvi Kopelowitz, Bar-Ilan University, Israel
Seth Pettie, University of Michigan, U.S.
Robert Tarjan, Princeton University, U.S.
Mikkel Thorup, University of Copenhagen, Denmark
Submissions and Deadlines:
A link to the submission site is available https://easychair.org/my/conference?conf=sosa21.
Short Abstract Submission and Paper Registration Deadline: August 12, 2020, 4:59 PM Eastern Time
Full Paper Submission Deadline: August 19, 2020, 4:59 PM Eastern Time
Acceptance Notification: early October 2020
Proceedings (posted online): early January 2021
How to Participate
Authors must submit their papers electronically, in PDF format.
Submissions should begin with a title page containing the paper title, each author’s name, affiliation, and email address, and an abstract summarizing the contributions of the paper. There is no page limit. The paper should begin with a clear description of the algorithmic problem to be solved, a survey of prior work on the problem—including a candid assessment of prior work in terms of simplicity and elegance—and a discussion of the contributions of the paper. The body of the paper should be written for a general theoretical computer science audience, and substantiate the main claims of the paper with full proofs. The submission should be typeset using 11 point font, in a single-column format with ample spacing throughout and ample margins all around. The submissions ought to be visually easy to read.
Brevity is a hallmark of simplicity. Authors are specifically encouraged to submit short and simple papers. Final papers may not exceed fifteen (15) pages in double column format.
The program committee may designate one or more papers as SOSA Best Papers. All submissions will be considered.
(Does it still make sense to blog such announcements or is these days Twitter the only way to go about this? Asking for a friend 🙂 )
Prasad Raghavendra and Avishay Tal have organized a sequence of 6 lectures on some of the exciting recent advances in analysis of Boolean functions.
Lecture Series: Advances in Boolean Function Analysis
The Simons Institute is organizing a series of lectures on Advances in Boolean Function Analysis, that will highlight a few major developments in the area. The series will feature weekly two-hour lectures from July 15th to Aug 18th. The lectures aim to address both the broad context of the results and their technical details. Though closely related in theme, each lecture will be self-contained. The schedule is attached below (more info at link).
Talks take place on Wednesdays at 10am Pacific time (1pm Eastern). If you can’t catch them live, they will be redcorded.
Zoom Link: https://berkeley.zoom.us/j/93086371156
Talk Schedule:
July 15, Wednesday 10:00am PDT (1pm EDT) Dor Minzer (Institute of Advanced Study)On the Fourier-Entropy Influence Conjecture
July 22, Wednesday, 10:00am PDT (1pm EDT) Hao Huang (Emory University) & Avishay Tal (UC Berkeley)Sensitivity Conjecture and Its Applications
August 3rd, Monday, 10:00am PDT (1pm EDT) Shachar Lovett (UC San Diego)Improved Bounds for the Sunflower Lemma
August 5, Wednesday, 10:00am PDT (1pm EDT) Ronen Eldan (Weizmann Institute)Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis
August 12, Wednesday, 10:00am Esty Kelman (Tel Aviv University) KKL via Random Restrictions
August 18, Tuesday, 10:00am Pooya Hatami (Ohio State University)Pseudorandom Generators from Polarizing Random Walks
TCS book: Call for GitHub issues
I originally planned this summer to finish the work on my Introduction to Theoretical Computer Science book, and in particular write the two missing chapters on space complexity and interactive proof systems. Needless to say, this summer did not go as planned and I won’t be able to write these chapters. However, I still intend to go over the existing chapters, fixing typos, adding examples, exercises, and generally making it friendlier to beginning undergraduate students.
Toward this end, I would be grateful for people posting bugs, typos, and suggestions as GitHub issues (I currently have 267 closed and 14 open issues which I hope to get to soon). Of course, if you are technically inclined and there’s a simple local fix, you can also make a pull request.
Aside from these fixes, I am making two more “global” changes to the book. First, I am adding a “non mathy overview” for each chapter. While some students got a lot from reading the book prior to lectures, others were intimidated by the mathematical notation, and so I hope this more gentle introduction will be helpful. I am also adding more examples & solved exercises toward this end.
Another change is that I now follow the more traditional way of presenting deterministic finite automata before Turing machines – DFAs are still optional and can be skipped without missing anything, but some instructors find them as a good introduction to Turing Machines. Thus the order of presentation of materials in the book is roughly as follows:
- Introduction, representing objects as strings – Representing numbers, lists, etc. Specifying computational tasks as functions mapping binary strings to binary strings, Cantor’s theorem.
- Finite functions and Boolean circuits – Every function can be computed by some circuit, circuits as straightline programs, representing circuits as strings, universal circuit evaluator, counting lower bound.
- Computing on unbounded inputs – DFAs (optional), Turing Machines, equivalence between Turing machines, RAM machines and programming languages, λ calculus (optional), cellular automata (optional)
- Uncomputability – Universal Turing machine, Halting problem, reductions, Rice’s Theorem. Optional: Gödel’s incompleteness theorem, uncomputability of quantified arithmetic statements, context free grammars.
- Efficient computation – Modeling running time, time hierarchy theorem, P and EXP
- NP and NP completeness – Polynomial-time reductions, Cook-Levin Theorem (using circuits), definition of NP using “proof system”/”verifying algorithms” (no non-deterministic TMs), NP completeness, consequences of P=NP: search to decision, optimal machine learning, etc..
- Randomized computation: Worst-case randomized computation, defining BPP, Sipser-Gács, does BPP=P? (a little on derandomization)
- Cryptography: One time pad, necessity of long keys for information theoretic crypto, pseudorandom generators and stream ciphers, taste of public key and “magic” (ZKP, FHE, MPC)
- Quantum computing: Some quantum mechanics background – double slit experiment, Bell’s inequality. Modeling quantum computation. Bird’s eye view of Shor’s algorithm and quantum Fourier transform.
Crowdsourcing Masters program
Going directly from undergraduate to Ph.D can be a good idea for many students interested in research, but it’s not the only route or the best choice for everyone.
As I wrote before, for students that discovered their interest in theoretical CS late in their undergrad, or perhaps after they graduated, a research Masters, can be a great option. This is particularly the case if the program is funded (i.e., students get a stipend and don’t need to pay tuition). Such programs are not common in the U.S., but there are some excellent choices around the world.
Since (as far as I know) there is no single source listing such programs, I thought a crowdsourced Google spreadsheet might be useful and so created one here: http://tiny.cc/tcsmasters
If you know of more places, please fill out this form: https://forms.gle/qfnbEZYYYDtFCDpx9
STOC 2020 slack channel open (from Madhur Tulsiani)
Madhur writes:
Thanks to all who participated in STOC 2020! Since the discussions on some of the topics from the business meeting, on SafeToC, and on the papers/workshops are still ongoing, we will keep the Slack workspace open till July 31st (instead of just one week after the conference, as announced earlier). Also, if any members of the community are interested in joining the discussions, they are welcome to email us (stoc2020@ttic.edu) and we can send them an invitation to join the workspace.
Of course the organizers may not always be able to quickly respond to help messages during the next month. However, all members are welcome to participate in discussions, create new topics or channels as needed, and use the workspace as they prefer.
TheoryFest organization team (stoc2020@ttic.edu)
STOC 2020 information (guest post by Madhur Tulsiani)
Dear fellow theorists,
As you already know, STOC 2020 this year will be a virtual conference. If you are interested in attending the conference, but haven’t registered yet, please do so soon (students: $25, regular: $50). This will help us ensure we have capacity for various online events.
Upon registration, you should receive a confirmation email from CVENT, also containing access information for various conference events. Also, if you are a student looking to register for STOC but the cost is a burden, please email us at stoc2020@ttic.edu.
How will the conference work?
- Videos: The videos for all conference talks are now available on YouTube, and can be accessed through the links in the conference program. Registration is not required to view the talks on Youtube.
- Slack: The conference has a Slack workspace, with one channel for every paper and workshop, and additional channels for information, announcements, social events, help, etc. The invitations for the Slack workspace will be sent to registered participants. Authors are also encouraged to monitor the channels for their papers. All access information for the conference will also be available here. The workspace is currently active, and will remain active for at least one week after the conference.
- Zoom sessions: The conference will feature Zoom sessions with short presentations by the speakers. The total time for each paper is 10 minutes. Given that participants have access to the full talks by the speakers on Youtube, these can be thought of as being analogues of poster sessions. The workshops will also be held as separate sessions. The links for the Zoom sessions are available via information in the registration confirmation email.
- Social events: The conference will include junior/senior “lunches”, breakout tables for impromptu and scheduled hangouts, and a group event using gather.town. The timings for the events can be found in the conference program. Sign-up links for various events will be sent to all registered participants – please do sign-up soon!
See you all at (virtual) STOC 2020. Please do let us know if you have any questions or suggestions.
TheoryFest organization team
TCS visioning workshop
[From Jelani Nelson and David Woodruff. This workshop can be very important to ensure TCS is represented in what is likely to be a difficult funding environment in coming years. –Boaz ]
The CATCS will be hosting a virtual “Visioning Workshop” the week of July 20 in order to identify broad research themes within theoretical computer science (TCS) that have potential for a major impact in the future. The goals are similar to the workshop of the same name in 2008: to package these themes in a way that can be consumed by the general public, which we would deliver primarily to the Computing Community Consortium and others (e.g. funding agencies) to help them advocate for TCS.
While participation in the workshop is primarily through invitation, we have a few slots available for the broader community. If you are interested in participating, please see details of the application process below. The workshop will be organized according to area-wise breakout groups. Each breakout group will have 1-2 leads. Breakout groups will meet for 4-5 hours spread across several days and will be tasked with brainstorming ideas and preparing materials related to their topic. Leads are further expected to participate in plenary sessions held on Monday July 20 and Friday July 24 (4-5 hrs of additional time) where these materials will be discussed.
If you are interested in participating in the workshop, please fill out this Google form by Monday June 15 ( https://forms.gle/cdCTsLfUs56CDhKS9 ). On this form, applicants are asked to contribute one or two major results in the last 10 years whose significance can be explained in layperson terms, and one or two major challenges for theory whose significance can be explained in layperson terms. [The results need not and generally will not be your own. They just should be easy-to-explain major results in your research area–Boaz] These descriptions can be very brief. We will just use them to select participants and create breakout groups.
