Matrix rigidity : a survey

Access full-text files

Date

2022-05-06

Authors

Xie, Yangxinyu

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Since Valiant’s establishment of matrix rigidity to analyse circuit complexity, various contributions to the bounds of matrix rigidity of special candidates has bloomed. In this thesis, we cover the following topics: existing explicit and semi-explicit rigidity lower bounds for various families of matrices, Paturi-Pudlák dimensions, rigid sets, connections between data structure lower bounds and rigidity lower bounds and non-rigidity results.

Description

LCSH Subject Headings

Citation