16 Search Results for "Ganesh, Arun"

Document
DOI: 10.4230/LIPIcs.SEA.2026.4
Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance

Authors: Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.
Cite as

Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti. Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arbib_et_al:LIPIcs.SEA.2026.4,
  author =	{Arbib, Claudio and D'Ascenzo, Andrea and Kara\c{s}an, Oya E. and Pizzuti, Andrea},
  title =	{{Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.4},
  URN =		{urn:nbn:de:0030-drops-260081},
  doi =		{10.4230/LIPIcs.SEA.2026.4},
  annote =	{Keywords: Levenshtein Distance, Median String Problem, Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.2
Learning Rate Scheduling with Matrix Factorization for Private Training

Authors: Nikita P. Kalinin and Joel Daniel Andersson

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
We study differentially private model training with stochastic gradient descent under learning rate scheduling and correlated noise. Although correlated noise, in particular via matrix factorizations, has been shown to improve accuracy, prior theoretical work focused primarily on the prefix-sum workload. That workload assumes a constant learning rate, whereas in practice learning rate schedules are widely used to accelerate training and improve convergence. We close this gap by deriving general upper and lower bounds for a broad class of learning rate schedules in both single- and multi-epoch settings. Building on these results, we propose a learning-rate-aware factorization that achieves improvements over prefix-sum factorizations under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient constructions suitable for practical deployment, and experiments on CIFAR-10 and IMDB datasets confirm that schedule-aware factorizations improve accuracy in private training.
Cite as

Nikita P. Kalinin and Joel Daniel Andersson. Learning Rate Scheduling with Matrix Factorization for Private Training. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalinin_et_al:LIPIcs.FORC.2026.2,
  author =	{Kalinin, Nikita P. and Andersson, Joel Daniel},
  title =	{{Learning Rate Scheduling with Matrix Factorization for Private Training}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{2:1--2:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.2},
  URN =		{urn:nbn:de:0030-drops-259738},
  doi =		{10.4230/LIPIcs.FORC.2026.2},
  annote =	{Keywords: differential privacy, machine learning, matrix factorization}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.20
Privacy, Prediction, and Allocation

Authors: Ben Jacobsen and Nitin Kohli

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Algorithmic predictions are increasingly used to inform the allocation of scarce resources. The promise of these methods is that, through machine learning, they can better identify the people who would benefit most from interventions. Recently, however, several works have called this assumption into question by demonstrating the existence of settings where simple, unit-level allocation strategies can meet or even exceed the performance of those based on individual-level targeting. Separately, other works have objected to individual-level targeting on privacy grounds, leading to an unusual situation where a single solution, unit-level targeting, is recommended for reasons of both privacy and utility. Motivated by the desire to fully understand the interplay of privacy and targeting levels, we initiate the study of aid allocation systems that satisfy differential privacy, synthesizing existing works on private optimization with the economic models of aid allocation used in the non-private literature. To this end, we investigate private variants of both individual and unit-level allocation strategies in both stochastic and distribution-free settings under a range of constraints on data availability. Through this analysis, we provide clean, interpretable bounds characterizing the tradeoffs between privacy, efficiency, and targeting precision in allocation.
Cite as

Ben Jacobsen and Nitin Kohli. Privacy, Prediction, and Allocation. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 20:1-20:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jacobsen_et_al:LIPIcs.FORC.2026.20,
  author =	{Jacobsen, Ben and Kohli, Nitin},
  title =	{{Privacy, Prediction, and Allocation}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{20:1--20:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.20},
  URN =		{urn:nbn:de:0030-drops-259935},
  doi =		{10.4230/LIPIcs.FORC.2026.20},
  annote =	{Keywords: Differential privacy, fair allocation, limits of prediction}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.22
Separating Oblivious and Adaptive Differential Privacy Under Continual Observation

Authors: Mark Bun, Marco Gaboardi, and Connor Wagaman

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
We resolve an open question of Jain, Raskhodnikova, Sivakumar, and Smith (ICML 2023) by exhibiting a problem separating differential privacy under continual observation in the oblivious and adaptive settings. The continual observation (a.k.a. continual release) model formalizes privacy for streaming algorithms, where data is received over time and output is released at each time step. In the oblivious setting, privacy need only hold for data streams fixed in advance; in the adaptive setting, privacy is required even for streams that can be chosen adaptively based on the streaming algorithm’s output. We describe the first explicit separation between the oblivious and adaptive settings. The problem showing this separation is based on the correlated vector queries problem of Bun, Steinke, and Ullman (SODA 2017). Specifically, we present an (ε,0)-DP algorithm for the oblivious setting that remains accurate for exponentially many time steps in the dimension of the input. On the other hand, we show that every (ε,δ)-DP adaptive algorithm fails to be accurate after releasing output for only a constant number of time steps.
Cite as

Mark Bun, Marco Gaboardi, and Connor Wagaman. Separating Oblivious and Adaptive Differential Privacy Under Continual Observation. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 22:1-22:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.FORC.2026.22,
  author =	{Bun, Mark and Gaboardi, Marco and Wagaman, Connor},
  title =	{{Separating Oblivious and Adaptive Differential Privacy Under Continual Observation}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{22:1--22:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.22},
  URN =		{urn:nbn:de:0030-drops-259959},
  doi =		{10.4230/LIPIcs.FORC.2026.22},
  annote =	{Keywords: differential privacy, continual observation, continual release, streaming algorithms, adaptive algorithms}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.9
Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video

Authors: Pantea Karimi, Sadjad Fouladi, Vibhaalakshmi Sivaraman, and Mohammad Alizadeh

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Real-time video streaming relies on rate control to match video bitrate to network capacity while keeping latency low. Existing deployed video rate controllers react slowly to network changes, causing under-utilization and latency spikes. In contrast, modern delay-sensitive congestion control algorithms (CCAs) adapt on round-trip-time timescales, maintaining a tight feedback loop that achieves both high utilization and low latency. We introduce Vidaptive, a lightweight framework that enables real-time video to leverage responsive CCAs without codec changes. Vidaptive decouples encoding from transmission: it paces video frames at the CCA’s rate and injects dummy packets when the encoder output is insufficient, preserving a continuous feedback loop. An online algorithm dynamically adjusts the encoder’s target bitrate to align with CCA capacity while bounding frame latency. Implemented in Google WebRTC, Vidaptive improves both video quality and tail latency on diverse cellular traces. Compared to GCC, it delivers 1.5× higher bitrate, +40% VMAF, +1.4 dB SSIM, +1.3 dB PSNR, and reduces 95th-percentile frame latency by 57% (2.2 seconds). Against Salsify, it achieves lower tail latency without invasive codec modifications. These results show that coupling existing CCAs with a thin adaptation layer can outperform specialized video rate controllers while remaining deployable in practice.
Cite as

Pantea Karimi, Sadjad Fouladi, Vibhaalakshmi Sivaraman, and Mohammad Alizadeh. Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 9:1-9:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karimi_et_al:OASIcs.NINeS.2026.9,
  author =	{Karimi, Pantea and Fouladi, Sadjad and Sivaraman, Vibhaalakshmi and Alizadeh, Mohammad},
  title =	{{Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{9:1--9:29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.9},
  URN =		{urn:nbn:de:0030-drops-255942},
  doi =		{10.4230/OASIcs.NINeS.2026.9},
  annote =	{Keywords: real-time video, congestion control, transport protocols, video rate control, low-latency video communication, tight feedback loop}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.5
OrbitalBrain: A Distributed Framework for Training ML Models in Space

Authors: Om Chabra, Chenning Li, Kevin Hsieh, Santiago Segarra, Behnaz Arzani, Peder Olsen, and Ranveer Chandra

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Earth observation nanosatellites capture high-resolution photos of the Earth in near real-time. These images increasingly support ML applications that are critical for safety and response, such as forest fire and flood detection. However, the downlink bandwidth is limited, resulting in days or weeks of delay from image capture to training. In this work, we propose OrbitalBrain, an efficient in-space distributed ML training framework that leverages limited and predictable satellite compute, bandwidth, and power to intelligently balance data transfer, model aggregation, and local training. Our evaluations demonstrate that OrbitalBrain achieves 1.52×-12.4× speedup in time-to-accuracy while always reaching a higher final model accuracy compared to state-of-the-art ground-based or federated learning baselines. Furthermore, our approach is complementary to satellite imagery capturing and downloading, enhancing the overall efficiency of satellite-based applications.
Cite as

Om Chabra, Chenning Li, Kevin Hsieh, Santiago Segarra, Behnaz Arzani, Peder Olsen, and Ranveer Chandra. OrbitalBrain: A Distributed Framework for Training ML Models in Space. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chabra_et_al:OASIcs.NINeS.2026.5,
  author =	{Chabra, Om and Li, Chenning and Hsieh, Kevin and Segarra, Santiago and Arzani, Behnaz and Olsen, Peder and Chandra, Ranveer},
  title =	{{OrbitalBrain: A Distributed Framework for Training ML Models in Space}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{5:1--5:32},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.5},
  URN =		{urn:nbn:de:0030-drops-255907},
  doi =		{10.4230/OASIcs.NINeS.2026.5},
  annote =	{Keywords: Satellite networks, Distributed machine learning, Federated learning, Earth observation, In-orbit computing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.4
pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer

Authors: Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
This work addresses the inherent issues of high latency in blockchains and low scalability in traditional consensus protocols. We present pod, a novel notion of consensus whose first priority is to achieve the physically-optimal latency of 2δ, or one round-trip, i.e., requiring only one network trip (duration δ) for writing a transaction and one for reading it. To accomplish this, we first eliminate inter-replica communication. Instead, clients send transactions directly to all replicas, which independently process transactions and append them to local logs. Replicas assign a timestamp and a sequence number to each transaction in their logs, allowing clients to extract valuable metadata about the transactions and the system state. Later on, clients retrieve these logs and extract transactions (and associated metadata) from them. Necessarily, this construction achieves weaker properties than a total-order broadcast protocol, due to existing lower bounds. Our work models the primitive of pod and defines its security properties. We then show pod-core, a protocol that satisfies properties such as transaction confirmation within 2δ, censorship resistance against Byzantine replicas, and accountability for safety violations. We show that single-shot auctions can be realized using the pod notion and observe that it is also sufficient for other popular applications.
Cite as

Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros. pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.DISC.2025.4,
  author =	{Alpos, Orestis and David, Bernardo and Mitrovski, Jakov and Sofikitis, Odysseas and Zindros, Dionysis},
  title =	{{pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.4},
  URN =		{urn:nbn:de:0030-drops-248219},
  doi =		{10.4230/LIPIcs.DISC.2025.4},
  annote =	{Keywords: consensus, censorship resistance, accountability, auctions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.74
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications

Authors: Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Min-plus matrix multiplication is a fundamental tool for designing algorithms operating on distances in graphs and different problems solvable by dynamic programming. We know that, assuming the APSP hypothesis, no subcubic-time algorithm exists for the case of general matrices. However, in many applications the matrices admit certain structural properties that can be used to design faster algorithms. For example, when considering a planar graph, one often works with a Monge matrix A, meaning that the density matrix A^◻ has non-negative entries, that is, A^◻_{i,j} := A_{i+1,j} + A_{i,j+1} - A_{i,j} -A_{i+1,j+1} ≥ 0. The min-plus product of two n×n Monge matrices can be computed in 𝒪(n²) time using the famous SMAWK algorithm. In applications such as longest common subsequence, edit distance, and longest increasing subsequence, the matrices are even more structured, as observed by Tiskin [J. Discrete Algorithms, 2008]: they are (or can be converted to) simple unit-Monge matrices, meaning that the density matrix is a permutation matrix and, furthermore, the first column and the last row of the matrix consist of only zeroes. Such matrices admit an implicit representation of size 𝒪(n) and, as shown by Tiskin [SODA 2010 & Algorithmica, 2015], their min-plus product can be computed in 𝒪(nlog n) time. Russo [SPIRE 2010 & Theor. Comput. Sci., 2012] identified a general structural property of matrices that admit such efficient representation and min-plus multiplication algorithms: the core size δ, defined as the number of non-zero entries in the density matrices of the input and output matrices. He provided an adaptive implementation of the SMAWK algorithm that runs in 𝒪((n+δ)log³ n) or 𝒪((n+δ)log² n) time (depending on the representation of the input matrices). In this work, we further investigate the core size as the parameter that enables efficient min-plus matrix multiplication. On the combinatorial side, we provide a (linear) bound on the core size of the product matrix in terms of the core sizes of the input matrices. On the algorithmic side, we generalize Tiskin’s algorithm (but, arguably, with a more elementary analysis) to solve the core-sparse Monge matrix multiplication problem in 𝒪(n+δlog δ) ⊆ 𝒪(n + δ log n) time, matching the complexity for simple unit-Monge matrices. As witnessed by the recent work of Gorbachev and Kociumaka [STOC'25] for edit distance with integer weights, our generalization opens up the possibility of speed-ups for weighted sequence alignment problems. Furthermore, our multiplication algorithm is also capable of producing an efficient data structure for recovering the witness for any given entry of the output matrix. This allows us, for example, to preprocess an integer array of size n in Õ(n) time so that the longest increasing subsequence of any sub-array can be reconstructed in Õ(𝓁) time, where 𝓁 is the length of the reported subsequence. In comparison, Karthik C. S. and Rahul [arXiv, 2024] recently achieved 𝒪(𝓁+n^{1/2}polylog n)-time reporting after 𝒪(n^{3/2}polylog n)-time preprocessing.
Cite as

Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka. Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ESA.2025.74,
  author =	{Gawrychowski, Pawe{\l} and Gorbachev, Egor and Kociumaka, Tomasz},
  title =	{{Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{74:1--74:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.74},
  URN =		{urn:nbn:de:0030-drops-245427},
  doi =		{10.4230/LIPIcs.ESA.2025.74},
  annote =	{Keywords: Min-plus matrix multiplication, Monge matrix, longest increasing subsequence}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.16
Estimation of Substitution and Indel Rates via k-mer Statistics

Authors: Mahmudur Rahman Hera, Paul Medvedev, David Koslicki, and Antonio Blanca

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Methods utilizing k-mers are widely used in bioinformatics, yet our understanding of their statistical properties under realistic mutation models remains incomplete. Previously, substitution-only mutation models have been considered to derive precise expectations and variances for mutated k-mers and intervals of mutated and non-mutated sequences. In this work, we consider a mutation model that incorporates insertions and deletions in addition to single-nucleotide substitutions. Within this framework, we derive closed-form k-mer-based estimators for the three fundamental mutation parameters: substitution, deletion rate, and insertion rates. We provide theoretical guarantees in the form of concentration inequalities, ensuring accuracy of our estimators under reasonable model assumptions. Empirical evaluations on simulated evolution of genomic sequences confirm our theoretical findings, demonstrating that accounting for insertions and deletions signals allows for accurate estimation of mutation rates and improves upon the results obtained by considering a substitution-only model. An implementation of estimating the mutation parameters from a pair of fasta files is available here: https://github.com/KoslickiLab/estimate_rates_using_mutation_model.git. The results presented in this manuscript can be reproduced using the code available here: https://github.com/KoslickiLab/est_rates_experiments.git.
Cite as

Mahmudur Rahman Hera, Paul Medvedev, David Koslicki, and Antonio Blanca. Estimation of Substitution and Indel Rates via k-mer Statistics. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rahmanhera_et_al:LIPIcs.WABI.2025.16,
  author =	{Rahman Hera, Mahmudur and Medvedev, Paul and Koslicki, David and Blanca, Antonio},
  title =	{{Estimation of Substitution and Indel Rates via k-mer Statistics}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.16},
  URN =		{urn:nbn:de:0030-drops-239422},
  doi =		{10.4230/LIPIcs.WABI.2025.16},
  annote =	{Keywords: k-mers, mutation rate, indel, alignment-free, estimation, substitution, insertion, deletion}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.3
Private Estimation When Data and Privacy Demands Are Correlated

Authors: Syomantak Chaudhuri and Thomas A. Courtade

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
Differential Privacy (DP) is the current gold-standard for ensuring privacy for statistical queries. Estimation problems under DP constraints appearing in the literature have largely focused on providing equal privacy to all users. We consider the problems of empirical mean estimation for univariate data and frequency estimation for categorical data, both subject to heterogeneous privacy constraints. Each user, contributing a sample to the dataset, is allowed to have a different privacy demand. The dataset itself is assumed to be worst-case and we study both problems under two different formulations - first, where privacy demands and data may be correlated, and second, where correlations are weakened by random permutation of the dataset. We establish theoretical performance guarantees for our proposed algorithms, under both PAC error and mean-squared error. These performance guarantees translate to minimax optimality in several instances, and experiments confirm superior performance of our algorithms over other baseline techniques.
Cite as

Syomantak Chaudhuri and Thomas A. Courtade. Private Estimation When Data and Privacy Demands Are Correlated. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chaudhuri_et_al:LIPIcs.FORC.2025.3,
  author =	{Chaudhuri, Syomantak and Courtade, Thomas A.},
  title =	{{Private Estimation When Data and Privacy Demands Are Correlated}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.3},
  URN =		{urn:nbn:de:0030-drops-231305},
  doi =		{10.4230/LIPIcs.FORC.2025.3},
  annote =	{Keywords: Differential Privacy, Personalized Privacy, Heterogeneous Privacy, Correlations in Privacy}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.10
Count on Your Elders: Laplace vs Gaussian Noise

Authors: Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
In recent years, Gaussian noise has become a popular tool in differentially private algorithms, often replacing Laplace noise which dominated the early literature on differential privacy. Gaussian noise is the standard approach to approximate differential privacy, often resulting in much higher utility than traditional (pure) differential privacy mechanisms. In this paper we argue that Laplace noise may in fact be preferable to Gaussian noise in many settings, in particular when we seek to achieve (ε,δ)-differential privacy for small values of δ. We consider two scenarios: First, we consider the problem of counting under continual observation and present a new generalization of the binary tree mechanism that uses a k-ary number system with negative digits to improve the privacy-accuracy trade-off. Our mechanism uses Laplace noise and whenever δ is sufficiently small it improves the mean squared error over the best possible (ε,δ)-differentially private factorization mechanisms based on Gaussian noise. Specifically, using k = 19 we get an asymptotic improvement over the bound given in the work by Henzinger, Upadhyay and Upadhyay (SODA 2023) when δ = O(T^{-0.92}). Second, we show that the noise added by the Gaussian mechanism can always be replaced by Laplace noise of comparable variance for the same (ε, δ)-differential privacy guarantee, and in fact for sufficiently small δ the variance of the Laplace noise becomes strictly better. This challenges the conventional wisdom that Gaussian noise should be used for high-dimensional noise. Finally, we study whether counting under continual observation may be easier in an average-case sense than in a worst-case sense. We show that, under pure differential privacy, the expected worst-case error for a random input must be Ω(log(T)/ε), matching the known lower bound for worst-case inputs.
Cite as

Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani. Count on Your Elders: Laplace vs Gaussian Noise. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andersson_et_al:LIPIcs.FORC.2025.10,
  author =	{Andersson, Joel Daniel and Pagh, Rasmus and Steiner, Teresa Anna and Torkamani, Sahel},
  title =	{{Count on Your Elders: Laplace vs Gaussian Noise}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.10},
  URN =		{urn:nbn:de:0030-drops-231376},
  doi =		{10.4230/LIPIcs.FORC.2025.10},
  annote =	{Keywords: differential privacy, continual observation, streaming, prefix sums, trees}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.74
Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay

Authors: Noam Touitou

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We consider the online service with delay problem, in which a server traverses a metric space to serve requests that arrive over time. Requests gather individual delay cost while awaiting service, penalizing service latency; an algorithm seeks to minimize both its movement cost and the total delay cost. Algorithms for the problem (on general metric spaces) are only known for the clairvoyant model, where the algorithm knows future delay cost in advance (e.g., Azar et al., STOC'17; Azar and Touitou, FOCS'19; Touitou, STOC'23). However, in the non-clairvoyant setting, only negative results are known: where n is the size of the metric space and m is the number of requests, there are lower bounds of Ω(√n) and Ω(√m) on competitiveness (Azar et al., STOC'17), that hold even for randomized algorithms (Le et al., SODA'23). In this paper, we present the first algorithm for non-clairvoyant online service with delay. Our algorithm is deterministic and O(min{√n log n, √m log m})-competitive; combined with the lower bounds of Azar et al., this settles the correct competitive ratio for the problem up to logarithmic factors, in terms of both n and m.
Cite as

Noam Touitou. Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 74:1-74:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{touitou:LIPIcs.STACS.2025.74,
  author =	{Touitou, Noam},
  title =	{{Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{74:1--74:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.74},
  URN =		{urn:nbn:de:0030-drops-228995},
  doi =		{10.4230/LIPIcs.STACS.2025.74},
  annote =	{Keywords: Online, Delay, Deadlines, k-server, Non-clairvoyant}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.70
Universal Algorithms for Clustering Problems

Authors: Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
This paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)-approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other 𝓁_p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))-approximation is the strongest type of guarantee obtainable for universal clustering.
Cite as

Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Universal Algorithms for Clustering Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ICALP.2021.70,
  author =	{Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya},
  title =	{{Universal Algorithms for Clustering Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{70:1--70:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.70},
  URN =		{urn:nbn:de:0030-drops-141397},
  doi =		{10.4230/LIPIcs.ICALP.2021.70},
  annote =	{Keywords: universal algorithms, clustering, k-median, k-means, k-center}
}
Document
DOI: 10.4230/LIPIcs.FORC.2021.1
Privately Answering Counting Queries with Generalized Gaussian Mechanisms

Authors: Arun Ganesh and Jiazheng Zhao

Published in: LIPIcs, Volume 192, 2nd Symposium on Foundations of Responsible Computing (FORC 2021)

Abstract
We give the first closed-form privacy guarantees for the Generalized Gaussian mechanism (the mechanism that adds noise x to a vector with probability proportional to exp(-(||x||_p/σ)^p) for some σ, p), in the setting of answering k counting (i.e. sensitivity-1) queries about a database with (ε, δ)-differential privacy (in particular, with low 𝓁_∞-error). Just using Generalized Gaussian noise, we obtain a mechanism such that if the true answers to the queries are the vector d, the mechanism outputs answers d̃ with the 𝓁_∞-error guarantee: 𝔼[||d̃ - d||_∞] = O(√{k log log k log(1/δ)}/ε). This matches the error bound of [Steinke and Ullman, 2017], but using a much simpler mechanism. By composing this mechanism with the sparse vector mechanism (generalizing a technique of [Steinke and Ullman, 2017]), we obtain a mechanism improving the √{k log log k} dependence on k to √{k log log log k}, Our main technical contribution is showing that certain powers of Generalized Gaussians, which follow a Generalized Gamma distribution, are sub-gamma. In subsequent work, the optimal 𝓁_∞-error bound of O(√{k log (1/δ)}/ε) has been achieved by [Yuval Dagan and Gil Kur, 2020] and [Badih Ghazi et al., 2020] independently. However, the Generalized Gaussian mechanism has some qualitative advantages over the mechanisms used in these papers which may make it of interest to both practitioners and theoreticians, both in the setting of answering counting queries and more generally.
Cite as

Arun Ganesh and Jiazheng Zhao. Privately Answering Counting Queries with Generalized Gaussian Mechanisms. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.FORC.2021.1,
  author =	{Ganesh, Arun and Zhao, Jiazheng},
  title =	{{Privately Answering Counting Queries with Generalized Gaussian Mechanisms}},
  booktitle =	{2nd Symposium on Foundations of Responsible Computing (FORC 2021)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-187-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{192},
  editor =	{Ligett, Katrina and Gupta, Swati},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2021.1},
  URN =		{urn:nbn:de:0030-drops-138698},
  doi =		{10.4230/LIPIcs.FORC.2021.1},
  annote =	{Keywords: Differential privacy, counting queries, Generalized Gaussians}
}
Document
DOI: 10.4230/LIPIcs.WABI.2020.17
Near-Linear Time Edit Distance for Indel Channels

Authors: Arun Ganesh and Aaron Sy

Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)

Abstract
We consider the following model for sampling pairs of strings: s₁ is a uniformly random bitstring of length n, and s₂ is the bitstring arrived at by applying substitutions, insertions, and deletions to each bit of s₁ with some probability. We show that the edit distance between s₁ and s₂ can be computed in O(n ln n) time with high probability, as long as each bit of s₁ has a mutation applied to it with probability at most a small constant. The algorithm is simple and only uses the textbook dynamic programming algorithm as a primitive, first computing an approximate alignment between the two strings, and then running the dynamic programming algorithm restricted to entries close to the approximate alignment. The analysis of our algorithm provides theoretical justification for alignment heuristics used in practice such as BLAST, FASTA, and MAFFT, which also start by computing approximate alignments quickly and then find the best alignment near the approximate alignment. Our main technical contribution is a partitioning of alignments such that the number of the subsets in the partition is not too large and every alignment in one subset is worse than an alignment considered by our algorithm with high probability. Similar techniques may be of interest in the average-case analysis of other problems commonly solved via dynamic programming.
Cite as

Arun Ganesh and Aaron Sy. Near-Linear Time Edit Distance for Indel Channels. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.WABI.2020.17,
  author =	{Ganesh, Arun and Sy, Aaron},
  title =	{{Near-Linear Time Edit Distance for Indel Channels}},
  booktitle =	{20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-161-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{172},
  editor =	{Kingsford, Carl and Pisanti, Nadia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.17},
  URN =		{urn:nbn:de:0030-drops-128061},
  doi =		{10.4230/LIPIcs.WABI.2020.17},
  annote =	{Keywords: edit distance, average-case analysis, dynamic programming, sequence alignment}
}
  • Refine by Type
  • 16 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 6 2026
  • 6 2025
  • 2 2021
  • 2 2020

  • Refine by Author
  • 4 Ganesh, Arun
  • 2 Andersson, Joel Daniel
  • 2 Maggs, Bruce M.
  • 2 Panigrahi, Debmalya
  • 1 Alizadeh, Mohammad
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 3 Security and privacy → Privacy-preserving protocols
  • 2 Computing methodologies → Machine learning
  • 2 Security and privacy
  • 1 Applied computing → Computational biology
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • Show More...

  • Refine by Keyword
  • 3 differential privacy
  • 2 Differential privacy
  • 2 continual observation
  • 1 Correlations in Privacy
  • 1 Deadlines
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact