1 citations · 1 across the 1 of their papers we have counts for
5 papers
Approximate Replicability in Learning
Max Hopkins, Russell Impagliazzo, Christopher Ye
Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness…
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 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…
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…