Distribution-Free Testing of Linear Functions on R^n

Noah Fleming, Yuichi Yoshida

To Appear at ITCS 2020. [arXiv]

Semialgebraic Proofs and Efficient Algorithm Design

Noah Fleming, Pravesh Kothari, Toniann Pitassi

Foundations and Trends in Theoretical Computer Science 2019. [ECCC]

Stabbing Planes

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

ITCS 2018. [DROPS]
[Slides]

Random log(n)-CNFs are Hard for Cutting Planes

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

FOCS 2017. [ECCC]
[Slides]

Complexity of alignment and decoding problems: restrictions and approximations

Noah Fleming, Antonina Kolokolova, Renesa Nizamee

Machine Translation 2015. [DOI]