Congratulations to my colleague Subhash Khot (down the hall), Irit Dinur (across the river and through the woods), Dor Minzer (up the coast), and Guy Kindler and Muli Safra (across the seas), who just got the 2026 Held Prize for their groundbreaking work on 2-2 games!
Did you know? 2026 is one of the integers which, when divided by the sum of the squares of its digits, does nothing particularly remarkable
Hayden Rome, Jayson Lynch, Jeffery Li, Chirag Falor, Neil Thompson
How fast are algorithms reducing the demands on memory? A survey of progress in space complexity
https://arxiv.org/abs/2511.22084
Esty Kelman, Uri Meir, Debanuj Nayak, Sofya Raskhodnikova: Homomorphism Testing with Resilience to Online Manipulations https://arxiv.org/abs/2511.23363 https://arxiv.org/pdf/2511.23363 https://arxiv.org/html/2511.23363
Paul G\"olz, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
Fair Allocation of Indivisible Goods with Variable Groups
https://arxiv.org/abs/2511.06218
The SACT group at #USyd 🇦🇺 has a number of postdoc positions available (2+ years) in all areas of TCS, with one focusing on streaming and one on planning and synthesis. Expected start mid- or end 2026.
Excellent candidates are encouraged to contact us by email, or during #FOCS2025 #TCSSky
🎉 Abigail Gentle (PhD student) and Clément Canonne's paper "Uniformity Testing under User-Level Local Privacy" has been accepted at #ITCS2026!
🔗 Paper: www.arxiv.org/abs/2510.18379 (coauthored with Vikrant Singhal (OpenDP and Harvard))
#theory #algorithms #privacy
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
Halfspaces are hard to test with relative error
https://arxiv.org/abs/2511.06171
Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
https://arxiv.org/abs/2511.07244
Hadi Hosseini, Vishwa Prakash HV, Aditi Sethia, Jatin Yadav
The Landscape of Almost Equitable Allocations
https://arxiv.org/abs/2511.07395
Hadi Hosseini, Sanjukta Roy, Aditi Sethia
Fair Societies: Algorithms for House Allocations
https://arxiv.org/abs/2511.07022
Haris Aziz, Xinhang Lu, Simon Mackenzie, Mashbat Suzuki
Fair Division with Indivisible Goods, Chores, and Cake
https://arxiv.org/abs/2511.04891
Soham Chatterjee, Prahladh Harsha, Mrinal Kumar: Deterministic list decoding of Reed-Solomon codes https://arxiv.org/abs/2511.05176 https://arxiv.org/pdf/2511.05176 https://arxiv.org/html/2511.05176
Qian Li, Xin Lyu: Multi-Pass Streaming Lower Bounds for Uniformity Testing https://arxiv.org/abs/2511.03960 https://arxiv.org/pdf/2511.03960 https://arxiv.org/html/2511.03960
Egor Gagushin, Marios Mertzanidis, Alexandros Psomas
On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences
https://arxiv.org/abs/2511.03810
Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell: Boolean function monotonicity testing requires (almost) $n^(1/2)$ queries https://arxiv.org/abs/2511.04558 https://arxiv.org/pdf/2511.04558 https://arxiv.org/html/2511.04558
Hadi Hosseini, Shraddha Pathak, Yu Zhou
Non-Monotonicity in Fair Division of Graphs
https://arxiv.org/abs/2511.03629
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
Ideals, Gr\"obner Bases, and PCPs
https://arxiv.org/abs/2511.03703
Matija Buci\'c, Zhongtian He, Shang-En Huang, Thatchaphol Saranurak: Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching https://arxiv.org/abs/2511.02214 https://arxiv.org/pdf/2511.02214 https://arxiv.org/html/2511.02214
Diptajit Roy, Nitin Saxena, Madhavan Venkatesh
Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
https://arxiv.org/abs/2511.02262
Academics in Assyria in the 7th c BC complain that admin is preventing them from doing research and teaching
Wiktionary's visual aid to demonstrate what the Swedish word for "funny" means
Alongside the new bulletin, is the first video on the new EATCS Youtube channel!
We learn about different ways to record your seminar talks.
A screenshot with a short excerpt from the the interview. Question: Are there any blog posts you’d like to highlight from over the years? Gautam: I really like posts that share more about the humans behind the research. Omer Reingold ran a series on “research-life stories,” a great representative one is Bobby Kleinberg’s. Luca Trevisan had a series of posts from gay and lesbian computer scientists in commemoration of Turing’s 100th birthday, you can read his own account here. Arnab: Completely agreed with Gautam. I’d also like to highlight Gil Kalai’s valiant effort at “Combinatorics and More.” Gil’s blog has been actively maintained since 2008! It’s still often the first place to break news about advances in combinatorics.
The new EATCS Bulletin #147 is available!
eatcs.org/images/bulle...
In the TCS on the Web Column, I talked to the maintainers of the TCS Blog Aggregator: Nima Anari, Arnab Bhattacharyya and
Gautam Kamath.
It was a very fun interview!
@gautamkamath.com @schmiste-ch.bsky.social
Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma: Testing forbidden order-pattern properties on hypergrids https://arxiv.org/abs/2510.22845 https://arxiv.org/pdf/2510.22845 https://arxiv.org/html/2510.22845
A little-known algorithmic process called “differential privacy” helps keep census data anonymous. Conservatives want it gone.
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
L\'aszl\'o Kozma, Michal Opler: Compact representations of pattern-avoiding permutations https://arxiv.org/abs/2510.20382 https://arxiv.org/pdf/2510.20382 https://arxiv.org/html/2510.20382
