 Award ID(s):
 1718820
 Publication Date:
 NSFPAR ID:
 10185956
 Journal Name:
 Innovations in Theoretical Computer Science Conference
 Sponsoring Org:
 National Science Foundation
More Like this

We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is γstable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most γ ≥ 1. The goal then is to efficiently recover this “pronounced” optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving \tilde{O}(∆/sqrt(log ∆))stable instances on graphs of maximum degree ∆, (k − 1)stable instances on kcolorable graphs and (1 + ε)stable instances on planar graphs (for any fixed ε > 0), using both combinatorial techniques as well as LPs and the SheraliAdams hierarchy. For general graphs, we give an algorithm for (εn)stable instances, for any fixed ε > 0, and lower bounds based on the planted clique conjecture. As a byproduct of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural result showing that themore »

Finding locally optimal solutions for MAXCUT and MAX k CUT are wellknown PLScomplete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worstcase instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the runtime of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP for maxcut in arbitrary graphs is quasipolynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP for maxcut in complete graphs is ( O Φ 5 n 15.1 ), where Φ is an upper bound on the random edgeweight density and Φ is the number of vertices in the input graph. While Angel, Bubeck, Peres, and Wei’s result showed the first polynomial smoothed complexity, they also conjectured that their runtime bound is far from optimal. In this work, we make substantial progress toward improving the runtime bound. We prove that the smoothed complexity of FLIP for maxcut in complete graphs is O (Φ n 7.83 ). Our results are based on a carefully chosen matrix whose rank captures themore »

Abstract Sequence mappability is an important task in genome resequencing. In the (
k ,m )mappability problem, for a given sequenceT of lengthn , the goal is to compute a table whosei th entry is the number of indices such that the length$$j \ne i$$ $j\ne i$m substrings ofT starting at positionsi andj have at mostk mismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of . We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for$$k=1$$ $k=1$ , works in$$k=O(1)$$ $k=O\left(1\right)$ space and, with high probability, in$$O(n)$$ $O\left(n\right)$ time. Our algorithm requires a careful adaptation of the$$O(n \cdot \min \{m^k,\log ^k n\})$$ $O(n\xb7min\{{m}^{k},{log}^{k}n\})$k errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the allpairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop time algorithms to compute$$O(n^2)$$ $O\left({n}^{2}\right)$all (k ,m )mappability tables for a fixedm and all or a fixed$$k\in \{0,\ldots ,m\}$$ $k\in \{0,\dots ,m\}$k and all . Finally, we show that, for$$m\in \{k,\ldots ,n\}$$ $m\in \{k,\dots ,n\}$ , the ($$k,m = \Theta (\log n)$$ $k,m=\Theta (logn)$k ,m )mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper presented at SPIRE 2018. 
Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2n(11/O(k)) time algorithm for kSAT in the worst case. For this reason, it has been hypothesized that the worstcase kSAT problem cannot be solved in 2n(1f(k)/k) time for any unbounded function f. This hypothesis has been called the "SuperStrong ETH", modelled after the ETH and the Strong ETH. It has also been hypothesized that kSAT is hard to solve for randomly chosen instances near the "critical threshold", where the clausetovariable ratio is such that randomly chosen instances are satisfiable with probability 1/2. We give a randomized algorithm which refutes the SuperStrong ETH for the case of random kSAT and planted kSAT for any clausetovariable ratio. For example, given any random kSAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2n(1c*log(k)/k) time with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a wellknown algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1999). The Unique kSAT problem is the special case where there is at most one satisfying assignment. Improving priormore »

Adversarial training (AT) is a widely recognized defense mechanism to gain the robustness of deep neural networks against adversarial attacks. It is built on minmax optimization (MMO), where the minimizer (i.e., defender) seeks a robust model to minimize the worstcase training loss in the presence of adversarial examples crafted by the maximizer (i.e., attacker). However, the conventional MMO method makes AT hard to scale. Thus, FASTAT (Wong et al., 2020) and other recent algorithms attempt to simplify MMO by replacing its maximization step with the single gradient signbased attack generation step. Although easy to implement, FASTAT lacks theoretical guarantees, and its empirical performance is unsatisfactory due to the issue of robust catastrophic overfitting when training with strong adversaries. In this paper, we advance FASTAT from the fresh perspective of bilevel optimization (BLO). We first show that the commonly used FASTAT is equivalent to using a stochastic gradient algorithm to solve a linearized BLO problem involving a sign operation. However, the discrete nature of the sign operation makes it difficult to understand the algorithm performance. Inspired by BLO, we design and analyze a new set of robust training algorithms termed Fast Bilevel AT (FASTBAT), which effectively defends signbased projected gradient descentmore »