New answers tagged

0

split every vertex $v$ into $v'$ and $v''$ and connect $v'$ to the incoming arcs and to $v''$, connect $v''$ to the outgoing arcs of $v$; set the flow constraints for $(v',v'')$ to $[0,a_v]$. If all other flow constraints are $[0,1]$ then, because of the integrality of the mincost flow problem the constraints on the number of active arcs will be met.


2

The triviality problem (input: a finite group presentation of a group $G$, output: yes/no according to whether $G$ is a trivial group) is not solvable by an algorithm. Indeed just apply the Adian-Rabin theorem to the property "being trivial". Now we deduce the general case of your question as follows: Suppose by contradiction that you have an ...


4

The function $f(x)$ is closely related to the notion of autocorrelation, which for a binary sequence $x$ of length $|x|=N$ and shift $w$ can be expressed as $$\textbf{AC}_x(w) := N - 2H(x\oplus R(x,w)).$$ The values of $\textbf{AC}_x(w)$ for various non-trivial shifts (i.e. $1\leq w\leq N-1$) are called out-of-phase autocorrelation values. So, $$f(x) = \min_{...


-2

Suppose x contains n 1’s, and y is a cyclic shift of x. Suppose that there are exactly m positions where both x and y have 1’s. Then x XOR y has 2(n-m) 1’s. Thus f(x) is always even. Thus a necessary condition for H(x) = f(x) = n is that n is even. Consider the length 4 sequence x = 0110. The cyclic shifts are x_1=1100, and x_2=1001, and x_3 = 0011, so that ...


7

Adding to Sean Lawton's answer, there was an arxiv posting yesterday by Davies-Juhász-Lackenby-Tomasev, The signature and cusp geometry of hyperbolic knots that describes a relation between the cusp geometry of a hyperbolic knot, its signature, and its hyperbolic volume. The authors describe how this was found via machine learning. This is not exactly what ...


8

I saw two articles today (12/2/21) that reminded me of this post. I am mentioning them here to potentially help the OP: Learning knot invariants across dimensions by Jessica Craven, Mark Hughes, Vishnu Jejjala, Arjun Kar (on arXiv) DeepMind’s AI helps untangle the mathematics of knots, by Davide Castelvecchi (on nature.com).


2

One can also completely break this key exchange (and a more general key exchange algorithm) using linear algebra. Consider the following key exchange algorithm. Suppose that $\mathcal{A}_{L},\mathcal{B}_{L}$ are sets of $m\times m$-matrices and $\mathcal{A}_{R},\mathcal{B}_{R}$ are sets of $n\times n$-matrices. Let $C$ be a publicly available $m\times n$-...


0

pyMCFSimplex seems to best fit my needs. "It is a free Python port of a Python Wrapper for MCFSimplex. pyMCFimplex is a Python-Wrapper for the C++ MCFSimplex Solver Class from the Operations Research Group at the University of Pisa. MCFSimplex is a piece of software hat solves big sized Minimum Cost Flow Problems very fast through the (primal or dual) ...


4

This protocol as it is stated is broken using a quotient attack. I am going to explain this technique in as general of a context that I can (this idea should also break generalizations of this protocol). Suppose that $X$ is a set. Let $G,H$ be monoids that act on $X$. Here $G$ acts on $X$ on the left so that $gx\in X$ whenever $g\in G,x\in X$, and $H$ acts ...


4

You may want to take a look at this article . The article is both entertaining and well written, and here are its core ideas: KNOTS AS WORDS IN A LANGUAGE First core idea is to leverage the representation of knots as phrases in a suitable language. This is the cool part of the article, and actually a good recap of the fundamentals of Knot Theory, so I ...


2

The answer is false. Let $G$ be the 3-prism and $\varphi$ the coloring shown below. $G$ cannot have a 2-distance vertex 4-coloring. As all pairs of vertices in $G$ have distance either 1 or 2, a 2-distance coloring of $G$ would require 6 colors.


6

Here is a section on graph theory in A compendium of NP optimization problems by P. Crescenzi and V. Kann.


10

A site dedicated to graph classes, including the computational complexity of associated problems, is https://www.graphclasses.org


7

https://en.wikipedia.org/wiki/List_of_NP-complete_problems $$ \quad\quad\quad\quad\quad\quad\quad\quad $$


Top 50 recent answers are included