All Questions

Filter by
Sorted by
Tagged with
26 votes
4 answers
3k views

DFA intersection in subquadratic space?

The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the ...
67 votes
17 answers
4k views

Applications of TCS to classical mathematics?

We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.). What are some examples of when it has gone the other way around? Here ...
-2 votes
2 answers
384 views

Can every non-deterministic finite automate be changed into one with only one acceptance state? [closed]

How can an arbitrary non-deterministic finite automate be converted into one with only one accept stage? If so, what is the proof that this can always be done?
-6 votes
1 answer
6k views

What is the advantage of red/black trees in comparison with unbalanced trees? [closed]

In which situations would I use a red/black tree instead of an unbalanced tree?
42 votes
7 answers
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?
  • 1,648
23 votes
1 answer
378 views

Cliquewidth of Almost Cographs

(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer) I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (...
  • 5,235
39 votes
13 answers
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 ...
22 votes
2 answers
580 views

Lower bounds for constant-depth formulae?

We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known ...
21 votes
3 answers
540 views

Are recursive forms of Godel's statement possible?

The self-referentiality of the P/NP problem has sometimes been highlighted as a barrier to its resolution, see, for instance, Scott Aaronson's paper, is P vs. NP formally independent? One of the many ...
36 votes
5 answers
2k views

Complexity of testing for a value versus computing a function

In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example: Evaluating the ...
10 votes
2 answers
295 views

Is there an official name for a notion of "reusably universal"?

There are several different (probably inequivalent) notions of computational universality (see for example the last couple pages of http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf)...
10 votes
3 answers
1k views

A more intuitive proof of the Zone theorem ?

The Zone theorem says that if we stab an arrangement of n lines with another line, the total complexity of its zone, the set of all 0-, 1-, and 2-faces adjacent to it, is O(n). The actual constant is ...
10 votes
5 answers
3k views

What are good references on understanding online learning?

Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I ...
23 votes
3 answers
1k views

What is known about solutions to sparse integer linear programming problems?

If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what ...
  • 681
5 votes
0 answers
254 views

When designing an explicitly parallel language, what built in functions should be parallelized? [closed]

As stated by the title. Some examples that I would include would be map and conditionals. What other functions should be built in already parallel for users to expand on it?
  • 171
51 votes
4 answers
5k views

What are the best current lower bounds on 3SAT?

What are the best current lower bounds for time and circuit depth for 3SAT?
93 votes
9 answers
19k views

What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why? Turing, Rosser etc ...
user avatar
24 votes
2 answers
846 views

What evidence do we have for (and against) Unique Games Conjecture?

Subhash Khot's Unique Games Conjecture is one of active research areas in complexity theory. What evidence do we have for it? What evidence do we have against it?
57 votes
18 answers
2k views

Where and how did computers help prove a theorem?

The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful in building a conjecture that lead to a theorem, falsifying a ...
21 votes
4 answers
491 views

Which results in complexity theory make essential use of uniformity?

A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like ...
  • 21.3k
141 votes
30 answers
24k views

Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
17 votes
3 answers
2k views

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ...
14 votes
1 answer
691 views

What are the historical roots of Milner's bigraphs?

Robin Milner defined bigraphs as a type of graphical structure with graph-like structure but where the nodes can be nested. They generalise process calculi like CCS and the $\pi$-calculus, but Milner ...
14 votes
2 answers
1k views

How large a treewidth can a tree plus half the edges have?

Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible? It ...
  • 1,384
17 votes
2 answers
677 views

H-free cut problem

Suppose you are given a connected, simple, undirected graph H. The H-free cut problem is defined as follows: Given a simple, undirected graph G, is there a cut (partition of vertices into two ...
  • 1,855
27 votes
4 answers
2k views

What specific evidence is there for P = RP?

RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
-1 votes
2 answers
615 views

Minimum spanning tree algorithm. [closed]

Is the following a valid algorithm for finding a minimum spanning tree? Given a weighted graph with unique weights, remove the all edges that are the highest cost edge in any cycle of the original ...
  • 151
12 votes
2 answers
675 views

Simple balanced trees with O(1) concat?

In Purely Functional Worst Case Constant Time Catenable Sorted Lists, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data ...
  • 11.1k
30 votes
2 answers
2k views

Hierarchies in NP (under the assumption that P != NP)

Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem. Is there any evidence of more ...
  • 1,855
26 votes
1 answer
2k views

Consequences of Complete problems for NP intersects coNP

What are the consequences of having complete problems in $NP\cap coNP$?
65 votes
11 answers
5k views

What are good references to understanding the proof of the PCP theorem?

I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
20 votes
2 answers
1k views

Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE: END OF THE LINE: Given circuits S and P ...
  • 5,973
24 votes
3 answers
1k views

Graph Isomorphism and hidden subgroups

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
21 votes
1 answer
326 views

A comparison of extractors in terms of tradeoffs between time, randomness and space ?

Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?
128 votes
11 answers
11k views

How hard is unshuffling a string?

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a ...
  • 22.9k
8 votes
1 answer
452 views

Best resources for string searching or pattern matching exercises

I would like to be somewhat good at string searching and pattern matching, could you point me to some good online resources? Exercise problems would be great. Thanks.
17 votes
3 answers
758 views

Are there any known implementations for quantum computing constructs?

Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the ...
  • 2,233
17 votes
1 answer
1k views

Online transitive closure better than O(N^2) per edge addition

I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: ...
  • 696
16 votes
6 answers
4k views

Complexity of the Fisher-Yates Shuffle Algorithm

This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n). In ...
16 votes
1 answer
564 views

Why is it important that the secret is at the end when signing with MD5?

it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?
19 votes
0 answers
502 views

To what extent MSO = WS1S, when adding relations?

[This question has been asked on MathOverflow with no luck a month ago.] Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma =\{a_1, \ldots, a_n\}$, I define two ...
24 votes
5 answers
2k views

What are some career options for someone with a computer scientist master degree?

Other than going fully academic and getting a doctorate/post-doc, or going for a more or less 'standard' job in software development, what are some other career options in the full or semi theoretical ...
35 votes
4 answers
980 views

Correspondence between complexity classes and logic

I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, ...
  • 853
50 votes
12 answers
4k views

What is the theoretical basis of imperative programming?

Functional programming has a theoretical basis in lambda calculus and combinatory logic. As someone involved with statistical computing, I find these concepts to be very useful for modeling. Is ...
  • 2,233
8 votes
3 answers
3k views

Is Deolalikar's 2010 proof that $P \ne NP$ correct?

There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof. So ... is the proof correct or not ? (Please only answer this if you ...
  • 853
21 votes
3 answers
542 views

space-bounded TMs and oracles

In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions). Is such a ...
8 votes
1 answer
195 views

Process modeling with fine-grained notions of location

Is anyone aware of any process algebraic (or related) formalisms that capture fine-grained location information? I'm familiar with ambients and bigraphs, which obviously have a location model, but ...
  • 288
10 votes
1 answer
317 views

Generalizing the FFT

Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically? Is there an algorithm that takes in a description of transform (I don't know ...
15 votes
2 answers
1k views

What is the following variation on Set Cover known as?

What is the following variation on set cover known as? Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in ...
  • 356
8 votes
1 answer
1k views

What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?

A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like, ...
  • 191

15 30 50 per page