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

learn more… | top users | synonyms

0
votes
0answers
55 views

Problems solved by the greedy algorithm for matroids

Given a matroid $\mathcal{M} = (E, \mathcal{I})$ with weights $w : E \rightarrow Q^+$, it is well known that the greedy algorithm finds a maximum weight independent set $S \in \mathcal{I}$ in ...
2
votes
5answers
420 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
61 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
571 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
0answers
117 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 ...
46
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
2k 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 ...
8
votes
6answers
600 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
432 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
307 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 ...
15
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 ...
4
votes
0answers
207 views

listing of strongly NP problems

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 ...
7
votes
3answers
433 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 ...
13
votes
7answers
644 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 ...
30
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
476 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 ...
19
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.
16
votes
2answers
336 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
196 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
95 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 ...
10
votes
1answer
417 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
200 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 ...
1
vote
1answer
497 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' ...
24
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
259 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 ...
13
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 ...
11
votes
3answers
498 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? ...
37
votes
10answers
7k 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 ...
5
votes
2answers
348 views

Could any one enumerate some applications of enumerative combinatorics and Ramsey theory in TCS?

The combinatorics, needless to say, is very closely related to TCS. But I found it hard to find the applications of enumerative combinatorics or Ramsey theory. Or rather than being applied to TCS, ...
15
votes
2answers
789 views

Notable examples of the square root idea in complexity analysis

There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include baby-step giant-step ...
26
votes
19answers
5k 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 ...
8
votes
1answer
2k views

Major unsolved problems in distributed systems?

Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain. Something like membership protocols, data ...
11
votes
2answers
617 views

List of theorems stating that P does not equal NP if and only if

I think it would be a good idea to make a list of theorems stating that P does not equal NP if and only if such and such exits, some complexity class is contained in another complexity class and so on ...
9
votes
4answers
509 views

Approximation algorithms used in exact algorithms

Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms. However, constant factors are ignored in time complexity. So I wonder if ...
4
votes
7answers
449 views

Menagerie of polygons

UPDATE Now community wiki. My new version of the question is: let's make a big list of classes of polygons. We may be able to produce the most comprehensive list on the web, or in the literature. ...
23
votes
2answers
679 views

Advice for attending my first TCS conference

I will be attending my first computer science conference and after reading the advice for how to improve conferences I noticed the several suggestions were about grad students attending their first ...
40
votes
5answers
819 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 ...
58
votes
12answers
5k 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 ...
25
votes
5answers
741 views

Quantum proofs of classical theorems

I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be ...
20
votes
4answers
548 views

Missing Wikipedia articles

Which missing TCS topics on Wikipedia would you most like there to be an article about? They could be glaring omissions or just topics you think should really have an article. One topic per answer ...
71
votes
3answers
7k 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 ...
23
votes
5answers
2k views

Long-lasting errors in computer science

This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow ) As we know, in mathematics even famous mathematicians, superstars and geniuses are doing ...
5
votes
3answers
261 views

Best algorithm for calculating lists of neighbours

Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted ...
31
votes
17answers
2k 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
15answers
3k 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, ...
25
votes
2answers
794 views

Complexity of Topological Properties.

I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description ...
26
votes
15answers
2k views

Examples where insight from geometry was useful for solving something completely non-geometric

One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think ...
57
votes
34answers
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 ...