Files in this item
Files  Description  Format 

application/pdf KOILIARISDISSERTATION2019.pdf (834kB)  (no description provided) 
Description
Title:  Subset sum and community problems: From social to geometry 
Author(s):  Koiliaris, Konstantinos 
Director of Research:  HarPeled, Sariel 
Doctoral Committee Chair(s):  HarPeled, Sariel 
Doctoral Committee Member(s):  Karahalios, Karrie; Kolla, Alexandra; Boutsidis, Christos 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Stochastic Block Model
Semidefinite Programming Subset Sum Divideandconquer Nearest neighbors 
Abstract:  In this thesis we study three different problems: We consider the problem of identifying underlying communitylike structures in graphs. Towards this end we study the Stochastic Block Model (SBM) on $k$clusters: a random model on $n=km$ vertices, partitioned in $k$ equal sized clusters, with edges sampled independently across clusters with probability $q$ and within clusters with probability $p$, $p>q$. The goal is to recover the initial ``hidden'' partition of $[n]$. We study semidefinite programming (SDP) based algorithms in this context. In the regime $p = \frac{\alpha \log(m)}{m}$ and $q = \frac{\beta \log(m)}{m}$ we show that a certain natural SDP based algorithm solves the problem of {\em exact recovery} in the $k$community SBM, with high probability, whenever $\sqrt{\alpha}  \sqrt{\beta} > \sqrt{1}$, as long as $k=o(\log n)$. This threshold is known to be the information theoretically optimal. We also study the case when $k=\theta(\log(n))$. In this case however we achieve recovery guarantees that no longer match the optimal condition $\sqrt{\alpha}  \sqrt{\beta} > \sqrt{1}$, thus leaving achieving optimality for this range an open question. Given a (multi) set $S$ of $n$ positive integers and a target integer $u$, the subset sum problem is to decide if there is a subset of $S$ that sums up to $u$. We present a series of new algorithms that compute and return \emph{all} the realizable subset sums up to the integer $u$ in $\tilde{O}(\min\{\sqrt{n}u,u^{5/4},\sigma\})$, where $\sigma$ is the sum of all elements of $S$ and $\tilde{O}$ hides polylogarithmic factors. We also present a modified algorithm for integers modulo $m$, which computes all the realizable subset sums modulo $m$ in $\tilde{O}(\min \{\sqrt{n}m,m^{5/4}\})$ time. Our contributions improve upon the standard dynamic programming algorithm that runs in $O(nu)$ time. To the best of our knowledge, the new algorithms are the fastest deterministic algorithms for this problem. The new results can be employed in various algorithmic problems, from graph bipartition to computational social choice. Finally, we also improve a result on covering $\Z_m$, which might be of independent interest. Consider the following problem: Let $P$ be a set of points in the plane that are colored by, say, red and blue. For a permutation $\pi$ of $P$, consider the coloring algorithm that assigns the $i$th point, according to $\pi$, the color of the closest point to it in $\{p_{\pi(1)}, \ldots, p_{\pi(i1)}\}$. If this color assigned to $p_{\pi(i)}$ is incorrect, we are forced to \emph{seed} it (i.e., color it explicitly) with its correct color. Here, we are interested in finding a permutation that minimizes the number of points that need to be seeded. We call this the \emph{disparity} problem. Here, we study this problem and related variants, including incremental versions, and versions where the all points are colored according to the color of their nearest seed. 
Issue Date:  20190416 
Type:  Text 
URI:  http://hdl.handle.net/2142/105206 
Rights Information:  Copyright 2019 Konstantinos Koiliaris 
Date Available in IDEALS:  20190823 
Date Deposited:  201905 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois