Testing, Proofs and Locality
Event details
| Date | 19.06.2024 |
| Hour | 10:30 › 12:30 |
| Speaker | Guy Wessenberg |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Alessandro Chiesa
Thesis co-advisor: Prof. Michael Kapralov
Co-examiner: Prof. Mika Göös
Abstract
A central theme in theoretical computer science is that of "watching the world through a straw hole." This refers to the challenge of developing optimal algorithms and protocols under constrained conditions where the ability to query the
input is limited. To achieve effective algorithms, one must make certain assumptions about the input and demonstrate that
meaningful conclusions can be drawn from local observations.
This write-up explores different perspectives on this theme through three papers, chosen for their insights into the local-to-global phenomenon and their diverse techniques, which we hope to use in our research. The first paper, [GOS+09], presents an algorithm for testing if a Boolean function's Fourier spectrum is sparse, using analytical techniques on Boolean functions. The second paper, [RVW13], investigates a modification to the property testing model by allowing interaction with a prover, demonstrating the advantage of
interaction. The third paper, [And07], identifies dense subgraphs via local exploration of a graph, and is analyzed using spectral graph techniques. We conclude with a research proposal focused on aspects related to the discussed topics and techniques.
Background papers
1. Gopalan, Parikshit, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. "Testing Fourier dimensionality and sparsity." SIAM Journal on Computing, vol. 40, no. 4, 2011, pp. 1075–1100.
https://link.springer.com/content/pdf/10.1007/978-3-642-02927-1_42.pdf
2. Rothblum, Guy N., Salil P. Vadhan, and Avi Wigderson. "Interactive proofs of proximity: delegating computation in sublinear time." Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC), 2013, pp. 793–802.
https://dl.acm.org/doi/pdf/10.1145/2488608.2488709
3. Andersen, Reid. "A local algorithm for finding dense subgraphs." ACM Transactions on Algorithms, vol. 6, no. 4, 2010, pp. 60:1–60:12.
https://dl.acm.org/doi/pdf/10.1145/1824777.1824780
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Alessandro Chiesa
Thesis co-advisor: Prof. Michael Kapralov
Co-examiner: Prof. Mika Göös
Abstract
A central theme in theoretical computer science is that of "watching the world through a straw hole." This refers to the challenge of developing optimal algorithms and protocols under constrained conditions where the ability to query the
input is limited. To achieve effective algorithms, one must make certain assumptions about the input and demonstrate that
meaningful conclusions can be drawn from local observations.
This write-up explores different perspectives on this theme through three papers, chosen for their insights into the local-to-global phenomenon and their diverse techniques, which we hope to use in our research. The first paper, [GOS+09], presents an algorithm for testing if a Boolean function's Fourier spectrum is sparse, using analytical techniques on Boolean functions. The second paper, [RVW13], investigates a modification to the property testing model by allowing interaction with a prover, demonstrating the advantage of
interaction. The third paper, [And07], identifies dense subgraphs via local exploration of a graph, and is analyzed using spectral graph techniques. We conclude with a research proposal focused on aspects related to the discussed topics and techniques.
Background papers
1. Gopalan, Parikshit, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. "Testing Fourier dimensionality and sparsity." SIAM Journal on Computing, vol. 40, no. 4, 2011, pp. 1075–1100.
https://link.springer.com/content/pdf/10.1007/978-3-642-02927-1_42.pdf
2. Rothblum, Guy N., Salil P. Vadhan, and Avi Wigderson. "Interactive proofs of proximity: delegating computation in sublinear time." Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC), 2013, pp. 793–802.
https://dl.acm.org/doi/pdf/10.1145/2488608.2488709
3. Andersen, Reid. "A local algorithm for finding dense subgraphs." ACM Transactions on Algorithms, vol. 6, no. 4, 2010, pp. 60:1–60:12.
https://dl.acm.org/doi/pdf/10.1145/1824777.1824780
Practical information
- General public
- Free