CS Theory RSS Posts (last 6 months), from https://theory.report/atom.xml

• arXiv: Data Structures and Algorithms: Online Conformal Prediction with Efficiency Guarantees — 2025-07-04

  Authors: Vaidehi Srinivas

• arXiv: Data Structures and Algorithms: On the Structure of Replicable Hypothesis Testers — 2025-07-04

  Authors: Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Shyam Narayanan, Sandeep Silwal

• arXiv: Data Structures and Algorithms: On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms — 2025-07-04

  Authors: Jens Schlöter

• arXiv: Data Structures and Algorithms: On the Adversarial Robustness of Online Importance Sampling — 2025-07-04

  Authors: Yotam Kenneth-Mordoch, Shay Sapir

• arXiv: Data Structures and Algorithms: Numerical Linear Algebra in Linear Space — 2025-07-04

  Authors: Yiping Liu, Hoai-An Nguyen, Junzhao Yang

• arXiv: Data Structures and Algorithms: New algorithms for girth and cycle detection — 2025-07-04

  Authors: Liam Roditty, Plia Trabelsi

• arXiv: Data Structures and Algorithms: Indexing Tries within Entropy-Bounded Space — 2025-07-04

  Authors: Lorenzo Carfagna, Carlo Tosoni

• arXiv: Data Structures and Algorithms: Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime — 2025-07-04

  Authors: Tomasz Kociumaka, Ali Shahali

• arXiv: Data Structures and Algorithms: Connected k-Median with Disjoint and Non-disjoint Clusters — 2025-07-04

  Authors: Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin, Melanie Schmidt

• arXiv: Data Structures and Algorithms: Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds — 2025-07-04

  Authors: Itai Boneh, Egor Gorbachev, Tomasz Kociumaka

• arXiv: Data Structures and Algorithms: An Easy Proof of a Weak Version of Chernoff inequality — 2025-07-04

  Authors: Sariel Har-Peled

• arXiv: Data Structures and Algorithms: A Computational Proof of the Highest-Scoring Boggle Board — 2025-07-04

  Authors: Dan Vanderkam

• arXiv: Computational Geometry: A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets — 2025-07-04

  Authors: Oswin Aichholzer, Joseph Dorfer

• arXiv: Computational Complexity: Stiefel optimization is NP-hard — 2025-07-04

  Authors: Zehua Lai, Lek-Heng Lim, Tianyun Tang

• Ben Recht: Standard error of what now? — 2025-07-03

• arXiv: Data Structures and Algorithms: SPARSE-PIVOT: Dynamic correlation clustering for node insertions — 2025-07-03

  Authors: Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović

• arXiv: Data Structures and Algorithms: Optimal Dispersion Under Asynchrony — 2025-07-03

  Authors: Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Gokarna Sharma

• arXiv: Data Structures and Algorithms: Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut — 2025-07-03

  Authors: Surender Baswana, Koustav Bhanja, Anupam Roy

• arXiv: Data Structures and Algorithms: Dynamic Similarity Graph Construction with Kernel Density Estimation — 2025-07-03

  Authors: Steinar Laenen, Peter Macgregor, He Sun

• arXiv: Data Structures and Algorithms: Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition — 2025-07-03

  Authors: Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, Yinzhan Xu

• arXiv: Computational Geometry: Search-Based Robot Motion Planning With Distance-Based Adaptive Motion Primitives — 2025-07-03

  Authors: Benjamin Kraljusic, Zlatan Ajanovic, Nermin Covic, Bakir Lacevic

• arXiv: Computational Geometry: Multiple Watchman Routes in Staircase Polygons — 2025-07-03

  Authors: Anna Brötzner, Bengt J. Nilsson, Christiane Schmidt

• arXiv: Computational Geometry: A Stable and Theoretically Grounded Gromov-Wasserstein Distance for Reeb Graph Comparison using Persistence Images — 2025-07-03

  Authors: Erin W. Chambers, Guangyu Meng

• arXiv: Computational Geometry: A Deterministic Partition Tree and Applications — 2025-07-03

  Authors: Haitao Wang

