The purpose of this group is to provide a forum for studying and discussing theoretical computer science. The material will typically be at an upper-division undergraduate level, although this may vary with the interests of the group members. Interaction can be in the form of adhoc posts and responses on any relevant topic. Possible areas of discussion might include (but are not limited to):
formal languages and automata
computability
complexity theory
distributed computing
Kolmogorov complexity
mathematical logic
recursion theory
graph theory
neural networks
quantum computing
etc...
Membership Approval
Unfortunately—due to spam—comp-sci-theory now requires membership approval. In order to distinguish legitimate computer science enthusiasts from spammers, you must write a little bit of information about yourself when you apply. For example, you could write your reasons for wanting to join the group, or what you would like to get out of this list, or some of your personal topics of interest, etc... Users who do not write anything will be automatically rejected. Unfortunately this is the only way we can keep the group spam-free.
Please note that there are no formal prerequisites for being in this group. You need only have an interest in computer science (and NOT be a spammer). :)
Hi all, As most of you may already know, it was proved by Reingold that undirected st-connectivity is in log space. The proof uses the zig-zag product of