Files in this item

FilesDescriptionFormat

application/pdf

application/pdfKOILIARIS-DISSERTATION-2019.pdf (834kB)Restricted Access
(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


This item appears in the following Collection(s)

Item Statistics