CS Theory RSS
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