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

• CCI: jobs: Miller Research Postdoctoral Fellow at Miller Institute for Basic Research in Science, UC Berkeley (apply by September 12, 2025) — 2025-07-25

  The Miller Institute at UC Berkeley seeks exceptional PhD researchers for its 2026-2029 Miller Research Postdoctoral Fellowship. We’re looking for ...

• arXiv: Data Structures and Algorithms: Zeroth-order log-concave sampling — 2025-07-25

  Authors: Yunbum Kook

• arXiv: Data Structures and Algorithms: Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa — 2025-07-25

  Authors: Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, Stanislav Živný

• arXiv: Data Structures and Algorithms: Smoothed Analysis of Online Metric Problems — 2025-07-25

  Authors: Christian Coester, Jack Umenberger

• arXiv: Data Structures and Algorithms: On recognizing graphs representing Persistent Perfect Phylogenies — 2025-07-25

  Authors: Paola Bonizzoni, Gianluca Della Vedova, Mauricio Soto Gomez, Gabriella Trucco

• arXiv: Data Structures and Algorithms: Dual Charging for Half-Integral TSP — 2025-07-25

  Authors: Nathan Klein, Mehrshad Taziki

• arXiv: Data Structures and Algorithms: Better Bounds for Semi-Streaming Single-Source Shortest Paths — 2025-07-25

  Authors: Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan

• arXiv: Computational Geometry: Gromov-Hausdorff distance between chromatic metric pairs and stability — 2025-07-25

  Authors: Ondřej Draganov, Sophie Rosenmeier, Nicolò Zava

• arXiv: Computational Geometry: Explainable Mapper: Charting LLM Embedding Spaces Using — 2025-07-25

  Authors: Xinyuan Yan, Rita Sevastjanova, Sinie van der Ben, Mennatallah El-Assady, Bei Wang

• arXiv: Computational Complexity: The hidden subgroup problem for infinite groups — 2025-07-25

  Authors: Greg Kuperberg

• arXiv: Computational Complexity: Fagin's Theorem for Semiring Turing Machines — 2025-07-25

  Authors: Guillermo Badia, Manfred Droste, Thomas Eiter, Rafael Kiesel, Carles Noguera, Erik Paul

• Computational Complexity: Answer to my GROUP ONE/GROUP TWO Prez question — 2025-07-24

  In a prior post I asked what criteria I used to place Prez and VP nominees since 1976 into two groups.

• Decentralized Thoughts: An Analysis of Latency and Block Capacity in Nakamoto Consensus — 2025-07-24

  Achieving high throughput is essential for blockchain ecosystems to become competitive alternatives to their centralized counterparts across a wide...

• arXiv: Data Structures and Algorithms: Triadic First-Order Logic Queries in Temporal Networks — 2025-07-24

  Authors: Omkar Bhalerao, Yunjie Pan, C. Seshadhri, Nishil Talati

• arXiv: Data Structures and Algorithms: Stable Iterative Solvers for Ill-conditioned Linear Systems — 2025-07-24

  Authors: Vasileios Kalantzis, Mark S. Squillante, Chai Wah Wu

• arXiv: Data Structures and Algorithms: RLZ-r and LZ-End-r: Enhancing Move-r — 2025-07-24

  Authors: Patrick Dinklage, Johannes Fischer, Lukas Nalbach, Jan Zumbrink

• arXiv: Data Structures and Algorithms: Residual Prophet Inequalities — 2025-07-24

  Authors: Jose Correa, Sebastian Perez-Salazar, Dana Pizarro, Bruno Ziliotto

• arXiv: Data Structures and Algorithms: Optimal Pure Differentially Private Sparse Histograms in Near-Linear — 2025-07-24

  Authors: Florian Kerschbaum, Steven Lee, Hao Wu

• arXiv: Data Structures and Algorithms: Fast One-Pass Sparse Approximation of the Top Eigenvectors of Huge — 2025-07-24

  Authors: Edem Boahen, Simone Brugiapaglia, Hung-Hsu Chou, Mark Iwen, Felix Krahmer

• arXiv: Data Structures and Algorithms: Compatibility of Max and Sum Objectives for Committee Selection and — 2025-07-24

  Authors: Yue Han, Elliot Anshelevich

• arXiv: Data Structures and Algorithms: Advancing Quantum State Preparation using LimTDD — 2025-07-24

  Authors: Xin Hong, Aochu Dai, Chenjian Li, Sanjiang Li, Shenggang Ying, Mingsheng Ying

• CS Theory Events: TTIC Summer Workshop on Incentives for Collaborative Learning and Data Sharing — 2025-07-23

  August 13-15, 2025 Toyota Technological Institute at Chicago https://sites.google.com/ttic.edu/incentivesdatasharing/home Submission deadline: July...

• Gil Kalai: Amazing: Jie Ma, Wujie Shen, and Shengjie Xie Gave an Exponential Improvement for Ramsey Lower Bounds — 2025-07-23

  By Gil Kalai

• arXiv: Data Structures and Algorithms: Toward a Lightweight and Robust Design for Caching with Predictions — 2025-07-23

  Authors: Peng Chen, Hailiang Zhao, Jiaji Zhang, Xueyan Tang, Yixuan Wang, Shuiguang Deng

• arXiv: Data Structures and Algorithms: The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches — 2025-07-23

  Authors: Sara Ahmadian, Edith Cohen, Uri Stemmer

• arXiv: Data Structures and Algorithms: Online Joint Replenishment Problem with Arbitrary Holding and Backlog — 2025-07-23

  Authors: Yossi Azar, Shahar Lewkowicz

• arXiv: Data Structures and Algorithms: Online Combinatorial Optimization with Graphical Dependencies — 2025-07-23

  Authors: Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, Sahil Singla

• arXiv: Data Structures and Algorithms: Longest Unbordered Factors on Run-Length Encoded Strings — 2025-07-23

  Authors: Shoma Sekizaki, Takuya Mieno

• arXiv: Data Structures and Algorithms: Best-of-Both-Worlds Guarantees with Fairer Endings — 2025-07-23

  Authors: Telikepalli Kavitha, Surya Panchapakesan, Rohit Vaish, Vignesh Viswanathan, Jatin Yadav

• arXiv: Data Structures and Algorithms: An unconditional lower bound for the active-set method in convex — 2025-07-23

  Authors: Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis

• arXiv: Data Structures and Algorithms: An Exact Solver for Maximizing a Submodular Function Subject to a — 2025-07-23

  Authors: Sabine Münch, Stephen Raach

• arXiv: Data Structures and Algorithms: A Best Possible General Form of the Master Theorem for — 2025-07-23

  Authors: Carl D. Offner

• arXiv: Computational Geometry: Improved Wake-Up Time For Euclidean Freeze-Tag Problem — 2025-07-23

  Authors: Sharareh Alipour, Arash Ahadi, Kajal Baghestani

• arXiv: Computational Geometry: Analysis of Design Algorithms and Fabrication of a Graph-based — 2025-07-23

  Authors: Mehdi Gorjian, Gregory A. Luhan, Stephen M. Caffey

• arXiv: Computational Complexity: Monotone Circuit Complexity of Matching — 2025-07-23

  Authors: Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

• arXiv: Computational Complexity: Constructing material network representations for intelligent amorphous — 2025-07-23

  Authors: S. -Y. Zhang, J. Tian, S. -L. Liu, H. -M. Zhang, H. -Y. Bai, Y. -C. Hu, W. -H. Wang

