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.
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
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
There are also some computational models:
Here is the first paper: Rusins Freivalds: Ultrametric automata and Turing machines. Turing-100 2012: 98-112
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
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
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 ...
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.5k4 gold badges57 silver badges144 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.5k4 gold badges57 silver badges144 bronze badges
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, ...
2
Bryant's "Graph-Based Algorithms for Boolean Function Manipulation" introduced Reduced-Order Binary Decision Diagrams (ROBDDs) for representing and manipulating Boolean functions. I believe these see a lot of use in CAD tools and circuit synthesis problems. Bryant's paper is a good place to start a literature review for BDD. He cites a few key earlier ...
2
From SSRN, two papers related to the complexity of portfolio optimization:
Walter Murray, Howard Howan Stephen Shek, A Local Relaxation Method for Cardinality Constrained Portfolio Optimization Problem, October 15, 2011.
Marcos Lopez de Prado, Multi-Period Integer Portfolio Optimization Using a Quantum Annealer, October 6, 2015.
From arXiv:
Dan A. Iancu, ...
1
In functional programming, the most general and elegant abstractions for problems are often algebraic (or category-theoretic) in nature: monoids, semirings, functors, monads, F-algebras, F-coalgebras, etc. Some classic results (e.g., the Yoneda lemma) happen to have computational content and utility.
Also, there is homotopy type theory, which interprets ...
1
Recently, we explore (see our paper on springerlink: A formal series-based unification of the frequent itemset mining approaches) a unification attempt to pattern mining (a popular instance of data mining) approaches by mean of formal series and weighted automata. These tools are based on mappings between monoids and semiring structures.
1
Predicting the stock market is hard! Can TCS make this sentiment more formal?
If stocks are modeled as random variables like geometric Brownian motions then prediction becomes a concern of statisticians, I suppose.
But there is also market psychology. The field known as technical analysis is all about trying to extrapolate from past prices. How hard might ...
1
Archdeacon's survey Topological Graph Theory was almost mentioned already:
http://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf
Only top voted, non community-wiki answers of a minimum length are eligible