74 Search Results for "Vishnoi, Nisheeth K."

Volume

LIPIcs, Volume 24

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

FSTTCS 2013, December 12-14, 2013, Guwahati, India

Editors: Anil Seth and Nisheeth K. Vishnoi

Document
DOI: 10.4230/LIPIcs.STACS.2026.13
Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.3
Linear Matroid Intersection Is in Catalytic Logspace

Authors: Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of {P}. We address this problem for the class catalytic logspace (CL) with a polynomial time bound (CLP). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class CLP ⊆ {P}. This was the first subclass of {P} shown to contain bipartite matching, and additionally the first problem outside TC¹ shown to be contained in CL. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in CLP.
Cite as

Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear Matroid Intersection Is in Catalytic Logspace. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.3,
  author =	{Agarwala, Aryan and Alekseev, Yaroslav and Vinciguerra, Antoine},
  title =	{{Linear Matroid Intersection Is in Catalytic Logspace}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.3},
  URN =		{urn:nbn:de:0030-drops-252908},
  doi =		{10.4230/LIPIcs.ITCS.2026.3},
  annote =	{Keywords: Catalytic Computing, Computational Complexity, Matroid Theory, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.63
Perfect Simulation of Las Vegas Algorithms via Local Computation

Authors: Xinyu Fu, Yonggang Jiang, and Yitong Yin

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The notion of Las Vegas algorithms was introduced by Babai (1979) and can be defined in two ways: - In Babai’s original definition, a randomized algorithm is called Las Vegas if it has a finitely bounded running time and certifiable random failure. - Another definition widely accepted today is that Las Vegas algorithms refer to zero-error randomized algorithms with random running times. The equivalence between the two definitions is straightforward. Specifically, for randomized algorithms with certifiable failures, repeatedly running the algorithm until no failure is encountered allows for faithful simulation of the correct output when it executes successfully. We show that a similar perfect simulation can also be achieved in distributed local computation. Specifically, in the LOCAL model, with a polylogarithmic overhead in time complexity, any Las Vegas algorithm with finitely bounded running time and locally certifiable failures can be converted to a zero error Las Vegas algorithm. This transformed algorithm faithfully reproduces the correct output of the original algorithm in successful executions. This is achieved by a reduction to a distributed sampling problem under the Lovász Local Lemma (LLL), where the objective is to sample from the joint distribution of random variables avoiding all bad events. We then design the first efficient algorithm to solve this sampling problem in the LOCAL model.
Cite as

Xinyu Fu, Yonggang Jiang, and Yitong Yin. Perfect Simulation of Las Vegas Algorithms via Local Computation. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 63:1-63:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ITCS.2026.63,
  author =	{Fu, Xinyu and Jiang, Yonggang and Yin, Yitong},
  title =	{{Perfect Simulation of Las Vegas Algorithms via Local Computation}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{63:1--63:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.63},
  URN =		{urn:nbn:de:0030-drops-253503},
  doi =		{10.4230/LIPIcs.ITCS.2026.63},
  annote =	{Keywords: Las Vegas algorithms, perfect simulation, Lov\'{a}sz Local Lemma, sampling}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.89
On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

Authors: Tsz Chiu Kwok, Zhewei Wei, and Mingji Yang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system 𝐌x = b in sublinear time, with the goal of estimating t^{⊤}x^{∗} for a given vector t ∈ ℝⁿ and a specific solution x^{∗}. This setting naturally generalizes the study of sublinear-time solvers for symmetric diagonally dominant (SDD) systems [Andoni-Krauthgamer-Pogrow, ITCS 2019] to the asymmetric case, which has remained underexplored despite extensive work on nearly-linear-time solvers for RDD/CDD systems. Our first contributions are characterizations of the problem’s mathematical structure. We express a solution x^{∗} via a Neumann series, prove its convergence, and upper bound the truncation error on this series through a novel quantity of 𝐌, termed the maximum p-norm gap. This quantity generalizes the spectral gap of symmetric matrices and captures how the structure of 𝐌 governs the problem’s computational difficulty. For systems with bounded maximum p-norm gap, we develop a collection of algorithmic results for locally approximating t^{⊤}x^{∗} under various scenarios and error measures. We derive these results by adapting the techniques of random-walk sampling, local push, and their bidirectional combination, which have proved powerful for special cases of solving RDD/CDD systems, particularly estimating PageRank and effective resistance on graphs. Our general framework yields deeper insights, extended results, and improved complexity bounds for these problems. Notably, our perspective provides a unified understanding of Forward Push and Backward Push, two fundamental approaches for estimating random-walk probabilities on graphs. Our framework also inherits the hardness results for sublinear-time SDD solvers and local PageRank computation, establishing lower bounds on the maximum p-norm gap or the accuracy parameter. We hope that our work opens the door for further study into sublinear solvers, local graph algorithms, and directed spectral graph theory.
Cite as

Tsz Chiu Kwok, Zhewei Wei, and Mingji Yang. On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 89:1-89:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kwok_et_al:LIPIcs.ITCS.2026.89,
  author =	{Kwok, Tsz Chiu and Wei, Zhewei and Yang, Mingji},
  title =	{{On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{89:1--89:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.89},
  URN =		{urn:nbn:de:0030-drops-253768},
  doi =		{10.4230/LIPIcs.ITCS.2026.89},
  annote =	{Keywords: Spectral Graph Theory, Linear Systems, Sublinear Algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.8
Parameterized Verification of Timed Networks with Clock Invariants

Authors: Étienne André, Swen Jacobs, Shyam Lal Karra, and Ocan Sankur

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We consider parameterized verification problems for networks of timed automata (TAs) based on different communication primitives. To this end, we first consider disjunctive timed networks (DTNs), i.e., networks of TAs that communicate via location guards that enable a transition only if there is another process in a certain location. We solve for the first time the case with unrestricted clock invariants, and establish that the parameterized model checking problem (PMCP) over finite local traces can be reduced to the corresponding model checking problem on a single TA. Moreover, we prove that the PMCP for networks that communicate via lossy broadcast can be reduced to the PMCP for DTNs. Finally, we show that for networks with k-wise synchronization, and therefore also for timed Petri nets, location reachability can be reduced to location reachability in DTNs. As a consequence we can answer positively the open problem from Abdulla et al. (2018) whether the universal safety problem for timed Petri nets with multiple clocks is decidable.
Cite as

Étienne André, Swen Jacobs, Shyam Lal Karra, and Ocan Sankur. Parameterized Verification of Timed Networks with Clock Invariants. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andre_et_al:LIPIcs.FSTTCS.2025.8,
  author =	{Andr\'{e}, \'{E}tienne and Jacobs, Swen and Karra, Shyam Lal and Sankur, Ocan},
  title =	{{Parameterized Verification of Timed Networks with Clock Invariants}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.8},
  URN =		{urn:nbn:de:0030-drops-250878},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.8},
  annote =	{Keywords: Networks of Timed Automata, Parameterized Verification, Timed Petri Nets}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.46
Efficient Parallel Ising Samplers via Localization Schemes

Authors: Xiaoyu Chen, Hongyang Liu, Yitong Yin, and Xinyuan Zhang

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficiency, with polylogarithmic depth and polynomial total work, and are applicable to Ising models in the following regimes: (1) Ferromagnetic Ising models with external fields; (2) Ising models with interaction matrix J of operator norm ‖J‖₂ < 1. Our parallel Gibbs sampling approaches are based on localization schemes, which have proven highly effective in establishing rapid mixing of Gibbs sampling. In this work, we employ two such localization schemes to obtain efficient parallel Ising samplers: the field dynamics induced by negative-field localization, and restricted Gaussian dynamics induced by stochastic localization. This shows that localization schemes are powerful tools, not only for achieving rapid mixing but also for the efficient parallelization of Gibbs sampling.
Cite as

Xiaoyu Chen, Hongyang Liu, Yitong Yin, and Xinyuan Zhang. Efficient Parallel Ising Samplers via Localization Schemes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 46:1-46:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.46,
  author =	{Chen, Xiaoyu and Liu, Hongyang and Yin, Yitong and Zhang, Xinyuan},
  title =	{{Efficient Parallel Ising Samplers via Localization Schemes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{46:1--46:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.46},
  URN =		{urn:nbn:de:0030-drops-244129},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.46},
  annote =	{Keywords: Localization scheme, parallel sampling, Ising model}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.5
Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT

Authors: Aditya Anand, Euiwoong Lee, Davide Mazzali, and Amatya Sharma

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
This paper studies complete k-Constraint Satisfaction Problems (CSPs), where an n-variable instance has exactly one nontrivial constraint for each subset of k variables, i.e., it has binom(n,k) constraints. A recent work started a systematic study of complete k-CSPs [Anand, Lee, Sharma, SODA'25], and showed a quasi-polynomial time algorithm that decides if there is an assignment satisfying all the constraints of any complete Boolean-alphabet k-CSP, algorithmically separating complete instances from dense instances. The tractability of this decision problem is necessary for any nontrivial (multiplicative) approximation for the minimization version, whose goal is to minimize the number of violated constraints. The same paper raised the question of whether it is possible to obtain nontrivial approximation algorithms for complete Min-k-CSPs with k ≥ 3. In this work, we make progress in this direction and show a quasi-polynomial time polylog(n)-approximation to Min-NAE-3-SAT on complete instances, which asks to minimize the number of 3-clauses where all the three literals equal the same bit. To the best of our knowledge, this is the first known example of a CSP whose decision version is NP-Hard in general (and dense) instances while admitting a polylog(n)-approximation in complete instances. Our algorithm presents a new iterative framework for rounding a solution from the Sherali-Adams hierarchy, where each iteration interleaves the two well-known rounding tools: the conditioning procedure, in order to "almost fix" many variables, and the thresholding procedure, in order to "completely fix" them. Finally, we improve the running time of the decision algorithms of Anand, Lee, and Sharma and show a simple algorithm that decides any complete Boolean-alphabet k-CSP in polynomial time.
Cite as

Aditya Anand, Euiwoong Lee, Davide Mazzali, and Amatya Sharma. Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.APPROX/RANDOM.2025.5,
  author =	{Anand, Aditya and Lee, Euiwoong and Mazzali, Davide and Sharma, Amatya},
  title =	{{Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.5},
  URN =		{urn:nbn:de:0030-drops-243712},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.5},
  annote =	{Keywords: Constraint Satisfiability Problems, Approximation Algorithms, Sherali Adams}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.16
Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs

Authors: Tommaso d'Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, and Jiyu Zhang

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Whether or not the Sparsest Cut problem admits an efficient O(1)-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture. Revisiting spectral algorithms for Sparsest Cut, we present a novel, simple algorithm that combines eigenspace enumeration with a new algorithm for the Cut Improvement problem. The runtime of our algorithm is parametrized by a quantity that we call the solution dimension SD_ε(G): the smallest k such that the subspace spanned by the first k Laplacian eigenvectors contains all but ε fraction of a sparsest cut. Our algorithm matches the guarantees of prior methods based on the threshold-rank paradigm, while also extending beyond them. To illustrate this, we study its performance on low degree Cayley graphs over Abelian groups - canonical examples of graphs with poor expansion properties. We prove that low degree Abelian Cayley graphs have small solution dimension, yielding an algorithm that computes a (1+ε)-approximation to the uniform Sparsest Cut of a degree-d Cayley graph over an Abelian group of size n in time n^O(1) ⋅ exp{(d/ε)^O(d)}. Along the way to bounding the solution dimension of Abelian Cayley graphs, we analyze their sparse cuts and spectra, proving that the collection of O(1)-approximate sparsest cuts has an ε-net of size exp{(d/ε)^O(d)} and that the multiplicity of λ₂ is bounded by 2^O(d). The latter bound is tight and improves on a previous bound of 2^O(d²) by Lee and Makarychev.
Cite as

Tommaso d'Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, and Jiyu Zhang. Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dorsi_et_al:LIPIcs.APPROX/RANDOM.2025.16,
  author =	{d'Orsi, Tommaso and Jones, Chris and Ruotolo, Jake and Vadhan, Salil and Zhang, Jiyu},
  title =	{{Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.16},
  URN =		{urn:nbn:de:0030-drops-243827},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.16},
  annote =	{Keywords: Sparsest Cut, Spectral Graph Theory, Cayley Graphs, Approximation Algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.19
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

Authors: Ian DeHaan, Neng Huang, and Euiwoong Lee

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language Γ which has the dual discriminator operation as a polymorphism, there exists a |D|-approximation algorithm for MinCostCSP(Γ) where D is the domain. Complementing our algorithmic result, we show that any constraint language Γ where MinCostCSP(Γ) admits a constant-factor approximation must have a near-unanimity (NU) polymorphism unless P = NP, extending a similar result by Dalmau et al. on MinCSPs. These results imply a dichotomy of constant-factor approximability for constraint languages that contain all permutation relations (a natural generalization for Boolean CSPs that allow variable negation): either MinCostCSP(Γ) has an NU polymorphism and is |D|-approximable, or it does not have any NU polymorphism and is NP-hard to approximate within any constant factor. Finally, we present a constraint language which has a majority polymorphism, but is nonetheless NP-hard to approximate within any constant factor assuming the Unique Games Conjecture, showing that the condition of having an NU polymorphism is in general not sufficient unless UGC fails.
Cite as

Ian DeHaan, Neng Huang, and Euiwoong Lee. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dehaan_et_al:LIPIcs.APPROX/RANDOM.2025.19,
  author =	{DeHaan, Ian and Huang, Neng and Lee, Euiwoong},
  title =	{{On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  URN =		{urn:nbn:de:0030-drops-243851},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  annote =	{Keywords: Constraint satisfaction problems, approximation algorithms, polymorphisms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.21
Dual Charging for Half-Integral TSP

Authors: Nathan Klein and Mehrshad Taziki

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this extended abstract, we show that the max entropy algorithm is a randomized 1.49776 approximation for half-integral TSP, improving upon the previous known bound of 1.49993 from Karlin et al. This also improves upon the best-known approximation for half-integral TSP due to Gupta et al. Our improvement results from using the dual, instead of the primal, to analyze the expected cost of the matching. We believe this method of analysis could lead to a simpler proof that max entropy is a better-than-3/2 approximation in the general case.
Cite as

Nathan Klein and Mehrshad Taziki. Dual Charging for Half-Integral TSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.APPROX/RANDOM.2025.21,
  author =	{Klein, Nathan and Taziki, Mehrshad},
  title =	{{Dual Charging for Half-Integral TSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.21},
  URN =		{urn:nbn:de:0030-drops-243879},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.21},
  annote =	{Keywords: Approximation Algorithms, Graph Algorithms, Randomized Rounding, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.TQC.2025.3
Mixing Time of Quantum Gibbs Sampling for Random Sparse Hamiltonians

Authors: Akshar Ramkumar and Mehdi Soleimanifar

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm [Chen et al., 2023] provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n × n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.
Cite as

Akshar Ramkumar and Mehdi Soleimanifar. Mixing Time of Quantum Gibbs Sampling for Random Sparse Hamiltonians. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ramkumar_et_al:LIPIcs.TQC.2025.3,
  author =	{Ramkumar, Akshar and Soleimanifar, Mehdi},
  title =	{{Mixing Time of Quantum Gibbs Sampling for Random Sparse Hamiltonians}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.3},
  URN =		{urn:nbn:de:0030-drops-240520},
  doi =		{10.4230/LIPIcs.TQC.2025.3},
  annote =	{Keywords: Quantum algorithms, quantum Gibbs sampling, mixing time analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.49
Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game

Authors: Antares Chen, Lorenzo Orecchia, and Erasmo Tani

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Despite there being significant work on developing spectral- [Chan et al., 2018; Lau et al., 2023; Kwok et al., 2022], and metric-embedding-based [Louis and Makarychev, 2016] approximation algorithms for hypergraph conductance, little is known regarding the approximability of other hypergraph partitioning objectives. This work proposes algorithms for a general model of hypergraph partitioning that unifies both undirected and directed versions of many well-studied partitioning objectives. The first contribution of this paper introduces polymatroidal cut functions, a large class of cut functions amenable to approximation algorithms via metric embeddings and routing multicommodity flows. We demonstrate a simple O(√{log n})-approximation, where n is the number of vertices in the hypergraph, for these problems by rounding relaxations to metrics of negative-type. The second contribution of this paper generalizes the cut-matching game framework of Khandekar et al. [Khandekar et al., 2007] to tackle polymatroidal cut functions. This yields an almost-linear time O(log n)-approximation algorithm for standard versions of undirected and directed hypergraph partitioning [Kwok et al., 2022]. A technical contribution of our construction is a novel cut-matching game, which greatly relaxes the set of allowed actions by the cut player and allows for the use of approximate s-t maximum flows by the matching player. We believe this to be of independent interest.
Cite as

Antares Chen, Lorenzo Orecchia, and Erasmo Tani. Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.49,
  author =	{Chen, Antares and Orecchia, Lorenzo and Tani, Erasmo},
  title =	{{Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.49},
  URN =		{urn:nbn:de:0030-drops-234261},
  doi =		{10.4230/LIPIcs.ICALP.2025.49},
  annote =	{Keywords: Hypergraph Partitioning, Cut Improvement, Cut-Matching Game}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.6
Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method

Authors: Deeksha Adil and Thatchaphol Saranurak

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a dynamic algorithm for maintaining (1+ε)-approximate maximum eigenvector and eigenvalue of a positive semi-definite matrix A undergoing decreasing updates, i.e., updates which may only decrease eigenvalues. Given a vector v updating A ← A-vv^⊤, our algorithm takes Õ(nnz(v)) amortized update time, i.e., polylogarithmic per non-zeros in the update vector. Our technique is based on a novel analysis of the influential power method in the dynamic setting. The two previous sets of techniques have the following drawbacks (1) algebraic techniques can maintain exact solutions but their update time is at least polynomial per non-zeros, and (2) sketching techniques admit polylogarithmic update time but suffer from a crude additive approximation. Our algorithm exploits an oblivious adversary. Interestingly, we show that any algorithm with polylogarithmic update time per non-zeros that works against an adaptive adversary and satisfies an additional natural property would imply a breakthrough for checking psd-ness of matrices in Õ(n²) time, instead of O(n^ω) time.
Cite as

Deeksha Adil and Thatchaphol Saranurak. Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adil_et_al:LIPIcs.ICALP.2025.6,
  author =	{Adil, Deeksha and Saranurak, Thatchaphol},
  title =	{{Decremental (1+\epsilon)-Approximate Maximum Eigenvector: Dynamic Power Method}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.6},
  URN =		{urn:nbn:de:0030-drops-233834},
  doi =		{10.4230/LIPIcs.ICALP.2025.6},
  annote =	{Keywords: Power Method, Dynamic Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.29
Guessing Efficiently for Constrained Subspace Approximation

Authors: Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, and David P. Woodruff

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper we study constrained subspace approximation problem. Given a set of n points {a₁,…,a_n} in ℝ^d, the goal of the subspace approximation problem is to find a k dimensional subspace that best approximates the input points. More precisely, for a given p ≥ 1, we aim to minimize the pth power of the 𝓁_p norm of the error vector (‖a₁-Pa₁‖,…,‖a_n-Pa_n‖), where P denotes the projection matrix onto the subspace and the norms are Euclidean. In constrained subspace approximation (CSA), we additionally have constraints on the projection matrix P. In its most general form, we require P to belong to a given subset 𝒮 that is described explicitly or implicitly. We introduce a general framework for constrained subspace approximation. Our approach, that we term coreset-guess-solve, yields either (1+ε)-multiplicative or ε-additive approximations for a variety of constraints. We show that it provides new algorithms for partition-constrained subspace approximation with applications to fair subspace approximation, k-means clustering, and projected non-negative matrix factorization, among others. Specifically, while we reconstruct the best known bounds for k-means clustering in Euclidean spaces, we improve the known results for the remainder of the problems.
Cite as

Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, and David P. Woodruff. Guessing Efficiently for Constrained Subspace Approximation. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhaskara_et_al:LIPIcs.ICALP.2025.29,
  author =	{Bhaskara, Aditya and Mahabadi, Sepideh and Pittu, Madhusudhan Reddy and Vakilian, Ali and Woodruff, David P.},
  title =	{{Guessing Efficiently for Constrained Subspace Approximation}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.29},
  URN =		{urn:nbn:de:0030-drops-234068},
  doi =		{10.4230/LIPIcs.ICALP.2025.29},
  annote =	{Keywords: parameterized complexity, low rank approximation, fairness, non-negative matrix factorization, clustering}
}
  • Refine by Type
  • 73 Document/PDF
  • 17 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 4 2026
  • 13 2025
  • 1 2023
  • 1 2019
  • 3 2018
  • Show More...

  • Refine by Author
  • 10 Vishnoi, Nisheeth K.
  • 3 Chakaravarthy, Venkatesan T.
  • 2 Celis, L. Elisa
  • 2 Choudhury, Anamitra Roy
  • 2 Fomin, Fedor V.
  • Show More...

  • Refine by Series/Journal
  • 73 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Approximation algorithms analysis
  • 2 Mathematics of computing → Spectra of graphs
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Facility location and clustering
  • 2 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 7 Approximation Algorithms
  • 4 approximation algorithms
  • 3 Automata
  • 2 Algorithms
  • 2 Approximation Algorithm
  • 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