8 citations · 13 across the 14 of their papers we have counts for
21 papers
Non-existence probabilities and lower tails in the critical regime via Belief Propagation
Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of…
Error-Correcting Graph Codes
Swastik Kopparty, Aditya Potukuchi, Harry Sha
In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance is a family of graphs on a common vertex set of size , such that if…
Unbalanced Random Matching Markets with Partial Preferences
Aditya Potukuchi, Shikha Singh
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 dra…
Approximately counting independent sets in dense bipartite graphs via subspace enumeration
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
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…
Blocking sets, minimal codes and trifferent codes
Anurag Bishnoi, Jozefien D'haeseleer, Dion Gijswijt +1
We prove new upper bounds on the smallest size of affine blocking sets, that is, sets of points in a finite affine space that intersect every affine subspace of a fixed codimension…
Algorithms for the ferromagnetic Potts model on expanders
Charlie Carlson, Ewan Davies, Nicolas Fraiman +3
We give algorithms for approximating the partition function of the ferromagnetic -color Potts model on graphs of maximum degree . Our primary contribution is a fully polynomi…