Subset sum and community problems: From social to geometry

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{α \log(m)}{m} and q = \frac{β \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{α} - \sqrt{β} > \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=θ(\log(n)). In this case however we achieve recovery guarantees that no longer match the optimal condition \sqrt{α} - \sqrt{β} > \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,σ\}), where σ 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 π of $P$, consider the coloring algorithm that assigns the $i$th point, according to π, the color of the closest point to it in \{p_π(1), \ldots, p_π(i-1)\}. If this color assigned to p_π(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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2019

Author dc:creator

• Koiliaris, Konstantinos

Contributors dc:contributor

• Har-Peled, Sariel
• Karahalios, Karrie
• Kolla, Alexandra
• Boutsidis, Christos

• Stochastic Block Model
• Semidefinite Programming
• Subset Sum
• Divide-and-conquer
• Nearest neighbors

Statement dc:rights

• Copyright 2019 Konstantinos Koiliaris

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/105206

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/105206