## Files in this item

FilesDescriptionFormat

application/pdf

KOILIARIS-DISSERTATION-2019.pdf (834kB)
(no description provided)PDF

## Description

 Title: Subset sum and community problems: From social to geometry Author(s): Koiliaris, Konstantinos Director of Research: Har-Peled, Sariel Doctoral Committee Chair(s): Har-Peled, 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 Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Stochastic Block Model Semidefinite Programming Subset Sum Divide-and-conquer Nearest neighbors Abstract: In this thesis we study three different problems: We consider the problem of identifying underlying community-like 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(i-1)}\}$. 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: 2019-04-16 Type: Text URI: http://hdl.handle.net/2142/105206 Rights Information: Copyright 2019 Konstantinos Koiliaris Date Available in IDEALS: 2019-08-23 Date Deposited: 2019-05
﻿