21
I think there are lot of similar problems. Here are two in vertex version and one in edge version:
1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set).
This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in
Garey, Johnson & Stockmeyer.
2) Does a given graph have a ...
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
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 ...
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
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
Update (2020)
Have a look at this year's CPPCon talk - Monoids, Monads, and Applicative Functors: Repeated Software Patterns
Also look for mentions of the Fin category in Category Theory in Context
Objects can implement category theoretic data types and access patterns.
For a better understanding I would recommend Stepanov's book , Mike Stay's article, and ...
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 ...
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
...
5
I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written:
Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-11828
The first chapter gives a summary of the problem, known proof techniques and provides references to recent ...
4
Another example is the efficient dominating set problem also known as 1-perfect code in graphs. The problem is to determine the existence of a dominating set $C$ in undirected graph such that the shortest path between any two nodes in the dominating set $C$ is at least 3 (edges). The problem was proven to be $NP$-complete independently by many researchers. ...
answered Nov 19 '13 at 14:38
Mohammad Al-Turkistany
20.3k4 gold badges56 silver badges142 bronze badges
4
An $NP$-complete structural problem is to decide the existence of odd (even) hole in directed graphs. Anna Lubiw proved the $NP$-completeness of the above two problems.
A hole is chordless cycle of length greater than three. A cycle in directed graph is chordless if its length is greater than 3 and no two of its vertices are joined by an
edge of the ...
answered Nov 19 '13 at 3:34
Mohammad Al-Turkistany
20.3k4 gold badges56 silver badges142 bronze badges
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
20.3k4 gold badges56 silver badges142 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
From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper.
Bonfante, ...
3
Elaborating on one of the bullet points mentioned by the OP (GoldreichKNR09): there are several hierarchy theorems in property testing and proofs of proximity, relating to the query complexity, the adaptivity, or the testability with regard to number of rounds (for proofs of proximity). See, e.g.,
Hierarchy Theorems for Property Testing, Oded Goldreich, ...
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
