William F. Sawin

Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.

? Tutorial for this page

Demo Data from EDBT 2026 / reviewers in the wild / expert

dblp:56/11267 · DBLP profile ↗

← Back

2ranked-venue papers

0as first author

0since 2021 · last 2016

—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science

2 papers

Graph algorithms and graph theory · 82% Information theory · 18%

Topics — the 6 heaviest of 6, each with the papers that count most for it

Topic	Weight	Papers	Last	Evidence papers
Graph algorithms and graph theory expander graphs	0.2	1	2016	Ramanujan coverings of graphs · STOC 2016
Graph algorithms and graph theory › graph theory graph covering	0.2	1	2016	Ramanujan coverings of graphs · STOC 2016
Graph algorithms and graph theory › expander graphs ramanujan graphs	0.2	1	2016	Ramanujan coverings of graphs · STOC 2016
Graph algorithms and graph theory spectral graph theory	0.2	1	2016	Ramanujan coverings of graphs · STOC 2016
Information theory › signal processing › compressed sensing restricted isometry property	0.2	1	2013	Certifying the Restricted Isometry Property is Hard · IEEE Trans. Inf. Theory 2013
Information theory › signal processing compressed sensing	0.0	1	2013	Certifying the Restricted Isometry Property is Hard · IEEE Trans. Inf. Theory 2013

Methods — techniques the papers use, named apart from their topics

spectral radius bounds · 0.2interlacing families · 0.2reduction · 0.2complexity analysis · 0.2

Year	Publication	Venue	Position
2016	Ramanujan coverings of graphs abstract Let G be a finite connected graph, and let ρ be the spectral radius of its universal cover. For example, if G is k-regular then ρ=2√k−1. We show that for every r, there is an r-covering (a.k.a. an r-lift) of G where all the new eigenvalues are bounded from above by ρ. It follows that a bipartite Ramanujan graph has a Ramanujan r-covering for every r. This generalizes the r=2 case due to Marcus, Spielman and Srivastava (2013). Chris Hall, Doron Puder, William F. Sawin	STOC	3
2013	Certifying the Restricted Isometry Property is Hard abstract This paper is concerned with an important matrix condition in compressed sensing known as the restricted isometry property (RIP). We demonstrate that testing whether a matrix satisfies RIP isNP-hard. As a consequence of our result, it is impossible to efficiently test for RIP providedP≠NP. Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin	IEEE Trans. Inf. Theory	4