texts:
Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and
 $W=
\begin{bmatrix}
w_1[\vec{x}_1]\\
\vdots\\
w_n[\vec{x}_n]\\
\end{bmatrix}$
where $w_i$ is an $m$-dim row vector  each entry of which is a  linear function over $\vec{x}_i$.  Given $d\in \mathbb{R}^m$, we define
 $\max Wd=
\begin{bmatrix}
\max_{\vec{x}_1 \in \Theta_1} w_1[\vec{x}_1] \cdot d\\
\vdots\\
\max_{\vec{x}_n \in \Theta_n} w_n[\vec{x}_n] \cdot d\\
\end{bmatrix}$

Clearly
$A=\{\max Wd\mid d\in \mathbb{R}^m\}$ is not a linear space (see example below).

The question is to compute a basis of the linear space spanned by $A$?

Eample:
Let $W=[ x\  y]$ and $\Theta_1=\{0\leq x\leq 1, 0\leq y\leq 1, x+y=1\}$. (In this case $n=1$ and $m=2$). Then

for $d=[1\  0]^T$, we have $\max Wd= [1]$;
for $d=[ 0\ 1]^T$, we have $\max Wd= [1]$;
for $d=[1\ 1]^T$, we have $\max Wd= [1]$.

In this case $A=\mathbb{R}$.

The motivation of the problem is from geometry and an interesting feature here is that the optimization is involved which makes the problem unusual.


texts:
Problem: transform an array $A$ of $n$ natural numbers (of $t$-bits) into an array $B$, which is a permutation of $\{1, ..., n\}$ with the property that, whenever $B[i] \leq B[j]$ holds, $A[i] \leq A[j]$ holds. Call this operation "scaling".

For instance:

A = 7 7 2 5 9
B = 3 4 1 2 5
B = 4 3 1 2 5 -- a second "non stable" possibility

Assuming $n$ can be represented in $t$ bits, is there a way of scaling an array in place?

The time and space complexity should be as close to $O(n)$ and $O(1)$ as possible, with a $O(\log n)$ factor being probably acceptable.

A. Maus, IPS, sorting by transforming an array into its own sorting
permutation with almost no space overhead, solves a related problem; but it seems that the method approaches standard bucket sorting, requiring $O(n)$ space, as $\log_2 n$ approaches $t$.


texts: What is the complexity of (possibly succinct) Nurikabe?

texts:
Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid which is to be filled with on/off values for each cell, with each number indicating a region of connected 'on' cells of that size, and some minor constraints on the region of 'off' cells (it must be connected and can't contain any contiguous 2x2 regions). The Wikipedia page has more explicit rules and sample puzzles.

Generically, puzzles of this sort tend to be NP-complete, and Nurikabe is no exception; they fall into NP because the solution itself serves as a (polynomially-verifiable) witness to the problem.  But unlike most similar puzzles, Nurikabe instances might be succinct: Sudoku on an $n\times n$ grid requires $\Theta(n)$ givens to be solvable (if less than $n-1$ givens are offered, then there's no way of distinguishing between the missing symbols), Nonograms obviously require at least one given for each row or column, and Minesweeper must have givens on at least $1\over16$ of the cells or there will be cells not next to a given (and whose status therefore can't be determined).  But while the givens of a Nurikabe puzzle have to sum to $\Theta(n^2)$, it's possible to have $\mathrm{O}(1)$ givens each of that size, so that $\Theta(\log(n))$ bits might be enough to specify a Nurikabe puzzle of size $n$ - or inverting, $k$ bits may be enough to specify a Nurikabe instance of size exponential in $k$, meaning that the only guarantee is that the problem lies in NEXP.

Unfortunately, the proofs of Nurikabe's hardness I've found all use constructions with $\Theta(n^2)$ givens of constant size, so their instances are polynomial in the grid size rather than logarithmic, and I can't rule out that all solvable 'succinct' Nurikabe puzzles have additional structure such that solutions can be described and verified just as succinctly; for instance, the one example I know of a puzzle with 2 givens of size $\Theta(n^2)$ leads to regions of both on and off cells that are each the union of $\mathrm{O}(1)$ rectangles, and so have a succinct description of their own.  Does anyone know of additional research that's been done into this puzzle beyond the basic NP-completeness result, and in particular any further complexity results for the possibly-succinct cases?

(note: this was originally asked over at math.SE, but there haven't been any answers there yet and this seems appropriately research-level for this site)


texts: Delocalization of eigenvectors in Expanding Graphs

texts:
Given an adjacency matrix $A$, can we say something about whether the eigenvectors corresponding to its highest (or second-highest) eigenvalues are de-localized ?

By de-localization I mean that every coordinate in the vector has nearly the same absolute value. Are there existing results regarding this for expanders?


texts: Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain

texts:
The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of infinite words, and finite words over $\Sigma$. The book is concerned with Type-2 computability, which defines computability over infinite words. Then a function $f : \subseteq \Sigma^{\omega} \to \Sigma^{\ast}$ is called computable iff there exists a Turing machine reading its input on a read-only tape from left to right (without going back), and outputting symbols on its output tape without the ability to go back, i.e. what is written once could not be erased. This is called Type-2 computability (or a Type-2 machine).

  Statement: A function $f :\subseteq \Sigma^{\omega} \to \Sigma^{\ast}$ is computable, iff $f = h_{\ast}$ for some computable function $h :\subseteq \Sigma^{\ast} \to \Sigma^{\ast}$ with prefix-free domain.

  Proof: Let $M$ be a Type-2 machine computing $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$. Define $h :\subseteq \Sigma^{\ast} \to \Sigma^{\ast}$ by
  $$
 h(w) := \left\{\begin{array}{ll} f(w0^{\omega}) & \mbox{if on input $w0^{\omega}$ the machine $M$ halts after exactly $|w|$ steps} \\
     \mbox{div} & \mbox{otherwise.} \\
 \end{array}\right.
$$
  Then $h$ is computable, has prefix-free domain and satisfies $f = h_{\ast}$. [...]

I am unsure about $f = h_{\ast}$. Surely if $h_{\ast}(p) = u$, then $h(w) = u$ for some $w \in \mbox{dom}(h)$ with $w \sqsubseteq p$. By the defintion of $\mbox{dom}(h)$ this mean the machine halts on $w0^{\omega}$ in exactly $|w|$ steps, hence has read at most $|w|$ symbols, and thereby exhibiting the same behavior on $p$, i.e. we have $f(p) = u$.

But now I want to show that if $h_{\ast}(p)$ diverges, then $f$ diverges too, or, giving the same, that if $f(p) = u$ then $h_{\ast}(p) = u$. But for example suppose $f(p) = u$, and let $k$ be the steps taken by the machine reading $p$ to halt and produce $u$, then surely the prefix $v$ of $p$ read in this process has at most length $k$. But as $|v| < k$ is possible, we could not conclude that $v \in \mbox{dom}(h)$, but by padding $v$ with zeros we know $v0^{k - |v|} \in \mbox{dom}(h)$ by definition, and hence $h_{\ast}(v0^{\omega}) = h(v0^{k - |v|})$ so that $f(p) = h_{\ast}(v0^{\omega})$. But this is all I get, I do not see how to conclude $h_{\ast}(p) = f(p)$, as this would mean we have some prefix $x$ from $p$ such that the machine takes exactly $|x|$ steps in producing $u$, but in general we cannot conclude that $v0^{k - |v|}$ is a prefix of $p$ if $k - |v| > 0$.

So why does this result holds? And why $h_{\ast} = f$?


texts: The best known upper bound for two-way probabilistic finite automata with one-counter

texts:
It is known that the class of languages recognized by two-way deterministic finite automata with one-counter (2D1CAs) is a proper subset of $ \mathsf{L} $ (deterministic log-space):
A 2D1CA can run at most $ O(n^2) $ steps if it halts on a given input, and there is a language in $ \mathsf{L} $, i.e.
\begin{equation}
\mathtt{DG} = \lbrace w_0 \$ w_1 \$ \cdots \$ w_k \mid k \geq 1, w_{i \in \lbrace 0, \ldots, k \rbrace} \in \lbrace a,b\rbrace^* , \mbox{ and }  w_0=w_i \mbox{ for some }  1 \leq  i  \leq k \rbrace,
\end{equation}
which cannot be recognized by any 2D1CA (Duris and Galil, 1982).

What happens if such an automaton can use a coin?

More precisely, what is the best known upper bound for the class of languages recognized by two-way probabilistic finite automata with one-counter (2P1CAs) with bounded error?


texts: Algorithm for ranking members of a regular language?

texts:
A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines any string in the language and has the property that, for some lexicographic ordering, $s_1 < s_2 \implies rank(s_1) < rank(s_2)$. Another property is that given $rank(s_0)$ we can efficiently determine $s_0$ using an 'unrank' algorithm.

However, the paper wasn't very specific and I don't know where to find a more detailed description of the algorithm. Can anyone point me in the right direction?

I remember that it involves compiling a regular expression to a DFA and giving the description of the DFA to the ranking algorithm.

Thanks for your help.


texts: Reduction from independent set in hypergraphs to independent set in graphs

texts:
Let me introduce my notations.

IS-H :

Input : an hypergraph $G=(V,H)$, an integer $k$
Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and for all $h\in H$, $h \nsubseteq S$ ?

I denote IS the same problems in graphs.

I know that $IS-H \le_{karp} IS$ as $IS-H \in NP$ and $IS$ is $NP-hard$, but I need an explicit reduction to compute an explicit bound on the size of the obtained instance of $IS$. I have such a reduction in mind but I would prefer to cite an existing one (any "natural" reduction is ok for me, as I don't need to tune the constant in the size of the obtained instance).

Do you know if such a reduction is made explicit somewhere ?
Thank you in advance


texts: Delaunay Triangulation of Parallelepiped

texts: Given $n$ linearly independent vectors $v_1, v_2, \ldots, v_n$ in $n$-dimensional space. Let $V$ be the set of $2^n$ points of the form $x_1 v_1 + x_2v_2 + \ldots + x_nv_n$, in which $x_i$ can be $0$ or $1$. $V$ is the set of vertices of an n-dimensional parallelepiped. Is there any way to find the Delaunay triangulation of $V$ using subexponential space with respect to $n$? I understand that the size of the output is big, and we can't store the whole output. But is there any way to output the Delaunay edges one by one without storing the previous result?


texts:
It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, planar graph isomorphism) run in $O(n^k)$ where $k$ is insanely large.

I am looking for examples of natural problems that are known to be solvable simultaneously in deterministic logspace and $O(n^k)$ time where $k \leq 10$. There is nothing special about 10. Looking at the currently known logspace algorithms, I think $k \leq 10$ is interesting enough.
Aleliunas et al. showed that undirected st-connectivity is in $RL$ (randomized logspace). The running time of their algorithm is $O(n^3)$. Are there natural problems that can be solved simultaneously in $RL$ and linear time (or) near linear time i. e., $O(n{\log}^i{n})$ time ?

Edit : To make things more interesting let's look at problems that are at least $NC^1$-hard.


texts:
I was reading this paper by A. Schrijver on "Finding k disjoint paths in directed planar graphs".

First they describe what are cohomologous functions on a graph. My interpretation of this definition is as follows: Suppose you have a function $\phi: A \rightarrow G$, then you can extend this function to a group homomorphism $\widetilde{\phi}: \pi_1(D, r) \rightarrow G$ as:
$$l = (r \xrightarrow{a_1} v_1 \xrightarrow{a_2} v_2 \rightarrow \cdots \xrightarrow{a_{n-1}} v_{n-1} \xrightarrow{a_n} r) \mapsto \phi(a_1)\phi(a_2) \ldots \phi(a_n)$$

Now cohomologous functions just identifies all these homomorphisms, that is $\phi, \psi$ are cohomologous iff $\widetilde{\phi} = \widetilde{\psi}$.

Next they define homologous functions on a graph. I think two functions are homologous if for any vertex on the boundary of outer face, the net flow passing through it remains the same for both the functions.

(The net flow passing through a vertex is defined as $\phi(a_1)^{\epsilon_1}\phi(a_2)^{\epsilon_2} \cdots \phi(a_n)^{\epsilon_n}$ in the clockwise order)

This can be seen by considering the dual graph and then observing that two functions are homologous on a planar graph iff they are cohmologous on the dual graph, as mentioned in the paper, and that any loop at $r$ corresponds to net flow at a corresponding boundary vertex (as I have tried to demonstrate in the picture below).

I am not sure if my interpretation for this homologous functions is correct.
The author mentions in the beginning of the paper that, this tool gives us a convenient way to "record shift of curves over the plane". I don't see how that follows.
Why is the outer face special for this algorithm? Couldn't we have fixed any face $F$ to begin with and consider functions with $f(F)=1$, as opposed to $f(R)=1$?

Any help would be really appreciated.


texts: How is SDP an extension of spectral algorithms?

texts:
In one of his lectures, Uri Feige described semidefinite programming (SDP) as

  ... an algorithmic technique that extends both linear programming and spectral algorithms.

I know the basic definition of SDP and understand it as linear programming extended by the possibility of saying "take these variables, arrange them into a matrix. Now, the matrix has to be positive semidefinite". Is this interpretation correct/useful? How is this an extension of spectral algorithms?


texts: A Question on Convex Conjugate Duality for KL Divergence

texts:
The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as
$$f^*(x^*):=\sup_{x\in X} ~\langle  x, x^*\rangle-f(x),$$ where $X^*$ is the topological dual of $X$ and $\langle\cdot, \cdot\rangle$ is dual pairing between $X$ and $X^*$.

The relative entropy (aka Kullback-Leibler divergence) $D(\cdot||Q):\mathcal{P}(X)\mapsto \mathbb{R}^+$, is defined for two probability measures $P$ and $Q$ (P<< Q)  as
$$D(P||Q)=\int_XdP \log\frac{dP}{dQ}.$$

I have been trying to calculate the convex conjugate of map $P\mapsto D(P||Q)$ but I have failed. I know that the answer is $\log \mathbb{E}_{Q}[e^{f}]$ where $\mathbb{E}_Q[\cdot]$ is the expectation operator with respect to probability measure $Q$.


texts: Is the problem NP-C or polynomially solvable?

texts:
I am considering a problem of the following: Given a set $X$ of integers and another integer B, are there two subsets of $X$, say $X_1$ and $X_2$, such that $X_1-X_2=B$ ? (Here, $X_i$ also denotes the sum of integers in the set $X_i$)

I wonder whether this problem is solvable in polytime or NP-complete? Thanks.


texts: Algorithm for choosing unique items from a collection of sets of items

texts:
I have a number of sets, each containing items with a numerical value and a string.

I want to choose one item out of each set, so that:
1. the strings of the chosen items form a set (i.e. the strings are not equal to any of the strings from the other chosen items)
2. the numerical values of the chosen items are as high as possible

It is not always possible to satisfy 1., e.g. two sets may contain only one item each, both with the same string. When not possible to satisfy 1., the optimal solution is the one that is closest to satisfy 1., 2. is not as important.

How do I find the optimal solution? Are there any widely known algorithms for performing this or something similar?


texts: Are a few hundred reduction steps too many to get the normal form of Y fac ⌜3⌝?

texts:
As I have been teaching the basis of λ-calculus lately, I have implemented a simple λ-calculus evaluator in Common Lisp. When I ask the normal form of Y fac 3 in normal-order reduction, it takes 619 steps, which seemed a bit much.

Of course, each time I did similar reductions on paper, I never used the untyped λ-calculus, but added numbers and functions operating on them. In this case, fac is defined as such:

fac = λfac.λn.if (= n 0) 1 (* n (fac (- n 1)))

In this case, considering =, * and - as currying functions, it only take approximately 50 steps to get Y fac 3 to its normal form 6.

But in my evaluator, I used the following:

true = λx.λy.x
false = λx.λy.y
⌜0⌝ = λf.λx.x
succ = λn.λf.λx.f n f x
⌜n+1⌝ = succ ⌜n⌝
zero? = λn.n (λx.false) true
mult = λm.λn.λf.m (n f)
pred = λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)
fac = λfac.λn.(zero? n) ⌜1⌝ (* n (fac (pred n)))
Y = λf.(λf.λx.f (x x)) f ((λf.λx.f (x x)) f)

In 619 steps, I get from Y fac ⌜3⌝ to the normal form of ⌜6⌝, namely λf.λx.f (f (f (f (f (f x))))).

From a quick skimming of the many steps, I guess it's the definition of pred that warrants such a long reduction, but I still wonder if it just may be a big nasty bug in my implementation...

EDIT: I initially asked about a thousand steps, some of a which were indeed caused a incorrect implementation of the normal order, so I got down to 2/3 of the initial number of steps. As commented below, with my current implementation, switching from Church to Peano arithmetic actually increases the number of steps…


texts:
The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater than the sum $\sum_i \sqrt{b_i}$.  The complexity status of this problem is open; see this post for further details.  This problem arises naturally in computational geometry, especially in problems involving Euclidean shortest paths, and is a significant stumbling block in transferring algorithms for those problems from the real RAM to the standard integer RAM.

Call a problem Π sum-of-square-roots-hard (abbreviated Σ√-hard?) if there is a polynomial-time reduction from the sum of square roots problem to Π.  It is not hard to prove that the following problem is sum-of-square-roots-hard:

  Shortest paths in 4d Euclidean geometric graphs

  Instance: A graph $G=(V,E)$ whose vertices are points in $\mathbb{Z}^4$, with edges weighted by Euclidean distane; two vertices $s$ and $t$

  Output: The shortest path from $s$ to $t$ in $G$.

Of course this problem can be solved in polynomial-time on the real RAM using Dijkstra's algorithm, but each comparison in that algorithm requires solving a sum-of-square-roots problem.  The reduction uses the fact that any integer can be written as the sum of four perfect squares; the output of the reduction is actually a cycle on $2n+2$ vertices.

What other problems are sum-of-square-roots-hard?  I'm particularly interested in problems for which there is a polynomial-time solution on the real RAM.  See
my previous question for one possibility.

As Robin suggests, boring answers are boring.  For any complexity class X that contains sum-of-square-roots (for example, PSPACE or EXPTIME), every X-hard problem is boringly  sum-of-square-roots-hard.


texts: What is the correct name for the space of genotypes and fitness?

texts:
I'm looking for a formal definition of the space that consists of the dimensions gene 1-N and the fitness.

In literature there is often the search space mentioned, but it only contains all genes. If I extend the search space by the fitness dimension, how can I call this space?


texts: Theoretical explanations for practical success of SAT solvers?

texts:
What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together?

By analogy, the smoothed analysis (arXiv version))for the simplex algorithm does a great job explaining why it works so well in practice, despite the fact that it takes exponential time in the worst case and is NP-mighty (arXiv version).

I have heard a little bit about things like backdoors, structure of the clause graph, and phase transitions, but (1) I don't see how these all fit together to give the larger picture (if they do), and (2) I don't know whether these really explain why SAT solvers work so well, for example, on industrial instances. Also, when it comes to things like structure of the clause graph: why is it that current solvers are able to take advantage of certain clause graph structures?

I only find the results about phase transitions partially satisfying in this regard, at least in my currently limited understanding. The phase transition literature is about instances of random k-SAT, but does that really explain anything about real-world instances? I don't expect real-world instances of SAT to look like random instances; should I? Is there a reason to think phase transitions tell us something, even intuitively, about real-world instances even if they don't look like random instances?

Related questions that help, but don't completely answer my question, particularly the request for tying things together into a coherent picture:

Why is there an enormous difference between SAT solvers?
Which SAT problems are easy?
What's the correlation between treewidth and instance hardness from random 3SAT?


texts: What is the significance of the word "combinational" in combinational logic?


texts: Some examples of tools to demonstrate problem is in $NC$

texts:
Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no complete problems.
What are some of the known techniques to show a problem is in $NC$?
For example reducing to determinants is one way since there is an $NC$ algorithm for determinants. Every attempt to show perfect matching is in $NC$ is through a reduction to determinant by derandomizing isolation lemma.


texts: Relating univalence for a theory of cateogries to the skeleton concept

texts:
Say I work in homotopy type theory and my sole objects of study are conventional categories.

Equivalences here are given by functors $F:{\bf D}\longrightarrow{\bf C}$ and  $G:{\bf C}\longrightarrow{\bf D}$ which provide equivalences of categories ${\bf C} \simeq {\bf D}$. There exist natural isomorphisms $\alpha:\mathrm{nat}(FG,1_{\bf C})$ and $\beta:\mathrm{nat}(GF,1_{\bf D})$ so that this functor and "inverse" functor are transformed to unit functor.

Now univalence relates equivalences to the identity type ${\bf C}={\bf D}$ of the intentional type theory I have chosen to talk about categories. Since I only deal with categories and those are equivalent if they have isomorphic skeletons, I wonder if I can express the univalence axiom in terms of passing to the skeleton of the categories.

Or, otherwise, can I define the identity type, i.e. the syntactic expression
${\bf C}={\bf D}:=\dots$
in a way which essentially says "there is a skeleton (or isomorphi) and ${\bf C}$ and ${\bf D}$ are both equivalent to it."?

(In the above I try to interpret the type theory in terms of concepts which are easier to define - the category theoretical notions. I think about this because morally, it seems to me that the axiom "corrects" intentional type theory by hard-coding the principle of equivalence, which is already a natural part of the formulation of category theoretical statements, e.g. specifying objects only in terms universal properties.)


texts: More legent proof of MIP=NEXP using the PCP theorem

texts:
Can we prove $\mathsf{MIP}=\mathsf{NEXP}$ using the PCP theorem $\mathsf{NP}=\mathsf{PCP(log(n),O(1))}$ as a shortcut?

$\mathsf{MIP}$ is the class of languages with multi-prover interactive proof systems.

Here is what I know:

Intuitively, it's hard for me to see how another prover adds any power to the protocol. The only way I can think of is to somehow make the two provers contradict each other to easily detect false positives.

I have come across the implication that $\mathsf{NEXP}=\mathsf{PCP}(n^{O(1)},O(1))$ and tried to use it, but I fail to understand why the following protocol doesn't work for a single prover:

ask the prover for the length of the exponential certificate.
repeat C times: (for some constant C which we know exists due to the above theorem).

generate a random index to the certificate and ask the prover to hand over the bits from the given location.
verify that the certificate is still valid, otherwise reject.

after C successful queries - accept.

Obviously there is some defect in this protocol because $\mathsf{IP}=\mathsf{PSPACE}$ and it has not been proven that $\mathsf{PSPACE}=\mathsf{NEXP}$ (which would be implied if the protocol is correct).

Also the following paper seems relevant:

Laszlo Babai, Lance Fortnow and Carsten Lund, "Nondeterministic exponential time has two-prover interactive protocols", 1990.

Note:

The question was a homework but was posted more than a year ago.


texts:
Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, check whether they are isomorphic or not. There are different ways to input a group, the two mostly used are by a Cayley table and by a generating set. Here I am assuming input groups are given by their Cayley table.  More formally:

$\textbf{Group Isomorphism Problem}$

$\textbf{Input : }$ Two groups $(G,\cdot)$ and $(H,\times)$.

$\textbf{Decide : } $ Is $G \cong H$?

Let us assume that $n = |G| = |H|$

Group Isomorphism problem when input groups are given by Cayley table is not known to be in $\textbf{P}$ in general. Although there are group classes like the abelian group class for which the problem is known to be in polynomial time, groups which are the extension of an abelian group, simple groups etc. Even for nilpotent class two groups, no algorithm better than brute force is known.

A brute force algorithm for group isomorphism is given by Tarjan, which is as follows. Let $G$ and $H$ are two input groups, and let $S$ be a generating set of the group $G$. It is a well-known fact that every finite group admits a generating set of $\mathcal{O}(\log n)$ size and which can be found in polynomial time. The number of images of the generating set $S$ in the homomorphism from $G$ to $H$ is $n^{\log n}$ many. Now, check whether each possible homomorphism is bijective or not. The overall runtime will be $n^{\log n + \mathcal{O}(1)}$.

Let me first define the center of the group $G$:

$$Z(G) = \{g \in G \mid ag=ga, \forall a \in G\}$$

$Z(G)$ denotes the elements of the group $G$ which commutes with all other elements of the group $G$. Groups for which $G/Z(G)$ ( / used for quotient) is abelian are known as a nilpotent class two groups. To me it appears that nilpotent class two groups are the hardest instances to solve the group isomorphism problem. The meaning of "hardest instances" is: solving that case will allow researchers who work in group theory to solve the isomorphism problem of a large number of groups.

Initially, I thought that simple groups are the hardest instances as they are building blocks of all groups, but later came to know that the isomorphism problem for simple groups is in $\textbf{P}$.

Question:  What is the hardest instance for the group isomorphism problem?


texts:
I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ contains all of the positive and none of the negative points; by assumption, the sample admits at least 1 consistent triangle).

