Most Popular
1500 questions
17
votes
2 answers
Gentle introduction to graph isomorphism for bounded valance graphs
I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it too abstract. I would be thankful if anybody can…
DurgaDatta
- 1,281
- 6
- 18
17
votes
2 answers
Unary languages recognized by two-way deterministic counter automata
2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language:
\begin{equation}
\mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace.
\end{equation}
Is there any other nontrivial unary language…
Abuzer Yakaryilmaz
- 3,707
- 1
- 20
- 38
17
votes
3 answers
Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)
Answer: not known.
The questions asked are natural, open, and apparently difficult; the question now is a community wiki.
Overview
The question seeks to divide languages belonging to the complexity class $P$ — together with the decision Turing…
John Sidles
- 1,536
- 1
- 12
- 28
17
votes
1 answer
Which results make quantum space interesting?
Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation?
I know many interesting results for quantum computation with sublogarithmic space bounds and various kind of quantum automata models.
On…
Abuzer Yakaryilmaz
- 3,707
- 1
- 20
- 38
17
votes
2 answers
Decidability of fractal maze
A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article:
Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy of the maze, be sure to record the letter name of…
Nick Alger
- 353
- 2
- 11
17
votes
1 answer
Geometric picture behind quantum expanders
(also asked here, no replies)
A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert \mathbb{E}_{U \sim \nu} U \otimes U^{\dagger} -…
Marcin Kotowski
- 2,806
- 19
- 25
17
votes
1 answer
How does inheritance differ from subtyping?
In programming language perspective, what is mean by subtyping? I heard that "Inheritance is not Subtyping". Then what are the differences between inheritance and subtyping?
RoboAlex
- 273
- 2
- 6
17
votes
2 answers
Representing non-planar graphs with overlapping circles
We know that we can represent any planar graph by a set of circles in the plane, known as a coin graph. Each circle represents a vertex and there is an edge between two vertices if and only if the circles "kiss" at their boundary.
Suppose that…
Joe
- 1,327
- 8
- 19
17
votes
3 answers
Merging Two Binary Search Trees
I'm looking for an algorithm to merge two binary search trees of arbitrary size and range. The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into an arbitrary external node in the other tree. …
efritz
- 273
- 2
- 6
16
votes
6 answers
What is the point of calling $\lambda$-calculus an algebra?
What is the difference of calling $\lambda$-calculus an algebra instead of a calculus? I raise this question because I read somewhere the line "$\lambda$-calculus is not a calculus but an algebra" (iirc, attributed to Dana Scott). What is the point?…
day
- 2,795
- 1
- 20
- 27
16
votes
2 answers
Permutation phrases with LR parsing
A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$ through $A_n$. At the position of the…
Alex ten Brink
- 4,680
- 25
- 48
16
votes
13 answers
What are some problems where we know we have an optimal algorithm?
What are some non-trivial problems where we know the current algorithm we have is the asymptotically optimal one? (For turing machines)
And how is this proved?
sture
- 173
- 4
16
votes
1 answer
Solving a linear diophantine equation approximately
Consider the following problem:
Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in standard binary representation.
Output: $\mathbf{x}…
Sasho Nikolov
- 18,189
- 2
- 67
- 115
16
votes
3 answers
When can we say that two programs are different?
Q1. When can we say that two programs (written in some programming language like C++) are different?
The first extreme is to say that two programs are equivalent iff they are identical. The other extreme is to say two programs are equivalent iff…
Anonymous
- 4,041
- 19
- 43
16
votes
3 answers
Chernoff-type Inequality for pair-wise independent random variables
Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value and the deviation. Is there a Chernoff-type…
Rahul Tripathi
- 161
- 1
- 3