# Tag Info

6

For an extreme example, chordal graphs can have as many as $\binom{n}{2}$ edges but chordal graphs that happen to also be bipartite can have only $n-1$ edges (they are forests). Or even more extremely, consider complete graphs versus (complete $\cap$ bipartite) graphs. But perhaps it makes sense to restrict your problem only to classes of graphs that are ...

7

A version of Tucker's algorithm was used in B. Awerbuch, A. Israeli, and Y. Shiloach, Finding Euler Circuits in Logarithmic Parallel Time, STOC 1984, to find Euler tours efficiently in parallel, and similar ideas can be used to make the algorithm run sequentially in linear time. Suppose you have a connected graph $G$ in which all vertices have even degree, ...

1

It can be done on $O(|E|\log |E|)$, nevertheless implementing it might be cumbersome. I won't get into details of how implement, but a general overview so we can analyze its running time: For this we will need and adjacency list instead of an adjacency matrix. Step 1.-, for each vertex split away the vertices, you can split away all the edges for each ...

3

In the paper titled "ON MULTIDIMENSIONAL PACKING PROBLEMS" that appeared in SODA and then in SICOMP (http://epubs.siam.org/doi/abs/10.1137/S0097539799356265) we considered several packing problems where items are d-dimensional vectors. We discuss PIPs which are the same as as multidimensional knapsack (we mention this) and their approximability when d is not ...

1

The Knapsack Problems text by Kellerer et al. cites the two references below as proving that multidimensional knapsack is strongly NP-hard already in the special case of CARDINALITY 2-KP (two-dimensional, with unit values). It also reproduces a proof, reducing from EQUIPARTITION, i.e., the existence of an FPTAS for CARDINALITY 2-KP implies that the ...

8

The question is usually taken to be moot, for the following reason. Grover's algorithm is a combinatorial search algorithm to find a solution to an arbitrary predicate. While, yes, $\Theta(\log N)$ is the quantum gate complexity in each stage of the black-box algorithm, the predicate needs to be computed too. The quantum gate complexity of that is ...

-1

See Venema, Yde. Temporal Logic. The blackwell guide to Philosophical Logic.

2

Another example is the classical work of Coppersmith and Winorgrad from 1990 on matrix multiplication, which is based on additive combinatorics http://www.sciencedirect.com/science/article/pii/S0747717108800132

1

Computability theory in general has been somewhat under-formalized. The short answer is that most theorems of computability theory do not pass one of the three tests for formalization: A proof that is computationally intensive or untrusted for some reason (long, complex). A result that is relevant to undergraduate mathematics. A result that is useful to ...

11

One interesting question about complexity classes over a unary alphabet that is not in the above references is the strength of Valiant's class #P1, the class of counting problems over a unary alphabet (see http://epubs.siam.org/doi/abs/10.1137/0208032). Not much is known about its power, though it has natural complete problems and, like unary languages, has ...

22

There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk. Giovanni Pighizzini, Investigations on Automata and Languages over a Unary Alphabet, CIAA 2014. doi:10.1007/978-3-319-08846-4_3

6

In a recent article, Hüffner, Komusiewicz, and Nichterlein refer to this class as sparse split graphs. They also refer to the complement class, the complete split graphs, as dense split graphs. Hüffner, Komusiewicz, and Nichterlein. "Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes."

7

To say a bit more about Geometric Complexity Theory (GCT): this is the application of algebraic geometry and representation theory towards a long-term program to resolve P versus NP. The questions raised in GCT tend to be deep mathematical questions, some of which go back over 100 years to the pioneers of algebraic geometry and representation theory - ...

8

The edge-complement of graphs in your class are complete split graphs: they can be partitioned into an independent set and a clique, such that every vertex in the independent set is adjacent to every vertex in the clique (see, for example, http://www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Hence you could call your graph class co-complete split ...

1

We explored the Runtime-Accuracy tradeoff in the context of nearest neighbors in a 2010 COLT paper [journal version]: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6867374 Roughly speaking, your dataset has margin $\gamma$ if every pair of opposite-labaled points is at least $\gamma$ apart in distance. You can also impose a desired margin by counting ...

6

Modern research in automata theory (in a broad sense) is an interesting case. It relies on a lot of mathematics, but not necessarily the kind of mathematics you would learn in standard courses in mathematics. A very loose explanation might be that in computer science, the fundamental object is the Boolean semiring $\mathbb{B}$, while in mathematics, finite ...

6

Geometric complexity theory is extremely "mathematical" and many of its leading investigators are more mathematicians. see eg Geometric Complexity Theory: an introduction for geometers / Landsberg Group theory is being connected to TCS in many deep ways eg in the study of the word problem, isomorphisms, and undecidability. see eg THE WORD PROBLEM AND THE ...

4

Not totally a theoretical CS topic but uses many results from theoretical CS : you may be interested in software verification which goal is to ensure that a program do what it's supposed to do, and nothing else. Among the different techniques in that topic, some are particularly math-oriented. Many critical systems, in avionics/spatial/nuclear notably, have ...

12

Here are three more fields that fit your criteria. Category theory. This is clearly interesting to most pure maths fields, but also has been very influential in the theory of (functional, sequential) programming languages. Logic, particularly proof theory. The connections with computer science are too many to name, but logic is not only a rich field of ...

9

Yes: Graph theory, computational geometry, complexity theory, combinatorics are the things I research on in CS. Vector spaces and measure theory could be useful in theoretical machine learning too. There is a lot more pure maths employed in theoretical CS, but they don't hit the news as often like AI and machine learning, which is why you don't hear about ...

13

The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true as permanent is complete for both VNP and #P. Indeed, the Boolean part of VNP is essentially just #P/poly (it contains #P/poly and is contained in ...

3

The books below may be more to your liking, but in general, the texts/lecture notes are written for the use of (mainly) postgraduate students in engineering and cannot presume deep knowledge of convex analysis. Csizsar, I., and Korner, J., Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd Ed, Cambridge. Berger, T., Rate Distortion ...

Top 50 recent answers are included