Browsing by Subject "Matrix rigidity"
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
Item Matrix rigidity : a survey(2022-05-06) Xie, Yangxinyu; Gal, A. (Anna)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.