Author name cluster

Shyan Akmal

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

SODA Conference 2022 Conference Paper

Near-Optimal Quantum Algorithms for String Problems

Shyan Akmal
Ce Jin 0001

We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: Longest Common Substring can be solved by a quantum algorithm in Õ ( n 2/3 ) time, improving upon the recent Õ ( n 5/6 )-time algorithm by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, 2019) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n 1/2 + o (1) time, improving upon the recent Õ ( n 3/4 )-time algorithm by Wang and Ying (2020). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. Longest Square Substring can be solved by a quantum algorithm in time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2020) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.

Details

FOCS Conference 2021 Conference Paper

MAJORITY-3SAT (and Related Problems) in Polynomial Time

Shyan Akmal
R. Ryan Williams

Majority-SAT (a. k. a. MAJ-SAT) is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^(n-1) satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k. We prove that for every k, Majority-kSAT is in P; in fact, the problem can be solved in linear time (whereas the previous best-known algorithm ran in exponential time). More generally, for any positive integer k and constant p in (0, 1) with bounded denominator, we give an algorithm that can determine whether a given k-CNF has at least p(2^n) satisfying assignments, in deterministic linear time. We find these results surprising, as many analogous problems which are hard for CNF formulas remain hard when restricted to 3-CNFs. Our algorithms have interesting positive implications for counting complexity and the complexity of inference, significantly reducing the known complexities of related problems such as E-MAJ-kSAT and MAJ-MAJ-kSAT. Our results immediately extend to arbitrary Boolean CSPs with constraints of arity k. At the heart of our approach is an efficient method for solving threshold counting problems by extracting and analyzing various sunflowers found in the corresponding set system of a k-CNF. Exploring the implications of our results, we find that the tractability of Majority-kSAT is somewhat fragile, in intriguing ways. For the closely related GtMajority-SAT problem (where we ask whether a given formula has greater than 2^(n-1) satisfying assignments) which is also known to be PP-complete, we show that GtMajority-kSAT is in P for k at most 3, but becomes NP-complete for k at least 4. We also show that for Majority-SAT on k-CNFs with one additional clause of arbitrary width, the problem is PP-complete for k at least 4, is NP-hard for k=3, and remains in P for k=2. These results are counterintuitive, because the “natural” classifications of these problems would have been PP-completeness, and because there is a stark difference in the complexity of GtMajority-kSAT and Majority-kSAT for all k at least 4.

Details

AIJ Journal 2020 Journal Article

Quantifying controllability in temporal networks with uncertainty

Shyan Akmal
Savana Ammons
Hemeng Li
Michael Gao
Lindsay Popowski
James C. Boerkoel

Controllability for Simple Temporal Networks with Uncertainty (STNUs) has thus far been limited to three levels: strong, dynamic, and weak. Because of this, there is currently no systematic way for an agent to assess just how far from being controllable an uncontrollable STNU is. We provide new insights inspired by a geometric interpretation of STNUs to introduce the degrees of strong and dynamic controllability — continuous metrics that measure how far a network is from being controllable. We utilize these metrics to approximate the probabilities that an STNU can be dispatched successfully offline and online respectively. We introduce new methods for predicting the degrees of strong and dynamic controllability for uncontrollable networks. We further generalize these metrics by defining likelihood of controllability, a controllability measure that applies to Probabilistic Simple Temporal Networks (PSTNs). Finally, we empirically demonstrate that these metrics are good predictors of actual dispatch success rate for STNUs and PSTNs.

Details DOI

ICAPS Conference 2019 Conference Paper

Quantifying Degrees of Controllability in Temporal Networks with Uncertainty

Shyan Akmal
Savana Ammons
Hemeng Li
James C. Boerkoel Jr.

Controllability for Simple Temporal Networks with Uncertainty (STNUs) has thus far been limited to three levels: strong, dynamic, and weak. Because of this, there is currently no systematic way for an agent to assess just how far from being controllable an uncontrollable STNU is. We use a new geometric interpretation of STNUs to introduce the degrees of strong and dynamic controllability – continuous metrics that measure how far a network is from being controllable. We utilize these metrics to approximate the probabilities that an STNU can be dispatched successfully offline and online respectively. We introduce new methods for predicting the degrees of strong and dynamic controllability for uncontrollable networks. In addition, we show empirically that both metrics are good predictors of the actual dispatch success rate.

Details