Questions on the future of lower bounds

Will any of the yellow books be useful?

https://media.springernature.com/w153/springer-static/cover/book/9783030276447.jpg

Book 576 (not pictured) was saved just in time from the paper mill. It was rumored that Lemma 76.7.(ii) could have applications to lower bounds. Upon closer inspection, that lemma has a one-line proof by linearity of expectation if you change the constant 17 to 19. This change does not affect the big-Oh.

Will the study of randomness lead to the answer to any of the questions that are open since before randomness became popular? I think it’s a coin-toss.

Will there be any substance to the belief that algebraic lower bounds must be proved first?

Will the people who were mocked for working on DLOGTIME uniformity, top fan-in k circuits, or ZFC independence have the last laugh?

Will someone switch the circuit breaker and lit up CRYPT, DERAND, and PCPOT, or will they remain unplugged amusement parks where you sit in the roller coaster, buckle up, and pretend?

Will diagonalization be forgotten, or will it continue to frustrate combinatorialists with lower bounds they can’t match for functions they don’t care about?

Will decisive progress be made tonight, or will it take centuries?

Only Ketan Mulmuley knows for sure.

3 thoughts on “Questions on the future of lower bounds

  1. Perhaps someone will prove that NP=EXP, and then P not NP follows from time hierarchy. This could be the future of lower bounds research. Only Ryan Williams knows for sure.

  2. 1) Only when the problem is resolved will we know what the right train of thought was.
    2) I predict that P NE NP will be solved in the year 2525 but we still won’t know the status of GI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s