• arXiv: Computational Complexity: Symport/Antiport P Systems with Membrane Separation Characterize P^(#P) — 2025-07-03

  Authors: Vivien Ducros, Claudio Zandron

• arXiv: Computational Complexity: PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs — 2025-07-03

  Authors: Venkatesan Guruswami, Xuandi Ren, Kewen Wu

• arXiv: Computational Complexity: Hardness of Quantum Distribution Learning and Quantum Cryptography — 2025-07-03

  Authors: Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae

• Computational Complexity: A Professor Again — 2025-07-02

  A new dean has taken my place, and I have returned to the professoriate at Illinois Tech, ending thirteen years in administration, six as dean and ...

• Gil Kalai: Some Events — 2025-07-02

  Annual meeting of the Israeli Mathematical Union and student talks day, July 6 and 7

• arXiv: Data Structures and Algorithms: Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms — 2025-07-02

  Authors: Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, Martin Nöllenburg

• arXiv: Data Structures and Algorithms: On the (In)Approximability of the Monitoring Edge Geodetic Set Problem — 2025-07-02

  Authors: Davide Bilò, Giodano Colli, Luca Forlizzi, Stefano Leucci

• arXiv: Data Structures and Algorithms: Lazy B-Trees — 2025-07-02

  Authors: Casper Moldrup Rysgaard, Sebastian Wild

• arXiv: Data Structures and Algorithms: Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard — 2025-07-02

  Authors: Benjamin Bergougnoux, Lars Jaffke

• arXiv: Data Structures and Algorithms: Best Agent Identification for General Game Playing — 2025-07-02

  Authors: Matthew Stephenson, Alex Newcombe, Eric Piette, Dennis Soemers

• arXiv: Data Structures and Algorithms: A Simple Algorithm for Trimmed Multipoint Evaluation — 2025-07-02

  Authors: Nick Fischer, Melvin Kallmayer, Leo Wennmann

• arXiv: Computational Geometry: Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem — 2025-07-02

  Authors: Vanja Stojanović, Bor Pangeršič

• arXiv: Computational Geometry: Compact Representation of Semilinear and Terrain-like Graphs — 2025-07-02

  Authors: Jean Cardinal, Yelena Yuditsky

• arXiv: Computational Geometry: Analyzing Time-Varying Scalar Fields using Piecewise-Linear Morse-Cerf Theory — 2025-07-02

  Authors: Amritendu Dhar, Apratim Chakraborty, Vijay Natarajan

• arXiv: Computational Complexity: Sensitivity and Query Complexity under Uncertainty — 2025-07-02

  Authors: Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, Karteek Sreenivasaiah

• arXiv: Computational Complexity: Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits — 2025-07-02

  Authors: Jefferson D. S. Silva, Adenilton J. da Silva

• David Eppstein: Geometric street art in Kanazawa — 2025-07-01

  Kanazawa was this year’s host of Computational Geometry Week and the Symposium on Computational Geometry, and a great place to visit for lots of re...

• Ben Recht: Two years of substacking — 2025-07-01

• arXiv: Computational Geometry: Passage-traversing optimal path planning with sampling-based algorithms — 2025-07-01

  Authors: Jing Huang, Hao Su, Kwok Wai Samuel Au

• arXiv: Computational Geometry: Moving Matter: Using a Single, Simple Robot to Reconfigure a Connected Set of Building Blocks — 2025-07-01

  Authors: Javier Garcia, Jonas Friemel, Ramin Kosfeld, Michael Yannuzzi, Peter Kramer, Christian Rieck, Christian Scheffer, Arne Schmidt, Harm Kube,...

• arXiv: Computational Geometry: Escher Tile Deformation via Closed-Form Solution — 2025-07-01

  Authors: Crane He Chen, Vladimir G. Kim

• arXiv: Computational Geometry: $C_4$-free subgraphs of high degree with geometric applications — 2025-07-01

  Authors: Zach Hunter, Aleksa Milojević, Istvan Tomon, Benny Sudakov

• arXiv: Computational Complexity: Factorization norms and an inverse theorem for MaxCut — 2025-07-01

  Authors: Igor Balla, Lianna Hambardzumyan, István Tomon

• arXiv: Computational Complexity: Constant-depth circuits for polynomial GCD over any characteristic — 2025-07-01

  Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

• arXiv: Computational Complexity: Closure under factorization from a result of Furstenberg — 2025-07-01

  Authors: Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

• arXiv: Computational Complexity: Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations — 2025-07-01

  Authors: Melissa Antonelli, Arnaud Durand, Juha Kontinen