Sidhanth Mohanty

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-201

August 8, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-201.pdf

What makes an algorithmic problem easy or hard? Many general algorithmic techniques arising from decades of research, along with the theory of NP-completeness based on reductions between hard problems, offers a good answer for problems where the input is "worst-case".

However, this theory has very little to say when the input is random, and comprises of independent samples, as is frequently the case for problems in statistics. Statistical problems seemingly go through abrupt phase transitions in complexity, from hard to easy once the number of samples crosses a threshold. Understanding this boundary between "hard" and "easy" for statistical problems is still in nascent stages.

This thesis comprises recent progress in understanding these phase transitions from the lens of semidefinite programming.

Advisors: Prasad Raghavendra

---

BibTeX citation:

@phdthesis{Mohanty:EECS-2023-201,
    Author= {Mohanty, Sidhanth},
    Title= {Phase Transitions in Inference},
    School= {EECS Department, University of California, Berkeley},
    Year= {2023},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-201.html},
    Number= {UCB/EECS-2023-201},
    Abstract= {What makes an algorithmic problem easy or hard?  Many general algorithmic techniques arising from decades of research, along with the theory of NP-completeness based on reductions between hard problems, offers a good answer for problems where the input is "worst-case".

However, this theory has very little to say when the input is random, and comprises of independent samples, as is frequently the case for problems in statistics.  Statistical problems seemingly go through abrupt phase transitions in complexity, from hard to easy once the number of samples crosses a threshold.  Understanding this boundary between "hard" and "easy" for statistical problems is still in nascent stages.

This thesis comprises recent progress in understanding these phase transitions from the lens of semidefinite programming.},
}

EndNote citation:

%0 Thesis
%A Mohanty, Sidhanth 
%T Phase Transitions in Inference
%I EECS Department, University of California, Berkeley
%D 2023
%8 August 8
%@ UCB/EECS-2023-201
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-201.html
%F Mohanty:EECS-2023-201