The best they (or I) could do is an algorithm that runs in time $O(m^6)$, where $m$ is sample size. Can anyone do better?


texts: How to determine whether a proof requires "higher-order reasoning techniques"?

texts:
The question:

Suppose I have a specification of a problem consisting of axioms and a goal (i.e. the associated proof problem is whether the goal is satisfiable given all the axioms). Let us also assume that the problem does not contain any inconsistencies/contradictions among the axioms.
Is there a way to determine in advance (i.e. without first constructing a full proof) that proving the problem will require "higher-order reasoning"?

By "higher-order reasoning", I mean applying proof steps which require higher-order logic to be written down. A typical example for "higher-order reasoning" would be induction: Writing down an induction scheme in principle requires using higher-order logic.

Example:

One can specify the proof problem "Is addition on two natural numbers commutative?" using first-order logic (i.e. define natural number via constructors zero/succ along with standard axioms, together with axioms that recursively define a "plus" function). Proving this problem requires induction on the structure of either the first or the second argument of "plus" (depending on the exact definition of "plus"). Could I have known this before attempting to prove it, e.g. by analyzing the nature of the input problem...? (Of course, this is just a simple example for illustration purposes - in reality, this would be interesting for more difficult proof problems than commutativity of plus.)

Some more context:

In my research, I frequently try to apply automated first-order theorem provers like Vampire, eprover etc. to solve proof problems (or parts of proof problems), some of which may require higher-order reasoning. Often, provers require quite some time to come up with a proof (provided there is a proof which only requires first-order reasoning techniques). Of course, trying to apply a first-order theorem prover to a problem that requires higher-order reasoning typically results in a timeout.

Therefore, I have been wondering whether there are any methods/techniques which can tell me in advance whether a proof problem will require higher-order reasoning techniques (meaning "don't waste time trying to hand it to a first-order theorem prover") or not, at least maybe for particular input problems.

I looked in the literature for an answer to my question and asked some fellow researchers from the area of theorem proving about that - but so far, I didn't receive any good answers. My expectation would be that there is some research on that topic from people who try to combine interactive theorem proving and automated theorem proving (Coq community? Isabelle community (Sledgehammer)?) - but so far, I could not find anything.

I guess that in general, the problem I outlined here is undecidable (is it?). But maybe there are good answers for refined versions of the problem...?


texts:
Is the following decision problem NP-complete:

  Let $G$ be an undirected graph and $b \le c$
  two integers. Is it possible to
  select for every vertex of $G$ exactly
  $b$ different neighbors such that no
  node is chosen more then $c$ times.

The case $b = 1$ can be solved for any $c$ in polynomial time using maximal matching.

Motivation: Each node wants to place $b$ backups at different neighbors, but each node has only capacity to store $c$ backups.


texts: Finding a point outside of each of a set of polygons in a bounded space

texts: I know there are algorithms for finding a point inside a simple polygon.  Given a set of polygons inside a rectangle (think a bunch of polygons on a computer screen), is there an efficient algorithm for finding a point that is inside the rectangle but not inside any of the specified polygons?  (Note that these polygons don't overlap, but may share a common border (or part of a border).)


texts: Three Clique Sums of Bounded Treewidth and Bounded Genus graphs

texts:
This question asks about the forbidden minors of the class of graphs that can be formed by taking three clique sums of planar graphs and bounded treewidth graphs(The class is defined for some constant $t$), if there is a forbidden minors set for the class with all graphs have crossing number at most one.
A reverse of the statement is known from Robertson and Seymours graph minor theory, that for any graph $H$ with crossing number at most one, there exists a constant, say $t$, such that any $H$ minor free graph can be written as a three clique sum of planar graphs and graphs with treewidth $\leq t$.
I want to ask a similar question for bounded genus graphs, that is, if $C$ is a class of graphs that can be expressed as three clique sums of bounded genus and bounded treewidth graphs, what can we say about the forbidden minors of the class? (It is a finite set since $C$ is minor closed right?)


texts: Equilvalence among two Scheduling problems

texts:
I have two problems for scheduling:

Packets arrive at a router. Router schedules them i.e. router determines which one will go out first and which one last. Here, the problem is which packet to send first and which to last.
Packets arrive to a scheduler and it decides which packet will go out on which path. Here, the problem is to choose between paths -- which we call scheduling.

Is there any equivalence between the two problems ?

What do I mean by equivalence : Like consider a FIFO scheduling policy in 1. Is there any policy for problem 2 that can be fundamentally called similar to FIFO policy in 1 ?

Is there any transformation from a solution of problem 1 to 2 ?


texts: Where can I find an elementary small-step structural operational semantics for closures?

texts:
Lexical closures are an implementation technique in languages with first-class functions.

I'm interested in a simple operational description of function closures. Does anyone know of such a description?


texts: What if a problem is both in $\Pi_2^p$ and $NP$-hard?

texts:
If a problem $P$ belongs to both $\Pi_2^p$ and $NP$-hard (thanks to some reduction from a $NP$-complete problem) but not to $NP$, does it imply that $P$ is $\Pi_2^p$-complete?

If the answer is no, are there some problems with these properties which have not been shown to be $\Pi_2^p$-complete?


texts: Compiler Optimization: How do you automatically fuse conditionals into the loop index?

texts:
Let's say that you have some loop

for(i=0;i<n;i++){
    if(i > 3 && i < 8){ p(i); }
}

How would I go about automatically fusing that into

for(i=4;i<8;i++){
    p(i);
}

How about

for(i=0;i<n;i++){
    if(isodd(n)){p(i);}
}

To

for(i=1;i<n;i+=2){
    p(i);
}

And for the final challenge, fuse

for(i=0;;i++){
    if((i>>2)%2 == 0){ p(i); }
}

To

for(i=0;;i+=8){
    for(j=0;j<4;j++){ p(i+j); }
}

I'm not asking how to do this by hand. I want the compiler to figure out how to do this. I have a gut feeling like this is some well known problem, I just don't know what name it has, or even how I'd google for it.


texts: Drawing graphs of bounded crossing number

texts:
Fáry's theorem says that a simple planar graph can be drawn without crossings so that each edge is a straight line segment.

My question is whether there is an analogous theorem for graphs of bounded crossing number.  Specifically, can we say that a simple graph with crossing number k can be drawn so that there are k crossings in the drawing and so that each edge is a curve of degree at most f(k) for some function f?

EDIT: As David Eppstein remarks, it is readily seen that Fáry's theorem implies a drawing of a graph with crossing number k so that each edge is a polygonal chain with at most k bends.  I'm still curious though whether each edge can be drawn with bounded degree curves.  Hsien-Chih Chang points out that f(k) = 1 if k is 0, 1, 2, 3, and f(k) > 1 otherwise.


texts: How to generate a permutation uniformly by repeating using an one-bit uniform random generator?

texts:
If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}.

