Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
259
questions
268
votes
39
answers
142k
views
What Books Should Everyone Read?
[Timeline]
This question has the same spirit of what papers should everyone read and what videos should everybody watch. It asks for remarkable books in different areas of theoretical computer ...
48
votes
4
answers
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-...
- 18.9k
616
votes
6
answers
130k
views
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:
IntMap (also invented by ...
- 8,861
122
votes
15
answers
19k
views
What Lecture Notes Should Everyone Read?
There has been several questions with the same scheme as this one:
What papers should everyone read
What books should everyone read
What are the recent TCS books whose drafts are available online
...
68
votes
17
answers
5k
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 ...
37
votes
7
answers
9k
views
Books on programming language semantics
I've been reading Nielson & Nielson's "Semantics with Applications", and I really like the subject. I'd like to have one more book on programming language semantics -- but I really can get only ...
- 972
102
votes
39
answers
15k
views
What are the recent TCS books whose drafts are available online?
Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.
For instance, the Approximation Algorithms entry of the above post cites ...
85
votes
20
answers
11k
views
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science. The best examples are those ...
79
votes
14
answers
23k
views
Uses of algebraic structures in theoretical computer science
I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (...
- 893
55
votes
2
answers
4k
views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as "...
- 18.9k
44
votes
7
answers
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 ...
- 3,713
31
votes
2
answers
7k
views
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
- 803
20
votes
4
answers
3k
views
Computational complexity in quantitative finance
Predicting the stock market is hard! Can TCS make this sentiment more formal?
Recently I have started thinking a little bit about finance, and was wondering how knowledge of TCS could help. Hedge ...
- 10.2k
8
votes
2
answers
1k
views
(0,1)-vector XOR problem
this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. ...
- 10.9k
73
votes
14
answers
19k
views
Applications of topology to computer science
I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments. It ...
- 851
33
votes
7
answers
2k
views
Algorithmic lens in the social sciences
Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In ...
- 10.2k
30
votes
3
answers
2k
views
Translating SAT to HornSAT
Is it possible to translate a boolean formula B into an equivalent conjunction of Horn clauses? The Wikipedia article about HornSAT seems to imply that it is, but I have not been able to chase down ...
- 1,089
23
votes
2
answers
3k
views
computing the minimal NFA for a DFA
Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
- 10.9k
18
votes
3
answers
1k
views
Trade off between time and query complexity
Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query ...
- 10.2k
18
votes
2
answers
6k
views
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ...
- 10.9k
17
votes
2
answers
1k
views
A reading list on experimental algorithmics
As in, the area of the papers in the ACM Journal on Experimental Algorithmic JEA.
Which were the foundational works? What are the main results? How are they characterized? Any interesting connections ...
84
votes
42
answers
17k
views
Funny TCS-related papers etc?
What is the funniest TCS-related published work you know?
Please include only those that are intended to be funny. Works which are explicitly crafted to be intelligently humorous (rather than, say, ...
46
votes
5
answers
3k
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-...
- 563
42
votes
23
answers
5k
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, ...
41
votes
3
answers
4k
views
Is the integer factorization problem harder than RSA factorization: $n = pq$?
This is a cross-post from math.stackexchange.
Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $...
user17
40
votes
1
answer
3k
views
Prerequisite for learning GCT
It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory.
While I am a CS student and do NOT have classes of very abstract ...
- 401
38
votes
12
answers
31k
views
Books on automata theory for self-study
I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
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.7k
28
votes
2
answers
1k
views
Kolmogorov's conjecture that $P$ has linear-size circuits
In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find ...
- 381
25
votes
5
answers
2k
views
Subexponentially solvable hard graph problems
In light of the recent result of Arora, Barak, and Steurer, Subexponential Algorithms for Unique Games and Related Problems, I'm interested in graph problems that have subexponential time algorithms ...
- 20.8k
19
votes
4
answers
1k
views
"All-different hypergraph coloring" - known problem?
I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
- 1,023
17
votes
3
answers
931
views
Formal Semantics of Programming Languages
I'm new to programming languages theory and I'm seeking for a good resource on a resource for formal semantics of programming languages. Specifically looking for structural operational semantics. I ...
- 273
17
votes
1
answer
955
views
Reading up on $BQP = BPP^{BQNC}$
What should I read to understand this problem?
The power of small-depth quantum
circuits. Is $BQP = BPP^{BQNC}$? In other
words, can the "quantum" part of any
quantum algorithm be compressed ...
- 1,641
16
votes
1
answer
471
views
Lower bounds on the size of CFGs for specific finite languages
Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?
We can make the question more interesting by specifying a sequence of ...
- 14.2k
6
votes
0
answers
1k
views
k-CNF ←→ k-DNF conversion to minimize errors
the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ...
- 10.9k
2
votes
0
answers
554
views
State of the art for SAT solvers [duplicate]
Possible Duplicate:
Best Upper Bounds on SAT
I'm working on the obstruction-set-free grid coloring problem; a specific instance of it is described in this previous question on coloring 17x17 ...
- 5,961
2
votes
1
answer
571
views
techniques or examples of analyzing a series of graphs
Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "...
- 10.9k
123
votes
18
answers
9k
views
Examples of the price of abstraction?
Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely:
It is known that Gaussian ...
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
41
votes
6
answers
3k
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 ...
39
votes
7
answers
7k
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 ...
- 4,670
34
votes
2
answers
1k
views
Does LOGLOG = NLOGLOG?
Define LOGLOG as the class of languages which can be computed in space O(loglog n) by a deterministic Turing machine (with two-way access to the input). Similarly define NLOGLOG as the class of ...
- 14k
30
votes
2
answers
1k
views
Polynomial method for complexity results
Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee ...
- 7,628
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.5k
28
votes
6
answers
2k
views
Alternative proofs of Schwartz–Zippel lemma
I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz.
Are there any other ...
- 3,664
27
votes
5
answers
2k
views
Ecology and evolution through the algorithmic lens
The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very ...
- 10.2k
27
votes
3
answers
1k
views
Succinct Problems in $\mathsf{P}$
The study of Succinct representation of graphs was initiated by Galperin and Wigderson in a paper from 1983, where they prove that for many simple problems like finding a triangle in a graph, the ...
- 1,334
25
votes
3
answers
1k
views
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?
Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" ...
user17918
24
votes
2
answers
1k
views
What is the big version of NC?
$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$...
- 10.2k
24
votes
3
answers
1k
views
NP complete graph problems about structural properties
(This question is a bit of a "survey".)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some ...
- 431