Purdue University Graduate School
Browse

Complexity Bounds for Search Problems

Download (1.73 MB)
thesis
posted on 2024-04-18, 12:21 authored by Nicholas Joseph ReckerNicholas Joseph Recker

We analyze the query complexity of multiple search problems.

Firstly, we provide lower bounds on the complexity of "Local Search". In local search we are given a graph G and oracle access to a function f mapping the vertices to numbers, and seek a local minimum of f; i.e. a vertex v such that f(v) <= f(u) for all neighbors u of v. We provide separate lower bounds in terms of several graph parameters, including congestion, expansion, separation number, mixing time of a random walk, and spectral gap. To aid in showing these bounds, we design and use an improved relational adversary method for classical algorithms, building on the prior work of Scott Aaronson. We also obtain some quantum bounds using the traditional strong weighted adversary method.

Secondly, we show a multiplicative duality gap for Yao's minimax lemma by studying unordered search. We then go on to give tighter than asymptotic bounds for unordered and ordered search in rounds. Inspired by a connection through sorting with rank queries, we also provide tight asymptotic bounds for proportional cake cutting in rounds.

Funding

CAREER: Dynamics of Searching for Equilibria

Directorate for Computer & Information Science & Engineering

Find out more...

History

Degree Type

  • Doctor of Philosophy

Department

  • Computer Science

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Simina Branzei

Additional Committee Member 2

Alex Pothen

Additional Committee Member 3

Mikhail Atallah

Additional Committee Member 4

Kristoffer Hansen

Usage metrics

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC