IIT Bombay is organizing an online Monotonicity Festival which is dedicated to understanding the impressive progress over the last couple of decades in Testing Boolean Monotonicity over various partially ordered domains (most notably, the Boolean Hypercube and the Hypergrid). Five of the lectures in this ongoing festival (with six planned lectures in total) have already taken place. Tomorrow is the last lecture where (PTReview’s own) Seshadhri will shed some light on the Directed Talagrand Inequality central to the analysis of the Monotonicity tester presented in the seminal work of Khot-Minzer-Safra.

The talk will begin at 10:30 AM India time tomorrow (April 30, 2024). Here is the zoom link: https://us06web.zoom.us/j/85365027303?pwd=hreOInC1dMwdFYnTOVa0nblSs9kDz6.1

Also, here is the link for all the YouTube playlist where we will upload all the talks: https://www.youtube.com/playlist?list=PLuoJqx7PPeVKzhTgFbMQH1zvF40yClpES

Thanks to Hadley Black, Deeparnab Chakrabarty and C. Seshadhri for kindly agreeing to give the talk.

The 8th edition of WoLA, the Workshop on Local Algorithms, will be taking place on August 5-7, 2024 at the Simons Institute, as part of the Simons Institute’ summer program on Sublinear Algorithms.

Now, what is WoLA, some of you may ask?
“Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in large networks and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities.”

Save the date — the workshop has consistently been a great event for the local algorithms community to meet and discuss, and everyone is welcome to attend! (Registration is free)

The schedule is still being finalized, but here are some salient points:

• on the first day, a celebration of Dana Ron‘s work and far-reaching influence, at the occasion of her 60th birthday
• an open problem session for people to propose and discuss open questions and directions in local algorithms
• Senior-junior lunches, and lightning talks (“graduating bits”) for graduating or soon-to-be-graduating students and postdocs
• contributed short talks and a poster session

Importantly, there will also be another event (independent of WoLA, but very much related) on August 8 at the Simons Institute: a one-day birthday celebration for Ronitt Rubinfeld, “RR@60”, organized by Arnab Bhattacharyya, Funda Ergun, Krzysztof Onak, and Ravi Kumar. So plan on attending both!

To register your interest in attending WoLA (optional: for planning purposes), please fill the Simons Institute form on the right side here (or, alternatively, the form below). If you’d like to present your work, as a short contributed talk and/or a poster, or would like to take part in the “graduating bits” session, please express your interest by filling this form by ⏰ May 3, 5pm ET. Notifications will be sent by May 15.

If you have any questions about WoLA, or need an invitation letter to attend (for visa reasons), please indicate it in the form.

Update (25/04): updated the post to include the link to the Simons Institute registration form.

Clément Canonne, on behalf of the WoLA PC (Talya Eden, Manuela Fischer, Michael Kapralov, Robi Krauthgamer, Reut Levi, Rotem Oshman, Michal Parnas, Ron Rothblum, and Jara Uitto)

Exciting news!* Next year, the Simons Institute will host a summer program on Sublinear Algorithms. from May 20 to August 9, 2024. Organised by Artur Czumaj, Piotr Indyk, Jelani Nelson, Noga Ron-Zewi, Ronitt Rubinfeld, Asaf Shapira and myself, the summer program will feature 4 workshops:

• the bootcamp (May 21 to 24)
• Extroverted Sublinear Algorithms (June 17 to 21)
• Sublinear Graph Simplification (July 29 to August 2)
• the Workshop on Local Algorithms (WoLA) (August 5 to 7)

This is, of course, in addition to the bulk of the program itself: research discussions, reading groups, talks, social activities… If you happen to be in the area, you’re more than welcome to come and take part in some of these!

While each workshop will have its own set of attendees (more details soon), there are also some slots for (1) long-term visitors and (2) Simons Research Fellows (within five years of the award of their PhD at the start of academic year 2024-25, may already hold faculty positions) you can apply to! The deadline to apply is December 1, 2023:

• Application for Long-Term Visitor
• Application for Simons Research Fellow

Hope to see many of you next summer! Oh, and to conclude… have you seen our logo?

* Full disclosure: I am biased, being an organizer, but do find that very exciting.

Good news, everyone! WOLA, the Workshop on Local Algorithms, is coming back this year, with WOLA 2022 taking place in person* in Warsaw on June 25–27. Exciting speakers, events and outings are being planned!

Keep track of updates by visiting the website, and register at https://ideas-ncbr.pl/en/wola/registration/ (even if you intend to attend remotely).

