FOCS 2021 Best Paper Awards

On behalf of the FOCS 2021 PC, I am delighted to announce the Best Paper Awards.

Best paper:

Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas. Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

This paper makes a fundamental advance by proving super-polynomial lower bounds against algebraic circuits of arbitrary constant depth.

Paper: https://eccc.weizmann.ac.il/report/2021/081/

Machtey Award for Best Student Paper:

Xiao Mao. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance

This paper shows how, unlike the weighted case, the unweighted tree edit distance problem has a sub-cubic time algorithm.

Paper: https://arxiv.org/abs/2106.02026

Congratulations to the winners and see you all in Denver from Feb 7-10, 2022!

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