Aviad Rubinstein @aviad-rubinstein.bsky.social · 02/10/2026The 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 RubinsteinACM SIGecom @acmsigecom.bsky.social · 30/09/2026The 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.gleSIGecom Job Candidates 2026-2027Just 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 RubinsteinClément Canonne @ccanonne.github.io · 29/09/2026A 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... 47321
Reposted by Aviad Rubinsteinarxiv cs.DS @arxiv-cs-ds.bsky.social · 28/09/2026Zhiyi Huang Settling the Matroid Secretary Problem arxiv.org/abs/2609.30421 052
Reposted by Aviad RubinsteinLance Fortnow @lance.fortnow.com · 26/09/2026In 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 RelativizeWe 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/2026Some 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/2026This 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 RubinsteinClément Canonne @ccanonne.github.io · 17/09/2026The 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... 44014
Reposted by Aviad Rubinsteinarxiv cs.DS @arxiv-cs-ds.bsky.social · 15/09/2026Sahil Singla The Matroid Secretary Conjecture is True arxiv.org/abs/2609.14555 062
Reposted by Aviad RubinsteinAaron Roth @aaroth.bsky.social · 15/09/2026A 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.orgThe $k$-server conjecture is trueThe $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 RubinsteinClément Canonne @ccanonne.github.io · 14/09/2026Big (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.ilECCC - TR26-179 2459
Reposted by Aviad Rubinstein𝖬𝖺𝗁𝖽𝗂 𝖢𝗁𝖾𝗋𝖺𝗀𝗁𝖼𝗁𝗂 @mahdi.ch · 04/09/2026THE 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 RubinsteinPaul Goldberg @paulwgoldberg.bsky.social · 27/08/2026stumbled across this fun example of impressive research productivity economistwritingeveryday.com/2026/08/26/n... 011
Reposted by Aviad RubinsteinKira 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 RubinsteinLance Fortnow @lance.fortnow.com · 23/08/2026Sad 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 RubinsteinClément Canonne @ccanonne.github.io · 11/08/2026So... 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/ 1173
Reposted by Aviad RubinsteinRobin Kothari @robinkothari.bsky.social · 22/07/2026Frontier 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 RubinsteinFOCS 2026 @focs2026.bsky.social · 17/06/2026The call for workshop proposals at #FOCS2026 is up! focs.computer.org/2026/call-fo... Submission deadline: ⏰ July 31focs.computer.orgCall for workshops – FOCS 2026 066
Reposted by Aviad RubinsteinClément Canonne @ccanonne.github.io · 15/05/2026Nominate "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.comSTOC2026-TCS for All Spotlight Workshop Nomination 063
Reposted by Aviad RubinsteinKate Donahue @kpaxdonahue.bsky.social · 29/04/2026CFP: 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 RubinsteinKira Goldner @kiragoldner.bsky.social · 20/04/2026Submission 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.ioEasy Peasy at EC'26 — Rome, July 2026Easy 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 RubinsteinAlex Teytelboym @t8el.bsky.social · 27/04/2026Just 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 RubinsteinEuropean Association for Theoretical Computer Science @eatcs.bsky.social · 27/04/2026The 2026 Presburger Award for Young Scientists goes to Vincent Cohen-Addad and @gautamkamath.com 🥳🎉 You can read the laudatio here:eatcs.orgPresburger Award 2026 – LaudatioEuropean Association for Theoretical Computer Science 1256
Reposted by Aviad RubinsteinClément Canonne @ccanonne.github.io · 26/04/2026An 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 RubinsteinACM 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 RubinsteinACM 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 RubinsteinACM 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 RubinsteinClément Canonne @ccanonne.github.io · 15/03/2026Since 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.orgACM SIGACT - SIGACT Distinguished Service Award 1137
Aviad Rubinstein @aviad-rubinstein.bsky.social · 03/03/2026This 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.orgThe Complexity of Min-Max Optimization with Product ConstraintsWe 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/2026Apps 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 Rubinsteinbenjamin dickman @benjamindickman.bsky.social · 25/12/2025There 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.comStaff Writer (Mathematics), Quanta MagazinePOSITION 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.comSign in - Google Accounts 010
Reposted by Aviad RubinsteinRobin Kothari @robinkothari.bsky.social · 15/10/2025Are 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.comStudent Researcher, PhD, Winter/Summer 2026 — Google Careers 0132
Aviad Rubinstein @aviad-rubinstein.bsky.social · 13/10/2025The 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.orgStanford 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 RubinsteinVasilis Gkatzelis @gkatzelis.bsky.social · 30/09/2025It 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.comSIGecom Job Candidates 2025-2026Just 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 RubinsteinAl Roth @alroth.bsky.social · 17/09/2025Market design is growing fast… #econsky marketdesigner.blogspot.com/2025/09/rece...marketdesigner.blogspot.comRecent 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/2025The 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 RubinsteinNeurIPS Conference @neuripsconf.bsky.social · 02/07/2025NeurIPS 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.cc2025 Call For Ethics ReviewersIf 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 RubinsteinNatalie Collina @ncollina.bsky.social · 03/07/2025This 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 RubinsteinACM SIGecom @acmsigecom.bsky.social · 02/07/2025See 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.comEdit-a-thonLet's get together and create or edit Wikipedia pages for EconCS entries. Both new and experienced Wiki editors are welcome! 062
Reposted by Aviad RubinsteinDivyarthi Mohan @divyarthi.bsky.social · 02/07/2025Sign up here to let us know you are interested: docs.google.com/forms/d/e/1F...docs.google.comWikipedia edit-a-thon @ EC'25Please 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 RubinsteinDivyarthi Mohan @divyarthi.bsky.social · 02/07/2025Join 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 RubinsteinGautam Kamath @gautamkamath.com · 30/06/2025ICML'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/2025Finally, a NYT word-of-the-day that I recognize ;) www.nytimes.com/2025/06/26/l...nytimes.comWord of the Day: spectral 040
Aviad Rubinstein @aviad-rubinstein.bsky.social · 15/05/2025www.linkedin.com/feed/update/...linkedin.comCongratulations to Xiao Mao, a CS PhD student and advisee of Aviad… | Stanford University Department of Computer ScienceCongratulations to Xiao Mao, a CS PhD student and advisee of Aviad Rubinstein. He co-authored a paper titled "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths," which w... 080
Reposted by Aviad RubinsteinSteven Strogatz @stevenstrogatz.com · 03/04/2025Today I stumbled across a book called Algorithms for Toddlers. Perfect for kids -- or your own inner toddler! www.youtube.com/watch?v=nnLO...youtube.comAlgorithms For Toddlers!YouTube video by Mary Wootters 1536
Reposted by Aviad RubinsteinThomas Steinke @stein.ke · 03/03/2025Alphanumeric 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 RubinsteinTCS+ @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.gleTCS+ RSVP: Prasanna Ramakrishnan (2025/03/05)Title: How to Appease a Voter Majority 163
Reposted by Aviad RubinsteinAnupam 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.appstoc2025theoryfest.netlify.appVite + React + TS 097
Reposted by Aviad RubinsteinHuck Bennett @huckbennett.bsky.social · 21/02/2025This 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.comA probabilistic algorithm for verifying matrix products using O(n2) time and log2n + O(1) random bits 1116