1. k-Coloring is Faster than Computing the Chromatic Number
   2026/07/28 by Or Zamir · 1 voice
   #cs.DS
2. The Knapsack Secretary Problem is Strictly Harder Than the Secretary Problem
   2026/07/24 by Eric Balkanski, Jason Chatzitheodorou, Dimitris Fotakis +1 · 1 citation
   #cs.DS
3. Reachability in Directed Acyclic Graphs with Near-Linear Cut Queries
   2026/07/23 by Sanjeev Khanna, Aaron Putterman, Junkai Song · 1 citation
   #cs.DS
4. The Polynomial-Time Low-Degree Conjecture is False
   2026/07/22 by Songtao Mao · 1 voice
   #cs.CC #cs.DS
5. Bellman-Ford in Almost-Linear Time
   2026/07/21 by Isaac M. Hair, George Z. Li, Jason Li +1 · 1 voice
   #cs.DS
6. Splay trees are almost dynamically optimal
   2026/07/20 by Petr Chmel, Bernhard Haeupler, Richard Hladík +5 · 1 voice · 1 citation
   #cs.DS
7. Nonexistence of Simultaneously EF1 and Pareto Optimal Allocations for Submodular Valuations
   2026/07/20 by Harish Chandramouleeswaran, Prajakta Nimbhorkar · 1 citation
   #cs.GT #cs.DS
8. Stringological sequence prediction II: Right-to-left automaticity and related complexity measures
   2026/07/19 by Vanessa Kosoy · 1 voice
   #cs.FL #cs.DS #cs.LG
9. Semi-Streaming Matching in a Single Pass II: Greedy is Optimal
   2026/07/16 by Sepehr Assadi, Max Jiang, Mars Xiang · 5 voices
   #cs.DS #cs.CC
10. The 2026 Algorithmic Information Theory Data Compression Challenge
    2026/06/16 by André Ribeiro, Rúben Garrido, Violeta Ramos +28 · 2 voices
    #cs.IT #cs.DS
11. Counterexamples to Wegner's Conjecture for Rectangles
    2026/06/16 by Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman +1 · 2 voices
    Computer Science · Mathematics · #cs.CG #cs.DM #cs.DS #math.CO
12. A canonical generalization of OBDD
    2026/04/07 by Florent Capelli, YooJung Choi, Stefan Mengel +2 · 6 voices
    #cs.AI #cs.DS
13. Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
    2026/03/30 by Bartłomiej Dudek, Nick Fischer, Geri Gokaj +4 · 1 voice
    #cs.DS
14. Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse
    2026/03/29 by Gregory Magarshak · 1 voice
    Computer Science · #cs.LG #cs.AI #cs.CL #cs.DS #cs.IR #cs.IT
15. The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
    2026/03/25 by Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +3 · 2 voices
    #math.CO #cs.CG #cs.DM #cs.DS
16. A more accurate rational non-commutative algorithm for multiplying 4x4 matrices using 48 multiplications
    2026/03/19 by Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic · 1 voice
    Computer Science · #cs.DS #cs.SC
17. Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation
    2026/02/24 by Keigo Oka · 18 voices
    #cs.DS
18. Flip Distance Between Triangulations of Convex Polygons is NP-Complete
    2026/02/26 by Joseph Dorfer · 5 voices
    #cs.CG #cs.CC #cs.DM #cs.DS #math.CO
19. The S-Hamiltonian Cycle Problem
    2026/02/18 by Antoine Amarilli, Arthur Lombardo, Mikaël Monet · 2 voices
    #cs.DS
20. A Faster Directed Single-Source Shortest Path Algorithm
    2026/02/08 by Ran Duan, Xiao Mao, Xinkai Shu +1 · 1 voice
    Computer Science · #cs.DS
21. Adaptive Hashing: Faster Hash Functions with Fewer Collisions
    2026/02/05 by Gábor Melis · 1 voice
    Computer Science · #cs.DS
22. A 58-Addition, Rank-23 Scheme for General 3x3 Matrix Multiplication
    2025/12/26 by A. I. Perminov, Perminov, A. I. · 3 voices
    #cs.DS
23. Accuracy and resource advantages of quantum eigenvalue estimation with non-Hermitian transcorrelated electronic Hamiltonians
    2025/11/26 by Alexey Uvarov, Artur F. Izmaylov, Uvarov, Alexey +1 · 1 voice · 1 citation
    Chemistry · Computer Science · Physics and Astronomy · #Advanced Physical and Chemical Molecular Interactions #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Non-Hermitian Physics #cs.DS #physics.chem-ph #quant-ph
24. No Cords Attached: Coordination-Free Concurrent Lock-Free Queues
    2025/11/12 by Yusuf Motiwala, Motiwala, Yusuf · 2 voices
    Computer Science · #Distributed systems and fault tolerance #Parallel Computing and Optimization Techniques #Software System Performance and Reliability #cs.DC #cs.DS #cs.PF
25. Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
    2025/10/24 by Eleon Bach, Alexander E. Black, Bach, Eleon +5 · 8 voices
    #cs.DS #math.OC
26. Uniformity Testing under User-Level Local Privacy
    2025/10/21 by Clément L. Canonne, Canonne, Clément L., Abigail Gentle +3 · 2 voices · 1 citation
    #cs.DS #cs.CR #cs.DM
27. Efficient learning of bosonic Gaussian unitaries
    2025/10/07 by Marco Fanizza, Vishnu Iyer, Fanizza, Marco +7 · 2 voices · 2 citations
    #quant-ph #cs.DS #cs.LG
28. Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
    2025/10/03 by Dhruv Rohatgi, Rohatgi, Dhruv, Abhishek Shetty +11 · 1 voice · 2 citations
    Computer Science · #Formal Methods in Verification #Machine Learning and Algorithms #Natural Language Processing Techniques #cs.DS #cs.LG
29. Necessity of Block Designs for Optimal Locally Private Distribution Estimation
    2025/08/07 by Abigail Gentle, Gentle, Abigail · 2 voices · 2 citations
    #cs.IT #cs.CR #cs.DS
30. The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
    2025/07/24 by Jiale Chen, Yalda Shabanzadeh, Chen, Jiale +7 · 3 citations
    Computer Science · Mathematics · #Advanced Data Compression Techniques #Advanced Vision and Imaging #Image and Object Detection Techniques #cs.DS #cs.IT #cs.LG #math.IT

more