I have a solution:  run the one-bit random generator n*n times to decide if each pair of elements will be exchanged.

The complexity is O(n*n).

I want to know if there more efficiency solution? What is the lower bound for this problem?


texts: The SQ argument in Balazs Szorenyi's paper

texts:
I am asking about the proof in Theorem 5 (page 6) of this paper,
http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf
Quite a few things about this short argument seem unclear to me,

Towards the bottom of page 3 when the SQ oracle was defined it seemed that for a tolerance parameter of $\tau$ and the true concept being $f^*$ and a query concept of $h$ the SQ oracle is guaranteed to return a $c$ s.t $\vert c - \langle f^*,h \rangle \vert \leq \tau$. Now in the proof of Theorem 5 (page 6) there is no $f^*$ that has been mentioned! So is there an implicit assumption about what this $f^*$ is?
Are we assuming that this $f^*$ is a part of this uncorrelated set, $\{f_1,f_2,..,f_d\}$?

The argument in Theorem 5 seems to assume that the adversarial oracle can return $c=0$ always. But why should this be a consistent option given that the oracle is forced to satisfy the condition, $\vert c - \langle f^*,h \rangle \vert \leq \tau$. If $c=0$ has to always be a consistent oracle reply then we need it to be true that all queries $h$ being made are such that it satisfies the equation, $\vert\langle f^*,h \rangle \vert \leq \tau$. But now this is a new constraint that the queries $h$ have to be of somewhat low correlation with the truth $f^*$!. But this wasnt specified anywhere!
At this point it seems that the algorithm could be lucky and it could send to the Oracle the query $h = f^*$ and then if $c=0$ has to be a valid adversarial reply we need $\tau \geq 1$ and that doesnt make sense!

Lastly what else is the SQ algorithm allowed to do apart from making $(h,\tau)$ SQ-queries? Are we forcing it to work s.t after it receives $c=0$ as the Oracle reply all its allowed to do is to eliminate from its set of probable outputs those functions in the set $\{f_1,..,f_d\}$ which are more than $\tau$ correlated? Why is it that the SQ algorithm never seems to consider that there could be functions in ${\cal F}$ outside this uncorrelated set which are also more than $\tau$ correlated to the query $h$?


texts:
I am wondering if there is a good way to complete the following analogy:
monad : Kleisli category :: applicative functor : ??

That is, a given monad T on a category C gives rise to its Kleisli category C_T, whose objects are those of C, but whose morphisms between A and B are the morphisms between A and T(B) in C (Wikipedia entry). What I'd like to know is if there is a kind of "equivalent" notion for applicatives.
At first blush, it seems that such a category would be constructed in the following way, given a category C and an applicative functor (F : C -> C, pure, (<*>)). The category C_F is the one whose objects are taken from C (as above), but whose morphisms between A and B are in one-to-one correspondence with the morphisms between 1 and F(B^A) in C - that is, "elements" of F(B^A). In addition, identities and composition are given by:
id_(C_F)_A = pure id_C_A

f o_(C_F) g = pure (o_C) <*> f <*> g

where id_X_A is the identity on A in category X, and (o_X) is composition between morphisms in X.


texts: Topics from theoretical computer science suitable for a bachelor thesis?

texts:
this is my first question, so please be patient :) My question in particular:
Is the field of theoretical computer science so complex, that it is just "too much" for a bachelor thesis? Unfortunately I haven't found any old thesises because the relevant chair of the university hasn't been occupied for years.

Because of theoretical computer science is the only topic that really interests me, I thought of writing my bachelor thesis in this field.
What would be suitable topics or at least fields that can be arranged in the limited focus of a bachelor thesis?
I thought of topics like parametrized complexity or formal software verfication (which is actually a bit of the target)

Best regards


texts: How does inheritance differ from subtyping?

texts: In programming language perspective, what is mean by subtyping? I heard that "Inheritance is not Subtyping". Then what are the differences between inheritance and subtyping?


texts: Complexity class of a subset problem similar to subset sum

texts:
What could be the complexity class of the following problem:
Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' \subset S : \sum{S'} = K$ such that the elements of $S'$ form an arithmetic series with difference $d$ and $a = x_1$. So $S' = \{x_1, x_2 ..., x_n\}$ $: x_{i+1} = x_i + d$ for $2 \le x_i \le n$.

The problem is in NP, since given a solution set $A$ it is possible to check in polynomial time if $\sum{A} = K$.

The regular [0,1] Knapsack Problem and Subset Sum problem are NP complete and initially I figured this being similar would also be NP complete. However it differs since there is no relationship between the elements of a solution set of a Subset Sum problem. I was also unable to work out a reduction of any known NP-Complete problem to this problem.

The constraint on the solution set in the problem does not make it solvable in polynomial time. At best I can work out pseudo-polynomial time algorithms to solve this and the time blows up as K increases.

Am I right in suspecting this might be an NP-indeterminate problem or am I missing something?

PS: This is not homework. I am new at this and if this is not the right place for this question please advise and I shall move it. Thanks.

EDIT: After the discussions in the comments below I am providing a few examples towards what I am working on.

The above problem is trivial for the case where $d = 1$ and $n = 2$ for all $K$. It is easy when $K$ is even and for $d = 2$ and $n = 2$. I have been working on cases where $d = 2$ and $d = 4$ for $n \ge 3$ and didn't realise this.

For the case $K$ odd and $d = 2$, say $K = 65$ and I have $S = \{1,2,...,64\}$ and $S'= \{9,11,13,15,17\}$. The best algorithm I have for this takes time proportional to $\sqrt{K}$ and is thus exponential as $K$ grows.

For $K$ even, $d = 2$ and $n \ge 3$, say $K = 24$ I have $S'= \{3,5,7,9\}$.

I have found that when $K$ is odd or even then $|S|$ is odd or even respectively. I am trying to see if I can get a better algorithm to determine $S'$ or if I should concentrate elsewhere.


texts:
I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly productive over the last year or so and have 3 accepted papers and two submitted papers. All of this to say that I am a fairly experienced graduate student and what I am about to describe is not anecdotal.

Every submission brings me more dissatisfaction than satisfaction. Just before I start working on a problem, me and my advisor identify a list of concrete questions that need to be answered. After lots of thinking, we have some very nice non-trivial results which gives me a lot of happiness and satisfaction. As we start to write down all of the results, inevitably, there are some more interesting variants that pop up but are much harder to make progress on. After the initial euphoria point, I feel everything seems to go downhill. There are so many variants that also need to be answered, are clearly in the purview of the problem at hand but I am not able to. By the time we submit the paper, I am so dismayed that results in the paper seem almost trivial. Perhaps this is simply tunnel vision, but I can't overcome the sadness about not being able to answer peripheral questions (although these make for a terrific conclusion section).

This has happened every single time and I am wondering if this is a common feeling. Do other people in theory community feel the same way? I am not sure if this is an academia wide feeling. My fellow graduate students from other areas are over the moon after every submission (but this is just anecdotal).

Edit - I see that there is another soft-question on the front page. I apologize for adding another one. Its holiday season and (only?) after a few drinks, one starts to ponder over these things!


texts:
We know that the decision version of Bin-packing problem is NP-complete:
Given an integer B, an integer k, and a list of integers X = (x1, x2, . . . , xn) where xi ∈ [0, B], is there any partition of X into k sublists, such that each sublist sums to at most B?

But what about the special case where the given numbers x_i's are as follows:
x_1 = 1, x_2 = 2, ... , x_n = n.

Then is this case also NP-complete?

In general is there any reference that I can find all or many versions of Bin-packing problem, and the facts known about them?


texts: Easy decision hard counting Parametrized

texts:
It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P.
Is there a problem, that exhibits the same behavior in parametrized  complexity? (Decision in FPT and counting in #W[1] or some other counting class?)


texts: Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$?

texts:
I am trying to find about algorithms that, given graph $H, G$, determine if $H$ is a topological minor of $G$ (and if so, exhibit this explicitly). Most of the literature on this topic seems to be focused on the case when $H$ is a fixed small graph while $G$ goes to infinity --- e.g. testing if $G$ is planar. What are the algorithms when $H$ and $G$ are comparable in size?

If this problem requires exponential time, I would still be interested in the best algorithms and/or real implementations


texts:
Suppose we are given a linear equation $Ax = b$, where $A \in Z_{q}^{m \times n}$ and $b \in Z_{q}^{m}$.

Note that $q$ is NOT necessarily a prime here. I wonder whether the following can be done in $poly(n, m ,q)$ time:

Check whether there exists $x \in Z_{q}^{n}$ such that $Ax = b$.
Suppose there exists $x$ such that $Ax = b$, find such $x$.

Thanks.


texts: How kerberos key distribution protocol prevents replay attack ?


texts: Is this edge orientation optimization problem NP-hard?

texts:
Is the following optimization problem NP-hard?

Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)$, where $d_{out}$ (resp. $d_{in}$) is the number of out-neighbors (resp. in-neighbors).

Motivation:
Assume the edge orientation does not induce any cycle of length 3, then the following algorithm lists all triangles in the input undirected graph in linear memory and in time $O(\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)+m+n)$ where $m$ is the number of edges and $n$ is the number of nodes.

For each node u:
  For each out-neighbor v of node u:
    For each out-neighbor w of node v:
      If u,w is an edge of the input undirected graph:
        output triangle u,v,w

Implementation details: the graph should be stored in a CSR-like format and, in addition, the edges of the input undirected graph should be put in a hashtable.
Finding the edge orientation that minimizes the quantity should lead to a faster algorithm. I think that the constraint "no induced cycle of length 3" is too complicated and, as a stepping stone, I've decided to formulate the above problem.
The question is related to that one where the edge orientation has to induce a DAG.
Another formulation: The problem can be written as the following Integer Quadratic Programming.
\begin{align}
 \text{Minimize} &\qquad \sum_{v\in V} y_v\times (d_v-y_v) &\qquad  (IQP)\\
 \text{s.t.} &\qquad \forall v \in V, \forall u \in N_v, x_{u,v}  \in \{0,1\}  \\
 &\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &\qquad \forall v \in V, y_v=\sum_{u \in N_v} x_{u,v}\\
