Thomas Dueholm Hansen

STOC Conference 2019 Conference Paper

Faster k -SAT algorithms using biased-PPSZ

• Thomas Dueholm Hansen
• Haim Kaplan
• Or Zamir
• Uri Zwick

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k -SAT problem, for every k >3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k ≥ 3. For k =3 we also improve on Herli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308 n to 1.307 n .

SODA Conference 2017 Conference Paper

Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs

• Shiri Chechik
• Thomas Dueholm Hansen
• Giuseppe F. Italiano
• Veronika Loitzenbauer
• Nikos Parotsidis

Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp. , 2-vertex-connected) if the removal of any edge (resp. , vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge- and 2- vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with Õ ( mn ) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced O ( n 2 ) time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time O ( m 3/2 ), which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k -connectivity for k > 2. For constant values of k, we extend one of our algorithms to compute the maximal k -edge-connected in time O ( m 3/2 log n ), improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in O ( n 2 log n ) time.

FOCS Conference 2016 Conference Paper

Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time

• Shiri Chechik
• Thomas Dueholm Hansen
• Giuseppe F. Italiano
• Jakub Lacki
• Nikos Parotsidis

We present randomized algorithms with a total update time of Õ(m √n) for the problems of decremental single source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler.

STOC Conference 2016 Conference Paper

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

• Amir Abboud
• Thomas Dueholm Hansen
• Virginia Vassilevska Williams
• R. Ryan Williams

A recent, active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk (STOC’15) proves that computing the Edit Distance of two sequences of length n in truly subquadratic O ( n 2−ε ) time, for some ε>0, is impossible under SETH. The result was extended by follow-up works to simpler looking problems like finding the Longest Common Subsequence (LCS). SETH is a very strong assumption, asserting that even linear size CNF formulas cannot be analyzed for satisfiability with an exponential speedup over exhaustive search. We consider much safer assumptions, e.g. that such a speedup is impossible for SAT on more expressive representations, like subexponential-size NC circuits. Intuitively, this assumption is much more plausible: NC circuits can implement linear algebra and complex cryptographic primitives, while CNFs cannot even approximately compute an XOR of bits. Our main result is a surprising reduction from SAT on Branching Programs to fundamental problems in P like Edit Distance, LCS, and many others. Truly subquadratic algorithms for these problems therefore have far more remarkable consequences than merely faster CNF-SAT algorithms. For example, SAT on arbitrary o ( n )-depth bounded fan-in circuits (and therefore also NC -Circuit-SAT) can be solved in (2−ε) n time. An interesting feature of our work is that we get major consequences even from mildly subquadratic algorithms for Edit Distance or LCS. For example, we show that if an arbitrarily large polylog factor is shaved from n 2 for Edit Distance then NEXP does not have non-uniform NC 1 circuits.

SODA Conference 2016 Conference Paper

Subtree Isomorphism Revisited

• Amir Abboud
• Arturs Backurs
• Thomas Dueholm Hansen
• Virginia Vassilevska Williams
• Or Zamir

STOC Conference 2015 Conference Paper

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

• Thomas Dueholm Hansen
• Uri Zwick

The Random-Facet pivoting rule of Kalai and of Matousek, Sharir and Welzl is an elegant randomized pivoting rule for the simplex algorithm, the classical combinatorial algorithm for solving linear programs (LPs). The expected number of pivoting steps performed by the simplex algorithm when using this rule, on any linear program involving n inequalities in d variables, is 2 O(√{(n-d),log({d}/{√{n-d}}},) , where log n=max{1,log n}. A dual version of the algorithm performs an expected number of at most 2 O(√{d,log({(n-d)}/√d},) dual pivoting steps. This dual version is currently the fastest known combinatorial algorithm for solving general linear programs. Kalai also obtained a primal pivoting rule which performs an expected number of at most 2 O(√d,log n) pivoting steps. We present an improved version of Kalai's pivoting rule for which the expected number of primal pivoting steps is at most min{2 O(√(n-d),log(d/(n-d) ,)},2 O(√{d,log((n-d)/d}},) }. This seemingly modest improvement is interesting for at least two reasons. First, the improved bound for the number of primal pivoting steps is better than the previous bounds for both the primal and dual pivoting steps. There is no longer any need to consider a dual version of the algorithm. Second, in the important case in which n=O(d), i.e., the number of linear inequalities is linear in the number of variables, the expected running time becomes 2 O(√d) rather than 2 O(√d log d) . Our results, which extend previous results of Gartner, apply not only to LP problems, but also to LP-type problems, supplying in particular slightly improved algorithms for solving 2-player turn-based stochastic games and related problems.

SODA Conference 2014 Conference Paper

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles

• Thomas Dueholm Hansen
• Haim Kaplan
• Uri Zwick

Dantzig's pivoting rule is one of the most studied pivoting rules for the simplex algorithm. While the simplex algorithm with Dantzig's rule may require an exponential number of pivoting steps on general linear programs, and even on min cost flow problems, Orlin showed that O ( mn 2 log n ) Dantzig's pivoting steps suffice to solve shortest paths problems, where n and m are the number of vertices and edges, respectively, in the graph. Post and Ye recently showed that the simplex algorithm with Dantzig's rule requires only O ( m 2 n 3 log 2 n ) pivoting steps to solve deterministic MDPs with the same discount factor for each edge, and only O ( m 3 n 5 log 2 n ) pivoting steps to solve deterministic MDPs with possibly a distinct discount factor for each edge. We improve Orlin's bound for shortest paths and Post and Ye's bound for deterministic MDPs with the same discount factor by a factor of n to O ( mn log n ), and O ( m 2 n 2 log 2 n ), respectively. We also improve by a factor of n the bound for deterministic MDPs with varying discounts when all discount factors are sufficiently close to 1. These bounds follow from a new proof technique showing that after a certain number of steps, either many edges are excluded from participating in further policies, or there is a large decrease in the value. We also obtain an Ω( n 2 ) lower bound on the number of Dantzig's pivoting steps required to solve shortest paths problems, even when m = Θ( n ). Finally, we describe a reduction from the problem of finding a minimum cost to time ratio cycle to the problem of finding an optimal policy for a discounted deterministic MDP with varying discount factors that tend to 1. This gives a strongly polynomial time algorithm for the problem that does not use Megiddo's parametric search technique.

SODA Conference 2014 Conference Paper

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes

• Thomas Dueholm Hansen
• Mike Paterson
• Uri Zwick

Upper bounds are given for the complexity of two very natural randomized algorithms for finding the sink of an Acyclic Unique Sink Orientation (AUSO) of the n -cube. For Random-Edge, we obtain an upper bound of about 1. 80 n, improving upon the the previous upper bound of about 2 n / n log n obtained by Gärtner and Kaibel. For R andom -J ump, we obtain an upper bound of about (3/2) n, improving upon the previous upper bound of about 1. 72 n obtained by Mansour and Singh. AUSOs provide an appealing combinatorial abstraction of linear programming and other computational problems such as finding optimal strategies for turn-based Stochastic Games.

SODA Conference 2011 Conference Paper

A subexponential lower bound for the Random Facet algorithm for Parity Games

• Oliver Friedmann
• Thomas Dueholm Hansen
• Uri Zwick

Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. They also form a very natural subclass of Deterministic Mean Payoff Games, which in turn is a very natural subclass of turn-based Stochastic Mean Payoff Games. It is a major open problem whether these game families can be solved in polynomial time. The currently theoretically fastest algorithms for the solution of all these games are adaptations of the randomized algorithms of Kalai and of Matousek, Sharir and Welzl for LP-type problems, an abstract generalization of linear programming. The expected running time of both algorithms is subexponential in the size of the game, i. e. ,, where n is the number of vertices in the game. We focus in this paper on the algorithm of Matousek, Sharir and Welzl and refer to it as the Random Facet algorithm. Matoušek constructed a family of abstract optimization problems such that the expected running time of the Random Facet algorithm, when run on a random instance from this family, is close to the subexponential upper bound given above. This shows that in the abstract setting, the upper bound on the complexity of the Random Facet algorithm is essentially tight. It is not known, however, whether the abstract optimization problems constructed by Matoušek correspond to games of any of the families mentioned above. There was some hope, therefore, that the Random Facet algorithm, when applied to, say, parity games, may run in polynomial time. We show, that this, unfortunately, is not the case by constructing explicit parity games on which the expected running time of the Random Facet algorithm is close to the subexponential upper bound. The games we use mimic the behavior of a randomized counter. They are also the first explicit LP-type problems on which the Random Facet algorithm is not polynomial.

STOC Conference 2011 Conference Paper

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

• Oliver Friedmann
• Thomas Dueholm Hansen
• Uri Zwick

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. With essentially all deterministic pivoting rules it is known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2 Ω(n α ) , for some α>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.