All Questions
12,315
questions
16
votes
1
answer
378
views
Compared growth of the number of syntactic classes and Nerode classes.
For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. :
u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].
Now define the Nerode equivalence as the ...
- 3,916
29
votes
4
answers
2k
views
Bounded-cardinality bounded-frequency set cover: hardness of approximation
Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.
Example: the case $k = 4$ ...
- 11.4k
379
votes
92
answers
113k
views
Algorithms from the Book
Paul Erdős talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the ...
32
votes
1
answer
6k
views
What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes
I'm trying to wrap my head around what the real differences between the Actor Model of concurrency and Communicating Sequential Processes (CSP) model of concurrency.
So far the best that I have ...
- 423
37
votes
3
answers
2k
views
Parameterized complexity of Hitting Set in finite VC-dimension
I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
- 2,583
25
votes
2
answers
1k
views
Approximating the sign rank of a matrix
The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in ...
- 1,704
29
votes
2
answers
2k
views
What are the consequences of Parity-L = P?
Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or ...
- 8,871
230
votes
60
answers
96k
views
Major unsolved problems in theoretical computer science?
Wikipedia only lists two problems under "unsolved problems in computer science":
P = NP?
The existence of one-way functions
What are other major problems that should be added to this list?
Rules:
...
22
votes
2
answers
1k
views
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 ...
- 2,025
30
votes
2
answers
6k
views
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
- 793
15
votes
3
answers
914
views
Can it be determined if language L lies in NP?
Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
- 793
14
votes
1
answer
38k
views
Is integer factorization an NP-complete problem? [duplicate]
Possible Duplicate:
What are the consequences of factoring being NP-complete?
What notable reference works have covered this?
- 793
13
votes
1
answer
346
views
Finding odd holes in circulant Paley graphs
The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 ...
- 8,871
12
votes
2
answers
385
views
Computational query complexity of SQ-learning
It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...
- 9,820
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 ...
- 962
68
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?
- 793
-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?
- 793
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
380
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,245
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
587
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 ...
- 13.4k
21
votes
3
answers
541
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 ...
- 853
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 ...
- 36.3k
10
votes
2
answers
297
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)...
- 6,974
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 ...
- 31.9k
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?
- 13.5k
94
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 ...
user200
24
votes
2
answers
868
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
495
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 ...
- 311
14
votes
1
answer
696
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
682
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 ...
- 18.8k
-1
votes
2
answers
616
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
678
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$?
- 3,280
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}...
- 1,459
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,953
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 ?
- 31.9k
21
votes
1
answer
329
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 ?
- 31.9k
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
457
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.