Most Popular
1500 questions
17
votes
2 answers
Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?
Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?
$isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$
$link(G,a,b)$: Adds an edge from $a$ to $b$ in the graph…
Justin Kilpatrick
- 173
- 5
17
votes
2 answers
Is PARITY in QAC_0 (if that even makes sense)
As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in
fact const-dept circuits require EXP number of gates.
What about QUANTUM circuits?
a) Can PARITY be done with a quantum circuit that has constant depth and poly…
Bill GASARCH
- 549
- 2
- 4
17
votes
3 answers
Succinct data structures survey?
Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them.
For those that don't know about succinct data structures:
Given a combinatorial structure, with
a(n) distinct…
Chad Brewbaker
- 2,359
- 15
- 18
17
votes
0 answers
complexity of checking if a subspace is a Euclidean section of L1
If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have
$(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$
for some small $\epsilon >0$, then we say that $X$ is an almost-Euclidean…
Luca Trevisan
- 4,912
- 28
- 34
17
votes
0 answers
Linear-time algorithm to test if clique number equals degeneracy bound?
Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique.
A well-known bound on the clique number is $\omega\le d+1$, which is helpful when solving the maximum clique problem or…
Austin Buchanan
- 1,166
- 1
- 17
- 28
17
votes
1 answer
Can we derive Cubical Type Theory from Self-Types?
Self Types are known for being a simple extension to the Calculus of Constructions that allow it to derive all inductive datatypes of a proof assistant like Coq and Agda, without a "hardcoded" native datatype system. I am now trying to answer if we…
MaiaVictor
- 3,137
- 11
- 33
17
votes
4 answers
Applications of metric structures on posets/lattices in theoryCS
Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper bound in $X$, and similarly define $x \wedge y$…
Suresh Venkat
- 32,071
- 4
- 95
- 271
17
votes
5 answers
Why do TCS papers have author names in alphabetical order of their surnames?
I am currently doing a Ph.D. in Theoretical Computer Science, and any research paper I encountered so far has the author's names in alphabetical order of their surnames.
For example consider the most fundamental book on algorithms: "Introduction to…
Inuyasha Yagami
- 1,531
- 1
- 8
- 25
17
votes
3 answers
Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?
There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an optimum value. And another theory, that of differential…
Oleksandr Bondarenko
- 4,215
- 1
- 25
- 46
17
votes
2 answers
Category theory, computational complexity, and combinatorics connections?
I have been trying to read “Pearls of Functional Algorithm design”, and subsequently “The Algebra of Programming”, and there is an obvious correspondence between recursively (and polynomially) defined data types and combinatorial objects, having the…
Stefan Petrov
- 173
- 1
- 7
17
votes
6 answers
When have we found better bounds for known algorithms?
Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - obviously that's happened! But better analysis leading…
Rob Simmons
- 341
- 1
- 5
17
votes
1 answer
Is the Set of all Primitive Words a Prime Language?
A word $w$ is called primitive, if there is no word $v$ and $k > 1$ so that $w = v^k$.
The set $Q$ of all primitive words over an alphabet $\Sigma$ is a well known language. WLOG we can choose $\Sigma = \{ a,b \}$.
A language $L$ is prime, if for…
Henning
- 59
- 2
- 13
17
votes
1 answer
The TOC Blog Aggregator is Offline
I apologise if this is off-topic.
It seems that the domain name has expired. I hope some member(s) of the community here (I am not one) may know who was the administrator/owner of that site. It was quite a useful resource.
kodlu
- 2,070
- 13
- 23
17
votes
0 answers
Did von Neumann answer to Gödel's letter?
On 20 March 1956, Kurt Gödel wrote a famous letter to John von Neumann, in which he formulated the P versus NP question.
Here is a link to that letter: [pdf of letter]
I cant seem to find John von Neumann's answer to Gödel's letter online.
Was…
dreizehnutters
- 171
- 4
17
votes
4 answers
How to come up with an non-trivial idea in theoretical computer science?
I am a PhD student working in theoretical computer science. I have read the research papers of many researcher and I have seen many tools and mathematics they use for designing an algorithm. For example see this research paper [Primality in P]. I…
lovw
- 307
- 1
- 5