# Tag Info

4

The following paper proves an exponential separation of perceptrons of depth $d$ versus depth $d+1$. A perceptron is a circuit with a single threshold gate at the top, and unbouded fan-in boolean circuits as its inputs: Christer Berg, Staffan Ulfberg: A Lower Bound for Perceptrons and an Oracle Separation of the $\mathsf{PP}^{\mathsf{PH}}$ Hierarchy. J. ...

5

Literally stated, the problem of exponentially separating neural nets of depth d from depth d-1, for all d, is open, to the best of my knowledge. When your "activation functions" are linear threshold functions for example, it is open whether all nets of all depths d can be simulated, with a polynomial increase in size, in depth 3.

8

The paper that people usually cite is Almost Optimal Lower Bounds for Small Depth Circuits, which appears in STOC 1986. The main result pertaining to your question is: There exists a family of functions admitting linear size, depth $k$ circuits (of unbounded fan-in AND/OR and NOT) that requires exponential size at depth $k-1$. What's possible even ...

6

Bollobas showed that for any $d$ and any $g$, there exists a $d$-regular graph $G$ of girth at least $g$ such that $$\alpha(G) < \frac{2n\log d}{d}.$$ So you cannot hope for more than a factor 16 improvement. McKay gave somewhat sharper bounds.

7

Upon request of Marzio De Biasi I'm converting my comment into an answer. A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open: 1) Is isomorphism of asymmetric graphs in P? 2) Can ...

-3

there are many old SAT search, variable ordering, backtracking etc heuristics that can be regarded as verging on learning algorithms and many are applicable/generalizable to CSPs, and exact boundaries here may be blurring. possibly these have generally traditionally been two different fields, machine learning and constraint satisfaction, but with increasing ...

7

One family of results not mentioned in the excellent references of @Marzio's answer is relations between the isoperimetric (Dehn) function of a group $G$ and the nondeterministic time complexity of the word problem in $G$. For example: For finitely generated groups $G$, $WP(G) \in \mathsf{NP}$ if and only if $G$ can be embedded in a finitely presented ...

3

Via Rubin: There is a sequence of polytopes $\{ P_k\}_k$ each defined by two variables and one constraint (plus two nonnegativity constraints) such that the integer hull of $P_k$ has $k+3$ vertices and $k+3$ facets. $P_k=\{ (x,y)\in \mathbb{R}^2_+ ~|~f_{2k} x + f_{2k+1}y \le f^2_{2k+1}-1\}$ Here, $f_j$ is the $j$-th Fibonacci number. This shows that the ...

7

