Tarun Kathuria

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-292

December 19, 2023

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

Over the last few decades, the design of algorithms for combinatorial problems has benefited greatly from a continous optimization perspective. In this dissertation, we will focus on some specific ideas from continous optimization, particularly so-called interior point methods (IPMs), for the design of efficient algorithms for some combinatorial problems in theoretical computer science. We will present algorithms for three different applications using these ideas:

1) We first present an improved interior point method algorithm for exact $s$-$t$ maximum flow on directed graphs that runs in time $O(m^{4/3+o(1)}U^{1/3})$ where $U$ is the ratio of the maximum to minimum capacities on the edges. 2) We then design a faster interior point method for the class of semi-definite programs (SDPs), a class of convex programs that have led to polynomial time algorithms for a variety of problems in combinatorial optimization, statistics and machine learning. Our algorithm runs in $O(\sqrt{n} (mn^2 + m^\omega + n^\omega)\log(1/\varepsilon))$ time for an SDP with $m$ constraints and $n$ sized variable matrix, which improves over the previous results in a wide variety of regimes. 3) We present a constructive proof of the Spencer problem by designing a Stieltjes transform based barrier function and running a random walk analyzed using this barrier function which gives a signing with discrepancy of $O(\sqrt{n})$ with high probability. We then show that unlike previous such approaches, our approach may generalize to resolve matrix discrepancy problems.

Advisors: Prasad Raghavendra

---

BibTeX citation:

@phdthesis{Kathuria:EECS-2023-292,
    Author= {Kathuria, Tarun},
    Title= {Improved Interior Point Methods for Some Structured Combinatorial Problems},
    School= {EECS Department, University of California, Berkeley},
    Year= {2023},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-292.html},
    Number= {UCB/EECS-2023-292},
    Abstract= {Over the last few decades, the design of algorithms for combinatorial problems has benefited greatly from a continous optimization perspective. In this dissertation, we will focus on some specific ideas from continous optimization, particularly so-called interior point methods (IPMs), for the design of efficient algorithms for some combinatorial problems in theoretical computer science. We will present algorithms for three different applications using these ideas:

1) We first present an improved interior point method algorithm for exact $s$-$t$ maximum flow on directed graphs that runs in time $O(m^{4/3+o(1)}U^{1/3})$ where $U$ is the ratio of the maximum to minimum capacities on the edges.
2) We then design a faster interior point method for the class of semi-definite programs (SDPs), a class of convex programs that have led to polynomial time algorithms for a variety of problems in combinatorial optimization, statistics and machine learning. Our algorithm runs in $O(\sqrt{n} (mn^2 + m^\omega + n^\omega)\log(1/\varepsilon))$ time for an SDP with $m$ constraints and  $n$ sized variable matrix, which improves over the previous results in a wide variety of regimes.
3) We present a constructive proof of the Spencer problem by designing a Stieltjes transform based barrier function and running a random walk analyzed using this barrier function which gives a signing with discrepancy of $O(\sqrt{n})$ with high probability. We then show that unlike previous such approaches, our approach may generalize to resolve matrix discrepancy problems.},
}

EndNote citation:

%0 Thesis
%A Kathuria, Tarun 
%T Improved Interior Point Methods for Some Structured Combinatorial Problems
%I EECS Department, University of California, Berkeley
%D 2023
%8 December 19
%@ UCB/EECS-2023-292
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-292.html
%F Kathuria:EECS-2023-292