44
The short answer: the really minimum knowledge of math to understand the first half of the plan of GCT, once you've seen a little of groups, rings, and fields, is basically laid out in Chapter 3 of my thesis (shameless self plug). That chapter is, however, incomplete, in that I don't get to the representation theory part of things. The representation theory ...
15
Every unary context-free language is regular.
(e.g. a direct consequence of Parikh's theorem)
If every iterative/pumping pair of a context-free language L is
degenerated, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies:
$$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was ...
14
I wish I had a good answer for you. I use Book:Fundamental Data Structures (a collection of relevant Wikipedia articles) for my course on this subject but it's not really a complete textbook (for one thing, it has no exercises). CLRS is, I think, at a good level of detail for this sort of class but is missing too many of the important structures.
13
Rings, modules, and algebraic varieties are used in error correction and, more generally, coding theory.
Specifically, there is an abstract error correcting scheme (algebraic-geometry codes) which generalizes Reed-Solomon codes and Chinese Remainder codes. The scheme is basically to take your messages to come from a ring R and encode it by taking its ...
13
De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers replace the complex numbers used by Fürer. Both algorithms give the best bit-complexity for integer multiplication.
13
Here is what Scott Aaronson has to say on the subject:
What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity measures: the decision-tree complexity of $f$, the certificate complexity of $f$, the randomized query complexity of $f$, the quantum query complexity of $f$, the ...
12
Nobody has yet mentioned directed algebraic topology, which was in fact developed to provide a suitable algebraic topological toolbox for the study of concurrency.
There are also several low dimensional topological approaches to topics in the theory of computation, all fairly new:
Various approaches to fault-tolerant anyonic quantum computation based on ...
11
Assuming that the complexity of the provability problem would satisfy you, the landscape of complexities of substructural logics with and without contraction is somewhat complex. I'll try to survey here what is known for propositional linear logic and propositional logic. The short answer is that contraction sometimes helps (e.g. LLC is decidable, while LL ...
11
There are absolutely some relationships between the semantics and practice of OOP and category theory. This is somewhat unsurprising since both fields attempt to give a principled generic account of structure and behavior in a synthetic manner.
The most apparent work I am aware of is the categorical semantics of UML, which is admittedly different from OOP ...
10
The only advanced data structures book that I'm aware of is the one by Peter Braß (Advanced Data Structures). It's not a bad book, but I'm not convinced that it's truly advanced at the graduate level.
10
Hensel lifting is very closely related to the $p$-adics: it's basically getting a better and better approximation to a $p$-adic number, "better" in the sense of "closer in the $p$-adic valuation. Hensel lifting is used in many algorithms such as factoring polynomials or doing linear algebra over $\mathbb{Z}$ (if I recall correctly Dixon has a paper on the ...
10
I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity.
It's hard to say what areas a new communication complexity researcher should delve into, since easy problems have likely been solved already, and harder problems are hard ;) One suggestion is to take known communication lower ...
9
There is a class $\mathsf{D}$, defined in a 1975 paper by L. Adelman and K. Manders, which is a diophantine analogue of the class $\mathsf{NP}$.
A language $L$ is contained in $\mathsf{D}$ iff there exists a polynomial $P$ such that
$$x \in L \Leftrightarrow \exists y_1, \dots y_n < poly(|x|) \colon ~P(x, y_1,\dots, y_n) = 0.$$
Whether $\mathsf{D}$ equals ...
9
The Handbook of Data Structures and Applications (Chapman & Hall/CRC Computer & Information Science Series) is mostly devoted to elementary data structures, but it also contains a few advanced materials that you may find useful for teaching a graduate level course. Given the huge size (1392 pages), this book may be classified as an encyclopedic ...
8
I'm pretty sure no such book exists.
I drew up an annotated bibliography for my recent course, which was loosely based on Erik's course at MIT. It's definitely incomplete—I covered very few geometric data structures and no text data structures, for example—but you might still find it useful.
7
Algebra (and algebraic geometry) has had a pretty big role to play in cryptography, with elliptic curve groups, (number-theoretic) lattices, and of course $\mathbb{Z}_p$ being the basis for nearly all modern cryptographic work.
7
For some material more recent than Kearns and Vazirani, you could check out Rocco Servedio's lecture notes for Advanced Topics in Computational Learning Theory, or the notes from Sasha Rakhlin's class.
7
Kearns and Vazirani is maybe a bit old, but good introduction.
7
Not exactly the most recent (published in 2001), but the text by Arnold L. Rosenberg, Lenwood S. Heath, "Graph Separators, with Applications" may be a good place to look. The Google book link is provided here:
http://books.google.ca/books/about/Graph_Separators_with_Applications.html?id=7DNKE5ZiNZYC&redir_esc=y
7
For a better understanding I would recommend Stepanov's book , Mike Stay's article, and his more recent blog on Category Theory in Javascript.
Use composition not inheritance.
Use sum types like enums to shrink the state space of your variables.
Use product types (tuples) like std::pair in C++.
If you have a function like A someFunc(A a, B b, C c); the ...
6
I recommend looking at Stasys Jukna's books Extremal Combinatorics and Boolean Function Complexity. For discrepancy and the like, you can look at Bernard Chazelle's book The Discrepancy Method (available online at his homepage).
6
The Design of Approximation Algorithms by Williamson & Shmoys (http://www.designofapproxalgs.com/) is a great book for many approximation methods such as greedy algorithms, semidefinite programming, etc. Also, it covers some topics within complexity that are closely related to approximation algorithms (inapproximability, Unique Games-based hardness of ...
6
There are also some computational models:
Here is the first paper: Rusins Freivalds: Ultrametric automata and Turing machines. Turing-100 2012: 98-112
6
In addition to the Geometric Complexity Theory Program already mentioned by Sasho Nikolov (see e.g. here, and - shameless self plug, but has tons of references on uses of AG in complexity - here), there's also:
Work on matrix multiplication (Strassen's work especially come to mind, as well as the more recent GCT-style work of Burgisser and Ikenmeyer, but ...
6
Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger).
Razborov's 2011 introductory survey lists four open problems, two of which are also in the KN textbook:
(KN 2.10) Is it true that $D(f) \le O(\log \chi(f))$?
Here $\chi(f)$ is the ...
5
The theory of regular languages of infinite trees gave rise to several hierarchies, that are currently studied, with many questions that are still open.
When using automata on infinite trees, the parity condition (or Mostowski condition) is of special interest, because non-deterministic parity automata can express all regular languages of ininite trees, and ...
5
You may find of interest the following recent handbooks.
The range of topics covered goes well beyond CLRS, and the material is well suited for graduate and Ph.D. students, even though you may choose a few selected topics for advanced undergraduate students.
Algorithms and Theory of
Computation Handbook Second Edition (Special Topics and Techniques)
...
5
As I understand it, the original motivation was to study CREW PRAM (consecutive read exclusive write parallel RAM) model. In this model, several processors compute a function with shared memory access, but with no write conflicts. Stephen Cook and Cynthia Dwork and Rudiger Reischuk ("A lower time-bound for parallel random access machines without simultaneous
...
4
Here is a new hierarchy for context-free languages by Tomoyuki Yamakami.
He introduces an oracle mechanism in nondeterministic pushdown automata and notions of Turing and many-one reducibilities. Then a new hierarchy is constructed for Context-free languages (CFL) similar to the polynomial hierarchy. For example, $CFL$, $CFL^{CFL}$, etc. The interesting ...
4
I rather liked "Algorithmics for Hard Problems" by Juraj Hromkovic
Only top voted, non community-wiki answers of a minimum length are eligible