\end{align}
with $N_v$ the set of neighbors of node $v$ in the input undirected graph and $d_v=|N_v|$.
Is (IQP) NP-hard?


texts: How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples

texts: Traditionally, the boolean satisfiability problem is framed as, given a boolean formula, is there an assignment that satisfies the formula. I'm trying to look at this differently - from the perspective of a Non-Deterministic Turing machine that, given a set of examples, will returns a formula that satisfies all of them. I'm familiar with non-determinism to seek out a single solution, but in this case, there is another dimension - specifically not whether there is any expression in the Universe of expressions that will satisfy each example, but instead what is the 1 expression that is satisfied by all the example assignments. Does anyone have a recommendation on how picture this?


texts:
I'm a new at the cellular neural network, which is a special case of the recurrent neural network: my questions are:
I understand the implementation of Chua circuit for the CNN, but I still need to

1- understand intuitively why every cell in CNN receives a summation of the outputs from the surrounding cells? mathematically it is clear how to analysis it but I'm talking about the idea behind that.
2- When do we decide to change the elements of matrix A and B or one of them, since some papers they set matrix B to zeros and sometimes matrix A to zero? I know they want to reduce the error but there is something still not clear.
3-I want to use CNN to classify images and I'm looking to a good reference to do that.

Thank you in advance,


texts: Practical Implications of Kolmogorov's Result on the Universal Approximation Theorem with Neural Networks

texts: After having read matus's beautiful answer in this thread explaining (among other things) Kolmogorov's result regarding the Universal Approximation Theorem with Neural Networks, I wonder: if just $\mathcal{O}$($d^2$) nodes can replicate (!) the target function, provided we can use different transfer functions, do there exist theory or algorithms for inferring from the training data which transfer functions to use?


texts: Complexity of the edge-disjoint cycle covers

texts:
I am interested in decompositions of a directed graph $G=(V,E)$ into non-intersecting Eulerian subgraphs $G_i=(V_i, E_i)$. I want to find the decomposition that covers the largest number of edges.

I believe that the best case is when a "Eulerian decomposition" exists, that is, the union of $E_i$ gives back $E$.

This problem is related to the minimum cycle cover of a graph but distinct. The minimum cycle cover wants to find cycles covering all edges with minimum overlap, whereas I want find cycles with no overlap covering as many edges as possible.

More specifically, I am interested in complexity results related to the following problems:

Given an integer $k$, is there an edge-disjoint cycle decomposition covering more than $k$ edges?
Is there an edge-disjoint cycle decomposition covering all edges?

Edit:

The second question has been answered in comments and appears to be polynomial.
The first question seems to be equivalent to "What is the smallest number of edges that can be removed from a graph so that each vertex has the same in-degree as its out-degree."


texts: TCS Research Frontier with Huge Practical and Industrial Impact on our Society

texts:
While CS theorists pursue the beauty and unity of their mathematical theories, their results can have a practical and industrial impact.

As we know, P versus NP is often talked about with its relation to public crypto. systems. Moreover, streaming algorithms often directly lead to industrial benefits.

Is there any possible research direction that would satisfy the following conditions?

(1)Solving problems in this area of TCS would lead to a fundamental change in our society.

(2)It would be required to understand other academic subjects (such as physics or electronics) to solve problems related to this TCS field.

I am afraid that this question is not appropriate for this stack exchange, but please forgive me if it is.


texts: Quantum annealing or adiabatic quantum optimization with continuous optimization problems

texts: How do quantum annealing or adiabatic quantum optimization deal with continuous optimization problems such as SDP?


texts: Is putting articles on arXiv or alternatives, before peer review, generally acceptable?

texts:
How common is it to place articles on arXiv or similar sites before publishing in a peer-reviewed journal?

I'm trying to get a feel for what my chances are, of publishing in a journal if I put an unreviewed article on Cornell's archival site, before I publish.  Is this common in theoretical computer science?

NOTE:  I see @Kaveh has recommended putting a paper on arXiv first in this question, so this gives me some hope!


texts: Approximate bound/algorithm for "product of sums maximization" problem

texts:
I am looking for some approximate algorithm with upper/lower bound for the following problem:

Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into disjoint sets $S_1, S_2, \dots, S_k$ so that the following function is maximized:

$$
\prod_{i=1}^{n} \sum_{j \in S_i} a_j
$$

