Subset sum and community problems: From social to geometry

Koiliaris, Konstantinos

Permalink

https://hdl.handle.net/2142/105206 Copy

Description

Title

Subset sum and community problems: From social to geometry

Author(s)

Koiliaris, Konstantinos

Issue Date

2019-04-16

Director of Research (if dissertation) or Advisor (if thesis)

Har-Peled, Sariel

Doctoral Committee Chair(s)

Har-Peled, Sariel

Committee Member(s)

• Karahalios, Karrie
• Kolla, Alexandra
• Boutsidis, Christos

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2019-05

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2019 Konstantinos Koiliaris

Owning Collections