Tootfinder

Allometric scaling of brain activity explained by avalanche criticality
Tiago S. A. N. Sim\~oes, Jos\'e S. Andrade Jr., Hans J. Herrmann, Stefano Zapperi, Lucilla de Arcangelis
https://arxiv.org/abs/2512.10834 https://arxiv.org/pdf/2512.10834 https://arxiv.org/html/2512.10834
arXiv:2512.10834v1 Announce Type: new
Abstract: Allometric scaling laws, such as Kleiber's law for metabolic rate, highlight how efficiency emerges with size across living systems. The brain, with its characteristic sublinear scaling of activity, has long posed a puzzle: why do larger brains operate with disproportionately lower firing rates? Here we show that this economy of scale is a universal outcome of avalanche dynamics. We derive analytical scaling laws directly from avalanche statistics, establishing that any system governed by critical avalanches must exhibit sublinear activity-size relations. This theoretical prediction is then verified in integrate-and-fire neuronal networks at criticality and in classical self-organized criticality models, demonstrating that the effect is not model-specific but generic. The predicted exponents align with experimental observations across mammal species, bridging dynamical criticality with the allometry of brain metabolism. Our results reveal avalanche criticality as a fundamental mechanism underlying Kleiber-like scaling in the brain.
toXiv_bot_toot

Selling Privacy in Blockchain Transactions
Georgios Chionas, Olga Gorelkina, Piotr Krysta, Rida Laraki
https://arxiv.org/abs/2512.08096 https://arxiv.org/pdf/2512.08096 https://arxiv.org/html/2512.08096
arXiv:2512.08096v1 Announce Type: new
Abstract: We study methods to enhance privacy in blockchain transactions from an economic angle. We consider mechanisms for privacy-aware users whose utility depends not only on the outcome of the mechanism but also negatively on the exposure of their economic preferences. Specifically, we study two auction-theoretic settings with privacy-aware users. First, we analyze an order flow auction, where a user auctions off to specialized agents, called searchers, the right to execute her transaction while maintaining a degree of privacy. We examine how the degree of privacy affects the revenue of the auction and, broadly, the net utility of the privacy-aware user. In this new setting, we describe the optimal auction, which is a sealed-bid auction. Subsequently, we analyze a variant of a Dutch auction in which the user gradually decreases the price and the degree of privacy until the transaction is sold. We compare the revenue of this auction to that of the optimal one as a function of the number of communication rounds. Then, we introduce a two-sided market - a privacy marketplace - with multiple users selling their transactions under their privacy preferences to multiple searchers. We propose a posted-price mechanism for the two-sided market that guarantees constant approximation of the optimal social welfare while maintaining incentive compatibility (from both sides of the market) and budget balance. This work builds on the emerging line of research that attempts to improve the performance of economic mechanisms by appending cryptographic primitives to them.
toXiv_bot_toot

Replaced article(s) found for cs.DS. https://arxiv.org/list/cs.DS/new
[1/1]:
- Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai, Vihan Shah, Chen Wang
https://arxiv.org/abs/2411.09979 https://mastoxiv.page/@arXiv_csDS_bot/113502653187863544
- A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
William Kuszmaul
https://arxiv.org/abs/2501.03488 https://mastoxiv.page/@arXiv_csDS_bot/113791396712128907
- The Structural Complexity of Matrix-Vector Multiplication
Emile Anand, Jan van den Brand, Rose McCarty
https://arxiv.org/abs/2502.21240 https://mastoxiv.page/@arXiv_csDS_bot/114097340825270885
- Clustering under Constraints: Efficient Parameterized Approximation Schemes
Sujoy Bhore, Ameet Gadekar, Tanmay Inamdar
https://arxiv.org/abs/2504.06980 https://mastoxiv.page/@arXiv_csDS_bot/114312444050875805
- Minimizing Envy and Maximizing Happiness in Graphical House Allocation
Anubhav Dhar, Ashlesha Hota, Palash Dey, Sudeshna Kolay
https://arxiv.org/abs/2505.00296 https://mastoxiv.page/@arXiv_csDS_bot/114437013364446063
- Fast and Simple Densest Subgraph with Predictions
Thai Bui, Luan Nguyen, Hoa T. Vu
https://arxiv.org/abs/2505.12600 https://mastoxiv.page/@arXiv_csDS_bot/114538936921930134
- Compressing Suffix Trees by Path Decompositions
Becker, Cenzato, Gagie, Kim, Koerkamp, Manzini, Prezza
https://arxiv.org/abs/2506.14734 https://mastoxiv.page/@arXiv_csDS_bot/114703384646892523
- Improved sampling algorithms and functional inequalities for non-log-concave distributions
Yuchen He, Zhehan Lei, Jianan Shao, Chihao Zhang
https://arxiv.org/abs/2507.11236 https://mastoxiv.page/@arXiv_csDS_bot/114862112197588124
- Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
Peter Robinson, Ming Ming Tan
https://arxiv.org/abs/2507.11257 https://mastoxiv.page/@arXiv_csDS_bot/114862223634372292
- Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
Santhoshini Velusamy, Huacheng Yu
https://arxiv.org/abs/2509.07286 https://mastoxiv.page/@arXiv_csDS_bot/115178875220889588
- Uncrossed Multiflows and Applications to Disjoint Paths
Chandra Chekuri, Guyslain Naves, Joseph Poremba, F. Bruce Shepherd
https://arxiv.org/abs/2511.00254 https://mastoxiv.page/@arXiv_csDS_bot/115490402963680492
- Dynamic Matroids: Base Packing and Covering
Tijn de Vos, Mara Grilnberger
https://arxiv.org/abs/2511.15460 https://mastoxiv.page/@arXiv_csDS_bot/115580946319285096
- Branch-width of connectivity functions is fixed-parameter tractable
Tuukka Korhonen, Sang-il Oum
https://arxiv.org/abs/2601.04756 https://mastoxiv.page/@arXiv_csDS_bot/115864074799755995
- CoinPress: Practical Private Mean and Covariance Estimation
Sourav Biswas, Yihe Dong, Gautam Kamath, Jonathan Ullman
https://arxiv.org/abs/2006.06618
- The Ideal Membership Problem and Abelian Groups
Andrei A. Bulatov, Akbar Rafiey
https://arxiv.org/abs/2201.05218
- Bridging Classical and Quantum: Group-Theoretic Approach to Quantum Circuit Simulation
Daksh Shami
https://arxiv.org/abs/2407.19575 https://mastoxiv.page/@arXiv_quantph_bot/112874282709517475
- Young domination on Hamming rectangles
Janko Gravner, Matja\v{z} Krnc, Martin Milani\v{c}, Jean-Florent Raymond
https://arxiv.org/abs/2501.03788 https://mastoxiv.page/@arXiv_mathCO_bot/113791421814248215
- On the Space Complexity of Online Convolution
Joel Daniel Andersson, Amir Yehudayoff
https://arxiv.org/abs/2505.00181 https://mastoxiv.page/@arXiv_csCC_bot/114437005955255553
- Universal Solvability for Robot Motion Planning on Graphs
Anubhav Dhar, Pranav Nyati, Tanishq Prasad, Ashlesha Hota, Sudeshna Kolay
https://arxiv.org/abs/2506.18755 https://mastoxiv.page/@arXiv_csCC_bot/114737342714568702
- Colorful Minors
Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht
https://arxiv.org/abs/2507.10467
- Learning fermionic linear optics with Heisenberg scaling and physical operations
Aria Christensen, Andrew Zhao
https://arxiv.org/abs/2602.05058
toXiv_bot_toot

