3 papers
cs.CC2025
KRW Composition Theorems via Lifting
Susanna F. de Rezende, Or Meir, Jakob Nordström +2
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ). Karchmer, Raz…
cs.CC2025
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
Or Meir
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ). Karchmer, R…
cs.CC2024
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for
Yuval Filmus, Or Meir, Avishay Tal
HÃ¥stad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of under a random restrictio…