Applications of sunflower lemma in theoretical computer science In one lecture by Kewen Wu who is one of the authors of paper

  Improved bounds for the sunflower lemma,

it is said that the sunflower lemma can be applied to many fields like

circuit lower bounds
data structure lower bounds
matrix multiplication
pseudorandomness
cryptography
property testing
fixed parameter complexity

What I can know about the sunflower lemma comes from the books

  Parameterized Complexity Theory

  Extremal Combinatorics

  The Mathematics of Paul Erdős II     2013

and papers

  Improved Bound On Sets Including No Sunflower
  With Three Petals Junichiro Fukuyama 2018

  Improved bounds for the sunflower lemma Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang 2019

How is it applied to the field of computer science?

Sunflower lemma has applications in data structure lower bounds(as mentioned above). For eg. see:
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.


Exact arithmetic complexity of Ryser's formula for computing permanent What is the exact number of multiplication operations and addition operations needed to calculate the permanent in Ryser's formula (both original and the Gray coded version)?

I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for $4 \times 4$ determinant where he uses Gaussian elimination. He mentions estimating the precise gap between permanent and determinant calculation for $4 \times 4$ is already a notorious open problem.

I am also looking for counts for other calculations/formulas of Permanent.

Ryser: $n(n-2)2^{n-1} + n$ additions and $(n-1)(2^{n}-1)$ multiplications.

Ryser+Gray code: $n(2^{n}-2)$ additions and $(n-1)(2^{n}-1)$ multiplications.

Number of multiplications: For each nonempty subset of $[n]$, $n-1$ multiplications are used to multiply $n$ sums together.

Number of additions for Ryser: for each nonempty $S \subseteq [n]$, and for each $i \in [n]$ you compute $\sum_{j \in S} a_{ij}$ which uses $|S|-1$ additions. $\sum_{\emptyset \neq S \subseteq [n]}(|S|-1) = \sum_{k=1}^{n} (k-1) \binom{n}{k} = \sum_{k=1}^{n} k \binom{n}{k} - \sum_{k=1}^{n} \binom{n}{k} = n2^{n-1} - (2^{n}-1)$.

Additions for Ryser+Gray: The Gray code version does not give you a smaller formula, but only a smaller circuit (which is still good, I just thought it was worth pointing out). Its savings require the re-use of previously computed quantities. For each $i \in [n]$, it does a Gray code over the nonempty sets $S \subseteq [n]$. Since there are $2^{n}-1$ such sets, and each transition of the Gray code involves a single addition/substraction, that gives the $2^{n}-2$.


Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$? I have a set of $n$ binary vectors $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ and a target vector $t = 1^k$ which is the all-ones vector.

  Conjecture: If $t$ can be written as a linear combination of elements of $S$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$, then $t$ can be written as a linear combination of $S$ over $\mathbb{Z}$, i.e., there is a linear combination with integer coefficients which sums to $t$ over $\mathbb{Z}$.

Is this true? Does it look familiar to anyone? I'm not even sure what keywords to use when searching for literature on this topic, so any input is appreciated.

Observe that the converse certainly holds: if $t = \sum_{i=1}^n \alpha_i s_i$ for integers $a_i$, then evaluating the same sum mod $q$ for any modulus $q$ still gives equality; hence a linear combination with integer coefficients implies the existence of a linear combination for all moduli.

Edit 14-12-2017: The conjecture was initially stronger, asserting the existence of a linear combination over $\mathbb{Z}$ whenever $t$ is a linear combination mod $q$ for all primes $q$. This would have been easier to exploit in my algorithmic application, but turns out to be false. Here is a counter-example. $s_1, \ldots, s_n$ are given by the rows of this matrix:

$\left(
\begin{array}{cccccc}
 1 & 0 & 0 & 1 & 1 & 1 \\
 0 & 1 & 0 & 1 & 1 & 1 \\
 0 & 0 & 1 & 1 & 1 & 1 \\
 0 & 0 & 0 & 0 & 1 & 1 \\
 0 & 0 & 0 & 1 & 0 & 1 \\
 1 & 1 & 1 & 0 & 0 & 1 \\
\end{array}
\right)$

Mathematica verified that the vector $t = (1,1,1,1,1,1)$ is in the span of these vectors mod $q$ for the first 1000 primes, which I take as sufficient evidence that this is the case for all primes. However, there is no integer linear combination over $\mathbb{Z}$: the matrix above has full rank over $\mathbb{R}$ and the unique way to write $(1,1,1,1,1,1)$ as a linear combination of $(s_1, \ldots, s_6)$ over $\mathbb{R}$ is using coefficients $(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$. (You cannot write $t$ as a linear combination of these vectors mod $4$, though, so it does not contradict the updated form of the conjecture.)

The revised conjecture is true, even under relaxed constraints on $S$ and $t$—they may be arbitrary integer vectors (as long as the set $S$ is finite). Notice that if we arrange the vectors from $S$ into a matrix, the question simply asks about the solvability of the linear system
$$Sx=t$$
in the integers, hence I will formulate the problem as such below.

  Proposition: Let $S\in\mathbb Z^{k\times n}$ and $t\in\mathbb Z^k$. Then the linear system $Sx=t$ is solvable in $\mathbb Z$ if and only if it is solvable in $\mathbb Z/q\mathbb Z$ for all prime powers $q$.

This can be proved in at least two ways.

Proof 1:

For any prime $p$, the solvability of the system modulo each $p^m$ implies that it is solvable in the ring of $p$-adic integers $\mathbb Z_p$. (There is a minor problem in that the solutions are not unique, hence given solutions mod $p^m$ and mod $p^{m'}$ need not be compatible. This can be sorted out e.g. using the compactness of $\mathbb Z_p$, or using König’s lemma.)

Consequently, the system is also solvable in the product
$$\hat{\mathbb Z}=\prod_{p\text{ prime}}\mathbb Z_p,$$
i.e., the ring of profinite integers. I claim that this implies its solvability in $\mathbb Z$.

Notice that solvability of the system (i.e., $\exists x\,Sx=t$) is expressible as a (primitive positive) first-order sentence in the language of abelian groups, augmented with a constant $1$ so that we can define $t$. Now, one can check that the complete first-order theory of the structure $(\mathbb Z,+,1)$ can be axiomatized as follows (it’s an order-free version of Presburger’s arithmetic, or rather, of the theory of $\mathbb Z$-groups):

the theory of torsion-free abelian groups,
the axioms $\forall x\,px\ne1$ for each prime $p$,
the axioms $\forall x\,\exists y\,(x=py\lor x=py+1\lor\dots\lor x=py+(p-1))$ for each prime $p$.

However, all these axioms hold in $\hat{\mathbb Z}$ as well. Thus, the structures $(\mathbb Z,+,1)$ and $(\hat{\mathbb Z},+,1)$ are elementarily equivalent, and the solvability of $Sx=t$ in $\hat{\mathbb Z}$ implies its solvability in $\mathbb Z$.

In fact, we do not actually need the full axiomatization of $(\mathbb Z,+,1)$ above: it is enough to observe that $\hat{\mathbb Z}$ satisfies the axioms 2., which means that $\mathbb Z$ is a pure subgroup of $\hat{\mathbb Z}$, and therefore a pure $\mathbb Z$-submodule.

Proof 2:

There exist matrices $M\in\mathrm{GL}(k,\mathbb Z)$ and $N\in\mathrm{GL}(n,\mathbb Z)$ such that the matrix $S'=MSN$ is in the Smith normal form. Put $t'=Mt$. If $x$ is a solution of $Sx=t$, then $x'=N^{-1}x$ is a solution of $S'x'=t'$, and conversely, if $x'$ is a solution of $S'x'=t'$, then $x=Nx'$ is a solution of $Sx=t$. (This equivalence holds over any commutative ring, as $M,M^{-1},N,N^{-1}$ are integer matrices.)

Thus, we may assume without loss of generality that $S$ is a diagonal matrix (meaning that the excess rows or columns are zero if $k\ne n$). Then the system $Sx=t$ is unsolvable in $\mathbb Z$ only if

for some nonzero diagonal entry $s_{ii}$ of $S$, the corresponding entry $t_i$ of $t$ is not divisible by $s_{ii}$, or
for some $i$, the $i$th row of $S$ is zero, but $t_i\ne0$.

Let $q$ be a prime power such that $q\nmid t_i$, and, in the first case, $q\mid s_{ii}$. Then the system $Sx=t$ is not solvable in $\mathbb Z/q\mathbb Z$.


SMT solving with less-than theory and monotonic functions I am attempting to solve a less-than theory within an SMT paradigm that involves variables assigned to reals and assumes that all the functions used in the theory are monotonic. The theory's signature has the terms denoted as T and the formulas are denoted as φ. The syntax is given as follows:

$$T = x \mid f(T) \tag{1}$$
$$φ = T < T \mid ¬φ \mid φ ∧ φ \mid φ ∨ φ \tag{2}$$

An example formula in this domain is:

$$(x < y) ∧ (y < z) ∧ ((f(z) < f(y)) ∨ (f(x) < f(z)))$$

How would I begin thinking about how to encode a general formula within the less-than theory as a SAT problem? What is the decision process and encoding algorithm?

I can think of 2 straight forward approaches

Directly add $\forall xy (x < y \Rightarrow f(x) < f(y))$.
Or Akcermannize the problem and add these as axioms for all pairs of terms.


Is there a general theory for why certain algorithms are inefficient in high-level languages? First of all, I apologise off the bat for my mangling of CompSci language. I have no real training or background in computer science or mathematics.

I've been wondering lately whether there's a 'general' explanation for the inefficiency of high-level languages in performing certain kinds of algorithms - from simple cases like the massive performance improvement in C over, say, Python, when looping over a set, up to complex mathematical algorithms.

Is it purely a quantitative matter - C is more efficient because it's not doing weird magic behind the scenes and the programmer directly interacts with main memory? And because it's not doing things like interrupts for garbage collection and other general housekeeping like a high-level language might?

Or is there some deeper ontological explanation for this? Is there some qualitative property of a low-level procedural language (or, at times, of a functional language) that makes it possible to express and compute a problem efficiently? Or is it simply a matter of brute resource and CPU cycle efficiency?

There is no deeper reason other than quality of compilers and interpreters.

Some languages are not designed with speed of execution in mind. For example, the design goals of Python did not include speed of execution at the very top. In such cases you should not wonder where speed has gone.

Some languages are intended to run fast but it takes time for people to produce good compilers and runtime environments. Typical examples are the so-called "high-level" languages. For example, early variants of ML were memory hogs that ran sort of fast until the garbage collector kicked in. Nowadays, 25 years later, a modern variant of ML, such as Ocaml, runs with speeds comparable to those of C and C++, and in most cases you don't even notice that there is a garbage collector.

Why is it harder to compile high-level languages to fast code? Well, because they are high level. Programs written in such languages operate directly with concepts that are far removed from the underlying hardware. In contrast, low level languages such as C, C++ and java are essentially glorified assembly languages and there is very little that the compiler actually needs to do.

Also, there are languages out there whose design is essentially screwed up in such a way that efficient compiled code is hard to obtain. Typically such languages have no or little compile-time type checking or unreasonable amounts of reflection, i.e., eval <string>, and an operational semantics which relies heavily on string replacement and manipulation of source code. Bourne shell comes to mind, TeX/LaTeX as well, and maybe Python to an extent. As long as such "features" are deliberate design choices that is ok, but there also seem to be languages out there whose design was based on ignorance of programming language theory.


is determining an unknown CFL from intersection of two CFLs decidable? this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it to them. eg it is known that CFLs are not closed under intersection but thats not the immediate answer.) a proof is ok but also looking for ref(s) if known. analysis of nontrivial special cases also might be interesting. also a single non empty/non trivial example case has not been given so far (eg plz exclude both languages regular languages).

  let $L_1, L_2$ be CFLs and $L=L_1 \cap L_2$ is known to be a CFL. is there an algorithm for constructing $L$?

It's well-known you can present computation history of a Turing machine as an intersection of two CFLs. Take a deterministic Turing machine $M$ and force it to reject everything except possibly the empty word. The set of computation histories is either empty (if $M$ rejects the empty word), or a singleton (if there's an accepting computation for the empty word), and if there was an algorithm for your problem, you could tell those cases apart.


Program equivalence wherein the programs are known to always halt Say I have two programs with possibly infinite state spaces and some oracle has asserted that they both always halt. Can I always decide if they're contextually equivalent? If yes, is there a known effective algorithm (or approach that when applied on a case-by-case or language-by-language basis provides an effective algorithm) to do so?

The answer is obviously yes/yes for finite input domains, but for infinite input domains: does the decidability depend at all on how infinitely huge (e.g. countable vs. uncountable) the input domains are?

As a counter-example to this, consider the Context-Free Equivalence problem: it's undecidable to determine, given two context free languages, whether they accept the same set.

If your problem were decidable, we could use it to determine CFL equivalence, since it's always possible to turn a CFL into an always-halting Turing machine.

So even for countably infinite inputs, the problem is undecidable.

It's also worth mentioning that, for standard Turing Machines, all input domains are countably infinite, since they're sets of finite strings.


Looking for a particular normal form for Context-sensitive grammar I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to Kuroda normal form and Greibach normal form. That is to say, each rule in such form might be one of the following:

$A\beta\rightarrow a_1\dots a_k B_1 B_2\dots B_n a_{k+1}\dots a_m$

or

$A\rightarrow a_1\dots a_k B_1 B_2\dots B_n a_{k+1}\dots a_m$

where $A,B_i\in N$, $\beta\in(N\cup T)$, $a_i\in T$, $m\geq 0$, $n\geq 0$, $k\geq 0$, $(m+n)>0$.

The idea is that three conditions are satisfied:

In the left-hand side parts of rules, non-terminals always come first.
In the right-hand side parts of rules all non-terminals are grouped together.
Context-sensitive rules contain no more than two symbols in the left-hand side of the rule.

As an answer I would expect either a counter-example, which proves that it is not always possible to transform any context-sensitive grammar into this form, either a link to the existent paper where such normal form is described, either a proof that such normal form exists :-)

