Most Popular
1500 questions
21
votes
7 answers
Universities for Quantum Computing / Information?
Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research?
The aim here is to collect a useful list for someone considering graduate study in these fields, not to discuss…
Vincent Russo
- 935
- 1
- 6
- 21
21
votes
2 answers
Is it necessary to call matrix multiplication $n$ times to find a claw
A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the subgraph induced by $N[v]$ for each vertex $v$,…
Yixin Cao
- 2,560
- 1
- 16
- 29
21
votes
2 answers
Deterministic communication complexity vs partition number
Background:
Consider the usual two-party model of communication complexity where Alice and Bob are given $n$-bit strings $x$ and $y$ and have to compute some Boolean function $f(x,y)$, where $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$.
We define the…
Robin Kothari
- 13,617
- 2
- 60
- 116
21
votes
3 answers
How much time to recognize palindromes in logarithmic space?
It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time algorithm uses a copy of the input, and thus also…
Bruno
- 4,449
- 33
- 45
21
votes
3 answers
Using Kolmogorov complexity as input "size"
Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$.
Normally in the analysis of algorithms or computational complexity theory, we have some sets
$$I(n) = \{w \in S : |w| = n\}$$
of all inputs…
Andrew
- 284
- 1
- 16
21
votes
2 answers
$NP$-completeness of recognizing the difference of two permutations
Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two permutations. Unfortunately, I don't see a…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
21
votes
1 answer
A Lambda calculus for invertible (r-Turing computable) functions
I'm interested in the concept of "r-Turing completeness", as defined by Axelsen and Glück (2011). A system is r-Turing complete if it can compute the same set of functions as a reversible Turing machine, without producing any "garbage" data. This is…
N. Virgo
- 699
- 3
- 10
21
votes
1 answer
Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?
Consider the problem of finding a maximum disjoint set - a maximum set of non-overlapping geometric shapes, from a given collection of candidates. This is an NP-complete problem, but in many cases, the following greedy algorithm yields a…
Erel Segal-Halevi
- 2,212
- 12
- 20
21
votes
2 answers
Max-Cut algorithm that shouldn't work, unclear why
OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic:
Given an undirected graph $G=(V,E)$, give an algorithm that finds a cut $(S,\bar{S})$…
Yonatan
- 794
- 4
- 13
21
votes
1 answer
Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?
Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $.
It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) (Szepietowski, 1994). (There is an ATM using…
Abuzer Yakaryilmaz
- 3,707
- 1
- 20
- 38
21
votes
6 answers
What is the best way to get a close-to-fair coin toss from identical biased coins?
(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many suffice). This question concerns the case when…
Hrushikesh
- 376
- 1
- 7
21
votes
4 answers
Abstract algebra for Theoretical Computer Scientists
I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ). I think this was partly as I needed to see applications and any that I could find were in…
Majid
- 333
- 2
- 7
21
votes
3 answers
Graphs in which every minimal separator is an independent set
Background:
Let $u, v$ be two vertices of an undirected graph $G=(V,E)$.
A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$
belong to different connected components of $G-S$. If no proper
subset of a $u,v$-separator $S$ is a…
user13667
- 398
- 3
- 10
21
votes
2 answers
An intuitive/informal proof for LP Duality?
What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of understanding the bound?
The way I was taught Duality…
PhD
- 5,305
- 5
- 25
- 40
21
votes
1 answer
Combinators for the Primitive Recursive Functions
It is well-known that the S and K combinators are Turing Complete. Are there combinators that suffice to yield (only) the primitive recursive functions?
NietzscheanAI
- 775
- 4
- 11