Source author record

Konstantinos Koiliaris

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Machine Learning math.PR

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

A Faster Pseudopolynomial Time Algorithm for Subset Sum

Given a multiset $S$ of $n$ positive integers and a target integer $t$ , the subset sum problem is to decide if there is a subset of $S$ that sums up to $t$ . We present a new divide-and-conquer algorithm that computes all the realizable subset sums up to an integer $u$ in $\widetilde{O}\!\left(\min\{\sqrt{n}u,u^{4/3},σ\}\right)$ , where $σ$ is the sum of all elements in $S$ and $\widetilde{O}$ hides polylogarithmic factors. This result improves upon the standard dynamic programming algorithm that runs in $O(nu)$ time. To the best of our knowledge, the new algorithm is the fastest general algorithm for this problem. We also present a modified algorithm for cyclic groups, which computes all the realizable subset sums within the group in $\widetilde{O}\!\left(\min\{\sqrt{n}m,m^{5/4}\}\right)$ time, where $m$ is the order of the group.

preprint2015arXiv

Multisection in the Stochastic Block Model using Semidefinite Programming

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.