Questions tagged [reference-request]

Reference-request is used when the author needs to know about work related to the question.

Filter by
Sorted by
Tagged with
271 votes
39 answers
144k 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
5k 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-...
András Salamon's user avatar
623 votes
6 answers
131k 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 ...
jkff's user avatar
  • 8,941
123 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 ...
38 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 ...
Jay's user avatar
  • 982
102 votes
41 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 ...
80 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 (...
GEL's user avatar
  • 903
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 "...
András Salamon's user avatar
44 votes
7 answers
6k 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 ...
Joseph O'Rourke's user avatar
31 votes
2 answers
7k views

What would be the consequences of factoring being NP-complete?

Are there any references covering this?
txwikinger's user avatar
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 ...
Artem Kaznatcheev's user avatar
9 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. ...
vzn's user avatar
  • 11k
74 votes
14 answers
20k 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 ...
Ben 's user avatar
  • 861
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 ...
Artem Kaznatcheev's user avatar
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 ...
Evgenij Thorstensen's user avatar
23 votes
2 answers
4k 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 ...
vzn's user avatar
  • 11k
19 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 ...
vzn's user avatar
  • 11k
19 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 ...
Artem Kaznatcheev's user avatar
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 ...
85 votes
42 answers
18k 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-...
Evan's user avatar
  • 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, ...
42 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 $...
user avatar
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 ...
syucha's user avatar
  • 401
39 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 ...
Joshua Grochow's user avatar
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 ...
Hamid's user avatar
  • 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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Falk Hüffner's user avatar
17 votes
1 answer
964 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 ...
Joshua Herman's user avatar
17 votes
3 answers
953 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 ...
systemsfault's user avatar
16 votes
1 answer
478 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 ...
Yuval Filmus's user avatar
  • 14.4k
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 ...
vzn's user avatar
  • 11k
2 votes
1 answer
573 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 "...
vzn's user avatar
  • 11k
2 votes
0 answers
557 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 ...
Daniel Apon's user avatar
  • 5,991
123 votes
18 answers
10k 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}...
Alexandre Passos's user avatar
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 ...
Tatiana Starikovskaya's user avatar
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 ...
Alex ten Brink's user avatar
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 ...
domotorp's user avatar
  • 13.8k
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 ...
Hsien-Chih Chang 張顯之's user avatar
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$ ...
Jukka Suomela's user avatar
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 ...
Dai Le's user avatar
  • 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 ...
Artem Kaznatcheev's user avatar
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 ...
Nikhil's user avatar
  • 1,344
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" ...
user avatar
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 ...
G. Bach's user avatar
  • 431
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$...
Artem Kaznatcheev's user avatar

1
2 3 4 5 6