A set of grammars in Kuroda form $\mathcal{K}$ is a strict subset of grammars in the described form $\mathcal{L}$:$\mathcal{K}\subset\mathcal{L}$. This follows from the fact that the first form covers first three forms of Kuroda since $k$ and $m$ can be equal to $0$. And the last one covers '$A$ $\mathcal\rightarrow$ $a$' form since $k$ and $n$ can be equal to $0$.

Let $\mathcal{G}$ - set of all Context-sensitive grammars.
Since it's proven that for any Context-sensitive grammar $G\in\mathcal{G}$ there is a mapping $K:\mathcal{G}\rightarrow\mathcal{K}$ (i.e. there is an algorithm of transforming any CS-grammar into Kuroda form), we can say that mapping $L:\mathcal{G}\rightarrow\mathcal{L}$ also always exists and it is equal to $K$: $L$ = $K$.

Indeed, for any $G\in\mathcal{G}$ there should be satisfied the following condition: $L(G)\in\mathcal{L}$. If $L=K$, then $L(G)\in\mathcal{K}\subset\mathcal{L}$.

Q.E.D.


Are endmarkers necessary for Deterministic Pushdown Automata? In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to accept as arguments triples $(q, \sigma, \gamma)$ with $\sigma$ that might be a right endmarker symbol. It is written: "The right endmarker delimits the input string and is a necessary addition. With NPDAs, we could guess where the end of the input string was, but with DPDAs we have no such luxury." (p. 176).
Can we show that this condition is necessary? Can we give an example of a language accepted by this kind of DPDA's that is not accepted by any DPDA whose transition function has no argument with an endmarker?

Short answer: it depends on how you set the acceptance condition of the DPDA model: final state or empty stack.

The endmarkers are not necessary for DPDAs in which the accept condition is final state (which is also used to define the deterministic context-free languages - DCFLs): for all $L \dashv$ ("endmarked" language) recognized by a DPDA there is a DPDA that recognizes $L$.

See:

Theorem 2.43. $A$ is a DCFL if and only if $A \dashv$ is DCFL

in Michael Sipser's Introduction to the Theory of Computation.

But endmarkers play a role when proving equivalence between DPDAs and DCFGs (deterministic context free grammars):

Theorem: An endmarked language is generated by a deterministic CFG iff it can be recognized by a DPDA

Very informally a DCFG for $L$ exists if and only if there is a DPDA that accepts $L$ with empty stack acceptance condition (the stack is empty at the end of the input); which is not the "standard" definition of a DPDA. With non-determinism the two conditions are equivalent because the PDA can guess the end of the input and clear the stack with $\epsilon$ moves; without non-determinism they are not equivalent.

Without the endmarker DCFGs can only generate a proper subset of the languages recognized by DPDAs: DCFGs can only generate the prefix-free languages recognized by DPDAs (no string is a prefix of another string).

As a simple example consider this language: $L = \{ a^n b^m \mid m < n \}$. There is no DPDA with empty stack acceptance condition for it.

Note on the Kozen's book

In Lecture 23 he defines PDA as: $M = ( Q, \Sigma, \Gamma, \delta, s, \bot, F)$ where "... $F\subseteq Q$ is the final or accepts states".
Then he describes the two different acceptance conditions and proves their equivalence for (N)PDAs.

In Supplementary Lecture F he defines DPDA as: "$M = ( Q, \Sigma, \Gamma, \delta, s, \dashv, \bot, F)$ where everything is the same as with NPDAs except  (i) $\vdash$ is a special symbol not in $\Sigma$, called the right-endmarker ..." (then he adds the other conditions to forbid non-determinism and to prevent the pop of the $\bot$ symbol).

He then says: "We consider only acceptance by final state. One can define acceptance by empty stack and prove that such machines are equivalent. The assumption (iii) would have to be modified accordingly" (which is correct because the model described uses the extra endmarker $\dashv$).


Expected vs worst-case communication complexity In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an $n$-bit string as input; denoted by $X$ for Alice's input, and $Y$ for Bob's input. They need to output "no" if and only if there exists an index $i$ such that $X[i]=Y[i]=1$, otherwise they should output "yes".

The seminal paper An information statistics approach to data stream and communication complexity shows a lower bound of $\Omega(n)$ bits for this problem on the worst case length of the transcript $\Pi$ sent between Alice and Bob. At the end of their argument, the authors show this by using that $|\Pi| \ge H[\Pi]$, where $|\Pi|$ is the transcript length and $H[\Pi]$ is the entropy of the transcript.

I was wondering why the authors didn't show the significantly stronger statement that the expected communication complexity is at least $\Omega(n)$. This holds because even the expected length of the transcript is at least as long as $H[\Pi]$ (by the converse of Shannon's coding theorem, right?).

Actually, all lower bounds that I've seen in communication complexity seem to be shown only for the worst case length.

Is there some reason why the expected communication complexity isn't considered that I'm missing?

The reason is that a lower bound on the worst-case complexity automatically implies a lower bound on the expected complexity, so there is no reason to prove the latter.

To see the implication, observe that every randomized protocol with expected complexity $c$ and error probability $\varepsilon$ can be transformed into a randomized protocol with worst-case complexity $c/\varepsilon$ and error probability $2\varepsilon$: The new protocol simulates the old protocol, but forces the simulation to halt after $c/\varepsilon$ bits have been transmitted. By Markov inequality, a forced halting occurs with probability at most $\varepsilon$, so it adds at most $\varepsilon$ to the original error probability.

Since error probability can be amplified, it follows that every randomized protocol with expected complexity $c$ and constant error probability can be transformed into a randomized protocol with worst-case complexity $O(c)$ and the same error probability. Thus, if we show that there is no randomized protocol with worst-case communication $O(c)$ and constant error probability that computes a function $f$, the same holds for protocols with expected communication $O(c)$.


How to tell if an effect is algebraic? I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?

