Some algorithms and hardness results for the planted clique problem
Abstract/Contents
- Abstract
- One fascinating aspect of trying to solve modern high-dimensional statistical tasks is the rich interplay between the twin requirements of computational as well as statistical tractability. The planted clique problem is a prototypical task that exhibits this interplay. As such, it has become a testbed for theoretical computer scientists interested in developing tools to understand and predict the computational intractability of statistically feasible problems. In this thesis, we discuss some algorithmic and hardness results for the planted clique problem, particularly using the lens of sublinear-time algorithms, query complexity, and memory complexity.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Mardia, Jay Sushil |
|---|---|
| Degree supervisor | Weissman, Tsachy |
| Thesis advisor | Weissman, Tsachy |
| Thesis advisor | Valiant, Gregory |
| Thesis advisor | Wootters, Mary |
| Degree committee member | Valiant, Gregory |
| Degree committee member | Wootters, Mary |
| Associated with | Stanford University, School of Engineering |
| Associated with | Stanford University, Department of Electrical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Jay Mardia. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/df272wv9313 |
Access conditions
- Copyright
- © 2023 by Jay Sushil Mardia
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...