Here is a few things I guess about the above problem (Let's call it PSM),

PSM is very similar to the multi-processor scheduling problem (with k processors and $a_i$'s as the job lengths) with a slightly different objective function. This is quite simple to show that PSM is at least as hard as multi-processor scheduling problem. Assume we are given a solution to PSM. The makespan of the solution must be minimum (it means this is a solution to the multi-processor scheduling problem as well), otherwise the product of sums is not maximized (right?).
We cannot have an FPTAS for PSM since multi-processor scheduling is strongly NP-hard.
For $k$ even, assume we have a $(1+\alpha)$-approximate algorithm for the multi-processor scheduling problem. The algorithm gives an upper bound of $(1-\alpha^2)^{k/2}$ for the PSM problem. That's because the worst case happens when $k/2$ of the sums are $(1+\alpha)\times OPT_{makespan}$ and the rest of them are equal to $(1-\alpha)\times OPT_{makespan}$. Therefore, we find a $((1+\alpha)(1-\alpha))^{k/2} \times OPT_{PSM}$ solution.

By the way, this is a wireless network scheduling problem. I have already discussed a variation of the problem here.
Any hint, solution, inapproximability result, reference to a book or a paper is appreciated.


texts: How many maximal planar graphs are there?

texts:
We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. isomorphic triangulations are seen as equal?
All results I can find are for plane graphs, i.e. concrete embeddings, and not abstract graphs.


texts: What is the minimal extension of FO that captures the class of regular languages?

texts:
Context: relations between logic and automata

Büchi's Theorem states that Monadic Second Order logic over strings (MSO) captures the class of regular languages. The proof actually shows that existential MSO ($\exists\text{MSO}$ or EMSO) over strings is enough to capture regular languages. This might be a bit surprising, since, over general structures, MSO is strictly more expressive than $\exists\text{MSO}$.

My (original) question: a minimal logic for regular languages?

  Is there a logic which, over general structures, is strictly less expressive than $\exists\text{MSO}$, but that still captures the class of regular languages when considered over strings?

In particular, I'd like to know what fragment of the regular languages is captured by FO over strings when extended with a least-fixed point operator (FO+LFP). It seems like a natural candidate for what I'm looking for (if it is not $\exists\text{MSO}$).

A first answer

As per @makoto-kanazawa's answer, both FO(LFP) and FO(TC) capture more than regular languages, where TC is an operator of transitive closure of binary relations. It remains to be seen whether TC can be replaced by another operator or set of operators in such a way that the extension captures exactly the class of regular languages, and no others.

First-order logic alone, as we know, is not enough, since it captures star-free languages, a proper subclass of the regular languages. As a classical example, the language Parity$\;\;=(aa)^*$ cannot be expressed using a FO sentence.

Updated question

Here is a new wording of my question, which remains unanswered.

  What is the minimal extension of first-order logic such that FO + this extension, when taken over strings, captures exactly the class of regular languages?

Here, an extension is minimal if it is the least expressive (when taken over general structures) among all extensions that capture the class of regular languages (when taken over strings).


texts: measures for a DAG (directed acyclic graph)?

texts:
Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential.
Well, is there a measure for the importance of a node (like the cut vertex in undirected graph)? or how separated the DAG is? May be after small amount of edge deletion (or node deletion) the DAG was decomposed into separated components (Better if the components have similar cardinality)?


texts: Is there a sensible notion of an approximation algorithm for an undecidable problem?

texts:
Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them.  For example, the halting problem is undecidable, but practical progress can be made on creating tools for detecting potential infinite loops in your code.  Tiling problems are often undecidable (e.g., does this polyomino tile some rectangle?) but again it is possible to advance the state of the art in this area.

What I am wondering is if there is any decent theoretical method of measuring progress on solving undecidable problems, that resembles the theoretical apparatus that has been developed for measuring progress on NP-hard problems.  Or does it seem that we are stuck with ad hoc, I-know-progress-when-I-see-it assessments of how much particular breakthroughs advance our understanding of undecidable problems?

Edit: As I think about this question, it occurs to me that perhaps parameterized complexity may be relevant here.  An undecidable problem may become decidable if we introduce a parameter and fix the value of the parameter.  I'm not sure if this observation is of any use, though.


texts: What is the fastest deterministic algorithm for incremental dynamic tree reachability?

texts:
As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.

The paper (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) introduces an algorithm for maintaining the transitive closure of a graph with O(n) amortized time pre  insertion. I wonder whether better algorithm exists for trees?


texts: Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

texts:
$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By this I mean that the quantum polynomial-time verifier is allowed to apply $\ket{\psi} \mapsto U\ket{\psi}$  once during its computation. Overall, we accept if there exists a $U$ that makes the computation accept w.h.p. and reject otherwise.

Similarly, is there an analogue of $\mathsf{QMA}(2) = \mathsf{QMA}(k)$ where Merlin provides to Arthur $k = O(1)$ "independent" accesses to unitaries $U_1, \dots, U_k$?

Bonus points if these are secretly equivalent to the usual notions of $\mathsf{QMA}$ and $\mathsf{QMA}(2)$ :)

The context is that in my application I want Arthur to implement, given $\ket{\psi}$ from Merlin, the Householder transformation $I - 2\ket{\psi}\bra{\psi}$. Unfortunately, I don't know how to do this given only $\ket{\psi}$, even if I'm allowed to corrupt $\ket{\psi}$ in the course of applying the transformation. If someone happens to know how to do this, this would also resolve my particular problem (although I think the question might be interesting independent of my application).

Edit - Martin Schwarz has pointed out that the part of the question below the line was proved to not be possible by Kumar and Paraoanu. The first part of the question remains valid though, I think.

Edit 2 (5/20) -  When the unitary in question is only over a constant number of qubits, one possible approach is to have Merlin send the Choi-Jamiolkowski representation $\rho$ of $U$. Applying $U$ to a state $\sigma$ then corresponds to teleporting $\sigma$ into the first (block of) qubit(s) of $\rho$, where we abort if the teleportation fails. I'm not sure about soundness but we maybe can use a combination of the quantum de Finetti theorem and quantum state tomography to ensure soundness, following Beigi, Shor, and Watrous. However, both of these tools are prohibitively expensive for states over more than a constant number of qubits. Furthermore, teleportation only succeeds with with probability inverse exponential in the number of qubits (and we cannot correct because errors may not commute with the unitary). Thus, it seems to me that this does not, at least naively, work for unitaries over more than a constant number of qubits.


texts: Global properties of hereditary classes?

texts:
A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal.

Classes of graphs that exclude a minor have nice properties that do not depend on the specific excluded minor.  Martin Grohe showed that for graph classes excluding a minor there is a polynomial algorithm for isomorphism, and fixed-point logic with counting captures polynomial time for these graph classes.  (Grohe,   Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors, LICS, 2010.)  These can be thought of as "global" properties.

  Are there similar "global" properties known for hereditary classes (either graphs or more general structures)?

It would be good to see each answer focus on just one specific property.


texts: Characterization of the Set of all s-t-Min-Cut Edge Sets

texts:
I would like to know how to answer the following problem:

Input: A family of sets $S$ over a universe $U$.
Question: Is there a directed flow network $N$ with edges $U$ such that the set of all $s$-$t$ min-cut edge sets is exactly $S$?

A min-cut edge set is the set of edges crossing a min-cut in $s$-$t$ direction.
I have come up with a partial solution: If there are three sets $A,B,C \in S$ such that the symmetric difference of $A$ and $B$ is a subset of $C$, then the answer to the problem is no. Unfortunately, this does not suffice.


texts: Explanation of states, models and worlds in Kripke semantics?

texts:
Can someone explain to me how the concepts of states, models and worlds work together in Kripke semantics?

I've been trying to piece together how the parts work are linked together but cannot figure it out.

From what I understand, a model $M$ consists of worlds.
Now as far as I can gather from that, states would be the same as worlds.
However, I cannot find this confirmed anywhere.

Could someone explain to me how these concepts work?
Obviously, I've googled them, but most texts are quite complicated to grasp with little experience on the subject. Even textbooks remain quite vague.


texts:
Given integers $a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem
$$
\exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b?
$$
I can't find this subset-sum variant in the literature.


texts: A problem that is in PSPACE but not known to be in PH?

texts: As we know Graph Isomorphism is in NP but it is not known to be NP-Complete or P-Complete. I was wondering if there are any problems that are known to be in PSPACE but not known to be PSPACE-Complete and not lie in PH?


texts: Best way to determine the minimum dimension of a structure given only distances between points

texts:
I came across this problem in an area of physics quite far removed from computer science, but it seems like the type of question that has been studied in CS, so I thought I'd try my luck asking it here.

Imagine you are given a set of points $\{v_i\}_{i=1}^n$ and list of some of the distances between points $d_{ij}$. What is the most efficient way to determine the minimum dimensionality of the space in which you need to embed these points? In other words, what is the smallest $k$ such that there exist a set of points in $\mathbb{R}^k$ satisfying the distances constraints $d_{ij}$. I would be equally happy with an answer for $\mathbb{C}^k$, but this seems harder.

I am happy to say that the distances need to match $d_{ij}$ only to within some constant accuracy $\epsilon$ and to have the points restricted to points on some lattice of constant spacing, in order to avoid issues of computing with reals.

Indeed, I would be quite happy with a solution for the decision version of this problem, where given $d_{ij}$ and $k$ you are asked whether or not such a set of vertices $\{v_i\}$ exist. Trivially the problem is in NP, since given a set of points in $\mathbb{R}^k$ it is easy to check that they satisfy the distance requirements, but it feels like there should be sub-exponential time algorithms for this particular problem.

The most obvious approach seems to be to try to build $k$-dimensional structures iteratively, by adding additional points one at a time and determining whether or not a new spatial dimension needs to be added at each iteration. The problem with this is that it seems you can run into ambiguities where there is more than one way to add a point to the existing structure, and it is not clear which one will lead to fewer dimensions as you continue to add more points.

Lastly, let me say that I know that it is easy to create lists of distances which cannot be satisfied in any number of dimensions (i.e. ones which violate the triangle inequality). However, for the instances I care about there will always be some minimum finite number of dimensions in which a satisfying set of points can be found.


texts:
I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.

Is it an interesting approach to class separation?

The motivation for the question is that we have to say

  there is some function that cannot be computed by size $f(n)$ circuits and can be computed by a size $g(n)$ circuit where $f(n)<o(g(n))$. (and possibly something regarding the depth)

so, if $f(m)g(n) \leq n^{O(1)}$, the property seem to be unnatural (it violates the largeness condition). Clearly we can't use diagonalization, because we aren't in a uniform setting.

Is there a result in this direction?


texts: minimizing size of regular expression for finite sets

texts:
It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification.

What are the results if the language is finite?

One can consider this problem in two models:

The input is all the strings in the language, and we measure the input size by the sum of the length of all strings.
The input is a DFA, and we measure the input size by the number of states of the DFA.

Kleene star is not useful in the finite case, so only $()$, $|$ and $\cdot$(concatenation) are used in the expression. Of course, the length of a regular expression seems arbitrary. Instead, one can give weight to each operation(include adding parenthesis), and ask to minimize the weight of the regular expression.

Edit: As adrianN noted, it's related to grammar based codes. It's NP-complete to produce the minimum length context free grammar to describe a finite set. It's not clear why minimum size context free grammar can imply much about minimum size regular expression. Maybe a clever rewrite rule can related these two, and prove that in the first model, the problem is in NP.


texts: Programming languages with canonical functions

texts:
Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, e.g. if f(x) returned x + 1, and g(x) returned x + 2, then f(f(x)) and g(x) would generate indistinguishable executables when the program is compiled.

Perhaps more importantly, where/how might I find more information on canonical representation of programs (Googling "canonical representation programs" has been less than fruitful)? It seems like a natural question to ask, and I'm afraid that I just don't know the proper term for what I am looking for. I'm curious as to whether it is possible for such a language to be Turing complete, and if not, how expressive a programming language you can have, while still retaining such a property.

My background is rather limited, so I would prefer sources with fewer prerequisites, but references to more advanced sources may be cool too, as that way I'll know what I want to work towards.


texts: Given a sparse matrix $A$ in $\mathbb{Z}^{n\times n}$, how easily could one check whether a coefficient $\alpha_k$ of the characteristic polynomial $P_A$ of $A$ is equal to $0$ (without the need to compute $P_A$)? Are there any known deterministic/randomized algorithms for this task?


texts: Are there common names for the subtiers of PTIME?

texts:
We all know P, or PTIME, I think, as a common name for the class of polynomial-time problems. Are there common names for the first few levels inside P; that is, for constant-time, linear-time, quadratic-time, cubic-time, ...? How do those names interact with common building blocks like "-SPACE" or "/poly"?

For linear-time algorithms, the Complexity Zoo gives LIN as a name, and extends that to NLIN by analogy with P and NP. In a drawing I made based on my reading of "Comparing Complexity Classes", I built the names "LINSPACE" and "NLINSPACE" according to what I think are community conventions.

If none exist, I have been imagining "KONST" for constant-time, "QUAD" for quadratic-time, and "CUB" (pronounced like "cub", "cube", or "kyubei", not sure) for cubic-time. I'm hoping that better community conventions already exist.

For examples of natural usage of these classes, I'd like to use the Chomsky hierarchy. Here, we have four extremely natural problems, and each corresponds to a level of complexity that has no nice name, but probably ought to:

REG, the class of regular languages, is also DSPACE(1), or "KONSTSPACE" in my nonce terms.
CFL $\subseteq$ DTIME($n^3$), or "CUB". This fact isn't in Complexity Zoo, which makes me feel a little strange; it's not a secret, is it? This class also closely relates to matrix multiplication, as CFL $\subseteq$ MM.
CSL is also NSPACE(n), or "NLINSPACE".
RE is fine as-is; we know quite a bit about RE.

In general, I see interesting things happening up to the third level of many hierarchies, and I think that even merely labeling up to the third level can be very useful.

I should divulge that I have a bias; I think mathematical objects should be nameable using only Unicode, and these clarified names clearly work towards that goal. Of course, "DTIME(n³)" is also still Unicode, but longer to spell, write, and say than "CUB".


texts: Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$

texts:
Let $p$ be a prime.  Suppose we consider the function $f: GF\left(p \right) \rightarrow \left\{0, 1 \right\}$ where $f(x) = x \bmod 2$ for all.

The question is the following:  are there any known circuit bounds or results on computing $f$ using arithmetic circuits over $GF(p)$?

In other words, we'd like to evaluate $f$ using only field additions and multiplications.

It's simple to do this with arithmetic circuits of size $O \left(p \right)$ and also probably straightforward to show that it cannot be done with arithmetic circuits of size $o\left( \log p \right)$.  However, it has been difficult for us to say anything concrete other than these simple bounds.  Any literature or references on this problem (or similar types of problem) would be greatly appreciated!  Thanks!


texts: Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime

texts:
i have some question concerning the class PP and PPT machines.

1) PP is defined as the class of problems $L$ for wich exist a probabilistic turing machine running in polytime with error probability < 1/2.

I would like to know if there exists a complexity class that says in the following way (or something similar). "The class of problem $L$ for wich exist a probabilistic turing machine running in expected(or avarage) polytime with error probability < 1/2."
I took a look at complexity zoo, papadimitriou and arora-barak books but nothing seems concerning this aspect.

2) Concerning Goldreich09 it seems that Expected Probabilistic Polinomial Time (EPPT) is defined regarding a strategy. Are there alternatives definition of EPPT not related to adversaries and interactive machines or EPPT is strictly linked with strategies and adversaries?

By question arises for the following reason. In Feige phd thesis there is written (page 10):

  A probabilistic Turing Machine is expected polynomial time, if for any input, its expected running time (over random flips) is polynomial.

This definition don't say anything about adversaries.

the first question then follows. can we create a complexity set of problem by using Probabilistic TM running in EPPT?

Thank in advance.


texts: Optimal payoff from sampling from a collection of Bernoulli random variables?

texts:
Suppose I have several Bernoulli random variables, $\{X_1, \ldots, X_k\}$, each of which has a fixed probability $p_i$ of equaling 1 for each sample. Further suppose each $p_i$ is randomly distributed according to some known distribution, but we do not know the actual values of $p_i$.

Finally, suppose I am going to take $n$ samples in total from these variables and want to maximize the expected sum of the resulting samples. What is the best algorithm for choosing variables to sample? Obviously, if we knew which had the highest probability, we would always choose that variable, but if $n$ isn't very large, we have to be careful about balancing choosing the variable we believe has the highest $p_i$ value and sampling other variables to possibly find one with a higher $p_i$ value.


