Search Results

Documents authored by Potukuchi, Aditya

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.125
Unbalanced Random Matching Markets with Partial Preferences

Authors: Aditya Potukuchi and Shikha Singh

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

Abstract
Properties of stable matchings in the popular random-matching-market model have been studied for over 50 years. In a random matching market, each agent has complete preferences drawn uniformly and independently at random. Wilson (1972), Knuth (1976) and Pittel (1989) proved that in balanced random matching markets, the proposers are matched to their ln nth choice on average. In this paper, we consider competitive markets with n jobs and n+k candidates, and partial lists where each agent only ranks their top d choices. Despite the long history of the problem, the following fundamental question remains unanswered for these generalized markets: what is the tight threshold on list length d that results in a perfect stable matching with high probability? In this paper, we answer this question exactly - we prove a sharp threshold d₀ = ln n ⋅ ln (n+k)/(k+1) on the existence of perfect stable matchings when k = o(n). That is, we show that if d < (1-ε) d₀, then no stable matching matches all jobs; moreover, if d > (1+ ε) d₀, then all jobs are matched in every stable matching with high probability. This bound improves and generalizes recent results by Kanoria, Min and Qian (2021). Furthermore, we extend the line of work studying the effect of imbalance on the expected rank of the proposers (termed the "stark effect of competition"). We establish the regime in unbalanced markets that forces this stark effect to take shape in markets with partial preferences.
Cite as

Aditya Potukuchi and Shikha Singh. Unbalanced Random Matching Markets with Partial Preferences. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 125:1-125:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{potukuchi_et_al:LIPIcs.ICALP.2025.125,
  author =	{Potukuchi, Aditya and Singh, Shikha},
  title =	{{Unbalanced Random Matching Markets with Partial Preferences}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{125:1--125: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.125},
  URN =		{urn:nbn:de:0030-drops-235025},
  doi =		{10.4230/LIPIcs.ICALP.2025.125},
  annote =	{Keywords: stable matching, probabilistic method, Gale-Shapley algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.67
Error-Correcting Graph Codes

Authors: Swastik Kopparty, Aditya Potukuchi, and Harry Sha

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance δ is a family C of graphs, on a common vertex set of size n, such that if we start with any graph in C, we would have to modify the neighborhoods of at least δ n vertices in order to obtain some other graph in C. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric. We extend their work by showing 1) Combinatorial results determining the optimal rate vs distance trade-off nonconstructively. 2) Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances. 3) Graph code analogues of dual-BCH codes, yielding large codes with distance δ = 1-o(1). This gives an explicit "graph code of Ramsey graphs". Several recent works, starting with the paper of Alon, Gujgiczer, Körner, Milojević, and Simonyi, have studied more general graph codes; where the symmetric difference between any two graphs in the code is required to have some desired property. Error-correcting graph codes are a particularly interesting instantiation of this concept.
Cite as

