Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
22
votes
3 answers

Justifying asymptotic worst-case analysis to scientists

I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. One of the biggest difficulties I've faced is in…
Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
22
votes
1 answer

What are the practical issues with intersection and union types?

I'm designing a simple statically typed functional programming language as a learning experience. It appears that the type system I have implemented so far could (with a little extra work) incorporate intersection and union types, e.g. you could…
mikera
  • 323
  • 1
  • 6
22
votes
3 answers

Limits to Parallel Computing

I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject: http://en.wikipedia.org/wiki/NC_%28complexity%29 The article contains the following sentence: It is…
Vladimir Levin
  • 221
  • 1
  • 2
22
votes
1 answer

Exact algorithm for NAE-3SAT

The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal. The problem is NP-complete. One can reduce 3SAT to it pretty easily so that the…
virgi
  • 2,489
  • 19
  • 25
22
votes
1 answer

Random functions of low degree as a real polynomial

Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$? EDIT: Nisan and Szegedy have shown that a function of degree $d$ depends on at most $d2^d$…
Igor Shinkar
  • 1,927
  • 11
  • 21
22
votes
6 answers

References on Circuit Lower Bounds

Preamble Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than the latter, but Goldwasser and Sipser showed that…
Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
22
votes
3 answers

Bigger picture behind the choice of matrices in the Strassen algorithm

In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the algorithm proceeds recursively computing $7$ block…
user4292
22
votes
2 answers

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about algebraic geometry, and in fact also only have a…
Ross Snider
  • 2,035
  • 2
  • 20
  • 33
22
votes
3 answers

Sorting using a black box

Assume that we want to sort a list $S$ of $n$ real numbers. Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly. How much advantage can we gain using this black box? For example, can we sort the numbers with only…
AmeerJ
  • 679
  • 3
  • 15
22
votes
2 answers

Lower bound for determinant and permanent

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the following questions : Grigoriev and Karpinski proved…
Nikhil
  • 1,354
  • 10
  • 23
22
votes
1 answer

Exact planar electrical flow

Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor. How quickly can we compute the exact effective resistance between two vertices in G? Equivalently, how quickly can we compute the exact current…
Jeffε
  • 23,129
  • 10
  • 96
  • 163
22
votes
2 answers

Relation between $AC^0$ and regular languages

Let $\mathsf{REG}$ be the class of all regular languages. It is known $\mathsf{AC}^0 \not\subset \mathsf{REG}$ and $\mathsf{REG} \not\subset \mathsf{AC}^0$. But is there any characterization for languages in $\mathsf{AC}^0 \cap \mathsf{REG}$?
Alex Grilo
  • 554
  • 2
  • 9
22
votes
2 answers

Graphs in which all shortest paths are unique

I'm looking for undirected, unweighted, connected graphs $G=(V,E)$, in which for every pair $u,v \in V$, there is a unique $u \rightarrow v$ path that realizes the distance $d(u,v)$. Is this class of graphs well-known? What other properties does it…
László Kozma
  • 1,336
  • 1
  • 10
  • 16
22
votes
3 answers

Is there a concept of something like co-applicative functors sitting between comonads and functors?

Any monad is also an applicative functor and any applicative functor is a functor. Also, any comonad is a functor. Is there a similar concept between comonads and functors, something like co-applicative functor, and what are its…
Petr
  • 2,601
  • 15
  • 28
22
votes
1 answer

Consequences of $BQP \subseteq P/poly$?

While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{poly}$. What complexity-theoretic consequences…
Martin Schwarz
  • 5,496
  • 25
  • 41
1 2 3
…
99 100