texts: Where do I turn for help with research/publishing?

texts:
I have been developing a SAT algorithm for a while, and have reached a point where I'd like to share it.  I don't know many people in computer science, and I'm not sure exactly where to turn.

I'm wondering what resources are available for someone with an algorithm who is considering publishing.  I also need help analyzing the runtime and correctness of my algorithm.

My major problem is in analyzing the runtime.  I need help with a detailed analysis of this.  I'm fairly certain that the algorithm is correct, but it would be helpful if someone would verify this as well.

So is there anyone who would be willing to analyze my algorithm?  Additionally, what resources are available for a task like this?


texts: Are there uses for a Fourier transform of length $n^m$ with elements of maximum size $n$?

texts:
In essence, I'm trying to get a better feel for when there is a use for FFT with small coefficients, compared to the length, assuming that we get a better runtime.

I've been toying with an idea for a Fourier transform with elements of small size compared to the length of the transform.  It seems that the running time is $O(n^m \log_2{(n^m)})$ total bit operations of size $n$, but it doesn't require any multiplications.  I'm wondering if this could be useful, or if this can be totally circumvented with smaller transforms.  In the case that it does seem useful, or comparable to other situations, what are the uses for it?

Also, if we suppose that it requires $O(f(m) \cdot n^m)$ multiplications, could it still be useful?

As an example, it seems to me that this would decrease the depth of a multiplication algorithm, since we can decrease the size of the coefficients that we use recursion on.


texts:
Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that

The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$.
$\Psi(\mathcal C)$ has a solution if and only if $\mathcal C$ has a solution.
Any solution $x$ of $\Psi(\mathcal C)$ can be efficiently converted into a solution of $\mathcal C$ using $r$.
Without $r$, the solution $x$ (or any other property of $\Psi(\mathcal C)$) does not give any help in solving $\mathcal C$.

If there is such a $\Psi$, then it can be used to make others to solve computational challenges for us (with possibly replacing solving a CNF with other problems - I chose CNF because I wanted to make the problem more specific), in such a way that they cannot profit from a possible solution even if they know what problem we've used them to solve.
For example, we could embed a factorization problem into a computer game, which enables players to play only if they work on our problem in the background, from time to time sending back proofs of computation.
Maybe software can be even made "free" this way, where "free" hides a (possibly higher) cost in your parents' electricity bill.


texts: Termination of the Bellman-Ford algorithm in asynchronous distributed model

texts:
I'm looking for an algorithm to compute the BFS tree of a graph rooted in the leader processor $r$ in the asynchronous distributed model.

The only requirement is $O(D)$ time complexity, where $D$ denotes the diameter of the graph (message complexity isn't relevant).

Currently, I'm using Bellman-Ford algorithm, but I don't know how to guarantee the global termination of this method in $O(D)$ time. I was trying to use the convergecast technique, but with no success.

Is it possible to guarantee a termination of Bellman-Ford in $O(D)$ time or is there any other algorithm for computing the BFS tree in $O(D)$ time?


texts: Name for relationship where one graph is a minor usually implies another is?

texts:
Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must be a minor. What do you call the relationship between $G$ and $H$?

For example, consider a claw with each edge subdivided once and a claw with one edge subdivided twice. You can subdivide any edge of the former to produce a graph for which the latter is a minor $(k = 1)$. Is anyone writing about this or has it been given a name?


texts: Algebraic construction of $\varepsilon$-biased sets

texts:
Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by
$$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$
It is then possible to show the following

$\text{Tr}$ maps $\mathbb{F}_{2^\ell}$ into $\mathbb{F}_2$.
If $a\in\mathbb{F}_{2^\ell}$ is non-zero, then the mapping $f_a:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2}$ defined by $f_a(x)=\text{Tr}(a\cdot x)$ is $\mathbb{F}_2$-linear and $\mathbb{E}_{x\sim\mathbb{F}_{2^\ell}}[f(x)]=\frac{1}{2}$.

Now, we consider the set $S=\{s(x,y,z):x,y,z\in\mathbb{F}_{2^\ell}\}$ such that we index the entries of $s(x,y,z)$ by $0\leq i,j$ such that $i+j\leq c\sqrt{n}$ ($c$ is a constant so that there are exactly $n$ entries). For such $x,y,z$ and $i,j$ we set $s(x,y,z)_{i,j}=\text{Tr}(x^iy^jz)$.

I want to show that for an appropriate choice of $\ell$, the set $S$ described above is an $\varepsilon$-biased set of size $O(n\sqrt{n}/\varepsilon^3)$.

Fix $\vec{0}\neq \tau\in\{0,1\}^n$, what we need to show is that (under good choice of $\ell$)
$$\bigg|\mathbb{E}_{s\in S}\Big[(-1)^{\langle s,\tau\rangle}\Big]\bigg|\leq \varepsilon$$

Let $x,y,z\in\mathbb{F}_{2^\ell}$ and consider $\langle s(x,y,z),\tau\rangle$, I managed to show that (from $\mathbb{F}_2$-linearity above while indexing $\tau$ as we index $s(x,y,z)$)
$$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$
Finally, I thought of defining the bi-variate polynomial $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$ and saying that since it is a non-zero polynomial of low degree at most $c\sqrt{n}$ it attains each value of $\mathbb{F}_{2^\ell}$ with multiplicity at most $c\sqrt{n}2^\ell$ (from Schwartz-Zippel), so
$$\forall\alpha\in\mathbb{F}_{2^\ell}:\Pr\limits_{x,y\in\mathbb{F}_{2^\ell}}[p_\tau(x,y)=\alpha]\leq c\sqrt{n}/2^\ell$$

I want to use it but I am stuck..., maybe we can say that the distribution of $p_\tau(x,y)$ is close enough to $U_{\mathbb{F}_{2^\ell}}$ in statistical distance in order to infer that the expeced value of $f_z(p_\tau(x,y))$ is close enough to $1/2$?


texts: It is known that if calculating permanent is easy, then solving hard problems in NP is easy. Is there a transparent example regarding application of say finding independent set or find chromatic number of a graph through the permanent?


texts: Does L=P imply any new complexity class separations?

texts:
If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L.

I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly contained in NP?

Edit:

As Tsuyoshi points out, it is consistent with current state of our knowledge that L=NP in which case L=P=NP.

The question can be state more rigorously as improving the result in the first line of this post:

  Is there an interesting complexity class C which we don't know if it is separated from L (by the space hierarchy theorem, etc.), however we know that if L=P then L will be strictly contained in C?


texts: Is the problem "MIN-SET-PARTITION" an NP-hard problem?

texts:
Given a family of sets $F = S_1, ..., S_n$ of elements from a universe $U$, find the minimal integer $k$ for which there is a partition of $F$ of size $k$, such that every two sets in the same partition are disjoint. Formally, we want $P_1, ..., P_k$ such that for every $1 \leq i,j \leq k$, we have $P_i \subseteq F$ and $P_i \cap P_j = \emptyset$. Furthermore, for every $S,T \in P_i$ we have $S \cap T = \emptyset$. Finally, $\bigcup P_i = F$.

We can ask the same question as a decision problem: $\lbrace U,F,k \rbrace \in MIN-SET-PARTITION$ iff there is a partition (as described above) of $F$ of size $k$.

My intuition is that this is indeed NP-hard and that someone has probably already thought about it. I'd be happy to get a reference or a description of a reduction.

Thanks!


texts: What is the fastest known simulation of BPP using Las Vegas algorithms?

texts:
$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes.

$\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the probability of algorithm returning an incorrect answer is bounded, i.e. the error probability is at most $\frac{1}{3}$ (for both YES and NO instances).

On the other hand,
$\mathsf{ZPP}$ algorithms can be viewed as those probabilistic algorithms
which never return an incorrect answer, whenever they return an answer it is correct.
However their running-time is not bounded by a polynomial, they run in expected polynomial.

Let $\mathsf{ZPTime}(f)$ be the class of language decided by probabilistic algorithms with zero error probability and expected running-time $f$. These are also referred to as Las Vegas algorithms and $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$.

My question is what is best know simulation of $\mathsf{BPP}$ algorithms using Las Vegas algorithms? Can we simulate them in subexponential expected time? Is there any known improvement over the trivial brute-force simulation which takes exponential time?

More formally, do we know if
$\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ or $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ for some $\epsilon>0$?


texts: How to prove that Supremum preorder coincides with Hoare preorder?

texts:
Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$.

I mean:

Hoare preorder $(2^{B_L}, \sqsubseteq_H)$, where for $X, Y \in 2^{B_L}$,

$X \sqsubseteq_H Y \iff \forall x \in X$, $\exists y \in Y$ such that $x \sqsubseteq y$
Supremum preorder $(2^{B_L}, \sqsubseteq_{\sqcup})$, where for $X, Y \in 2^{B_L}$,

$X \sqsubseteq_{\sqcup} Y \iff \sqcup X \sqsubseteq \sqcup Y$

Where $l \in L$ is completely $\sqcup$-irreducibles $\iff \forall X' \subseteq L$ such that $l = \sqcup X' \implies l \in X'$ (note that $\bot$ isn't completely $\sqcup$-irreducible since $\bot = \sqcup \emptyset$ but $\bot \not\in \emptyset$).

I'm pretty sure that "Hoare" is the right name for the intended preorder, a little less about "Supremum" (maybe "Smyth" could be better).

My question is, given a distributive lattice $L$, how to prove that Hoare preorder and Supremum preorder coincide?
It is easy to see that in general (without distributivity) $X \sqsubseteq_H Y \implies X \sqsubseteq_{\sqcup} Y$. But I'm stuck in the converse implication $X \sqsubseteq_{\sqcup} Y \implies X \sqsubseteq_H Y$, that probably uses distributivity of $L$.

Where $L$ is distributive $\iff \forall a, b, c \in L$ it holds that $a \sqcap (b \sqcup c) = (a \sqcap b) \sqcup (a \sqcap c)$. By the way, I'm still not sure if I need to require $L$ to be only distributive or completely distributive.

Thanks in advance for any hint.


texts: Seminal papers related to SMT theories (particularly QF_ABV)

texts: I am working on an application using Quantifier-Free Bit-Vector/Array satisfiability which may or may not require mucking around with the internals of an SMT solver, and would like to understand what's going on behind the scenes of existing methods (beyond merely reading their API's).  What papers should anyone interested in working with SMT solvers, particular in QF_ABV, read?  I'd be particularly interested in 1) why and how current SAT solvers are able to work so well on an NP-complete problem and 2) the specifics of how bit-vector and array theories are implemented and any tricks that speed them up.


