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

learn more… | top users | synonyms

8
votes
2answers
404 views

Problems with no quantum advantage

I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. To start things off, I think computation of ...
6
votes
2answers
206 views

Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

What are some (not well-known) assertions that if true, the PH must collapse? Replies containing a short high-level assertion with reference(s) are appreciated. I tried to reverse-search without much ...
8
votes
8answers
606 views

Counterintuitive results for undergraduates

I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get ...
22
votes
2answers
1k views

Complexity zoo for unary languages

Of course, some complexity results may collapse for unary languages but I wonder if there is somewhere a survey summarizing the known results in this case: a kind of complexity zoo for unary ...
2
votes
1answer
55 views

List of papers on Runtime and Statistical Tradeoffs on Machine Learning

I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having ...
10
votes
2answers
979 views

List of number theoretic or algebraic problems in various complexity classes

I am looking for a list about the known or unknown complexity of various number theoretic /algebraic problems. For example, GCD in $NC^1$ is open, factoring in $P$ is open, computing sheaf ...
5
votes
2answers
248 views

Research problems in communication complexity

There have been many open challenges questions in this forum. For instance, Research and open challenges in Programming Language Theory What are current open problems in compiler theory? ...
10
votes
3answers
414 views

Problems not known to be PSPACE-complete

What are problems with the following properties: 1) they are restriction of (possibly well known) problems that are PSPACE-complete; 2) the restricted versions are in PSPACE, but it is an open ...
28
votes
7answers
3k views

Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
5
votes
1answer
289 views

How would a theory of computation course that culminated in lambda-calculus as “the” model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
4
votes
1answer
159 views

Introductions to steganography from an information-theoretic standpoint

Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
2
votes
2answers
117 views

Reference on cryptography methods

I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness ...
8
votes
1answer
176 views

What are the major research issues in distributed transactions?

Background: Transaction processing has been a traditional research topic in database theory. Nowadays distributed transactions are popularized by the large-scale distributed storage systems which ...
7
votes
0answers
102 views

Examples of open problems solved through application of a theorem already known

Are there good examples of reasonable open problems in TCS that had an 'obvious' solution via application of a theorem found in mathematics probably found a few decades earlier but went unnoticed in ...
2
votes
1answer
136 views

State of the art algorithms for community detection in graphs

Is anyone aware of the must read papers to get knowledge of the most recent algorithms and method for community detection in graphs, especially those that represent social networks?
2
votes
1answer
207 views

Important papers and open problems in Boolean functions

I am interested in Boolean function polynomial/rational exact/approximate/one sided approximate representation, relation to circuit/communication complexity, tools utilized to study Boolean functions ...
7
votes
4answers
321 views

Explaining computer science algorithms/concepts/ideas using metaphors

Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even ...
13
votes
2answers
509 views

Long-Standing Conjectures later trivially proved by an implication

I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.
12
votes
3answers
610 views

EXPSPACE-complete problems

I am currently trying to find EXPSPACE-complete problems (mainly to find inspiration for a reduction), and I am surprised by the small number of results coming up. So far, I found these, and I have ...
40
votes
16answers
10k views

Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS. It is quite clear that most of us might be attracted to read (or at least glance at) a ...
29
votes
7answers
3k views

Lipton's most influential results

Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize "for Introduction of New Ideas and Techniques". What are to your minds the main new ideas and techniques that Lipton ...
2
votes
5answers
461 views

Problems that are hard to prove in $\mathcal{P}$

What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after? I want to know a list of problems that are difficult to prove in the class of "easy" problems? Maybe like matching, ...
1
vote
0answers
82 views

Good references for understanding the underlying abstractions/ideas of functional programming?

What are some good references, not very dense, to understand the underlying math and computability aspects of the notion of "functional programming"? I'd like to have something that talks about it ...
12
votes
4answers
4k views

Interesting results in TCS which are easily explainable to programmers without technical background

Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math. In order to show them the beauty of TCS, I'd ...
2
votes
3answers
630 views