I think that you can start (and probably end, because it's a huge list :-) with the references in the recent Charles F. Miller's paper: "Turing machines to word problems" (2013). And another recent paper that surveys the connections between group theory and theory of automata and formal languages and hase a huge (>100 entries) reference section is: Tullio ...

5

You are probably looking for this paper: Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003. doi:10.1016/S0304-3975(03)00342-6 In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms. This includes CSPs as a special case of ...

4

Maybe I am mistaken but I think it is possible to make the example from http://math.stackexchange.com/a/78835/131224 Eulerian. Just take an octahedron and place 3 new vertices on each of its faces, connected to each other and also to two of the vertices of the face in a circular order. So if the face was $abc$, then add $def$ and connect $d$ to all but $a$, ...

16

[Following a suggestion of Kaveh, I am putting my (somewhat extended) comment as an answer] This "conjecture" of Kolmogorov is just a rumor. It was of course nowhere published or so. In the former USSR, "publishing" mathematics meant something different: make a talk at a seminar or tell your colleagues at lunch. Counting papers was not an issue. (Actually, ...

7

The main thing missing from your list is the beautiful 2006 paper of Klivans and Sherstov. They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.

5

Depth-2 TC0 probably can't be PAC learned in subexponential time over the uniform distribution with a random oracle access. I don't know of a reference for this, but here's my reasoning: We know that parity is only barely learnable, in the sense that the class of parity functions is learnable in itself, but once you do just about anything to it (such as ...

1

This question has been open for long now, and after some research I think I have the following answer There has been two candidate schemes proposed for multilinear pairing by Garg, Gentry, Halevi and Coron, Lepoint, Tibouchi. However either do not have a security proof and their security is given by extensive cryptanalysis. So, to sum it up, although it ...

5

I think you can make the classical local ratio algorithm by Bafna et al. give a $2-o(1)$ approximation on the following family of graphs: Take $G_n$ to be a $K_{n,n}$ (the complete bipertite graph with $n$ vertices on each side), and then delete a single edge. The following shows that the algorithm might output all of the "blue" vertices ($2n-4$ in number) ...

5

It's well-known you can present computation history of a Turing machine as an intersection of two CFLs. Take a deterministic Turing machine $M$ and force it to reject everything except possibly the empty word. The set of computation histories is either empty (if $M$ rejects the empty word), or a singleton (if there's an accepting computation for the empty ...

9

The $k$-disjoint path problem for fixed $k$. Given an undirected graph $G$ and $k$ node pairs $s_1t_1,s_2t_2,\ldots,s_kt_k$, are there node-disjoint paths in $G$ connecting the pairs? Polynomial-time algorithm follows from the work of Robertson and Seymour and relies on very non-trivial and difficult graph theoretic results. There are more general problems ...

4

There are some interesting problems in combinatorial optimization whose membership in $\sf{P}$ is quite non-trivial, in particular it often relies on some deep min-max theorem. Some examples are problems involving graphs (non-bipartite matching, maximum flow, and some of their extensions), posets (max antichain, max union of $k$ chains, path cover...), or ...

2

From the comment: in the mathematical field of graph theory, the Rado graph [1], also known as the random graph or the Erdős–Rényi graph, is the unique (up to isomorphism) countable graph $R$ such that for every finite graph $G$ and every vertex $v$ of $G$, every embedding of $G − v$ as an induced subgraph of $R$ can be extended to an embedding of $G$ into ...

9

Testing perfect graphs. Famous people (Lovasz, Knuth, ...) conjectured in the 1980s that there is a polynomial time recognition for perfect graphs. Such an algorithm was found after almost 20 years later by famous people ( Cornuéjols and other, FOCS 2003).

5

Convex Optimization is another relatively recent one. Edit: I suppose more specifically, Semidefinite Programming is a subfield of convex optimization that has been used in some breakthroughs in complexity theory recently. Edit edit: This question seemed to cover this point in a little more detail.

12

The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.

2

You can perform universal computation using zero forcing: a simple, repeated transformation of (improper) 2-colourings of vertices. Starting from an initial configuration in which most vertices are coloured white, except for some black "input" vertices, you repeatedly change the colour of any vertex with exactly one white neighbour to black. Logic gates are ...

2

Ok, let me try to answer this myself: I was looking for a reference, not a proof. My hope was that it is in fact a two-line proof, and that I was just missing that. This seems to be true. The people who saw it, never wrote it up; everybody else just repeated the fact, without seeing the proof, I guess. You can use reduction from any problem that can be ...

2

I believe you could also reduce from bin-packing which is strongly NP-complete according to wikipedia. Consider this instance of MD-KS: $$\max \sum_{i = 1, j = 1}^{n, m} x_{i,j} \\ s.t.: \sum_{j} x_{i,j} \le 1 \\ \;\;\;\;\;\;\;\; \sum_{i} a_{i} x_{i,j} \le b \\ \;\;\;\;\;\;\;x_{i, j} \in \{0, 1 \}$$ The optimization problem above finds the maximum number ...

3

A possible reduction is from Exact Cover by Three Sets (X3C) (which is strongly NP-hard): Instance: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F_i = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}, i=1,...,m$ of 3-elements subsets of $X$ (triples); Question: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of ...

11

Comparing two programming languages is difficult is a difficult problem, and far from being solved. The key issue is that there are many different ways languages can be compared, and none of them is compelling. The most widely used approach, coming from logic, is to consider translations between the languages to be compared. The general idea is as ...

4

My answer to the question is that I don't know of published work. However, I've recently been thinking a bit about formalizing what I believe is essentially your question, so I'll try to collect some thoughts in the following "extended comment", hoping that it will be interesting, useful, or spark productive discussion! (Maybe this is already well-known or ...

4

Only an extended comment: I only heard about it (and I know almost nothing about it :), but there is a computational model based on Graph Rewriting From Wikipedia: "... The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules ...

1

Following vzn's comment, you can define a straightforward extension of TMs using graph products. Define a "graph machine" as a tuple $M = (S,T)$ where $S$ is a sets of states, and $T$ is a binary relation over $S \times S$. Fix a graph family $\cal{G}$, and consider the following problem: given a graph $G \in \cal{G}$ and two $S$-labelings $L_1,L_2$ of $G$, ...

4

As in my comment, the configuration graph (Chapter 4.1.1. of Arora-Barak) is a simple way to view a Nondeterministic Turing Machine (NTM) as a graph. The vertices of the graph are labeled by configurations: the internal state of the NTM, the contents of the tape, and head positions. There is a directed edge from vertex $c_1$ to vertex $c_2$ if the NTM can ...

6

More generally, you can consider the identity $$f(g(x)) = g^{(n)}(x),$$ which generalizes your identities, in which $n=3,1,2$ (respectively). For a given function $g$, this identity states that $f$ needs to have given values on $\operatorname{ran} g$, and is free otherwise. The specific value of $n$ doesn't matter, in fact we can put whatever we want on ...

6

Seemingly the earliest characterization of the graphs in which every minimal separator is an independent set appeared in T. A. McKee, "Independent separator graphs," Utilitas Mathematica 73 (2007) 217--224. These are precisely the graphs in which no cycle has a unique chord (or, equivalently, in which, in every cycle, every chord has a crossing chord).

0

Foundations of Data Science by John Hopcroft and Ravindran Kannan. It's an amazing book on Algorithms for Big Data Analytics. They call it the 21st century algorithms.

8

APX-Hardness implies that there is a $\delta > 0$ such that the problem does not admit a $(1+\delta)$-approximation unless $P=NP$. Clearly this rules out a PTAS (assuming $P \neq NP$). As for QPTAS, it will rule it out unless you believe that NP is contained in quasi-polynomial time. As far as I know, that is the only reason why APX-Hardness rules out a ...

Top 50 recent answers are included