Aryabhata
  • Member for 11 years, 5 months
  • Last seen more than 2 years ago
Major unsolved problems in theoretical computer science?
39 votes

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 ...

View answer
Comparison-based data structure for finding items
24 votes

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
Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?
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
Can words in regular languages be generated by automata in a unique way?
Accepted answer
14 votes

Maybe I misunderstood your question, but wouldn't a Deterministic Finite Automaton do what you want?

View answer
Reducing complexity with parallelism
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
Is the problem of finding the chromatic number of a modified interval graph NP-Complete
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
Everyday encounters with NP-complete problems
7 votes

Crossword puzzle construction is NP-Complete: Given a set of answers, try to fit them into a grid.

View answer
Linear time in-place riffle shuffle algorithm
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
Finding small sets of integers in which every element is a sum of two others
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
Choosing subsets of a set such that the subsets satisfy a global constraint
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, ...

View answer
Graph families which have polynomial time algorithms for computing the chromatic number
4 votes

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 ...

View answer
Are there any applications of techniques in real analysis to theoretical computer science?
2 votes

If I recollect correctly Noga Alon's theorem on splitting necklaces uses the continuous version of the problem. See: http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf There is also a mention of that in ...

View answer
Approaching Number Theory conjectures through Graph Theory
1 votes

Riemann Hypothesis is equivalent to a statement about Merten's function, which is in turn gotten by a determinant of a matrix given by RedHeffer. If I recollect correctly, Graph Theory has been used ...

View answer