Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
18
votes
1 answer

Parametricity and projective eliminations for dependent records

It's well-known that in System F, you can encode binary products with the type $$ A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha $$ You can then define projection functions $\pi_1 : A \times B \to A$ and $\pi_2 : A \times B…
Neel Krishnaswami
  • 32,528
  • 1
  • 100
  • 165
18
votes
1 answer

Feasibility of Gödel machines

Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine It's a general problem solver which is capable of self-optimization. It's suitable for reactive environments. As I understand, it can be implemented as a…
Dmitry Vyal
  • 333
  • 2
  • 6
18
votes
3 answers

Does randomness buy us anything inside P?

Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$. Do we know of any problem $Q \in \mathsf{P}$ such that $Q \in \mathsf{BPTIME}(n^k)$ but $Q \not \in…
aelguindy
  • 951
  • 7
  • 15
18
votes
2 answers

Are theoretically sound pseudorandom generators used in practice?

As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they pass lots of (heuristic) statistical tests, there…
Henry Yuen
  • 3,798
  • 1
  • 21
  • 33
18
votes
2 answers

Temporally Flat One-Way Quantum Computing

I am a physicist at heart, and so I think One-Way Quantum Computing is brilliant. In particular, Graph State Measurement-based Quantum Computing (MBQC) has been a really nice development in Quantum Computing research as originated by Raussendorf &…
Matty Hoban
  • 283
  • 1
  • 4
18
votes
2 answers

Beginner's Guide to Derandomization

I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented. I'm new to the subject of "Derandomization," and as such, I wanted to know which reference to start from? I prefer one…
Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
18
votes
4 answers

Parametrized Algorithm for Finding Bicliques

Given an $n$ vertex undirected graph, what is the best known runtime bound for finding a subgraph which is a $k\times k$-biclique? Are there faster parametrized algorithms than the $\binom{n}{k}\mbox{poly}(n)$ time algorithm of "guessing" one side…
Andreas Björklund
  • 3,254
  • 1
  • 22
  • 23
18
votes
2 answers

Reconstructing a tree from separator queries

Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?". Assume that each query can be answered in…
Jagadish
  • 1,955
  • 21
  • 27
18
votes
2 answers

Lower bounds on #SAT?

The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying assignments $F$ has. Which are the best lower bounds on…
Giorgio Camerani
  • 6,842
  • 1
  • 34
  • 64
18
votes
5 answers

Real world applications of quantum computing (except for security)

Let's assume that we have built an universal quantum computer. Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it? I am interested in both: problems currently unsolvable for a…
Piotr Migdal
  • 635
  • 4
  • 11
18
votes
11 answers

Are there any applications of techniques in real analysis to theoretical computer science?

I have looked far and wide for such applications and have mostly turned up short. I can find plenty of applications of topology and similar structures on countable (or uncountable) sets, but rarely do I actually find uncountable sets as the object…
robinhoode
  • 313
  • 2
  • 6
17
votes
2 answers

Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?

In the "last paragraph" of the "first page" of the following paper: Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical Computer Science, 1995. I encountered a somewhat…
Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
17
votes
1 answer

Connectivity of graphs by edge and vertex removal

Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the standard definition, is $(k-1,0)$-connected,…
someone
  • 1,414
  • 12
  • 19
17
votes
2 answers

Finding k shortest Paths with Eppstein's Algorithm

I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap construction $H(G)$. So far: $out(v)$ contains all…
Laura
  • 273
  • 2
  • 6
17
votes
2 answers

Forbidden minors for bounded treewidth graphs

This question is similar to one of my previous questions. It is known that $K_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$. Is there a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs and…
Shiva Kintali
  • 10,578
  • 41
  • 74
1 2 3
…
99 100