Matrix rigidity : a survey
| dc.contributor.advisor | Gal, A. (Anna) | |
| dc.creator | Xie, Yangxinyu | |
| dc.creator.orcid | 0000-0002-1532-6746 | |
| dc.date.accessioned | 2022-11-21T20:15:18Z | |
| dc.date.available | 2022-11-21T20:15:18Z | |
| dc.date.created | 2022-05 | |
| dc.date.issued | 2022-05-06 | |
| dc.date.submitted | May 2022 | |
| dc.date.updated | 2022-11-21T20:15:19Z | |
| dc.description.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. | |
| dc.description.department | Computer Science | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | https://hdl.handle.net/2152/116762 | |
| dc.identifier.uri | http://dx.doi.org/10.26153/tsw/43657 | |
| dc.language.iso | en | |
| dc.subject | Matrix rigidity | |
| dc.subject | Computational complexity | |
| dc.subject | Linear algebra | |
| dc.title | Matrix rigidity : a survey | |
| dc.type | Thesis | |
| dc.type.material | text | |
| thesis.degree.department | Computer Sciences | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | The University of Texas at Austin | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science in Computer Sciences |
Access full-text files
Original bundle
1 - 1 of 1