24 citations · 26 across the 13 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2021
Effective Guessing Has Unlikely Consequences
András Z. Salamon, Michael Wehar
A classic result of Paul, Pippenger, Szemerédi and Trotter states that DTIME(n) is strictly contained in NTIME(n). The natural question then arises: could DTIME(t(n)) be contained…
cs.CC2020★ 1 cited
Superlinear Lower Bounds Based on ETH
András Z. Salamon, Michael Wehar
We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) i…