004.021 — Алгоритмы

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt, Conrad Schecker · 2026

The Gallai Vertex Problem is $Θ_2^p$-Complete Amir Nikabadi, Eva Rotenberg, Lasse Wulf · 2026

Polyhedral Instability Governs Regret in Online Learning Yuetai Li, Fengqing Jiang, Yichen Feng, Kaiyuan Zheng, Luyao Niu, Bhaskar Ramasubramanian, Basel Alomair, Linda Bushnell, Radha Poovendran · 2026

Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality Jingwei Ji · 2026

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing Sutanay Bhattacharjee, Ameya Panse, Jayalal Sarma · 2026

Learning-Augmented Online Scheduling with Parsimonious Preemption Mugen Blue, Sungjin Im, Alexander Lindermayr · 2026

Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Diptarka Chakraborty, Arya Mazumdar, Barna Saha, Alvin Hong Yao Yan · 2026

Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Niels Holtgrefe, Jannik Schestag · 2026

Efficient Uniform Sampling of Surjections via their Profiles Arnaud Carayol, Pablo Rotondo · 2026

Rounding Almost Commuting Hamiltonians Islam Faisal, Anand Natarajan, Alexander Poremba · 2026

Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph Kamil Khadiev, Ilnur Valeev · 2026

Creating Robust and Fair Graph Structures for Connectivity and Clustering Kushagra Chatterjee · 2026

Treewidth of the $n \times n$ toroidal grid Tatsuya Gima, Hiraku Morimoto, Yuto Okada, Yota Otachi · 2026

Fibonacci Heap Data Structure · 2007

Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50 David Kirkpatrick · 2013

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis · 2026

Space-Time Trade-off in Integer Linear Scaling Rounded to the Nearest Integer through Multiplicative and Additive Decomposition Kyeong Soo Kim · 2026

Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma · 2026

Adjacency Matrix Data Structure · 2007

Beyond the Half-Approximation: Fair and Efficient Online Class Matching Sander Borst, Max Springer · 2026

Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains Nicholas Zhao · 2026

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Akash Kumar, Abhiruk Lahiri, C. Seshadhri · 2026

Optimal Dimension-Free Sampling for Regularized Classification Meysam Alishahi, Alexander Munteanu, Simon Omlor, Jeff M. Phillips · 2026

Leftist Heap Data Structure · 2007

Array Data Structure · 2007

Unambiguous Parity‐Query Complexity Dmytro Gavinsky · 2025

Other Complexity Classes and Measures Eric Allender, Michael Loui, Kenneth Regan · 2009

Basic Notions in Computational Complexity Tao Jiang, Ming Li, Bala Ravikumar · 2009

Basic Searching Algorithms · 2007

Quoridor is PSPACE-Hard Marius Drop, Benjamin G. Rin, Finn van der Velde · 2026

A sharp interaction-degree threshold for simulating QAOA Ralfs Āboliņš, Andris Ambainis · 2026

Extending CDCL to disjunctions of parity equations Paul Beame, Glenn Sun · 2026

On the Limits of PAC Learning of Networks from Opinion Dynamics Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini · 2026

Entropy of pebble automata and space complexity J. Andres Montoya · 2026

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH Rishav Gupta, Bingkai Lin, Xin Zheng · 2026

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak, George Osipov, Fahad Panolan, Mateusz Rychlicki · 2026

Proof Systems Based on Structured Circuits Matthäus Micun, Christoph Berkholz · 2026

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing Joshua M. Courtney · 2026

Quantum state isomorphism problems for groups Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban, Arsalan Motamedi · 2026

The Secretary Problem with a Stochastic Precursor Franziska Eberle, Alexander Lindermayr · 2026

Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees Christian Janos Lebeda, David Erb, Tudor Cebere, Aurélien Bellet · 2026

On the Parameterized Complexity of Min-Sum-Radii Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, Melanie Schmidt · 2026

Optimal Testing of Reed-Muller Codes with an Online Adversary Esty Kelman, Uri Meir, Kai Zhe Zheng · 2026

Compact Trie Data Structure · 2007

Splay Tree Data Structure · 2007

Patricia Trie Data Structure · 2007

Efficient algorithms and data structures for indexing DNA sequence data Kamil Salikhov · 2024

B+-Tree Data Structure · 2007

Open Addressing Data Structure · 2007