Fast $k$-means Seeding Under The Manifold Hypothesis
Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal
https://arxiv.org/abs/2602.01104 https://arxiv.org/pdf/2602.01104 https://arxiv.org/html/2602.01104
arXiv:2602.01104v1 Announce Type: new
Abstract: We study beyond worst case analysis for the $k$-means problem where the goal is to model typical instances of $k$-means arising in practice. Existing theoretical approaches provide guarantees under certain assumptions on the optimal solutions to $k$-means, making them difficult to validate in practice. We propose the manifold hypothesis, where data obtained in ambient dimension $D$ concentrates around a low dimensional manifold of intrinsic dimension $d$, as a reasonable assumption to model real world clustering instances. We identify key geometric properties of datasets which have theoretically predictable scaling laws depending on the quantization exponent $\varepsilon = 2/d$ using techniques from optimum quantization theory. We show how to exploit these regularities to design a fast seeding method called $\operatorname{Qkmeans}$ which provides $O(\rho^{-2} \log k)$ approximate solutions to the $k$-means problem in time $O(nD) \widetilde{O}(\varepsilon^{1 \rho}\rho^{-1}k^{1 \gamma})$; where the exponent $\gamma = \varepsilon \rho$ for an input parameter $\rho < 1$. This allows us to obtain new runtime - quality tradeoffs. We perform a large scale empirical study across various domains to validate our theoretical predictions and algorithm performance to bridge theory and practice for beyond worst case data clustering.
toXiv_bot_toot

Spatially-informed transformers: Injecting geostatistical covariance biases into self-attention for spatio-temporal forecasting
Yuri Calleo
https://arxiv.org/abs/2512.17696 https://arxiv.org/pdf/2512.17696 https://arxiv.org/html/2512.17696
arXiv:2512.17696v1 Announce Type: new
Abstract: The modeling of high-dimensional spatio-temporal processes presents a fundamental dichotomy between the probabilistic rigor of classical geostatistics and the flexible, high-capacity representations of deep learning. While Gaussian processes offer theoretical consistency and exact uncertainty quantification, their prohibitive computational scaling renders them impractical for massive sensor networks. Conversely, modern transformer architectures excel at sequence modeling but inherently lack a geometric inductive bias, treating spatial sensors as permutation-invariant tokens without a native understanding of distance. In this work, we propose a spatially-informed transformer, a hybrid architecture that injects a geostatistical inductive bias directly into the self-attention mechanism via a learnable covariance kernel. By formally decomposing the attention structure into a stationary physical prior and a non-stationary data-driven residual, we impose a soft topological constraint that favors spatially proximal interactions while retaining the capacity to model complex dynamics. We demonstrate the phenomenon of ``Deep Variography'', where the network successfully recovers the true spatial decay parameters of the underlying process end-to-end via backpropagation. Extensive experiments on synthetic Gaussian random fields and real-world traffic benchmarks confirm that our method outperforms state-of-the-art graph neural networks. Furthermore, rigorous statistical validation confirms that the proposed method delivers not only superior predictive accuracy but also well-calibrated probabilistic forecasts, effectively bridging the gap between physics-aware modeling and data-driven learning.
toXiv_bot_toot