texts: Small area containing large amount of patterns

texts:
The problem:

I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times q}$ satisfying

1) $1 \leq p,q \leq m$

2) $A(1,1) = A(p,q) = 1$ and $A(i,j) = 0$ otherwise.

I want to find the smallest $n$ and an $(0,1)$-matrix $B_{n\times n}$ so that $B$ contains every matrix in $\mathcal{M}$. We define that $B$ contains a matrix $A$ if and only if there exists $1 \leq i,j \leq n$ so that $A_{p \times q} = B(\{i,\dots,i+p-1\}, \{j,\dots,j+q-1\})$. Informally speaking, we want the template $B$ contains every patterns in $\mathcal{M}$.

The problem looks like a 2D extension of the shortest superstring problem. However, the patterns are very restricted.

The questions:

1) Is this problem NP-hard or not?

2) Could we come up with an approximation algorithm with performance guarantees?

3) If both of questions one and two are hard to answer, what are good heuristics for designing the template $B$?

4) Suppose $\mathcal{M}$ is a given set of matrices without constraints, can we still solve it with an approximation algorithm?


texts: On finding a chain decomposition of a Partial Order

texts:
I am reading a paper by Daskalakis et al. entitled "Sorting and Selection in Posets". http://arxiv.org/abs/0707.1532

In that paper it is presented an enhancement to the algorithm Poset-BinInsertionSort by Faigle & Turan (Figure 1 in the paper) for the reconstruction of a partial order when we are allowed to invoke an oracle telling us if two elements are related or not. The enhancement consists in replacing a step of the previous algorithm with a less expensive step (Figure 2: the EntropySort algorithm).

Now, here's the question. The complexity, in terms of number of queries to the oracle, of the Feigle & Turan algorithm is $O(wn \log n)$ for a poset of width $w$ made up of $n$ elements. (For definitions please see the paper's introduction)

Algorithm in Figure 1 proceeds by incrementally adding one element at a time and in step 4.c it asks for finding a chain decomposition of the set of elements considered so far. I'm struggling with this point because, even if we keep the chain decomposition up-to-dated I am not able to reduce the number of queries to $O(\log n)$ as it would have been requested to keep the complexity of $O(n \log n + wn)$ as claimed in theorem 6 of the paper.

  In brief, here's the question. Suppose you are given a Poset $P=(A,R)$
  of width w (i.e. the cardinality of the largest antichain is w)
  suppose you have $A^\prime \subseteq A$. Is it possible to build a
  decomposition of size $q \leq w$ in time $O(\log n)$ queries as
  requested by the algorithm in the paper?

Thanks in advance.
f


texts: Non-uniform hierarchy theorem for approximating functions

texts:
It is easy to show (by probabilistic argument) that there exist functions that require circuits of size $O(2^n/n)$. This, in turn, can be used to prove a non-deterministic hierarchy theorem showing (roughly) that if $2^n/n > T(n) \gg t(n)$ then there exist functions that can be computed by circuits of size $T$ but not by circuits of size $t$.

What is known if we are instead interested in approximating functions rather than computing them exactly? This question can be asked in many ways, but for concreteness let us say that $f \in approxSIZE(t)$ if there is a circuit family of size $t$ that (for each input length) computes $f$ correctly 3/4 of the time. What can be said about existence of hard functions here? What kind of hierarchy theorem is known? Does the answer change if we require the circuits to compute $f$ correctly $1-1/n$ of the time?