• arXiv: Computational Complexity: Computational aspects of the trace norm contraction coefficient — 2025-07-23

  Authors: Idris Delsol, Omar Fawzi, Jan Kochanowski, Akshay Ramachandran

• Ben Recht: Digging in the crates — 2025-07-22

• ECCC Papers: TR25-102 | Monotone Circuit Complexity of Matching | — 2025-07-22

  We show that the perfect matching function on $n$-vertex graphs requires monotone circuits of size $\smash{2^{n^{\Omega(1)}}}$. This improves on th...

• Computational Complexity: Trevisan Prize- Deadline July 31 for Notification Intent, Aug 31 for nomination. — 2025-07-22

  A new prize:

• arXiv: Data Structures and Algorithms: Topological Social Choice: Designing a Noise-Robust Polar Distance for — 2025-07-22

  Authors: Athanasios Andrikopoulos, Nikolaos Sampanis

• arXiv: Data Structures and Algorithms: Tighter Lower Bounds for Single Source Personalized PageRank — 2025-07-22

  Authors: Xinpeng Jiang, Haoyu Liu, Siqiang Luo, Xiaokui Xiao

• arXiv: Data Structures and Algorithms: Quantum State Preparation Based on LimTDD — 2025-07-22

  Authors: Xin Hong, Chenjian Li, Aochu Dai, Sanjiang Li, Shenggang Ying, Mingsheng Ying

• arXiv: Data Structures and Algorithms: Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division — 2025-07-22

  Authors: Jarosław Byrka, Franciszek Malinka, Tomasz Ponitka

• arXiv: Data Structures and Algorithms: Predict, Reposition, and Allocate: A Greedy and Flow-Based Architecture — 2025-07-22

  Authors: Aqsa Ashraf Makhdomi, Iqra Altaf Gillani

• arXiv: Data Structures and Algorithms: On zeros and algorithms for disordered systems: mean-field spin glasses — 2025-07-22

  Authors: Ferenc Bencs, Kuikui Liu, Guus Regts

• arXiv: Data Structures and Algorithms: On Algorithmic Robustness of Corrupted Markov Chains — 2025-07-22

  Authors: Jason Gaitonde, Elchanan Mossel

• arXiv: Data Structures and Algorithms: New Algorithms for #2-SAT and #3-SAT — 2025-07-22

  Authors: Junqiang Peng, Zimo Sheng, Mingyu Xiao

• arXiv: Data Structures and Algorithms: Language Generation in the Limit: Noise, Loss, and Feedback — 2025-07-22

  Authors: Yannan Bai, Debmalya Panigrahi, Ian Zhang

• arXiv: Data Structures and Algorithms: k-PCA for (non-squared) Euclidean Distances: Polynomial Time — 2025-07-22

  Authors: Daniel Greenhut, Dan Feldman

• arXiv: Data Structures and Algorithms: Job Scheduling under Base and Additional Fees, with Applications to — 2025-07-22

  Authors: Yi-Ting Hsieh, Mong-Jen Kao, Jhong-Yun Liu, Hung-Lung Wang

• arXiv: Data Structures and Algorithms: Fast Algorithms for Graph Arboricity and Related Problems — 2025-07-22

  Authors: Ruoxu Cen, Henry Fleischmann, George Z. Li, Jason Li, Debmalya Panigrahi

• arXiv: Data Structures and Algorithms: Dvorak-Dell-Grohe-Rattan theorem via an asymptotic argument — 2025-07-22

  Authors: Alexander Kozachinskiy

• arXiv: Data Structures and Algorithms: Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts — 2025-07-22

  Authors: Pan Peng, Hangyu Xu

• arXiv: Data Structures and Algorithms: Characterizing and Testing Configuration Stability in Two-Dimensional — 2025-07-22

  Authors: Yonatan Nakar, Dana Ron

• arXiv: Data Structures and Algorithms: Certificate-Sensitive Subset Sum: Realizing Instance Complexity — 2025-07-22

  Authors: Jesus Salas

• arXiv: Data Structures and Algorithms: Better Models and Algorithms for Learning Ising Models from Dynamics — 2025-07-22

  Authors: Jason Gaitonde, Ankur Moitra, Elchanan Mossel

• arXiv: Data Structures and Algorithms: Asynchronous Collective Tree Exploration: a Distributed Algorithm, and a — 2025-07-22

  Authors: Romain Cosson, Laurent Massoulié

• arXiv: Data Structures and Algorithms: An n{O(loglog n)} time approximation scheme for capacitated VRP in — 2025-07-22

  Authors: René Sitters

• arXiv: Data Structures and Algorithms: Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and — 2025-07-22

  Authors: Sheikh Shakil Akhtar, Jayakrishnan Madathil, Pranabendu Misra, Geevarghese Philip

• arXiv: Data Structures and Algorithms: A Myhill-Nerode Type Characterization of 2detLIN Languages — 2025-07-22

  Authors: Benedek Nagy

• arXiv: Data Structures and Algorithms: A Black-Box Approach for Exogenous Replenishment in Online Resource — 2025-07-22

  Authors: Suho Kang, Ziyang Liu, Rajan Udwani

• arXiv: Data Structures and Algorithms: 1.64-Approximation for Chromatic Correlation Clustering via Chromatic — 2025-07-22

  Authors: Dahoon Lee, Chenglin Fan, Euiwoong Lee

• arXiv: Computational Geometry: Variable Min-Cut Max-Flow Bounds and Algorithms in Finite Regime — 2025-07-22

  Authors: Rivka Gitik, Alejandro Cohen

• arXiv: Computational Geometry: TrajLens: Visual Analysis for Constructing Cell Developmental — 2025-07-22

  Authors: Qipeng Wang, Shaolun Ruan, Rui Sheng, Yong Wang, Min Zhu, Huamin Qu

• arXiv: Computational Geometry: On Quad Mesh Extraction From Messy Grid Preserving Maps — 2025-07-22

  Authors: Nicolas Ray

• arXiv: Computational Geometry: k-PCA for (non-squared) Euclidean Distances: Polynomial Time — 2025-07-22

  Authors: Daniel Greenhut, Dan Feldman

• arXiv: Computational Complexity: Studying homing and synchronizing sequences for Timed Finite State — 2025-07-22

  Authors: Evgenii Vinarskii, Jakub Ruszil, Adam Roman, Natalia Kushik

• arXiv: Computational Complexity: Pseudorandomness of Expander Walks via Fourier Analysis on Groups — 2025-07-22

  Authors: Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy

• arXiv: Computational Complexity: Efficient Algorithms for Relevant Quantities of Friedkin-Johnsen Opinion — 2025-07-22

  Authors: Gengyu Wang, Runze Zhang, Zhongzhi Zhang

• arXiv: Computational Complexity: Complexity of Faceted Explanations in Propositional Abduction — 2025-07-22

  Authors: Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist, Johannes K. Fichte

• The Learning Theory Alliance Blog: Testing Assumptions of Learning Algorithms — 2025-07-21

  Today’s technical post is by Arsen Vasilyan. This focuses on the very exciting new “testable learning” he introduced with Rubinfeld in a 2023 paper...

