12 citations · 27 across the 28 of their papers we have counts for
8 papers · 1 filter
Extracting Mergers and Projections of Partitions
Swastik Kopparty, Vishvajeet N
We study the problem of extracting randomness from somewhere-random sources, and related combinatorial phenomena: partition analogues of Shearer's lemma on projections. A somewhere…
A Cauchy-Davenport theorem for linear maps
Simao Herdade, John Kim, Swastik Kopparty
We prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets of the finite field , the classical Cauchy-Davenport theorem gives a low…
A local central limit theorem for the number of triangles in a random graph
Justin Gilmer, Swastik Kopparty
In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos-Renyi random graph , where is a fixed constant. Our…
The Homomorphism Domination Exponent
Swastik Kopparty, Benjamin Rossman
We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, defined as the maximum real number c such that |Hom(F,T)| \geq |Hom(G,T)|^c for every graph…
Optimal Testing of Reed-Muller Codes
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck +2
We consider the problem of testing if a given function f : F_2^n -> F_2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. The Gower…
Random Graphs and the Parity Quantifier
Phokion G. Kolaitis, Swastik Kopparty
The classical zero-one law for first-order logic on random graphs says that for any first-order sentence in the theory of graphs, as n approaches infinity, the probability that…