* Virtual participation is also possible.

Ainesh Bakshi, Rajesh Jayaram, and Samson Zhou are organizing a 3-day Workshop on Algorithms for Large Data (nicely abbreviated as WALD(O), the O standing for Online), featuring many talks which should be of interest to the readers of this blog, as well as an open problems and a poster sessions, and a junior/senior lunch. As the organizers describe it:

This workshop aims to foster collaborations between researchers across multiple disciplines through a set of central questions and techniques for algorithm design for large data. We will focus on topics such as sublinear algorithms, randomized numerical linear algebra, streaming and sketching, and learning and testing.

The workshop will take place on August 23 — August 25 (ET). Attendance is free, but registration is required by August 20th. More details at https://waldo2021.github.io/

The fifth WOLA (Workshop on Local Algorithms) will be virtual, and take place June 14-15. Registration is free, but required: please fill this form by June 10th to attend.

Local algorithms — that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input — have been studied in a number of areas in theoretical computer science and mathematics. Some of the related areas include sublinear-time algorithms, distributed algorithms, streaming algorithms, (massively) parallel algorithms, inference in large networks, and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities.

This year, the workshop will include:

• A poster session: Please submit your poster proposal (title and abstract) at by May 26th. Everyone is invited to contribute. This session will take place on gather.town.
• Invited long talks: the tentative schedule is available, and features talks by James Aspnes, Jelani Nelson, Elaine Shi, Christian Sohler, Uri Stemmer, and Mary Wootters.
• Junior-Senior social meetings
• An AMA (Ask Me Anything) session, moderated by Merav Parter
• A Slack channel
• An Open Problems session

The Program Committee of WOLA 2021 is comprised of:

• Venkatesan Guruswami (CMU)
• Elchanan Mossel (MIT)
• Merav Parter (Weizmann Institute of Science)
• Sofya Raskhodnikova (chair) (Boston University)
• Gregory Valiant (Stanford)

and the organizing committee:

• Sebastian Brandt (ETH)
• Yannic Maus (Technion)
• Slobodan Mitrović (MIT)

For more detail, see the website; to stay up to date with the latest announcements concerning WOLA, join our mailing list!

While we at PTReview always look through the posted papers, we do not check for correctness. We make a serious attempt to make sure the paper is reasonable. In a few instances, we have decided not to post a (topically relevant) paper, because it looks absolutely wrong. Our position is: the benefit of doubt goes to the author, and a borderline paper should be posted. We are only curating relevant tech reports, not passing judgment on results.

In some borderline cases, readers familiar with the subject complained to us that the paper should be not be considered a scientific contribution (because of, say, unspecified algorithms, blatantly incorrect or unverifiable central claims). These are cases where we were also unsure of the paper. We have usually removed/not posted such papers.

If the paper author(s) feels that his/her paper should nonetheless be posted, then they should email us at little.oh.of.n@gmail.com. As long as the paper is not complete nonsense and appears to cite relevant history, we will defer to the authors’ wishes.

As it may have transpired by now, FOCS 2017 (a.k.a. the 58^th Annual Symposium on Foundations of Computer Science) is around the corner.

I am not going to go into the details of the talks on or related to property testing at the conference itself,\({}^{(\ast)}\) but instead focus on (one of) the workshops.

This FOCS will include 3 workshops,\({}^{(\dagger)}\) on Saturday 14^th (gird your loins — they last the full day!):

• Linear Sketching as a Tool for Everything
• Frontiers in Distribution Testing
• Hardness Escalation in Communication Complexity and Query Complexity

The second,  Frontiers in Distribution Testing, is specifically about recent advances, new questions, and novel directions in property testing of distributions. Co-organized by Gautam Kamath and me, its official objective is to “catch the community up in recent developments, and highlight some of the most interesting frontiers in distribution testing.”

It’ll feature a stellar lineup of speakers\({}^{(\ddagger)}\) (namely, Ilias Diakonikolas, Jiantao Jiao, Alon Orlitsky, Constantinos Daskalakis, Ryan O’Donnell, Ronitt Rubinfeld, and Tom Gur), as well as an open problem session — and, very possibly, pictures of eggs. The program is available, with all relevant details, on the workshop webpage.

If you are around next Saturday, consider attending — and submit your favorite open problems!

\({}^{(\ast)}\) Hint: look at Sessions 7A and 10B.
\({}^{(\dagger)}\) Thanks to the FOCS workshop chairs James Lee and Aleksander Mądry.
\({}^{(\ddagger)}\) A lineup of stellar speakers.