## New answers tagged algorithms

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

#### Related Tags

algorithms × 1376graph-theory × 304

co.combinatorics × 285

computational-complexity × 207

nt.number-theory × 186

linear-algebra × 110

computer-science × 82

reference-request × 70

mg.metric-geometry × 70

gr.group-theory × 69

pr.probability × 62

computational-geometry × 58

ag.algebraic-geometry × 51

computational-number-theory × 49

approximation-algorithms × 49

combinatorial-optimization × 46

polynomials × 45

na.numerical-analysis × 44

matrices × 42

discrete-geometry × 42

oc.optimization-and-control × 38

prime-numbers × 36

ac.commutative-algebra × 34

linear-programming × 34

graph-colorings × 27