4 citations · 4 across the 1 of their papers we have counts for
2 papers
cs.CC2019★ 4 cited
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira +3
Hardness magnification reduces major complexity separations (such as ) to proving lower bounds for some natural problem against…
cs.DS2015
On learning k-parities with and without noise
Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal
We first consider the problem of learning -parities in the on-line mistake-bound model: given a hidden vector with and a sequence of "questions" $a_1,…