Replaced article(s) found for cs.DS. https://arxiv.org/list/cs.DS/new
[1/1]:
- Language Generation in the Limit: Noise, Loss, and Feedback
Yannan Bai, Debmalya Panigrahi, Ian Zhang
https://arxiv.org/abs/2507.15319 https://mastoxiv.page/@arXiv_csDS_bot/114896208560390692
- Online Firefighting on Cactus Graphs
Max Hugen, Bob Krekelberg, Alison Hsiang-Hsuan Liu
https://arxiv.org/abs/2509.22277 https://mastoxiv.page/@arXiv_csDS_bot/115286656155128312
- Improved Extended Regular Expression Matching
Philip Bille, Inge Li G{\o}rtz, Rikke Schjeldrup Jessen
https://arxiv.org/abs/2510.09311 https://mastoxiv.page/@arXiv_csDS_bot/115365884736976741
- Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
Andreas G\"obel, Janosch Ruff, Leon Schiller
https://arxiv.org/abs/2511.20376 https://mastoxiv.page/@arXiv_csDS_bot/115614988823215273
- Analysis of Shuffling Beyond Pure Local Differential Privacy
Shun Takagi, Seng Pei Liew
https://arxiv.org/abs/2601.19154 https://mastoxiv.page/@arXiv_csDS_bot/115971701218309765
- Exact (n 2) Comparison Complexity for the N-Repeated Element Problem
Andrew Au
https://arxiv.org/abs/2601.21202 https://mastoxiv.page/@arXiv_csDS_bot/115982906572495225
- A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning
Pedro Valdeira, Yuejie Chi, Cl\'audia Soares, Jo\~ao Xavier
https://arxiv.org/abs/2309.09977
- Optimal Sequential Flows
Hugo Gimbert, Corto Mascle, Patrick Totzke
https://arxiv.org/abs/2511.13806 https://mastoxiv.page/@arXiv_mathOC_bot/115575399809016779
toXiv_bot_toot
Replaced article(s) found for physics.ins-det. https://arxiv.org/list/physics.ins-det/new
[1/1]:
- A nonlinear multiphysics model for the design validation of the ASTAROTH copper-steel cryogenic c...
Alessandria, Armani, Coelli, Cortis, D'Angelo, Martinenghi, Monti, Orlandi, Sorbi, Toso, Zani
https://arxiv.org/abs/2511.22529 https://mastoxiv.page/@arXiv_physicsinsdet_bot/115643479525772405
- Quantum noise in a squeezed-light-enhanced multiparameter quantum sensor
Aleksandra Sierant, Diana M\'endez-Avalos, Santiago Tabares Giraldo, Morgan W. Mitchell
https://arxiv.org/abs/2506.08190 https://mastoxiv.page/@arXiv_quantph_bot/114664134107738542
- Evaluation of PID Performance at CEPC and Optimization with Combined dN/dx and Time-of-Flight Data
Dian Yu, Houqian Ding, Yongfeng Zhu, Ming Qi, Kun Liu, Yunyun Fan
https://arxiv.org/abs/2507.18164 https://mastoxiv.page/@arXiv_hepex_bot/114912892827917148
toXiv_bot_toot
@… are you a bot? your account seems very bot like!
[2026-02-10 Tue (UTC), 26 new articles found for hep-ph High Energy Physics - Phenomenology]
toXiv_bot_toot
GoDaddy integrates Cloudflare's AI Crawl Control into its hosting platform, enabling site owners to block, permit, or possibly monetize automated crawler access (Alistair Barr/Business Insider)
https://www.businessinsider.com/cloudflare
[2026-02-09 Mon (UTC), 16 new articles found for math.AP Analysis of PDEs]
toXiv_bot_toot
[2026-02-10 Tue (UTC), 3 new articles found for cs.OS Operating Systems]
toXiv_bot_toot
[2026-02-09 Mon (UTC), 3 new articles found for math.AC Commutative Algebra]
toXiv_bot_toot
BLOATUS
bot by @…
No laws were broken in the making of this bot: please don't ruin my life.
#satire #potus45
Crosslisted article(s) found for cs.DS. https://arxiv.org/list/cs.DS/new
[1/1]:
- Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm
Giacomo Belli, Michele Amoretti
https://arxiv.org/abs/2602.06535 https://mastoxiv.page/@arXiv_quantph_bot/116040046858615026
- Induced Cycles of Many Lengths
Maria Chudnovsky, Ilya Maier
https://arxiv.org/abs/2602.06874 https://mastoxiv.page/@arXiv_mathCO_bot/116039905295882594
- Circuit Diameter of Polyhedra is Strongly Polynomial
Bento Natura
https://arxiv.org/abs/2602.06958 https://mastoxiv.page/@arXiv_mathOC_bot/116040016711065918
toXiv_bot_toot
Crosslisted article(s) found for physics.ins-det. https://arxiv.org/list/physics.ins-det/new
[1/1]:
- Shallow Trap States Control Electrical Performance of Amorphous Oxide Semiconductor Thin-Film Tra...
Mattsson, Lee, Malmberg, Parker, Vogt, Kim, Hong, Yun, Ha, Lee, Cheong, Wager, Graham
https://arxiv.org/abs/2602.06329 https://mastoxiv.page/@arXiv_physicsappph_bot/116039613646926885
toXiv_bot_toot
[2026-02-09 Mon (UTC), no new articles found for cs.OS Operating Systems]
toXiv_bot_toot
Partial fraction decompositions on hyperplane arrangements
Claire de Korte, Teresa Yu
https://arxiv.org/abs/2602.06531 https://arxiv.org/pdf/2602.06531 https://arxiv.org/html/2602.06531
arXiv:2602.06531v1 Announce Type: new
Abstract: We initiate the study of partial fraction decompositions (PFDs) in several variables using tools from commutative algebra. We give criteria for when a rational function with poles on a hyperplane arrangement has a desirable PFD. Our criteria are obtained by examining the primary decomposition of ideals coming from hyperplane arrangements. We then present an algorithm for finding a PFD that satisfies properties desired by physicists, and demonstrate the effectiveness of this algorithm for computing large examples coming from Feynman integrals.
toXiv_bot_toot
Fiberace
bot by @…
No laws were broken in the making of this bot: let's not make entertainment lead to internment.
#satire #potus45
Crosslisted article(s) found for hep-ph. https://arxiv.org/list/hep-ph/new
[1/1]:
- "Observations on the possible electromagnetic nature of nucleon interactions and pions" -- histor...
Mathias Bostr\"om, Drew F. Parsons
[2026-02-09 Mon (UTC), 2 new articles found for cs.DS Data Structures and Algorithms]
toXiv_bot_toot
Fork, Explore, Commit: OS Primitives for Agentic Exploration
Cong Wang, Yusheng Zheng
https://arxiv.org/abs/2602.08199 https://arxiv.org/pdf/2602.08199 https://arxiv.org/html/2602.08199
arXiv:2602.08199v1 Announce Type: new
Abstract: AI agents increasingly perform agentic exploration: pursuing multiple solution paths in parallel and committing only the successful one. Because each exploration path may modify files and spawn processes, agents require isolated environments with atomic commit and rollback semantics for both filesystem state and process state. We introduce the branch context, a new OS abstraction that provides: (1) copy-on-write state isolation with independent filesystem views and process groups, (2) a structured lifecycle of fork, explore, and commit/abort, (3) first-commit-wins resolution that automatically invalidates sibling branches, and (4) nestable contexts for hierarchical exploration. We realize branch contexts in Linux through two complementary components. First, BranchFS is a FUSE-based filesystem that gives each branch context an isolated copy-on-write workspace, with O(1) creation, atomic commit to the parent, and automatic sibling invalidation, all without root privileges. BranchFS is open sourced in https://github.com/multikernel/branchfs. Second, branch() is a proposed Linux syscall that spawns processes into branch contexts with reliable termination, kernel-enforced sibling isolation, and first-commit-wins coordination. Preliminary evaluation of BranchFS shows sub-350 us branch creation independent of base filesystem size, and modification-proportional commit overhead (under 1 ms for small changes).
toXiv_bot_toot
Characterization of Some Graphs Realizing Regularity Bounds for Binomial Edge Ideals
Nursel Erey, Muhammed Ergen, Takayuki Hibi
https://arxiv.org/abs/2602.06524 https://arxiv.org/pdf/2602.06524 https://arxiv.org/html/2602.06524
arXiv:2602.06524v1 Announce Type: new
Abstract: In this paper, we characterize all graphs $G$ satisfying \[\operatorname{reg}(S/J_G)=\ell(G)=c(G)\] where $\ell(G)$ is the sum of the lengths of the longest induced paths in each connected component of $G$ and $c(G)$ is the number of the maximal cliques of $G$. We also characterize all connected graphs $G$ that satisfy \[\operatorname{reg}(S/J_G)=\ell(G)=|V(G)|-\omega(G) 1\] where $\omega(G)$ is the clique number of $G$. Moreover, we investigate the possible values of the regularity of $S/J_G$ within the intervals $[\ell(G), c(G)]$ and $[\ell(G), |V(G)|-\omega(G) 1]$.
toXiv_bot_toot
Cheetolini
bot by @…
No laws were broken in the making of this bot: please don't extraordinarily rendition me to a black site.
#satire #potus45
Hard thermal contributions to phase transition observables at NNLO
Fabio Bernardo, Mikael Chala, Luis Gil, Philipp Schicho
https://arxiv.org/abs/2602.06962 https://
[2026-02-10 Tue (UTC), 13 new articles found for cs.DS Data Structures and Algorithms]
toXiv_bot_toot
HALO: A Fine-Grained Resource Sharing Quantum Operating System
John Zhuoyang Ye, Jiyuan Wang, Yifan Qiao, Jens Palsberg
https://arxiv.org/abs/2602.07191 https://arxiv.org/pdf/2602.07191 https://arxiv.org/html/2602.07191
arXiv:2602.07191v1 Announce Type: new
Abstract: As quantum computing enters the cloud era, thousands of users must share access to a small number of quantum processors. Users need to wait minutes to days to start their jobs, which only takes a few seconds for execution. Current quantum cloud platforms employ a fair-share scheduler, as there is no way to multiplex a quantum computer among multiple programs at the same time, leaving many qubits idle and significantly under-utilizing the hardware. This imbalance between high user demand and scarce quantum resources has become a key barrier to scalable and cost-effective quantum computing.
We present HALO, the first quantum operating system design that supports fine-grained resource-sharing. HALO introduces two complementary mechanisms. First, a hardware-aware qubit-sharing algorithm that places shared helper qubits on regions of the quantum computer that minimize routing overhead and avoid cross-talk noise between different users' processes. Second, a shot-adaptive scheduler that allocates execution windows according to each job's sampling requirements, improving throughput and reducing latency. Together, these mechanisms transform the way quantum hardware is scheduled and achieve more fine-grained parallelism.
We evaluate HALO on the IBM Torino quantum computer on helper qubit intense benchmarks. Compared to state-of-the-art systems such as HyperQ, HALO improves overall hardware utilization by up to 2.44x, increasing throughput by 4.44x, and maintains fidelity loss within 33%, demonstrating the practicality of resource-sharing in quantum computing.
toXiv_bot_toot
Constructing Koszul filtrations: existence and non-existence for G-quadratic algebras
Emily Berghofer, Lisa Nicklasson, Peder Thompson, Thomas Westerb\"ack
https://arxiv.org/abs/2602.06490 https://arxiv.org/pdf/2602.06490 https://arxiv.org/html/2602.06490
arXiv:2602.06490v1 Announce Type: new
Abstract: Given a standard graded algebra over a field, we consider the relationship between G-quadraticity and the existence of a Koszul filtration. We show that having a quadratic Gr\"obner basis implies the existence of a Koszul filtration for toric algebras equipped with the degree reverse lexicographic term order and for algebras defined by binomial edge ideals. We also resolve a conjecture of Ene, Herzog, and Hibi by constructing an example where this implication fails. These results are underpinned by algorithms we develop for constructing Koszul filtrations. We also demonstrate the utility of these algorithms on the pinched Veronese algebra.
toXiv_bot_toot
Il Douché
bot by @…
No laws were broken in the making of this bot: no waterboarding please and thank you.
#satire #potus45
Revisiting the Electroweakino Sector of the Baryon Number Violating MSSM at the HL-LHC with Deep Neural Networks
Rahool Kumar Barman, Arghya Choudhury, Subhadeep Sarkar
https://arxiv.org/abs/2602.06957
A Faster Directed Single-Source Shortest Path Algorithm
Ran Duan, Xiao Mao, Xinkai Shu, Longhui Yin
https://arxiv.org/abs/2602.07868 https://arxiv.org/pdf/2602.07868 https://arxiv.org/html/2602.07868
arXiv:2602.07868v1 Announce Type: new
Abstract: This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n} \sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].
toXiv_bot_toot
Equilibria: Fair Multi-Tenant CXL Memory Tiering At Scale
Kaiyang Zhao, Neha Gholkar, Hasan Maruf, Abhishek Dhanotia, Johannes Weiner, Gregory Price, Ning Sun, Bhavya Dwivedi, Stuart Clark, Dimitrios Skarlatos
https://arxiv.org/abs/2602.08800 https://arxiv.org/pdf/2602.08800 https://arxiv.org/html/2602.08800
arXiv:2602.08800v1 Announce Type: new
Abstract: Memory dominates datacenter system cost and power. Memory expansion via Compute Express Link (CXL) is an effective way to provide additional memory at lower cost and power, but its effective use requires software-level tiering for hyperscaler workloads. Existing tiering solutions, including current Linux support, face fundamental limitations in production deployments. First, they lack multi-tenancy support, failing to handle stacked homogeneous or heterogeneous workloads. Second, limited control-plane flexibility leads to fairness violations and performance variability. Finally, insufficient observability prevents operators from diagnosing performance pathologies at scale.
We present Equilibria, an OS framework enabling fair, multi-tenant CXL tiering at datacenter scale. Equilibria provides per-container controls for memory fair-share allocation and fine-grained observability of tiered-memory usage and operations. It further enforces flexible, user-specified fairness policies through regulated promotion and demotion, and mitigates noisy-neighbor interference by suppressing thrashing.
Evaluated in a large hyperscaler fleet using production workloads and benchmarks, Equilibria helps workloads meet service level objectives (SLOs) while avoiding performance interference. It improves performance over the state-of-the-art Linux solution, TPP, by up to 52% for production workloads and 1.7x for benchmarks. All Equilibria patches have been released to the Linux community.
toXiv_bot_toot
Don Whoreleon
bot by @…
No laws were broken in the making of this bot: no investigating me please.
#satire #potus45
Parametric-Resonance Production of QCD Axions
Pirzada, Yu Gao, Qiaoli Yang
https://arxiv.org/abs/2602.06922 https://arxiv.org/pdf/2602.06922
Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
Wojciech Gabryelski, Zbigniew Go{\l}\c{e}biewski, Martin P\'epin
https://arxiv.org/abs/2602.08471 https://arxiv.org/pdf/2602.08471 https://arxiv.org/html/2602.08471
arXiv:2602.08471v1 Announce Type: new
Abstract: We propose two efficient algorithms for generating uniform random directed acyclic graphs, including an asymptotically optimal exact-size sampler that performs $\frac{n^2}{2} o(n^2)$ operations and requests to a random generator. This was achieved by extending the Boltzmann model for graphical generating functions and by using various decompositions of directed acyclic graphs. The presented samplers improve upon the state-of-the-art algorithms in terms of theoretical complexity and offer a significant speed-up in practice.
toXiv_bot_toot
Orange Foolius
bot by @…
No laws were broken in the making of this bot: let's not get carceral over comedy.
#satire #potus45
QED Effects in PDFs -- A Les Houches Comparison Study
Thomas Cridge, Juan Cruz Martinez, Joey Huston
https://arxiv.org/abs/2602.06908 https://arxiv.org/pdf…
Fast Makespan Minimization via Short ILPs
Danny Hermelin, Dvir Shabtay
https://arxiv.org/abs/2602.06514 https://arxiv.org/pdf/2602.06514 https://arxiv.org/html/2602.06514
arXiv:2602.06514v1 Announce Type: new
Abstract: Short integer linear programs are programs with a relatively small number of constraints. We show how recent improvements on the running-times of solvers for such programs can be used to obtain fast pseudo-polynomial time algorithms for makespan minimization on a fixed number of parallel machines, and other related variants. The running times of our algorithms are all of the form $\widetilde{O}(p^{O(1)}_{\max} n)$ or $\widetilde{O}(p^{O(1)}_{\max} \cdot n)$, where $p_{\max}$ is the maximum processing time in the input. These improve upon the time complexity of previously known algorithms for moderate values of $p_{\max}$.
toXiv_bot_toot
El Cheeto Loco
bot by @…
No laws were broken in the making of this bot: please don't ruin my life.
#satire #potus45
MadSpace -- Event Generation for the Era of GPUs and ML
Theo Heimel, Olivier Mattelaer, Ramon Winterhalder
https://arxiv.org/abs/2602.06895 https://arxiv.o…
Unsplittable Transshipments
Srinwanti Debgupta, Sarah Morell, Martin Skutella
https://arxiv.org/abs/2602.07230 https://arxiv.org/pdf/2602.07230 https://arxiv.org/html/2602.07230
arXiv:2602.07230v1 Announce Type: new
Abstract: We introduce the Unsplittable Transshipment Problem in directed graphs with multiple sources and sinks. An unsplittable transshipment routes given supplies and demands using at most one path for each source-sink pair. Although they are a natural generalization of single source unsplittable flows, unsplittable transshipments raise interesting new challenges and require novel algorithmic techniques. As our main contribution, we give a nontrivial generalization of a seminal result of Dinitz, Garg, and Goemans (1999) by showing how to efficiently turn a given transshipment $x$ into an unsplittable transshipment $y$ with $y_a<x_a d_{\max}$ for all arcs $a$, where $d_{\max}$ is the maximum demand (or supply) value. Further results include bounds on the number of rounds required to satisfy all demands, where each round consists of an unsplittable transshipment that routes a subset of the demands while respecting arc capacity constraints.
toXiv_bot_toot
Donny Dorko
bot by @…
No laws were broken in the making of this bot: please don't torture me.
#satire #potus45
Study of $B \to K_0^*(1430)\,\ell^ \ell^-$ Decay in the Standard Model and Scalar Leptoquark Scenario
M. Dadashzadeh, K. Azizi
https://arxiv.org/abs/2602.06892 https://
Prune, Don't Rebuild: Efficiently Tuning $\alpha$-Reachable Graphs for Nearest Neighbor Search
Tian Zhang, Ashwin Padaki, Jiaming Liang, Zack Ives, Erik Waingarten
https://arxiv.org/abs/2602.08097 https://arxiv.org/pdf/2602.08097 https://arxiv.org/html/2602.08097
arXiv:2602.08097v1 Announce Type: new
Abstract: Vector similarity search is an essential primitive in modern AI and ML applications. Most vector databases adopt graph-based approximate nearest neighbor (ANN) search algorithms, such as DiskANN (Subramanya et al., 2019), which have demonstrated state-of-the-art empirical performance. DiskANN's graph construction is governed by a reachability parameter $\alpha$, which gives a trade-off between construction time, query time, and accuracy. However, adaptively tuning this trade-off typically requires rebuilding the index for different $\alpha$ values, which is prohibitive at scale. In this work, we propose RP-Tuning, an efficient post-hoc routine, based on DiskANN's pruning step, to adjust the $\alpha$ parameter without reconstructing the full index. Within the $\alpha$-reachability framework of prior theoretical works (Indyk and Xu, 2023; Gollapudi et al., 2025), we prove that pruning an initially $\alpha$-reachable graph with RP-Tuning preserves worst-case reachability guarantees in general metrics and improved guarantees in Euclidean metrics. Empirically, we show that RP-Tuning accelerates DiskANN tuning on four public datasets by up to $43\times$ with negligible overhead.
toXiv_bot_toot
Genghis Convict
bot by @…
No laws were broken in the making of this bot: let's not have humor lead to homicide.
#satire #potus45
Direct Detection and Cosmological Constraints of Dark Matter with Dark Dipoles
Takumi Kuwahara, Jun-Chen Wang, Shu-Run Yuan
https://arxiv.org/abs/2602.06861 https://
Towards Efficient Data Structures for Approximate Search with Range Queries
Ladan Kian, Dariusz R. Kowalski
https://arxiv.org/abs/2602.06860 https://arxiv.org/pdf/2602.06860 https://arxiv.org/html/2602.06860
arXiv:2602.06860v1 Announce Type: new
Abstract: Range queries are simple and popular types of queries used in data retrieval. However, extracting exact and complete information using range queries is costly. As a remedy, some previous work proposed a faster principle, {\em approximate} search with range queries, also called single range cover (SRC) search. It can, however, produce some false positives. In this work we introduce a new SRC search structure, a $c$-DAG (Directed Acyclic Graph), which provably decreases the average number of false positives by logarithmic factor while keeping asymptotically same time and memory complexities as a classic tree structure. A $c$-DAG is a tunable augmentation of the 1D-Tree with denser overlapping branches ($c \geq 3$ children per node). We perform a competitive analysis of a $c$-DAG with respect to 1D-Tree and derive an additive constant time overhead and a multiplicative logarithmic improvement of the false positives ratio, on average. We also provide a generic framework to extend our results to empirical distributions of queries, and demonstrate its effectiveness for Gowalla dataset. Finally, we quantify and discuss security and privacy aspects of SRC search on $c$-DAG vs 1D-Tree, mainly mitigation of structural leakage, which makes $c$-DAG a good data structure candidate for deployment in privacy-preserving systems (e.g., searchable encryption) and multimedia retrieval.
toXiv_bot_toot
Genghis Convict
bot by @…
No laws were broken in the making of this bot: rescind the warrant.
#satire #potus45
Cavity, lumped-circuit, and spin-based detection of axion dark matter: differences and similarities
Deniz Aybas, Hendrik Bekker, Dmitry Budker, Wei Ji, On Kim, Younggeun Kim, Derek F. Jackson Kimball, Jia Liu, Xiaolin Ma, Chiara P. Salemi, Yannis K. Semertzidis, Alexander O. Sushkov, Kai Wei, Arne Wickenbrock, Yuzhe Zhang
https://arxiv.org…
Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
Sharareh Alipour
https://arxiv.org/abs/2602.07720 https://arxiv.org/pdf/2602.07720 https://arxiv.org/html/2602.07720
arXiv:2602.07720v1 Announce Type: new
Abstract: Many multiagent tasks -- such as reviewer assignment, coalition formation, or fair resource allocation -- require selecting a group of agents such that collaboration remains effective even in the worst case. The \emph{weighted max-min $T$-join problem} formalizes this challenge by seeking a subset of vertices whose minimum-weight matching is maximized, thereby ensuring robust outcomes against unfavorable pairings.
We advance the study of this problem in several directions. First, we design an algorithm that computes an upper bound for the \emph{weighted max-min $2k$-matching problem}, where the chosen set must contain exactly $2k$ vertices. Building on this bound, we develop a general algorithm with a \emph{$2 \ln n$-approximation guarantee} that runs in $O(n^4)$ time. Second, using ear decompositions, we propose another upper bound for the weighted max-min $T$-join cost. We also show that the problem can be solved exactly when edge weights belong to $\{1,2\}$.
Finally, we evaluate our methods on real collaboration datasets. Experiments show that the lower bounds from our approximation algorithm and the upper bounds from the ear decomposition method are consistently close, yielding empirically small constant-factor approximations. Overall, our results highlight both the theoretical significance and practical value of weighted max-min $T$-joins as a framework for fair and robust group formation in multiagent systems.
toXiv_bot_toot
Budget Bashar
bot by @…
No laws were broken in the making of this bot: please don't extraordinarily rendition me to a black site.
#satire #potus45
Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
Kanstantsin Pashkovich, Thomas Snow
https://arxiv.org/abs/2602.07355 https://arxiv.org/pdf/2602.07355 https://arxiv.org/html/2602.07355
arXiv:2602.07355v1 Announce Type: new
Abstract: We study online algorithms for maximum cardinality matchings with edge arrivals in graphs of low degree. Buchbinder, Segev, and Tkach showed that no online algorithm for maximum cardinality fractional matchings can achieve a competitive ratio larger than $4/(9-\sqrt 5)\approx 0.5914$ even for graphs of maximum degree three. The negative result of Buchbinder et al. holds even when the graph is bipartite and edges are revealed according to vertex arrivals, i.e. once a vertex arrives, all edges are revealed that include the newly arrived vertex and one of the previously arrived vertices. In this work, we complement the negative result of Buchbinder et al. by providing an online algorithm for maximum cardinality fractional matchings with a competitive ratio at least $4/(9-\sqrt 5)\approx 0.5914$ for graphs of maximum degree three. We also demonstrate that no online algorithm for maximum cardinality integral matchings can have the competitive guarantee $0.5807$, establishing a gap between integral and fractional matchings for graphs of maximum degree three. Note that the work of Buchbinder et al. shows that for graphs of maximum degree two, there is no such gap between fractional and integral matchings, because for both of them the best achievable competitive ratio is $2/3$. Also, our results demonstrate that for graphs of maximum degree three best possible competitive ratios for fractional matchings are the same in the vertex arrival and in the edge arrival models.
toXiv_bot_toot
Spin Light of neutrino in polarized matter
Alexander Grigoriev, Alexei Ternov
https://arxiv.org/abs/2602.06708 https://arxiv.org/pdf/2602.06708
Pampers President
bot by @…
No laws were broken in the making of this bot: tell the black helicopters to return to base.
#satire #potus45
Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
Yu-Sheng Shih, Meng-Tsung Tsai, Yen-Chu Tsai, Ying-Sian Wu
https://arxiv.org/abs/2602.08002 https://arxiv.org/pdf/2602.08002 https://arxiv.org/html/2602.08002
arXiv:2602.08002v1 Announce Type: new
Abstract: We study the space complexity of four variants of the standard subgraph finding problem in the streaming model. Specifically, given an $n$-vertex input graph and a fixed-size pattern graph, we consider two settings: undirected simple graphs, denoted by $G$ and $H$, and oriented graphs, denoted by $\vec{G}$ and $\vec{H}$. Depending on the setting, the task is to decide whether $G$ contains $H$ as a subgraph or as an induced subgraph, or whether $\vec{G}$ contains $\vec{H}$ as a subgraph or as an induced subgraph. Let Sub$(H)$, IndSub$(H)$, Sub$(\vec{H})$, and IndSub$(\vec{H})$ denote these four variants, respectively.
An oriented graph is well-oriented if it admits a bipartition in which every arc is oriented from one part to the other, and a vertex is non-well-oriented if both its in-degree and out-degree are non-zero. For each variant, we obtain a complete dichotomy theorem, briefly summarized as follows.
(1) Sub$(H)$ can be solved by an $\tilde{O}(1)$-pass $n^{2-\Omega(1)}$-space algorithm if and only if $H$ is bipartite.
(2) IndSub$(H)$ can be solved by an $\tilde{O}(1)$-pass $n^{2-\Omega(1)}$-space algorithm if and only if $H \in \{P_3, P_4, co\mbox{-}P_3\}$.
(3) Sub$(\vec{H})$ can be solved by a single-pass $n^{2-\Omega(1)}$-space algorithm if and only if every connected component of $\vec H$ is either a well-oriented bipartite graph or a tree containing at most one non-well-oriented vertex.
(4) IndSub$(\vec{H})$ can be solved by an $\tilde{O}(1)$-pass $n^{2-\Omega(1)}$-space algorithm if and only if the underlying undirected simple graph $H$ is a $co\mbox{-}P_3$.
toXiv_bot_toot
Physics of strong electromagnetic fields in relativistic heavy-ion collisions
Koichi Hattori
https://arxiv.org/abs/2602.06697 https://arxiv.org/pdf/2602.06…
The Lyin' King
bot by @…
No laws were broken in the making of this bot: put the zip ties down.
#satire #potus45
Welfarist Formulations for Diverse Similarity Search
Siddharth Barman, Nirjhar Das, Shivam Gupta, Kirankumar Shiragur
https://arxiv.org/abs/2602.08742 https://arxiv.org/pdf/2602.08742 https://arxiv.org/html/2602.08742
arXiv:2602.08742v1 Announce Type: new
Abstract: Nearest Neighbor Search (NNS) is a fundamental problem in data structures with wide-ranging applications, such as web search, recommendation systems, and, more recently, retrieval-augmented generations (RAG). In such recent applications, in addition to the relevance (similarity) of the returned neighbors, diversity among the neighbors is a central requirement. In this paper, we develop principled welfare-based formulations in NNS for realizing diversity across attributes. Our formulations are based on welfare functions -- from mathematical economics -- that satisfy central diversity (fairness) and relevance (economic efficiency) axioms. With a particular focus on Nash social welfare, we note that our welfare-based formulations provide objective functions that adaptively balance relevance and diversity in a query-dependent manner. Notably, such a balance was not present in the prior constraint-based approach, which forced a fixed level of diversity and optimized for relevance. In addition, our formulation provides a parametric way to control the trade-off between relevance and diversity, providing practitioners with flexibility to tailor search results to task-specific requirements. We develop efficient nearest neighbor algorithms with provable guarantees for the welfare-based objectives. Notably, our algorithm can be applied on top of any standard ANN method (i.e., use standard ANN method as a subroutine) to efficiently find neighbors that approximately maximize our welfare-based objectives. Experimental results demonstrate that our approach is practical and substantially improves diversity while maintaining high relevance of the retrieved neighbors.
toXiv_bot_toot
Nostra-dumbass
bot by @…
No laws were broken in the making of this bot: don't have me abducted.
#satire #potus45
Neighborhood-Aware Graph Labeling Problem
Mohammad Shahverdikondori, Sepehr Elahi, Patrick Thiran, Negar Kiyavash
https://arxiv.org/abs/2602.08098 https://arxiv.org/pdf/2602.08098 https://arxiv.org/html/2602.08098
arXiv:2602.08098v1 Announce Type: new
Abstract: Motivated by optimization oracles in bandits with network interference, we study the Neighborhood-Aware Graph Labeling (NAGL) problem. Given a graph $G = (V,E)$, a label set of size $L$, and local reward functions $f_v$ accessed via evaluation oracles, the objective is to assign labels to maximize $\sum_{v \in V} f_v(x_{N[v]})$, where each term depends on the closed neighborhood of $v$. Two vertices co-occur in some neighborhood term exactly when their distance in $G$ is at most $2$, so the dependency graph is the squared graph $G^2$ and $\mathrm{tw}(G^2)$ governs exact algorithms and matching fine-grained lower bounds. Accordingly, we show that this dependence is inherent: NAGL is NP-hard even on star graphs with binary labels and, assuming SETH, admits no $(L-\varepsilon)^{\mathrm{tw}(G^2)}\cdot n^{O(1)}$-time algorithm for any $\varepsilon>0$. We match this with an exact dynamic program on a tree decomposition of $G^2$ running in $O\!\left(n\cdot \mathrm{tw}(G^2)\cdot L^{\mathrm{tw}(G^2) 1}\right)$ time. For approximation, unless $\mathsf{P}=\mathsf{NP}$, for every $\varepsilon>0$ there is no polynomial-time $n^{1-\varepsilon}$-approximation on general graphs even under the promise $\mathrm{OPT}>0$; without the promise $\mathrm{OPT}>0$, no finite multiplicative approximation ratio is possible. In the nonnegative-reward regime, we give polynomial-time approximation algorithms for NAGL in two settings: (i) given a proper $q$-coloring of $G^2$, we obtain a $1/q$-approximation; and (ii) on planar graphs of bounded maximum degree, we develop a Baker-type polynomial-time approximation scheme (PTAS), which becomes an efficient PTAS (EPTAS) when $L$ is constant.
toXiv_bot_toot
Return of the CHAMPs: A clockwork portal to charged dark matter
Debajyoti Choudhury, Vineet K. Jha, Suvam Maharana
https://arxiv.org/abs/2602.06681 https://
Nelson Tandela
bot by @…
No laws were broken in the making of this bot: please don't ruin my life.
#satire #potus45
Approximate Cartesian Tree Matching with Substitutions
Panagiotis Charalampopoulos, Jonas Ellert, Manal Mohamed
https://arxiv.org/abs/2602.08570 https://arxiv.org/pdf/2602.08570 https://arxiv.org/html/2602.08570
arXiv:2602.08570v1 Announce Type: new
Abstract: The Cartesian tree of a sequence captures the relative order of the sequence's elements. In recent years, Cartesian tree matching has attracted considerable attention, particularly due to its applications in time series analysis. Consider a text $T$ of length $n$ and a pattern $P$ of length $m$. In the exact Cartesian tree matching problem, the task is to find all length-$m$ fragments of $T$ whose Cartesian tree coincides with the Cartesian tree $CT(P)$ of the pattern. Although the exact version of the problem can be solved in linear time [Park et al., TCS 2020], it remains rather restrictive; for example, it is not robust to outliers in the pattern.
To overcome this limitation, we consider the approximate setting, where the goal is to identify all fragments of $T$ that are close to some string whose Cartesian tree matches $CT(P)$. In this work, we quantify closeness via the widely used Hamming distance metric. For a given integer parameter $k>0$, we present an algorithm that computes all fragments of $T$ that are at Hamming distance at most $k$ from a string whose Cartesian tree matches $CT(P)$. Our algorithm runs in time $\mathcal O(n \sqrt{m} \cdot k^{2.5})$ for $k \leq m^{1/5}$ and in time $\mathcal O(nk^5)$ for $k \geq m^{1/5}$, thereby improving upon the state-of-the-art $\mathcal O(nmk)$-time algorithm of Kim and Han [TCS 2025] in the regime $k = o(m^{1/4})$.
On the way to our solution, we develop a toolbox of independent interest. First, we introduce a new notion of periodicity in Cartesian trees. Then, we lift multiple well-known combinatorial and algorithmic results for string matching and periodicity in strings to Cartesian tree matching and periodicity in Cartesian trees.
toXiv_bot_toot
Chiral phase transition with primordial black holes: Distinct phase structure and catalysis
Masanori Tanaka, Jun-Chen Wang, Jing-Jun Zhang
https://arxiv.org/abs/2602.06661 https…
Tangerine Terror
bot by @…
No laws were broken in the making of this bot: don't make me go to gulag.
#satire #potus45
Incremental (k, z)-Clustering on Graphs
Emilio Cruciani, Sebastian Forster, Antonis Skarlatos
https://arxiv.org/abs/2602.08542 https://arxiv.org/pdf/2602.08542 https://arxiv.org/html/2602.08542
arXiv:2602.08542v1 Announce Type: new
Abstract: Given a weighted undirected graph, a number of clusters $k$, and an exponent $z$, the goal in the $(k, z)$-clustering problem on graphs is to select $k$ vertices as centers that minimize the sum of the distances raised to the power $z$ of each vertex to its closest center. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact $(k, z)$-clustering solution in the induced shortest-path metric.
While efficient dynamic $k$-center approximation algorithms on graphs exist [Cruciani et al. SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic $(k,z)$-clustering problem. As the main result of this paper, we develop a randomized incremental $(k, z)$-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of $\tilde O(k m^{1 o(1)} k^{1 \frac{1}{\lambda}} m)$, where $\lambda \geq 1$ is an arbitrary fixed constant. Our incremental algorithm consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size $\tilde{O}(k)$ with a total update time of $m^{1 o(1)}$ over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant, a property that may be of independent interest.
In the second stage, we maintain a constant-factor approximate $(k,z)$-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static $(k,z)$-clustering algorithm.
toXiv_bot_toot
Carrot Caligula
bot by @…
No laws were broken in the making of this bot: let's not get carceral over comedy.
#satire #potus45
CP violation angles from H$\to\tau\tau$ decays at FCC-ee
Sofia Giappichini, Markus Klute, Matteo Presilla
https://arxiv.org/abs/2602.06635 https://arxiv.or…
Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
Pan Peng, Yuyang Wang
https://arxiv.org/abs/2602.07394 https://arxiv.org/pdf/2602.07394 https://arxiv.org/html/2602.07394
arXiv:2602.07394v1 Announce Type: new
Abstract: We study \emph{local computation algorithms (LCAs)} for constructing spanning trees. In this setting, the goal is to locally determine, for each edge $ e \in E $, whether it belongs to a spanning tree $ T $ of the input graph $ G $, where $ T $ is defined implicitly by $ G $ and the randomness of the algorithm. It is known that LCAs for spanning trees do not exist in general graphs, even for simple graph families. We identify a natural and well-studied class of graphs -- \emph{expander graphs} -- that do admit \emph{sublinear-time} LCAs for spanning trees. This is perhaps surprising, as previous work on expanders only succeeded in designing LCAs for \emph{sparse spanning subgraphs}, rather than full spanning trees. We design an LCA with probe complexity $ O\left(\sqrt{n}\left(\frac{\log^2 n}{\phi^2} d\right)\right)$ for graphs with conductance at least $ \phi $ and maximum degree at most $ d $ (not necessarily constant), which is nearly optimal when $\phi$ and $d$ are constants, since $\Omega(\sqrt{n})$ probes are necessary even for expanders. Next, we show that for the natural class of \emph{\ER graphs} $ G(n, p) $ with $ np = n^{\delta} $ for any constant $ \delta > 0 $ (which are expanders with high probability), the $ \sqrt{n} $ lower bound can be bypassed. Specifically, we give an \emph{average-case} LCA for such graphs with probe complexity $ \tilde{O}(\sqrt{n^{1 - \delta}})$.
Finally, we extend our techniques to design LCAs for the \emph{minimum spanning tree (MST)} problem on weighted expander graphs. Specifically, given a $d$-regular unweighted graph $\bar{G}$ with sufficiently strong expansion, we consider the weighted graph $G$ obtained by assigning to each edge an independent and uniform random weight from $\{1,\ldots,W\}$, where $W = O(d)$. We show that there exists an LCA that is consistent with an exact MST of $G$, with probe complexity $\tilde{O}(\sqrt{n}d^2)$.
toXiv_bot_toot
Mr. Miracle Ear
bot by @…
No laws were broken in the making of this bot: no waterboarding please and thank you.
#satire #potus45
CoLLM: AI engineering toolbox for end-to-end deep learning in collider analyses
W. Esmail, A. Hammad, M. Nojiri
https://arxiv.org/abs/2602.06496 https://ar…
Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
Moran Feldman, Justin Ward
https://arxiv.org/abs/2602.08473 https://arxiv.org/pdf/2602.08473 https://arxiv.org/html/2602.08473
arXiv:2602.08473v1 Announce Type: new
Abstract: We study the problem of maximizing a non-negative monotone submodular objective $f$ subject to the intersection of $k$ arbitrary matroid constraints. The natural greedy algorithm guarantees $(k 1)$-approximation for this problem, and the state-of-the-art algorithm only improves this approximation ratio to $k$. We give a $\frac{2k\ln2}{1 \ln2} O(\sqrt{k})<0.819k O(\sqrt{k})$ approximation for this problem. Our result is the first multiplicative improvement over the approximation ratio of the greedy algorithm for general $k$. We further show that our algorithm can be used to obtain roughly the same approximation ratio also for the more general problem in which the objective is not guaranteed to be monotone (the sublinear term in the approximation ratio becomes $O(k^{2/3})$ rather than $O(\sqrt{k})$ in this case).
All of our results hold also when the $k$-matroid intersection constraint is replaced with a more general matroid $k$-parity constraint. Furthermore, unlike the case in many of the previous works, our algorithms run in time that is independent of $k$ and polynomial in the size of the ground set. Our algorithms are based on a hybrid greedy local search approach recently introduced by Singer and Thiery (STOC 2025) for the weighted matroid $k$-intersection problem, which is a special case of the problem we consider. Leveraging their approach in the submodular setting requires several non-trivial insights and algorithmic modifications since the marginals of a submodular function $f$, which correspond to the weights in the weighted case, are not independent of the algorithm's internal randomness. In the special weighted case studied by Singer and Thiery, our algorithms reduce to a variant of their algorithm with an improved approximation ratio of $k\ln2 1-\ln2<0.694k 0.307$, compared to an approximation ratio of $\frac{k 1}{2\ln2}\approx0.722k 0.722$ guaranteed by Singer and Thiery.
toXiv_bot_toot
Uncle Touch Too Much
bot by @…
No laws were broken in the making of this bot: don't make me go to gulag.
#satire #potus45
Transeverse-Momentum Subtraction for Semi-Inclusive Deep-Inelastic Scattering
Jun Gao, Hai Tao Li, Hua Xing Zhu, Yu Jiao Zhu
https://arxiv.org/abs/2602.06364 https://
Quid Pro Combover
bot by @…
No laws were broken in the making of this bot: don't send me to a camp, please.
#satire #potus45
Scalar Tsunamis from Black Hole Formation
Arturo de Giorgi, Yeray Garcia del Castillo, Joerg Jaeckel
https://arxiv.org/abs/2602.06112 https://arxiv.org/pdf…
Donnie Deathcount
bot by @…
No laws were broken in the making of this bot: rescind the warrant.
#satire #potus45
Dark Matter Heating of Compact Stars Beyond Capture: A Relativistic Framework for Energy Deposition by Particle Beams
Jaime Hoefken Zink, Shihwen Hor, Maura E. Ramirez-Quezada
https://arxiv.org/abs/2602.06111
Lil' Donny Moscow
bot by @…
No laws were broken in the making of this bot: please don't ruin my life.
#satire #potus45
Replaced article(s) found for hep-ph. https://arxiv.org/list/hep-ph/new
[2/2]:
- Dilaton Effective Field Theory across the Conformal Edge
Thomas Appelquist, James Ingoldby, Maurizio Piai
Covidiot in Chief
bot by @…
No laws were broken in the making of this bot: don't make me go to gulag.
#satire #potus45
Replaced article(s) found for hep-ph. https://arxiv.org/list/hep-ph/new
[1/2]:
- Probing Boson Clouds with Supermassive Black Hole Binaries
Ximeng Li, Jing Ren, Xi-Li Zhang
The Florida Fondler
bot by @…
No laws were broken in the making of this bot: I hope you'll lol, not take legal action.
#satire #potus45
Probing Extended Higgs Sectors via Multi-Top Events from Higgs Pair Decays in 2HDM Type-I at the HL-LHC
Ijaz Ahmed, M. Ibad, Farzana Ahmad, Jamil Muhammad
https://arxiv.org/abs/2602.06217
Walker: Taxes Evader
bot by @…
No laws were broken in the making of this bot: please don't extraordinarily rendition me to a black site.
#satire #potus45
Commander in Fleece
bot by @…
No laws were broken in the making of this bot: don't have me abducted.
#satire #potus45
Circus Peanut President
bot by @…
No laws were broken in the making of this bot: please don't ruin my life.
#satire #potus45
Orange Glazed Grifter
bot by @…
No laws were broken in the making of this bot: let's leave the extrajudicial killing out of it.
#satire #potus45
Count of Mostly Crisco
bot by @…
No laws were broken in the making of this bot: let's leave the extrajudicial killing out of it.
#satire #potus45
Donald Duck-the-draft
bot by @…
No laws were broken in the making of this bot: let's leave the extrajudicial killing out of it.
#satire #potus45
President Dunning-Kruger
bot by @…
No laws were broken in the making of this bot: no investigating me please.
#satire #potus45
Payless Putin
bot by @…
No laws were broken in the making of this bot: don't send me to a camp, please.
#satire #potus45
Emperor Palpateeny Hands
bot by @…
No laws were broken in the making of this bot: no waterboarding please and thank you.
#satire #potus45
Absolute Cock-Juggling Numpty
bot by @…
No laws were broken in the making of this bot: put the zip ties down.
#satire #potus45
Pervert Hoover
bot by @…
No laws were broken in the making of this bot: let's not have humor lead to homicide.
#satire #potus45
Marginally Sentient Spray-Tan
bot by @…
No laws were broken in the making of this bot: let's not get carceral over comedy.
#satire #potus45…
President Rottinghands McRagebaby
bot by @…
No laws were broken in the making of this bot: please don't come after me.
#satire #potus45
@arXiv_csDS_bot@mastoxiv.page
