# All Questions

11,315 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
2k views

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 $... 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 ... 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 ... 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-... 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). ... 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 ... 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-... 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)... 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. 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|$)... 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 ... 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 ... 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 ... 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 ... 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, ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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})}$. ... 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-... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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, ... 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, ... 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 ... 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^{...
1k views

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 ...
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 ...
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 ...
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. ...
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 ...
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?
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 ...
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 ...
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 ...
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, ...
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$, ...