Questions whose answers are a big list of items (books, theorems, software, ...)
0
votes
0answers
64 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 ...
14
votes
11answers
1k 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 ...
2
votes
0answers
135 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
384 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
485 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 ...
25
votes
1answer
778 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
185 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 ...
17
votes
6answers
824 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
320 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
183 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
88 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 ...
8
votes
1answer
263 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
135 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
201 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' ...
23
votes
10answers
1k 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
216 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
929 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
925 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
408 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?
...
27
votes
10answers
4k 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
306 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, ...
12
votes
2answers
526 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 ...
24
votes
18answers
3k 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 ...
5
votes
1answer
855 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 ...
8
votes
4answers
469 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
399 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
617 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 ...
39
votes
5answers
749 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 ...
55
votes
12answers
3k 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 ...
22
votes
3answers
591 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
529 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 ...
62
votes
2answers
4k 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 ...
22
votes
5answers
1k 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
245 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 ...
25
votes
15answers
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, ...
33
votes
15answers
2k 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, ...
17
votes
1answer
592 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 ...
21
votes
15answers
1k 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 ...
56
votes
34answers
3k 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 ...
10
votes
2answers
217 views
Exhibits for a Museum of Computing
All of the computer-related museums and exhibits I'm aware of seem to only cover the history of computing machinery, but nothing on topics of computer science.
You are involved in the creation of a ...
17
votes
1answer
1k views
Major mistakes in accepted FOCS/STOC papers [closed]
Have you come across an occasion like that in the past? Well, there is a possibility for everything but I would like to know how realistic this incidence can be. I am referring to serious mistakes ...
27
votes
3answers
586 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 ...
24
votes
12answers
2k 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 ...
34
votes
15answers
3k views
Conjectures implying Four Color Theorem
Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are ...
11
votes
3answers
547 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 ...
10
votes
4answers
410 views
Constructions better than a random one.
I am interested in examples of constructions in the complexity theory which are better than a random constructions.
The only one example of such construction which I know is in the field of ...
5
votes
1answer
348 views
Simple Constructions of Special Graph Families
Consider the following definition, taken from Chung's 1978 paper:
An $(n, m)$-concentrator is a graph with $n$ input vertices and $m$ output vertices,
$n \ge m$, having the property that, for ...
3
votes
1answer
698 views
Website with TCS Fun Facts
This interesting paper http://www.math.hmc.edu/~su/papers.dir/leitzel.pdf is about how to motivate students during a course.
One of the idea is to add some "fun facts" during the course for some ...
3
votes
3answers
344 views
What are the most known database disk storage layout algorithms?
I can list for example algorithms used in databases:
append only b-trees (MVCC like used in CouchDB)
merged logs (like used in Big Table, Hbase, Cassandra)
paged storages grouped in extents (like in ...
5
votes
6answers
4k views
Application of graph theory in Computer Science
i am a CS student, we did graph theory in class and i found it interesting. i wanted to know what the real applications of graph theory in the computer science field. For an example i found that some ...