The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.

Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:

Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").
Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.
If your effect looks like you're passing around state of some sort, then it's likely algebraic.
Nondeterministic choice, search, etc., are typically algebraic.
Exception-like effects are algebraic (transactions of various sorts are included).
Anything that looks like communication (I/O, reader monad) is algebraic.
Probabilistic programming is algebraic.

Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.


Algorithm for Max Network Flow with lower bounds and its complexity I have built a max network flow graph that carries certain amount of people from a source to a destination. Now, I'd like to attach a lower bound $l_(e_)$ constraint to each edge $e$. But I don't know what algorithm to use and how to analyze its complexity. Here's the graph:

http://jeffe.cs.illinois.edu/teaching/algorithms/notes/25-maxflowext.pdf

There's a very simple reduction from that problem to the maximum flow problem. This is simply called "maximum flow with edge demands".


Is $UP\not=NP$ with respect to random oracle? It is shown in An average-case depth hierarchy theorem for Boolean circuits a random oracle makes $PH$ infinite.

  Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\not=\dots\not=PH\not=PSPACE$ with respect to a random oracle or does a random oracle give $UP=NP$?

Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the Complexity Zoo for questions like this...


Best way to determine if a list of bytes are random? Is there some algorithm out there that can return some value indicating a level of randomness? I believe it's called Data Entropy.

I recently read this article: http://faculty.rhodes.edu/wetzel/random/mainbody.html

Would his approach of analyzing coin flips apply for bytes? Should I drop down to the bit level where it's true/false again or is there a way to determine based on the full byte value?

Are their better analyses than this article?

In TCS, another approach to this problem has been via property testing of distributions, where one is to distinguish whether a distribution is (truly) uniform distribution or is "not even close" to being uniform (in a formal way). Here one gets precise bounds on the number of samples needed to decide on the question.

See, for example Section 6 of the following tutorial:
http://people.csail.mit.edu/ronitt/papers/icm.ps

In particular, one can decide whether a distribution on $[n]$ is truly uniform or is $\epsilon$-far (in total variation distance) from uniform with $O(\sqrt{n}/\epsilon^4)$ queries/samples from the said distribution. (This is also tight in the sense that $\Omega(\sqrt{n})$ samples are needed.)


Asymptotic complexity of CDCL SAT solver that only selects negative literals If a CDCL SAT solver only selects negative literals as decision literals (but can set positive literals through unit propogation) but has a perfect heuristic for determining which literal to select next, what kind of claims can be made about its running time?

Is it necessarily exponential on some infinite class of satisfiable instances?

Not a direct answer to the question but, as DPLL can be seen as a special case of CDCL, hopefully of interest.

The problem of finding optimal branching literals for DPLL is (in a way) harder than SAT itself: the paper "On the complexity of choosing
the branching literal in DPLL" by Liberatore shows that
choosing optimal branching literals in DPLL  is both NP-hard and coNP-hard.


What is the optimal data structure for a tree of maps. I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a programming map with keys and values, like map in the STL or dict in python.

For example, there might be a root node:

root = {'car':1, 'boat':2}

and 2 children, each adding an element to the parent map

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

I would like this to be as space efficient as possible, ie i don't want to store a complete copy of the resulting map at each node, but ideally the lookup would still be O(log N), N being the total number of elements at the node, not the entire tree.

I was thinking perhaps there is a smart hash function I might use for this, but couldn't come up with anything.

The naive approach would be storing the newly added entries in a map at each node and then move up the tree if nothing is found. I don't like this because it depends on the tree depth.

First of all, I think what you mean by "map" is a "dictionary" in TCS lingo. Second, I don't understand the phrase "ideally the lookup would still be $O(\log N)$", since in a dictionary the lookup takes O(1) time with various hash tables. Thirdly, you haven't stated whether the problem is static or dynamic; I'm assuming static.

The optimal complexity to this problem is $\Theta($predecessor search), e.g. $O(\lg\lg N)$ using van Emde Boas. This is optimal if you word size is $\Theta(\lg n)$; see http://people.csail.mit.edu/mip/papers/pred/pred.pdf for the optimal predecessor bounds.

The proper way to attack the problem is to build one global hash table and deal with the hierarchy separately for each key in the table. For one key $x$, we know the nodes where it appears. Consider an in-order traversal of the tree. The nodes where $x$ appears define intervals in this order. To determine whether $x$ is in the hash table of some node $v$, you have to ask whether $v$ stabs any segment as defined above. This is easily done by predecessor search, where we build a predecessor table for all interval end points.

For a lower bound, note that even one stabbing question is as hard as predecessor (see the reductions from colored predecessor search). Since the paper references above shows optimal direct-sum behavior for predecessor search, it means the algorithm described above is optimal for any ration between the number of nodes and the total number of keys.


Finding the size $k$ subset in a metric space that maximizes the min distance between elements I have a metric space $(X,d)$ and I'd like to find a subset of size k of far away elements.

We can cast this as the following optimization problem $\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, i,j \in S} d(i,j))$

For the case $k = 2$, there is a well known 2-approximation, which picks an arbitrary point and finds the point that is furthest from it. There is a natural extension of this idea, which at the $m$th stage, picks the point that maximizes the min distance to each of the $m-1$ previously chosen points. This uses $O(k^2|X|)$ time.

Questions:

This seems like a natural enough problem that it's been studied -- what are the keywords to this problem?
Does this greedy extension work well? What are some other heuristics to try?
For fixed $k$, is there a constant factor approximation with query size $O(|X|)$? Can one obtain a decent approximation in better than $O(k^2|X|^k)$ time?

Similar objective functions, such as $\prod_{i \not = j, i,j \in S} d(i,j) $, are also interesting.

From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This paper by Ravi, Rosenkrantz, and Tayi seems to prove that your heuristic is a $2$-approximation, and that this factor is actually optimal by a reduction to clique.

I skimmed it, so I might be missing some subtle points, but the idea of the proof seems quite simple: take an optimal $S\subseteq X$ with $\vert S\vert=k$, with objective value $\mathsf{OPT}$. Note that the $k$th point you add in the greedy algorithm will attain the closest distance (to another point) in the greedy solution, so it suffices to show that the last point you add must have distance at least $\mathsf{OPT}/2$ from the previous $k-1$ points you selected. This is seen by noting that the $k$ (open) metric balls of radius $\mathsf{OPT}/2$ around each point in $S$ are disjoint; as a result, at least one of these balls does not contain any of the first $k-1$ points you have chosen. The respective center in $S$ is therefore an option at step $k$ which attains a pairwise distance of at least $\mathsf{OPT}/2$ from all previously chosen points, so the same must be true of the greedy point chosen at the $k$th step.


A variant of Critical SAT in DP A language $L$ is in the class $DP$ iff there are two languages $L1 \in NP$ and $L2 \in coNP$ such that $L = L1 \cap L2$

A canonical $DP$-complete problem is SAT-UNSAT : given two 3-CNF expressions, $F$ and $G$, is it true that $F$ is satisfiable and $G$ is not?

The Critical SAT problem is also known to be $DP$-complete : Given a 3-CNF expression $F$, is it true that $F$ is unsatisfiable but deleting any clause makes it satisfiable?

I am considering the following variant of the Critical SAT problem : Given a 3-CNF expression $F$, is it true that $F$ is satisfiable but adding any 3-clause (out of $F$ but using the same variables as $F$) makes it unsatisfiable?
But I don't succeed in finding a reduction from SAT-UNSAT or even prove it is $NP$ or $coNP$ hard.

My question: is this variant DP-complete ?

Thank you for your answers.

[I made it into a proper answer b/c somebody gave it -1]

If any clause is allowed to be added, then the language is empty -- clearly to any satisfiable formula $F$ you can add a 3-clause $c$ made up of variables that do not appear in $F$: $F \cup \{ c \}$ will be satisfiable.

If the added clauses must use variables of $F$, then the language is in P.

Justification is as follows:

Take any $F \in L$, i.e. $F \in SAT$ and for any 3-clause $c$ on variables of $F$, $F \cup \{c\} \in UNSAT$. Say $c = l_1 \lor l_2 \lor l_3 \notin F$, where $l_i$ is a literal. Since $F \cup \{ c \}$ is UNSAT, all models of $F$ must have $l_i=0$ (for $i=1,2,3$) - because if some model had e.g. $l_1=1$, then it would satisfy $c$ and so $F \cup \{c\}$. Now, assume that there exists another clause $c'$ that is exactly like $c$, but with one or more literal flipped and such that $c' \notin F$, say $c' = \neg l_1 \lor l_2 \lor l_3$. Then by the same argument all models of $F$ must have $l_1 = 1$. Thus, the necessary condition for $F \in L$ is that for each clause $c \in F$ there are exactly 6 other clauses in $F$ that use the three variables of $c$ -- lets call these 7-clause subsets of $F$ blocks. Note that each block implies a unique satisfying assignment to its variables. When this necessary condition is satisfied, $F$ is either uniquely satisfiable or unsatisfiable. The two cases can be distinguished by testing whether the assignments implied by the blocks of $F$ clash, which can clearly be done in linear time.


Number of Maximum Overlap in n-Dimensions Given a list of compact axis-aligned intervals (in 1-D), rectangles (in 2-D), cuboids (3-D) etc, what is the maximum number that overlap at any point?

In 1-D there's a fairly simple solution that exploits the the ordering of R: assuming you have a set of pairs $\{[a_1,b_1],...,[a_n,b_n]\}$ sort all of the a's and b's (together) then scan from a_min to b_max adding one to the count of overlap whenever you encounter $a_i$ for any i and subtracting one whenever you see a $b_j$ for any j. Then just keep track of the maximum value of count that you see.

I'm not sure how to extend this to 2-D, let alone n-D. Any ideas?

This is a well-known variant of Klee's measure problem.  The best algorithm known, due to Timothy Chan, runs in roughly $O(n^{d/2})$ time, ignoring polylogarithmic factors.  Faster algorithms are known for the special cases of fat boxes and boxes with one or more fixed coordinates; see recent work by Karl Bringmann and Hakan Yıldız, respectively.


