The problems from CS (CVP and circuit complexity) are very important problems that have been worked on by top researchers for 30-40 years. Some of these researchers include Turing Award winners. A solution to them would be a best-paper award at many top CS conferences.

▲

kcexn 2 days ago | parent [-]

I assume you're talking about No. 5, the arithmetic circuit complexity bound? The existence of a lower bound than state-of-the-art is certainly a significant result and worth publishing.

But the wording of the result makes it sound like we don't know what the lowest possible complexity bound might be. So, prior to this result did we think there couldn't be a lower possible bound? Or did the arithmetic circuit community think there were lower possible bounds but didn't see it as a high value target for experts to tackle (maybe a problem that was instead regularly given to students to study).

	▲	Ar-Curunir 2 hours ago \| parent [-]
		Circuit complexity lower bounds (and lower bounds in general) are notoriously difficult to come across. For example, despite our best efforts, the state of the art lower bounds on time complexity of algorithms for solving 3SAT is O(n). In contrast, our best algorithms for the task run in time roughly O(2^n). That’s an exponential gap. This is despite decades of trying to find lower bounds.