Note (added after Ryan Williams's answer): In fact, the answer to my first question follows from a simple modification of Shannon's lower bound, since a circuit on $n$ input bits can only $\epsilon$-approximate $\sum_{i=0}^{\epsilon \cdot 2^n} {2^n \choose i} < 2^{H(\epsilon) \cdot 2^n}$ functions, where $H$ denotes the binary entropy function. A hierarchy theorem should follow from this in the usual way.


texts: A sorting algorithm that uses the minimum comparasions possible

texts:
I'm looking for a sorting algorithm that minimizes comparisons instead of time complexity.
The algorithm shouldn't compare any two elements for which the relation between them can be derived from comparisons previously made. For example, given three elements $A$, $B$, and $C$ such that $A<B<C$, the algorithm shouldn't attempt to compare $A$ to $C$ if it already compared $A$ to $B$ and $B$ to $C$. (Of course, if the algorithm compared $A$ to $B$ and then $A$ to $C$, it would then also need to compare $B$ to $C$. That's okay.)
Since sorting algorithms have been studied for decades, I'm guessing there already exists an algorithm for this.
My use case is allowing a user to sort things by preference by showing two of those things side-by-side.


texts: Estimating the cardinality of multisets given some sets of different sizes

texts:
The count-distinct problem is: given a stream of elements $x_1, \dots, x_n$ which contains duplicates, find the number of distinct elements using a small amount of space.
I also want the following property: given two or more streams $S_1, \dots, S_k$ we see the streams one after the other. After we see the streams, we are given two streams at random $S_i$ and $S_j$ and asked to return the number of unique elements in $S_i \setminus S_j$. We would like to solve this problem using as small amount of memory as possible; notably we cannot afford to remember all the elements in all the streams before the query of $S_i \setminus S_j$.
This problem can be solved using the HyperLogLog algorithm. However, this algorithm really only works when $|S_i|$ for all $i$ are about the same length. This is because the error probability is given by $O(1/\sqrt{m})$ where $m$ is the amount of memory used to store the hash values of the HyperLogLog algorithm. Suppose we care about small space $m = \log(n)$ where $n = \max_{S_i} (|S_i|)$. Then, suppose the query asks for $S_i$ and $S_j$ where $|S_i| < (1/\sqrt{\log n}) |S_j|$. In this case, we would not achieve a good error bound on $|S_i \setminus S_j|$ (by the inclusion-exclusion principle $|S_i \setminus S_j| = |S_i \cup S_j| - |S_j|$) since the error bound on $S_j$ could mask the number of elements in $S_i$.
Are there any other existing data structures that can handle this when the sizes of $S_i$ differ by more than a $(1/\sqrt{m})$-factor? Please do comment if any part of this question is unclear.


texts: How are these statements about CTT reconcilable?

texts:
From http://www.scholarpedia.org/article/Computational_type_theory#Judgements_and_Propositions:

  The other kind of logical claim made in CTT is the judgment that a belongs to A. This can be reduced to the equality claim by writing a=a in A.

From http://www.nuprl.org/documents/Constable/naive.pdf:

  It does not make sense to regard a in B as a proposition; for instance, it is not clear what the negation of a in B would mean.

and again, from the same paper:

  Also we can define an empty type, void. $$ void= \{ x:A \space |\space x \neq x \space in \space A \} $$

If $a\space in\space B$ can be written $a=a\space in\space B$, then surely the negation of $a\space in\space B$ is $a\neq a\space in\space B$?


texts:
First of all, to my best understanding, traditionally, if $f$ is a one-way function that maps a length $l$ bit string to another length $l$ bit string (i.e., $f:\{0,1\}^l\rightarrow\{0,1\}^l$), then given a length $l$ bit string $x$ that is chosen uniformly at random from $\{0,1\}^l$, the probability that an adversary can invert it in poly time is at most $o(1/poly(l))$. (Notice, it is small $o$, not big $O$.)

Now, further assume $f$ is a one-way permutation, that is, $f$ is bijective. Hence, according to discussion in first paragraph, I think it's safe to say:

$$\forall x\in_{\mathcal{u}}: \mathbb{P}(A(f(x))=x)<1/poly(n)$$

where $A$ is the adversary.

In fact, I'm going to strength our assumption a bit:

$$\forall x\in_{\mathcal{u}}: \mathbb{P}(A(f(x))=x)\leq 1/2^l$$

Now, my question is, under above assumption, we give Eve a length $l$ string $x$ that is chosen uniformly at random, what is the probability that Eve found another string $y$ such that $f(y)$ and $f(x)$ has, say $l/4$ bits are the same?

More formally, let $I=\{i_1,\cdots,i_{|I|}\}$ be a set of non-negative integers (indice), let $L_{I,x}$ be the set of length $l$ bit strings such that:

$$\forall x'\in L_{I,x}: \forall i_j\in I, f(x')[i_j]=f(x)[i_j]$$

where $f(x)[i_j]$ denotes the $i_j$th bit of $f(x)$ (and similar for $f(x')[i_j]$),

and the question is: given $I$, when we choose $f(x)$ uniformly at random from $\{0,1\}^l$, what is the probability that Eve found any $x'$ that is in $L_{I,x}$?

Answers are great, but pointers to existing literature that studies this kind of problem are warmly welcome as well!

Thanks in advance!


texts:
This is not necessarily a research question. Just a question out of curiosity:

I am trying to understand if one can define "irreducible" languages.
As a first guess I call a language L "reducible" if it can be written as
$L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$, otherwise call the language "irreducible". Is it true:

1) If P is irreducible, A,B, C are languages such that $A\cap B = \emptyset$, $P \cap C = \emptyset$ and $A\cdot B = C\cdot P$, then there exists a language $B' \cap P = \emptyset$ such that $B = B'\cdot P$? This would correspond in integers to the lemma of Euklid and would be usefull to prove uniqueness of "factorization".

2) Is it true that every language can be factored in a finite number of irreducible languages?

If someone has a better idea on how to define "irreducible" language, I would like to hear it. (Or is there maybe already a definiton of this, which I am unaware of?)


texts: How much computer science / software experience is needed for a math major to do work in AI?

texts: As a math major who is planning on getting their PhD in mathematics, how much computer science or software engineering experience/education do I need to comfortably do research in AI, i.e., would a computer science minor suffice, or should I just teach myself as I need? And is applied mathematics the best form of math to get a PhD in for AI research?


texts:
Consider this "variant" of linear programming:

Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$;

minimize $\sum a_i x_i$

such that       $\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$

For example:

minimize $0.1 x_1+ 0.2x_2 +0.3x_3+0.4 x_4$

such that  $\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$

What's the complexity of  solving this problem? Can it be reduced to linear programming? Is there any efficient approach? Or is there any deep theory behind this problem?

Many thanks.


texts: Is there a difference between incompleteness and unknowable?

texts: Godel proved that there are statements that are true but not provable. Unproven conjectures such "Twin Primes" might fall into such a class, as I understand. If so, does it mean that we will never know if it's true or false? If true would it only be in the sense that some infinitely large and infinitely fast computer determined so by brute force? Or might it be that the conjecture (or another conjecture) could be neither true nor false and instead forever indeterminate?


texts: Where is the quote "Informal proofs are algorithms, formal proofs are code" from?

texts:
Does anyone know the origin of the quote,

  Informal proofs are algorithms; formal proofs are code.

Its made in Benjamin C. Pierce et al.'s Software Foundations.


texts:
My question today is (as usual) a bit silly; but I would request you to kindly consider it.

I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that it is used in FPT algorithms, but I do not think that that was the reason why this notion was defined.

I have written up the scribe notes on this topic in the class of Prof Robin Thomas. I think I understand some of the applications of this concept (as in it transfers separation properties of the tree to the graph decomposed), but for some reason I am not really convinced that the reason this concept was developed was to measure closeness of a graph to a tree.

I will try to make myself more clear (I am not sure if I can, please let me know if the question is not clear). I would like to know if similar notions existed elsewhere in some other branch of mathematics from where this notion was supposedly "borrowed". My guess will be topology -- but owing to my lack of background, I cannot say anything.

The primary reason as to why I am curious about this would be -- the first time I read its definition, I was not sure why and how would anyone conceive of it and to what end. If the question is not still clear I would finally try stating it this way - Let us pretend the notion of treewidth did not exist. What natural questions (or extensions of some mathematical theorems/concepts) to discrete settings will lead one to conceive of a definition (let me use the word involved) as treewidth's.


texts: Cryptography protocols using graph problem instances

texts:
I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances from graph theory are preferred to number theory, when building challenges.

(Side question: is number theory generally preferred because the data is more concise and the primitives might be faster in implementation?)


texts: Existence of solution for a system of multi-variate polynomial equations and in-equations

texts:
Formally, I have 2 finite sets of polynomials :

$P = \{p_1, p_2, p_3, ...p_m\}$ and $Q = \{q_1, q_2, q_3, ...q_n\}$, where for $1 \leq i \leq m$, and $1 \leq j \leq n$, I have $p_i, q_j \in \mathbb{C}[x_1, x_2, \ldots x_k]$ (that is these are multivariate polynomials that can admit roots with possibly complex values for each of the variables) [although the coefficients can be assumed to be over $\mathbb{Z}$ or $\mathbb{Q}$]

What are the most efficient (having running time polynomial in the number of variables, and number of polynomials, but not necessarily the degree) algorithms to check for existence of a solution $\bar{u} = (u_1, \ldots, u_k) \in \mathbb{C}^k$ such that $p_i(u_1, \ldots, u_k) = 0$, and $q_j(u_1, \ldots, u_k)\neq 0$, for all $1 \leq i \leq m$, and $1 \leq j \leq n$.

P.S: For the specific problem I am looking into, the degree (maximum sum of powers of variables in any term) does not exceed 2.That is the polynomials, are in some sense, sparse.

Remark

The set of all such points in $\mathbb{C}^k$ is sometimes referred to as constructible sets, and I understand that an efficient algorithm for calculating GCD of multi-variate polynomials immediately yields an efficient algorithm for solving the above problem. I tried to do a (somewhat extensive) survey for relevant literature, but could not really find efficient algorithms (that run in time polynomial in the number of variables, and the number of polynomials).
Are there any efficient randomized algorithms ?


texts: Is it possible to verify a typechecker for a total dependently-typed language in that language's logic?

texts:
I understand the diagonalization argument against implementing an eval function in a total language, and that typechecking in a dependently typed language requires evaluation, so implementing a typechecker for a total dependently typed language in itself is out. But is it possible to write a typechecker T for total dependently typed language A in (possibly non-total) language B, formalize B in A, and prove the correctness/termination/etc. of T in that formalization (without relying on cheats like including a primitive operation in B that does typechecking)? If not, is it possible to add some (presumably non-computable?) axiom to A that is not included in T and allows the proof to go through without allowing verifying incorrect implementations?

More concretely, suppose I have some formalization of turing machines in Coq and write a turing machine that takes a finite text stream (encoded in some reasonable format) and outputs a 1 if it represents a well-typed Gallina fragment and a 0 otherwise. Could I prove termination and correctness of that turing machine in Coq itself?


texts:
I have a problem in graph theory and search the name and the complexity of the following problem :

Let $G = (V,A)$ be a directed graph, $p : A \rightarrow \mathbb{N}$ be a weight on the arcs of $G$ and $k_1, k_2\in \mathbb{N}$.

Is there a walk $w$ of $G$ of length $k_1$ ($w = (v_{i_1} \ldots v_{i_{k_1}})$) such that $\sum_{j = 1}^{n-1}p((v_{i_j},v_{i_{j+1}})) \leq k_2$ ?

Can you help to find the name and the complexity of this problem ?
Anybody has ever read something on this?


texts:
Suppose we want to train $K$ linear classifiers based on iid samples. Each classifier is of the form
$x\mapsto\mathrm{sign}(w\cdot x+\theta)$, with the constraint that the hyperplane $w$ is the same for all of the classifiers, but the thresholds $\theta$ can all be different. The motivation for this problem comes from transfer learning: we want to train a model of loan approval decisions where the lenders share a common decision procedure ($w$) but differ in their risk thresholds ($\theta$) --- and we wish to pool the samples so as to increase the statistical significance of the common $w$.
We model this as follows.
Each loan applicant is modeled as a point in $\mathcal{X}=\mathbb{R}^d$, represented by its feature vector.
Each lender's decision regarding an applicant
is a
signed
bit $y\in\mathcal{Y}:=\{-1,1\}$.
The $K$ lenders will be indexed by
$k\in[K]:=\{1,\ldots,K\}$.
Let $\mathcal{D}$ be a distribution over
$\mathcal{X}\times\mathcal{Y}\times[K]$.
Thus, a randomly drawn triple
$(X,Y,\kappa)\sim\mathcal{D}$ corresponds to the
decision $Y$ regarding applicant $X$ by
lender $\kappa$.
We consider the usual SVM hinge loss
incurred by $(w,\theta)$ on a labeled point
$(x,y)\in\mathcal{X}\times\mathcal{Y}$:
$$
\ell(w,\theta;x,y)
=
\max\{0,1-y(w\cdot x+\theta)\}
.
$$
On a sample of $n$ labeled triples
$(X_i,Y_i,\kappa_i)$, we define the sample risk
of the classifier defined by
$(w,\theta_1,\theta_2,\ldots,\theta_K)$
by
$$
R =
\sum_{i=1}^n
\sum_{k=1}^K
1[\kappa_i=k]
\ell(w,\theta_k;X_i,Y_i).
$$
As usual, we regularize this loss by the norm
of $w$, so the expression we'll be minimizing is
$$
L=
R+\lambda||w||^2,
$$
where $\lambda>0$ is a regularization parameter to be tuned via cross-validation. Minimizing $L$ is a convex (in fact, quadratic) program, which can be accomplished via SGD.
The Rademacher-based generalization bounds for this classifier class are straightforward to work out. (Spoiler alert: It's of order $O(\Theta\sqrt{K/n})$,
where $\Theta=||w||\cdot\max_{i\in[n]}||X_i||$.)
Question: Has a similar model of transfer learning appeared in the literature?


texts: Does an initial algebra for a class have to belong to the class itself?

texts:
In the context of algebraic data types, a concept of initial algebras is usually defined, e.g., in the following way:

  An algebra $S$ is initial in a class $C$ of algebras iff for every $A\in C$ there exists a unique homomorphlsm $h_A\colon S → A$.

At least "Initial Algebra Semantics and Continuous Algebras by" J. A. Goguen, J. W. Thatcher, E. G. Wagner, J. B. Wright states it this way. The proofs in that paper seem to imply that $S$ is assumed to belong to $C$ in the above definition.  Now, I'm wondering whether this restriction is meaningful. Put differently, has some reputable work defined an initial algerba for a class in such a way that the algebra is allowed to lie outside of the class?


texts: Set packing with maximum coverage objective

texts:
We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.

Set-Packing asks how many disjoint sets we can pack, and is defined as follows:

Given a number $k\in[m]$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that all of the sets in $\mathcal{S'}$ are disjoint?

Maximum-Coverage, allows intersecting sets, but asks how much of the universe can we cover by $k$ sets:

Given numbers $k\in[m]$,$r\in[n]$ is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that $|\cup_{s\in\mathcal{S''}}s|\geq r$?

I'm interested in what seems to be a combination of the two, a disjoint cover, which aims at covering as much of $\mathcal{U}$ as possible.

Disjoint-Maximum-Coverage:

Is there a set $\mathcal{S'} \subseteq \mathcal{S}$ such that $|\cup_{s\in\mathcal{S'}}s|\geq k$ (i.e. it covers at least $k$ elements) and the sets in $\mathcal{S'}$ are disjoint?

What can we say about the approximation hardness of $DMC$?
Is this problem known under a different name?

Related results:

Both Set-Packing and Maximum-Coverage are known to be $APX$-Hard (and even stronger than that - Unless $P=NP$, $SP$ can't be approximated within $ln(|S|)(1-o(1))$, and $MC$ has a tight bound using the greedy algorithm).

$MC$ is approximable within $1-\frac{1}{e} + o(1)$, while the best known bound for $SP$ is a $O(\sqrt S)$ approximation.


texts: Complexity of finding the maximal number of pair-wise disjoint sets

texts:
Assume that I have $P$ sets with elements taken from $r$ possible ones. Each set is of size $n$ ($n<r$), where the sets can overlap. I want to determine whether the following two problems are NP-complete or not:

Problem A. Are there $M$ ($1 \le M \le P$) distinct sets within the $P$ sets (i.e., their pair-wise intersection is empty)?

Problem B. Now $k$ ($k<n$) elements can be chosen from each set. Are there $L$ ($1 \le L \le P$) distinct sets of size $k$ each within the $P$ sets? Note that only one set of $k$ elements can be taken from each set of $n$ elements.

Remark: I am mainly interested in the case where $k,n$ are fixed ($n \ge 2, k \ge 2$).

I think that Problem A can be thought as an $n$-uniform $r$-partite hyper-graph matching problem. That is, we have the elements of $r$ as vertices, and each hyper-edge contains a subset of $n$ vertices of the graph.

In the $n$-uniform $r$-partite hyper-graph matching problem NP-complete?
I think that Problem B is equivalent to finding the number of distinct hyper-edges of cardinality $k$ taken from hyper-edges of cardinality $n$. Is this restricted version (in the sense that each $k$-cardinality set is taken from a pre-chosen set of $n$ elements rather than taken arbitrarily from $r$ elements) of Problem A NP-complete?

Example ($n=3,r=5, P=3$):

$A=\{1,2,3\}$, $B=\{2,3,4\}$, $C=\{3,4,5\}$

If $k=n=3$, there is only $M=1$ one distinct set, which is $A$ or $B$ or $C$, since each of the pairs $(A,B)$, $(A,C)$, $(B,C)$ has non-empty intersection.

If $k=2$, we have $L=2$ distinct sets: one solution is $\{1,2\}$, $\{3,4\}$ (subsets of $A$ and $B$).


texts: Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

texts:
The following question arose as a side product of some work I have been part of recently.
An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a circulant matrix and all its entries are either $0$ or $1$.  We assume that $m\leq n$.

Given such a partial circulant matrix $M$, what is the computational complexity of the following question?

  Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

The problem is clearly in NP but my guess is that it is not NP-hard (unlike this related question).  I have not, however, found a poly time solution.


texts: Is there a tool for finding Nash equilibria in parametric games?

texts:
There are a few tools, either online or offline, that could solve (find equilibrium) in a game explicitly given as a real-valued matrix.

Such tools are Game Theory Explorer and Gambit.

However, as far as I know, these can not be used for finding equilibrium in a game with parameters.

For example, consider a two player game symmetric game, parametrized by some $x\in[0,1]$, which is given by the following payoff matrix for the row player (and $A^t(x)$ for the column player):
$$A(x)=
 \left( \begin{array}{ccc}
\frac{x}{2} & x \\
1-x & \frac{1-x}{2} \\
\end{array} \right) $$

Each equilibrium in this game can be represented as $<p_a,p_b>\in[0,1]^2$ where $p_a$ is the probability of the first player playing the first strategy and $p_b$ is the probability the second player plays the first strategy.

Analytically we can find all the equilibriums for this game

$$EQ(x)=
\begin{cases}
\{<1,1>\}&\mbox{if } x>\frac{2}{3}\\
\{<3x-1,3x-1>,<1,0>,<0,1>\}&\mbox{if } \frac{1}{3}\leq x\leq\frac{2}{3}\\
\{<0,0>\}& \mbox{else}
\end{cases}
$$

I'm looking for a solver which is able to understand inputs like $A(x)$ and produce $EQ(x)$.

  Is there a tool which solves parametric games?


texts: What does mechanism design constitute? (Game Theory)

texts:
I've been reading about mechanism design and the field seems a little abstract, in that I cannot ascertain whether a certain approach towards solving games falls under mechanism design.

Let me clarify with the help of a specific example of an evolutionary game.

I have a population within which agents are either mutants or incumbents. The parameters to be decided are:

the fraction of the mutants ($\epsilon$)
the fitness $F$ of the agents

Now, if I came up with algorithms to define/calculate the above in such a way that the population ends up being evolutionarily stable, would my solution be called a mechanism?

Thanks


texts:
In the literature, I have only found a formal definition for safety properties in LTL. This, essentially, boils down to the following: "every trace that violates the property has a finite prefix attesting this violation". This, indeed, works nicely for LTL, which is based on traces. What about CTL?

For properties that can be equivalently expressed in LTL and in CTL, the definition safety in CTL can be given by transposing that from LTL. What about the ones that are not expressible in LTL?

For instance, AG p is clearly a safety property, when p is a state predicate. What about AG EF p? If the property is violated, then there exists a finite trace ending in a state, from which no state satisfying p is reachable.

Also, assuming there is a definition of safety in CTL, is there a syntactic characterisation of such properties?


texts: Impagliazzo and Wigderson's famous P=BPP paper

texts:
I'm reading Impagliazzo and Wigderson's famous $\mathsf P=\mathsf{BPP}$ paper in 1997.  Since I'm new to this field and the paper is a concise conference version, I have difficulty following their proofs.  In particular, some of their new theorems lack proofs.  To my best knowledge there hasn't been a journal version published.

I'm looking for resources from which I can learn their result, preferably those with formal proofs.  I'd be very grateful if you could tell me about such resources.


texts: Evaluate polynomial involving nearly-minimal graph cuts

texts:
So you want to evaluate the polynomial
$$
p(x) = \sum_{C} x^{|C|}
$$
where $C$ ranges over all nearly-minimum cuts in a graph (say, all minimal cuts of size $\alpha c$ where $c$ is the edge connectivity.) Here $\alpha$ is a small constant $>1$.

You can do any precomputation you want.

Two obvious algorithms present themselves. This is a polynomial of degree at most $\alpha c$, so you can do this is $O(c)$. Alternatively, for $\alpha$ sufficiently close to 1, the number of such cuts is at most $O(n^2)$, so you can do this in $O(n^2)$ work.

Are there any other algorithms available?

For $\alpha$ sufficiently close to 1, the set of all such cuts has a very nice structure, and these cuts can be represented in $O(n)$ space.


texts: How well can we do with this variable assignment problem?

texts:
Given in this problem is a set of values $0 \le c_{a,b} < n$, where $0 \le a < n$ and $0 \le b < n$.

The problem is to find the following sum as quickly as possible:

$$\sum_{a,b}{c_{a,b}x^a y^b} \bmod n$$

Here $x$ and $y$ are also assumed to be integers modulo $n$.

I'd like to know what the best method/approach is to solving this problem, and what kinds of worst-case behavior we can expect to get the sum.

Are there any similar problems whose solutions may help with this?

SOME NAIVE IDEAS

There are $n^2$ different constants and only $n$ different possible assignments for each $c_{a,b}$, so it seems that grouping some of the coefficients together is the best way to go.  However, beyond simple ideas, I'm not sure what will work best.  I'm hoping I can get some good suggestions.

MOTIVATION

My motivation for tackling this particular problem is that its solution may help improve the bounds of #3-SAT by some small degree.  However, the relation between the two is fairly complicated.


texts: Scott's normal form for $\exists y \forall x R(x,y) $

texts:
In this paper  Scott's reduction is discussed, which reduces any FO2 formula to Scott's Normal form. As far as I understand the reduction process explained in the paper can get you to formulas with only $\forall \forall$ and $\forall \exists$ quantification prefixes. Which has three possibilities of prefixes  $\forall x \forall y $, $\forall x \exists y$ and $\exists y \forall x$. Now scott's normal form only admits $\forall x \forall y $ and $\forall x \exists y$ quantification. Then how is the explained process sound for a formula like $\exists x \forall y R(x,y) $ ?
In other words, what is the scott's reduction for $\Phi(x,y) = \exists x \forall y R(x,y)$.
My attempt on reduction according to the paper:
$ Sc( \Phi(x,y) )= \exists x P(x)  \land \forall x \forall y (P(x) \leftrightarrow R(x,y)) $


texts: Adversarial Machine Learning, Learning with (Malicious) noise

texts:
I am reading some old papers regarding Learning With Malicious Noise. In one of them, Learning in the presence of Malicious Errors, by Kearns and Li $[1]$ (https://www.cis.upenn.edu/~mkearns/papers/malicious.pdf), it is proved that in the case that an adversary may choose a fraction $\beta \in [0, \frac{1}{2})$ of the training set to poison with instances, such that no restriction is put on the poison instances, then the upper bound $\beta < \frac{\epsilon}{\epsilon+1}$ must be met, so that it is possible to learn an $\epsilon$-good hypothesis with a probability at least $1-\delta$ (in the PAC-learning setting, using the usual notations). This bound is, however, not reached everytime, but for some specific hypothesis classes, the bound is much lower than that.

However, in the paper Learning from Noisy Examples, by Angluin and Laird $[2]$ (http://homepages.math.uic.edu/~lreyzin/f14_mcs548/angluin88b.pdf), it is shown that in the case of Clasification Noise, i.e. the attacker doesn't modify the underlying distribution of the instances, but may flip the label of some instances, with a probability $\beta$, then for every $\beta < \frac{1}{2}$, it is possible to find an $\epsilon$-good hypothesis with a probability at least $1-\delta$ (in the PAC-learning setting, using the usual notations), using at least $m \geq \frac{2}{\epsilon^2(1-2\beta)^2}\ln{\Big( \frac{2 \cdot |\mathcal{H}|} {\delta} \Big)}$ instances, where $\mathcal{H}$ is the hypothesis class supposed to be learned.

The question is: why is not possible to apply the result of $[2]$ in the case of $[1]$? How is the hypothesis that the underlying distribution of instances stays the same in case of $[2]$ used to prove the correctness? I am not able to find that in the proof. Can you please point it out for me?

Thank you so much everyone!


texts: Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

texts:
I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using Cover & Thomas[1] as an example (page 51):

  Theorem 3.1.1.(AEP): If $X_1, X_2, \cdots $ are i.i.d. ~p(x), then (...)

The proof is by using the weak law of large numbers and the fact that a statistic of independent random variables is also a random variable.

Shannon defines a Source X as an ergodic Markov chain of order k, therefore in the message $X^{(n)}=(X_1, X_2 ...X_n), X_i$ are not independent. The aforementioned AEP proof assumes a memoryless Markov chain.  Why?

How can I be sure that the proof of AEP holds for a source that is an ergodic Markov chain?

[1]T. M. Cover and Joy A. Thomas. Elements of Information Theory. 2nd ed. OCLC: ocm59879802. Wiley-Interscience, 2006. isbn: 9780-471-2419-5-9.


texts: Problems with complexity between P and NP that have  NP-complete generalizations

texts:
Can anyone list some well-known problems that satisfies the following conditions:

1. has a generalization problem that is known to be NP-complete
2. has not been proved to be NP-complete nor has a known polynomial time solution.


texts: A question on linear extensions of partial orders

texts:
If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with each of the partial orders).

I've come across a variation:

  Fix a set $V$. You're given sequences $\sigma_1, \ldots \sigma_k$ of
  elements drawn from $V$ without repetition (the sequences are of
  length between 1 and $|V|$).

  Is there a way to fix orientations for each of the sequences (either
  forward or reverse) so that the resulting collection of chains (viewed
  as a partial order) admits an extension ?

Is this problem well-known ?

Note: The orientation is chosen for an entire sequence. So if the sequence is $1-2-4-5$, you can either keep it that way, or flip it to $5-4-2-1$, but you can't do anything else.


texts: Estimator for sum of independent and identically distributed (iid) variables

texts:
This is a repost of a question at math.stackexchange, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot.

Consider the Chernoff bound described in Theorem 1 of this paper:

  Theorem 1. Let $X_1,\ldots,X_n$ be discrete, independent random variables such that $E[X_i] = 0$ and $|X_i|<1$ for all $i$. Let $X:=\sum_{i=1}^n X_i$ and $\sigma^2$ be the variance of $X$. Then,
  $$\Pr\left[|X|\ge \lambda\sigma\right] \le 2e^{-\lambda^2/4}$$
  for any $0\le\lambda\le 2\sigma$.

I want to apply this estimator for a computation, but the variance of the variables $X_i$ is unknown to me. Apart from that, my variables satisfy all the conditions of Theorem 1. In fact, my variables are independent and identically distributed (iid).

On the other hand, there is Chebyshev's inequality for finite samples which does not require knowledge of the variance (or mean) of a given random variable and replaces it with the corresponding values of my given sample.
 However, the estimator is not good enough for my application and I was wondering if there is an estimator similar to Theorem 1 but not featuring the variance of the distribution itself.

Intuitively speaking, it would be nice to have the best of both worlds: If that is not possible, then what is the best bound I can achieve for a sum of iid variables, without any knowledge about their variance?

Edit. I will explain the application in greater detail. I have a tree, at its leaves $v$ are labels $\ell(v)$ with values from the interval $[-1,1]$. I want to know whether these values sum to zero, but summing them up would take too long, because there are too many of them. However, I can easily do a random walk from the root to a leaf. Viewing the tree as a decision tree this way, let $p(v)$ be the probability of each leaf $v$. I then sample a couple of leaves $v_1,\ldots,v_n$ and compute the values $\tfrac{\ell(v_i)}{P\cdot p(v_i)}$, where $P$ is an upper bound for $\tfrac{1}{p(v)}$. Under the null hypthesis that the leaf lables sum to zero, the expected value of a random variable sampling this fraction is
$$\sum_v p(v) \cdot \frac{\ell(v)}{Pp(v)} = \frac{1}{P} \sum_v \ell(v) = 0.$$
Hence, I am in the situation of Theorem 1. I compute
$$t=\sum_{i=1}^n \frac{\ell(v_i)}{P\cdot p(v_i)\cdot\sigma}$$
and by Theorem 1, $2e^{-t^2/4}$ is an upper bound for the probability that this sample was obtained under the assumption of the null hypothesis. Now, this works very well for small test instances when I compute $\sigma$ - which actually requires me to search the entire tree. For larger instances, that's exactly what I am trying to avoid, so I need something different. It would be less of a problem to use the mean or the standard deviation of my sample, for instance.

Note that
$$\textstyle
\sigma^2 = E(X^2)- E(X)^2 = E(X^2) = E(\sum_{i=1}^n X_i^2) + E(\sum_{i\ne j} X_i X_j).$$
Since $X_i$ and $X_j$ are independent, this means $\sigma^2 = n E(X_1^2)$. In my application, the expected value of $X_1^2$ is so small that reasonably large sample sizes cannot negate the effect that $\sigma^2$ is very small.


texts: Computing the distribution from which this algorithm samples from

texts:
Assume we have a set of integers $X_0=\{x_1\ge x_2\ge\ldots\ge x_n\}$.

Let $r\in(0,1]$ be a parameter and consider the ranking process:

i=0
while ($X_i\ne\emptyset$)

let $M = \max \{x\in X_i\}$   (i.e., the maximum of the numbers in $X_i$).
Let $C = \{x\in X_i | x \ge r\cdot M\}$ (the set of numbers which are at least $r\cdot M$)
Pick a uniform random number $y\in C$ as the $i$'th ranked number.
Set $X_{i+1} = X_i \setminus \{y\}$ and increment $i$.

The goal is to compute the rank distribution $D$ of $x_i$ (the input is the set $X$ and an index $i$).

  How fast can we find $D(X_0,i)$? (also - is there a fast way to approximate it?).

Currently I'm using a simple Monte Carlo simulation, which is quite slow for my application.

For example, consider $X_0 = \{5,4,3,2,1\}$ and let $r=\frac{1}{2}$.

The distribution of $x_3 = 3$ is as follows:

With probability $\frac{1}{3}$ it is ranked first.
With probability $\frac{5}{18}$ is ranks second (notice that if $5$ is ranked first, then the chance $x_3$ is ranked second is only $1/3$, but if $4$ was ranked first, it has a probability of $1/2$).
With probability $\frac{7}{36}$ is ranks third and with the same probability it ranks fourth.

The output is then $D(X_0,3) = <1/3, 5/18, 7/36, 7/36, 0>$.


texts:
I am aware that it is generally believed that P = BPP, but BQP != P (since factoring is in BQP, and factoring seems hard.)

For BPP, we have the hardness vs randomness result: which states that circuit lower bounds for EXP imply derandomization results for BPP.

Even though I do not expect BQP to be simulatable in sub-exponential time, I am curious if there are any implication results along the lines of "If pigs can whistle, than donkeys can fly."

Formally, I'm asking if there exists provable statements of the form:

If [XYZ] then BQP can be simulated in sub-exponential time.

Ideally, [XYZ] would be about the hardness of certain problems against certain complexity classes. However, any XYZ not of the form "BQP can be simulated in sub-exponential time" would be interesting.

Thanks!


texts: What is the optimal binary encoding of the elements of a monoid?

texts:
The Question

Let $M$ be a finite monoid. Let $S$ be a generating set of $M$. Say we have a binary encoding of $S$ represented by $\phi:S \rightarrow A^*$ where $A = \{0, 1\}$. This encoding should have the prefix property.

There is a natural extension of $\phi$ to $M$; for any $a \in M$ choose $b_i \in S$ s.t. $b_1b_2 \cdots b_n = a$ and let $\phi(a) = \phi(b_1)\phi(b_2)\cdots\phi(b_n)$.

I would like to minimize the quantity $\sum_{a \in M} |\phi(a)|$ by choosing $S$ and $\phi$ intelligently. Is there a name for this problem? Has research been conducted on it?

Motivation

I am attempting to design an instruction set for a virtual machine which optimizes code density. In my specific case, $M$ is the transformation monoid on $X$ (e.g. the set of all mappings from $X$ to itself under composition) where $X$ represents the state-space for my machine. Alternately, $M$ can be thought of as the set of all programs my machine can execute and $S$ can be thought of as the instruction set. I assume someone has already thought long and hard about this question.

P.S.

For the sake of propriety, I will add that I have already asked a similar question on the Mathematics StackExchange. I feel that the original question was worded very poorly, and that the forum was inappropriate. Hopefully no one minds that I've asked an improved, slightly different question here. If there is a problem, I would be happy to delete the original question.


texts: Conceptually simple linear-time suffix tree constructions

texts:
In 1973 Weiner gave the first linear-time construction of suffix trees. The algorithm was simplified in 1976 by McCreight, and in 1995 by Ukkonen. Nevertheless, I find Ukkonen's algorithm relatively involved conceptually.

Has there been simplifications to Ukkonen's algorithm since 1995?


texts: Follow the Perturbed Leader for nonlinear cost functions

texts:
The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known?

Note that in the last paragraph of [1] it says "It would be great to generalize FPL to nonlinear problems".

In [2] (page 69, 70, 71) there is analysis of FTPL for general functions, but the resulting bound $O(T)$ does not attain the optimal bound (i.e. $\sqrt{T}$). Are you aware of better analysis for FTPL (with general nonlinear functions) that attain the optimal regret?

Update:  The algorithm in [2] is indeed $O(\sqrt{T})$ (by choosing $\eta = 1/\sqrt{T}$) but it is calling the linear optimiazation oracle many times (not just once as in [1]), which results in having a different bound.

[1] http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf

[2] http://ocobook.cs.princeton.edu/OCObook.pdf


texts:
There are algorithmic graph theory/number theory/combinatorics/information theory/game theory.

  Is there algorithmic mathematical analysis?

According to wiki, mathematical analysis includes the theories of differentiation, integration, measure, limits, infinite series, and analytic functions. It is OK to focus on real analysis (wiki) that deals with the real numbers and real-valued functions of a real variable.

"Algorithmic" means studying something from the perspectives of computability theory and complexity theory.

Googling of "algorithmic mathematical analysis" leads me to "mathematical analysis of algorithms" or "applications of analysis to algorithms", which is not what I mean.


texts: Subset Sum Problem and hard looking instances that are not really hard

texts:
I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" instances are easier to solve than the really hard ones.. (and maybe this applies to other problems as well)

I was wondering if this has been described (and analyzed) elsewhere, any reference will be greatly appreciated.

The values in the input instance must have $GCD = 1$, if greater, the instance (let's name it $A$) will look harder than it really is, due an artificial input length
The real hardness, will only be known once all input values, and the target, have been divided by their GCD, creating a B instance from A, with $|B| < |A| $.
The reason is, when this input instances are presented to the algorithm, both instances will take the same number of steps to compute while having a supposedly different hardness (density). This characteristic can be used to present a $n\ge p$ instance, when in reality is $n<p$, just the values, and the target, have been multiplied by an integer long enough to produce the desired artificial length.

This was found when experimenting with edge cases, trying to better understand the input length impact in the algorithm, if a instance $n=100$ / $p=16$ takes $x$ total steps, and we create an artificial instance by multiplying the values and the target by the same integer, causing all the values including the target to have $\approx 100$ bits, the resultant instance, having $\approx 10000$ bits will take exactly the same number of steps like the original one having $\approx 1600$ bits, that is, $x$ steps.


texts: Is there a linear time algorithm for integer multiplication verification?

texts:
There is a quadratic randomized algorithm for matrix product verification.
Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?


texts:
I'm interested in studying how information spreads in a social network. The basic problem is as follows.

Let's say we have a large graph of people, with directed edges connecting them. Let's also assume that based on the links, we can robustly identify influential people using something like Pagerank, etc.

Within this setting, suppose we want to inform the people in the network of some important piece of news, and that we can only do so by face-to-face contact with individual people. Also, we have limited resources -- suppose, because of limited resources, we can only have face-to-face contact with n people, out of a total of N people in the whole graph.

Question: how do we choose this subset of n people from the graph?

One easy solution is to use Pagerank and identify the most influential people. However, this doesn't exploit the idea of redundancy: if the top 3 most influential people according to Pagerank have let's say 80% of their neighbors in common, then we're essentially wasting resources by marketing to each of these three people.

Any insight on this problem would be helpful -- it seems that this situation would occur often enough that someone must have come up with a formal treatment with efficient algorithms, etc. I can think of a few ways to do this, but they involve inefficient traversals, etc.


texts: Exact Algorithm for edge labeling problem in DAG

texts:
I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.

Problem: We are given directed acyclic graph $G=(V,E)$.  Without loss of generality assume that $G$ has exactly one source vertex $s$ and exactly one sink vertex $t$; let $P$ denote the set of all directed paths from $s$ to $t$ in $G$.  We are also given a set of vertices $R \subseteq V$.  The problem is to assign non-negative integer weights to the edges of $G$, so any two paths in $P$ have the same weight if and only if they contain the same subset of vertices in $R$.  (The weight of a path is the sum of the weights of its edges.)  The range of weights of paths in $P$ should be as small as possible.

Currently my approach does not seems efficient; I am just looking for some references to literature or some good insights. Anything otherwise is also appreciated.

Edit: Is there a hardness proof for this problem? Does the compact numbering always exists?


texts: Is an algorithm with an approximation factor of 4000 useful?

texts:
A paper published in SODA this year (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds.

To my surprise, when reading the paper, I verified that its constant approximation factor is 4000.

Therefore, I was left wondering if this algorithm is really useful for something.
Like, do you know, a solution that is 4000 times worse than the optimal solution can be anything, and probably a solution given by a simple polynomial-time greedy algorithm will be better than that of given by this more complex approximation algorithm.


texts:
What is known about the complexity of creating Block Designs (https://en.wikipedia.org/wiki/Block_design)?

I've found one paper that creates approximately solutions using Metaheuristics that claims that Block Design is NP-Hard, citing a paper from 1978. But that paper from 1978 makes no such claim or proof.

I'm particularly interested in the special case of Projective planes (https://en.wikipedia.org/wiki/Block_design#Projective_planes).


texts: Is Logic Done on Superpositional Bit Values Useful?

texts:
Let's say I have a way to represent $N$ bits such that those bits are in a superposition of the $2^N$ possible states those bits can have and that I can do XOR and AND on those superpositional bits to be able to map $N$ superpositional input bits to $M$ superpositional output bits using any logical circuit (since XOR and AND are supported).

Let's say that I am also able to include bits in those logic circuits which are not superpositional but have specific values of either 0 or 1.  This way I can do a NOT by XORing a superpositional bit by 1 for example.

At the end of the logic circuit when I have the superpositional result, I can then decide what values the input bits had, and get a non superpositional result out for those inputs, without evaluating the circuit again.  I can interpret the result as many times as I want for the entire permutation of input bits if I want to.

I'm wondering, would a superpositional logic technique like this be useful, and does anyone know if any work has been done in this area?

I know this is similar to how quantum computing works, except for a few key differences like not having interference, nor having probabilities for states, but it does allow cloning of the superpositional result, unlike quantum computing which only allows one question to be asked of the result.

I can think of a couple usage cases, but am wondering if there are others?

Using a superpositional result as a way of letting an untrusted person specify how inputs should map to outputs (basically, "script" some process), without havign to sandbox the logic, worry about division by zero, infinite loops, and the like.
I have yet to experiment deeply with this, but if you need to know several values of some function $f(x)$, it may be more computationally efficient to evaluate it superpositionally and then re-interpret the superpositional result several times, versus just calculating the function several times.


texts: Solving multiple instances of 3SUM generated from the same set

texts:
(this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM)

Suppose we have a list $S$ of $n$ integers.
Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ $\in S$ such that $a+b+c=0$. That's done in $O(n^2)$, and obviously the same thing can be done for $a+b+c=d$, with $d$ an integer.

Now, I use a somewhat modified version of this problem. Someone randomly picks $n$ triplets of elements of $S$, and for each of them, computes the sum of its elements. Let's call the list of these sums $Y$. That's $n$ instances of 3SUM built on the same set.

My goal is to invert one element of $Y$., i.e. is to find one element in $Y$, along with its corresponding elements in $S$. (To solve one of the possible instances of 3SUM, no matter which one)

I'm looking for a $O(n)$ solution. If we feed this solution some particular $S$ and $Y$ ,and we want to find a particular $d$ in $Y$, it would take the solution $O(n)$ attempts to find the $d$ we're looking for, thus running in $O(n^2)$, which is the 3SUM complexity.

I tried to use randomness in my solutions, without success. Someone also advised me to have a look at FFTs, but I can't see how I could use them in this case.

The best that I can do now, is to have $Y$ built with $n^{1.5}$ triplets instead of $n$, and then I can use the birthday paradox. If I pick $O(n^{1.5})$ triplets at random, I have a constant probability to find the same triplet twice. ($n^{1.5} = \sqrt{n^3}$)


texts: Complexity of selective network improvement problem

texts:
We have a network flow problem with a given directed graph $G=(V,E)$, for each arc $(i,j) \in E$, there is a cost $c_{ij}$ and upper and lower capacity $u_{ij}$ and $l_{ij}$ for the flow $f_{ij}$ through it. The min-cost flow to minimize $\sum_{(i,j) \in E}{c_{ij}f_{ij}}$ is well known to be solved in polynomial time. But now we are given opportunities to improve the cost on the arcs. Suppose we know in advance that after improvement on an arc, its cost will be reduced by $\Delta_{ij}$. My problem is given an integer $K$ ($K<|E|$), how to select the $K$ arcs to improve so that the resulting min-cost objective function is minimized?

Currently, I can formulate the problem as:

$\min{\sum_{(i,j) \in E}{(c_{ij}-x_{ij}\Delta_{ij})f_{ij}}}$

subject to

$\sum{f_{ij}} - \sum{f_{ji}}=b_i, \quad i \in V$
$l_{ij} \leq f_{ij} \leq u_{ij}, \quad (i,j) \in E$
$\sum{x_{ij}}=K, \quad (i,j) \in E$
$x_{ij} \in \{0,1\}, \quad (i,j) \in E$

Constraints 1. and 2. are just normal flow constraints while 3. and 4. are like packing constraints. With the introduce of 0/1 variable $x_{ij}$, this problem seems to be hard to solve. So I'm wondering what is the complexity of this problem? Thanks.


texts: Optimal algorithm for finding the girth of a sparse graph?

texts:
I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.

I thought about some modification on Tarjan's algorithm for undirected graphs, but I didn't find good results. Actually I thought that if I could find a 2-connected components in $O(|V|)$, then I can find the girth, by some sort of induction which can be achieved from the first part. I may be on the wrong track, though. Any algorithm asymptotically better than $\Theta(|V|^2)$ (i.e. $o(|V|^2)$) is welcome.


texts: Gaussian elimination for inverting matrices modulo prime power

texts:
Can I use Gaussian elimination to compute matrix inverse over the ring $\mathbb{Z}_{p^k}$ (ring of residues modulo $p^k$) where $p$ is prime and $k$ is an integer greater than $1$?

Such matrix is invertible if and only if its determinant is not congruent to zero modulo $p$. So we can check if it is invertible by constructing the second matrix — matrix of residues modulo $p$ of elements of the original matrix. The second matrix is over $\mathbb{Z}_p$ so we can use Gaussian elimination to compute its determinant. The determinant can be expressed as a polynomial formula (Laplace expansion) so the determinant of the second matrix is the determinant of the original one modulo $p$ and so the original matrix is invertible if and only if the determinant of the second one is not zero.

I think that using Gaussian elimination to compute the inverse in this case is correct and it is quite easy to prove. It uses exactly the same steps as inverting the aforementioned matrix over $\mathbb{Z}_p$. Gaussian elimination over the finite field $\mathbb{Z}_p$ fails if and only if the matrix is not invertible and it fails because all the elements under the pivot position are zero. It means that in the original matrix all these elements are congruent to zero modulo p so they are not invertible and Gaussian elimination fails over $\mathbb{Z}_{p^k}$. If the elimination succeeds over $\mathbb{Z}_p$ then it also succeeds over $\mathbb{Z}_{p^k}$ — if you can find nonzero pivot element in the matrix over $\mathbb{Z}_p$ then the equivalent element in the original matrix is invertible.

Moreover I have implemented it and it works. For invertible matrices it gives their inverses modulo $\mathbb{Z}_{p^k}$. For non-invertible it fails. I have conducted many tests for different matrix sizes, different $p$ and different $k$.

It is quite simple so there are two possibilities: either there is something wrong in my reasoning, or someone must have described it somewhere. However I could't find any reference for that fact. I've found some articles and books that discuss the computation of matrix inverses and determinants modulo integers (e.g. Pan, Stewart — Algebraic and numerical techniques for the computation of matrix determinants, von zur Gathen, Gerhard — Modern computer algebra) but I haven't found it there.

I would like to find some reference that clearly states that you can do Gaussian elimination over $\mathbb{Z}_{p^k}$ or some argument against it.

Thanks in advance.


texts:
This might be embarrassing, but it turned out I don't know what is $DTIME(n^a)^{DTIME(n^b)}$. It is between $DTIME(n^{ab})$ and $DTIME(n^{a(b+1)})$ but where?

Update: There are three possible ways to define oracle machines.

1, They have an oracle tape, which they can read (see wikipedia).

2, They have an oracle tape, from which they can pose questions (see Arora-Barak book).

3, Same as two, but after each question the tape is erased (I could swear I heard this too).

I had 2 in mind, as the most common (?) definition.
In case of 3 it is easy to prove that the answer is $DTIME(n^{ab})$ (see Kristoffer's answer).
In case of 1, I am not even sure that the bounds I claim hold, but maybe it is not hard to prove, I have no clue about this version.

Update: I have realized that the number of tapes changes the power, so it is best to forget this question...


texts: partitioning boolean lattice into the smallest number of chains

texts:
As a result of the Dilowrth's theorm we know that the Boolean Lattic can be partitioned into    $\dbinom{n}{n/2}$ chains and it is the smallest number of such chains. Another question regarding that, is who many different possible partitioning of a boolean lattic into smallest chains does exists?
I have some ideas. For example to start from one possible partitioning and find out other possible ones. Please help me with more ideas.


texts: Have people looked for parameterized algorithms for problems that are not in NP?

texts: Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the solution size)?


texts: Running an algorithm for fixed amount of time on RAM model machine

texts:
Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "Hello", and then resume its execution, run it again for $O(\sqrt{N})$ time and repeat this cycle until the algorithm execution terminates. If the algorithm takes time $T$, then there would be $O(T/\sqrt{N})$ print statements.

It is obvious that an algorithm can be paused/resumed in constant time by storing/loading the content of all registers of the CPU in the memory. However, how is it possible to measure elapsed time in the RAM model and stop the algorithm after $O(\sqrt{N})$ steps? Does the RAM model support such an operation (a Turing machine definitely does)? Any reference or a simple argument is welcome!


texts: Finding outer face in plane graph (embedded planar graph)

texts:
I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices.

Computing a list of all faces of the graph (as a list of oriented walks along their arcs) is fairly straightforward.

On the other hand, finding a simple way to pick the outer face out of the list of faces does not seem as easy: it is included in the list of faces, but since its orientation is "reversed" (i.e. relative to the outer region, rather than the inside of the graph boundary), all its properties in terms of neighbouring faces are identical to other faces.

Short of using plane coordinates to painstakingly identify the outer nodes/arcs of the graph, is there a more straightforward way to pick the outer face out of the list of faces using the combinatorial embedding (given as a table of arc successors in the oriented plane)?

Edit: Upon reading the comments, I realised that my wording was ambiguous (verging on the incorrect): while I have the combinatorial embedding and would like to use it (or the information derived from it), I also have coordinates derived from a drawing of that graph (hence the plane graph, not simply planar graph), ensuring that there is, indeed, a specific outer face.

What I meant to say is that I am looking for a method that would do more (or rather: less) than just looking at the coordinates of all faces and (for example), compute their orientation.

To be precise, the embedding and plane drawing give me:

a list of all faces (as an oriented walk of vertices).
for each arc: the face left and right of it.
for each vertex: an oriented walk of its ingoing/outgoing arcs (actually, my graph of interest is undirected, but that is probably not very relevant).

Edit 2: Despite the upvotes, the first comment does not really solve much (it essentially boils down to a recursive answer: "in order to find the outer face, use the leftmost vertex, then find the outer face", which isn't as trivial to solve as its commenter seemed to think.

@Zsbán provided what looks like the most efficient and elegant solution. Thanks!


texts:
Does there always exists a $n \times n$ grid with $0$s and $1$s that satisfy the following conditions:

there is an equal number of 1s and 0s in each row and column
no more than two identical numbers next to or below each other are
allowed
there can be no identical rows or columns

How to construct a nxn grid that satisfy all the above conditions?


texts:
I've been learning about interactive proofs lately and I've been wondering if the whole thing was nothing more than a theoretical curiosity, or if it had any practical applications. I thought I'd start off with an example which occurred to me in the shower:

It's been making the news lately that "God's Number"=20. (God's number is the minimal number of steps needed to solve the Rubik's Cube). While this is pretty interesting,  there seems to be a little twist ... This isn't a "normal" proof in the textbook, polynomial time verifiable sense. This proof has a distinctly "brute force" flavor to it - by this I mean, the dudes at Dr Morley's lab tried with billions and billions of combinations of cubes in Google's massive supercomputers to find this neat, tight lower bound.

Anyway, the question is: How can we be certain that Dr Morley Davidson and his team are honest? Well, right away can throw the argument from authority out of the window as it's not mathematically rigorous. The obvious alternative is to re-verify the proof, by checking the source code and running the whole thing again, which seems to be a terrible waste of computational resources, not to mention the fact that everybody who who wished to be convinced of this would need to do it on his own workstation - a very tedious and unpleasant proposition for the true skeptic. So this seems to be a kind of ontological deilema.

So what I believe is this is exactly a situation where we need an interactive proof. Google's Supercomputer could be the all powerful but deceptive Prover, and we the skeptical, if not anal members of the public are the Polynomially bounded Verifiers. If we could somehow query our "Oracle" a polynomial number of times, and be convinced of this lower bound, we could be convinced of the fact that he's right, beyond all reasonable doubt.

So it seems the Decision problem "God's Number is < 20" lies in $\Pi_2^p$ or can be restated as follows (informally)

For all starting combinations $\alpha$ in the Rubik's Cube, there exists a solution which takes <=20 steps, $\beta$ which solves it.

(not sure if that's correct, but $\alpha$ and $\beta$ are both small in size, given a starting configuration and a solution it's easy to verify that it does indeed solve the cube)

and the Decision problem "God's number is 20" can be restated as

God's number is <20 and there exists a solution for some starting combination of the Rubik's cube which takes 20 steps.

So there's probably a IP[n] proof for this. (once again, check my workings)

My question is twofold

Is there a actual way to do this?
What other examples of "pratical" uses of interactive proofs are there?


texts: Is Bayesian updating computationally unfeasible?

texts:
Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be possible to compute the Bayesian probabilities in polynomial time, and the Bayesian update algorithm should also be computable in polynomial time. Unfortunately, this doesn't appear to be the case in general.

Consider the following example: We have some set of all strings $X$ of length $n$, and a one-way function $f$ from $X$ to $Y$. For the Bayesian prior, choose a uniform probability distribution over $X$. Say the string is $x \in X$, but we haven't and won't measure it yet, so we don't know what $x$ is. However, we compute and measure $y = f(x)$. Using standard Bayesian theory, we can figure out what the theoretical Bayesian posterior distribution ought to be. However, by definition, it can't be computed in polynomial time.

What implications does this have for Bayesian theory?

PS: Actual physical agents often aren't all that rational. In fact, most of them can probably be Dutch booked, and their bets would be influenced a lot by the context. Also, many of them seldom update their beliefs based upon contrary evidence. Whatever Bayesianism is, it most certainly is an abstraction.


texts: What's the complexity of factoring over a set of generators (say in $GL_2$)?

texts:
In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know the time complexity of factoring it into a product of $A$s and $B$s is (or showing that such a factorization does not exist); that is, how long would it take to exhibit the product (or show the lack of existence)

$$ABBAAAB\cdots BAAB = C?$$

I have a feeling that this falls under Ladner's theorem but I'm not sure.


texts: Generate TSP instances with known optimal

texts:
Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value?

The idea is to be able to generating arbitrary large instances with known optimal value, in order to be able to test heuristics on them.

I found the paper Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, No. 2 (Feb., 1988), pp. 153-159 for generating TSP with known optimal, alas I cannot access it.


texts: Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

texts:
Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but since $m$ is very large, we use an oracle, that given a point $x \in R^k$, either says $x \in P$ or returns a half-space such that $x \notin S$.

My goal is to find a point in $P$ or determine that $P$ is empty. I'm aiming for  a polynomial running time in the representation size of $U$ and $k$, where $U$  is the largest absolute value in $A$. That is, the algorithm should make only polynomial many calls to the separation oracle.

In general, $P$ might be contained in a hyper-plane of lower dimension and thus it is problematic to use the ellipsoid method. So, as in Khachiyan's trick, I alter $P$ (and the separation oracle) to use $P^\epsilon$, where $\epsilon$ is something like $1/U$. Intuitively, the half-spaces that define $P^\epsilon$ are the same as the ones that define $P$ only that they are translated by $\epsilon$. The polytope $P^\epsilon$ has the following properties: $P^\epsilon$ is empty iff $P$ is empty, and if $P$ is not empty, $P^\epsilon$ is full-dimensional.

My question is as follows:
Assume the algorithm finds a point $p \in P^\epsilon$. Is it possible to generate a point in $P$ using $p$?


texts: How to cite Babai's new graph isomorphism result?

texts:
Recently, Babai has published a paper on STOC 2016 claiming that graph isomorphism can be solved in quasipolynomial time.

In the beginning of 2017, Babai retracted the quasipolynomial claim due to some serious mistakes found by Harald Helfgott. As explained by Babai himself, this flaw makes the improvement more modest in terms of running time.

About 5 days after retracting the quasi-polynomial claim, Babai posted another update in his homepage arguing that he had fixed the flaw in the proof, restoring in this way the quasi-polynomial running time.

I have to say that after this fast change on the status of the correctness of the proof I would normally completely ignore the new paper until it was published in a well respected journal.

But since Babai is Babai, most of the community is taking his's word for granted, at least publicly, even though the new version of the paper with all corrections implemented is not even available. Note that even great people make mistakes and there is a non-negligible chance that the new fix also has a flaw and so on.

So now, how should I cite the new result?

Cite the STOC paper claiming the quasipolynomial upperbound.
Cite the STOC paper explaining that it has a serious flaw and that the real running time improves the previous subexponential lower bound.
Cite the STOC paper saying that it had a flaw that was fixed by Babai.
Do not cite at all, and state the old upper bound of $2^{O(\sqrt{n})}$ as the current established upper bound.


texts: What kind of computations or algorithms give rise to iterated logarithm and inverse Ackermann function?

texts: I heard a statement saying that iterated logarithm and inverse Ackermann function are usually the slowest growing functions used in computer program complexity analysis.  Is that true? What kind of computations or algorithms naturally give rise -- in the sense as does divide-and-conquer gives rise to logarithm --  to iterated logarithm and inverse Ackermann function?


texts:
I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. The students immediately asked: "what does computability mean?" and I can't answer unless I teach them Turing machines, and then answer "a function is computable if a Turing machine computes it."

So,

  Is there a description of computability which does not require resorting to Turing machines, λ-calculus, or similar models of computation? Even an intuitive description will suffice.


texts: Software that generates and solves a Lasserre hierarchy

texts: Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre hierarchy. There are many software tools available to solve linear programs (e.g. CPLEX, lpSOLVE, GLPK) . I am looking for a (free) software tool that can do the following. If I give a linear program and a number t as input, then the tool must output the optimal value of the objective and values of the SDP variables at the t-th level of hierarchy.


texts: For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

texts:
I want to be very specific. Does anyone know of a disproof or a proof of the following proposition:

$\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$

$\forall G, H \in STRUC[\Sigma_{graph}] (min(|G|, |H|) = n, G \not\simeq H),$

$\exists \varphi \in \mathcal{L}(\Sigma_{graph}),$

$|\varphi| \leq p(n) \wedge qd(\varphi) \leq Clog(n)^k \wedge G \vDash \varphi \wedge H \nvDash \varphi.$

Intuitively, this should be true if all non-isomorphic graphs can be distinguished using "$Clog(n)^k$ local" statements, and I'd imagine that this is false. Of course any graph can be distinguished using polynomial quantifier depth, as you can simply specify your graph modulo isomorphism:

$\varphi = \exists x_1 \exists x_2 \exists x_3 ... \exists x_n (\forall x (\bigvee_{i \in V_G} x = x_i) \wedge (\bigwedge_{(i, j) \in E_G} E(x_i, x_j))) \wedge (\bigwedge_{(i, j) \notin E_G} \neg E(x_i, x_j))) \wedge (\bigwedge_{(i, j) \in V_G^2 \mid i \neq j}x_i \neq x_j).$

Edit: So it seems that the locality intuition I had is false. A formula of quantifier depth $k$ has Gaifman locality bounded by $O(3^k)$, which means that a log depth formula is basically global. For this reason, I have a hunch the proposition will turn out to be true, which would be much harder to prove in my opinion.


texts:
I am trying to grok dependent types, and there's something that I find unclear.

In C++, templates can have non-type (template) parameters. The values of these parameters have to be specified at compile time, and it is then - at compile time - that the value-dependant types are defined/created/generated/declared.
It is not possible to generate a dependent-type with a run-time value.

Beyond syntactic differences, how are languages with dependent types like e.g. Idris different from what C++ does (albeit with somewhat awkward and possibly convoluted syntax)? After all, the whole point of their strong type systems is also to catch type errors at compile time, so obviously any runtime behavior is already after all the compile time checks have succeeded.

If I was to define the proverbial fixed-size list/vector type (where the list size is embedded in the type), then append() would return a (new) list of a new type with the new incremented size specified as part of the type. In C++, you would need to know the actual types, i.e. the size of the list, at compile time. There is no way to call append() on the result of the previous append() call, a runtime-determined number of times (as in a loop), because there is no (obvious) way to specify the type of the object to hold the previous result at runtime. Calling it recursively would cause a compile-time stack explosion.

What does e.g. Idris do that is different?
What extra power comes from dependent-types in languages that support them?
Alternatively, what is C++ missing to be considered as a language that supports dependent-types?


texts: Generating graphs of girth $g$ such that the minimum cycles form a double edge cover

texts:
Let $g\geq 3$. I need to generate simple graphs $G$ of girth $g$ such that the set of all $g$-cycles forms a double edge cover of $G$ (that is, every edge is shared by exactly two $g$-cycles), and such that the intersection of any two $g$-cycles is either a vertex, an edge, or empty. The generated graphs should be arbitrarily large.

The method of generation should have some randomness to it, but not in a trivial sense. I want to be able to obtain fairly complicated graphs. For example, imagine an $n\times m$ rectangular grid in the plane. If we identify the opposite sides of the bounding rectangle, we obtain a graph that satisfies all of the above requirements for $g=4$. I would qualify this graph as simple.

Is there any such method?

Any references to similar problems are also appreciated.


texts:
I stumbled on an open problem posed by David Eppstein and I am interested in its complexity status. He conjectured that it is NP-complete.

Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ 0’s and 1’s

Question:  Is there a path through adjacent matrix entries, covering each matrix entry exactly once, with values matching the given sequence?

  Did anyone prove that the problem is indeed hard?


texts: Status quo of category theory and monads in theoretical computer science research?

texts:
Background. I am a bachelor student who is interested in research related to category theory, monads and Haskell, and I want to find a topic for my bachelor’s thesis in that area.

I have looked at the paper

Eugenio Moggi, “Notions of Computations and Monads”, 1991,

and I do not understand much of it yet. I will probably need quite some time to fully understand it.
But before spending more time on studying it, I want to get a better understanding of the field and its research potential.
I recently talked to a professor of mine about it and he told me that monads were in fashion in the research community back in the 90s, but nowadays they are out of fashion.

Therefore, I am now looking for recent work related to monads, and am wondering:

In what areas of theoretical computer science is nowadays research done  that is related to category theory and monads?
What sort of research has been built up or proposed on E. Moggi’s work on monads in the theory of programming? Has there been any follow up or on going research related to his paper?


texts: Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?

texts:
I have just started on the book Elements of Programming (2019) and after thinking about the definitions for value types in chapter 1, that in principle seem to link meaning (the abstract entities of a species) to a bit representation, I started wondering about the following quote (Section 1.2 "Values" p. 3):

  Lemma 1.1 If a value type is uniquely represented, equality implies representational equality.

  Lemma 1.2 If a value type is not ambiguous, representational equality
  implies equality.

  If a value type is uniquely represented, we implement equality by testing that both sequences of 0s and 1s are the same. Otherwise we must
  implement equality in such a way that preserves its consistency with the
  interpretations of its arguments.

With the definition of equality in the book being:

  Two values of a value type are equal if and only if they represent the
  same abstract entity. They are representationally equal if and only if their
  datums are identical sequences of 0s and 1s.

Doesn't this imply, that implementing equality by testing for representation equality is impossible for ambiguous value types?
If that is the case, shouldn't the book require a value type to be uniquely represented and unambiguous, in order to implement equality?
If a given value type is ambiguous, one could resolve the ambiguous-ness per contract, such that the comparison checks for equality under the assumption that the passed parameters are never ambiguously refer to different abstract entities, though that would probably not be enforceable at all.

I am probably nitpicking when reading that paragraph :)


texts:
According to the answers in posting it is possible that $\mathsf{VP} = \mathsf{VNP}$ and $\mathsf{P} \neq \mathsf{NP}$ are simultaneously correct.

$\mathsf{VP} = \mathsf{VNP}$ implies $\mathsf{P/poly} = \mathsf{PH/poly}$
(assuming the Generalized Riemann Hypothesis).
This means that $\mathsf{VP} = \mathsf{VNP}$ would
amplify the power of polynomial circuits even if $\mathsf{P} \neq \mathsf{NP}$.

The best known obstruction for $\mathsf{P} \neq \mathsf{BPP}$
comes from circuit related issue for problems in $\mathsf{E}$. However if circuits have more power which is the scenario posed by $\mathsf{VP}=\mathsf{VNP}$, may be the obstruction for $\mathsf{P} \neq \mathsf{BPP}$ is not legitimate anymore.

How does $\mathsf{VP} = \mathsf{VNP}$ amplify the power of randomness?

  If $\mathsf{VP} = \mathsf{VNP}$ were truth then is $\mathsf{P}\neq \mathsf{BPP}=\mathsf{NP}$ most likely scenario?

Are other possibilities such as $$(1)\mbox{ }\mathsf{P}=\mathsf{BPP}\neq \mathsf{NP}\quad \quad(2)\mbox{ }\mathsf{P}=\mathsf{BPP}=\mathsf{NP}\quad\quad(3)\mbox{ }\mathsf{P}\neq\mathsf{BPP}\neq\mathsf{NP}$$ least likely?

Are there any reasons to believe or not believe so?


texts: Circuits with oracles vs. Turing Machines with oracles

texts:
Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for a given oracle Turing machine?

This may be an elementary question, but it is not obvious where to look, and I'm the sort of person who likes to make sure that my foundations are using good-quality mortar. If there is a standard reference, please point me to it. (Papadimitriou's book, for instance, does not seem to describe circuits with oracles at all.)

My working hypothesis is this: a uniform circuit family with access to an oracle (e.g. for solving an NP-complete problem) is defined as follows:

One defines an infinite family of "oracle gates" On , one for each circuit size n, each of which compute a function fn : {0,1}cn → {0,1} for some constant c.
The functions fn computed by the oracle gates On should be  "uniform" in the following sense: for any n < N and x ∈ {0,1}n, we require fn(x) = fN( 0c(N−n) x ) --- that is, the oracle gates must use a consistent and extensbile "encoding" of their inputs.
One then defines a uniform circuit family, where the oracle gates are among the allowed operations to the circuit, restricting the circuit for input size n to use the gate On.

I imagine that some of the choices above may be arbitrarily fixed without losing any generality. What I am interested in is a reference for the correspondence, or at least  a description of how to modify the description above to obtain the standard one.


texts: Is it NP-hard to play international draughts correctly?

texts:
Is the following problem NP-hard?

  Given a board configuration for $n\times n$ international draughts, find a single legal move.

The corresponding problem for $n\times n$ American checkers (aka English draughts) is trivially solvable in polynomial time.  There are three major differences between these two games.

The first and most significant difference is the “flying king” rule.  In checkers, a king may jump over an adjacent opponent's piece into an empty square two steps away in any diagonal direction.  In international draughts, a king may jump over an opponent's piece an arbitrary distance away by moving an arbitrary distance along a diagonal.

As in checkers, the same piece can be used to capture a series of pieces in a single turn.  However, unlike checkers, captured pieces in international draughts are not removed until the entire sequence is over.  The capturing piece may jump over or land in the same empty square multiple times, but it may not jump over an opponent's piece more than once.

Finally, both checkers and international draughts have a forced capture rule: If you can capture an opponent's piece, you must.  However, the rules rules disagree when there are several options for multiple.  In checkers, you may choose any maximal sequence of captures; in other words, you can choose any capture sequence that ends when the capturing piece cannot capture any more.  In international draughts, you must choose the longest sequence of captures.  Thus, my problem is equivalent to the following:

  Given a board configuration for $n\times n$ international draughts, find a move that captures the maximum number of opposing pieces.

It would suffice to prove that the following problem is NP-complete.  (It's obviously in NP.)

  Given a board configuration for $n\times n$ international draughts involving only kings, can (and therefore must) one player capture all her opponent's pieces in a single turn?

The corresponding checkers problem can be answered in polynomial time; this is an entertaining homework exercise.  The problem looks more similar to Demaine, Demaine, and Eppstein's analysis of Phutball endgames; a solution to the entertaining homework exercise appears at the end of their paper.  A solution also appears in the FOCS 1978 paper by Frankel et al. that proves that playing checkers optimally is PSPACE-hard; see also Robson's 1984 proof that checkers is actually EXPTIME-complete.


texts: What percentage of SODA papers are galactic algorithms?

texts: Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. Approximately, what percentage of these algorithms are galactic, in the sense that previously known algorithms are better in all cases where the computation takes less than $10^{100}$ operations or that they are purely existential results with no known construction? We can assume that a reasonable engineering effort is made to implement the algorithms, but no new significant algorithmic advances are made during the implementation.


texts: Honest Majority unconditional coinflipping without private channels

texts:
All communication is assumed to be by the parties

taking turns making authenticated broadcasts.

  Is there a way for $n$ parties, each with access to ideal local randomness, to jointly

  choose a member of  {0,1}  randomly with a distribution that is close to uniform

  even when a small subset of the parties are controlled by a computationally
  unbounded adversary who wants to make that distribution far from uniform?

Regardless of what $n$ is or what "a small subset" means,
the best I've been able to come up with is:

k = parameter
for i in range(k):
 each party outputs a random bit
 if number_of_zeros_outputted < number_of_ones_outputted:
  return 1
 if number_of_ones_outputted < number_of_zeros_outputted:
  return 0
return 0


texts: What's the "smallest" complexity class for which a superlinear circuit bound is known?

texts: Apologies for asking a question that must surely be in a lot of standard references.  I'm curious about exactly the question in the title, in particular I am thinking of Boolean circuits, no depth bound.  I put "smallest" in quotes to allow for the possibility there are multiple different classes, not known to include each other, for which a superlinear bound is known.


texts: The number of words of length $n$ in a context-sensitive language

texts:
Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$.

What is known about $s_{L}(n)$?

Note that it is known that $s_{L}(n)$ is either polynomial, or grows exponentially if $L$ is a context-free language.


texts: Evaluating the multilinearization of an arithmetic circuit?

texts:
Let $p(x_1,\ldots,x_n)$ be a multi-variate polynomial with coefficients over a field $F$. The multilinearization of $p$, denoted by $\hat{p}$, is the result of repeatedly replacing each $x_i^d$ with $d > 1$ by $x_i$. The result is obviously a multilinear polynomial.

Consider the following problem: given an arithmetic circuit $C(x_1,\ldots,x_n)$ over $F$ and given field elements $a_1,\ldots,a_n$, compute $\hat{C}(a_1,\ldots,a_n)$.

Question: Assuming field-arithmetic can be done in unit time, is there a polynomial-time algorithm for this? Added later: I would also be interested in the special case where $C$ is actually a formula (a circuit of fan-out $1$).


texts: I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.


texts: Separation of a preprocessed polyhedron and a plane

texts:
I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

It argues that after we know the best separation of $P_{i}$ and $S$, realized by $r_i$ and $s_i$, we can find the best separation of $P_{i-1}$ and $S$ in $O(1)$ steps. This is done in the following way. We take the plane parallel to $S$ through $r_i$ and cut $P_{i-1}$ into two parts with it. On one side, the closest point to $S$ is $r_i$ and on the other we have an ``elementary'' polyhedron that we can check in $O(1)$ time. My problem is - how do we find this elementary polyhedron? Note that the degree of $r_i$ in $P_{i-1}$ might be unbounded.

In the pdf to prove Thm 5.1 from page 9, they use Thm 3.1 from page 4, which makes the whole thing harder to follow.


texts: An interesting variant of maximum matching problem

texts:
Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$.

Has anybody studied the following variant? For each edge $(u,v) \in M$ , $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$ holds, where c is a constant. We call this constraint a degree-constraint.

The classic constraint is an conjunction on degree with constant 1. The new variant is an disjunction on degree with constant $c$.

The problem on $c=2$ is already $NP-complete$ as shown by Jukka Suomela. I am interested in the potential approximation algorithms. A simple greedy algorithm is selecting maximum star subgraph iteratively until no star subgraph (i.e., no edge(a special star) ) can be selected. But this algorithm performs bad even when $G$ is a tree when $c=3$. There is a inner star whose center has degree $x$, and there are $x$ outer stars each center has degree $x$ and connected to the center of the inner star. The optimum value is $2*x+(x-2)*(x-1)$ by selecting $x-2$ edges from each of $x-2$ outer stars and 2 complete outer stars. The value produced by the greeedy algorithm is $x+1*x$ by selecting the inner star and one edge from every outer star.

The greedy algorithm above is $2\sqrt{n-1}$ approximation, where $n=|V|$. I want to find better approximation algorithm of this algorithm or prove its hardness of approximation.

Furthermore, I want to know the complexity class of this problem in the framework of parameterized complexity. Maybe it bears reasonable fixed parameter algorithm.

Thanks a lot for your comment and answer in advance. :-)


texts: Bounds on the size of the solution of a quadratic program

texts:
I am interested in a quadratic program of the form

$$ \min x^T Q x $$
$$s.t.$$
$$ Ax \leq b $$
where $x$ is a vector with $n$ entries, the size of the maximal entry in $Q, A$, and $b$ is $\varphi$, $A$ has $2^n$ rows, and  $Q$ has $poly(n)$ rows.

Is it true that if there is a minimal solution to the program, then there is one of size that is polynomial in $n$ and $\phi$?

Thanks!


texts: Is this constrained planar triangulation algorithm $O(m \log m)$?

texts:
Background: I am implementing triangle mesh CSG using symbolically perturbed exact arithmetic.  One of the required subalgorithms is retriangulating a triangular face $T_0$ of the input mesh cut by some number of edges defined by intersections between other faces $T_i$.  This reduces to a constrained triangulation problem in the plane.  However, I would like to minimize the degree of the predicates involved, and ideally use only triangle orientation tests where only of the triangle edges is a constraint edge (this has the lowest possible degree when mapped up into 3D).

Concretely, my plane triangulation problem is the following: I have an outer triangle $T$ in the plane, and $n$ constraint segments $S_i$ inside $T$.  The segments may intersect in their interiors; let $m \ge n$ be the number of vertices including the intersection vertices.  I am seeking an $O(m \log m)$ algorithm.

Candidate algorithm: Generate a BSP tree by picking a random input segment $S_i$, dividing the remaining input segments into left and right sets (which will overlap whenever another segment $S_j$ crosses line $S_i$), and recursing.  Triangulate the resulting convex polygons arbitrarily, then incrementally remove all unnecessary points generated by the algorithm (those where segments $S_j$ crosses line $S_i$ but not segment $S_i$).

Question: Has this algorithm or a variant been studied previously?  Is it $O(m \log m)$ time worst case?  Note that the final removal step is not obviously linear time even if only $O(m)$ unnecessary points are generated, so the algorithm could easily be much slower.


texts: Was counting complexity first introduced by Valiant in 1979?

texts:
Was #P first introduced in [1]?

  [1] Valiant, Leslie G. "The complexity of computing the permanent."
  Theoretical computer science 8.2 (1979): 189-201.


texts: Counting subsets of given set with certain properties

texts:
Consider the following problem: Given is a multiset of positive integers, $S$, and an integer $k$.
Count submulisets of $S$ of size $k$, $\{s_1,\dotsc,s_k\} \subseteq S$,
such that when the $s_i$ are ordered increasingly, $s_i \geq i$.

Can this problem be done in polynomial time (polynomial in size of $S$)?

Background: This is a very special case of counting independent subsets of a graph, (which is hard), but I suspect this special case might be solvable via some clever dynamic programming.


texts: An intuitive/informal proof for LP Duality?

texts:
What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of understanding the bound?

The way I was taught Duality only led to one understanding which I am sure is shared by a LOT of people I know: For every corresponding minimization problem there is an equivalent maximization problem that can be derived by inverting the inequality constraints. Period. This  "conclusion" of duality is what seems to stick but not "why is this so" (i.e. how/why is there a bound on the optimal solution).

Is there a way of playing with the inequalities just to 'show' the lower/upper bound on the optimum which could be a motivation for the proof?

I've gone through Chvatal's book as well as a few others but found nothing that could be understood by absolute noobs to LP. The closest that I got was from Vazirani's book on algorithms, where he talks about 'multiplying the inequalities with some magic numbers that show the bound' - I'm not sure how to reproduce the effect for an arbitrary LP.


texts: #2-SAT or 3-SAT and variable that appears most often

texts: Has anyone explored running times of 3-SAT or #2-SAT given by the occurrences of the highest occurring variable?  In other words, if the variable that appears most often appears $x$ times, has anyone been able to give a runtime that is a function of $x$?


texts: Proof for ACYCLIC PARTITION being NP-complete

texts:
I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers.

I'm interested in reading any proof of ACYCLIC PARTITION (Garey and Johnson) being NP-complete, and I'd love it if you could share a proof for the same here. It'd be great if you could also give an approximation algorithm for the problem.

EDIT:

The problem is defined as follows (Garey and Johnson):

Let $G = (V,A)$ be a directed graph, with a weight function $w(v)$ mapping each vertex $v$ to a positive integer, cost function $c(a)$ mapping each edge $a$ to a positive integer, and let there be two positive integers $B$ and $K$.

Is there a partition of V into disjoint sets $V1, V2,..., V_m$ such that the directed graph $G' = (V',A')$, where $V' = \{V1, V2,..., V_m\}$, and $(V_i, V_j)$ is in $A'$ if and only if $(v_i,v_j)$ is in $A$ for some $v_i \in V_i$ and some $v_j \in V_j$, is acyclic, such that the sum of the weights of the vertices in each $V_i$ does not exceed $B$, and such that the sum of the costs of all those arcs having their endpoints in different sets does not exceed $K$?


texts: Bit complexity of factoring univariate polynomial over $\mathbb{Q}$ (rationals)

texts:
What is the bit complexity of finding all the irreducible factors $f_1, ..., f_r$ of a degree-$d$ polynomial $f(x) = \sum_{i=0}^d a_i\cdot x^i \in \mathbb{Q}[x]$ whose all coefficients are $B$-bit values (that is, $-2^B < a_i < 2^B$)?

If I don't mistake:

Berlekamp-Zassenhaus Algorithm solves this in time $O(2^{r-1} \cdot poly(d, B))$, but I don't know the polynomial.
An algorithm by Arnold Schönhage finds these factors in $O(d^8 + d^5 \cdot B^3)$.

Furthermore, I have found some modern papers about this problem, but the bit complexity is not explicit given, instead, they provide the complexity in terms of "LLL switches"...

So, do you know the bit complexity of the best algorithm nowadays?


texts: Maximal subcoalgebras of an $F+1$-coalgebra corresponding to an $F$-coalgebra

texts:
This context of this question is Rutten's Universal Coalgebra, used for modelling systems.
I'm interested in finding a description of a functor between different types of coalgebras
corresponding to finding a certain subcoalgebra.

An $F+1$-coalgebra $\langle S, \alpha: S\to F(S)+1\rangle$ can be thought of as
a system whose transition shape is given by functor $F$ plus the possibility of an error/termination,
given by the $+1$. Assume that $F$ is a so-called Kripke polynomial functor: $F::=Id ~|~ B ~|~ F+F ~|~ F\times F ~|~ F^ A ~|~ \mathcal{P}_\omega F$, thus it preserves pullbacks.

A subcoalgebra of $\langle S, \alpha: S\to F(S)+1\rangle$ is coalgebra $\langle S', \alpha': S'\to F(S')+1\rangle$, where $S'\subseteq S$ and $\alpha'$ is $\alpha$ restricted to $S'$, such that its range falls withing $F(S')+1$.

I want to find the maximal subcoalgebra of this coalgebra which corresponds to an $F$-coalgebra. In terms of my application, this means I'm looking for the subset of states $S'\subseteq S$ that do not lead to the error state.

Clearly, I can take the pullback of the functions $\alpha: S\to F(S)+1$ and
$\mathit{inl}:F(S)\to F(S)+1$ to get a set $S_0\subseteq S$ which do not lead
to an error in the first step. Iterating this process for functors $F^i+1$ seems to lead to progressively smaller subsets $S_i$ of $S$ each avoiding the error state
for $i$ steps. What I'm lacking is a coherent description of the process.

Is whether there is a more universal description of this construction in terms of limits or colimits, or at least, some known approaches to the problem?