The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
46 views

Important papers in representation of Boolean functions

What are some of the important papers in the field of polynomial representation/approximation of Boolean functions? One such seem to be http://dl.acm.org/citation.cfm?id=129757
2
votes
1answer
82 views

Applications of algebraic geometry in Boolean complexity

Representing boolean functions by polynomials or rational functions either perfectly or approximately is an important topic while polynomials and rational functions is the body of algebraic geometry. ...
9
votes
4answers
139 views

Applications of $p$-adic numbers in CS

Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?
1
vote
1answer
173 views

What's the relation between OOP and category theory?

What's the relation between OOP and category theory? Is there some related work on this topic one can read?
4
votes
0answers
219 views

Heuristic algorithm design techniques

I am looking for a good relatively complete and up-to-date book or survey about heuristic algorithm design techniques.
11
votes
7answers
683 views

Handbook of advanced algorithms

I am looking for resources (preferably a handbook) on advanced topics in algorithms (topics beyond what is covered in algorithms textbooks like CLRS and DPV). The type of material that can be used ...
11
votes
1answer
175 views

A survey on separators?

There are by now mountains of results on separators in graphs, from planar separator, tree separator, bounded tree width graphs, bounded genus graphs, etc, etc, etc. Is there any good updated survey ...
3
votes
1answer
206 views

Surveys on Algorithmic Problems in Coding Theory

Coding Theory has many algorithmic problems that enriched theoretical computer science. I want to learn specifically the connection between coding theory and the hardness of computational problems. ...
8
votes
1answer
279 views

Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

I read the famous book by Alon and Spencer on the probabilistic method in combinatorics. Is there a survey or lecture notes on recent advances and relationships with the following complexity ...
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 ...
23
votes
4answers
2k views

Handbook of advanced data structures

I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms". A book that can be ...
5
votes
0answers
216 views

Detailed Materials on Sunflowers

Jukna's book Extremal Combinatorics explains basic results about sunflowers. Is there a more thorough survey of various sunflower results?
10
votes
2answers
515 views

Introductory resources on Computational Learning Theory

Recently I've been reading a decent number of CoLT papers. Although I don't struggle with the individual papers (at least not more than I usually struggle with other theory papers), I don't feel I ...
9
votes
0answers
153 views

Algorithms on graphs represented using BDDs

The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong ...
14
votes
1answer
942 views

Sufficient conditions for the regularity of a context-free language

It would be nice to collect a list of conditions that imply that a context-free language L is regular, i.e. conditions of the form: "if a given CFG/PDA has property P, then its languages is regular" ...
0
votes
1answer
137 views

Functions and Counting Problems in Streaming Computation

I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08(Paul Beame and Trinh Huynh. On the ...
15
votes
4answers
525 views

Automated theorem proving in linear logic

Is automatic theorem proving and proof searching easier in linear and other propositional substructural logics which lack contraction? Where can I read more about automatic theorem proving in these ...
11
votes
0answers
251 views

Survey on infinite alphabet automata?

The paper "Symbolic Finite State Transducers, Algorithms and Applications" by Bjorner et al (to appear at POPL 2012) describes one type of finite-state, infinite-alphabet automata/transducers by using ...
10
votes
3answers
305 views

Introductory notes on parallelization, in particular patterns of problems and algorithms

I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science. My focus is ...
20
votes
4answers
553 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 ...
15
votes
2answers
1k views

Computational complexity in quantitative finance

Predicting the stock market is hard! Can TCS make this sentiment more formal? Recently I have started thinking a little bit about finance, and was wondering how knowledge of TCS could help. Hedge ...
9
votes
4answers
568 views

Surveys on Network Coding

I want to start learning about Network Coding: http://en.wikipedia.org/wiki/Network_coding Do you know any good survey (e.g. from IEEE Surveys and Tutorials) on the above subjects. I found some ...
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, ...
11
votes
2answers
446 views

Is there a survey of the semantics of various programming language features?

Is there a survey (from paper, book chapter, tutorial, links, ...) of the semantics of various programming language features? I was originally overwhelmed by the features of D in here ...
2
votes
1answer
502 views

Survey on Optimization algorithms

I am trying to solve an optimization problem. I need some help in getting the results or survey on related issues. The question is a bit general but any help in identifying the correct sources would ...
5
votes
2answers
400 views

Is there any good and free Introduction to topological graph theory

My knowledge in topological graph theory is in low, I need some good reference which has two simple thing, Definition of new concepts (like genus,graph embedding in surface, ...) also contains related ...
9
votes
1answer
287 views

Holographic Algorithms - Equivalence of Bases

I was going through Les Valiant's seminal paper and I had a tough time with Proposition 4.3 on page 10 of the paper. I cannot see why is it the case that if there is a generator with certain values ...
8
votes
2answers
551 views

Is there a list of known problems?

Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us? [If not, can we make one? I know this is off ...
8
votes
2answers
313 views

Information on k-SAT (Introduction, Bounds, Methods, etc.)

I'd like to know where I can turn for a good, gentle introduction to k-SAT (this may be for mathematicians that may not have a good computer science background). I'd also like to know papers that ...
10
votes
10answers
948 views

Resources to learn about the P vs. NP problem

I was recently reminded about the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as explained by Stephen A. Cook on Clay Mathematics Institute. It has piqued my interest and I would like to learn more about ...
42
votes
14answers
4k views

Applications of topology to computer science

I'd like to write a survey on the applications of Topology in Computer Science. I plan to cover the history of topological ideas in Computer Science and also highlight a few current developments. It ...
46
votes
14answers
1k views

Where and how did computers help prove a theorem?

The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful in building a conjecture that lead to a theorem, falsifying a ...