Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits
Sergei Artemenko, Ronen Shaltiel
Article No.: 6
DOI: 10.1145/3018057

A sampling procedure for a distribution P over {0, 1}^ℓ is a function C: {0, 1}ⁿ → {0, 1}^ℓ such that the distribution...

Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs
Arnab Bhattacharyya, Sivakanth Gopi
Article No.: 7
DOI: 10.1145/3016802

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes...

Exact Perfect Matching in Complete Graphs
Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
Article No.: 8
DOI: 10.1145/3041402

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and...

A Complexity Trichotomy for Approximately Counting List H-Colorings
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Article No.: 9
DOI: 10.1145/3037381

We examine the computational complexity of approximately counting the list H-colorings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph...

Min/Max-Poly Weighting Schemes and the NL versus UL Problem
Anant Dhayal, Jayalal Sarma, Saurabh Sawlani
Article No.: 10
DOI: 10.1145/3070902

For a graph G(V, E) (|V| = n) and a vertex s ∈ V, a weighting scheme (W : E ↦ Z⁺) is called a min-unique (resp. max-unique)...