Pairing Heap Data Structure · 2007

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition Peter Davies-Peck · 2026

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds Samuel German · 2026

Clustering with Locally Bounded Ignorance Jaroslav Garvardt, Christian Komusiewicz · 2026

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov · 2026

Upper Bounds for Symmetric Approximate Bounded Indistinguishability Christopher Williamson · 2026

Non-Redundancy of Low-Arity Symmetric Boolean CSPs Amatya Sharma, Santhoshini Velusamy · 2026

Enhanced and Efficient Reasoning in Large Learning Models Leslie G. Valiant · 2026

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets Ali Asadi, Krishnendu Chatterjee, Alipasha Montaseri, Ali Shafiee · 2026

Parse indexing for choosing pseudo-MEMs Travis Gagie · 2026

Tolerant Testing for Unique Games Yuichi Yoshida · 2026

On efficient robust regression with subquadratic samples Deeksha Adil, Jarosław Błasiok, Hongjie Chen, Deepak Narayanan Sridharan · 2026

Linear Kernels for $l$-Exact Component Order Connectivity Yuxi Liu, Mingyu Xiao · 2026

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth Yuxi Liu, Kangyi Tian, Mingyu Xiao · 2026

Block-Sphere Vector Quantization Heesang Ann, Joongkyu Lee, Min-hwan Oh · 2026

Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations Claire Chang, Arin Khare, David Shmoys · 2026

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model Aleksey Upirvitskiy, Aleksandr Levin · 2026

Finite Sample Bounds for Learning with Score Matching Devin Smedira, Abhijith Jayakumar, Sidhant Misra, Marc Vuffray, Andrey Y. Lokhov · 2026

Stochastic Matching via Local Sparsification Sara Ahmadian, Edith Cohen, Mohammad Roghani · 2026

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order Niv Buchbinder, Moran Feldman, Siyue Liu, Sherry Sarkar · 2026

Graphs and Graph Algorithms · 2007

DialSort: Non-Comparative Integer Sorting via the Self-Indexing Principle: Architecture, Implementation, and Substrate-Aware Analysis Alexander Narvaez · 2026

Improved Parallel Algorithms for EF1 Allocations Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang, Gregory Kehne · 2026

Online Graph Embedding in Star Graphs Julien Dallot, Darya Melnyk, Maciej Pacut, Stefan Schmid · 2026

Iterative Chow Filtering for Learning with Distribution Shift Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan · 2026

Online Orthogonal Vectors Revisited Karthik Gajulapalli, Alexander Golovnev, Samuel King, Sidhant Saraogi · 2026

The stochastic block model has the overlap graph property for modularity Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel Pralat, Fiona Skerman, Yasmin Tousinejad · 2026

Chasing Small Sets Optimally Against Adaptive Adversaries Christian Coester, Alexa Tudose · 2026

Performance bounds for nearest neighbor search with k-d trees Marco Bazzani, Sanjoy Dasgupta · 2026

Streaming Complexity Separations for Dense and Sparse Graphs Yang P. Liu, Hoai-An Nguyen, Noah G. Singer, David P. Woodruff · 2026

Towards infinite PCSP: a dichotomy for monochromatic cliques Demian Banakh, Alexey Barsukov, Tamio-Vesa Nakajima · 2026

Multi-Prover Interactive Proof Systems with Leakage Vahid R. Asadi, Atsuya Hasegawa, François Le Gall · 2026

Optimal Inapproximability of Generalized Linear Equations over a Finite Group Amey Bhangale, Yezhou Zhang · 2026

Modelling Network Resilience: The Complexity of Some Graph Division Games Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Antonio Lauerbach, Alexander Wolff · 2026

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought Moritz Brösamle, Stephan Eckstein · 2026

Complexity of Finding and Enumerating Interconnection Trees Noé Demange, Yann Strozecki · 2026

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians Ranitha Mataraarachchi, François Le Gall, Suguru Tamaki · 2026

Computational Complexity Kent D. Lee, Steve Hubbard · 2015

Correction to “Unambiguous Parity‐Query Complexity” · 2026

Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm Christian Møller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille, Vedrana Andersen Dahl, Inge Li Gørtz · 2026

Low-Cost Arborescence Under Edge Faults Dipan Dey, Telikepalli Kavitha · 2026

Min-Max Optimization Requires Exponentially Many Queries Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender · 2026

