1 citations · 1 across the 5 of their papers we have counts for
Showing 2025Show all
2 papers · 1 filter
cs.CC2025
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…
cs.LG2025★ 1 cited
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…