Does anyone know of online video courses (in english) on randomness in theoretical computer science?

I have found some video courses like this one but they are all in russian or other languages I don't understand. I'll like to know if anyone has come across lectures (courses) of this kind which are ...
1
vote
2answers
178 views

research on systematically attacking multiple instances of undecidable problems

this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint. there are at least ...
48
votes
5answers
4k 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 ...
20
votes
11answers
3k 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 ...
10
votes
6answers
951 views

variations of SAT

I looked up on the internet, but I could not find any 'big-list' of variants of SAT problem. Apart from the (common) SAT, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT what else variants are ...
8
votes
3answers
494 views

Kolmogorov Complexity applications in Number Theory

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.) One of ...
3
votes
2answers
351 views

Asymptotically good codes

In short my question is what are all known explicit constructions of asymptotically good codes over finite alphabet? In more details: A sequence of codes codes $C_i: F^{k_i}\rightarrow F^{n_i}$ with ...
16
votes
11answers
2k views

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form? I understand lots of things that might cause a log ...
10
votes
4answers
619 views

List of strongly NP-hard problems with numerical data

I am looking for strongly NP-hard problems for a reduction. So far I have found the following problems: 3-partition problem bin-packing problem Numerical 3-dimensional matching TSP Any NP-complete ...
9
votes
3answers
451 views

Proofs found by computer

In 1996, a long-standing open problem was solved by a computer; namely, that Robbins algebra and Boolean algebra are the same. The proof was found by an automated theorem prover. Moreover, the known ...
14
votes
7answers
723 views

Pointers for CS applications of logic

I'm a grad student in math with a solid background in logic. I've taken a year-long graduate course in logic together with graduate courses on finite model theory and another on forcing and set ...
31
votes
1answer
1k 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 ...
1
vote
1answer
968 views

List of TCS conferences along with important dates

I saw that there is a post with a List of TCS conferences. However, this does not list important dates like conference date, submission deadline etc. Is there any post or website which maintains these ...
20
votes
7answers
1k views

Golden ratio or Pi in the running time

There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.
17
votes
2answers
346 views

What are TCS conjectures that were proved for primes and small values but then turned out to be false?

Are there any conjectures in theoretical computer science that involve some parameter n and were proved for small values of n AND for primes but later turned out to be false? In number theory such ...
2
votes
3answers
211 views

References on model checking and pi calculi

I'm a mathematician and it looks like I need to learn about these topics. What would be good references that go into the technical details of the following topics? (s)pi calculus model checking I'm ...
2
votes
0answers
96 views

Impractical problems in P [duplicate]

Possible Duplicate: Polynomial-time algorithms with huge exponent/constant In many texts you find statements like 'The class P characterizes the problems that are efficiently solvable. Even ...
11
votes
1answer
474 views

Online Algorithms books

Are there any recent books on Online Algorithms? I know of only two books on the subject. Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv: This is a classic but old ...
2
votes
1answer
258 views

Algorithms for graph generation given parameters

I guess there may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g. clustering coefficient, average path length, degree distribution, etc). I am ...
2
votes
1answer
781 views

What are some good references for mathematical optimization for the layman?

I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
25
votes
10answers
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 ...
7
votes
1answer
276 views

Reading list on rewriting systems?

I am new to studying rewriting systems as a first year PhD student. I would like to propose a special topics course on rewriting theory, and I want to make sure I don't leave any of the original ...
15
votes
5answers
1k views

Examples of pedantry in TCS

Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it): The ...
14
votes
5answers
1k views

Papers every complexity theorist should read

I am starting my PhD this autumn and I am planning to work in complexity theory for my thesis. I am compiling a list of important papers that every complexity theorist should know. What papers would ...
12
votes
4answers
1k views

Alan Turing Documentaries

To celebrate Alan Turing 100th birthday, I want to watch a documentary about his life. However, there are several documentaries to choose from. Which documentary about Alan Turing is your favorite? ...
43
votes
10answers
10k 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 ...