# Tag Info

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