Questions tagged [big-list]

Questions whose answers are a big list of items (books, theorems, software, ...)

Filter by
Sorted by
Tagged with
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? ...
268 votes
39 answers
136k 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 ...
479 votes
72 answers
178k views

What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...
229 votes
60 answers
95k 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: ...
377 votes
92 answers
112k views

Algorithms from the Book.

Paul Erdos 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 Book. If ...
36 votes
5 answers
8k views

NEXP-complete problems

There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
152 votes
39 answers
46k views

What videos should everybody watch?

Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...
102 votes
5 answers
23k views

List of TCS conferences and workshops

I would like to ask for help in compiling a list of as many TCS-related conferences and workshops as possible. My main motivation for doing this is to plan possible blog coverage of more theory ...
120 votes
15 answers
18k 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 ...
62 votes
13 answers
8k views

Open problems on the frontiers of TCS

In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment: I think we should distinguish between major open problems that are viewed ...
604 votes
6 answers
124k 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,661
102 votes
39 answers
14k 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 ...
77 votes
13 answers
22k 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 (...
  • 873
82 votes
20 answers
10k 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 ...
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 ...
71 votes
17 answers
9k views

Polynomial-time algorithms with huge exponent/constant

Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, ...
37 votes
9 answers
2k views

Surprising Results in Complexity (Not on the Complexity Blog List)

What were the most surprising results in complexity? I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of ...
31 votes
13 answers
4k views

Are there any counterintuitive results in theoretical computer science?

Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself? By paradoxes I mean counter intuitive ...
70 votes
13 answers
9k views

Common false beliefs in theoretical computer science

This post is inspired by the one in MO: Examples of common false beliefs in mathematics. Since the site is designed for answering research level questions, examples like $\mathsf{NP}$ stands for non-...
73 votes
9 answers
16k views

Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...
27 votes
12 answers
6k views

What are the popular science books that inspire TCS?

There is a reputation, that in computer science, we do not have popular science books. Of course that's not really true! (In the same spirit of list of What Books Should Everyone Read?, What papers ...
83 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, ...
71 votes
12 answers
9k views

How important is knowing how to program for TCS?

Coming from a more mathematical background, I never really learned how to code. I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in ...
  • 1,645
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, ...
39 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 ...
  • 391
23 votes
8 answers
3k views

graphs from real-life problems

Where can I find graphs relevant to real-life problems? Two repositories I know of are: University of Florida's Sparse Matrix Collection Bodlaender's TreewidthLib
20 votes
6 answers
3k views

Network / Social network analysis visualization tools?

I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network /...
120 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 ...
67 votes
3 answers
8k views

How do I referee a paper?

Updated below We all know the critical importance of peer-review. It is the main form of quality control and feedback on research. However, to an early-stage researcher (like me), it can sometimes ...
56 votes
16 answers
4k views

What tools do you use to write papers?

What tools do you use to write papers? From the little experience that I have, theoreticians spend a large amount of time writing and refining papers, besides actually being creative. That is, ...
53 votes
21 answers
4k views

Dinner-table description of theoretical computer science?

I'm often asked what a theoretical computer scientist does. It would be great to have some nice responses to this question. I tend to fall back to technical jargon and people's eyes usually glaze ...
35 votes
3 answers
981 views

An Anthology of Complexity Assumptions

In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue ...
38 votes
16 answers
8k views

Everyday encounters with NP-complete problems

Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap. ...
14 votes
3 answers
2k views

Lower Bounds for Data Structures

Are results known which rule out the existence of "too-good-to-be-true" data structures? For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz ...
2 votes
2 answers
2k views

Book recommendations for CompSci related math

Searching for good textbooks on math related to Computer Science I bought two german books yet, but found them not to be easily understandable and not suitable for self-study . German textbooks are ...
9 votes
5 answers
650 views

Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string ...
5 votes
0 answers
609 views

Learning quantum CS [duplicate]

Possible Duplicate: What is the quantum computational model? What is the best way to study quantum branch of CS for the person with rather advanced background in classical CS? Does one need to ...
53 votes
2 answers
6k views

What are the outstanding questions in purely functional data structures?

This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998. I'll start with two questions I have: Is there a purely functional set data ...
57 votes
13 answers
4k views

Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
45 votes
10 answers
4k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
62 votes
5 answers
5k views

Overarching reasons why problems are in P or BPP

Recently, when talking to a physicist, I claimed that in my experience, when a problem that naively seems like it should take exponential time turns out nontrivially to be in P or BPP, an "overarching ...
31 votes
19 answers
8k views

Beautiful results in TCS

Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me ...
63 votes
12 answers
3k views

Parameterized complexity from P to NP-hard and back again

I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, ...
  • 2,789
45 votes
5 answers
1k views

Casual tours around proofs

Today Ryan Williams posted an article on the arXiv (previously appeared in SIGACT News) containing a less technical version of his recent ACC lower bound technique. My question is not about the ...
34 votes
14 answers
6k 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 ...
21 votes
7 answers
28k views

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...
61 votes
33 answers
4k views

Small steps for better TCS conferences?

Often, when we take part in TCS conferences, we notice some little details that we wish the conference organisers would have taken care of. And when we are organising conferences, we have already ...
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 ...
14 votes
1 answer
2k views

What are the classic papers from the recursion theoretic area of complexity theory?

Two papers I would include are: D. Kozen, "Indexing of subrecursive classes", STOC, 1978. R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.
36 votes
13 answers
3k views

Easy decision problem, hard search problem

Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete). What are some other examples of problems where ...