I'd thought about fine-grained complexity of Furthest Pair for some time. Especially exciting to see AI-assisted discovery & algebraic number theory showing up (again!). Congrats to @barnacs.bsky.social, Yinzhan Xu, and Christopher Ye — hoping for many more such uses of these tools in TCS!

arXiv cs.CG Computational Geometry@cscg-bot.bsky.social · last mo.

Barna Saha, Yinzhan Xu, Christopher Ye: Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH https://arxiv.org/abs/2606.25887 https://arxiv.org/pdf/2606.25887 https://arxiv.org/html/2606.25887

Barna Saha, Yinzhan Xu, Christopher Ye: Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH https://arxiv.org/abs/2606.25887 https://arxiv.org/pdf/2606.25887 https://arxiv.org/html/2606.25887

DIMACS is hosting not one, not two, but three workshops on fine-grained complexity next month, from July 20–31! Registration is free but required. To register, click each relevant workshop page on the DIMACS events page: dimacs.rutgers.edu/events/list Hope to see many of you there!

@karthikcs.bsky.social · 6mo ago

2/3 Workshops (dates + links): • Algebraic Techniques in FGC (July 20–22): dimacs.rutgers.edu/events/detai... • FGC of String Problems (July 23–25): dimacs.rutgers.edu/events/detai... • FGC of Graph Problems (July 27–31): dimacs.rutgers.edu/events/detai...

1/3 Fine-Grained Complexity Fest at DIMACS this July! Three back-to-back workshops on Algebraic Techniques, String Algorithms, and Graph Algorithms in fine-grained complexity, with a terrific speaker lineup. Organized by @jalman.bsky.social , Elazar Goldenberg, and @eigx.bsky.social.

The 2026 Michael and Sheila Held Prize goes to Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer and Muli Safra for their work on the 2-to-2 Games Theorem.

Michael and Sheila Held Prize – NAS

The Michael and Sheila Held Prize is presented annually to honor outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent…

nasonline.org

Video playlist from the recently concluded DIMACS workshop titled, "Hardness of Approximation in P" are now available here: www.youtube.com/playlist?lis...

DIMACS Workshop on Hardness of Approximation in P held July 21-23, 2025 - YouTube

DIMACS Workshop on Hardness of Approximation in P July 21, 2025 - July 23, 2025 Rutgers Academic Building, Room 4225 (East Wing) Rutgers University Many impo...

youtube.com

The Call for Papers (CfP) for #SODA26 is out: www.siam.org/conferences-... The submission server is open: soda26.hotcrp.com Deadline: ⏰ Monday, July 14, AoE (July 15, 11:59am UTC)