Swastik Kopparty, Aditya Potukuchi, and Harry Sha. Error-Correcting Graph Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 67:1-67:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kopparty_et_al:LIPIcs.ITCS.2025.67,
  author =	{Kopparty, Swastik and Potukuchi, Aditya and Sha, Harry},
  title =	{{Error-Correcting Graph Codes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{67:1--67:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.67},
  URN =		{urn:nbn:de:0030-drops-226950},
  doi =		{10.4230/LIPIcs.ITCS.2025.67},
  annote =	{Keywords: Graph codes, explicit construction, concatenation codes, tensor codes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.35
A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs

Authors: Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph - in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to "high-temperature" problems on bounded-degree graphs, and our contribution is a notable exception as it applies to dense graphs in a low-temperature setting. Our methods give a counting-focused complement to the long line of work in combinatorial optimization showing that CSPs such as Max-Cut and Unique Games are easy on dense graphs via spectral arguments. Our contributions include a novel extension of the method of graph containers that differs considerably from other recent low-temperature algorithms. The additional key insights come from spectral graph theory and have previously been successful in approximation algorithms. As a result, we can overcome some limitations that seem inherent to the aforementioned class of algorithms. In particular, we exploit the fact that dense, regular graphs exhibit a kind of small-set expansion (i.e., bounded threshold rank), which, via subspace enumeration, lets us enumerate small cuts efficiently.
Cite as

Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{carlson_et_al:LIPIcs.ICALP.2024.35,
  author =	{Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Potukuchi, Aditya},
  title =	{{A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.35},
  URN =		{urn:nbn:de:0030-drops-201782},
  doi =		{10.4230/LIPIcs.ICALP.2024.35},
  annote =	{Keywords: approximate counting, independent sets, bipartite graphs, graph containers}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.30
On the List Recoverability of Randomly Punctured Codes

Authors: Ben Lund and Aditya Potukuchi

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

Abstract
We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this property. As an immediate corollary to our main theorem, we obtain better degree bounds on unbalanced expanders that come from Reed-Solomon codes.
Cite as

Ben Lund and Aditya Potukuchi. On the List Recoverability of Randomly Punctured Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lund_et_al:LIPIcs.APPROX/RANDOM.2020.30,
  author =	{Lund, Ben and Potukuchi, Aditya},
  title =	{{On the List Recoverability of Randomly Punctured Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{30:1--30:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.30},
  URN =		{urn:nbn:de:0030-drops-126330},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.30},
  annote =	{Keywords: List recovery, randomly punctured codes, Reed-Solomon codes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.93
A Spectral Bound on Hypergraph Discrepancy

Authors: Aditya Potukuchi

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Let ℋ be a t-regular hypergraph on n vertices and m edges. Let M be the m × n incidence matrix of ℋ and let us denote λ = max_{v ∈ 𝟏^⟂} 1/‖v‖ ‖Mv‖. We show that the discrepancy of ℋ is O(√t + λ). As a corollary, this gives us that for every t, the discrepancy of a random t-regular hypergraph with n vertices and m ≥ n edges is almost surely O(√t) as n grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
Cite as

Aditya Potukuchi. A Spectral Bound on Hypergraph Discrepancy. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 93:1-93:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{potukuchi:LIPIcs.ICALP.2020.93,
  author =	{Potukuchi, Aditya},
  title =	{{A Spectral Bound on Hypergraph Discrepancy}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{93:1--93:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.93},
  URN =		{urn:nbn:de:0030-drops-125002},
  doi =		{10.4230/LIPIcs.ICALP.2020.93},
  annote =	{Keywords: Hypergraph discrepancy, Spectral methods, Beck-Fiala conjecture}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.25
On the AC^0[oplus] Complexity of Andreev’s Problem

Authors: Aditya Potukuchi

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
Andreev’s Problem is the following: Given an integer d and a subset of S subset F_q x F_q, is there a polynomial y = p(x) of degree at most d such that for every a in F_q, (a,p(a)) in S? We show an AC^0[oplus] lower bound for this problem. This problem appears to be similar to the list recovery problem for degree-d Reed-Solomon codes over F_q which states the following: Given subsets A_1,...,A_q of F_q, output all (if any) the Reed-Solomon codewords contained in A_1 x *s x A_q. In particular, we study this problem when the lists A_1, ..., A_q are randomly chosen, and are of a certain size. This may be of independent interest.
Cite as

Aditya Potukuchi. On the AC^0[oplus] Complexity of Andreev’s Problem. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{potukuchi:LIPIcs.FSTTCS.2019.25,
  author =	{Potukuchi, Aditya},
  title =	{{On the AC^0\lbrackoplus\rbrack Complexity of Andreev’s Problem}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.25},
  URN =		{urn:nbn:de:0030-drops-115879},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.25},
  annote =	{Keywords: List Recovery, Sharp Threshold, Fourier Analysis}
}
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