Decidability of first-order theory of real closed fields with functions By a famous theorem of Tarski, the first-order theory of real closed fields is decidable, as it admits quantifier elimination. Can this result be extended so that propositions can be quantified over functions on real numbers? That is, I know that there is a decision procedure for statements like

$$\exists x \in \mathbb{R} ,\forall y \in \mathbb{R}, \exists z \in \mathbb{R}, x +y = zy$$

I'd like to know if there is a decision procedure for statements like

$$\forall f \in \mathbb{R} \to \mathbb{R}, \exists g \in \mathbb{R} \to \mathbb{R}, \forall z \in \mathbb{R}, f(g(z)) = g(f(z)) = z$$

Undecidability results would be just as interesting!

It's undecidable because we can interpret natural numbers (with addition and multiplication).

For example, let $Ind(f)$ be the formula:
$$f(0)=1 \land \forall x \ \big(f(x)=1 \to f(x+1)=1\big)$$

Now we can define the characteristic function of the set of natural numbers using its universality property as a minimal inductive function:
$$Ind(h) \land \forall f \ \big(Ind(f) \to \forall x \ (f(x)=0 \to h(x)=0)\big)$$

(As Emil wrote in his comment we don't even need the language of RCF, we can pick an arbitrary member of the structure as $0$, define a successor function as an injective function whose range lacks our $0$, and then define natural numbers using them. So the undeciability result applies to the second-order language of any infinite structure.)


What is the most important notion of sparsity for the design of efficient graph algorithms? There are several competing notions of a "sparse graph".  For instance, a surface-embeddable graph could be considered sparse.  Or a graph with bounded edge density.  Or a graph with high girth.  A graph with large expansion.  A graph with bounded treewidth.  (Even within the subfield of random graphs, it is slightly ambiguous as to what could be called sparse.)  Et cetera.

What notion of "sparse graph" has had the most impact on the design of efficient graph algorithms, and why?  Similarly, what notion of "dense graph" ... ?  (NB: Karpinski has worked a great deal on approximation results for one standard model of dense graphs.)

I have just seen a talk by J. Nesetril on a program of his (together with P. Ossona de Mendez) to capture measures of sparsity in graphs within a unified (asymptotic) framework.  My question -- yes, maybe quite subjective and I expect different camps -- is motivated by the desire to catch a multi-faceted perspective on the use of sparsity in algorithms (and plug any gaps in my own understanding of the issue).

I think that by any reasonable standard an n × n × n three-dimensional grid graph would have to be considered sparse, and that rules out most candidate definitions involving surface embeddings or minors. (Sublinear treewidth would still be possible, though.)

My current favorite sparsity measure is degeneracy. The degeneracy of a graph is the minimum, over all linear orderings of the vertices of the graph, of the maximum outdegree in the directed acyclic orientation of the graph formed by orienting each edge from earlier to later vertices in the ordering. Equivalently, it's the maximum, over all subgraphs, of the minimum degree in the subgraph. So for instance planar graphs have degeneracy five because any subgraph of a planar graph has a vertex of degree at most five. Degeneracy is easy to calculate in linear time, and the linear ordering that comes from the definition is useful in algorithms.

Degeneracy is within a constant factor of some other standard measures including arboricity, thickness, and the maximum average degree of any subgraph, but those are I think harder to use.


Langton's ant questions I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless.
So that is why I'm asking.

1)
Is there a mathematical proof that the Langton's ant will stay forever on the highway once it's enter in it ?

2)
Is there a proof that for only one initial condition the Langton's ant will always build the highway ?

There is an article on Langtons ant, published in the
SCTPLS Newsletter ( Society for Chaos Theory in Psychology & Life Sciences   Vol. 26, No. 2 February 2019 ) It introduces a first order recurrence relation for the cellular automata 'Langtons ant'   A copy can be downloaded from

http://buzwordsalad.com/lit/SCTPLS_LAWE_bw.pdf


Compiler Optimization: How do you automatically fuse conditionals into the loop index? Let's say that you have some loop

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

How would I go about automatically fusing that into

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

How about

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

To

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

And for the final challenge, fuse

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

To

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

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

A general approach is to automatically infer loop invariants.  There are techniques for inferring loop invariants that can be expressed in Presburger arithmetic, i.e., linear expressions over the integers plus quantifiers.  These typically rely upon the fact that there exist decision procedures for Presburger arithmetic, e.g., the Omega method (see also the web site).

These methods should be enough to build a special optimization that can solve your first two challenges.  For instance, you can use those methods to find loop strides.  In particular, you can use those methods to characterize the values of i that will reach the then-block of the if-statement: you can first check whether the sequence of values of i lies in an arithmetic progression, then characterize the progression (deduce find the minimum value of i, deduce the maximum value of i, and deduce the stride).

These methods have been studied in depth in the compiler literature on loop vectorization, where we want to know whether we can execute each iteration of the loop in parallel on a separate core.  Similar techniques should be useful for your kind of problem as well.

I don't know whether there's any reasonable algorithm for your third example, or whether anyone has studied that sort of thing in the compiler literature.


Use of Process Calculi and PL Theory for modern programming language development For a while now, I have been very interested in programming language theory and process calculi and have started to study them. To be honest, it something that I wouldn't mind going into for a career. I find the theory to be incredibly fascinating. One constant question I keep running into is if either PL Theory or Process Calculi have any importance at all in modern programming language development. I see so many variants on the Pi-calculus out there and there is a lot of active research, but will they ever be needed or have important applications? The reason why I ask is because I love developing programming languages and the true end goal would be to use the theory to actually build a PL. For the stuff I have written, there really has not been any correlation to theory at all.

My answer is really just an elaboration of Gilles', that I had not
read before I wrote mine. Maybe it's nevertheless helpful.

Let me begin my attempt at answering your question with a distinction
between two dimensions of programming languages work that relate quite
differently to programming language theory in general and process
calculus in particular.

Pure research.
Product focused research and development.

The latter typically takes place in industry with the aim of providing
programming languages as a product. The teams developing Java at
Oracle and C# at Microsoft are examples.  In contrast, pure research
is not tied to products. Its aim is to understand programming
languages as objects of intrinsic interest and to explore the
mathematical structures underlying all programming languages.

Because of divergent goals, Different aspects of programming language
theory are relevant in pure research and in product focused R&D The
picture below may give an indication what's important where.

One may ask at this point why the two dimensions are so seemingly
different and how they nevertheless relate.

The key insight is that programming language research and development
has multiple dimensions: technical, social and economic.  Almost by
definition, industry is interested in the economic payoff of
programming languages. Microsoft et al don't develop languages out of
the goodness of their hearts but because they believe programming
languages give them an economic advantage.  And they have investigated
deeply why some programming languages succeed, and others, seemingly
similar or with more advanced features, don't.  And they found that
there isn't a single reason. Programming languages and their
environments are complex, and so are the reasons for adopting or
ignoring any specific language.  But the single biggest factor for the
success of a programming language is the preferential attachment of
programmers to languages that are already widely used: the more people
use a language, the more libraries, tools, teaching material are
available, and the more productive a programmer can be using that
language. This is also called the network effect. Another reason is
the the high cost switching languages for individuals and
organisation: mastering language, especially to a not-so-experienced
programmer, and when the semantic distance to familiar languages is
large, is a serious, time-consuming effort.  Given these facts, one
may ask why do new languages get traction at all?  Why do companies
develop new languages at all? Why don't we just stay with Java or
Cobol?  I think there are several key reasons for whey a language does
succeed, and displaces the originally more popular incumbents.

A new domain of programming opens up that has no incumbents to
displace.  The primary example is the web with its concomitant rise
of Javascript.
Language stickiness. By this I mean the high price of changing
language. But sometimes programmers move into different fields,
taking a programming language with them, and being successful with
the old language in the new field.
A language is pushed by a big company with serious financial
firepower. This backing reduces the risk of adoption, because early
adopters can be reasonably sure that the language will still be
supported in a few years. A good example of this is C#.
A language might come with compelling tools and eco-system. Here too
C# and it's .Net and Visual Studio eco-system could be mentioned as
an example.
Old languages pick up new features. Java comes to mind, which, in
each iteration, picks up more good ideas from the functional
programming tradition.
Finally, a new language might have intrinsic technical advantages,
e.g. be more expressive, have nicer syntax, typing systems that
catch more errors, etc.

Given this background, it should not come as a surprise that there is
somewhat of a disconnect between pure programming language research,
and commercial programming language development. While both aim to
make software construction and evolution more efficient, especially
for large-scale software, industrial programming language work must be
more interested in facilitating quick adoption to reach a critical
mass and get the network effect.  This leads to a research focus on
things that working programmers care about. And that tends to be
things like library availability, compiler speed, quality of compiled
code, portability and so on.  Process calculus as we practise it today
is of little use to programmers working on mainstream projects
(although I believe that will change in the future).

Pure programming language research is quite different. It works with
simplified models of programming languages: the $\lambda$-calculus is
a massive simplification of functional programming. In the same way
the $\pi$-calculus is a massive simplification of concurrent
programming. These massive simplifications are the key to successful
research. They enable us to focus on core computational mechanisms
(e.g. $\beta$-reduction for functional programming,
resolution/unification for logic-programming, name-passing for
concurrent computation). To understand if a language like Scala can
have viable full type-inference, we don't need to worry about the JVM.
Indeed thinking about the JVM will detract from a better understanding
of type-inference. That's why abstraction of computation into tiny
core calculi is vital and powerful.

So you can think of programming language research as a massive sandbox
where people play with toys, and if they find something interesting
when playing with a specific toy, and have investigated the toy
thoroughly, then that interesting toy begins its long march towards
mainstream industrial acceptance. I say long march because language
features first invented by programming language researcher tend to
take decades before becoming widely accepted. For example garbage
collection was conceived in the 1950s and became widely available with
Java in the 1990s. Pattern matching harks back to 1970 and is widely
used only since Scala.

Process calculus is an especially interesting toy.  But it's too new
to be investigated thoroughly. That will take another decade of pure
research.  What currently going in process theory research is to take
the single biggest success story of programming language research, the
theory of (sequential) types and develop the theory of types for
message passing concurrency.  Typing systems of moderate expressivity
for sequential programming, say Hindley-Milner, are now
well-understood, ubiquitous and accepted by working programmers.  We'd
like to have moderately expressive types for concurrent programming.
Research on this started in the 1980s by pioneers like Milner,
Sangiorgi, Turner, Kobayashi, Honda, and others, often based,
explicitly or implicitly, on the idea of linearity which comes from
linear logic.  The last few years have seen a major increase in
activity and I expect this upwards trajectory to continue for the
foreseeable future. I also expect this work to start leaking into
product focused R&D, in parts for the pragmatic reason that young
researchers who have been trained in process calculus will go and work
in industrial R&D labs, but also because of the evolution of CPU and
computer architecture away from sequential forms of computation.

In summary, I would not worry that you don't find cutting edge
programming language theory such as process calculus useful in your
own work of building languages. That's simply because cutting edge
theory does not address the concerns of current programming
languages. It is about future languages. It will take a while for the
'real world' to catch up. The knowledge you use to build languages for
today is the programming language theory of the past.  I encourage you
to learn more about process calculus because it's one of the most
exiting areas of all of theoretical computer science.


About Closure under Resolution The question looks very simple, that is why I posted it first on MathSE, unsuccesfully - no answer for 12 days. I tried to find a short and elegant answer to the question, but I haven't succeed yet. Thank you for your attention.

A CNF formula is closed under resolution if all the possible resolvents are subsumed by a clause of the formula - a clause $c_1$ is subsumed by a clause $c_2$ if all the literals of $c_2$ are in $c_1$ (any clause is subsumed by itself then).

Given $F$,  a 3-CNF formula on $n$ variables $(x_i)$$_{i\le 1 \le n}$ which is closed under resolution. Given $I$, a partial assignment of $k$ variables among $(x_i)\   (k\le n)$. Let $F_{|I}$ the induced formula by applying $I$ to $F$: Any clause that contains a literal which evaluates to "true" under $I$ is deleted from the formula and any literals that evaluate to "false" under $I$ are deleted from all clauses -  the clauses that become empty by this deletion remain in the formula as the empty clause.

Question: Is $F_{|I}$ closed under resolution ?

Sure. If $C_1\ni x_i$ and $C_2\ni\neg x_i$ are in $F\restriction I$ (in particular, $x_i$ is unset by $I$), pick clauses $D_1,D_2$ in $F$ which restrict to $C_1$ and $C_2$, respectively. Then $x_i\in D_1$ and $\neg x_i\in D_2$, hence their resolvent $(D_1\let\bez\smallsetminus\bez\{x_i\})\cup(D_2\bez\{\neg x_i\})$ is subsumed by some $D\in F$. If $D$ contains a literal made true under $I$, then so does $D_1$ or $D_2$, contradicting their choice. Thus, $D\restriction I$ is in $F\restriction I$, and it subsumes $(C_1\bez\{x_i\})\cup(C_2\cup\{\neg x_i\})$.


Monomial decomposition as product of smaller monomials Is there an algorithm to get all possible decompositions of a monomial as the product of smaller monomials ?

For example $x^2y^3$ is $x∗xy^3$, $x^2∗y^3$, $xy∗xy^2$, and so on.

For a monomial in one inderminate, I know I can use an integer partitions of the monomial degree.

But this does not apply when there are at least two indeterminates.

(Sorry for misuse of vocabulary and may be uncomplete tags : I am french).

Note : this is a step in construction of an invariant polynomial as described in DOI : 10.1016/j.ijsolstr.2005.05.021.

For the moment, let's restrict to counting these factorizations, rather than listing them.  Warming up with the one-variable case, integer partitions give the answer, as you point out.  You can compute the number $p(n)$ of partitions of $n$ using the generating function
$$\sum_n p(n)x^n = \prod_{i>0} \frac{1}{1-x^i}.$$
This generalizes easily to two variables.  If $p(m,n)$ is the number of "partitions" of the 2-long vector $(m,n)$ (i.e. representations of $(m,n)$ as a sum of positive integral multiples of vectors of the form $(i,j)$ with $i,j\ge0$ and $i+j>0$), then
$$\sum_{m,n} p(m,n)x^m y^n = \prod_{i,j\ge0;\ i+j>0} \frac{1}{1-x^i y^j}.$$
The sequence $p(m,n)$ appears as A054225 in the OEIS.

If you want to list the factorizations rather than count them, look instead at
$$\prod_{i,j\ge0;\ i+j>0} \frac{1}{1-u_{i,j}\ x^i y^j}.$$
For example, the coefficient of $x^2 y^2$ here is
$$u_{2,2} + u_{2,1}u_{0,1} + u_{2,0}u_{0,2} + u_{2,0}u_{0,1}^2 + u_{1,2}u_{1,0} +
  u_{1,1}^2 + u_{1,1}u_{1,0}u_{0,1} + u_{1,0}^2u_{0,2} + u_{1,0}^2 u_{0,1}^2,$$
corresponding to the 9 factorizations of the monomial $x^2 y^2$.

In principle you could write down a two-dimensional recurrence for $p(m,n)$ which is analogous to the recurrence for the ordinary partition numbers.  However, for it to be algorithmically useful (e.g. more efficient than computing the series expansion above), one would need a closed form for the coefficient of $x^m y^n$ in the product
$$\prod_{i,j\ge0;\ i+j>0} (1-x^i y^j).$$


How to Define and Implement (Single-Writer) K-Atomic Snapshot Object? I am trying to motivate, define, and implement $K$-atomic snapshot object. To this aim, I first give some basic definitions on atomic snapshot object and $K$-atomic object. Then, I will give my understanding of $K$-atomic snapshot object and present my problems.

Atomic Snapshot Object:

In the paper "Atomic Snapshots of Shared Memory", the authors consider atomic snapshot objects —— shared objects partitioned into segments. For the single-writer atomic snapshot object, each segment belongs to a different processor and is written separately, but all segments can be read at once by any processor.

  The sequence specification of an atomic snapshot object provides two kinds of operations for each user $i, 0 \le i \le n-1$:

  A $scan_i$ invocation whose response is $return_i(V)$, where $V$ is an $n$-element vector called a view with a value for each segment, and
  An $update_i(d)$ invocation whose response is $ack_i$, where $d$ is the data to be written to $p_i's$ segment.

  A sequence of $scan$ and $update$ operations satisfies the atomic snapshot semantics means that, for each $V$ returned by a $scan$ operation, $V[i]$ equals the value written by the latest preceding $update_i$ operation, for all $i$.

$K$-Atomic Object:

In the paper On the Availability of Non-strict Quorum Systems, $K$-atomic object is introduced. Different from the classical atomic object (see Sharing Memory Robustly in Message-Passing Systems), in a system with $K$-atomic semantics,

  there exists an order of the operations that is consistent with real time order and such that the values returned by a read operation is equal to one of the values written by the last $K$ preceding writes in the order.

Problem 1: How to Define $K$-Atomic Snapshot Object?

$K$-atomic object is a relaxation (or a generalization) of classical atomic object, which is actually $1$-atomic object.

So based on the two concepts of $K$-atomic object and atomic snapshot object, can we define, in a reasonable manner, the $K$-atomic snapshot object?

One possible trial is to relax the timeliness of the snapshot:

  A sequence of $scan$ and $update$ operations satisfies the $K$-atomic snapshot semantics means that, for each $V$ returned by a $scan$ operation,

  $V[i]$ equals one of the values written by the last $K$ preceding $update_{i}$s, for all $i$, and
  there exists some time before the $scan$ operation at which $V[i]$ equals the value written by its latest preceding $update_{i}$, for all $i$.

Problem 2: Do you know or can you figure out some other reasonable definitions of $K$-atomic snapshot object?

Any comments, any suggestions, and any related literature references are welcomed.
Also, I appreciate the idea of implementation of the $K$-atomic snapshot object defined above myself (if you think it is OK).

Regarding Problem 1: I think the first part of the definition is fine.
The second item (about the time before $scan$) is not clear to me; More specifically, the order of quatifiers: is it $\exists time: \forall i$ or $\forall i: \exists time$ ? I guess the first, because in the second I don't see why it is necessary. But definitions should not need guessing ;-)

Regarding Problem 2: In principle there is two ways of looking at $K$. You can consider the last $K$ updates on a per item level or the last $K$ updates globally. The other choice is (already mentioned above) whether to require a point in time when the memory actually had the value returned by $scan$ (the $\exists time: \forall i$ case above) or whether not to require such a point.

A general comment: What happens when every process just updates $K$ times and scans until two scans are equal. Wouldn't that (trivially) implement ($1$-)atomic snapshot memory? If that is the case then the whole idea of $K$-atomic snapshpot memory could be hard to sell.


Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs I recently came across a strange concept and was wondering if this was a known / named concept in the realm of CS.

The concept is that you evaluate some computation or logical circuit that takes in N number of binary inputs and gives an output. (and if doing multiple of these in parallel it could then be N inputs to M outputs)

You can then change your mind after the fact about the values of the binary inputs you want the algorithm to have evaluated and essentially re-interpret the result of the original equation to get the answer for those different inputs.

The benefit here would be that if there was some complex and lengthy computation, that you could do it once, and then just re-interpret the result to get the answer of that same algorithm for different inputs.

It sounds strange I know, but are there any existing methods for this, or terminology at least?

Example:

As an example let's say you calculated a function $f(x) = x * 8$ for $x=5$ in a specific way that gave you a resulting bit string.  When an operation was done on the bit string, which was a function of the inputs (say, XOR against a number which was the function of the inputs for example), that the value came out to be 40.

But then, you say "OK but what would it be for $f(6)$?".  Since 6 is different than 5, the XOR constant changes, but you can use that new XOR constant against the result you already got from the previous calculations, to get the new correct answer of 48.

The decoding process is the same regardless of the algorithm/function being evaluated.  It is a function of the inputs, and has nothing to do with the details of the function itself (so isn't iterative computation).

it almost seems a little related to a karnaugh map, in that you get something boiled down to the results of the algorithm, no matter how complex the steps were to get to that result originally.

I'm not sure, but you might be talking about what has been termed incremental computation.

The key idea behind incremental computation is to program in a way such that the program responds to input changes by updating its output while only re-evaluating those portions of the program affected by the change. Incremental computing is feasible in situations where input changes lead to relatively small changes in the output. Clearly, in limiting cases one cannot avoid a complete re-computation of the output, but in many cases the results of the previous computation may be re-used to obtain the updated output more quickly than a complete re-evaluation. In many cases, taking advantage of incrementality therefore dramatically improves performance, especially as the input size increases.

Designing and developing applications that respond to incremental modifications, however, is challenging: it often involves developing highly specific, complex algorithms.

This has lead some people to investigate the idea of moving the responsibility to avoid reevaluation where possible to the language run-time: instead of expecting the programmer to develop software for a particular application and a particular class of incremental modifications, the language run-time is tracking the dynamic data dependences of the computation and incrementally updating their output as needed. This is called  or self-adjusting computation, and  the person most associated with this programming language approach is Umut Acar. I recommend visiting his website for further information.

Note that ideas like this go back to the 1950s. Ad-hoc forms of incremental computing are heavily used in modern web-browsers because you don't want to reprocess ("reflow") the full page when a mutatation (e.g. Javascript performs a DOM operation) is performed.

I also recommend to consider the  related field of online algorithms.


Required delta between proceedings and journal versions I am recently getting my papers rejected from journals (i.e., TALG) on the mere basis of not having a significant difference between the journal and proceedings (i.e., SODA) version.

The main reasons for me to submit to a journal is its thorough review process.
Other than that, SODA's 20 page limit is more than enough for all that I want to say. In fact, David Johnson has repeatedly asked the SODA crowd to not "save stuff for the journal version".

Any advice?

It depends. If you write a paper and exhaustively include all of the relevant materials, then you should submit the paper to a journal (if you think the journal you choose is more valuable then a conference on the basis of impact factor, reputation and other metrics). If you only describe part of the work, then it may be better to submit to a conference and later, when you have new/updated results, then you may consider submitting again to a journal. What constitutes a significant difference is of course highly variable and depends on your particular work. A very rough rule of thumb is that journal versions differ for at least 30% from corresponding conference versions. However, there are exceptions. And, finally, you should carefully decide the venue. Especially in TCS, a conference may be extremely valuable, in some cases even more than a journal. I do not think that the review process applied in some highly valued conference is worse than the average review process applied in journals. This is strictly dependent on the particular conference or journal, and on the reviewers an editor finds available.


A flowchart for concentration bounds When I teach tail bounds, I use the usual progression:

If your r.v is positive, you can apply Markov's inequality
If you have independence and also bounded variance, you can apply Chebyshev's inequality
If each independent r.v also has all moments bounded, then you can use a Chernoff bound.

After this things get a little less clean. For example

If your variables have zero mean, then a Bernstein inequality is more convenient
If all you know is that the combining function is Lipschitz, then there's a generalized McDiarmid-style inequality
if you have weak dependence then there are Siegel-style bounds, (and if you have negative dependence, then Jansson's inequality might be your friend)

Is there a reference anywhere to a convenient flowchart or decision tree describing how to choose the "right" tail bound, (or even when you have to dive into a sea of Talagrand) ?

I'm asking partly so that I have a reference, partly so that I can point it to my students, and partly because if I'm sufficiently annoyed and there isn't one, I might try to make one myself.

Fan Chung and Linyuan Lu.
Concentration inequalities and martingale inequalities: a survey
available at
http://projecteuclid.org/euclid.im/1175266369 or at Fan Chung Graham's web page.


Complexity of a variant of the max word problem. NP-complete? I'd like to be able to state that the following problem is NP hard.
I am wondering whether anybody have any pointers to related/recent work?

The problem:
Given a finite set of transition matrices $A$ and two non-negative vectors
$\vec{x}$ and $\vec{y}$.

Do there exist $A_1, A_2, ..., A_n \in A$ such that

$$\vec{x} \, A_1 \, A_2 ...  A_n \, \vec{y} \geq P$$

If you allow the repetition of matrices, i.e. there exists $ 1 \leq i < j \leq n $ s.t. $ A_i =A_j $, then your problem is actually undecidable.

Let $ EMPTY_{PFA} $ be the emptiness problem for probabilistic finite automaton (PFA).

A PFA is a 4 tuple: $ P=(\Sigma,\{A_{\sigma \in \Sigma}\},x,y) $, where $\Sigma = \{\sigma_1,\ldots,\sigma_k\}$ is the input alphabet, each $ A_{\sigma} $ is a stochastic matrix, $x$ is a stochastic row vector (initial distribution), and $ y $ is a zero-one column vector. Each word, say $w \in \Sigma^*$, corresponds to a sequence of the matrices from $ \{A_{\sigma \in \Sigma}\} $ by allowing repetition, and vice versa. The accepting probability of $w$ by $P$ is as follows:

$$f_P(w) = x \cdot A_{w_1} \cdot A_{w_2} \cdots A_{w_{|w|}} \cdot y, $$

where $w_i$ is the $i^{th}$ symbol of $w$ and $|w|$ is the length of $w$.

$ EMPTY_{PFA} $ is the problem of, for a given PFA $ P $ and a threshold $ \lambda \in (0,1) $, whether there exists a word accepted with a probability at least $ \lambda $. $ EMPTY_{PFA} $ was shown to be undecidable. It is an old result and you can start digging from this article: http://arxiv.org/abs/quant-ph/0304082

$ EMPTY_{PFA} $ can be reduced to your problem. So, if your problem is decidable, then $ EMPTY_{PFA} $ is also decidable. But this is a contradiction. So, your problem is undecidable, too.


Super-logspace mapping reducibility There are two well-known mapping reducibilities: polytime and logspace. In both cases, the length of the output string can be at most polynomial in the length of a given input string. If we allow to use more space (super-logspace), then the length of the output string can be super-polynomial.

Therefore, it seems interesting to me to ask whether this blow-up helps us to reduce some difficult problems to some easier problems when using super-logspace $ \left(\omega(\log n) \right) $. I am not interested in the "cheap" tricks such as padding.

More generally, is there any literature on super-logspace (or super-polynomial) mapping reducibility?

DEFINITION

Language $ \mathtt{A} $ is $s(n)$-space mapping reducible to language $ \mathtt{B} $, shown as $ \mathtt{A} \le_{m}^{s} \mathtt{B} $, if there exists a $ s(n) $-space DTM $ \mathcal{D} $ outputting $ f_{\mathcal{D}} (w) $ for a given input $ w $ such that

\begin{equation*}
 w \in \mathtt{A} \mbox{ if and only if } f_{\mathcal{D}} (w) \in \mathtt{B},
\end{equation*}

where $ \mathcal{D} $ has a two-way read-only input tape, a two-way read/write work tape, and a one-way write-only output tape.

UPDATE:
I have found an answer to my own question. But, I am still interested in further results.

In Model Checking Recursive Programs with Numeric Data Types, Hague and Lin presented a NEXP-complete language under logspace reduction, called $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $ composed by strings

\begin{equation*}
a^m \# a^k \# \theta,
\end{equation*} where $ \theta $ is a Boolean formula with variables $ x_1, \ldots, x_{m+k} $ satisfying that the string $ b \# a_1 \# \cdots \# a_{2^k-1} $ defined based on $ \theta $ (described below) is a member of $ \mathtt{KNAPSCAK} $, i.e. $ \sum_{i=1}^{2^k-1} a_i z_i = b $ for some $ z_1, \ldots,z_{2^k-1} \in \{0,1\} $, where $ b $ and each $ a_i $ are precisely $ 2^m $ bits (leading 0s permitted) binary numbers.

The string $ b \# a_1 \# \cdots \# a_{2^k-1} $ is defined based on $ \theta $ as follows. Let $ (i)_{2,k} $ be the $ k $-bit binary representation of $ i $.

The $ i^{th} $ bit of $ b $ is the value of $ \theta $ by setting $ x_1,\ldots,x_{k+m} $ to the digits of $ 0^k  (i)_{2,m} $ in order.
The $ i^{th} $ bit of $ a_j $ is the value of $ \theta $ by setting $ x_1,\ldots,x_{k+m} $ to the digits of $ (j)_{2,k}  (i)_{2,m} $ in order.

It is not hard to show that $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $ can be reduced to NP-Complete $ \mathtt{KNAPSCAK} $ via linearspace reduction.

Moreover, since any language in NEXP is logspace reducible to $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $, we can say that any language in NEXP is polyspace reducible to $ \mathtt{KNAPSACK} $. (Here we can combine logspace and linearspace reductions. Since the output string after logspace reduction can have polynomial length, we can use polynomial space overall.)


putting objects in buckets -- optimization problem Let $\mathcal B$ and $\mathcal O$ denote finite sets ("buckets" and "objects", respectively) and let
$$
E: \mathcal O \times \mathcal B \to \mathbb{R}_{>= 0}
$$
be a function.  Is there an algorithm that, given a partition of $| \mathcal B |$,
$$
| \mathcal B | = \sum_{b \in \mathcal{B}} \mu_b
$$
returns a function $\varphi: \mathcal O \to \mathcal B$ maximizing the quantity
$ \sum_{o \in \mathcal O} E(o, \varphi(o))$, subject to the constraint that $| \varphi^{-1} (b)| = \mu_b$ for all $b \in \mathcal B$?

Motivation: all objects need to be put into a bucket, but the buckets have different sizes.  The function $E$ gives the value of placing a given object in a given bucket.  If the buckets each have a certain capacity, how can an optimal distribution of objects in buckets be found?

I assume that $\cal O$ and $\cal B$ are of polynomial size. One way to solve this problem is to reduce it to the Maximum Cost Bipartite Matching Problem. Consider the following bipartite graph $G = (L\cup R, E)$:

$L = \{b_i: b\in {\cal B}, 1\leq i \leq\mu_b\}$, that is,  for
every bucket $b$ and $i\in \{1,\dots, \mu_b\}$, we introduce a vertex
$b_i$
$R = \cal O$
$E = L \times R$, the cost of the edge $(b_i,o)$ equals $E(o,b)$.

We find a maximum cost matching $M$ in $G$. Now we construct the solution to our original problem: bucket $b$ contains those objects that are matched in $M$ with vertices $b_1, \dots, b_{\mu_b}$. Clearly, each bucket $b$ contains $\mu_b$ objects. The value of this solution equals the cost of $M$.


finite automata under morphism Given two (deterministic) finite automata $A, B$ over $\Sigma$, a mapping $h:\Sigma\rightarrow \Sigma'$

Naturally $h$ can be extended to a mapping in $\Sigma^*\rightarrow \Sigma'^*$ which is denoted by $h$ as well.

Is the set
$$\{w\in L(A)\mid h^{-1}(h(w))\subseteq L(B)\}$$ regular?

The answer is yes. To prove this, consider the complement language:
$$\{w: w\notin L(A) \vee \exists x: h(x)=h(w)\wedge x\notin L(B)\}$$

Now, we construct an NFA $C$ as follows. Given a word $w$, $C$ has $\overline{A}$ as a component, such that if $w\notin L(A)$ then $C$ accepts. It remains to check the rest.

Let $D$ be a DFA that recognizes $\overline{B}$.
In order to check if there exists a word $x$ as described, $C$ guesses (i.e. has a nondeterministic transition), for every letter $\sigma$ of $w$, a transition in $D$ that can be taken with a letter $\tau$ such that $h(\tau)=h(\sigma)$. The accepting states of this component are those of $D$.

It is not hard to prove that $C$ accepts the language above, and by complementing it you get an automaton for your desired language.


Complexity of permutation related problems Given a group $G$ of permutations on $[n]=\{1, \cdots, n\}$, and two vectors $u,v\in \Gamma^n$ where $\Gamma$ is a finite alphabet which is not quite relevant here, the question is whether there exists some $\pi\in G$ such that $\pi(u)=v$ where $\pi(u)$ means applying the permutation $\pi$ on $u$ in an expected way.

Suppose further that $G$ is given, as the input, by a finite set $S$ of generators. What's the complexity of the problem? In particular, is it in NP?

Let $g_1, \ldots, g_k, g \in S_n$ where $S_n$ is the permutation group on $n$ elements. Testing whether $g \in \langle g_1, \ldots, g_k \rangle$ can be done in $\text{NC} \subseteq \text{P}$ by [1]. Let $u, v \in \Gamma^n$, then simply guess $g \in S_n$, test in polynomial time whether $g \in G$ and whether $g(u) = v$. This yields an $\text{NP}$ upper bound.

To complement this answer:

  Group membership was shown to belong to $\text{P}$ (Furst et al. 1980), then to
  $\text{NC}^3$ for abelian groups (McKenzie & Cook 1987; Mulmuley
  1987), to $\text{NC}$ for nilpotent groups (Luks & McKenzie 1988), solvable
  groups (Luks & McKenzie 1988), groups with bounded non-abelian
  composition factors (Luks 1986), and finally all groups (Babai et al.
  1987). A similar complexity classification of  aperiodic monoids
  membership owes to (Beaudry 1988; Beaudry et al. 1992; Kozen 1977),
  who show that membership for any fixed aperiodic monoid variety is
  either in $\text{AC}^0$ , in $\text{P}$, in $\text{NP}$, or in $\text{PSPACE}$ (and complete for
  that class with very few exceptions).

[1] L. Babai, E. M. Luks & A. Seress. Permutation groups in NC. Proc. $19^\text{th}$ annual ACM symposium on Theory of computing, pp. 409-420, 1987.


Algorithms for Nash equilibrium computation. I searched the forum to see if this has been asked before, and while algorithmic game theory is discussed, I couldn't find this particular issue addressed.  I am trying to figure out what the best known algorithm is for computing approximate (mixed-strategy) Nash equilibria in a finite n-person game.  Of course, this algorithm would be PPAD.  I am more interested in speed/efficiency than perfect accuracy of the algorithm.

Thanks,
Philip

Perhaps the 2008 paper presented at the Symposium on Algorithmic Game Theory
by Hémon, Rougemont, and Santha, "Approximate Nash Equilibria for Multi-player Games" could help?
They "exhibit polynomial-time algorithms for additive approximation" for $n$-player games.


Paths and Probabilities for a Random Walk on a Graph I'm working on a problem about $N$ nodes that are randomly positioned on a rectangular grid. I want to take a sample of $n\leq N$ nodes by randomly selecting the first node then visiting the nearest neighbour of the last selected node. Once a node is visited, it is excluded from future selctions. If a node has there multiple nearest neighbours, one is randomly picked among them.

I'm interested in the probability that a node is visited (I'm also interested in the probability that a pair of nodes appear in the same sample). I'm using the following population as an example: $$\{(-4,6),(0,5),(-3,4),(-2,4),(2,4),(3,4),(1,3),(5,3),(3,2),(2,1),(-1,0),(-3,1),(1,-1),(-4,-2),(-3,-2),(-1,-2),(3,-2),(4,-2),(2,-3),(4,-3),(2,-4),(4,-4),(5,-4),(-5,-5),(2,-5)\}$$

(Note: The numbers above the points are just identifying labels. They do not indicate anything about the order in which they are visited. A sample of three points would be something like $6 \rightarrow 5 \rightarrow 7$)

Here are my two approaches:

Enumerate all the possible paths of a specified length, calculate the probability of each path, then sum up the probabilities of the paths that include a particular node.
Repeatedly take samples then calculate the proportion of paths that include a particular node.

Is there a better way to solve my problem? By the way, I'm using R to do the computing.

I don't have any background in graph theory whatsoever. I'd like to look up terms and concepts that would be relevant to what I'm doing, but I'm not even sure where to begin. Do you have any ideas for a solution or do you know of any resources that can be understood by a novice?

You can make a state machine from this as follows.

Let the set of points generated be $V$.

Add extra dummy start node $s$. Add edges $(s, v)$ for all $v \in V$. And add edge
from $(u, v)$ where $u, v \in V$ are nearest neighbors.

Assuming points to visit are chosen uniformly assign probability $1/|V|$ to edges $(s,v)$
and probability of $1/\text{number of nearest neighbors}$ to edges that connect nearest neighbors.

This now forms a state diagram like http://en.wikipedia.org/wiki/Markov_chain#Example

The graph can be represented as matrix $G$ where $G_{ij} =1$ if there is edge between $i$ and $j$.
And probabilities can be put in a matrix $P$ of size $N + 1 \times N + 1$.

$G^k_{ij}$ gives number of paths of length $k$ from $i$  to $j$.

$(P^k x)_j$ gives probability of reaching $j$ from $i$ in $k$ steps where $x$ is a vector where only $i^{th}$ entry is 1 and others are 0.


Does $\exists\mathbb{R}=\mathbf{PSPACE}$? The complexity class $\exists \mathbb{R}$ (the existential theory of the reals, i.e. problems that can be reduced to deciding if a collection of polynomial inequalities has a solution) is known to be contained in PSPACE and to contain NP. See this paper for a reference; as far as I can tell, that's the paper that introduced $\exists\mathbb{R}$ as a distinct complexity class.

However, Reif gives an explicit construction which takes a Turing machine with a polynomial space bound and a string, and constructs a motion planning instance which has a solution if and only if the machine accepts the string. Since motion plan existence can be reduced to $\exists\mathbb{R}$ (see, e.g., this paper by Schwartz and Sharir), this seems to imply that $\mathbf{PSPACE} \subseteq \exists\mathbb{R}$, and thus that $\mathbf{PSPACE} = \exists\mathbb{R}$.

I don't come from a CS theory background, and I feel like I must be missing something fundamental, because there looks to be a whole subfield  of authors writing papers placing various problems in $\exists\mathbb{R}$.

The issue may be whether or not Schwartz and Sharir show that motion plan existence is many-one polynomial time reducible to $\exists\mathbb R$.

If they need several queries to $\exists\mathbb R$ for a given motion plan existence instance, then that's not a many-one reduction.


Is there an efficient algorithm to find the i-th dearrangement? Here is the background for this question. Friends and I were playing a game where everyone needs to give another people some gift. In order to determine who should give gift to whom, we decide to drew lots. But the problem is, someone might end up giving him/herself gifts, which is not funny. You can see that the expected number of such unfortunate people is 1, so this happens quite frequently.

For this purpose, dearrangement seems to be a great fit. If I can fairly generate a dearrangement, then I can just pick one dearrangement and use it to decide who give whom gifts.

Randomized dearrangement generation could be done with Las Vegas method. But the problem is,
it only has expected polynomial running time. So I came to this problem of finding i-th dearrangement. If I can randomly pick an i in [1, D_n], and use some worst case polynomial time (efficient) algorithm to obtain the i-th dearrangement, then it's done.

Actually this is might be good question but it is badly formulated in its current form. The well-known algorithms for generating random derangements have linear expected time, but maybe it's an open problem to find a worst case polynomial time algorithm.

See for example:
http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (and slides: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf)


Max flow: either saturate an edge or avoids Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half through another edge.

Can this be formulated as a max flow problem with a polynomial time solution or is this problem hard?

This problem is NP-hard.

Reduction from PARTITION:

Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:

$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$
$$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$
$$c((s,x_i))=c((x_i,v))=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$

$S$ is partitionable iff there exist "saturate edge or avoid" flow of value $c((v,t))$.


Fixed parameter tractable Integer Programming and $FPP$ Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $NC$? (Update: It is not known)
 What are some examples of problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $P$ complete and problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $NC$? Is there a theory behind such classification? (resolved by Ronald de Haan).

You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are often considered as subsets of $\Sigma^* \times \mathbb{N}$ (see [1, Chapter 2]). Classical complexity classes (such as NC, P and NP) are sets of classical decision problems, and parameterized complexity classes (such as FPT) are sets of parameterized decision problems.
(If $Q \subseteq \Sigma^* \times \mathbb{N}$ is a parameterized decision problem, then the unparameterized version of $Q$ denotes the classical decision problem $Q' = \{ x\ |\ (x,k) \in Q \}$.)

Integer linear programming (ILP) is a classical decision problem (that is, the variant you're referring to: deciding whether there exists a feasible integer solution that achieves at least a certain value of the objective function). If you consider a parameterized variant of this problem (e.g., when taking as parameter the number of variables), it is a parameterized decision problem. So asking whether the problem of ILP parameterized by the number of variables is P-complete or in NC does not make sense. What you should be asking is whether it is complete for a parameterized analogue of P, or whether it is contained in a parameterized analogue of NC.

The parameterized complexity class FPT (consisting of all parameterized decision problems that are fixed-parameter tractable) is the parameterized analogue of P. One possible appropriate parameterized analogue of NC is the parameterized complexity class FPP (see [2]). FPP consists of all parameterized decision problems that are solvable in time $f(k) \cdot (\log n)^c$ by a parallel algorithm with at most $f(k) \cdot n^c$ processors, for some computable function $f$ and some constant $c$, where $n$ is the input size and $k$ is the parameter value.

To answer question (2): an example of a parameterized decision problem that is FPT-complete and whose unparameterized version is NP-complete, is the problem of satisfiability of propositional logic formulas in CNF, parameterized by the size of the smallest strong backdoor to Horn (see, e.g., [3]). Essentially, this problem is FPT-complete (under an appropriate parameterized variant of log-space reductions) because satisfiability for propositional Horn formulas is P-complete (under log-space reductions).

For any NP-complete decision problem, you can come up with a parameterized version that is in FPP: take as parameter the size of the input. Then the problem is (trivially) solvable in time $f(k)$ (for some exponential function $f$) on a single processor. Basically, such an algorithm can solve the problem in brute force in time $f(k)$. You're probably asking for natural parameterized variants of NP-complete problems that are in FPP.

References

[1] Downey, Rodney G., and Michael R. Fellows. Fundamentals of parameterized complexity. Springer, 2013.

[2] Cesati, Marco, and Miriam Di Ianni. Parameterized parallel complexity. European Conference on Parallel Processing. Springer, Berlin, Heidelberg, 1998.

[3] Gaspers, Serge, and Stefan Szeider. Backdoors to satisfaction. In: The Multivariate Algorithmic Revolution and Beyond. Pages 287-317. Springer, 2012.


Optimizing multiplication in a partly commutative semigroup Let us say I have a semigroup M and its basis B. I know which elements of B commute.

What is the most efficient way to do multiplication in such a semigroup?

Essentially, this is a question of how to reduce "ABAAAXBCAAB" to "AAAABXAABBC" knowing that A, B and C commute with each other but not with X (after such a transform I can, for example, compute AAAA as (A^2)^2, or even store pre-computed powers of each element of B).

Okay, I've given it a bit of thought and I see that the algorithm is very easy.

Example: Let % denote "commutes". Let A % B, A % C, B % C, B % X.

Compute ABAAXCBA:

Let us keep a "result", an "active multiset" and a "remaining suffix". Let us append a special "$" symbol that commutes with noone onto the string.

Invariant: the product of "result", active multiset and the remaining suffix equals the product of original string.

Invariant: all items in the active multiset commute.

At each new element of the suffix, drop elements from the active multiset that don't commute with it into the product, and insert the element into the multiset.

(1, {}, ABAAXCBA$) ->
(1, {A:1}, BAAXCBA$) ->
(1, {A:1, B:1}, AAXCBA$) ->
(1, {A:2, B:1}, AXCBA$) ->
(1, {A:3, B:1}, XCBA$) -> (drop A^3)
(A^3, {B:1, X:1}, CBA$) ->
(A^3 X, {B:1, C:1}, BA$) ->
(A^3 X, {B:2, C:1}, A$) ->
(A^3 X, {B:2, C:1, A:1}, $) ->
(A^3 X B^2 C A, {$}, )

This version has at most O(|A|) (size of alphabet) overhead per input symbol and it does an optimal number of multiplications.


Complexity of Set Difference Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes $S_i \backslash S_j$ for any $i$ and $j$?
Has this problem been studied before in the literature? If an output-sensitive algorithm (after preprocessing the sets) is not possible, what is the best complexity we can attain?
I found that there is a related problem which focuses on set intersection rather than set difference. To the best of knowledge, there is no output-sensitive algorithm for the case of set intersection.

(Sorry but not enough reputation otherwise this would be a comment.)
Note that set difference is equivalent to set intersection with the complement i.e. $S_i\backslash S_j = S_i \cap \overline{S_j}$. Thus you could double the number of sets to $S_1, S_2, ...., S_k, \overline{S_1}, ..., \overline{S_k}$ and apply the set intersection pre-processing to the appropriate pairs.


Do "One Way Functions" have any applications outside crypto ? A function $f \colon \{0, 1\}^* \to \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm $A$,

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

for every polynomial $p(n)$ and sufficiently large $n$, assuming that $x$ is chosen uniformly from $\{ 0, 1 \}^n$. The probability is taken over the choice of $x$ and the randomness of $A$.

So... do "One Way Functions" have any applications outside cryptography? If yes, what are they?

One-way functions show up crucially in the Razborov-Rudich natural proofs result. I wouldn't consider circuit lower bounds as part of "cryptography", so maybe this fits your criteria.


Required mathematics for computational geometry research career I have a computer engineering degree and i am very interested in theoretical and combinatorial aspects of computational geometry .

I want to build the mathematical foundation for this area so i can apply for a decent research based postgraduate program .

My question is :
What topics in math should I study to prepare for this goal?

thank you

I'm going to answer a slightly different question (as indicated in my comment):

  Is there specific mathematical background that would help prepare for
  a graduate degree in TCS that focuses on computational geometry?

I have found (from conversations with other TCSers) that some kinds of geometric intuition are unfamiliar, so the best kind of background will help you in that regard. A comprehensive list along these lines would include:

Topology (point-set, combinatorial and algebraic)
Differential geometry (and some basic Riemannian geometry as well)
Convex analysis (especially duality)
Some basics in algebraic geometry (at least polynomials)
Basic functional analysis (normed spaces, Hilbert spaces, etc)

All of these tools show up in computational geometry nowadays on a regular basis, and their use will only get more sophisticated with time.

p.s As an aside, if you have a computer engineering degree, it's possible that your background in core theoryCS is weaker than if you had a straight-up CS degree (because of the emphasis on the EE side of things). If that's the case, then the material in the links provided by Kaveh will be immensely useful, probably more so than this list.


Canonical way of coloring graphs (individualization) for isomorphism purpose Stefan Kratsch and Pascal Schweitzer in their paper
Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs
give a characterization of graphs on which
Graph Isomorphism is solvable in polynomial time (Theorem 4, page 8).

I have a problem understanding the outline of the proof for Theorem 4 and
therefore the proofs of the different cases itself.
The main idea is to construct colored graphs of bounded color valence
for which the problem is solvable in polynomial time according to Theorem 5.

For creating such graphs one tries to find a canonical coloring.
One such method is called individualization.

As this method is just described as:

  We guess an ordered set of vertices of constant size,
  color the vertices in this set with singleton colors, and then
  color the remaining vertices according to their adjacencies to
  the vertices in the ordered set.

and not further specified in the following proofs.

I have two questions:

How exactly is this coloring done?
What exactly is a canonical coloring?

Typically the way individualization goes is this. You're trying to decide if two vertex-colored graphs $G$ and $H$ are isomorphic in a way that respects the colors (sends vertices of color $c$ in $G$ to those of the same color $c$ in $H$). You pick a vertex $v$ in $G$ and assign it a new color, say $c$, that has not been used before. This is called "individualization." Then for each vertex $w \in V(H)$ you will, in turn, try coloring $w$ with $c$ and see if there is an isomorphism $G \to H$ that respects this new coloring. (This incurs a multiplicative cost of $|V(H)|$, so you don't want to do this too often.) In other words, you are guessing the vertex $v$, and then trying to see which vertices of $H$ it can possibly map to.

To aid in this quest, frequently individualization is followed by a process called (Weisfeiler-Lehman) refinement. What happens here is that you assign new colors to each vertex according to the multi-set of colors of its neighbors. Then you do this again. Then you do this again. And you keep doing this until the partition of vertices by color does not change.

An isomorphism-invariant coloring of graphs is a method of assigning colors to vertices so that if two graphs are isomorphic, then there is an isomorphism between them that sends vertices of color $c$ to vertices of color $c$. Some authors will call this coloring canonical - and indeed, in the paper you cite, it may be that all they need is a canonical coloring in which each color class has bounded size. (Other authors might say that a canonical coloring is an isomorphism-invariant coloring in which each vertex receives a color that is distinct from that of all other vertices. In this way, if we can compute a canonical coloring of two graphs $G,H$, then there is only one possible isomorphism between them (namely, the one that respects the colors), and it is easy to check whether this is actually an isomorphism.)

Combined with individualization, one can talk about a coloring that is canonical relative to the individualizations that have been made previously. That is, it may not be canonical with respect to isomorphisms of the original graphs, but given the vertices that have been colored so far it is canonical. (In this sense individualization is a form of "partial brute-force search," in which you keep track of how the guesses you've made so far constrain your future search.)


Tableau method for two-variable first-order logic $FO^2$, i.e. two-variable first-order logic, has a NEXPTIME-complete satisfiability problem (see Grädel, Kolaitis and Vardi '97). However, the decidability and complexity of this fragment is proved by that paper in an indirect way, as far as I can tell.
What I need instead is an effective way to solve $FO^2$ satisfiability. What are the actual algorithms and methods available for this logic?
In particular, I would need a tableau-based method for $FO^2$ satisfiability. Is there any resource describing such a thing? Has it ever been developed?

You might check the FO2 solver by Tomer Kotek: https://forsyte.at/alumni/kotek/fo2-solver/ This is the only existing FO2 solver (Tony Tan with his student have a paper under submission, in which they proposed another algorithm, based on probabilistic methods).
I'm not aware of any tableaux algorithm for FO2.