23

The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fischer2, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that ...


14

Consider the parity function (or any other function that depends on all/most bits of the input). For the parity function, $T(w) = \Theta(|w|)$. So $$f_n = \Theta(n).$$ On the other hand, $$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$ Note that $K(2^{2^n}) = O(n)$. Thus $$...


12

The algorithm of Paturi, Pudlák, Saks and Zane (PPSZ) for $k\text{-} \mathrm{SAT}$ had been known to have a running time of $O(1.364^n)$ for $3\text{-}\mathrm{SAT}$, with a better bound of $O(1.308^n)$ for formulas guaranteed to have a unique satisfying assignment. Later Hertli gave an improved analysis showing that this improved run-time bound also holds ...


11

I have decided to ask David Wilson himself, soon thereafter got a reply: For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, which consists of two cliques of size $n/3$ connected by a path of length $n/3$. I don’t know what the worst constant is. The [Brightwell-Winkler] paper looks ...


9

Given the interest in this question, I thought it might be helpful to point out more explicitly the reason we should not be at all surprised by the answer and try to give some direction for refinements of the question. This collects and expands on some comments. I apologize if this is "obvious"! Consider the set of strings of Kolmogorov complexity $n$: $$J^...


8

The Logjam Attack mentions that analysis of the general number field sieve (as applied to computing discrete logarithms over $\mathbb{F}_p$) descent step was tightend, see top left of the 3rd page. As this is the only step that can't be pre-computed (if $\mathbb{F}_p$ is fixed), its efficiency was instrumental to their attack. The initial analysis appears ...


6

Recent work of Anupam Gupta, Euiwoong Lee, and Jason Li [1] shows that the Karger-Stein algorithm for the minimum $k$-cut problem has, in fact, asymptotic time complexity $O(n^{k+o(1)})$, improving on the original analysis which gave $O(n^{2k-2})$ (and on previous work by the same authors, which obtained a different algorithm running in time $O(n^{1.98k+O(1)...


6

The work function algorithm for $k$-server was shown to be $(2k-1)$-competitive by Koutsipias and Papadimitrou - the algorithm was known previously and analyzed only in special cases. It is conjectured to be $k$-competitive.


6

The main conferences where automata are among the main topics are ICALP, LICS, STACS, CSL, MFCS, FSTTCS. If you feel your paper is not strong enough for these conferences (which accept about a quarter of the papers that are sent each year), you can send to conferences which are a little less exigeant. The ICALP submission deadline is soon (in a week), ...


5

The set of problems that can be solved by an universal quantum computer in "polynomial time" (with at most 1/3 probability of error) is called BQP. Travelling salesman problem is in complexity class called NP. Furthermore, it is NP-complete: meaning that if the Travelling Salesman Problem can be solved in any model of computation which can also simulate ...


4

The $3$-Hitting Set problem had a few iterations of "better analysis" (see Fernau's papers [1] [2]) The algorithm before these paper had some arbitrary choices (like 'choose an edge'...), but when the choices are specifically-chosen in a certain way, it allows for a more refined analysis, that is where the improvement comes in. And I think his Appendices in ...


4

An easy case seems to be where the language $S$ contains only padded instances. When $S$ is obtained from a language $L$ by padding each instance of size $n$ with $2^n-n$ symbols, $f^K_{n}$ can be in the region of $2^{f_n}$.


4

First, if $k(n)$ and $T(n)$ are non-negative functions satisfying $$T(n)=3T(n-1)-T(n-2)+T(n-k(n))+3^{k(n)}\tag{$*$}$$ for all sufficiently large $n$, it is easy to see that $T(n)$ cannot have a finite limit, and in particular, it cannot be decreasing. But if $T(n_0+1)\ge T(n_0)$, then $T(n+1)>T(n)$ for all $n>n_0$ by induction on $n$. Thus, $T$ is ...


3

You want to read Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review, 1995 and references therein, especially those to papers by Robson. Here is a quote that answers your question: Robson put [in 1974] a fairly tight upper and lower bounds on the worst-case performance of the best possible allocation algorithm. He showed that a ...


3

In a recent paper, we found an mn upper bound (no big O) on the expected number of "cycles popped" by Wilson's algorithm and it is tight up to constants. It doesn't directly answer the question of Wilson's algorithms' running time as the average size of popped cycles does not seem obvious. On the other hand, I don't have enough "reputation" to leave a ...


2

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time you cover an element, update the cost of all sets that cover it. Then there are n total updates, so the total time for the algorithm using a priority queue in ...


2

There is some work on developing an algebraic or grammar-based view of string algorithms, for example Robert Giegerich, Carsten Meyer, Peter Steffen: A discipline of dynamic programming over sequence data. Sci. Comput. Program. 51(3): 215-263 (2004) Robert Giegerich, Hélène Touzet: Modeling Dynamic Programming Problems over Sequences and Trees with Inverse ...


2

Use Taylor series expansion for the function $\prod_{i=1}^{n} (u_i + y)$ around $y=0$ to obtain the error as $\epsilon (\prod_{j=1}^{n} u_j) \sum_{i=1}^{n} u_i^{-1} + O(\epsilon^2)$. Note that Taylor series works for $\epsilon = O(1/poly(n))$, because $\mathbf{u}$ is a unit normed vector and the product $\prod_{j=1}^{n} u_j < 1$.


2

research into GPU algorithms continues and it is well suited to some problems, but some of the initial excitement may be wearing off after lackluster results and difficulty of translating problems into GPU approaches. also in recent times there is some consternation over transfer overhead to/ from the GPU. from anecdotal/ background stories/ conversations ...


2

Just allocating memory without touching it is very cheap. The cost should be negligible in any kind of theoretical algorithm analysis. You pay the serious penalty the first time you touch each page. The CPU will generate page faults and the operating system will have to do the one-time setup for each memory page. This is a non-trivial cost. Large constant ...


Only top voted, non community-wiki answers of a minimum length are eligible