For any T ≥ 1, there are constants R=R(T) ≥ 1 and ζ=ζ(T)>0 and a randomized algorithm that takes as input an integer n and two strings x,y of length at most n, and runs in time O(n 1+1/T ) and ...outputs an upper bound U on the edit distance of edit(x,y) that with high probability, satisfies U ≤ R(edit(x,y)+n 1−ζ). In particular, on any input with edit(x,y) ≥ n 1−ζ the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).
Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on dynamic undirected graphs with fixed underlying vertex set, i.e., ...graphs which are modified by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the cover time, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on connected static undirected graphs the cover time is polynomial in the size of the graph. On the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of a simple random walk on connected dynamic graphs to be exponential. We relate this result to the cover time of static directed graphs. In addition we provide a simple strategy, the lazy random walk, that guarantees polynomial cover time regardless of the changes made by the adversary.
In this paper we provide a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness). ...If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ. Our decomposition can be used to design a sketch of size O(k2) for edit distance, and also a rolling sketch for edit distance of size O(k2). The rolling sketch allows to update the sketched string by appending a symbol or removing a symbol from the beginning of the string.
Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit ...distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log
n
).
In this article, we provide an algorithm with running time Õ(
n
2−2/7
) that approximates the edit distance within a constant factor.
Almost Linear Size Edit Distance Sketch Koucký, Michal; Saks, Michael E.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing,
06/2024
Conference Proceeding
Recenzirano
Odprti dostop
We design an almost linear-size sketching scheme for computing edit distance up to a given threshold k. The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The ...sketching algorithm depends on the parameter k and takes as input a string x and a public random string ρ and computes a sketch skρ(x;k), which is a compressed version of x. The recovery algorithm is given two sketches skρ(x;k) and skρ(y;k) as well as the public random string ρ used to create the two sketches, and (with high probability) if the edit distance ED(x,y) between x and y is at most k, will output ED(x,y) together with an optimal sequence of edit operations that transforms x to y, and if ED(x,y) > k will output large. The size of the sketch output by the sketching algorithm on input x is k2O(√log(n)loglog(n)) (where n is an upper bound on length of x). The sketching and recovery algorithms both run in time polynomial in n. The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS’2021), and Bhattacharya and Koucký (STOC’2023).
Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit ...distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this paper, we provide an algorithm with running time Õ(n^2-2/7) that approximates the edit distance within a constant factor.
We observe that many important computational problems in NC
1
share a simple self-reducibility property. We then show that, for any problem
A
having this self-reducibility property,
A
has ...polynomial-size TC
0
circuits if and only if it has TC
0
circuits of size
n
1+ϵ
for every ϵ> 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC
1
and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth
d
TC
0
circuits of size
n
1+ϵ
d
. If one were able to improve this lower bound to show that there is some constant ϵ> 0 (independent of the depth
d
) such that every TC
0
circuit family recognizing BFE has size at least
n
1+ϵ
, then it would follow that TC
0
≠ NC
1
. We show that proving lower bounds of the form
n
1+ϵ
is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC
0
, TC
0
and NC
1
via existing “natural” approaches to proving circuit lower bounds.
We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth
d
TC
0
and AC
0
6 circuits of size
n
1+
c
for some constant
c
depending on
d
.
We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403–435,
1999
), to any gadget which satisfies a certain hitting property. We prove that inner product and ...gap-Hamming satisfy this property, and as a corollary, we obtain a deterministic simulation theorem for these gadgets, where the gadget’s input size is logarithmic in the input size of the outer function. This yields the first deterministic simulation theorem with a logarithmic gadget size, answering an open question posed by Göös, Pitassi & Watson (in: Proceedings of the 56th FOCS,
2015
).
Our result also implies the previous results for the indexing gadget, with better parameters than was previously known. Moreover, a simulation theorem with logarithmic-sized gadget implies a quadratic separation in the deterministic communication complexity and the logarithm of the 1-partition number, no matter how high the 1-partition number is with respect to the input size—something which is not achievable by previous results of Göös, Pitassi & Watson (
2015
).
We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any
$r$-uniform hypergraph with $m$ edges and maximum vertex degree $o(\sqrt{m})$
contains a set of at most $(\frac{1}{2} - ...\epsilon_r)m$ edges the removal of
which breaks the hypergraph into connected components with at most $m/2$ edges.
We use this to give an algorithm running in time $d^{(1 - \epsilon_r)m}$ that
decides satisfiability of $m$-variable $(d, k)$-CSPs in which every variable
appears in at most $r$ constraints, where $\epsilon_r$ depends only on $r$ and
$k\in o(\sqrt{m})$. Furthermore our algorithm solves the corresponding #CSP-SAT
and Max-CSP-SAT of these CSPs. We also show that CNF representations of
unsatisfiable $(2, k)$-CSPs with variable frequency $r$ can be refuted in
tree-like resolution in size $2^{(1 - \epsilon_r)m}$. Furthermore for Tseitin
formulas on graphs with degree at most $k$ (which are $(2, k)$-CSPs) we give a
deterministic algorithm finding such a refutation.
PDF
