Sign in

Aviad Rubinstein

@aviad-rubinstein.bsky.social
236 followers 87 following 26 posts

Algorithms for Toddlers (youtu.be/nnLOi3ia210) | Algorithms for Teenagers (tinyurl.com/2cnp39cf) | Algorithms for Grown Ups (dblp.org/pid/11/10308)

PostsRepliesMedia
Aviad Rubinstein @aviad-rubinstein.bsky.social · 02/10/2026
The new call for Motwani postdocs application is now open! tinyurl.com/4r7etua2 BTW- Not quite ready for a postdoc? We updated the TCS Masters programs spreadsheet: tinyurl.com/493rxwkx Any career stage and in the (SF) Bay Area? Save the date for TOCA-SV on 11/6/2026!
064
Reposted by Aviad Rubinstein
ACM SIGecom @acmsigecom.bsky.social · 30/09/2026
The SIGecom Job Market Candidates initiative is back for 2026-27! A great resource both for junior researchers looking for academic positions and for those looking to hire from the EconCS community. Candidates: submit this form by Oct 7; LaTeX due Oct 12.
forms.gle
SIGecom Job Candidates 2026-2027
Just like in the last 11 years, this year there will be an article in SIGecom Exchanges profiling the current junior job market candidates from the SIGecom community. These profiles will include a res...
023
Reposted by Aviad Rubinstein
Clément Canonne @ccanonne.github.io · 29/09/2026
A very important message from Omer Reingold to our TCS community, especially us (arg, already) senior researchers: "snap out of it." Please, digest, and share. theorydish.blog/2026/09/29/s...
As for depression: the next time you have the urge to lament, or even celebrate, being “the last generation of human mathematicians,” perhaps keep it to yourself. Contemplating the end of your profession from the relative comfort of an established, tenured career is a privilege, and it comes with responsibilities. Senior academics are not merely individual researchers; we are stewards of our field, and we owe our junior colleagues active leadership rather than abandonment.
47321
Reposted by Aviad Rubinstein
arxiv cs.DS @arxiv-cs-ds.bsky.social · 28/09/2026
Zhiyi Huang Settling the Matroid Secretary Problem arxiv.org/abs/2609.30421
052
Reposted by Aviad Rubinstein
Lance Fortnow @lance.fortnow.com · 26/09/2026
In my 1989 thesis I asked if there was an oracle separating IP from MIP. That was before we knew that MIP=NEXP, though that result doesn't relativize. Bouland, Huang, Natarajan, Shalit, Tal and Astra now answer the original question.
arxiv.org
$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize
We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson...
0111
Aviad Rubinstein @aviad-rubinstein.bsky.social · 25/09/2026
Some teaching applied more stuff adapt by encouraging students to use LLMs and raising expectations from course projects. For mathier classes like undergrad algorithms, I mostly rely more heavily on in-person exams :-/ Alternatives? What should a theory class project with LLM look like?
261
Aviad Rubinstein @aviad-rubinstein.bsky.social · 22/09/2026
This book finally arrived 🤩 It's been a huge privilege to consult for the "How to Design an Algorithm?" chapter. Thank you @whatonearth.bsky.social for the opportunity! For those of you with children in your life (who are too old for our Algorithms-for-Toddlers), I think the book is excellent.
161
Reposted by Aviad Rubinstein
Clément Canonne @ccanonne.github.io · 17/09/2026
The Call for Papers for #STOC2027 is up! Importantly, the PC "will place substantial weight on the quality of exposition, and clarity of technical arguments and proofs" Also: - Public posting requirement - Required video submission and more. Deadline: ⏰ Nov 2, AoE acm-stoc.org/stoc2027/sto...
Policy experiments for STOC 2027: In light of rapid advances in generative AI and their impact on research and scientific communication, STOC 2027 is experimenting with several new policies intended to encourage high-quality submissions and promote clear and effective communication of research. The policies below include mandatory public posting and mandatory video submission. Detailed instructions for these two requirements will be released closer to the paper submission deadline.
44014
Reposted by Aviad Rubinstein
arxiv cs.DS @arxiv-cs-ds.bsky.social · 15/09/2026
Sahil Singla The Matroid Secretary Conjecture is True arxiv.org/abs/2609.14555
062
Reposted by Aviad Rubinstein
Aaron Roth @aaroth.bsky.social · 15/09/2026
A world without open problems Here are some that fell today: K-server: arxiv.org/abs/2609.15979 Matroid Secretary: arxiv.org/abs/2609.145... Matrix Spencer: arxiv.org/abs/2609.15025 (Well Matrix Spencer was maybe also a few weeks ago, but who's counting? arxiv.org/abs/2608.28816 )
arxiv.org
The $k$-server conjecture is true
The $k$-server conjecture states that a deterministic online algorithm can achieve competitive ratio $k$ on every metric space. We prove the conjecture. Specifically, we show that the work function al...
3316
Reposted by Aviad Rubinstein
Clément Canonne @ccanonne.github.io · 14/09/2026
Big (huge?) news on the computational complexity preprint server, with a paper by Yumou Fei, Dor Minzer, and Shuo Wang I am not qualified to read beyond the intro: the perfect completeness version of the (not) Unique Games Conjecture, the 4-to-1 Games conjecture! eccc.weizmann.ac.il/report/2026/...
eccc.weizmann.ac.il
ECCC - TR26-179
2459
Reposted by Aviad Rubinstein
𝖬𝖺𝗁𝖽𝗂 𝖢𝗁𝖾𝗋𝖺𝗀𝗁𝖼𝗁𝗂 @mahdi.ch · 04/09/2026
THE MOST important open question in list decoding of error-correcting codes, whether explicit Reed-Solomon codes are list decodable beyond Guruswami-Sudan's famous breakthrough is now resolved! Congrats to the team, including my amazing student Yeyuan Chen. #Proud eccc.weizmann.ac.il/report/2026/...
0121
Reposted by Aviad Rubinstein
Paul Goldberg @paulwgoldberg.bsky.social · 27/08/2026
stumbled across this fun example of impressive research productivity economistwritingeveryday.com/2026/08/26/n...
But I just discovered an economist that is, apparently, even more productive than Acemoglu, at least as measured by working papers. Nicholas Polson has, by my count using his SSRN page, already written 258 working papers in 2026 alone. He’s already written (or at least published to SSRN), six papers today, August 26, 2026. In the month of August 2026, he has written and posted to SSRN a total of 104 papers — and counting, since the month isn’t quite over.

These aren’t just short notes. Most of the papers are of normal academic length: 32 pages, 27 pages, 58 pages. The papers are both theoretical — involving complex math in some cases — or empirical, with regressions.
011
Reposted by Aviad Rubinstein
Kira Goldner @kiragoldner.bsky.social · 25/08/2026
"ChatGPT for Academic Researchers" to 100k faculty at mostly just R1/top American schools yet so far I've only heard of people being waitlisted -- so who actually got this? Very curious.
151
Reposted by Aviad Rubinstein
Lance Fortnow @lance.fortnow.com · 23/08/2026
Sad news from Hervé Moulin, the ousted editor of Games and Economic Behavior, a journal focused on game theory that had a long history of collaboration with the computing community. Elsevier "strategic priorities" guts yet another good journal. gametheorysociety.or...
271
Reposted by Aviad Rubinstein
Clément Canonne @ccanonne.github.io · 11/08/2026
So... does the inequality holds for arbitrary (not just product) distributions with square Hellinger? ALMOST! 🤯 This is surprisingly non-trivial, and this is surprisingly true, and this is due to T.S. Jayram (2009): it's true, if you put a weird constant in front of the RHS! 5/
Chain Rule-Type Inequality for Squared Hellinger, similar to the KL one but with a constant 3.46 in front of the RHS.
1173
Reposted by Aviad Rubinstein
Robin Kothari @robinkothari.bsky.social · 22/07/2026
Frontier LLMs can now solve many quantum computing and theoretical computer science problems that I've personally spent weeks or months working on. How is everyone else dealing with the existential crisis that accompanies this reality?
5194
Reposted by Aviad Rubinstein
FOCS 2026 @focs2026.bsky.social · 17/06/2026
The call for workshop proposals at #FOCS2026 is up! focs.computer.org/2026/call-fo... Submission deadline: ⏰ July 31
focs.computer.org
Call for workshops – FOCS 2026
066
Reposted by Aviad Rubinstein
Clément Canonne @ccanonne.github.io · 15/05/2026
Nominate "Rising Star" speakers at the TCS for All Spotlight Workshop at #STOC2026! Nominees must be senior PhD students or postdocs in TCS. (Preference will be given to speakers on the job market for postdoc/faculty positions.) Apply by ⏰ May 22 (11:59 pm PDT): docs.google.com/forms/d/e/1F...
docs.google.com
STOC2026-TCS for All Spotlight Workshop Nomination
063
Reposted by Aviad Rubinstein
Kate Donahue @kpaxdonahue.bsky.social · 29/04/2026
CFP: Workshop on Game Theory and Mechanism Design with Large Language Models @ EC '26 We invite working papers on the economics of LLM agents — algorithmic collusion, information design, delegation, mechanism & benchmark design, and more. Deadline: May 29 Details: llm-incentives.com
0114
Reposted by Aviad Rubinstein
Kira Goldner @kiragoldner.bsky.social · 20/04/2026
Submission deadline is May 4, 2026. Full Call for Papers available on our website. Submit your "right way to do it" results! Co-organized with @divyarthi.bsky.social and Taylor Lundy.
tlundy832.github.io
Easy Peasy at EC'26 — Rome, July 2026
Easy Peasy at EC'26 — a workshop on elegant, teachable proofs and results in Economics & Computation, held at EC'26 in Rome, July 2026.
153
Reposted by Aviad Rubinstein
Alex Teytelboym @t8el.bsky.social · 27/04/2026
Just a few days left to nomi for Highlights beyond EC! Simply fill out a short form: forms.gle/MF428Z2qsLDo... The amazing Highlights Beyond EC Committee for EC'26 is: Elliot Lipnowski, Vahideh Manshadi, and Alex Psomas Deadline: April 30, 2026. See you all in Rome! @acmsigecom.bsky.social 🇮🇹🍕🍝
forms.gle
012
Reposted by Aviad Rubinstein
European Association for Theoretical Computer Science @eatcs.bsky.social · 27/04/2026
The 2026 Presburger Award for Young Scientists goes to Vincent Cohen-Addad and @gautamkamath.com 🥳🎉 You can read the laudatio here:
eatcs.org
Presburger Award 2026 – Laudatio
European Association for Theoretical Computer Science
1256
Reposted by Aviad Rubinstein
Clément Canonne @ccanonne.github.io · 26/04/2026
An aperiodic reminder: there's no reason or justification to try to obfuscate your email on your academic website. None. Don't do it. Stop. "You can contact me at <first initial> dot <solve a wordle> at blah dot edu"? Spammers will easily do it. But other academics, journal editors? We'll give up.
4468
Reposted by Aviad Rubinstein
ACM SIGecom @acmsigecom.bsky.social · 15/04/2026
📢 Announcing the 2025 SIGecom Doctoral Dissertation Awardees! 🏆 Winner: Noah Golowich (MIT), advised by Constantinos Daskalakis and Ankur Moitra, for the thesis: "Theoretical Foundations for Learning in Games and Dynamic Environments"
152
Reposted by Aviad Rubinstein
ACM SIGecom @acmsigecom.bsky.social · 16/04/2026
📢 Announcing the 2026 SIGecom Mid-Career Awardee: Matt Weinberg, awarded for his contributions to algorithmic mechanism design, including auctions, blockchains, and stopping theory. Congrats! Thank you to the Selection Committee: Tuomas Sandholm (chair), Ilya Segal, and @timroughgarden.bsky.social!
071
Reposted by Aviad Rubinstein
ACM SIGecom @acmsigecom.bsky.social · 15/04/2026
🏅 Runners-up: - Xizhi Tan (Drexel), advised by @gkatzelis.bsky.social, for: "Learning-augmented mechanism design" - @yifanwu.bsky.social (Northwestern), advised by @jasonhartline.bsky.social, for: "Trustworthy AI: Foundations from Proper Scoring Rules"
185
Reposted by Aviad Rubinstein
Clément Canonne @ccanonne.github.io · 15/03/2026
Since SIGACT is on X but not BlueSky,* advertising the SIGACT Distinguished Service Award here, "given annually to an individual or group who has made substantial service contributions to the Theoretical CS community" #TCSSky ⏰ Nominate by April 30! sigact.org/prizes/servi... *I know. Ugh.
sigact.org
ACM SIGACT - SIGACT Distinguished Service Award
1137
Aviad Rubinstein @aviad-rubinstein.bsky.social · 03/03/2026
This is a really cool paper: arxiv.org/abs/2602.04665 (Posted on arXiv a month ago, but I was so amazed by the techniques that it took me a month of reading it back and forth to post here.) I have been thinking about this problem since Yair Carmon and John Duchi told me about it in 2019.
arxiv.org
The Complexity of Min-Max Optimization with Product Constraints
We study the computational complexity of the problem of computing local min-max equilibria of games with a nonconvex-nonconcave utility function $f$. From the work of Daskalakis, Skoulakis, and Zampet...
270
Aviad Rubinstein @aviad-rubinstein.bsky.social · 19/01/2026
Apps like Family Link are far from perfect but give me some level of control over my kids' screentime. But major GenAI models don't want to mess with the responsibility of releasing kids versions, so I have to give my kids access to my account. I wonder what could possibly go wrong 🤔
000
Reposted by Aviad Rubinstein
benjamin dickman @benjamindickman.bsky.social · 25/12/2025
There is a job posting for a mathematics staff writer at @quantamagazine.bsky.social: simonsfoundation.wd1.myworkdayjobs.com/en-US/simons... Maybe this is good for you or somebody you know! #MathSky 🧮 #iTeachMath ♾️
simonsfoundation.wd1.myworkdayjobs.com
Staff Writer (Mathematics), Quanta Magazine
POSITION SUMMARY Quanta Magazine is seeking a first-rate reporter and writer to identify and cover newsworthy developments in mathematics. The ideal candidate will have tireless appetite for exploring...
03216
Aviad Rubinstein @aviad-rubinstein.bsky.social · 23/10/2025
🤩 Excited to officially announce our upcoming local Theory-CS conference "TOCA-SV" (11/7 at Stanford): sites.google.com/cs.stanford....
sites.google.com
Sign in - Google Accounts
010
Reposted by Aviad Rubinstein
Robin Kothari @robinkothari.bsky.social · 15/10/2025
Are you a PhD student in quantum computing and interested in working with our team in 2026 as a student researcher (i.e., an internship that's ~3 months and in-person at our office)? If so, apply here: www.google.com/about/career...
google.com
Student Researcher, PhD, Winter/Summer 2026 — Google Careers
0132
Aviad Rubinstein @aviad-rubinstein.bsky.social · 13/10/2025
The new call for Motwani postdocs application is now open! academicjobsonline.org/ajo/jobs/30865 BTW- Not quite ready for a postdoc? We updated the TCS Masters programs spreadsheet: www.cs.princeton.edu/~smattw/mast... Any career stage and in the (SF) Bay Area? Save the date for TOCA-SV on 11/7!
academicjobsonline.org
Stanford University, Computer Science/Theory Lab/Stanford University
Job #AJO30865, Postdoc in Theoretical Computer Science at Stanford, Computer Science/Theory Lab/Stanford University, Stanford University, Stanford, California, US
0148
Reposted by Aviad Rubinstein
Vasilis Gkatzelis @gkatzelis.bsky.social · 30/09/2025
It is that time of year again to gather all the profiles of SIGecom job market candidates! Share this with any job market candidate at the intersection of Econ, CS, and OR that you may know. Candidates should complete the submission form (docs.google.com/forms/d/e/1F...) by October 7th, 2025.
docs.google.com
SIGecom Job Candidates 2025-2026
Just like in the last 10 years, this year there will be an article in SIGecom Exchanges profiling the current junior job market candidates from the SIGecom community. These profiles will include a res...
084
Reposted by Aviad Rubinstein
Al Roth @alroth.bsky.social · 17/09/2025
Market design is growing fast… #econsky marketdesigner.blogspot.com/2025/09/rece...
marketdesigner.blogspot.com
Recent good looking market design papers I hope to read (on auctions, unraveling, and interviews)
I'll post market design related news and items about repugnant markets. See also my Stanford profile. I have a general-interest book on market design: Who Gets What--and Why The subtitle is "The new economics of matchmaking and market design."
081
Aviad Rubinstein @aviad-rubinstein.bsky.social · 19/09/2025
The otter on this small sticker is still trying to understand our algorithm (w/ Alexandros Hollender) for cake cutting with 4 agents arxiv.org/abs/2311.02075. Sticker design credit: Eva Tardos.
140
Reposted by Aviad Rubinstein
NeurIPS Conference @neuripsconf.bsky.social · 02/07/2025
NeurIPS is seeking additional ethics reviewers this year. If you are able and willing to participate in the review process, please sign up at the form in the link: neurips.cc/Conferences/... Please share this call with your colleagues!
neurips.cc
2025 Call For Ethics Reviewers
If you are able and willing to participate in the review process, please sign up at this form. Feel free to share this call with your colleagues.
0118
Reposted by Aviad Rubinstein
Natalie Collina @ncollina.bsky.social · 03/07/2025
This best paper news is a good opportunity to highlight that a month or so ago I started maintaining CV of failures on my website. It will almost certainly continue to grow linearly in the number of things I attempt to do, and that’s a good thing! www.seas.upenn.edu/~ncollina/Fa...
seas.upenn.edu
0141
Reposted by Aviad Rubinstein
ACM SIGecom @acmsigecom.bsky.social · 02/07/2025
See everyone at #ACMEC25 on Monday, July 7! And while you're there, join us July 8, 8-10pm in Stanford Econ Landau 139 for a Wikipedia edit-a-thon! Feel free to contribute to the crowdsourced list of topics that need attention: docs.google.com/spreadsheets...
sites.google.com
Edit-a-thon
Let's get together and create or edit Wikipedia pages for EconCS entries. Both new and experienced Wiki editors are welcome!
062
Reposted by Aviad Rubinstein
Divyarthi Mohan @divyarthi.bsky.social · 02/07/2025
Sign up here to let us know you are interested: docs.google.com/forms/d/e/1F...
docs.google.com
Wikipedia edit-a-thon @ EC'25
Please fill out the following information to help us plan the event. Please note: participants are asked to bring their own laptop or other device. Power outlets and snacks will be provided. Suggest ...
161
Reposted by Aviad Rubinstein
Divyarthi Mohan @divyarthi.bsky.social · 02/07/2025
Join us for a Wikipedia edit-a-thon at #ACMEC25! When: July 8th, 8PM-10PM Where: Stanford Econ Landau 139 Website: sites.google.com/view/econcs-... Come hangout, grab snacks, and edit/create Wikipedia pages for EC topics. Suggest topics/articles that need attention: docs.google.com/spreadsheets...
1123
Reposted by Aviad Rubinstein
Gautam Kamath @gautamkamath.com · 30/06/2025
ICML's election for their board of directors has begun. I've thrown my hat in the ring. Please consider voting for Gautam Kamath. I have experience with the governance of TMLR, COLT, and ALT, and I think I've demonstrated myself as a consciencious and engaged community member.
0295
Aviad Rubinstein @aviad-rubinstein.bsky.social · 26/06/2025
Finally, a NYT word-of-the-day that I recognize ;) www.nytimes.com/2025/06/26/l...
nytimes.com
Word of the Day: spectral
040
Aviad Rubinstein @aviad-rubinstein.bsky.social · 15/05/2025
www.linkedin.com/feed/update/...
linkedin.com
Congratulations to Xiao Mao, a CS PhD student and advisee of Aviad… | Stanford University Department of Computer Science
Congratulations to Xiao Mao, a CS PhD student and advisee of Aviad Rubinstein. He co-authored a paper titled &quot;Breaking the Sorting Barrier for Directed Single-Source Shortest Paths,&quot; which w...
080
Reposted by Aviad Rubinstein
Steven Strogatz @stevenstrogatz.com · 03/04/2025
Today I stumbled across a book called Algorithms for Toddlers. Perfect for kids -- or your own inner toddler! www.youtube.com/watch?v=nnLO...
youtube.com
Algorithms For Toddlers!
YouTube video by Mary Wootters
1536
Reposted by Aviad Rubinstein
Thomas Steinke @stein.ke · 03/03/2025
Alphanumeric citations [ABC00] strike the right balance between compactness & communication. Plain numeric citations [1] are compact, but convey no information. Author-year citations (Aaronson, Barrington, & Coppersmith, 2000) are too verbose, even if abbreviated (Aaronson et al. 2000).
6426
Reposted by Aviad Rubinstein
TCS+ @tcsplus.bsky.social · 27/02/2025
📢 To kick off 2025, our first TCS+ talk will be next Wednesday, March 5 (10amPT, 1pm ET, 19:00 CET): Prasanna Ramakrishnan (@pras17.bsky.social), from the Stanford, will tell "How to Appease a Voter Majority"! RSVP to receive the link (available one day prior to the talk): forms.gle/DDFtJKi2Xoj6...
forms.gle
TCS+ RSVP: Prasanna Ramakrishnan (2025/03/05)
Title: How to Appease a Voter Majority
163
Reposted by Aviad Rubinstein
Anupam Gupta @anupamg.bsky.social · 27/02/2025
#STOC2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals. The deadline is March 9th. Apply here: stoc2025theoryfest.netlify.app
stoc2025theoryfest.netlify.app
Vite + React + TS
097
Reposted by Aviad Rubinstein
Huck Bennett @huckbennett.bsky.social · 21/02/2025
This is terrible news, and part of the ongoing assault on science in the U.S. by the new administration. To honor Tracy Kimbrel and his service to the NSF's AF division, here's a short thread about a beautiful algorithm of his, joint with Rakesh Sinha (www.sciencedirect.com/science/arti...). 1/
sciencedirect.com
A probabilistic algorithm for verifying matrix products using O(n2) time and log2n + O(1) random bits
1116