All Questions

Filter by
Sorted by
Tagged with
46
votes
5answers
2k views

Positive topological ordering

Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
46
votes
5answers
1k views

Are there Conservation Laws in Complexity Theory?

Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems. Or take primality. It is easier to show composites in NP ...
46
votes
0answers
2k views

Monotone complexity of s-t connectivity

In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide whether there is a path between all $n^2$ pairs $...
45
votes
8answers
7k views

The importance of Integrality Gap

I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
45
votes
8answers
5k views

Obituaries of dead conjectures

I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting ...
45
votes
5answers
2k views

Historical reasons for adoption of Turing Machine as primary model of computation.

It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-...
45
votes
4answers
11k views

Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
45
votes
5answers
1k views

Casual tours around proofs

Today Ryan Williams posted an article on the arXiv (previously appeared in SIGACT News) containing a less technical version of his recent ACC lower bound technique. My question is not about the ...
45
votes
4answers
4k views

Generalized Ladner's Theorem

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
45
votes
3answers
5k views

Wikipedia-style explanation of Geometric Complexity Theory

Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment)...
44
votes
7answers
4k views

Using lambda calculus to derive time complexity?

Are there any benefits to calculating the time complexity of an algorithm using lambda calculus? Or is there another system designed for this purpose? Any references would be appreciated.
44
votes
10answers
4k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
44
votes
0answers
1k views

Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
43
votes
10answers
16k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
43
votes
12answers
4k views

Applications of representation theory of the symmetric group

Inspired by this question and in particular the final paragraph of Or's answer, I have the following question: Do you know of any applications of the representation theory of the symmetric group in ...
43
votes
7answers
16k views

Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
42
votes
22answers
4k views

What hierarchies and/or hierarchy theorems do you know?

I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, ...
42
votes
5answers
19k views

Complexity of the simplex algorithm

What is the upper bound on the simplex algorithm for finding a solution to a Linear Program? How would I go about finding a proof for such a case? It seems as though the worst case is if each vertex ...
42
votes
8answers
3k views

Rigour leading to insight

On MathOverflow, Timothy Gowers asked a question titled "Demonstrating that rigour is important". Most of the discussion there was about cases showing the importance of proof, which people on ...
42
votes
8answers
4k views

What do you do when you cannot make progress on the problem you have been working on?

I am a 2nd year graduate student in theory. I have been working on a problem for the last year (in graph theory/algorithms). Until yesterday I thought I am doing well (I was extending a theorem from a ...
42
votes
7answers
5k views

Truly random number generator: Turing computable?

I am seeking a definitive answer to whether or not generation of "truly random" numbers is Turing computable. I don't know how to phrase this precisely. This StackExchange question on "efficient ...
42
votes
5answers
1k views

The cozy neighborhoods of “P” and of “NP-hard”

Let $X$ be an algorithmic task. (It can be a decision problem or an optimization problem or any other task.) Let us call $X$ "on the polynomial side" if assuming that $X$ is NP-hard is known to imply ...
42
votes
3answers
3k views

What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

Background The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
42
votes
4answers
4k views

How would I go about learning the underlying theory of the Coq proof assistant?

I'm going over the course notes at CIS 500: Software Foundations and the exercises are a lot of fun. I'm only at the third exercise set but I would like to know more about what's happening when I use ...
42
votes
4answers
2k views

Why have we not been able to develop a unified complexity theory of distributed computing?

The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed ...
42
votes
4answers
3k views

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

This is a question related to this one. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question. The classical proof of the ...
42
votes
3answers
3k views

Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

The Graph Isomorphism problem (GI) is arguably the best known candidate for an NP-intermediate problem. The best known algorithm is sub-exponential algorithm with run-time $2^{O(\sqrt{n \log n})}$. ...
41
votes
9answers
5k views

References for TCS proof techniques

Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? Garey and Johnson do this for the various kinds of widget constructions needed for NP-...
41
votes
12answers
2k views

Gröbner bases in TCS?

Does anyone know of interesting applications of Gröbner bases to theoretical computer science? Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was ...
41
votes
6answers
2k views

Which model of computation is “the best”?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
41
votes
7answers
4k views

When does randomization speed up algorithms and it “shouldn't”?

Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic ...
41
votes
3answers
5k views

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here. I have asked some people who are ...
41
votes
5answers
4k views

What would you advise someone who wants to do research as a hobby?

I love doing TCS in my spare time. Lately I have been trying to do some research as a hobby. I'm looking for some extra input from people who do this full-time: Do you think it is possible to do this ...
41
votes
2answers
2k views

Alphabet of single-tape Turing machine

Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing ...
40
votes
4answers
5k views

Single author papers against my advisor's will?

I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor. My advisor is not involved in my research projects at all. In particular, ...
40
votes
10answers
12k views

Data for testing graph algorithms

I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
40
votes
3answers
2k views

Circuit lower bounds over arbitrary sets of gates

In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis ...
40
votes
3answers
1k views

A fixed-depth characterization of $TC^0$? $NC^1$?

This is a question about circuit complexity. (Definitions are at the bottom.) Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{...
40
votes
3answers
1k views

Selecting papers to read

DISCLAIMER: This is an open ended question and stackexchange puritans would probably feel an extraordinary urge to vote it down to oblivion. However, I cannot think of any other forum more appropriate ...
40
votes
1answer
2k views

Importance of single author papers?

I'm a fourth year PhD student in theoretical computer science. I'd like to stay in academia, so I'm thinking about how best to advance my career. Obviously the best way to do that is write lots of ...
40
votes
1answer
605 views

Does Rabin/Yao exist (at least in a form that can be cited)?

In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation". This is for the result that the bounded-error communication complexity of the equality function ...
39
votes
7answers
6k views

Applicability of Church-Turing thesis to interactive models of computation

Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. ...
39
votes
13answers
3k views

Using error-correcting codes in theory

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of ...
39
votes
7answers
6k views

Many-one reductions vs. Turing reductions to define NPC

Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
39
votes
7answers
6k views

What do we know about provably correct programs?

The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
39
votes
9answers
23k views

What is the difference between non-determinism and randomness?

I recently heard this - "A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for ...
39
votes
6answers
6k views

Regular expressions aren't

Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton. For ...
39
votes
4answers
5k views

Why does Coq have Prop?

Coq has a type Prop of proof irrelevant propositions which are discarded during extraction. What are the reason for having this if we use Coq only for proofs. Prop is impredicative, so Prop : Prop, ...
39
votes
2answers
2k views

Are the problems PRIMES, FACTORING known to be P-hard?

Let PRIMES (a.k.a. primality testing) be the problem: Given a natural number $n$, is $n$ a prime number? Let FACTORING be the problem: Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...
39
votes
3answers
2k views

Why are mod_m gates interesting?

Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's. What's so ...

15 30 50 per page