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 ...
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
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
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.
8
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 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 ...
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
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
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
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
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 ...
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
Bart Jacobs tackled this problem at one point. In his view, classes can be considered as coalgebras. Roughly, we have a polynomial endofunctor $F : \mathbf{Sets} \to \mathbf{Sets}$ which gives the class's type signature. A pair of a carrier set $X$ and an arrow $X \to FX$ is then used to "implement" the class. For example, consider a class representing ...
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
Computational Geometry: Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Cheong. Computational Geometry: Algorithms and Applications; David Mount's Course Notes.
Randomized Algorithms: Motwani and Raghavan. Randomized Algorithms; Excellent Notes by James Aspnes; Mitzenmacher and Upfal. Probability and Computing.
Network Flows: Ahuja, Magnanti, ...
4
Have look at the Encyclopedia of Algorithms by Kao (Editor). It contains over 500 entries and many of them contain advanced algorithms.
answered Nov 5 '13 at 14:23
Mohammad Al-Turkistany
19.9k4 gold badges54 silver badges136 bronze badges
4
I rather liked "Algorithmics for Hard Problems" by Juraj Hromkovic
4
here is a nice general survey with a brief overview of diverse (recent) CS applications for p-adic theory, p3
What are p-Adic Numbers? What are They Used for? / Rozikov
Here are areas where p-adic dynamics proved to be effective: computer science (straight line programs), numerical analysis and simulations (pseudorandom numbers), uniform distribution of ...
3
There are known worst-case hardness results about ML decoding (for general and specific families of codes such as Reed-Solomon), computing or approximating minimum distance of codes, and so on. However there is a great room for improvement in these directions and several seemingly intractable problems are not analyzed yet.
There are coding theoretic ...
Only top voted, non community-wiki answers of a minimum length are eligible