texts: Finding Tours through Near-Hamiltonian Paths?

texts: Say I have a connected graph.  I want to find a tour that visits each vertex at least once.  It's not always possible, though, for there to be a solution if there is a bridge in the graph.  Is there a term for this sort of problem or a recommended approach to solving it?  The motivation if it helps that I ultimately have in mind is traversing every station in a subway system.


texts: A simple proof that decidability of typability in System F ($\lambda 2$) implies decidability of type checking?

texts:
Suppose we don't know Joe B. Wells's result from 1994 that both typability and type checking are undecidable in System F (AKA $\lambda 2$). In Barendregt's Lambda calculi with types (1992) I found a proof due to Malecki 1989 that type checking implies typability. This is because

  exists $\sigma$ such that $M:\sigma$

is equivalent to

  $(\lambda xy.y)M : (\alpha\rightarrow\alpha)$

(This is because if a term is typable in System F then all its subterms are.)

Is there a simple proof the other way around? That is, a proof that typability implies type checking in System F?


texts:
Most puzzles that you can buy are in P, NP-complete (like Sudoku) or PSPACE-complete (like Sokoban), at least if you scale them up.
Are there any natural puzzles that are PPAD-complete?
What about other similar classes, like PPA, PPADS etc?

If we don't insist on natural, then of course practically any PPAD-complete problem would be a puzzle, just during the puzzle you would need to run the some Turing machine a couple of times.
What I have in mind would be for example finding another Hamiltonian cycle in a cubic graph, which is known to be in PPA, just now known to be complete.


texts: Why does the Complexity Class PostBQP makes proving PP greater than or equal to QMA easier?

texts:
PP was proved greater than QMA in by Kitaev and Watrous 2000 -
Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems.

Later Aaronson proved that PostBQP was equal to PP in his PHD 2004.

It has been stated that the knowledge that PostBQP = PP makes proving PP is greater than or equal to QMA a lot easier.

Is there a short explanation of this. Or if not could someone provide a reference detailing this fact?


texts: Size of the constant $s_3$ in Exponential Time Hypothesis (ETH)

texts:
Exponential Time Hypothesis (ETH) says that there is a real number $s=s_3>0$ such that 3-SAT with $n$ variables and $m$ clauses cannot be solved in $2^{sn}(n+m)^{O(1)}$ time. The corollary "3-SAT cannot be solved in $2^{o(n)}(n+m)^{O(1)}$ time" is used more often.
Assuming ETH is true, is anything proved about how large $s$ is?
If not, is there at least a general consensus?


texts: An oracle construction relative to which BPP = EXP is usually attributed to Heller (Mathematical System Theory Vol. 17, 1984). Unfortunately I don't have the paper available in my library. Could someone explain how it goes? If it is easier to give an oracle where NP = EXP that would fine already.


texts: Advice for a mathematician trying to present a paper at a CS conference?

texts:
I am a mathematician who works primarily in the spectral theory of self-adjoint and unitary operators. Some of my research is of relevance in quantum walks, and I have one paper in particular that I would like to present in the Quantum Information Processing conference this January in Seattle.

The culture of the theoretical CS community seems very different from the math community. I even had to look up what it meant to  "present a paper" at a conference, since we never use that language in math conferences!

I was wondering if I could get some advice on presenting my paper for consideration in this conference. Along with an arXiv link to my paper I am supposed to give them a 1-3 page extended abstract, which I suppose is a way to convince them my paper is relevant for the conference. What is normally expected in such a document?

For instance, to what extent should I talk about the mathematical machinery? Would the organizers care about the (very difficult and technical) details of the proof, or should I just state an algorithm, assert that it works and explain why it is relevant to computer science?


texts: size bounds for circuits recognizing graph properties (reachability, cyclicity, ...)

texts:
I am interested in the following. Let the inputs of the circuit correspond to the arcs of a directed graph. The circuit has to output 1 iff there is a directed path from a given node S to a given node T such that all arcs on that path have input value 1.

I can construct Boolean circuits that have size linear in nm where n is the number of vertices in the graph and m is the number of arcs. I would like to know if smaller circuits are possible. Especially, circuits that are linear in n+m.


texts: How to prove a general convex set is nonempty or empty in polynomial time?

texts:
The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0 $ with $ f_{i}(x) $ being convex in $ x $.

I know ellipsoid method and interior method, but I do not find specific theorems to explain my question.

Can I use the theorem of equivalence of optimization and separation problems in ellipsoid method by setting the objective as a constant e.g. take $c=0$ in the objective $c^{\top}x $?


texts: An Exact Cover Variant encoded in a 4-Terminal Network

texts:
During research, I hit the following problem

Exact Cover Variant (ECV)
Input: Three set systems $S_1, S_2, S_3$ over a universe $U$, each closed with respect to $\cap$ and $\cup$.
Question: Is there an exact cover for $U$ consisting of sets in $S_1,S_2,S_3$?

This is easy. An important observation is that if there is an exact cover, then there is one consisting of at most one set of each set system (this is due to the closedness regarding $\cap$ and $\cup$). It hence suffices to iterate over all (polynomially many) possible solutions. So I will make the problem harder again. Instead of giving $S_1,S_2,S_3$ explicitly, it will be encoded in a multi-terminal network as follows:

Network Exact Cover (NEC)
Input: A 4-terminal network $N$ with node set $V$ and terminals $T=\{t_1,t_2,t_3,t_4\} \subseteq V$.
Question: Let $S_1,S_2,S_3$ be the source sides of all min-cuts separating $\{t_1,t_2\}, \{t_1,t_3\}, \{t_1,t_4\}$, respectively, from the remaining terminals. Is there an exact cover of $V-T$ using sets of $S_1,S_2,S_3$?

Due to the submodularity of min-cuts, the sets $S_1,S_2,S_3$ are closed with respect to $\cap$ and $\cup$ as well.
I cannot come up with a polynomial algorithm for NEC, neither can I proof NP-hardness (it clearly is in NP). Question: Do you have any ideas concerning NEC's complexity?
The reason NEC appears to be harder than ECV is that the number of elements of each set system may be exponential in $|V|$. Iterating over all possible solutions is not possible anymore. At the same time, these exponentially many min-cuts are given in a data structure (a network) that may make it easier to find a solution.
Also note that not for every three sets closed with respect to $\cap$ and $\cup$, there is a 4-terminal network encoding these sets in the above described way. This interdependency may be exploited (and at the same time makes it hard to find a reduction...).


texts:
Consider the following setting:

we are given a stack $s$ which contains $n$ items.
we can use a constant $O(1)$ number of extra stacks.
we can apply the following operations on these stacks:

check if a stack is empty,
compare the top items of two stacks,
delete the top item in a stack,
print the top item in a stack,
copy the top item of a stack into another stack,
copy the content of one stack to another stack.

Note that these are the only operations that are permitted.
We cannot swap items and
we are not allowed to push any item onto any of the stacks
with the exception of copying the top item into a stack
(after which the previous content of the target stack is discarded and
it will only contain the copied item).

Here is an algorithm to sort the stacks with $O(n^2)$ comparisons:

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

Can we do better?

  Is there a program that prints the sorted list of the items in the stacks
  using only $O(n\log n)$ comparisons?


texts: Find a boundary from set of 3d line segments

texts:
I have a set of n 3d line segments  [(p1_start,p1_end), (p2_start,p2_end),....(pn_start,pn_end)].
(I believe that they shod be nin-intersecting...)
These segments represent a (closed) boundary.  I am looking for effective algorithm to generate this boundary, i.e. to find the order of segments for boundary :  [pj_start,pj_end, ...p1_start, p1_end.....]
(segments can be connected via their ends: start to start , start to end, end to start, end to end)
I thought to start from arbitrary segment , say s = (pm_start, pm_end),
among all other segment find the one , which distance to pm_start or  pm_end is minimal, and add this segment end based on calculated minimum distance and continue this way for all segments
The complexity of this approach is not good
Can anyone propose effective algorithm for this problem


texts: Where is the proof that Coq + Excluded Middle is consistent

texts:
I've seen (and heard) it claimed that it is safe to add the classical axiom of excluded middle to Coq, but I can not seem to find a paper supporting this claim. The papers I see listed on the Coq wiki about excluded middle are showing inconsistency with impredicative Set.

Indeed, it seems that Coquand states that adding Excluded Middle (an inhabitant of $A+\neg A$) is inconsistent for CoC in section 4.5.3 of his description(PDF) of the metatheory of CoC. However, this section is a bit abstruse to me, so I may very well be misreading him.


texts: What is the currently best known algorithm for the transportation problem?

texts:
Consider the well known transportation problem:
There are $m$ supply nodes, $n$ demand nodes and $k$ feasible arcs.
Every node has a integer supply or demand, and the arcs have integer costs, used linearly, i.e. if $x$ units are shipped along an edge annotated with $c$, the cost is $c\cdot x$.

I have an article by Kleinschmidt and Schannath describing an $O(m\log m (k+n\log n))$ solution.

Is this the currently best algorithm, or has there been an improvement since 1995?

(My search turned up an article by Brenner from 2008, but I don't have access to it.  The title talks about the "unbalanced Hitchcock transportation problem", I am not sure it is the problem considered here).

Would this be the right algorithm to implement?

Which libraries provide implementations of the transportation problem?


texts: Sperner family that maximizes the subsets of a partition

texts:
Let $A$ be a set of size $k$ and $B$ be a set of size $\ell$, for fixed $k$ and $\ell$, and such that $A\cap B=\emptyset$.
What is the (or a) Sperner family $\mathcal{F}$ on $A\cup B$ for which $\mathcal{F}_B=\{C\cap B ~:~ C\in\mathcal{F}\}$ is maximized?

I actually just need an upper bound to $|\mathcal{F}_B|$ (possibly something better than $2^\ell$, which seems to be loose if $2^k<\ell$)

Any hint or reference where this kind of information or relevant material could be found would be much appreciated. Thanks.


texts:
Banaszczyk's theorem states that if $\Lambda$ is a rank-$m$ lattice with dual lattice $\Lambda^*$, then $\lambda_1(\Lambda) \cdot \lambda_m(\Lambda^*) \leq m$.

Can someone point me to a clean proof of this theorem? The proofs I am aware of in various lecture notes all lose a factor of 2 in the bound. And while Banaszczyk's paper is available, it is hard to read and seems to have this theorem buried among other results.