• Windows on Theory: AI Safety Course Intro Blog — 2025-07-21

  I am teaching CS 2881: AI Safety this fall at Harvard. This blog is primarily aimed at students at Harvard or MIT (where we have a cross-registerin...

• arXiv: Data Structures and Algorithms: Weighted Matching in a Poly-Streaming Model — 2025-07-21

  Authors: Ahammed Ullah, S. M. Ferdous, Alex Pothen

• arXiv: Data Structures and Algorithms: Treedepth Inapproximability and Exponential ETH Lower Bound — 2025-07-21

  Authors: Édouard Bonnet, Daniel Neuen, Marek Sokołowski

• arXiv: Data Structures and Algorithms: Tight Bounds for Answering Adaptively Chosen Concentrated Queries — 2025-07-21

  Authors: Emma Rapoport, Edith Cohen, Uri Stemmer

• arXiv: Data Structures and Algorithms: Strassen 2times2 Matrix Multiplication from a 3-dimensional Volume — 2025-07-21

  Authors: Benoit Jacob

• arXiv: Data Structures and Algorithms: Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and — 2025-07-21

  Authors: Sanjeev Khanna, Ashwin Padaki, Erik Waingarten

• arXiv: Data Structures and Algorithms: Quantum Pattern Matching with Wildcards — 2025-07-21

  Authors: Masoud Seddighin, Saeed Seddighin

• arXiv: Data Structures and Algorithms: Optimal antimatroid sorting — 2025-07-21

  Authors: Benjamin Aram Berendsohn

• arXiv: Data Structures and Algorithms: Improved girth approximation in weighted undirected graphs — 2025-07-21

  Authors: Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick

• arXiv: Data Structures and Algorithms: Faster Multi-Source Reachability and Approximate Distances via — 2025-07-21

  Authors: Michael Elkin, Chhaya Trehan

• arXiv: Data Structures and Algorithms: Combinatorics of Palindromes — 2025-07-21

  Authors: Michael Itzhaki

• arXiv: Data Structures and Algorithms: An Efficient Massively Parallel Constant-Factor Approximation Algorithm — 2025-07-21

  Authors: Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian

• arXiv: Computational Geometry: Isotropic Remeshing with Inter-Angle Optimization — 2025-07-21

  Authors: Hanbing Zheng, Chenlei Lv

• arXiv: Computational Geometry: Generalized cluster algorithms for Potts lattice gauge theory — 2025-07-21

  Authors: Anthony E. Pizzimenti, Paul Duncan, Benjamin Schweinhart

• arXiv: Computational Complexity: Proceedings of the 15th International Workshop on Non-Classical Models — 2025-07-21

  Authors: Nelma Moreira, Luca Prigioniero

• arXiv: Computational Complexity: Fast computational deep thermalization — 2025-07-21

  Authors: Shantanav Chakraborty, Soonwon Choi, Soumik Ghosh, Tudor Giurgică-Tiron

• arXiv: Computational Complexity: Exact versus Approximate Representations of Boolean Functions in the De — 2025-07-21

  Authors: Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

• arXiv: Computational Complexity: Characterizing p-Simulation Between Theories — 2025-07-21

  Authors: Hunter Monroe

• Computational Complexity: A Prez Question: Can AI do it? Can you? Can I? — 2025-07-20

   I am curious how AI or humans can do on the following question. I have listed out the nominees for Prez and VP (Vice Prez) since 1976 and put the...

• ECCC Papers: TR25-101 | Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis | — 2025-07-20

  A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the f...

• ECCC Papers: TR25-100 | Equality is Far Weaker Than Constant-Cost Communication | — 2025-07-20

  We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-...

• David Eppstein: Twenty years of blogging — 2025-07-20

  I made my first post to this blog twenty years ago, on July 20, 2005.

• Nisheeth Vishnoi: What is Intelligence? Architecture, Divergence, and Fiction — 2025-07-19

  A computational anatomy of intelligence. How faculties interact, architectures diverge, and coherence emerges through self-constructed fictions

• CCI: jobs: Postdoctoral fellow position at University of Houston apply by September 30, 2025 — 2025-07-18

  A postdoc is available in distributed and scalable machine learning, security, and fault tolerance in distributed computing at the CS department, U...

• ECCC Papers: TR25-099 | The Algebraic Cost of a Boolean Sum | — 2025-07-18

  It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant do...

• ECCC Papers: TR25-099 | The Algebraic Cost of a Boolean Sum | — 2025-07-18

  It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant do...

• Francis Bach: Revisiting scaling laws via the z-transform — 2025-07-18

  In the last few years, we have seen a surge of empirical and theoretical works about “scaling laws”, whose goals are to characterize the performanc...

• Decentralized Thoughts: 2-round BFT in Simplex style — 2025-07-18

  Simplex is a recent partially synchronous Byzantine Fault Tolerant (BFT) protocol that is gaining popularity. We take this opportunity to rehash se...

• arXiv: Data Structures and Algorithms: Waiting is worth it and can be improved with predictions — 2025-07-18

  Authors: Ya-Chun Liang, Meng-Hsi Li, Chung-Shou Liao, Clifford Stein

• arXiv: Data Structures and Algorithms: The Price of Diversity of the Traveling Salesman Problem — 2025-07-18

  Authors: Mark de Berg, Andrés López Martínez, Frits Spieksma

• arXiv: Data Structures and Algorithms: Splittable Spanning Trees and Balanced Forests in Dense Random Graphs — 2025-07-18

  Authors: David Gillman, Jacob Platnick, Dana Randall

• arXiv: Data Structures and Algorithms: Online Rounding for Set Cover under Subset Arrivals — 2025-07-18

  Authors: Jarosław Byrka, Yongho Shin

• arXiv: Data Structures and Algorithms: Max-Cut with Multiple Cardinality Constraints — 2025-07-18

  Authors: Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian

• arXiv: Data Structures and Algorithms: Maintaining Routing Structures under Deletions via Self-Pruning — 2025-07-18

  Authors: Bernhard Haeupler, Antti Roeyskoe

• arXiv: Data Structures and Algorithms: Kernelization for H-Coloring — 2025-07-18

  Authors: Yael Berkman, Ishay Haviv

• arXiv: Data Structures and Algorithms: Fast Approximate Rank Determination and Selection with Group Testing — 2025-07-18

  Authors: Adiesha Liyanage, Braeden Sopp, Brendan Mumey

• arXiv: Data Structures and Algorithms: Efficiently Constructing Sparse Navigable Graphs — 2025-07-18

  Authors: Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen

• arXiv: Data Structures and Algorithms: Efficient Semi-External Breadth-First Search — 2025-07-18

  Authors: Xiaolong Wan, Xixian Han

• arXiv: Data Structures and Algorithms: Cut-Matching Games for Bipartiteness Ratio of Undirected Graphs — 2025-07-18

  Authors: Tasuku Soma, Mingquan Ye, Yuichi Yoshida

• arXiv: Data Structures and Algorithms: Computing and Bounding Equilibrium Concentrations in Athermic Chemical — 2025-07-18

  Authors: Hamidreza Akef, Minki Hhan, David Soloveichik

• arXiv: Data Structures and Algorithms: Computing and Bounding Equilibrium Concentrations in Athermic Chemical — 2025-07-18

  Authors: Hamidreza Akef, Minki Hhan, David Soloveichik

• arXiv: Data Structures and Algorithms: Computational-Statistical Tradeoffs from NP-hardness — 2025-07-18

  Authors: Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan

• arXiv: Data Structures and Algorithms: Analysis of Langevin midpoint methods using an anticipative Girsanov — 2025-07-18

  Authors: Matthew S. Zhang

• arXiv: Data Structures and Algorithms: Analysis of Langevin midpoint methods using an anticipative Girsanov — 2025-07-18

  Authors: Matthew S. Zhang

• arXiv: Data Structures and Algorithms: An EPTAS for multiprocessor scheduling with rejection under a machine — 2025-07-18

  Authors: Mingyang Gong, Brendan Mumey

• arXiv: Data Structures and Algorithms: An EPTAS for multiprocessor scheduling with rejection under a machine — 2025-07-18

  Authors: Mingyang Gong, Brendan Mumey

• arXiv: Data Structures and Algorithms: A 1/2-Approximation for Budgeted k-Submodular Maximization — 2025-07-18

  Authors: Chenhao Wang

• arXiv: Computational Geometry: A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces — 2025-07-18

  Authors: Éric Colin de Verdière, Vincent Despré, Loïc Dubois

• arXiv: Computational Complexity: The Serial Scaling Hypothesis — 2025-07-18

  Authors: Yuxi Liu, Konpat Preechakul, Kananart Kuwaranancharoen, Yutong Bai

• arXiv: Computational Complexity: Ranking Vectors Clustering: Theory and Applications — 2025-07-18

  Authors: Ali Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee

• arXiv: Computational Complexity: FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond — 2025-07-18

  Authors: Gal Beniamini, Yuval Dor, Alon Vinnikov, Shir Granot Peled, Or Weinstein, Or Sharir, Noam Wies, Tomer Nussbaum, Ido Ben Shaul, Tomer Zekha...

• arXiv: Computational Complexity: FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond — 2025-07-18

  Authors: Gal Beniamini, Yuval Dor, Alon Vinnikov, Shir Granot Peled, Or Weinstein, Or Sharir, Noam Wies, Tomer Nussbaum, Ido Ben Shaul, Tomer Zekha...

• arXiv: Computational Complexity: Computational-Statistical Tradeoffs from NP-hardness — 2025-07-18

  Authors: Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan

• Ben Recht: The unpredictability conundrum — 2025-07-17

• ECCC Papers: TR25-098 | IPS Lower Bounds for Formulas and Sum of1 ROABPs | — 2025-07-17

  We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is...

• ECCC Papers: TR25-098 | IPS Lower Bounds for Formulas and Sum of1 ROABPs | — 2025-07-17

  We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is...

• arXiv: Data Structures and Algorithms: Weighted k-Server Admits an Exponentially Competitive Algorithm — 2025-07-17

  Authors: Adithya Bijoy, Ankit Mondal, Ashish Chiplunkar

• arXiv: Data Structures and Algorithms: Pathfinding in Self-Deleting Graphs — 2025-07-17

  Authors: Michal Dvořák, Dušan Knop, Michal Opler, Jan Pokorný, Ondřej Suchý, Krisztina Szilágyi

• arXiv: Data Structures and Algorithms: Online Block Packing — 2025-07-17

  Authors: Ariel Ben Eliezer, Noam Nisan

• arXiv: Data Structures and Algorithms: Kernelization for list H-coloring for graphs with small vertex cover — 2025-07-17

  Authors: Marta Piecyk, Astrid Pieterse, Paweł Rzążewski, Magnus Wahlström

• arXiv: Data Structures and Algorithms: Finite Pinwheel Scheduling: the k-Visits Problem — 2025-07-17

  Authors: Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, Euripides Markou, Aris Pagourtzis

• arXiv: Data Structures and Algorithms: FastReChain: Highly Responsive and Low-Overhead Centralized Route — 2025-07-17

  Authors: Zihan Zhu, Dongchao Wu, Zhanbang Zhang, Jian Yang

• arXiv: Data Structures and Algorithms: Approaching Optimality for Solving Dense Linear Systems with Low-Rank — 2025-07-17

  Authors: Michał Dereziński, Aaron Sidford

• arXiv: Data Structures and Algorithms: A near-complete resolution of the exponential-time complexity of k-opt — 2025-07-17

  Authors: Sophia Heimann, Hung P. Hoang, Stefan Hougardy

• arXiv: Computational Complexity: Which graph motif parameters count? — 2025-07-17

  Authors: Markus Bläser, Radu Curticapean, Julian Dörfler, Christian Ikenmeyer

• arXiv: Computational Complexity: Searching for Falsified Clause in Random (log n)-CNFs is Hard for — 2025-07-17

  Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

• arXiv: Computational Complexity: Searching for Falsified Clause in Random log n-CNFs is Hard for — 2025-07-17

  Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

• ECCC Papers: TR25-097 | On the Limits of Computationally Sound IPPs in the Isolated Model | — 2025-07-16

  Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hol...

• Computational Complexity: Turing, Wagner, Ruth — 2025-07-16

  Douglas Hofstadter first published Gödel, Escher, Bach: an Eternal Golden Braid in 1979 and my then high school self tried, and failed, to read tho...

• ECCC Papers: TR25-096 | Searching for Falsified Clause in Random log{n}-CNFs is Hard for Randomized Communication | — 2025-07-16

  We show that for a randomly sampled unsatisfiable $O(\log n)$-CNF over $n$ variables the randomized two-party communication cost of finding a claus...

• arXiv: Data Structures and Algorithms: Solving Random Planted CSPs below the n{k/2} Threshold — 2025-07-16

  Authors: Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin, Peter Manohar

• arXiv: Data Structures and Algorithms: Solving Linear Programs with Differential Privacy — 2025-07-16

  Authors: Alina Ene, Huy Le Nguyen, Ta Duy Nguyen, Adrian Vladu

• arXiv: Data Structures and Algorithms: Scheduling on Identical Machines with Setup Time and Unknown Execution — 2025-07-16

  Authors: Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, Hanna Sumita

• arXiv: Data Structures and Algorithms: Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic — 2025-07-16

  Authors: Weiming Feng, Minji Yang

• arXiv: Data Structures and Algorithms: Permutation patterns in streams — 2025-07-16

  Authors: Benjamin Aram Berendsohn

• arXiv: Data Structures and Algorithms: On Tight Robust Coresets for k-Medians Clustering — 2025-07-16

  Authors: Lingxiao Huang, Zhenyu Jiang, Yi Li, Xuan Wu

• arXiv: Data Structures and Algorithms: Multipass Linear Sketches for Geometric LP-Type Problems — 2025-07-16

  Authors: N. Efe Çekirge, William Gay, David P. Woodruff

• arXiv: Data Structures and Algorithms: Improved sampling algorithms and Poincar inequalities for — 2025-07-16

  Authors: Yuchen He, Zhehan Lei, Jianan Shao, Chihao Zhang

• arXiv: Data Structures and Algorithms: Fully Dynamic Euclidean k-Means — 2025-07-16

  Authors: Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou

• arXiv: Data Structures and Algorithms: FPT Parameterisations of Fractional and Generalised Hypertree Width — 2025-07-16

  Authors: Matthias Lanzinger, Igor Razgon, Daniel Unterberger

• arXiv: Data Structures and Algorithms: Finding Order-Preserving Subgraphs — 2025-07-16

  Authors: Haruya Imamura, Yasuaki Kobayashi, Yota Otachi, Toshiki Saitoh, Keita Sato, Asahi Takaoka, Ryo Yoshinaka

• arXiv: Data Structures and Algorithms: Faster algorithms for k-Orthogonal Vectors in low dimension — 2025-07-16

  Authors: Anita Dürr, Evangelos Kipouridis, Karol Węgrzycki

• arXiv: Data Structures and Algorithms: Efficient Branch-and-Bound for Submodular Function Maximization under — 2025-07-16

  Authors: Yimin Hao, Yi Zhou, Chao Xu, Zhang-Hua Fu

• arXiv: Data Structures and Algorithms: Distributionally Robust Optimization with Adversarial Data Contamination — 2025-07-16

  Authors: Shuyao Li, Ilias Diakonikolas, Jelena Diakonikolas

• arXiv: Data Structures and Algorithms: Deterministic Lower Bounds for k-Edge Connectivity in the Distributed — 2025-07-16

  Authors: Peter Robinson, Ming Ming Tan

• arXiv: Data Structures and Algorithms: Compressed data structures for Heegaard splittings — 2025-07-16

  Authors: Henrique Ennes, Clément Maria

• arXiv: Data Structures and Algorithms: Access Control for Information-Theoretically Secure Key-Document Stores — 2025-07-16

  Authors: Yin Li, Sharad Mehrota, Shantanu Sharma, Komal Kumari

• arXiv: Data Structures and Algorithms: A Fast Coloring Oracle for Average Case Hypergraphs — 2025-07-16

  Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber

• arXiv: Computational Geometry: Tileable Surfaces — 2025-07-16

  Authors: David Brander, Jens Gravesen

• arXiv: Computational Geometry: On Tight Robust Coresets for k-Medians Clustering — 2025-07-16

  Authors: Lingxiao Huang, Zhenyu Jiang, Yi Li, Xuan Wu

• arXiv: Computational Geometry: Compressed data structures for Heegaard splittings — 2025-07-16

  Authors: Henrique Ennes, Clément Maria

• arXiv: Computational Geometry: Bicriteria Polygon Aggregation with Arbitrary Shapes — 2025-07-16

  Authors: Lotte Blank, David Eppstein, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, Jonas Sa...

• arXiv: Computational Complexity: On the Complexity of the Skolem Problem at Low Orders — 2025-07-16

  Authors: Piotr Bacik, Joël Ouaknine, James Worrell

• arXiv: Computational Complexity: On the Complexity of the Optimal Correlated Equilibria in Extensive-Form — 2025-07-16

  Authors: Vincent Cheval, Florian Horn, Soumyajit Paul, Mahsa Shirmohammadi

• arXiv: Computational Complexity: FPT Parameterisations of Fractional and Generalised Hypertree Width — 2025-07-16

  Authors: Matthias Lanzinger, Igor Razgon, Daniel Unterberger

• arXiv: Computational Complexity: Equality is Far Weaker than Constant-Cost Communication — 2025-07-16

  Authors: Mika Göös, Nathaniel Harms, Artur Riazanov

• arXiv: Computational Complexity: Eigenvalue Bounds for Symmetric Markov Chains on Multislices With — 2025-07-16

  Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan

• arXiv: Computational Complexity: A Fast Coloring Oracle for Average Case Hypergraphs — 2025-07-16

  Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber

• ECCC Papers: TR25-095 | Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness | — 2025-07-15

  A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing els...

• Gil Kalai: Jorams seminar 2025: Hypercontractivity, Groups and Representations — 2025-07-15

  Joram’s seminar 2025

• David Eppstein: Linkage — 2025-07-15

  Dozens of the world’s most cited scientists stop falsely claiming to work in Saudi Arabia ((\mathbb{M})). Perhaps relatedly, Clarivate has tight...

• Ben Recht: Metascience of pull requests — 2025-07-15

• arXiv: Data Structures and Algorithms: Simultaneous Network Design with Restricted Link Usage — 2025-07-15

  Authors: Naonori Kakimura, Péter Madarasi, Jannik Matuschke, Kitti Varga

• arXiv: Data Structures and Algorithms: Phase transition of the Sinkhorn-Knopp algorithm — 2025-07-15

  Authors: Kun He

• arXiv: Data Structures and Algorithms: Paths and Intersections: Exact Emulators for Planar Graphs — 2025-07-15

  Authors: George Z. Li, Zihan Tan, Tianyi Zhang

• arXiv: Data Structures and Algorithms: Nearly Tight Sample Complexity for Matroid Online Contention Resolution — 2025-07-15

  Authors: Moran Feldman, Ola Svensson, Rico Zenklusen

• arXiv: Data Structures and Algorithms: Minimum-Peak-Cost Flows Over Time — 2025-07-15

  Authors: Mariia Anapolska, Emma Ahrens, Christina Büsing, Felix Engelhardt, Timo Gersing, Corinna Mathwieser, Sabrian Schmitz, Sophia Wrede

• arXiv: Data Structures and Algorithms: m-Eternal Domination and Variants on Some Classes of Finite and Infinite — 2025-07-15

  Authors: Tiziana Calamoneri, Federico Corò, Neeldhara Misra, Saraswati G. Nanoti, Giacomo Paesani

• arXiv: Data Structures and Algorithms: Improved Directed Expander Decompositions — 2025-07-15

  Authors: Henry Fleischmann, George Z. Li, Jason Li

• arXiv: Data Structures and Algorithms: Improved bicriteria approximation for k-edge-connectivity — 2025-07-15

  Authors: Zeev Nutov

• arXiv: Data Structures and Algorithms: Explicit Bounds and Parallel Algorithms for Counting Multiply Gleeful — 2025-07-15

  Authors: Sara Moore, Jonathan P. Sorenson

• arXiv: Data Structures and Algorithms: Covering a Few Submodular Constraints and Applications — 2025-07-15

  Authors: Tanvi Bajpai, Chandra Chekuri, Pooja Kulkarni

• arXiv: Data Structures and Algorithms: Computing the probability of intersection — 2025-07-15

  Authors: Alexander Barvinok

• arXiv: Data Structures and Algorithms: Colorful Minors — 2025-07-15

  Authors: Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht

• arXiv: Data Structures and Algorithms: Bicriteria Submodular Maximization — 2025-07-15

  Authors: Moran Feldman, Alan Kuhnle

• arXiv: Data Structures and Algorithms: Average Sensitivity of Hierarchical k-Median Clustering — 2025-07-15

  Authors: Shijie Li, Weiqiang He, Ruobing Bai, Pan Peng

• arXiv: Data Structures and Algorithms: Approximating Maximum Cut on Interval Graphs and Split Graphs beyond — 2025-07-15

  Authors: Jungho Ahn, Ian DeHaan, Eun Jung Kim, Euiwoong Lee

• arXiv: Data Structures and Algorithms: A Fixed Parameter Tractable Approach for Solving the Vertex Cover — 2025-07-15

  Authors: Mumuksh Tayal

• arXiv: Computational Complexity: The Network Satisfaction Problem for Relation Algebras with at most 4 — 2025-07-15

  Authors: Manuel Bodirsky, Moritz Jahn, Matěj Konečný, Simon Knäuer, Paul Winkler

• arXiv: Computational Complexity: Simultaneous Network Design with Restricted Link Usage — 2025-07-15

  Authors: Naonori Kakimura, Péter Madarasi, Jannik Matuschke, Kitti Varga

• arXiv: Computational Complexity: m-Eternal Domination and Variants on Some Classes of Finite and Infinite — 2025-07-15

  Authors: Tiziana Calamoneri, Federico Corò, Neeldhara Misra, Saraswati G. Nanoti, Giacomo Paesani

• arXiv: Computational Complexity: IPS Lower Bounds for Formulas and Sum of ROABPs — 2025-07-15

  Authors: Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Sinhababu

• arXiv: Computational Complexity: Directed disjoint paths remains W[1]-hard on acyclic digraphs without — 2025-07-15

  Authors: Ken-ichi Kawarabayashi, Nicola Lorenz, Marcelo Garlet Milani, Jacob Stegemann

• arXiv: Computational Complexity: Consensus, Inconsistency, Emergence: what's paraconsistency got to do — 2025-07-15

  Authors: Gabriel Rocha

• arXiv: Computational Complexity: Communication Complexity is NP-hard — 2025-07-15

  Authors: Shuichi Hirahara, Rahul Ilango, Bruno Loff

• arXiv: Computational Complexity: A Critique of Deng's P=NP — 2025-07-15

  Authors: Isabel Humphreys, Matthew Iceland, Harry Liuson, Dylan McKellips, Leo Sciortino

• ECCC Papers: TR25-094 | Communication Complexity is NP-hard | — 2025-07-14

  In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given f...

• ECCC Papers: TR25-093 | Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications | — 2025-07-14

  We consider random walks on “balanced multislices” of any “grid” that respects the “symmetries” of the grid, and show that a broad class of such wa...

• Property Testing Review: News for June 2025 — 2025-07-14

  Another (sigh) delayed post. A moderately busy month, with 4 papers with sublinear graph algorithms and, of course, distribution testing.

• arXiv: Data Structures and Algorithms: To buy or not to buy: deterministic rent-or-buy problems on — 2025-07-14

  Authors: Sander Borst, Moritz Venzin

• arXiv: Data Structures and Algorithms: On the Parallel Complexity of Finding a Matroid Basis — 2025-07-14

  Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

• arXiv: Data Structures and Algorithms: On the Constant-Factor Approximability of Minimum Cost Constraint — 2025-07-14

  Authors: Ian DeHaan, Neng Huang, Euiwoong Lee

• arXiv: Data Structures and Algorithms: On Fair Epsilon Net and Geometric Hitting Set — 2025-07-14

  Authors: Mohsen Dehghankar, Stavros Sintos, Abolfazl Asudeh

• arXiv: Data Structures and Algorithms: Mallows Model with Learned Distance Metrics: Sampling and Maximum — 2025-07-14

  Authors: Yeganeh Alimohammadi, Kiana Asgari

• arXiv: Data Structures and Algorithms: H-Planarity and Parametric Extensions: when Modulators Act Globally — 2025-07-14

  Authors: Fedor V. Fomin, Petr A. Golovach, Laure Morelle, Dimitrios M. Thilikos

• arXiv: Data Structures and Algorithms: Finding a solution to the Erds-Ginzburg-Ziv theorem in — 2025-07-14

  Authors: Yui Hin Arvin Leung

• arXiv: Data Structures and Algorithms: Fast and Efficient Merge of Sorted Input Lists in Hardware Using List — 2025-07-14

  Authors: Robert B. Kent, Marios S. Pattichis

• arXiv: Data Structures and Algorithms: Beer Path Problems in Temporal Graphs — 2025-07-14

  Authors: Andrea D’Ascenzo, Giuseppe F. Italiano, Sotiris Kanellopoulos, Anna Mpanti, Aris Pagourtzis, Christos Pergaminelis

• arXiv: Data Structures and Algorithms: Approximation Algorithms for the Cumulative Vehicle Routing Problem with — 2025-07-14

  Authors: Jingyang Zhao, Mingyu Xiao

• arXiv: Computational Geometry: Flexible arrangement of two Bennett tubes — 2025-07-14

  Authors: Georg Nawratil

• arXiv: Computational Geometry: Computing optimal trajectories for a tethered pursuer — 2025-07-14

  Authors: Aurelio Barrera-Vicent, José Miguel Díaz-Báñez, Fabio Rodríguez, Vanesa Sánchez-Canales

• arXiv: Computational Geometry: A Robust Approach to Detect Intersections between Triangles with — 2025-07-14

  Authors: Luca Garau, Gianmarco Cherchi

• arXiv: Computational Complexity: On the Constant-Factor Approximability of Minimum Cost Constraint — 2025-07-14

  Authors: Ian DeHaan, Neng Huang, Euiwoong Lee

• arXiv: Computational Complexity: Communication complexity of pointer chasing via the fixed-set lemma — 2025-07-14

  Authors: Emanuele Viola

• Computational Complexity: How much money did Francis Scott Key give to have a building named after him? — 2025-07-13

  UMCP has a building named

• ECCC Papers: TR25-092 | Complexity-Theoretic Inductive Inference | — 2025-07-12

  Inductive inference, introduced by Solomonoff (Information and Control, 1964), is a foundational concept in knowledge acquisition, formulated as th...

• Ben Recht: Are developers finally out of a job? — 2025-07-11

• CCI: jobs: Postdoc in Complexity Theory at University of Warwick apply by July 31, 2025 — 2025-07-11

  A postdoctoral position is available in the research group of Igor Carboni Oliveira at the University of Warwick. Candidates interested in computat...

• arXiv: Data Structures and Algorithms: On the Complexity of Hyperpath and Minimal Separator Enumeration in — 2025-07-11

  Authors: Kazuhiro Kurita, Kevin Mann

• arXiv: Data Structures and Algorithms: Finding sparse induced subgraphs on graphs of bounded induced matching — 2025-07-11

  Authors: Hans L. Bodlaender, Fedor V. Fomin, Tuukka Korhonen

• arXiv: Data Structures and Algorithms: Finding One Local Optimum Is Easy -- But What about Two? — 2025-07-11

  Authors: Yasuaki Kobayashi, Kazuhiro Kurita, Yutaro Yamaguchi

• arXiv: Data Structures and Algorithms: Efficient and Adaptive Estimation of Local Triadic Coefficients — 2025-07-11

  Authors: Ilie Sarpe, Aristides Gionis

• arXiv: Data Structures and Algorithms: A Randomized Rounding Approach for DAG Edge Deletion — 2025-07-11

  Authors: Sina Kalantarzadeh, Nathan Klein, Victor Reis

• arXiv: Computational Geometry: The Smooth Power of the Neandertal Method — 2025-07-11

  Authors: Aaron Montag, Tim Reinhardt, Jürgen Richter-Gebert

• arXiv: Computational Geometry: Approximation Depth of Convex Polytopes — 2025-07-11

  Authors: Egor Bakaev, Florestan Brunck, Amir Yehudayoff

• arXiv: Computational Geometry: A simple proof of a p,2-theorem for non-piercing regions — 2025-07-11

  Authors: Chaya Keller, Shakhar Smorodinsky

• arXiv: Computational Complexity: Turing complete Navier-Stokes steady states via cosymplectic geometry — 2025-07-11

  Authors: Søren Dyhr, Ángel González-Prieto, Eva Miranda, Daniel Peralta-Salas

• arXiv: Computational Complexity: The Richness of CSP Non-redundancy — 2025-07-11

  Authors: Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen, Victor Lagerkvist, Magnus Wahlström

• arXiv: Computational Complexity: Testing Isomorphism of Boolean Functions over Finite Abelian Groups — 2025-07-11

  Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, Manmatha Roy

• arXiv: Computational Complexity: On the Complexity of Hyperpath and Minimal Separator Enumeration in — 2025-07-11

  Authors: Kazuhiro Kurita, Kevin Mann

• arXiv: Computational Complexity: Nonogram: Complexity of Inference and Phase Transition Behavior — 2025-07-11

  Authors: Aaron Foote, Danny Krizanc

• arXiv: Computational Complexity: Finding One Local Optimum Is Easy -- But What about Two? — 2025-07-11

  Authors: Yasuaki Kobayashi, Kazuhiro Kurita, Yutaro Yamaguchi

• Ben Recht: An open mindset — 2025-07-10

• ECCC Papers: TR25-091 | Tree PCPs | — 2025-07-10

  Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired b...

• ECCC Papers: TR25-090 | Linear Prover IOPs in Log Star Rounds | — 2025-07-10

  Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover...

• arXiv: Data Structures and Algorithms: Prediction-Augmented Mechanism Design for Weighted Facility Location — 2025-07-10

  Authors: Yangguang Shi, Zhenyu Xue

• arXiv: Data Structures and Algorithms: Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees — 2025-07-10

  Authors: Mohsen Ghaffari, Jaehyun Koo

• arXiv: Data Structures and Algorithms: Parallel Batch-Dynamic Algorithms for Spanners, and Extensions — 2025-07-10

  Authors: Mohsen Ghaffari, Jaehyun Koo

• arXiv: Data Structures and Algorithms: Multi-Queue SSD I/O Modeling & Its Implications for Data Structure — 2025-07-10

  Authors: Erin Ransom, Andrew Lim, Michael Mitzenmacher

• arXiv: Data Structures and Algorithms: Faster Estimation of the Average Degree of a Graph Using Random Edges — 2025-07-10

  Authors: Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri

• arXiv: Data Structures and Algorithms: Faster Algorithms for 2k-1-Stretch Distance Oracles — 2025-07-10

  Authors: Avi Kadria, Liam Roditty

• arXiv: Data Structures and Algorithms: Designing Parallel Algorithms for Community Detection using Arachne — 2025-07-10

  Authors: Fuhuan Li, Zhihui Du, David A. Bader

• arXiv: Computational Geometry: Topological Machine Learning with Unreduced Persistence Diagrams — 2025-07-10

  Authors: Nicole Abreu, Parker B. Edwards, Francis Motta

• arXiv: Computational Geometry: An Improved Bound for Plane Covering Paths — 2025-07-10

  Authors: Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid,...

• arXiv: Computational Complexity: Trainability of Quantum Models Beyond Known Classical Simulability — 2025-07-10

  Authors: Sabri Meyer, Francesco Scala, Francesco Tacchino, Aurelien Lucchi

• arXiv: Computational Complexity: Efficient Algorithms for Quantum Hashing — 2025-07-10

  Authors: Ilnar Zinnatullin, Kamil Khadiev

• ECCC Papers: TR25-089 | Chain Rules for Time-Bounded Kolmogorov Complexity | — 2025-07-09

  Time-bounded conditional Kolmogorov complexity of a string $x$ given $y$, $K^t(x\mid y)$, is the length of a shortest program that, given $y$, prin...

• Computational Complexity: The Customers of the Academy — 2025-07-09

  I had an epiphany reading an article in the Trenton Times when I lived in New Jersey at the turn of the century. The article interviewed companies ...

• arXiv: Data Structures and Algorithms: Parameterized Restless Temporal Path — 2025-07-09

  Authors: Justine Cauvi, Laurent Viennot

• arXiv: Data Structures and Algorithms: Non-Adaptive Evaluation of k-of-n Functions: Tight Gap and a — 2025-07-09

  Authors: Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior

• arXiv: Data Structures and Algorithms: Learning-Augmented Online Covering Problems — 2025-07-09

  Authors: Afrouz Jabal Ameli, Laura Sanita, Moritz Venzin

• arXiv: Data Structures and Algorithms: Instance-Optimal Quantum State Certification with Entangled Measurements — 2025-07-09

  Authors: Ryan O’Donnell, Chirag Wadhwa

• arXiv: Data Structures and Algorithms: An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs — 2025-07-09

  Authors: Bruce W. Brewer, Haitao Wang

• arXiv: Data Structures and Algorithms: A Formal Refutation of the Blockchain Trilemma — 2025-07-09

  Authors: Craig Wright

• arXiv: Data Structures and Algorithms: 25 Additional Problems -- Extension to the Book 125 Problems in Text — 2025-07-09

  Authors: Maxime Crochemore, Thierry Lecroq, Wojtek Rytter

• arXiv: Computational Geometry: k-means considered harmful: On arbitrary topological changes in Mapper — 2025-07-09

  Authors: Mikael Vejdemo-Johansson

• arXiv: Computational Geometry: Fast and Accurate Collision Probability Estimation for Autonomous — 2025-07-09

  Authors: Charles Champagne Cossette, Taylor Scott Clawson, Andrew Feit

• arXiv: Computational Geometry: An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs — 2025-07-09

  Authors: Bruce W. Brewer, Haitao Wang

• arXiv: Computational Complexity: Unitary designs in nearly optimal depth — 2025-07-09

  Authors: Laura Cui, Thomas Schuster, Fernando Brandao, Hsin-Yuan Huang

• arXiv: Computational Complexity: Parameterized Restless Temporal Path — 2025-07-09

  Authors: Justine Cauvi, Laurent Viennot

• arXiv: Computational Complexity: On the Complexity of Problems on Graphs Defined on Groups — 2025-07-09

  Authors: Bireswar Das, Dipan Dey, Jinia Ghosh

• arXiv: Computational Complexity: Lineal Extensions of Kakeya Sets Missing Every ee-Random Point — 2025-07-09

  Authors: Neil Lutz, Spencer Park Martin, Rain White

• arXiv: Computational Complexity: Generalized and Unified Equivalences between Hardness and Pseudoentropy — 2025-07-09

  Authors: Lunjia Hu, Salil Vadhan

• arXiv: Computational Complexity: Complexity Results of Persuasion — 2025-07-09

  Authors: Alban Grastien

• arXiv: Computational Complexity: A Formal Refutation of the Blockchain Trilemma — 2025-07-09

  Authors: Craig Wright

• Nisheeth Vishnoi: What is Intelligence? Layers of Emergence — 2025-07-08

  How Intelligence Arises from Nature, One Layer at a Time

• CS Theory Events: Proof Complexity 2025 — 2025-07-08

  August 11-13, 2025 Oxford, UK https://feasible-math.org/events/PC25/ Proof complexity is a vibrant area in the intersection of computational comple...

• arXiv: Data Structures and Algorithms: Truthful, Credible, and Optimal Auctions for Matroids via Blockchains — 2025-07-08

  Authors: Aadityan Ganesh, Qianfan Zhang

• arXiv: Data Structures and Algorithms: Tight Guarantees for Cut-Relative Survivable Network Design via a — 2025-07-08

  Authors: Nikhil Kumar, JJ Nan, Chaitanya Swamy

• arXiv: Data Structures and Algorithms: The planar edge-coloring theorem of Vizing in Onlog n time — 2025-07-08

  Authors: Patryk Jędrzejczak, Łukasz Kowalik

• arXiv: Data Structures and Algorithms: The Fair Periodic Assignment Problem — 2025-07-08

  Authors: Rolf van Lieshout, Bart van Rossum

• arXiv: Data Structures and Algorithms: Recent Advances in Maximum-Entropy Sampling — 2025-07-08

  Authors: Marcia Fampa, Jon Lee

• arXiv: Data Structures and Algorithms: Quantum Algorithms for Bandits with Knapsacks with Improved Regret and — 2025-07-08

  Authors: Yuexin Su, Ziyi Yang, Peiyuan Huang, Tongyang Li, Yinyu Ye

• arXiv: Data Structures and Algorithms: Online Makespan Scheduling under Scenarios — 2025-07-08

  Authors: Ekin Ergen

• arXiv: Data Structures and Algorithms: Online Convex Optimization with Switching Cost with Only One Single — 2025-07-08

  Authors: Harsh Shah, Purna Chandrasekhar, Rahul Vaze

• arXiv: Data Structures and Algorithms: Maximizing the Margin between Desirable and Undesirable Elements in a — 2025-07-08

  Authors: Sophie Boileau, Andrew Hong, David Liben-Nowell, Alistair Pattison, Anna N. Rafferty, Charlie Roslansky

• arXiv: Data Structures and Algorithms: Liar's vertex-edge domination in subclasses of chordal graphs — 2025-07-08

  Authors: Debojyoti Bhattacharya, Subhabrata Paul

• arXiv: Data Structures and Algorithms: Improved Algorithms for Effective Resistance Computation on Graphs — 2025-07-08

  Authors: Yichun Yang, Rong-Hua Li, Meihao Liao, Guoren Wang

• arXiv: Data Structures and Algorithms: HiPerMotif: Novel Parallel Subgraph Isomorphism in Large-Scale Property — 2025-07-08

  Authors: Mohammad Dindoost, Oliver Alvarado Rodriguez, Bartosz Bryg, Ioannis Koutis, David A. Bader

• arXiv: Data Structures and Algorithms: Heights of butterfly trees — 2025-07-08

  Authors: John Peca-Medlin, Chenyang Zhong

• arXiv: Data Structures and Algorithms: Greedy Dynamic Matching — 2025-07-08

  Authors: Nick Arnosti, Felipe Simon

• arXiv: Data Structures and Algorithms: Distributed Approximation Algorithms for Minimum Dominating Set in — 2025-07-08

  Authors: Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek

• arXiv: Data Structures and Algorithms: Decremental Greedy Polygons and Polyhedra Without Sharp Angles — 2025-07-08

  Authors: David Eppstein

• arXiv: Data Structures and Algorithms: Combination generators with optimal cache utilization and communication — 2025-07-08

  Authors: Xi He, Max. A. Little

• arXiv: Data Structures and Algorithms: Color Distance Oracles and Snippets: Separation Between Exact and — 2025-07-08

  Authors: Noam Horowicz, Tsvi Kopelowitz

• arXiv: Data Structures and Algorithms: Bicriteria approximation for k-edge-connectivity — 2025-07-08

  Authors: Zeev Nutov, Reut Cohen

• arXiv: Data Structures and Algorithms: Agentic Distributed Computing — 2025-07-08

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

• arXiv: Data Structures and Algorithms: A simple algorithm for Combinatorial n-fold ILPs using the Steinitz — 2025-07-08

  Authors: Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi

• arXiv: Data Structures and Algorithms: A note on finding long directed cycles above the minimum degree bound in — 2025-07-08

  Authors: Jadwiga Czyżewska, Marcin Pilipczuk

• arXiv: Computational Geometry: Node-neighbor subnetworks and Hk-core decomposition — 2025-07-08

  Authors: Dinghua Shi, Yang Zhao, Guanrong Chen

• arXiv: Computational Geometry: Input-Sensitive Reconfiguration of Sliding Cubes — 2025-07-08

  Authors: Hugo Akitaya, Matias Korman, Frederick Stock

• arXiv: Computational Geometry: Decremental Greedy Polygons and Polyhedra Without Sharp Angles — 2025-07-08

  Authors: David Eppstein

• arXiv: Computational Geometry: Computing Largest Subsets of Points Whose Convex Hulls have Bounded Area — 2025-07-08

  Authors: Gianmarco Picarella, Marc van Kreveld, Frank Staals, Sjoerd de Vries

• arXiv: Computational Geometry: Approximation and Hardness of Polychromatic TSP — 2025-07-08

  Authors: Thomas Schibler, Subhash Suri, Jie Xue

• arXiv: Computational Complexity: Testing for Renamability to Classes of Clause Sets — 2025-07-08

  Authors: Albert Brandl, Christian G. Fermüller, Gernot Salzer

• arXiv: Computational Complexity: PFCS: Prime Factorization Cache System for Deterministic Data — 2025-07-08

  Authors: Duy Le

• arXiv: Computational Complexity: Low sets for counting functions — 2025-07-08

  Authors: Yaroslav Ivanashev

• David Eppstein: Ready lists — 2025-07-07

  Beginning computer science students learn about stacks, queues, and priority queues, different ways of organizing and ordering a collection of task...

• Ben Recht: You keep using that word — 2025-07-07

• Gil Kalai: Happy Birthday Saharon Shelah and Yuri Gurevich! — 2025-07-07

  Let me briefly report on two birthday conferences for long-time friends and colleagues Saharon Shelah and Yuri Gurevich. Yuri fest took place in Mu...

• arXiv: Data Structures and Algorithms: On the Approximability of Train Routing and the Min-Max Disjoint Paths — 2025-07-07

  Authors: Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, Laura Vargas Koch

• arXiv: Data Structures and Algorithms: Going Beyond Surfaces in Diameter Approximation — 2025-07-07

  Authors: Michał Włodarczyk

• arXiv: Data Structures and Algorithms: Discovering Algorithms with Computational Language Processing — 2025-07-07

  Authors: Theo Bourdais, Abeynaya Gnanasekaran, Houman Owhadi, Tuhin Sahai

• arXiv: Data Structures and Algorithms: Bayesian Optimal Stopping with Maximum Value Knowledge — 2025-07-07

  Authors: Pieter Kleer, Daan Noordenbos

• arXiv: Data Structures and Algorithms: Barvinok's interpolation method meets Weitz's correlation decay approach — 2025-07-07

  Authors: Ferenc Bencs, Guus Regts

• arXiv: Computational Complexity: Quantum Computation with Correlated Measurements: Implications for the — 2025-07-07

  Authors: David Miloschewsky, Supartha Podder

• arXiv: Computational Complexity: On the Approximability of Train Routing and the Min-Max Disjoint Paths — 2025-07-07

  Authors: Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, Laura Vargas Koch

• arXiv: Computational Complexity: Complexity of learning matchings and half graphs via edge queries — 2025-07-07

  Authors: Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev

• arXiv: Computational Complexity: Are Depth-2 Regular Expressions Hard to Intersect? — 2025-07-07

  Authors: Rocco Ascone, Giulia Bernardini, Alessio Conte, Veronica Guerrini, Giulia Punzi

• arXiv: Computational Complexity: A Near-Optimal Polynomial Distance Lemma Over Boolean Slices — 2025-07-07

  Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan

• Computational Complexity: The New Lower Bound on Busy Beaver of 6. — 2025-07-06

   We denote the busy beaver function by BB.

• ECCC Papers: TR25-088 | Factorization norms and an inverse theorem for MaxCut | — 2025-07-06

  We prove that Boolean matrices with bounded $\gamma_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros subm...

• 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 — 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 — 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 — 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 — 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 — 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 — 2025-07-03

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

• arXiv: Data Structures and Algorithms: A Deterministic Partition Tree and Applications — 2025-07-03

  Authors: Haitao Wang

• arXiv: Computational Geometry: Search-Based Robot Motion Planning With Distance-Based Adaptive Motion — 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 — 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. — 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 InApproximability 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 — 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 — 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 — 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 — 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 FAC0 to FAC1 via Discrete — 2025-07-01

  Authors: Melissa Antonelli, Arnaud Durand, Juha Kontinen