Provable Quantization with Randomized Hadamard Transform Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov · 2026

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs Quinten De Man, Gilvir Gill, Michael A. Bender, Laxman Dhulipala, David Tench · 2026

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand Ioannis Caragiannis, Kostas Kollias, Mohammad Roghani, Aaron Schild, Ali Kemal Sinop · 2026

Optimizing Line Segment Inspection with Limited-Range Drones José-Miguel Díaz-Báñez, José-Manuel Higes, Alina Kasiuk, Inmaculada Ventura · 2026

More efficient PBWT prefix-array access via batching Travis Gagie · 2026

B Complexity Analysis · 2007

Basic Searching Algorithms · 2005

Algorithms Alan Parker · 2018

CorBin: Generate High-Dimensional Binary Data with Correlation Structures · 2019

COLLECTION DATA STRUCTURES AND ALGORITHMS · 2007

Algorithms+Data Structures = Programs · 2024

Quantum algorithms for path and cycle containment problems Arjan Cornelissen, Amin Shiraz Gilani, Subhasree Patro · 2026

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings Balagopal Komarath, Harshil Mittal, Jayalal Sarma · 2026

Understanding Robust Catalytic Computing Michal Koucký, Ian Mertz, Sasha Sami · 2026

Robustness and Transferability of Pix2Geomodel for Bidirectional Facies Property Translation in a Complex Reservoir Abdulrahman Al-Fakih, Nabil Sariah, Ardiansyah Koeshidayatullah, Sherif Hanafy, SanLinn I. Kaka · 2026

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases Sanjeev Khanna, Aaron Putterman, Junkai Song · 2026

Rigid homotopies for sampling from algebraic varieties: a Waring structure complexity model Abigail R. Jones, Kisun Lee, Jose Israel Rodriguez · 2026

The Scaling Properties of Implicit Deductive Reasoning in Transformers Enrico Vompa, Tanel Tammet · 2026

Adjacency List Data Structue · 2007

Binary Heap Data Structure · 2007

Trie Data Structure · 2007

Advanced Sorting Algorithms · 2005

RETRACTION: Interactive Algorithms in Complex Image Processing Systems Based on Big Data Complexity · 2025

Basic Sorting Algorithms · 2005

The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives Ankur Moitra, Andrej Risteski, Dhruv Rohatgi · 2026

Connectivity augmentation is fixed-parameter tractable Tuukka Korhonen, Mikkel Thorup · 2026

Maximizing Reachability via Shifting of Temporal Paths Argyrios Deligkas, Michelle Döring, Eduard Eiben, George Skretas, Georg Tennigkeit · 2026

On the LSH Distortion of Ulam and Cayley Similarities Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Erasmo Tani · 2026

Quad Tree Data Structure · 2007

Sorted Array Data Structure · 2007

KD-Tree Data Structure · 2007

Tracked Array Data Structure · 2007

Complexity-scalable transform coding using variable complexity algorithms W. Pan, A. Ortega · 2024

Basic Sorting Algorithms · 2007

Advanced Algorithms · 2005

Parameterized Complexity of Generalized Vertex Cover Problems Jiong Guo, Rolf Niedermeier, Sebastian Wernicke · 2005

Resilient Algorithms and Data Structures Giuseppe F. Italiano · 2010

Complexity of Algorithms · 2000

Complexity Analysis · 2007

Algorithms, Data Structures, and Complexity: A Complexity-First Pedagogical Framework Valeriu Ungureanu · 2026

A case study in comparison based complexity: Finding the nearest value(s) Walter Cunto, J. Ian Munro, Patricio V. Poblete · 2024

On the Complexity of Scheduling Conditional Real-Time Code Samarjit Chakraborty, Thomas Erlebach, Lothar Thiele · 2001

Complexity Classes Eric Allender, Michael Loui, Kenneth Regan · 2009

Deterministically finding an element of large order in $\mathbb{Z}_N^*$ Itamar Nir · 2026

A Scalable and Unified Framework to Weighted Rank Aggregation Amir Carmel, Debarati Das, Tien-Long Nguyen · 2026

Dynamic Edge Coloring of Forests Haim Kaplan, David Naori, Yaniv Sadeh · 2026

State Canonization and Early Pruning in Width-Based Automated Theorem Proving Mateus de Oliveira Oliveira, Sam Urmian · 2026

Algorithms And Data Structures For Association Rule Mining And Its Complexity Analysis Alexander Prutzkow* · 2018