Most Popular
1500 questions
20
votes
3 answers
If an abstract machine can simulate itself, does that make it Turing complete?
For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e.g. simulating Conway's Game of Life in Conway's…
Jeremy Kun
- 1,318
- 7
- 16
20
votes
2 answers
Data structure for shortest paths
Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer queries of the form "distance between $u$ and $v$"…
ilyaraz
- 1,569
- 18
- 33
20
votes
2 answers
$\ell_p$-norm preserving Turing machines
Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine.
For people working in complexity theory going to quantum complexity a…
Marcos Villagra
- 3,290
- 27
- 45
20
votes
2 answers
n-dimensional pattern matching
What are some known results for finding an exact n-dimensional subarray inside a n-dimensional array?
In 1D, it is just a string matching problem, KMP does it in linear time.
In 2D, this paper shown it can be done in linear time with little extra…
Chao Xu
- 4,399
- 23
- 32
20
votes
5 answers
Reducing space usage of st-connectivity with multiple passes?
Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan observed that $\Omega(n/k)$ space is necessary to…
András Salamon
- 19,000
- 3
- 64
- 150
20
votes
1 answer
Merging lists of fragile objects
Background: Chao Xu posted the following question some time ago: "Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?". It seems that we are a bit stuck with…
Jukka Suomela
- 11,500
- 2
- 53
- 116
20
votes
4 answers
Computational complexity in quantitative finance
Predicting the stock market is hard! Can TCS make this sentiment more formal?
Recently I have started thinking a little bit about finance, and was wondering how knowledge of TCS could help. Hedge funds and investment firms seems to use algorithmic…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
20
votes
1 answer
What is the number of languages accepted by a DFA of size $n$?
The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this:
Define a DFA as $(Q,\Sigma,\delta,q_0,F)$, where everything is as usual and…
Janoma
- 1,406
- 11
- 27
20
votes
0 answers
Complexity of finding the smallest well-covered completion
This is related to an earlier question on which graphs have the property that all maximal independent sets are maximum — such graphs turn out to be known as the well-covered graphs. Any graph $G$ is an induced subgraph of a well-covered graph: for…
David Eppstein
- 50,990
- 3
- 170
- 278
20
votes
1 answer
Is there a better than linear lower bound for factoring and discrete log?
Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and its variant over group of points of elliptic curves…
v s
- 2,208
- 13
- 21
20
votes
6 answers
Parallel pseudorandom number generators
This question is primarily related to a practical software-engineering problem, but I would be curious to hear if theoreticians could provide more insight in it.
Put simply, I have a Monte Carlo simulation that uses a pseudorandom number generator,…
Jukka Suomela
- 11,500
- 2
- 53
- 116
20
votes
1 answer
Does cryptography have an inherent thermodynamic cost?
Reversible computing is a computational model that only allows
thermodynamically reversible operations. According to Landauer's
principle, which states that erasing a bit of information releases $kT
\ln(2)$ joules of heat, this rules out…
rphv
- 583
- 3
- 11
20
votes
11 answers
Models of random graphs, for real computer networks
I am interested in models of random graphs which are similar to the graphs of real computer networks. I am not sure if the common well-studied $G(n,p)$ model ($n$ vertices, each possible edge is selected with probability $p$) is good for studying…
Kaveh
- 21,577
- 8
- 82
- 183
20
votes
3 answers
How do models of hypercomputation overcome the Halting Problem?
Hypercomputation refers to models of computation that are not possible to simulate using Turing machines. (Hypercomputers are not necessarily physically realisable!) Some hypercomputers have access to a resource that allows the Halting Problem for…
András Salamon
- 19,000
- 3
- 64
- 150
20
votes
2 answers
Why isn't TheoretiCS very popular yet?
(My question is probably badly formulated, sorry for this.)
TheoretiCS is an overlay journal in Theoretical CS (hence charge-free and in full open access), launched two years ago. From my point of view it has all the desirable qualities (including a…
sparusaurata
- 499
- 3
- 12