3 Search Results for "Gajulapalli, Karthik"

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.30
Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs

Authors: David Eppstein and Daniel Frishberg

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We give a new rapid mixing result for a natural random walk on the independent sets of a graph G. We show that when G has bounded treewidth, this random walk - known as the Glauber dynamics for the hardcore model - mixes rapidly for all fixed values of the standard parameter λ > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets, b-edge covers, b-matchings, maximal independent sets, and maximal b-matchings. (For b-matchings, maximal independent sets, and maximal b-matchings we also require bounded degree.) Our results imply simpler alternatives to known algorithms for the sampling and approximate counting problems in these graphs. We prove our results by applying a divide-and-conquer framework we developed in a previous paper, as an alternative to the projection-restriction technique introduced by Jerrum, Son, Tetali, and Vigoda. We extend this prior framework to handle chains for which the application of that framework is not straightforward, strengthening existing results by Dyer, Goldberg, and Jerrum and by Heinrich for the Glauber dynamics on q-colorings of graphs of bounded treewidth and bounded degree.
Cite as

David Eppstein and Daniel Frishberg. Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ISAAC.2023.30,
  author =	{Eppstein, David and Frishberg, Daniel},
  title =	{{Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.30},
  URN =		{urn:nbn:de:0030-drops-193324},
  doi =		{10.4230/LIPIcs.ISAAC.2023.30},
  annote =	{Keywords: Glauber dynamics, mixing time, projection-restriction, multicommodity flow}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.65
Range Avoidance for Constant Depth Circuits: Hardness and Algorithms

Authors: Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi

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

Abstract
Range Avoidance (Avoid) is a total search problem where, given a Boolean circuit 𝖢: {0,1}ⁿ → {0,1}^m, m > n, the task is to find a y ∈ {0,1}^m outside the range of 𝖢. For an integer k ≥ 2, NC⁰_k-Avoid is a special case of Avoid where each output bit of 𝖢 depends on at most k input bits. While there is a very natural randomized algorithm for Avoid, a deterministic algorithm for the problem would have many interesting consequences. Ren, Santhanam, and Wang (FOCS 2022) and Guruswami, Lyu, and Wang (RANDOM 2022) proved that explicit constructions of functions of high formula complexity, rigid matrices, and optimal linear codes, reduce to NC⁰₄-Avoid, thus establishing conditional hardness of the NC⁰₄-Avoid problem. On the other hand, NC⁰₂-Avoid admits polynomial-time algorithms, leaving the question about the complexity of NC⁰₃-Avoid open. We give the first reduction of an explicit construction question to NC⁰₃-Avoid. Specifically, we prove that a polynomial-time algorithm (with an NP oracle) for NC⁰₃-Avoid for the case of m = n+n^{2/3} would imply an explicit construction of a rigid matrix, and, thus, a super-linear lower bound on the size of log-depth circuits. We also give deterministic polynomial-time algorithms for all NC⁰_k-Avoid problems for m ≥ n^{k-1}/log(n). Prior work required an NP oracle, and required larger stretch, m ≥ n^{k-1}.
Cite as

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi. Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.APPROX/RANDOM.2023.65,
  author =	{Gajulapalli, Karthik and Golovnev, Alexander and Nagargoje, Satyajeet and Saraogi, Sidhant},
  title =	{{Range Avoidance for Constant Depth Circuits: Hardness and Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{65:1--65:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.65},
  URN =		{urn:nbn:de:0030-drops-188901},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.65},
  annote =	{Keywords: Boolean function analysis, Explicit Constructions, Low-depth Circuits, Range Avoidance, Matrix Rigidity, Circuit Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.21
Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds

Authors: Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani

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

Abstract
We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted R₁ and R₂. In round R₁, the capacity of each school is fixed and mechanism M₁ finds a student optimal stable matching. In round R₂, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results: the first simply disallows any re-allocations in round R₂, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round R₂ under certain settings.
Cite as

Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani. Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds. 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. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.FSTTCS.2020.21,
  author =	{Gajulapalli, Karthik and Liu, James A. and Mai, Tung and Vazirani, Vijay V.},
  title =	{{Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{21:1--21:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.21},
  URN =		{urn:nbn:de:0030-drops-132626},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.21},
  annote =	{Keywords: stable matching, mechanism design, NP-Hardness}
}
  • Refine by Author
  • 2 Gajulapalli, Karthik
  • 1 Eppstein, David
  • 1 Frishberg, Daniel
  • 1 Golovnev, Alexander
  • 1 Liu, James A.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 Boolean function analysis
  • 1 Circuit Lower Bounds
  • 1 Explicit Constructions
  • 1 Glauber dynamics
  • 1 Low-depth Circuits
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2023
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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