5 Search Results for "Goyal, Navin"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.161
Nonuniform Deterministic Finite Automata over Finite Algebraic Structures

Authors: Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski

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

Abstract
Nonuniform deterministic finite automata (NUDFA) over monoids were invented by Barrington in [Barrington, 1985] to study boundaries of nonuniform constant-memory computation. Later, results on these automata helped to identify interesting classes of groups for which equation satisfiability problem (PolSat) is solvable in (probabilistic) polynomial time [Mikael Goldmann and Alexander Russell, 2002; Idziak et al., 2022]. Based on these results, we present a full characterization of groups, for which the identity checking problem (called PolEqv) has a probabilistic polynomial-time algorithm. We also go beyond groups, and propose how to generalise the notion of NUDFA to arbitrary finite algebraic structures. We study satisfiability of these automata in this more general setting. As a consequence, we present a full description of finite algebras from congruence modular varieties for which testing circuit equivalence CEqv can be solved by a probabilistic polynomial-time procedure. In our proofs we use two computational complexity assumptions: randomized Expotential Time Hypothesis and Constant Degree Hypothesis.
Cite as

Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Nonuniform Deterministic Finite Automata over Finite Algebraic Structures. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 161:1-161:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{idziak_et_al:LIPIcs.ICALP.2025.161,
  author =	{Idziak, Pawe{\l} M. and Kawa{\l}ek, Piotr and Krzaczkowski, Jacek},
  title =	{{Nonuniform Deterministic Finite Automata over Finite Algebraic Structures}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{161:1--161:14},
  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.161},
  URN =		{urn:nbn:de:0030-drops-235386},
  doi =		{10.4230/LIPIcs.ICALP.2025.161},
  annote =	{Keywords: program satisfiability, circuit equivalence, identity checking}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.13
Quantum Speedup for Sampling Random Spanning Trees

Authors: Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu

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

Abstract
We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
Cite as

Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu. Quantum Speedup for Sampling Random Spanning Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ICALP.2025.13,
  author =	{Apers, Simon and Gao, Minbo and Ji, Zhengfeng and Liu, Chenghua},
  title =	{{Quantum Speedup for Sampling Random Spanning Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{13:1--13:21},
  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.13},
  URN =		{urn:nbn:de:0030-drops-233907},
  doi =		{10.4230/LIPIcs.ICALP.2025.13},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Random Spanning Trees}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.58
Violating Constant Degree Hypothesis Requires Breaking Symmetry

Authors: Piotr Kawałek and Armin Weiß

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

Abstract
The Constant Degree Hypothesis was introduced by Barrington et. al. [David A. Mix Barrington et al., 1990] to study some extensions of q-groups by nilpotent groups and the power of these groups in a computation model called NuDFA (non-uniform DFA). In its simplest formulation, it establishes exponential lower bounds for MOD_q∘MOD_m∘AND_d circuits computing AND of unbounded arity n (for constant integers d,m and a prime q). While it has been proved in some special cases (including d = 1), it remains wide open in its general form for over 30 years. In this paper we prove that the hypothesis holds when we restrict our attention to symmetric circuits with m being a prime. While we build upon techniques by Grolmusz and Tardos [Vince Grolmusz and Gábor Tardos, 2000], we have to prove a new symmetric version of their Degree Decreasing Lemma and use it to simplify circuits in a symmetry-preserving way. Moreover, to establish the result, we perform a careful analysis of automorphism groups of MOD_m∘AND_d subcircuits and study the periodic behaviour of the computed functions. Our methods also yield lower bounds when d is treated as a function of n. Finally, we present a construction of symmetric MOD_q∘MOD_m∘AND_d circuits that almost matches our lower bound and conclude that a symmetric function f can be computed by symmetric MOD_q∘MOD_p∘AND_d circuits of quasipolynomial size if and only if f has periods of polylogarithmic length of the form p^k q^𝓁.
Cite as

Piotr Kawałek and Armin Weiß. Violating Constant Degree Hypothesis Requires Breaking Symmetry. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 58:1-58:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawalek_et_al:LIPIcs.STACS.2025.58,
  author =	{Kawa{\l}ek, Piotr and Wei{\ss}, Armin},
  title =	{{Violating Constant Degree Hypothesis Requires Breaking Symmetry}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{58:1--58: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.58},
  URN =		{urn:nbn:de:0030-drops-228837},
  doi =		{10.4230/LIPIcs.STACS.2025.58},
  annote =	{Keywords: Circuit lower bounds, constant degree hypothesis, permutation groups, CC⁰-circuits}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.23
Online Carpooling Using Expander Decompositions

Authors: Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
We consider the online carpooling problem: given n vertices, a sequence of edges arrive over time. When an edge e_t = (u_t, v_t) arrives at time step t, the algorithm must orient the edge either as v_t → u_t or u_t → v_t, with the objective of minimizing the maximum discrepancy of any vertex, i.e., the absolute difference between its in-degree and out-degree. Edges correspond to pairs of persons wanting to ride together, and orienting denotes designating the driver. The discrepancy objective then corresponds to every person driving close to their fair share of rides they participate in. In this paper, we design efficient algorithms which can maintain polylog(n,T) maximum discrepancy (w.h.p) over any sequence of T arrivals, when the arriving edges are sampled independently and uniformly from any given graph G. This provides the first polylogarithmic bounds for the online (stochastic) carpooling problem. Prior to this work, the best known bounds were O(√{n log n})-discrepancy for any adversarial sequence of arrivals, or O(log log n)-discrepancy bounds for the stochastic arrivals when G is the complete graph. The technical crux of our paper is in showing that the simple greedy algorithm, which has provably good discrepancy bounds when the arriving edges are drawn uniformly at random from the complete graph, also has polylog discrepancy when G is an expander graph. We then combine this with known expander-decomposition results to design our overall algorithm.
Cite as

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla. Online Carpooling Using Expander Decompositions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2020.23,
  author =	{Gupta, Anupam and Krishnaswamy, Ravishankar and Kumar, Amit and Singla, Sahil},
  title =	{{Online Carpooling Using Expander Decompositions}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.23},
  URN =		{urn:nbn:de:0030-drops-132647},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.23},
  annote =	{Keywords: Online Algorithms, Discrepancy Minimization, Carpooling}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.58
Lower Bounds for the Average and Smoothed Number of Pareto Optima

Authors: Navin Goyal and Luis Rademacher

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
Smoothed analysis of multiobjective 0-1 linear optimization has drawn considerable attention recently. In this literature, the number of Pareto-optimal solutions (i.e., solutions with the property that no other solution is at least as good in all the coordinates and better in at least one) for multiobjective optimization problems is the central object of study. In this paper, we prove several lower bounds for the expected number of Pareto optima. Our basic result is a lower bound of Omega_d(n^{d-1}) for optimization problems with d objectives and $n$ variables under fairly general conditions on the distributions of the linear objectives. Our proof relates the problem of lower bounding the number of Pareto optima to results in discrete geometry and geometric probability connected to arrangements of hyperplanes. We use our basic result to derive (1) To our knowledge, the first lower bound for natural multiobjective optimization problems. We illustrate this for the maximum spanning tree problem with randomly chosen edge weights. Our technique is sufficiently flexible to yield such lower bounds for other standard objective functions studied in this setting (such as multiobjective shortest path, TSP tour, matching). (2) Smoothed lower bound of min(Omega_d( n^{d-1.5} phi^{(d-\log d) (1-Theta(1/phi))}), 2^{Theta(n)}) for the 0-1 knapsack problem with d profits for phi-semirandom distributions for a version of the knapsack problem. This improves the recent lower bound of Brunsch and Röglin.
Cite as

Navin Goyal and Luis Rademacher. Lower Bounds for the Average and Smoothed Number of Pareto Optima. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 58-69, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.FSTTCS.2012.58,
  author =	{Goyal, Navin and Rademacher, Luis},
  title =	{{Lower Bounds for the Average and Smoothed Number of Pareto Optima}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{58--69},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.58},
  URN =		{urn:nbn:de:0030-drops-38488},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.58},
  annote =	{Keywords: geometric probability, smoothed analysis, multiobjective optimization, Pareto optimal, knapsack}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2020
  • 1 2012

  • Refine by Author
  • 2 Kawałek, Piotr
  • 1 Apers, Simon
  • 1 Gao, Minbo
  • 1 Goyal, Navin
  • 1 Gupta, Anupam
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Complexity classes
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 1 CC⁰-circuits
  • 1 Carpooling
  • 1 Circuit lower bounds
  • 1 Discrepancy Minimization
  • 1 Online Algorithms
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact