texts:
I am currently interested in obtaining (or constructing) and studying 3-CNF formulae which are unsatisfiable, and are of minimum size. That is, they must consist of as few clauses (m = 8 preferably) as possible, and as few distinct variables (n = 4 or more) as possible, such that removing at least one clause will render the formula satisfiable.

More formally, any qualifying 3-CNF formula F must satisfy the following conditions:

F is unsatisfiable
F has a minimum amount (4+) of distinct variables (or their negation)
F has a minimum amount of clauses (8+)
every proper subset of F is satisfiable (allowing removal of any arbitrary clause or clauses).
F has no 2 clauses that are reducible to a 2-CNF clause
e.g. (i, j, k) & (i, j, ~k) is NOT allowed ( they reduce to (i,j) )

For example, with n=4, there exists many minimal 8-clause 3-CNF formulae that are unsatisfiable. For one, by looking at the 4-hypercube and trying to cover it with edges (2-faces), one can construct the following unsatisfiable formula:

1. (~A,  B,  D)
2. (~B,  C,  D)
3. ( A, ~C   D)
4. ( A, ~B, ~D)
5. ( B, ~C, ~D)
6. (~A,  C, ~D)
7. ( A,  B,  C)
8. (~A, ~B, ~C)

This qualifies as a minimum unsatisfiable 3-CNF formula because:

It is unsatisfiable:

Clauses 1-3 are equivalent to:  D or A=B=C
Clauses 4-6 are equivalent to: ~D or A=B=C
They imply A=B=C, but by clauses 7 and 8, this is a contradiction.

There are only 4 distinct variables.
There are only 8 clauses.
Removing any clause renders it satisfiable.
No 2 clauses are 'reducible' to a 2-CNF clause.

So I guess my overall questions here are, in order of importance to me:

What are some other small minimum formulae which meet the above conditions?
(i.e. for say, 4,5,6 variables and 8,9,10 clauses)
Is there some sort of database or "atlas" of such minimum formulae?
What nonrandom algorithms exist for constructing them outright, if any?
What are some insights into these formulae's characteristics? Can they be counted or estimated, given n (# variables) and m (# clauses)?

Thank-you in advance for your replies.
I welcome any answer or comment.


texts:
Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause.  Can 3-SAT with $O(n)$ clauses be reduced to $(k,2k+1)$-SAT with $O(n)$ clauses (the constant may depend on $k$)?

3-SAT is NP complete, while 2-SAT and even $(k,2k)$-SAT are in P. $(k,2k+1)$-SAT for $k>1$ can be viewed as intermediate between 3-SAT and 2-SAT, and arguably as $2+ε$-SAT if $k$ is large.  The paper (2+ε)-SAT is NP-hard proves that it is NP complete (see also a blog post; also, $(a,k)$-SAT is $(1,a,k)$-SAT in the paper).  However, its proof goes through the PCP theorem and thus (given our lack of knowledge of linear size PCP) leaves open the question of whether the reduction can be done with a linear increase in the number of clauses.  Specifically, their NP-completeness proof uses a gadget reduction from inapproximability of label cover.  However, they only use local inapproximability rather than the full PCP theorem (they require satisfiability of label cover instances that are $ε$-satisfiable everywhere rather than just on average), which might make linear size more likely or easier.

The paper shows impossibility of a natural type of gadget reduction from 3-SAT:  Given a 3-SAT clause using variables $x,y,z$, replace it with a conjunction of clauses using $x$,$y$,$z$ and internal variables, with $x$,$y$,$z$ remaining the only connection with clauses derived from other 3-SAT clauses.  The problem is not in copying the inputs (using repeated variables in a clause, even $(k,2k)$-SAT allows variable copying), but is more deep.  Given a putative encoding of a clause $x∨y∨z$, a simple numerical argument (proposition 4.5 in the linked paper) shows that if $(x,y,z)$ values $(1,0,0)$,$(0,1,0)$, and $(0,0,1)$ can all satisfy at least $k$ literals of every size $2k+1$ clause ($k>1$), then by taking the majority assignment of the internal variables (across the 3 assignments), $(0,0,0)$ also satisfies at least one literal of every such clause.

The above impossibility argument does not appear to work if we define gadgets more broadly.  For example, instead of coding a 3-SAT variable $x$ by a single variable, we can code it by $O(1)$ variables (dependent on $k$).  This way, an encoding of $x=0$ in a gadget for $x∨y∨z$ might depend on whether $y=0$, so averaging the encoding of $x$ across 3 assignments might produce a bad encoding.  If desired, we can also code $x$ by a separate set of variables for every 3-SAT clause using $x$, using a copying gadget (if needed, with 3 inputs so that every variable is used by at most two gadgets) to connect the clauses.

The impossibility argument also does not appear to rule out a reduction from 3-SAT using a one-way deterministic finite state transducer, augmented with $O(1)$ slots for variable names, with the ability to read a variable name, output a variable name, and create a new variable name.  (Another natural operation is testing two variable names for identity, but that should not be needed for a reduction from 3-SAT.)


texts: Lower bound on alternations needed in $BQP$ versus $PH$ result?

texts:
What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ holds where $n$ is number of inputs to $\mathsf{SAT}$ formula (note $\mathsf{BQP}\subseteq\mathsf{PP}$) (here $\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ refers to $\mathsf{FP}$ with oracle access to ${\mathsf{PH}[O(f(n))]}$)? Is $f(n)=O\Big(\frac{n}{\log n}\Big)$ (comments in https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html seems to indicate such a bound on $f(n)$ however was not sure)?
What would be the consequence if indeed $\mathsf{PP}$ and/or $\#\mathsf{SAT}$ are/is in $\mathsf{PH}[O(\log n)]$ and $\mathsf{FP}^{\mathsf{PH[O(\log n)]}}$ respectively? Would it nullify the $\mathsf{BQP}$ versus $\mathsf{PH}$ result of Raz and Tal (it could still be $\mathsf{BQP}\not\subseteq\mathsf{PH}$ is true but the evidence achieved will be falsified) and the result Robin Kothari is quoting? Would it have other consequences?


texts: Graph-related applications of the fast Fourier transform (and other algebraic algorithms)

texts:
The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths).

However, while the fast Fourier transform algorithm implies several other near-linear-time algebraic algorithms including polynomial multiplication, multi-point evaluation, interpolation, etc., I do not know its application to any graph problem yet.

  What are applications of the fast Fourier transform to graph problems?

Actually, applications other fast algebraic algorithms (except fast matrix multiplication) are also welcomed.


texts:
In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. NP problem".

It seems to indicate that the only currently viable program could face serious obstacles.

What are some of the obstacles where the program could fail?


texts: Cohomological approach to boolean complexity

texts: A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this line of thought brought any new insights into boolean complexity, or does it remains rather a mathematical curiosity?


texts: High-Probability bounds for Stochastic multi-armed Bandit Problems

texts:
This paper gives some high probability results for UCB algorithm of the form,

\begin{align}
\mathbb{P}(R_{n} > r_0.x) \leq O(n^{-2\rho x + 1} + x^{-2 \rho  + 1} )
\end{align}

where $\rho$ is a parameter of the algorithm, $R_{n}$ is the regret till time $n$, and $r_{0}$ is the bound for the expected regret that is of order $O(\log n)$.

Is it possible to get high-probability bounds on the regret between time $n_2$ and $n_1$, that is $R_{n_2} - R_{n_1}$ , where $n_2 - n_1 = o(n_1)$ ? I presume we can modify the arguments in the above paper to do so, but if there is any resource that directly gives such bounds, then that would be helpful.


texts:
I am looking for a solver that computes an approximation to #SAT.  In other words, given a formula $\phi(x)$ in CNF, approximately count the number of satisfying assignments to $\phi$.  I'm interested in an approximate count, not the exact number.  Are there any existing working implementations that I can download and try?

To be clear, I'm not looking for algorithms or for papers describing algorithms; I'm looking for an implementation I can use, in the style of a SAT solver.  This question is related to #SAT Solver download, except that one asks for solvers that exactly count the number of satisfying assignments, whereas I am interested in solvers that approximate the number of satisfying assignments (I do not need an exact count).


texts: Which results in complexity theory make essential use of uniformity?

texts:
A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like time and space hierarchy theorems) make essential use of uniformity as they need to simulate the programs in the smaller class.

  Which results in complexity theory (other than diagonalization proofs) use uniformity essentially?


texts:
Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$.

1) Is $k$-sum random self-reducible?

That is if $k$-sum can be computed in time $n^{O(k^b)}$ for some $0<b<1$ on $\frac{1}{2}+\epsilon$ of inputs where $n$ is the number of input integers, then can $k$-sum be computed time $n^{O(k^b)}$ for all inputs of $n$ input integers in a randomized sense?

The Patrascu-Williams paper http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf talks about deterministic algorithms and does not imply hierarchy collapse but only tells that the ETH fails (somewhat mildly) when we have a deterministic $n^{O(k^b)}$ algorithm. We have a randomized setting here and even if we have such a random self-reducible condition satisfied, we may still not upset the big picture.

2)Likewise can the $\mathsf{NP=coNP}$ problem be random self reducible?

That is, if for an $\mathsf{NP}$ complete problem we have short certificates for $\frac{1}{2}+\epsilon$ of the $\mathsf{NO}$ instances, then we have short certificates for all $\mathsf{NO}$ instances in a randomized sense?

Update The results in http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf seems to indicate the $\mathsf{NP}=\mathsf{coNP}$ issue is not random self-reducible.


texts: Call-by-push-value's denotational semantics of "thunk diverge"

texts:
I was reading about Call-by-Push-Value in the introducing paper from 1999, but I have some confusion, partially because of my unfamiliarity with domain theory. I might have figured it out, but I'd hope to get it confirmed. (If this is not the appropriate venue, advise is welcome on which one is).

I was confused by the statement:

  $[[ \mbox{thunk diverge} ]]\ \rho$ is the least element of the predomain $[[U\ \underline B]]\ \rho$

I was confused because AFAICS, predomains are not guaranteed to have a bottom element in general.

The behavior of $[[U\ \underline B]]$ was defined earlier by saying:

  if $[[\underline B]]$ is the domain $(X, \le, \bot)$, then $[[U\ \underline B]]$ is its underlying predomain $(X, \le)$

Finally, predomains and domains are defined as:

  A domain $(X, \le, \bot)$ is a predomain with a least element $\bot$.*

Originally, I misunderstood the text as implying that to construct $[[U\ \underline B]]$, you remove the bottom element from $[[\underline B]]$. Now, instead, I realize that probably, the semantics of U is just forgetting that $\bot$ is a distinguished element (like a forgetful functor from the category of domains to category of predomains, if my intuition is right). That's because, in a domain, we assume that $\bot$ belongs to X, not to its lifting: that is, $\bot \in X$, instead of $\bot \in X_\bot$.

Question: Is my new reading (above paragraph) correct?

Furthermore, the paper seems to imply that $[[U (F A)]]$ is a predomain created by lifting $[[A]]$ (by adding an additional bottom element below all elements of $[[A]]$). Does that make sense? If so, $T = U \circ F$ would seem to be a partiality monad, matching the fact that this definitions are needed to support the "divergence side effect".

*The definition of predomain is longer, but apparently it does indeed not imply the existence of least elements, so it should be irrelevant to the question. For reference:

  A predomain $(X, \le)$ is a countably based, algebraic directed-complete poset, with joins of all nonempty bounded subsets, in which the down-set $\{y \in X : y \le x\}$ of each $x \in X$ has a least element.


texts:
For $p\in[0,1]^{\mathbb{N}}$ and $\alpha\ge1$, define
$$ H_\alpha(p) = \sum_{i\in\mathbb{N}}p_i|\log(p_i)|^\alpha.
$$
When $\sum_i p_i=1$ and $\alpha=1$, $H_1(p)$ is just the Shannon entropy of the distribution $p$. Has anyone encountered the object $H_\alpha$ anywhere in the literature? A reference would be much appreciated. I'm thinking of calling $H_\alpha$ hyperentropy for $\alpha>1$; is that term already taken by chance?


texts: Number of different longest common substrings

texts:
Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common substrings of $w_1,w_2$. We can define $A(w_1,w_2)$ as follows:
$$A(w_1,w_2)=\{s\in\Sigma^*\mid w_1=x_1sx_2,\;w_2=y_1sy_2,\;x_1,x_2,y_1,y_2\in\Sigma^*\}$$
In genereal, this substring $s$ is not unique. Therefore, I am looking for the maximal number $m(k,n)$ of different longest common substrings for an arbitrary pair of strings of length $n$. Formally:
$$m(k,n)=\max\limits_{w_1,w_2\in\Sigma^n}\left|\left\{s\in A(w_1,w_2)\mid\forall x\in A(w_1,x_2):\;|s|\ge |x| \right\}\right|$$

Natural upper bound: It is easy to see, that $m(k,n)\le n$ since the maximal number of substrings of the same length for a strings of length $n$ is $n$ (for substrings of length $1$). For $n\le k$ we even achieve $m(k,n)=n$ (take a string $w_1$ which consists of different letters and $w_2$ the reverse string of $w_1$). For $n> k$ we conclude that $m(k,n)<n$, but from now on it seems to be difficult.

Lower bound: Based on De-Bruijn sequences it is possible to deduce a lower bound as follows:
As a conclusion of a paper of  Lin et al, for each $m$ there are orthogonal De-Bruijn sequences $B_1(k,m)$ and $B_2(k,m)$ of length $k^m$, which means that the longest substring of $B_1(k,m)$ and $B_2(k,m)$ is of length $m$. The special property of (those) De-Bruijn sequences is, that each string of length $m$ is actually a substring (some of them by reading the De-Bruijn sequence cyclic). Therefore, both $B_1(k,m)$ and $B_2(k,m)$ containing $k^m-m+1$ different subtrings of length $m$ (acyclic) and for that reason there are at least $k^m-2m+2$ different longest common substrings for $B_1(k,m)$ and $B_2(k,m)$. So, for $n$ as a power of $k$, we get
$$m(k,n)\ge n-2\log_kn+2$$
I'm quite sure we can achieve a very close result (caused by some rounding-issues) for each $n$.

But my question is, how tight are these bounds? I could imagine that orthogonal De-Bruijn sequences are already (asymptotic) worst case examples, i.e.
$$m(k,n)\in n-\Theta(\log n).$$
But I am neither sure about this nor able to show it.

Any help is welcome!


texts:
We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem.

My question is

  about the density of primes when we choose random numbers from a different distributions.
  The main example I have is numbers of the form $2^a3^b5^c+1$. Are there theorems similar to the prime number theorem when we restrict the numbers to those of this form?

More generally, let's call a set $A \subseteq \mathbb{N}$ efficiently enumerable if there is a (deterministic) polytime algorithm enumerator for $A$, i.e. a polytime algorithm that whose range is exactly $A$ (and for simplicity lets assume that the enumeration is also injective so every member of $A$ appears exactly once) (is there a common name for this in the literature?).

  Are there efficiently enumerable sets such that a theorem similar to the prime number theorem or something stronger holds for the distribution of primes in them?

Note that if we can find prime numbers in deterministic polynomial time, then the density would be one for the corresponding set, but that is open for now, so can we get closer to density 1 by replacing $\mathbb{N}$ with another efficiently enumerable set?

This came out of a discussion a few days ago about better ways of finding primes in practice. If there is a deterministic polytime algorithm to find primes then the question for the corresponding enumeration would be trivial, but since that is open, one may want to see if there are other efficiently enumerable sets that can be used to find primes in practice. This might be related to the number of random bits that is used by a probabilistic polytime algorithm to generate primes also.

  What are the known upperbounds for the number of random bits (used by a probabilistic poly-time algorithm) are known for generating primes?


texts:
I'm wondering if there are any references on "reverse skolemization", that is, converting a formula with functions into one purely consisting of quantifiers by eliminating function applications.

I'm working in a boolean domain, and my end goal is to make something that can be solved by a QSAT solver.

For example, if I have a formula $\phi$ like this:

$\exists f : \mathbb{B}^n \to \mathbb{B}^n \ldotp \exists g : \mathbb{B}^n \to \mathbb{B} \ldotp \forall x : \mathbb{B}^n \ldotp g(x) \implies g(f(x)) $

I want to be able to convert it into an equi-satisfiable formula that quantifies over booleans, not functions, i.e. a formula whose skolemization is  $\phi$.

Is this possible, and if so, are there any references for how to do this algorithmically in the general case?


texts: Automata learning without counterexamples

texts:
In Angluin's automata learning framework, a student aims to learn a regular language $L\subseteq \Sigma^*$ by asking two types of questions to his teacher:

Word queries: given $w\in \Sigma^*$, is $w\in L$?

Equivalence queries: given a language $K\subseteq \Sigma^*$, is $K=L$? If not, the teacher gives a counterexample, i.e. a word $w\in K\setminus L \cup L\setminus K$.

Using Angluin's algorithm, the student learns $L$ with polynomially many queries in the number of states of the minimal DFA of $L$ and the size of the counterexamples.

Now, consider a restricted scenario where the teacher no longer gives counterexamples. Is it still possible to learn L with a polynomial number of queries? I conjecture that this is not the case because for every polynomial-length sequence of queries and answers, one can find several regular languages consistent with the answers.

Does anyone see how to prove this?


texts: Is this problem on unambiguous finite automata NP-complete?

texts:
An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such
that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp., $n$-NFA) is a UFA (resp., NFA) $A$ over alphabet $\{0,1\}$ such that $L(A) \subseteq \{0,1\}^n$. Without loss of generality, I will assume that such automata have exactly one initial state $q_I$ and one final state $q_F$ and that they are trimmed (meaning that each state is both accessible from $q_I$ and co-accessible from $q_F$). This implies in particular that all the paths from $q_I$ to some state $q$ have the same length. I am interested in the following decision problem:
INPUT: An $n$-UFA $A$, integer (or rational) weights $\beta_i \in \mathbb{N}$ for $1 \leq i \leq n$, and a threshold $t\in \mathbb{N}$.
OUTPUT: YES if there exists a word $w \in \{0,1\}^n$ such that $w \notin L(A)$ and $\sum_{i=1}^n w_i \beta_i \geq t$, NO otherwise.
Observe that this problem is in NP: guess a word $w \in \{0,1\}^n$, check in polynomial time that $w \notin L(A)$ and $\sum_{i=1}^n w_i \beta_i \geq t$ and accept if this is the case.
Question: is this problem NP-complete?
Some observations:

If we replace “$w\notin L(A)$” by “$w\in L(A)$”, then the problem becomes solvable in polynomial time, even for NFAs. Indeed, given an $n$-NFA, we can easily compute by induction, for every state $q$ that is at distance $i$ from $q_I$, the quantity $\max_{w \in \{0,1\}^i \text{ s.t. } q \in \delta(q_I,w)}(\sum_{j=1}^i w_j \beta_j)$, where $\delta(q_I,w)$ is the set of states that can be reached from $q_I$ by reading $w$.
If we consider the problem for NFAs instead of UFAs, then this is NP-complete. Indeed, if we let $\beta_i=1$ for $1 \leq i \leq n$ and $t=0$, then this is just asking if there exists a word of size $n$ that is not in the language, and there is an easy reduction from DNF falsifiability (the automaton nondeterministically branches to a gadget that checks a clause, or see this post for instance).
If all the $\beta_i$s are equal, then this is PTIME. Indeed, in that case the problem is simply
asking if there exists a word $w\in \{0,1\}^n$ of hamming weight $\geq \lceil \frac{t}{\beta} \rceil$ that is not in $L(A)$. But for $1 \leq j \leq n$, because $A$ is a UFA, we can easily compute in polynomial time the number of words $w \in \{0,1\}$ of hamming weight $j$ that are in $L(A)$, an so by a counting argument we can detect if one such word is missing. Hence, any hardness proof will need to use distinct $\beta_i$ values.
As observed in the comments, this problem can be rephrased using special kinds of unambiguous (Max,+) automata (see e.g., Section 3 of
Colcombet, Thomas, Unambiguity in automata theory), where all the  edges that are at the same distance from the initial state have the same weight.

As for the context: ultimately, I would like to obtain superpolynomial lower bounds on the size of UFAs recognizing the complement of UFAs that recognize finite languages. Since this seems hard, I'd like to at least obtain this conditionally to P $\neq$ NP. So I came up with this problem which, if proven NP-complete, would show that we cannot complement a UFA recognizing a finite language in PTIME. Note that Raskin, Michael, A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton shows such a lower bound, but the UFAs that are used are cyclic, and the proof seems to crucially rely on this.


texts: Is the AND logic function considered to be a bent function? If it is, how could one make a hyper-bent funtion using logic gates? Thank you (two questions in one: very efficient :) )


texts:
I am reading the proof from here and I stumbled upon a technical (yet crucial) problem. I know this is rather specific and the context is problematic, but I couldn't figure it out myself.

In pages 51 and 55, after presenting the "standard" verifiers, they turn to modify the verifiers in order to check split assignments.

In the first case (p. 51) they check that $f_1,\dots,f_k$ are $0.01$-close to the polynomial code, and then they use the Algebraization (+Zero-Testers) to construct a family of polynomials (with a Sum-Check property related to the input formula) that each can be evaluated at a point given 3 values of each of $\widetilde{f}_1,\dots,\widetilde{f}_k$ (the codewords of the polynomial code closet to $f_1,\dots,f_k$).

In the second case (p. 55) they check that $f_1,\dots,f_k$ are $0.01$-close to being linear, and then they define a function $f$ to be a special sum of $\widetilde{f}_1,\dots,\widetilde{f}_k$ such that $f$ can be evaluated at a point given values of each of $\widetilde{f}_1,\dots,\widetilde{f}_k$ (the linear functions closet to $f_1,\dots,f_k$).

Then in both cases they perform tests (Sum-Check or Tensor + Hadamard) on the values of a random polynomial in the family / $\widetilde{f}$.

My problem is that the procedure for reconstruction of the required values of each of $\widetilde{f}_i$ can provide incorrect values with some non-negligible constant probability. Moreover, the probability that all the values are reconstructed correctly is very low, only $c^k$ for some constant $c$. And this is true for both cases.

This can be bad as some of the steps of the verifiers require to obtain values of the target function $f$ / a polynomial from the family w.h.p.

So, we need to amplify the success probability by repeatedly using the "reconstruction algebraic procedure" some $O(\log k)$ times for each $\widetilde{f}_i$.

Now, this means that the blow-up in the query complexity of the sub-routine (relatively to the query complexity of the original verifiers) is slightly larger than $k$, i.e. it is $O(k\log k)$ (in contrast to the "guaranteed"-"desired" $O(k)$ blowup in the statement of the theorems).

Is this a problem or am I missing something (which I probably am)?


texts: Best communication complexity lower bound of disjointness

texts:
It is well known that no deterministic two-party protocol can solve disjointness problem (DISJ) on $n$-bit inputs without sending $n+1$ bits in the worst case (see, e.g., the book by Kushilevitz and Nisan). For bounded-error randomized protocols, a lower bound of $\delta n$, for some constant $\delta$, has also been shown in a seminal paper by Razborov [Razborov92]. My question is:

  What is the best known explicit value of $\delta$ currently (both upper and lower bounds)?

Also, is there any belief on the actual value of $\delta$?

[Razborov92] Alexander A. Razborov: On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2): 385-390 (1992) doi:10.1016/0304-3975(92)90260-M


texts: Planarity testing of directed graph and 3d grid

texts:
I wonder if there exist definitions (and known algorithms) of planarity testing for the following case:

1-  A directed graph

let $G=(V=\{1,\ldots,n\},E)$ be a directed graph.

Assume $e_{ij} =(v_i,v_j), e_{ji} = (v_j,v_i)$ are two unique edges.

I'm looking for a known (similar) definitions for this kind of planarity testing that forbids any of the above combinations for $1\leq i<j \leq n$.

2- A 3d grid

Assume our graph is embedd in a 3d grid, where each point the grid has the following structure: $(i,j,k)$, where w.l.o.g $1\leq i<j<k \leq n$.
And the edges must be "straight" (in the 3d-world).

I'm asking whether it is known a problem and there are known planarity testing algorithms for this kind of problem.

Thanks.


texts: Constructing terms of function types out of the empty type

texts:
If a function $f$ is understood as its graph, i.e. a set of pairs $\langle x,y\rangle$ where $x$ is input and $y$ is output, then the empty set $\emptyset$ is a valid function, and for any set $A$, we have the empty function in $\emptyset\to A$. This makes $\emptyset$ the initial object in the category of sets. By set extensionality, there is only this empty function and this also fits with cardinalities, where we like $|A^{\emptyset}|=|A|^{|\emptyset|}=1$.
In logic, we usually take that form absurdum follows everything, ex falso quodlibet, and in the propositions interpretation for types, if $\bf 0$ denotes the empty type (or bottom type), we want a function ${\bf 0}\to \tau$ for all types $\tau$ too.

I've been told in some programs this would be done by defining alla

definition exfalso (a : Type) (x : 0) : a := "case x of -emptyspace-"

Now I try to construct the terms for function types involving the empty type over the standard theories you'd find in books, but I can't quite reproduce the good properties, see below. I wonder

  Which type theories actually let you construct a term of a function type from the empty type, and then, is it unique?

My considerations (leading to more question) are this...

Take simply types lambda calculus. We have $(\lambda (x:\tau).x):\tau\to\tau$ and so $(\lambda (x:{\bf 0}).x):{\bf 0}\to{\bf 0}$. In any model of the type theory, this will be the empty function and so I'm okay with that. But how do I construct, from the typing rules of the theory, any type of ${\bf 0}\to{\bf \tau}$, where $\tau$ isn't ${\bf 0}$? And then, how is there only one? Depending on how the theory lets you define functions, I could imagine ${\bf 0}\to\mathrm{Nat}$ to have zero or an infinite number of terms (constant functions which can never take any input). I guess the cardinal arithmetic then only works out once we pass to the set theoretic model, where all those constant functions are, extensionally, the empty function. Is that right? In a type theory with booleans $\bf 2$, how many functions $\bf 0\to\bf 2$ are there? If $a,b:\bf 2$, are $\lambda x.a$ and $\lambda x.b$ generally two function of this type?


texts: Understanding efficient classical simulation of quantum computing

texts:
I want to understand the Gottesman-Knill theorem, which basically says that using some subclass of unitary transformations (from the Clifford group) there is no quantum speed-up ie. we can simulate the system efficiently on a classical computer.

I want to understand the claims presented in http://core.ac.uk/download/pdf/11923581.pdf .
The author says that the reason that using only Clifford group brings efficient classical simulation is because the transformations in Clifford group inlcude only rotations of the Bloch sphere by multiples of $\pi/2$. He then goes on to explain that these transformations don't violate Bell's inequalities (specifically CHSH inequalities):

  In an entangled quantum system, no amount of $k\pi/2$
  transformations of one of the constituent systems will cause it to take on an
  orientation with respect to the other subsystems that is not a multiple of $\pi/2$ (unless it was so oriented initially).And as we have seen above, the statistics of compound
  states for which the difference in orientation between subsystems is a multiple of $\pi/2$
  are capable in general of being reproduced by a classical hidden variables theory.

I wan't to know if this claim is correct and first of all, I would be happy if someone explained this to me on an example. I heard that stabilizer formalism can violate Bell's inequalities so this is all weird to me.

PS. My basic intention is to have a clearer picture of why some subclass of transformations can be efficiently simulated classicaly and I thought this would be a nice way to understand it (if of course it is true). If anyone has any other ideas as to how to explain the Gottesman-Knill (besides stabilizer formalism), I would be very happy.


texts: Maximize graph with k cut edge operations

texts:
I have undirected graph with N nodes each with some weight. There are M edges and in exactly K operations I want to maximize the XOR sum of connected components of the graph. ((n1 XOR n2 XOR n3) + (c1 XOR c2 XOR c3)).
(There can be multiple edges between 2 nodes.

I've tried attempting it with Minimum spanning tree with cut edge but couldn't succeed. Any help?


texts: Representing boolean function by a polynomial

texts: Supposing we have a boolean function from $f:\{0,1\}^n\rightarrow\{0,1\}$. It is clear that a real multivariate polynomial $p(x)$ such that $f(x)=p(x)$ on $x\in\{0,1\}^n$ can be multilinear. What are some interesting classes of boolean functions for which the minimal degree of $p(x)$ is known? Do we have concrete examples?


texts:
Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph or consists of a single edge with $|V_i|=2$.

Example: The complete bipartite graph $K_{m,n}$ possesses a Hamilton decomposition if and only if $m=n$.

I am looking for an algorithm that decides whether a given graph possesses a Hamilton decomposition. Is this decision problem NP-complete? If not, how can we find such a decomposition?

Note: In the literature a Hamilton decomposition often denotes a decomposition of the edges $E$ of $G$ such that the induced subgraphs are Hamilton. In contrast I am interested in a decomposition of the vertices.


texts: Problems not known to be PSPACE-complete

texts:
What are problems with the following properties:

1) they are restriction of (possibly well known) problems that are PSPACE-complete;

2) the restricted versions are in PSPACE, but it is an open problem if they are PSPACE-complete (or even if they are NP-hard).

Four examples from "puzzles & C.":

The complexity of 1x1 Rush Hour [1] (PSPACE-complete for blocks of size 2x1 );
[SOLVED] The complexity of planar Subway Shuffle [1] (PSPACE-complete even for planar graphs, a draft of the paper can be downloaded here );
The complexity of Lunar-Lockout without fixed blocks [1] (PSPACE-complete with fixed blocks);
(not so famous) The complexity of (my) Switch-network problem (it is a restriction of the PSPACE-complete Sokoban, NP-hard in the non-planar case, see this Q&A on cstheory).

If you have many, group them by topic.

[1] Robert A. Hearn, Erik D. Demaine: Games, puzzles and computation. A K Peters 2009, ISBN 978-1-56881-322-6, pp. I-IX, 1-237


texts:
Post's lattice, described by Emil Post in 1941, is basically a complete inclusion diagram of sets of Boolean functions that are closed under composition: for example, the monotone functions, the linear functions over GF(2), and all functions.  (Post didn't assume that the constants 0 and 1 were available for free, which made his lattice much more complicated than it would be otherwise.)

My question is whether anything analogous has ever been published for classical reversible gates, like the Toffoli and Fredkin gates.  I.e., which classes of reversible transformations on {0,1}n can be generated by some collection of reversible gates?  Here are the rules: you're allowed an unlimited number of ancilla bits, some preset to 0 and others preset to 1, as long as all the ancilla bits are returned to their initial settings once your transformation of {0,1}n is finished.  Also, a SWAP of 2 bits (i.e., a relabeling of their indices) is always available for free.  Under these rules, my student Luke Schaeffer and I were able to identify the following ten sets of transformations:

The empty set
The set generated by the NOT gate
The set generated by NOTNOT (i.e., NOT gates applied to any 2 of the bits)
The set generated by CNOT (i.e., the Controlled-NOT gate)
The set generated by CNOTNOT (i.e., flip the 2nd and 3rd bits iff the 1st bit is 1)
The set generated by CNOTNOT and NOT
The set generated by the Fredkin (i.e., Controlled-SWAP) gate
The set generated by Fredkin and CNOTNOT
The set generated by Fredkin, CNOTNOT, and NOT
The set of all transformations

We'd like to identify any remaining families, and then prove that the classification is complete---but before we spend much time on it, we'd like to know whether anyone has done it before.


texts:
(Unlike most posts on stackexchange with that word,

I really do doubt that they work as described.)

In Figure 15 of this paper, the cells two to the right of the leftmost circle and two to the left of the rightmost circle hold the values 3 and 1 respectively. $\:$ Due to the rows of 1s that are three above each of those circles, the mostly-blank area is presumably supposed to have no mines, which would make the value 3 impossible. $\:$ Since the figure is otherwise mostly symmetric, I believe the 3 I mentioned two sentences ago should be replaced with a 1. $\:$ However, even if that is done, I do not see any way to determine the status of the $z$s even after both $r$ and $s$ are revealed, despite the three sentences on the previous page whose middle sentence starts with "Additionally". $\:$ For the same reason, Figure 14 also does not seem to do what it is supposed to.

  Am I missing something here?


texts: Why is plus-comm a b $:\equiv$ refl (plus a b) not a proof of the commutativity of addition?

texts:
I've been curious about the 'geometric situation' that one has when considering the type
$\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)$.
Here, addition is defined in the usual inductive way.
This proposition has an informative proof, which I will denote by $\textrm{plus-comm}$. One interesting property that I've observed of this proof is that it computes to reflexivity on any specific $\textrm{Nat}$ values. I conjecture that this should be true of all terms of this type in my system.
That is, if $a$ and $b$ are $\textrm{Nat}$ values, then $(\textrm{plus-comm}\ a\ b) \equiv \textrm{refl}\ (\textrm{plus}\ a\ b)$. For instance, this says that answering the question 'Why is 2+3 = 3+2?' with 'Because the commutative law of addition holds' reduces to 'Because both equal 5'. (In reference to a passage by Morris Klein. :P)
We have a term
$$\lambda n, m. \textrm{refl}\ (\textrm{plus}\ n\ m) : \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m).$$
If we could show that the type $ \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m)$ equaled the type $\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)$, then this term yields* a valid proof of commutativity, which is something that I proximally find highly intuitively unappealing.
Now, I can't seem to prove the equality stated above from commutativity, and I imagine that there is a good reason for why this is impossible.
* I am assuming extensionality and univalence. Thus, an equality of said types would yield an equivalence by which I could map the reflexivity term. However, the types in question shouldn't have any non-trivial higher groupoid structure, so I don't imagine that HoTT operations would perform any non-trivial computations (such as identifying these two proofs) in this setting. If the resolution of this question involves HoTT ideas, then I would be very intrigued.
What is going on in this situation?
TL;DR: We have that:
$$n, m:\textrm{Nat} \vdash (\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m).$$
Why does it not follow that:
$$\vdash \left(\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m)\right) = \left(\prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)\right)?$$


texts:
Are there any algorithms for SAT solving which are not DPLL based?
Or are all algorithms used by SAT solvers are DPLL based?


texts: On theoretical aproaches for solving $\mathsf{SAT}$ in special cases

texts:
In what cases $\mathsf{SAT}$ can be solved in polynomial time?

I know two cases: $2$-$\mathsf{SAT}$ and Horn-$\mathsf{SAT}$.

Question 1: Is there a reference with algorithms for solving $\mathsf{SAT}$ effectively in some other cases?

I think that it is important to understand in what case $\mathsf{SAT}$ can be solved effectively. It can be related to the problem of understanding of effectivity of $\mathsf{SAT}$-solvers. And this is why I am surprised why there are small papers about this theme (it would be nice if I am wrong).

In fact there is a simple method for generating examples when $\mathsf{SAT}$ can be solved effectively:  Consider some $\mathsf{L}\in\mathsf{P}$.  For every $x$ there exists $\mathsf{CNF}$ $\phi_x$ such that $x\in\mathsf{L}\iff\phi_x$ is satisfiable. So, for $\mathsf{CNF}$ of kind $\phi_x$ there exists a polynomial algorithm for $\mathsf{SAT}$.

Example: Consider $\mathsf{L}$ to be $2$-$\mathsf{COLORING}$. This problem is reduced to $2$-$\mathsf{SAT}$ problem.

Question 2: Are there any other examples when a problem from $\mathsf{P}$ can be reduced to $\mathsf{CNF}$ of some adequate form (i.e. it is possible to analyse it and understand why it can be solved in polynomial time)?


texts: Large classes which contain LOGSPACE for which strict inclusions are unknown

texts:
The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references).

Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these known to be strict?

Q2: If no, is there an established class $C$ which contains $P^{\#P}$ and for which it is not known if the inclusion $L\subset C$ is strict?

Q3: Are such inclusions discussed in literature?


texts: A comparison of extractors in terms of tradeoffs between time, randomness and space ?

texts: Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?


texts: Is there an approximation algorithm for MAX k DOUBLE SET COVER?

texts:
Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define the following maximization problem:

MAX k DOUBLE SET COVER
INPUT: a set system $(X,\mathcal S)$, an integer $k$
OUTPUT: a set $\mathcal C\subseteq \mathcal S$, $|\mathcal C| \le k$
MEASURE: the number of elements of $X$ that are doubly covered by $\mathcal C$

MAX k DOUBLE SET COVER is a generalization of the problem MAX k SET COVER, where we only require simple coverage instead of double coverage (see the celebrated 1998 paper by Feige, "A threshold of $\ln n$ for approximating Set Cover"), where a $(1-1/e)$-approximation is given).

  My question: Is there any known nontrivial positive approximation bound for MAX k DOUBLE SET COVER?
  Note: I am especially interested in the restriction where the set system has maximum intersection one, that is, any two sets in $\mathcal S$ share at most one element (SET COVER for these set systems remains hard to approximate, see this paper).

As pointed out in the answer to this other question, the problem DENSEST k-SUBGRAPH is a special instance restriction of MAX k DOUBLE SET COVER with set systems with intersection one: an input graph $G$ corresponds to the hypergraph $(E(G),\mathcal S_G)$ where $\mathcal S_G$ has a set $S_v$ for each vertex $v$ of $V(G)$ containing the edges incident to $v$ in $G$.
DENSEST k-SUBGRAPH has an $O(n^{1/4})$-approximation algorithm (this paper); perhaps this algorithm can been (has been) extended to MAX k DOUBLE SET COVER (for set systems with intersection one)?
(The complexity of DENSEST k-SUBGRAPH being well-studied and a tough open problem, for MAX k DOUBLE SET COVER I am not expecting anything better than an approximation ratio of the form $O(n^{\delta})$ for some $\delta<1$.)

Any related observation or reference is welcome. Thanks!


texts: Strongly Regular Graph and GI-Completeness

texts: It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (Similar to the belief that GI may not be NP-Complete).


texts: Can a det. $k$-counter machine ($k \geq 2$) be simulated by a det. $k'$-counter machine using non-$\epsilon$-moves followed by $\epsilon$-moves?

texts:
I have a question concerning deterministic $k$-counter machines, for $k \geq 2$. Recall that in this context, the determinism is expressed by the fact that the machine can never face a choice between either reading a (proper) symbol of its input alphabet, or reading $\varepsilon$ (i.e., the empty symbol). In other words, let's call a transition involving a non-empty input symbol a "regular transition", and a transition involving $\varepsilon$ an "$\varepsilon$-transition" (like as usual). The determinism condition simply states that the machine never has to choose between a regular or an $\varepsilon$-transition (cf. Book by Hopcroft, Motwani and Ullman 2001, p.349).

In this context, I would like to know if every $k$-counter machine $\mathcal{C}$, for $k \geq 2$, can be simulated by a $k'$-counter machine $\mathcal{C}'$ which, on every input, always uses regular transitions followed by $\epsilon$-transitions?

For the case of stacks machines with a stack alphabet larger than or equal to the input alphabet, I believe that the answer is yes. The idea would be to consider a machine $\mathcal{C}'$ which always begins by copying its input on a designated stack – using only regular transitions – and then works exclusively by considering this stack as a kind of input tape – using only $\epsilon$-transitions.

What about the case of $k$-counter machines ($k \geq 2$)?


texts: How do journals serve the TCS community?

texts:
In the past, journals were the main way scientific/mathematical discoveries were disseminated and vetted. In some areas, they still are. However, in (theoretical) computer science that role is almost entirely performed by conferences and open web-based dissemination (e.g. arxiv or personal homepages).

There are still TCS journals (like ToC and JACM), but they seem to primarily publish papers that have already appeared in conferences and usually have an arxiv preprint. So I don't understand what value they are adding.

What purpose do journals serve in TCS?

I have heard three arguments in favour of journals, but I don't find any of them convincing:

Journals supposedly have higher standards for reviewing than conferences. It is true that conference reviewing is under greater time pressure, but it is still the same pool of reviewers (and the amount of time the reviewer is given to read the paper has very little correlation with how long they actually spend reading the paper). As a reviewer, I don't fundamentally treat a journal review request any differently than I treat an external review for a conference.
Journal versions are higher quality than conference versions. This is true, but it is moot, as most people will read neither. When I want to read a paper, I search for it and click on the most promising link, which is almost always the arxiv version. Thus it is extremely rare for me to read a journal version of a paper even if it exists.
Journals can provide an additional quality signal on top of which conference the paper appeared in. This seems superfluous and a lot of effort for very little signal.

I have only submitted to TCS journals when invited. I have found the process tiresome, since it creates extra work and drags on for years. Thus I am not inclined to submit otherwise. Is there a good reason for me to submit?


texts: Empirical Rademacher averages versus Hoeffdings bound

texts:
Let $M$ be finite set with $n$ distinct elements. I want to probalistically  approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$.

An upper-bound for the number of samples need to get an (additive) $\varepsilon$-approximation can be derrived using the Hoeffding bound.

I am interested in achieving (empirical) better bounds using empirical Rademacher averages. My idea is to adaptability sample from $M$, to fulfill
    \begin{equation}
  \sup_{f \in \mathcal{F}}\,| L_{\mathcal{D}}(f) - L_{S}(f) | \leq 2\cdot\mathcal{R}_{\mathcal{F}}(S) + 3 \sqrt{\frac{ \log (2/\delta)}{2m}} \leq \epsilon,
 \end{equation}
where
\begin{equation*}
 \mathcal{F} = \{ \mathbf{1}_{Q} \mid Q \subseteq M \},
\end{equation*}
and $\mathbf{1}_{Q}$ equals $1$ if the current sample is in $Q$, and otherwise $0$.
It follows that
\begin{equation*}
 L_{\mathcal{D}}(\mathbf{1}_{Q}) =  \frac{|P(Q)|}{|M|}.
\end{equation*}

Can one achieve better bounds using this approaches, e.g., by using Massart's Lemma to approximate $\mathcal{R}_{\mathcal{F}}(S)$?


texts:
In simple form:

  Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states?

Details

Of interest here are $v$-vertex graphs encoded using a sequence of edges, each edge being a pair of distinct vertices from $\{0,1,\dots,v-1\}$.

Suppose $(M_v)$ is a sequence of two-way finite automata (deterministic or nondeterministic), such that $M_v$ recognizes $k$-Clique on $v$-vertex input graphs and has $s(v)$ states.
A general form of the question is then:
Is $s(v) = \Omega(v^k)$?

If $k = k(v) = \omega(1)$ and $s(v) \ge v^{k(v)}$ for infinitely many $v$, then NL ≠ NP.
Less ambitiously, I am therefore stipulating that $k$ is fixed, and the $k=3$ case is the first nontrivial one.

Background

A two-way finite automaton (2FA) is a Turing machine which has no workspace, only a fixed number of internal states, but can move its read-only input head back and forth.
In contrast, the usual kind of finite automaton (1FA) moves its read-only input head in one direction only.
Finite automata can be deterministic (DFA) or nondeterministic (NFA), as well as having one-way or two-way access to their input.

A graph property $Q$ is a subset of graphs.
Let $Q_v$ denote the $v$-vertex graphs with property $Q$.
For every graph property $Q$, the language $Q_v$ can be recognized by a 1DFA with at most $2^{v(v-1)/2}$ states, by using a state for every possible graph and labelling them according to $Q$, and transitions between states labelled by edges.
$Q_v$ is therefore a regular language for any property $Q$.
By the Myhill-Nerode theorem there is then a unique up to isomorphism smallest 1DFA that recognizes $Q_v$.
If this has $2^{s(v)}$ states, then standard blowup bounds yield that a 2FA recognizing $Q_v$ has at least $s(v)^{\Omega(1)}$ states.
So this approach via standard blowup bounds only yields at most a quadratic in $v$ lower bound on the number of states in a 2FA for any $Q_v$ (even when $Q$ is hard or undecidable).

$k$-Clique is the graph property of containing a complete $k$-vertex subgraph.
Recognizing $k$-Clique$_v$ can be done by a 1NFA that first nondeterministically chooses one of $\binom{v}{k}$ different potential $k$-cliques to look for, and then scans the input once, looking for each of the required edges to confirm the clique, and keeping track of these edges using $2^{k(k-1)/2}$ states for each of the different potential cliques.
Such a 1NFA has $\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$ states, where $1 \le c_v \le e$.
When $k$ is fixed, this is $\Theta(v^k)$ states.
Allowing two-way access to the input potentially allows an improvement over this one-way bound.
The question is then asking for $k=3$ whether a 2FA can do better than this 1FA upper bound.

Addendum (2017-04-16): see also a related question for deterministic time and a nice answer covering the best known algorithms.
My question focuses on nonuniform nondeterministic space.
In this context the reduction to matrix multiplication used by the time-efficient algorithms is worse than the brute-force approach.


texts: Enumerating topological sorts of a vertex-labeled DAG

texts:
Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a topological sort of $G$ is a bijection $\sigma$ from $\{1, \ldots, n\}$ to $V$ (i.e., an ordering of $V$ in a sequence) such that whenever $(v, v') \in E$ then $\sigma^{-1}(v) < \sigma^{-1}(v')$ (i.e., if there is an edge from $v$ to $v'$ then $v$ occurs before $v'$ in the sequence). The label of $\sigma$ is the word $\sigma(1) \cdots \sigma(n)$ in $L^n$.

Given $(G, \lambda)$, I would like to enumerate the labels of topological sorts of $G$ efficiently. What is the complexity of enumerating the labels of topological sorts? Of course, as there can be exponentially many, I want to study complexity as a function of the size of the output, or in terms of delay. In particular, can enumeration be performed with polynomial delay? (or even constant delay?)

In the case where all vertices of $G$ carry distinct labels (or, equivalently, the vertices are $\{1, \ldots, n\}$ labeled by themselves), I know that labels can be enumerated in constant amortized time, by this result on enumerating linear extensions of posets (which is the same thing as enumerating topological sorts of a DAG). However, when vertices are labeled arbitrarily, it could be the case that a very large number of topological sorts have the same label, so you can't just enumerate topological sorts of $G$ and compute their labels to get an efficient way to enumerate the labels. In poset terminology, the labeled DAG $(G, \lambda)$ can be seen as a labeled poset, and I couldn't find enumeration results about those.

I already know the hardness of some related problems thanks to answers to my other questions here. In particular, I know that finding the lexicographically minimal label is NP-hard. I also know that deciding whether a given label can be achieved by some topological sort is NP-hard (from the hardness of this problem: given a candidate label sequence $s$, ask for a topological sort of $G$ where each vertex must occur at a position where the right label occurs in $s$). However, I don't think that any of this implies hardness for enumeration, as you may enumerate in any order you like (not necessarily lexicographic), and an enumeration algorithm can't be used to decide efficiently whether a label is achievable, even with constant delay (as there may be exponentially many sequences to enumerate first).

Note that, it is obviously easy to enumerate a first label $s$ (just take any topological sort). To enumerate another label than $s$, you can proceed by imposing that some element $v$ of $V$ gets enumerated at some position $i \in \{1, \ldots, n\}$ where $s_i \neq \lambda(v)$: try out every $v$ and $i$, and check if $G$ has a topological sort where $v$ is at position $i$, which can clearly be done in PTIME. But as you output more and more labels, I'm not sure of how to generalize this approach.


texts: None-monotone submodular function examples

texts: What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?


texts: What is the difference between meaning and denotation?

texts: In programming language semantics, it is often heard that people talking about meaning and denotation.  They seem not to be the same.  What is the difference?  Is the former associated with operational semantics while the latter with denotational semantics?  Thanks.


texts: Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?

texts:
Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?

$isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$
$link(G,a,b)$: Adds an edge from $a$ to $b$ in the graph $G$
$unlink(G,a,b)$: Removes the edge from $a$ to $b$ in $G$
$add(G,a)$: Adds a vertex to G
$remove(G,a)$: Removes a vertex from G

A few notes:

If we disallowed $unlink$, it seems it would be easy to maintain the connectedness information, using a disjoint-set type data structure.
Obviously, $isConnected$ could be implemented using depth or breadth-first search, using the naive pointer-based representation of the graph. But this is inefficient.

I'm hoping for amortized constant or logarithmic time for all three operations. Is this possible?


texts: Lexicographically minimal topological sort of a labeled DAG

texts:
Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and where we are asked to compute the lexicographically smallest topological sort of $G$ in terms of $\lambda$. More precisely, a topological sort of $G$ is an enumeration of $V$ as $\mathbf{v} = v_1, \ldots, v_n$, such that for all $i \neq j$, whenever there is a path from $v_i$ to $v_j$ in $G$, then we must have $i < j$. The label of such a topological sort is the sequence of elements of $S$ obtained as $\mathbf{l} = \lambda(v_1), \ldots, \lambda(v_n)$. The lexicographical order on such sequences (which all have length $|V|$) is defined as $\mathbf{l} <_{\text{LEX}} \mathbf{l'}$ iff there is some position $i$ such that $l_i <_L l_i'$ and $l_j = l'_j$ for all $j < i$. Pay attention to the fact that each label in $S$ can be assigned to multiple vertices in $V$ (otherwise the problem is trivial).

This problem can be stated either in a computation variant ("compute the lexicographically minimal topological sort") or in a decision variant ("is this input word the minimal topological sort?"). My question is, what is the complexity of this problem? Is it in PTIME (or in FP, for the computation variant) or is it NP-hard? If the general problem is NP-hard, I am also interested about the version where the set $S$ of possible labels is fixed in advance (i.e., there are only a constant number of possible labels).

Remarks:

Here is a small real-world example to motivate the problem. We can see the DAG as representing tasks of a project (with a dependency relationship between them) and the labels are integers representing the number of days that each task takes. To finish the project, it will take me the same total amount of time no matter the order I choose for the tasks. However, I would like to impress my boss, and to do this I want to finish as many tasks as possible as fast as possible (in a greedy manner, even if it means being very slow at the end because the harder tasks remain). Choosing the lexicographically minimal order optimises the following criterion: I want to choose an order $o$ such that there is no other order $o'$ and a number of days $n$ where after $n$ days I would have finished more tasks with order $o'$ than with order $o$ (i.e., if my boss looks at time $n$, I give a better impression with $o'$), but for all $m < n$ I have finished no less tasks with order $o'$ than with order $o$.

To give some insight about the problem: I already know from previous answers that the following related problem is hard: "is there a topological sort which achieves the following sequence"? However, the fact here that I want a sequence which is minimal for this lexicographic order seems to constrain a lot the possible topological orders that may achieve it (in particular the reductions in those other answers no longer seem to work). Intuitively, there are much less situations where we have a choice to make.

Note that there seems to be interesting rephrasings of the problems in terms of set cover (when restricting the problem to DAGs that are bipartite, i.e., have height two): given a set of sets, enumerate them in a order $S_1, \ldots, S_n$ that minimises lexicographically the sequence $|S_1|$, $|S_2 \backslash S_1|$, $|S_3 \backslash (S_1 \cup S_2)|$, $\ldots$, $|S_n \backslash (S_1 \cup \cdots \cup S_{n-1})|$. The problem can also be rephrased on undirected graphs (progressively expand a connected area of the graph following the order that minimizes the lexicographic sequence of the uncovered labels). However, because of the fact that the sequence has to be greedy at all times by definition of the lexicographic order, I can't get reductions (e.g., of Steiner tree) to work.

Thanks in advance for your ideas!


texts: Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

texts:
The $k$-cycle problem is as follows:

Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.

Question: Does there exist a (proper) $k$-cycle in $G$?

Background: For any fixed $k$, we can solve $2k$-cycle in $O(n^2)$ time.

  Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J.  Discrete Math. 10(2): 209-222 (1997)

However, it is not known if we can solve 3-cycle (i.e. 3-clique) in less than matrix multiplication time.

My Question: Assuming that $G$ contains no 4-cycles, can we solve the 3-cycle problem in $O(n^2)$ time?

David suggested an approach for solving this variant of the 3-cycle problem in $O(n^{2.111})$ time.


texts: Texts on application of randomized algorithms

texts:
as far as I know, Motwani & Raghavan, ”Randomized Algorithms”, Cambridge University Press, 1995 is the standard book for randomized algorithms. This is an excellent theoretical intro.

Which is another book (or book containing chapters) on applied randomized algorithms, especially on image processing, bioinformatics or pattern matching.

Thanks,
Lucian


texts: Travelling Salesman and Planar Travel - Generalized TSP

texts:
Our beloved Travelling Salesman just bought the Manual of the Planes and wants to make some use of it. He is not a great adventurer though, so he will restrain his travels in the Parallel and Fundamental Planes, which are tightly coupled with the Material Plane (and try not to spend so much time in the Quasi-elemental Plane of Minerals and all the gold that lies there!). Let's say therefore that we have M-1 Parallel Planes and our salesman can visit each city in any of them. Travel from Material Neverwinter to Astral Luskan is of course different than travel from Material Neverwinter to Material Luskan and not always in a trivial manner (might cost more, might cost less). To make matters worse, the Salesman can visit each city in only one Plane and cannot therefore benefit from a portal connecting Shadow Waterdeep with Faerie Baldur's Gate if he initially arrived in Material Waterdeep (assume Dimensional Anchors covering the cities). So the Salesman has to complete his path using these new restrictions.

A 4th Level Wizard exclaimed instantly that this Plane Travelling Salesman has a problem that is not easier than those of his normal colleagues (just assume that the travel between two cities costs the same regardless of the Planes used and you have a classic TSP). The question is: How can he convert the problem into another that has already been researched by the scholars?

Less nerdy description:

Replace each of the N nodes in the original TSP with M subnodes. Distances are given for every pair of subnodes between different nodes. For each node, a single subnode must be used in the solution. Give an algorithm for the new problem.

Edit:

It turns out that it is indeed a well-researched problem so I am adding all the aliases I found for it.

Generalized TSP
Group TSP
TSP with Neighbourhoods
Set TSP
One-of-a-Set TSP
Multiple Choice TSP
Covering Salesman Problem


texts:
I am a Computer Science student who is greatly intrigued by algorithms.

However I am curious whether computer scientists who study algorithms teach themselves to formally analyze algorithms and prove the correctness of algorithms as is done in the CLR book, or do they mostly focus on the technique and design of the algorithms.


texts: Does optimal fitting flat must pass through the mean of the point set?

texts:
I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line.

Project clustering is a natural generalization of k-means clustering. Given a point set $P$, the goal to find $k$, $j$-dimensional affine spaces(flats) $F_1,\cdots,F_k$, such that the following objective function is minimized

$\sum_{p\in P} \min_{1\leq i \leq k}dist^2(p,F_i)$, where $dist(p,F)$ is the orthogonal distance between point $p$ and flat $F$.

Clearly, as is the case with k-means, the $k$ optimal flats induces a partitioning of the point set $P$, into $k$ subsets $C_1,\cdots,C_k$, such that points in $C_i$ is closer to flat $F_i$ than any other flat $F_j, i\neq j$.

The aforementioned paper (in page 7, third line from last), it is said that "It is easy to see that $F_i$  passes through the mean $o_i$ of $C_i$". I fail to see the simplicity of this. Can someone  please elaborate on that, with a proof sketch?

N.B: mean of a point set $P$ is defined as $\frac{1}{|P|}\sum_{p\in P}p$.


texts: Do past time LTL and future time LTL have the same expressiveness?

texts: I would like to ask if anybody is aware of a paper comparing the expressiveness of past time LTL and that of (future time) LTL.


texts: Ternary (and beyond) computation and quantum computing?

texts:
Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved.  I have always thought that having more states could improve computing power (e.g. using a trit instead of a bit), but there is a seeming lack of attention being paid to the problem.

Some work has been done in the quantum computing area using qubits to achieve more than the normal two energy levels (see, for example, the recent effort at UCSB).

What advances have been made toward having ternary (or greater) computers, and what are the primary the implications of the extra states?


texts:
Given an integer $K$, a set of tasks $T=\{a_1,b_1,\dots,a_n,b_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following structure:

Does an ordering function $F:T\rightarrow \{1,2,\dots, 2n\}$ exist such that $F(b_n) \leq K$ ($b_n$ is always the last task in the ordering)?
What is the computational complexity of the problem?

If arbitrary precedence constraints (or any partial orderings) are allowed then the problem is NP-Complete (becomes Jobshop / Flowshop or their variant). The question is what is the complexity in the case when the tasks have the precedence constraints with the fixed structure?


texts: Who introduced nondeterministic computation?

texts:
I have two historical questions:

  Who first described nondeterministic computation?

I know that Cook described NP-complete problems, and
that Edmonds proposed that P algorithms are "efficient" or "good" algorithms.

I searched this Wikipedia article and
skimmed "On the Computational Complexity of Algorithms,"
but couldn't find any reference to when nondeterministic computation was first discussed.

  What was the first reference to the class NP? Was it Cook's 1971 paper?


texts:
I am Ph.D student (about to graduate) in TCS. I have worked on some problems. I have been able to publish few research paper. There are many research problems in mathematics as well in TCS. I am sure that all of the problems of mathematics are not interesting to all TCS researchers. There seems to be gap between mathematics and TCS to me. I have made many attempts to define research problem on very old mathematical problems, some time algorithm is trivial and some time motivation is not clear to me. I don't if in the future I come up with an algorithmic problem on some mathematical problem will that be interesting to TCS community. I am here as I want to know when it makes sense to define a algorithmic question on mathematical problem for TCS researchers point of view. Let us say I am able to give an algorithm which classify all modules(Algebraic structure) of some rank. Will that interesting to TCS researchers?

There is one other way for me to not care about other and work on problems which I find interesting, but in that case I don't I will be a successful researcher or not.

In short while defining algorithmic question what are things or questions I should ask to myself

Question : What type of mathematical problems interesting for TCS researchers?


texts: Find all paths between specially paired nodes in a DAG in linear time

texts:
If I have a DAG with 2n nodes partitioned into n pairs of nodes with e edges, is there a linear-time (O(n + e)) way to find the subset of all pairs for which there exists a path from one to the other?
So for instance, in the DAG (letting \ and / be downward-pointing edges):
   A_1     C_2
  /   \   /   \
A_2    B_1     D_1
  \       \   /
   B_2     C_1
     \
      D_2

I want to return the set {A_2, C_1} since there exists a path from A_1 to A_2 and from C_2 to C_1, but there's no (directed) path between B_1 and B_2 or between D_1 and D_2.

Does it help to add the constraint that the graph be symmetric under reversing all the edges and swapping each node with its partner?


texts: Is the set of Multiplicative Proof Nets a proper subset of set of well formed single-agent Interaction Nets?

texts:
There are various criteria for the correctness of multiplicative proof nets.
In Correctness of Multiplicative Proof Nets is Linear, Stefano Guerrini nicely describes few of them with an efficient algorithm.

We can erase the difference between par and tensor connectives and treat it as an interaction net with a single node (agent) type.
In such a net we still can perform cut elimination faithfully as the procedure does not depend on the node labeling (by par and tensor). Is that right?

Assuming that's right let's consider the converse problem.
Let's have an interaction net with single agent type that normalizes. Further assume that the normalized net has no vicious cycles.

Is it always possible to assign par-tensor labeling to the un-normalized net so that we obtain a correct proof net? Is there an efficient 'labeling' inference algorithm?


texts: What is the competitive ratio of a $d$-way associative LRU cache?

texts:
In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$.

It is well known that for a $k$-sized LRU cache has a competitive ratio of $k$ and that no deterministic algorithm can do better than that.

Consider the following (randomized) algorithm:

We choose a random hash function that maps items into $\{1,\ldots,d\}$.
Whenever we see a request, we hash it into one of $d$ LRU caches (of size $k/d$ each).

  What is the competitive ratio of this limited associativity LRU variant?

It seems that if $k\gg d$, we can use a balls-and-bins analysis to show that an input that consists of round robin of $k$ items will give a $k/d (1-o(1))$ lower bound.

Is this tight?
What about other cases?


texts:
Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1].

I am interested in a more fine-grained version of the "polynomial time", that is, if we use parameterized reductions.

A parameterized problem is a subset of $Σ^∗ × Z \geq 0$, where $Σ$ is a finite alphabet and $Z\geq 0$ is the set of nonnegative numbers. An instance of a parameterized problem is therefore a pair $(I, k)$, where $k$ is the parameter.

A parameterized problem $π_1$ is fixed-parameter reducible to a parameterized problem $π_2$ if there exist functions $f$, $g$ : $Z≥0 → Z≥0$, $ Φ : Σ∗ × Z≥0 → Σ^∗$ and a polynomial $p(·)$ such that for any instance $(I, k)$ of $π_1$, $(Φ(I, k), g(k))$ is an instance of $π_2$ computable in time $f(k) · p(|I|)$ and
$(I, k) ∈ π_1$ if and only if $(Φ(I, k), g(k)) ∈ π_2$. Two parameterized problems are fixed-parameter equivalent if they are fixed-parameter reducible to each other.

Some NP-complete problems are FPT, for example, the decision version of vertex cover problem is NP-Complete, it has a $O(1.2738^k + kn)$ algorithm[2]. Finding better fixed-parameter reductions of a FPT problem which is NP-Complete can lead to a better algorithm, for example, by invoking a reduction to an
"above guarantee version" of the Multiway Cut problem can lead to an algorithm in time $O^*(4^k)$ for AGVC(Above Guarantee Vertex Cover) problem[3], which is better than the original $O^*(15^k)$ algorithm [4].

$\textbf{My Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic.}$

Is that conjecture true?

[1]  Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets", SIAM Journal on Computing 6 (2): 305–322.

[2] J. Chen, I. A. Kanj, and G. Xia, Improved upper bounds for vertex cover, Theor.Comput. Sci., 411 (2010), pp. 3736-3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk, On multiway
cut parameterized above lower bounds, in IPEC, 2011.

[4] M. Mahajan and V. Raman, Parameterizing above guaranteed values: Maxsat and
maxcut, J. Algorithms, 31 (1999), pp. 335-354.


texts:
I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger.
In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they claim that $f(X)$ is the sufficient statistics of $X$ from $Y$. This means that $I(Y; X)=I(Y; f(X))$ where $I(\cdot; \cdot)$ is the mutual information.

I don't understand the definition of $f$. What does $f(X)=c$ mean?

The above implies that we have the two Markov chains $Y\to X\to f(X)$ and $Y\to f(X)\to X$. I don't understand the second Markov chain. Is there any intuition behind this? (The proof is given in the paper but I am looking for some intuition.)

Is the entropy of $f(X)$ equal to $H(Y|X)$?


texts: How does white noise on the output channels influence the training of a neural network?

texts:
Let $\rho(\sigma): \mathbb{R} \rightarrow \mathbb{R}$ be a probability density that is parametrized by a parameter vector $\sigma \in \mathbb{R}^s$ (for example the normal distribution where $s = 1$ and $\sigma$ is the variance), $x \in \mathbb{R}^n$ a vector with $x_{i+1} - x_i = c\;\; \forall \, 1 \leq i < n$ for a constant $c \in \mathbb{R}$ and $v \in \mathbb{R}^n$ a vector with

$$ v_i \equiv \int_{x_i-c/2}^{x_i+c/2}dx\;\; \rho(x | \sigma) $$

$f(\sigma, \theta): \mathbb{R}^2 \rightarrow \mathbb{R}$ is a function which is parametrized by the same $\sigma$ and an additional parameter vector $\theta \in \mathbb{R}^t$. $f$ is not known analytically but can be computed numerically.
$w \in \mathbb{R}^n$ is another vector with

$$ w_i \equiv \int_{x_1-c/2}^{x_n+c/2}dx \int_{x_i-c/2}^{x_i+c/2}dy\;\;f(x, y | \sigma, \theta) \cdot \rho(x | \sigma) $$

I want to train a neural network (specifically a multilayer perceptron) to compute $v$ (or equally $\sigma$) from a given $\{w, \theta\}$ ($x$ is fixed and known). For this I create training data $\{v, w\}$ by sampling the complete parameter space $\mathbb{R}^s \times \mathbb{R}^t$. The integrals are computed by Monte Carlo sampling. And this is where my question sets in:

I train the network to go from $\{w, \theta\} \rightarrow v$ and $v$ only depends on $\sigma$ so for traversing directions of the parameter space for which $\sigma$ is constant I feed the very same $v$ to the neural network. Especially for cases $t > s$ (but also for others) the network will see many different inputs that all map to the very same output. This holds if I use the same seed for the random number generator for every case. Instead I could also use a different seed each time which will lead to slightly different $v$ (and $w$) while their overall features are preserved. Those statistical fluctuations should behave like white noise (for a RNG with long autocorrelations). Doing so the neural network would see a different output each time while still learning the correct features.

My question is, what effect does the addition of white noise to the output channels have on the training of the neural network (MLP)? Does it improve the learning because it gets to see a greater variety with respect to the training data? Or does it make it worse because it suppresses the feature that the output actually should be identical?


texts: What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?

texts:
There are many inapproximability results which rely on the unique games conjecture.  For example,

  Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a factor R for any constant R > RGW.

(Here RGW = 0.878… is the approximation ratio of the Goemans–Williamson algorithm.)

However, some people prefer to use the term “UG-hard” as:

  It is UG-hard to approximate the maximum cut problem within a factor R for any constant R > RGW.

Is the latter just a shorthand for the former, or do they mean different statements?


texts: Evaluating boolean formula without knowing all values

texts:
I am looking for research approaches for the following problem: assume we have a set of $m$ computers, each carries a bit, and a Boolean formula $\varphi$ over those $m$ variables. The computers are not allowed to communicate with each other, only with one "special" computer that can communicate with everyone else. This special computer wants to evaluate $\varphi$ - but with as little communication as possible. For example, if there are 2 computers and $\varphi=x_1 \vee x_2$, - they can agree on the following rule: if their variable is 1, they remain silent, otherwise they send their value to the special computer. In this way, the special computer can evaluate $\varphi$ without knowing all the $m$ values (in some cases).
This problem can be phrased also as follows: what is minimum information required in order to evaluate $\varphi$? in the above example, knowing that one variable equals to 1 is enough to determine the value of the formula.
It seems like not so difficult problem, and I was wandering if there are any approaches for this problem (bounds on the minimum information which is needed in the average case for an arbitrary formula, for example). I didn't find much while searching - I'll be glad for direction.


texts: Incremental Maximum Flow in Dynamic graphs

texts:
I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/deleted with its corresponding edges to form a graph $G^1$. What is a maximum flow in newly created graph? Is there a way to prevent from recalculating maximum flow?

Any preprocessing which isn't very time/memory consuming is appreciated.

Simplest idea is recalculating the flow.

Another simple idea is as this, save all augmenting paths which used in previous maximum flow calculation, for adding a vertex $v$, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to the $v$ then goes to the destination, but problem is, this path should be simple, I couldn't find better than $O(n\cdot m)$ for this case, for $m=|E|$. (Also note that if it was just one path this could be done in $O(n+m)$ but it's not so.)

Also for removing node above idea doesn't work.

Also I already saw papers such as Incremental approach for edges, but seems they are not good enough in this case, it's more than $O(m)$ for each edge and seems is not suitable extension in this case (we just recalculate a flow). Also currently I'm using Ford-Fulkerson maximum flow algorithm If there is better option for online algorithms, it's good to know it.


texts: How to prove the existence of a pure Nash equilibrium?

texts:
I have a game as given by the table below. I would like to prove that the game has always at least one pure Nash equilibrium (NE). I used a computer program and in fact the game has a pure NE. So, I am claiming the existence of at least one pure NE.

I looked in the internet but most of the paper that I read are talking about general games.

I need to know what do I need to know and to do in order to prove my claim? I do not want to give me the whole answer (if you have any), just give the tools and some hints and that would be appreciated. Also, can you give, in general, situation, how to prove the existence of a pure NE? Thank you.

Here is the game:

$$\begin{array}{c|c|c|c|}
P1\backslash P2 & \text{$a_1$} & \text{$a_2$} & \text{$a_3$} \\ \hline
\text{$a_1$} & (-1, -1) & (p, q)   & (r, 0) \\ \hline
\text{$a_2$} & (s, t)   & (-1, -1) & (x, 0) \\ \hline
\text{$a_3$} & (0, y)   & (0, z)   & (0, 0) \\ \hline
\end{array}$$

You can see that it is a 2 players ($P1$ is the row player and $P2$ is the column player) game where each player has the action space $\{a_1, a_2, a_3\}$. Here $p,q,r,s,t,x,y,z$ are integers in the set $\{-1, 1\}$ which are related to each others by:

If p == 1 then r = 1
If s == 1 then x = 1
If q == 1 then z = 1
If t == 1 then y = 1

My algorithm that I used is a brute force one that search for all possible values of $p,q,r,s,t,x,y,z$ and then see for each possible value if there is a pure NE or not.


texts: Construction of graph embeddings with non-intersecting edges

texts:
I have a bipartite graph whose genus $g$ I know. I have a genus $g$ real surface(a $g$-holed donut). I want to construct a graph embedding on the surface so that I have no intersecting edges. Has this problem been studied before?

That is given a genus $g$ bipartite graph, provide an explicit algorithm that can embed the graph in a non-intersecting manner on to a real surface with $g$ handles.

Is there any notion of equivalence of embeddings of graphs on surfaces? If so, given a genus $g$ graph, in how many non-equivalent ways can one do the embedding?


texts: Number of k-expressions of graph (clique Width)

texts:
The clique-width of a graph $G$ is the minimum number of labels needed to construct G by means of the following 4 operations.
The Construction of a graph $G$ using the four operations is represented by an algebraic expression called $k$-$expression$, Where
$k$ is the number of labels used in expression.
For example, $K_4$(complete graph with four vertices) can be constructed by
$$\rho_{2\rightarrow 1}(\eta_{1,2}(\rho_{2\rightarrow 1}(\eta_{1,2}(\rho_{2\rightarrow 1}(\eta_{1,2}(a(1)\oplus b(2)))\oplus c(2))) \oplus d(2))).$$

Question--> How many k-expressions for bounded clique width graph?
Any particular graph classes known for this question?


texts: Is there a backup/replacement for the Complexity Zoo?

texts:
This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close.

The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/Complexity_Zoo) has certainly been of great service to the TCS community over the years. Apparently it is down since quite a while. I was wondering, if someone is still maintaining it, if it has moved, if there is a backup server, or if there are other plans to preserve this wonderful database of complexity classes, their relationships and citations to relevant publications. If not, are there comparable webpages that could be used as a replacement?

UPDATE (Aug 1, 2012): The Zoo is back online, and Scott is looking for people volunteering to mirror it to avoid any future outages.


texts: What is the complexity of this covering problem?

texts:
Edit: I first misformulated my constraint (2), it is now corrected. I also added more information and examples.

With some colleagues, studying some other algorithmic question, we were able to reduce our problem down to the following interesting problem, but we were not able to solve the question of its complexity. The problem is as follows.

  Instance: An integer $n$, an integer $k<n$, and a set $S=\{\{s_1,t_1\},\ldots,\{s_n,t_n\}\}$ of $n$ pairs from the set $\{1,\ldots,n\}$.

  Question: Is there a set $S'\subseteq S$ of size $k$ such that for each element $i$ of $\{1,\ldots,n\}$:
  (1) if $i<n$, the interval $[i,i+1]$ is included in some interval $[s_i,t_i]$ defined by a pair in $S'$, and
  (2) at least one of $i$, $i+1$ belongs to some pair of $S'$?
  (2) $i$ belongs to some pair of $S'$.

Example
The set $\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$ is a feasible solution (assuming $n$ is even): the pair $\{1,n\}$ ensures condition (1), whereas all other pairs ensure condition (2).

Remarks
(I) Since each pair contains exactly two elements, in order to fulfill condition (2), we need at least $\frac{n}{2}$ pairs. BTW this implies a trivial 2-approximation by returning the whole $S$, since we assume $|S|\leq n$.

(II) Another way of looking at the problem is to consider a ladder with $n$ steps (such as the one below), together with a set $S$ of $n$ cycles of the ladder. Each step of the ladder corresponds to some element, and each side edge is an interval $[i,i+1]$. A cycle including steps $s,t$ corresponds exactly to a pair $\{s,t\}$: it covers all consecutive intervals between $s$ and $t$, and it stops at both $s$ and $t$.The question is then whether there is a set $S'\subseteq S$ of $k$ cycles whose union covers all the edges of the ladder (including step edges and side edges).

(III) If one was asking only for condition (1), the problem would correspond to the dominating set problem in some interval graph defined from the intervals $[s_i,t_i]$ given by the pairs of $S$ together with additional tiny intervals $[i+\epsilon,i+1-\epsilon]$ for each $i$ in $\{1,\ldots, n-1\}$. This problem is classically solvable in linear time (see e.g. here).Similarly, if one was just asking for condition (2), this could be reduced to the edge cover problem (vertices are the elements, edges are the pairs), which is also polynomial-time solvable by a maximum matching approach.

So my question is in the title:

  Is this problem in P? Is it NP-complete?

Any reference to a similar problem is welcome.


texts: Fixed-parameter tractability of string homomorphism

texts:
String homomorphism is a function $h: \Sigma \to \Sigma^*$, which naturally defines a homomorphism on strings from $\Sigma^*$ with respect to concatenation. We denote $H(s) = h(s_1)h(s_2)\dots h(s_n)$ for $s \in \Sigma^*$, $s = s_1 s_2 \dots s_n$.

It is known that the problem "Given two strings $s$, $t$, decide whether there exist a homomorphism $h$ such that $H(s) = t$" is NP-complete. However, this problem seems also interesting when the alphabet of $s$ is small.

Now I allow a smaller alphabet for $s$ and thus redefine the homomorphism as a function $h: \Sigma \to Q^*$, where $|\Sigma| = k$, and let $s \in \Sigma^*$, $t \in Q^*$. Is now the problem of deciding the homomorphism existence known to be in FPT with the parameter $k$?


texts: Algebraic decision trees and adversary arguments

texts:
In the comparison tree model, we establish lower bounds on computing
$\min$ and $\max$ of $n$ numbers via the adversary argument. Are there problems
on which we know lower bounds in the algebraic decision tree model via the
adversary argument? Please suggest relevant references.


texts: program search with optimization methods for (resource bounded) Kolmogorov complexity

texts:
Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization methods (gradient descent, genetic algorithms, etc)?
In theoretical computer science, I read about methods which search iteratively amongst all programs (like Levin search http://www.scholarpedia.org/article/Universal_search), but I was wondering if methods using optimization could, in some cases, find solutions faster ?
For instance we could describe a program by an LSTM [1], trained to produce the string, but with a regularization that encourages the weights of the LSTM itself to be simple to code (for instance encouraging sparsity).
In Machine Learning, there are many works trying to encode a dataset with a simple model (using the Minimum Description Length theory for instance), although in most cases the models they consider are not Turing complete because they are feedforward network [6]: for instance works like [7].
On the other hand, there are programs that intend to learn a Turing machine (like [2]), which are Turing complete [5], but in this case I'm not aware of any work trying to reduce the complexity of encoding the model themselves (except maybe this work [4]).
Question: Has there been some works on short program search using optimization methods, and ideally that give guarantees on how close we can be to the (resource bounded) Kolmogorov complexity after $t$ iterations ? From my understanding, finding an explicit program to compress a string gives an upper bound on the Kolmogorov complexity of the string, which is good, but I was wondering if there could be guarantees like in say convex optimization, of the type: after $t$ iterations of the search/optimization, we are guaranteed to be this $\epsilon$ close to the true resource bounded Kolmogorov complexity. More generally, I'm curious of any related work in this area.
[1] https://en.wikipedia.org/wiki/Long_short-term_memory
[2] "Neural Turing Machines" https://arxiv.org/abs/1410.5401
[3] Differentiable Neural Computer: https://deepmind.com/blog/article/differentiable-neural-computers
[4] "Neural Abstract reasoner" https://arxiv.org/abs/2011.09860
[5] "On the Turing completeness of modern neural networks architectures" https://openreview.net/pdf?id=HyGBdo0qFm
[6] https://stackoverflow.com/a/20950522/15569217
[7] Keeping the neural networks simple by minimizing the description length of the weights https://dl.acm.org/doi/10.1145/168304.168306


texts:
Circuit Minimization is the problem to minimize the size of a given circuit. Is there anything similar for general programs?

In particular my question is -

Do there exist algorithms to minimize the # of instructions for a given program. I know it's an undecidable problem but I'm not looking for a solution that returns something optimal.

While one can apply preexisting compiler transformations to accomplish this, I'm looking for something where I don't have to define a set of very narrow transformations and algorithms to search for them beforehand.

Edit: The other question I have is whether one can have a calculus that is sound and complete that allows us to explore the whole space of such semantically equivalent programs or is that not possible.


texts: Why does simhash work?  I understand how to implement the hash algorithm, mechanically, from the many articles such as http://matpalm.com/resemblance/simhash/.  But is there a simple intuitive explanation for why this particular procedure is so effective at capturing similarity?


texts: A reading list on experimental algorithmics

texts:
As in, the area of the papers in the ACM Journal on Experimental Algorithmic JEA.

Which were the foundational works? What are the main results? How are they characterized? Any interesting connections to other areas of computer science?


texts:
I'm currently working on a linear time heuristic for the rectangle decomposition of a binary matrix. This problem has a polynomial time solution, which in our case is too slow for large-scale processing. I devised a linear time heuristic and I would like to characterize its approximation ratio and  the problem is that I'm not familiar with approximations algorithms.

In this paper, Kalinowski proved that there is no integrality gap for this problem. What consequences does this result have? Does it mean that is impossible to design an approximation algorithm?


texts: Counting words accepted by a regular grammar

texts:
Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted?  Both "with exactly n letters" and "with at most n letters" are of interest.

Margareta Ackerman has two papers on the related subject of enumerating words accepted by an NFA, but I wasn't able to modify them to count efficiently.

It seems like the restricted nature of regular languages should make counting them relatively easy -- I almost expect a formula more than an algorithm  Unfortunately my searches so far haven't turned up anything, so I must be using the wrong terms.


texts:
Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely

  $\mathsf{move}(v_i, v_j)$:  this operator moves $v_i$ to the position immediately after $v_j$; that is, after calling this function, the graph $G$ becomes (if $i > j$)
  $$
v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_j \rightarrow v_i \rightarrow v_{j+1} \rightarrow \cdots \rightarrow v_{i-1} \rightarrow v_{i+1} \rightarrow \cdots
$$
  $\mathsf{reachable}(v_i, v_j)$: whether $v_j$ is reachable from $v_i$ in $G$; that is, whether there is a path from $v_i$ to $v_j$

My current idea is to arrange $v_1$, $v_2$, $\cdots$, $v_n$ in a balanced binary tree such that if $v_j$ is reachable from $v_i$, then either one of below holds:

$v_j$ is in the right subtree of $v_i$;
$v_i$ is in the left subtree of $v_j$;
there is a node $v_k$ such that $v_i$ is in the left subtree of $v_k$ and $v_j$ is in the right subtree of $v_k$.

Using a balanced BST, we can get the rank of each node and by comparing the ranks of two nodes, we can know whether a node is reachable from another.  Therefore, two operations above can be implemented in $O(\log n)$ time.

  Q: Is there a better data structure with better complexity please?


texts: In the lower bound result by Ryan Williams (Non-uniform $\mathsf{ACC}$ circuit lower bounds), there is a mention of "little evidence that Pseudorandom function generators exist in $\mathsf{ACC}^0$. Is there any development in this regard that might be of interest? (Even old results implying something along these lines will be great.)


texts:
As microbenchmarking is a common method for the performance evaluation, I was expecting it to be extensively researched up to now. The search for related literature has not revealed much, hence I would appreciate for sharing relevant papers.

Examples of microbenchmarking frameworks: criterion for haskell, jmh for java, benchmark for c++ from google

In general, references to literature about performance evaluation in practice are appreciated.

Thanks!


texts:
I have just started learning about coding theory. Hence, I would like to ask for your suggestions and guidance for a very beginner like me.

Which books are good for beginning coding theory? (I start reading the notes by J.I. Hall
from here).
Which topics now are hot in coding theory? so that I could look at and choose the track to follow.
Where I could find lastest preprints and papers on coding theory. I know only "Designs, Codes and Cryptography".

Many thanks in advance.


texts:
Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can be written in the unambiguous form 'a*`. The answer to this question gives an algorithm for deciding whether a regular expression is ambiguous.

Is there an algorithm for finding an equivalent unambiguous form of any given RE?
Are there REs that are inherently ambiguous?

(This question seems relevant by title; not by content)


texts: Computational complexity of random sampling

texts:
I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a multivariate Gaussian), in terms of elemental operations... or what computational complexities have conventional algorithms.

Thank you


texts: Information theoretic lower-bound on object graph serialization

texts:
This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding object graphs to storage (wire) format. I'm sure there is applicable research into this, but I it seems my base information is failing to provide the right terms to feed into search engines.

I have tried something like "information theoretic lower bound graph node types" and variants, but the results are something I don't understand could be related to the question in hand. Maybe something I could understand is the paper Succinct Posets, which states

  Partially ordered sets, or posets, are useful for modelling relationships between objects, and appear in many different areas, such as natural language processing, machine  learning,  and  database  systems.  As  problem  instances  in  these  areas are  ever-increasing  in  size,  developing  more  space  efficient  data  structures  for representing posets is becoming an increasingly important problem

Maybe, though, I'm having the wrong terms. Maybe I understand it wrongly on how could one decode a type of concrete instantiations of classes be encoded efficiently, i.e. maybe preserving the order of internal fields, their types and  the data. Is there research that could be useful for this purpose?

As for a concrete pondering on this subject, here's one useful speclet on what I'm thinking besides the Wikipedia link.

<edit 2017-05-13: As per question by D.W. That is a good clarification to ask. I am not sure if this is the right forum to ask and if I ask makes sense, but I try to construct this in more detail.

I see there are multiple serialization systems that each try to be as space efficient and fast as possible when encoding to the storage/wire representation. Then when decoding back to a class, the systems try to be as fast as possible.
What comes to part 1., it looks the systems are vague on the principles, if any, on how close they come to the possible bounds.

When I'm searching on this, I'm searching things like:

Lower bound graph compression.
Lower bound information compression.
Succinct data structures (e.g. Burrows-Wheeler).
Encoding object graph lower bound.

I get interesting links for sure, but I fail to find on something that would somehow treat "nodes" (e.g. objects having data member fields in programs) and the graph structure that the objects point to other objects together with compressing the relations and data types for fast reconstruction of that structure.

I do get interesting links with those search terms in 1., 2. and 3., but nothing I feel is on this particular matter. So, what I perhaps hope are pointers to what to look for – if it's possible to understand from this description – in way of research applicable to this rather practical problem. This isn't that easy. I have looked for here too, I found, for instance, the question asked recently by D.W. Lower bounds on single-source shortest paths in directed graphs, but it doesn't look like being applicable to this case.


texts: Iterating over all stabilizer operations on $k$ qubits

texts:
Stabilizer circuits, i.e. quantum circuit that only use the $H$, $\sqrt{Z}$, and $CNOT$ gates, can only implement a finite subset of all possible unitary operations.

I want to iterate over all these operations for a small number of qubits, or sample from the space for a larger number of qubits.

I could just use the stabilizer circuits themselves as stands ins for the operations: iterate over the possible circuits with up to $n$ operations and $k$ qubits, sample from the possible circuits, etc. But many circuits encode the same operation, so focusing on the circuits would create extra work and bias the sampling. Also there's not a clear length cut-off.

What's a straightforward way to generate all the operations in the group? To sample from the group?