30 citations · 61 across the 15 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
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.CC2019★ 2 cited
Consistency of circuit lower bounds with bounded theories
Jan Bydzovsky, Jan Krajicek, Igor C. Oliveira
Proving that there are problems in that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are…