International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong


Invited Speakers

Female Forum

Hardness Results for Weaver’s Discrepancy Problem

Peng Zhang

Rutgers University

Marcus, Spielman and Srivastava (Annals of Mathematics, 2015) solved the Kadison-Singer Problem by proving a strong form of Weaver’s conjecture: They showed that for all > 0 and all lists of vectors of norm at most √α whose outer products sum to the identity, there exists a signed sum of those outer products with operator norm at most √8α + 2α. Besides its relation to the Kadison-Singer problem, Weaver’s discrepancy problem has applications in graph sparsification and randomized experimental design.
We prove that it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals the zero matrix from those in which every signed sum has operator norm at least k√α, for some absolute constant k > 0. Thus, it is NP-hard to construct a signing that is a constant factor better than that guaranteed to exist.
This talk will be based on joint work with Daniel Spielman.

Peng Zhang is an assistant professor in Computer Science at Rutgers University. Before joining Rutgers, she obtained her Ph.D. from Georgia Tech and then was a postdoc at Yale University. Her research lies broadly in the design of efficient algorithms, including solving structured linear equations and linear programs, discrepancy theory and its applications in randomized experimental design.