1 citations · 1 across the 5 of their papers we have counts for
4 papers · 1 filter
High Rate Efficient Local List Decoding from HDX
Yotam Dikstein, Max Hopkins, Russell Impagliazzo +1
We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a co…
Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
Farzan Byramji, Russell Impagliazzo
We prove lower bounds for proofs of the bit pigeonhole principle (BPHP) and its generalizations in bounded-depth resolution over parities (Res). For weak BPHP with…
The Greedy Coin Change Problem
Shreya Gupta, Boyang Huang, Russell Impagliazzo
The Coin Change problem, also known as the Change-Making problem, is a well-studied combinatorial optimization problem, which involves minimizing the number of coins needed to make…
The Computational Complexity of Factored Graphs
Shreya Gupta, Boyang Huang, Russell Impagliazzo +2
While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might h…