Are there truly subquadratic-time algorithms (meaning $O(n^{2-\delta})$ time for some constant $\delta>0$) for 3SUM-hard Problems? In 2014, Grønlund and Pettie described a deterministic algorithm ...

I believe here is a different proof, proving the impossibility of an $\mathcal{O}(\log ^k n)$ query time structure, with $\mathcal{O}(n)$ pre-processing. Suppose in the preprocessing you do $\mathcal{... View answer Accepted answer 16 votes It is known that for every pair of naturals numbers n,a such that n <= a <= 2^n, there exists a minimal NDFA with n states whose corresponding equivalent minimal dfa has a states (over a four ... View answer Accepted answer 14 votes Maybe I misunderstood your question, but wouldn't a Deterministic Finite Automaton do what you want? View answer Accepted answer 12 votes If you mean O(1) processors, then no, computation complexity cannot be reduced. Simply line up the work done by each processor and do it on a single one. If you are worried about synchronization, ... View answer 7 votes According this here: http://www.cs.bme.hu/~dmarx/papers/marx-chordal-iwpec-slides.pdf (see slides 14 and 15) For fixed$k$, for the class of graphs formed by adding$k$edges to interval graphs, the ... View answer 7 votes Crossword puzzle construction is NP-Complete: Given a set of answers, try to fit them into a grid. View answer 6 votes This was a seeding question at cs.stackexchange.com and an answer is here: https://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400 It is an explanation of the ... View answer 6 votes I suppose a linear time algorithm should be possible for Question #1) (and if you are willing to deal with a different representation, an O(1) time algorithm) Given any N >= 23, we construct a ... View answer Accepted answer 5 votes From my answer at math.stackexchange: https://math.stackexchange.com/questions/3205/choosing-subsets-of-a-set-such-that-the-subsets-satisfy-a-global-constraint/3207#3207 Assuming$m\$ is an input, ...

Algorithms for coloring quadtrees. M. Bern, D. Eppstein, and B. Hutchings. http://arXiv:cs.CG/9907030. Algorithmica 32(1):87-94, 2002. We consider several variations of the problem of coloring ...