Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,595
questions
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
269
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 ...
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 ...
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
...
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 ...
94
votes
2
answers
40k
views
What is the actual time complexity of Gaussian elimination?
In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
- 23k
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 ...
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, ...
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
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
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 ...
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
55
votes
7
answers
4k
views
For which problems in P is it easier to verify the result than to find it?
For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) ...
- 11.3k
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
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
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
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
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, ...
42
votes
9
answers
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
12
answers
3k
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 ...
- 11k
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 ...
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
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
39
votes
5
answers
1k
views
Results in Theoretical CS independent of ZFC
I'm going to ask a quite vague question, since the borderline between theoretical computer science and math is not always easy to distinguish.
QUESTION: Are you aware of any interesting result in CS ...
- 491
39
votes
3
answers
2k
views
Is there a backup/replacement for the Complexity Zoo?
This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close.
The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/...
- 5,446
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.
38
votes
2
answers
3k
views
Multiplying n polynomials of degree 1
The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.
You can do $O(n \...
- 1,870
37
votes
6
answers
2k
views
Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?
A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover).
Does anyone know of a problem ...
- 534
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
36
votes
14
answers
7k
views
Book on Probability
While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability.
It seems that the authors of ...
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
34
votes
3
answers
3k
views
complexity of greatest common divisor (gcd)
Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
- 451
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
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
31
votes
2
answers
7k
views
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
- 803
30
votes
6
answers
1k
views
Well known classes of boolean formulas that require exponentially long resolution proofs
You might often find cutting plane methods, variable propagation, branch and bound, clause learning, intelligent backtracking or even handwoven human heuristics in SAT solvers. Yet for decades the ...
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
30
votes
2
answers
5k
views
Quantum matrix multiplication?
It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model? Do we have any intuition that we can beat ...
- 3,738
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
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
29
votes
4
answers
1k
views
Compendium of the Best Approximation and Hardness Results for NP optimization problems
Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?
Based on the feedback, it seems that it is safe to assume there is not such a ...
29
votes
0
answers
1k
views
Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof: if $EXP\...
28
votes
10
answers
2k
views
Probabilistic (randomized) algorithms before "modern" computer science appeared
Edit: I choice the answer with highest score by December 06, 2012.
This is a soft question.
The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?
In ...
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
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
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
27
votes
3
answers
926
views
The complexity of determining if a fixed graph is a minor of another
The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:
1) It appears that there ...
- 779
27
votes
1
answer
919
views
Coloring complexity of graphs
Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
- 14.2k
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