texts: Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

texts:
Edit: I originally defined a regular function as a function computable by a Mealy machine, but Denis pointed out that that was a weaker model than what I was thinking of.

So to be more precise, by a "finite-state transducer" with input alphabet $A$ and output alphabet $B$, I mean a deterministic finite automaton over $(A \cup \{\epsilon\}) \times (B \cup \{\epsilon\})$.

In particular, if both of the following hold for a transducer, then the transducer computes a function:

Every transition $(q, (x,y), q')$ is uniquely determined by $q$ and $x$;
If there is a transition $(q, (\epsilon, x), q')$ for any $x$, then there are no other transitions from state $q$.

Feel free to generalize or restrict as desired.

Definitions:

Let $L$ and $M$ be languages. A regular function $f:L\to M$ is a function computable by a finite-state transducer $A$ such that $(l,m)\in L(A)$ if and only if $l \in L$ and $m=f(L)\in M$. Note that it is decidable whether the relation computed by a given FST is a function.

Define the equalizer $Eq(f,g)$ of two regular functions $f,g:A\to B$ as the set of all strings $x\in A$ such that $f(x)=g(x)=y$ for some $y\in B$.

"Theorem": The equalizer of two regular functions is regular.

"Proof": Since $f$ and $g$ are regular functions, they are also regular relations. In particular, we can take their intersection $h=f\cap g$. By definition, we have $(x,y)\in h$ if and only if $(x,y)\in f$ and $(x,y)\in g$; in function notation this becomes $(x,y)\in h$ iff $f(x)=g(x)=y$. By the closure properties of regular relations, it follows that $h$ is a regular relation; and since $f$ and $g$ are functions, $h$ is also a function.

Since $h$ is a regular relation, it is recognized by some finite state transducer $T$. We can take the input projection $\pi_1 T$, giving us a finite automaton which accepts a string $x$ if and only if $(x,y)\in h$ for some $y$. Let $E$ denote the language of the automaton $\pi_1 T$. By the definitions of $h$, $f$, and $g$, it follows that $x\in E$ if and only if $x\in A$ and $f(x)=g(x)=y$ for some $y\in B$. $\square$

But wait. Suppose $A$ is the set of all nonempty strings $\Sigma^+$ over some alphabet $\Sigma$, and suppose $f$ and $g$ are homomorphisms (every homomorphism is a regular function.) Then we can take the equalizer $P=Eq(f,g)$, which is regular by the above "theorem".

Now $P$ will be nonempty iff there is a string $x\in \Sigma^+$ such that $f(x)=g(x)$. In other words, $P$ encodes the Post correspondence problem (PCP) for $f$ and $g$.

But since $P$ is regular, it is recognized by some finite automaton, and emptiness is decidable for finite automata. Since intersection and projection are computable constructions on transducers, we therefore have a method to solve PCP given the transducers for the homomorphisms $f$ and $g$. But this is impossible since PCP is undecidable. So where am I wrong?


texts: Conditioning Probability on a Language With Measure 0

texts:
Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you can think of an infinite word $w$ over $\Sigma$ as a result of tossing the n-sided coin infinitely many times.
With this view, I can think of $\omega$-regular langauges over $\Sigma$ as events. There are interesting languages that have measure $0$. For example, consider the language $L = \bigcup\limits_{i\in \Sigma } \Sigma^* \cdot (\Sigma \setminus \{i\})^\omega$. That is, $L$ consists of all infinite words over $\Sigma$ that have finitely many $i$'s, for some $i$.
Now I am interested in computing $P(L_2|L)$ for some language $L_2 \subseteq L$. Sometimes, I can guess the answer by "symmetry" considerations in case $L$ and $L_2$ are "simple" enough, but my question is: how can I condition on a language $L$ which is of measure $0$ in the general case?
Example:
assume again that $L = \bigcup\limits_{i\in \Sigma } \Sigma^* \cdot (\Sigma \setminus \{i\})^\omega$. Consider the following event (or language):
$$ L_2 = L\setminus \{ w \in \Sigma^\omega: \text{$w$ has finitely many 1's, and every $j\neq 1$ appears infinitely often in $w$}\}$$
What is $P(L_2|L)$? In other words, how can I compute the fraction of words that I did not through out from $L$.
I believe there is a way to condition on a language of measure $0$ but I'm not sure how. A similar simple situation appears in the following: one can sample a random $(x, y)$ point in a rectangle $[0, 1]\times [0, 1] \subseteq\mathbb{R}_2$ and then ask what is the probability $P(y \geq \frac{1}{2} | x = \frac{1}{2})$. Clearly, this probability is $\frac{1}{2}$ although we condition on the line $x = \frac{1}{2}$ which has measure $0$ in $[0, 1]\times [0, 1]$. The way I think about the line-rectangle example is as follows. I imagine the line $x = \frac{1}{2}$ as a rectangle of width $\epsilon \to 0$. Is there a similar approach that can be adapted to $\omega$-reuglar languages?


texts: Where is $MA$ more relevant than $\exists BPP$?

texts:
(EDITED)
A previous version of this question asked about a complexity class I called $MA^*$, which has been recognized by users to be $\exists BPP$.
The difference between $MA$ and $\exists BPP$ is that in the latter class the probabilistic verifier decides a BPP language; while the probabilistic verifier in $MA$,  when $x\in L$, is required to accept with bounded error only for one certificate and can answer just randomly for all the others, thus violating the BPP promise.
What is the natural reason to allow this "strange" power to the class? E.g. an $MA$ language which is not (trivially) in $\exists BPP$ would answer the question. More generally, in which contexts the class $MA$ comes up naturally but $\exists BPP$ wouldn't (trivially) work?
P.S. For now, I'm answering me as follows. A set $C$ of certificates $x,c$ for $x \in L$ makes sense only in reference to a verification procedure for $(x,c)$. If the verifier is probabilistic, and we want bounded error, there could be some $x,c$ that aren't decided. For $x \notin L$, it remains defined that $(x,c) \notin C$, or soundness is compromised. But what should define $(x,c) \in C$ for $x \in L$, if not the verification procedure itself? So in this sense $MA$ is more natural than $\exists BPP$, because $MA$ doesn't assume $C$ before the verification procedure.


texts: On-policy/Off-policy Offline/Online Evaluation: Which would be an example of Online Off-Policy Evaluation?

texts:
In the context of the following question:
off-policy and offline policy reinforcement learning
, it can be concluded that off-policy/on-policy learning can be orthogonal to an online/offline sampling scenario.

I am having trouble connecting these concepts to the idea of evaluating an RL approach (target/behavior policy) aimed to be deployed in a real-world environment (e.g. a web application).

In this case, I believe that the online evaluation would be to test the RL approach when deployed and that the offline evaluation would be to use historical data or a simulation of the real-world environment.

Following this assumption, examples of the different evaluation combinations can be:

Off-policy/offline evaluation: evaluate the target policy using a historical dataset collected with a policy other than the target policy.
On-policy/online evaluation: experience used to evaluate is collected by following the target policy sampling directly from the real-world environment.

But it is hard for me to think of examples for the other combinations:

On-policy/offline evaluation: data used to evaluate the target policy is collected by following the target policy on a simulation of the real-world environment. Does this make sense?
Off-policy/online evaluation: I can't think of an example that makes sense, i.e., if the target policy can be evaluated directly with the real-world environment, why use a different behavior/target policy to sample experience?

Note that my question is in the context of evaluation, i.e. the goal is only to evaluate the target policy and not to learn a new policy.

I am wondering if any of these ideas make sense and if anyone can think of an example for the case of Off-policy/online evaluation?


texts: Computational complexity of classifying with an already-trained SVM

texts:
If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine?  I care about both time and space complexity.

Does the answer change if the underlying metric space is unusual -- for instance, Damerau-Levenshtein edit distance (computing which is $O(n^2)$ time and space for strings of equal length) instead of Euclidean ($O(n)$ time and $O(1)$ space)?

(This is related to Computational complexity of learning (classification) algorithms - fitting the parameters but that's about the training process.)

(Edit: the paper that sparked this question is http://www.cs.stonybrook.edu/~xcai/fp.pdf )


texts: Communication complexity of edit resilient synchronization

texts:
Supposing we have two strings $A$ and $B$ that are both edit distance $\tau$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been studied?

Supposing before edit errors assume $A$ and $B$ have been distorted by some additive noise is there a communication complexity model where synchronizing such strings have been studied?

I am looking for reasonable upper and lower bound models. I am also looking for references and survey of bounds.


texts: What evidence do we have for (and against) Unique Games Conjecture?

texts:
Subhash Khot's Unique Games Conjecture is one of active research areas in complexity theory.

  What evidence do we have for it? What evidence do we have against it?


texts: Intuitive explanation behind Goemans-Williamson randomized rounding

texts:
A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more sophisticated: first, they do a semi-definite relaxation to obtain $n$ unit vectors $X_i$ (rather than the $n$ bits $x_i$ that the original integer program MAXCUT is supposed to solve for), and then each vector  $X_i$ is converted to a random bit by seeing what side of a random hyperplane
$g\sim N(0,I_n)$
 it falls on.

Intuitively, the new random variables $\mathrm{sign}(X_i\cdot g)$ are no longer independent -- unlike the naive randomized cut, where each vertex was chosen independently. I can see why creating dependencies might be beneficial: if a given vertex $i$ is chosen to be in the cut and has a large degree, then perhaps we might not want its neighbors to be in the cut. Is there an intuitive explanation behind the kind of dependencies that Goemans-Williamson rounding is creating between the vertices and why these are beneficial for obtaining larger cuts? [I understand the formal proof, which is relatively simple and very slick. Looking for intuition!]


texts: Complexity of weighted cycle in a hamiltonian graph

texts:
Assume a weighted graph G and a positive value k are given.

What is the complexity of finding a cycle with total weight k when G is Hamiltonian or Hamiltonian-connected?

pointing to papers and books is also welcome!
I wish it wouldn’t look as a homework!


texts:
Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \ $  different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a maximum flow problem. Does anyone
have a pointer for this ? Also any references to problems that can be reformulated, in not completely obvious ways, to maximum flow problems would be valued.


texts:
No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition:

A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a randomized Turing-machine $T$ that decides membership with error $\le \frac 13$ in time $f(n)$ [so far usual definition of $\mathsf{BPTIME}$] and it can be proved that $T$ accepts every $x$ with probability $\ge \frac 23$ or with probability $\le \frac 13$ [so there is a proof that $T$ satisfies the $\mathsf{BP}$ condition].

Note that this definition is completely different from that of $\mathsf{PromiseBPTIME}$.
For $\mathsf{ProvableBPTIME}$ there is a Time Hierarchy: On input $(T,\Psi,x)$, reject if $\Psi$ is not a proof that $T$ satisfies the $\mathsf{BP}$ condition, otherwise simulate $T$ on input $(T,\Psi,x)$ (until our running time permits), then negate the answer. Using standard tricks, hierarchy results can be established also about $\mathsf{RTIME}$ and similar classes.
This method almost gives a Time Hierarchy theorem for $\mathsf{BPTIME}$ as well, the only issue is that if there is a $T$ that satisfies the $\mathsf{BP}$ condition but this cannot be proved. (Think about fast primality tests using the Generalized Riemann Hypothesis.) In fact, I find the situation quite plausible that there are some fast algorithms whose correctness cannot be proved. If this is the case, it would be quite hard to diagonalize against them with an algorithm that must provably satisfy the $\mathsf{BP}$ condition.
So my questions would be:
1, Has $\mathsf{ProvableBPTIME}$ been defined before?
2, Are there known hierarchy theorems using some kind of provability?
3, Is there a way to take care somehow of the unprovably correct algorithms?
Related questions: Hierarchy for BPP vs derandomization, Is there a Quantum equivalent of the Time hierarchy theorem ?,
https://cs.stackexchange.com/questions/132936/does-promisebptime-have-a-time-hierarchy-theorem
Update 2020/12/24: Joshua pointed out that in Chapter 6 of Hartmanis: Feasible Computations and Provable Complexity Properties a similar definition was considered but only for the provability of the time/space bound $f(n)$ of deterministic classes. I would instead define $\mathsf{ProvableDTIME}[f(n)]$ as deterministic algorithms whose correctness can be proven. (Again think about primality tests using the GRH.) Then we can ask the following.

$\mathsf{DTIME}[f(n)]\neq\mathsf{ProvableDTIME}[f(n)]$ for some time-constructible function $f(n)$?
Could $\mathsf{P}$ and $\mathsf{ProvableP}$ differ?


texts: Are there any algorithms that are similar to Fagin's Algorithm, but for unranked lists?

texts:
Fagin's Algorithm is a popular algorithm for finding the top-$k$ items from multiple ranked lists of the items (i.e., via different scoring functions), using some monotonic aggregation function for the final list's scores.

I'm wondering if there has been any research into a similar algorithm for when the multiple lists have not been ranked yet.  My goal is to avoid scoring all the items before finding the top-$k$ in the final list. Approximations or some probabilistic approach would be fine; I'm just not finding the area of research to look into.

Example Data: given $N$ cars, assume there are several scoring functions representing someone's preferences: safetyPreference(), coolnessPreference(), etc., where these functions return a value from $1-5$, with higher being more preferred, and the aggregate preference being the sum across all preference functions.


texts: Proof of greedy method to compute minimum Prime Implicant of a monotone Boolean function

texts:
The decision version of Prime Implicant problem is NP-complete for Monotone Boolean function. I present below a greedy algorithm to find the minimum prime implicant ( minimum number of variables which upon setting $1$ will make the function to evaluate $1$) of a monotone Boolean function whose CNF representation is given to us.
Input:- A CNF $\phi(x_1, x_2, \ldots ,x_n)$  , Initialisation:- $S=\{ \}$ , Output:- Set $S$

Pick the variable $\{x_1, x_2, \ldots ,x_n\}$ which appears max number of times in $\phi$ breaking ties arbitrarily.
Set this variable $x_i$ to $1$ and include in set $S$ and remove all the clauses which are satisfied.
Continue this process until all the clauses are satisfied and output $S$

Observe that this algorithm need not be polynomial in $n$. We also need to argue its correctness. I cannot come up with a counterexample to disprove this or come up with a proof prove its correctness. This is how I am trying to prove.

Greedy choice must be part of an optimal solution

Suppose a set $S_{opt} \subseteq {\{x_1, x_2, \ldots ,x_k\}}$ be an optimal solution i.e. setting all these variables to $1$ satisfies all the clauses. Let $x_i$ appears max number of times. So if we remove some $x_j \in F$ and include $x_i$ then it should still be optimal i.e. setting all the variables in $S_{opt} \setminus \{x_j\} \cup \{x_i\}$ to $1$ should still satisfy all the clauses. But I can't prove this argument.
Can you help me either proving or disproving my greedy method?


texts: Shortest cycle with a specific number of vertices

texts:
Given an undirected graph with n nodes, I need to find the shortest cycle of involving exactly n/2 vertices (i.e. keeping the distance traveled by the cycle to a minimum). Some nodes cannot directly connect; they're in specific areas and I can only travel from one area to another, not within one area.

I'm just asking in general here, what kind of techniques can I use to get the best (shortest) possible cycle of n/2 nodes?  So far I've written a basic substitution optimizer and just a greedy Depth First Search.  I'm wondering what would be the best approach for me to start on now?


texts:
I'm currently looking into the representation theory of Scott domains. In his paper "dI-Domains as prime information systems" (1992), Guo-Qiang Zhang uses prime information systems to represent dI-domains. A prime information system is an information system where additionally we have linearity and finiteness of entailment, in the following sense:

$X \vdash b$ implies $\{a\} \vdash b$, for some $a \in X$, and
the deductive closures $\overline{X} = \{b \mid X \vdash b\}$ are finite.

If $A$ is a (prime) information system, write $Pt(A)$ for the points (also "elements", "ideals") of $A$, that is, for the usual consistent and deductively closed (possibly infinite) sets of tokens in $A$; for the finite ones write $Pt_f(A)$. Then, a stable approximable mapping between two prime information systems with carriers $A$ and $B$, according to Zhang, is a relation $r \subseteq Pt_f(A) \times B$, such that

if $(a_i,p_i) \in r$, for $i = 1, \ldots, m$ and $\bigcup_i a_i \in Con_A$, then $\{p_1, \ldots, p_m\} \in Con_B$,
if $a \cup b \in Pt_f(A)$, and $(a, p) \in r$, $(b, p) \in r$, then $a=b$, and
if $(a, p) \in r$ and $\{p\} \vdash_B q$, then $(b, q) \in r$, for some $b \subseteq a$.

Now in Definition 5.4 he writes:

  Let $A = (A, Con_A, \vdash_A)$ and $B = (B, Con_B, \vdash_B)$ be prime information systems. A molecule $m$ is a finite stable approximable mapping, such that for some $(a , p) \in m$, $b \subseteq a$ and $\{p\} \vdash q$, for any other $(b , q)$ in $m$.

He then uses molecules as tokens of an appropriate function space and goes on to show cartesian closure of the category of prime information systems with stable approximable mappings. My problem is that my intuition is too low to allow me to even parse the definition.

My questions: What is the defining formula of a molecule, and in particular, how are these $b$'s quantified? What would be your intuition of a molecule?


texts: Average height of the least common ancestor of 2 random nodes in a binary tree

texts:
We have a binary tree with height $h$, and for the sake of analysis assume it's a complete tree.

If we pick two nodes at random (with or without replacement, your choice), what is the expected height of the subtree rooted at the least common ancestor of those nodes?

I believe I've calculated the first few results, by exhaustive case analysis (for the situation of choosing a node at random with replacement, i.e. both nodes may be the same):

Tree height 1 (1 node), height of subtree: 1

Tree height 2 (3 nodes), height of subtree: 1.666... (5/3)

Tree height 3 (7 nodes), height of subtree: 2.551... (125/49)

What is the actual formula?


texts: Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

texts:
This is another attempt to formalize my former question on the topic.

I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (think around 53), we can achieve a speed-up that is exponential in their number.
So if the problem requires time $2^n$ on a classic computer, then I would hope for a hybrid quantum-classical algorithm that uses $q$ qubits and takes $2^{n-q^c}$ time for some constant $c$.
Here $c$ is independent of $q$, which can be any number, up to $n^{1/c}$ or so by when the problem becomes polynomial on the quantum computer.
Are there such problems?


texts: Secure multiparty computation of number of 1s times number of 0s in a shared string

texts:
Suppose there are $N>2$ parties $p_j$, each with a bit $b_j\in{\{0,1\}}$. I want to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b_j})\times(N-\sum{b_j})$.

The computation should be secure in the sense that no party can learn more than the final result $R$. For example, it's not ok to perform secure sum, because then $\sum{b_j}$ will become known, and the sum is sensitive in my problem. So, is there any existing secure computation protocol that fits the demand?

Edit: The number $N$ in the problem is large, at least over $1000$. So efficient secure multiparty computation is needed. A secure sum protocol could be efficient but generic  SMC like boolean circuits might be too computation intensive. So I need an efficient protocol.


texts:
In my academic career, I've read quite a few academic papers on various computer science topics.  Many of which involve an implementation and some assessment of that implementation, yet I have found that very few of them actually publish the code they used.

To me, the benefits of including the actual implementation would be significant, namely:

Extension of trust or reproducability (just test it yourself!)
Clarification of ambiguities (particularly for papers written by non-native speakers)
Reuse of code for applications

So why is it that so few papers actually include any code?

I suppose that it might be the intention of the organization behind the paper to utilize the implementation in their own applications, and thus would not want to release it, but if that's the case, why even write the paper?


texts: On $n$ dimensional manifolds and lattices

texts:
EDIT (By Tara B):  I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper.

I'm looking for the proof of Theorem 4 that appears in this paper:

An Infinite Hierarchy of Intersections of Context-Free Languages by Liu and Weiner.

  Theorem 4: An $n$-dimensional affine manifold is not expressible as a finite union of affine manifolds each of which is of dimension $n-1$ or less.

Does anyone knows a reference to the proof?
If the manifold is finite and we define a natural order on the elements, is there any similar statement in terms of lattices?

Some background to understand the theorem:

Definition: Let $\mathbb{Q}$ be the set of rational numbers. A subset $M\subseteq \mathbb{Q}^n$ is an affine manifold if $(\lambda x+(1-\lambda)y)\in M$ when $x\in M$, $y\in M$, and $\lambda\in\mathbb{Q}$.

Definition: An affine manifold $M'$ is said to be parallel to an affine manifold $M$ if $M'=M+a$ for some $a\in \mathbb{Q}^n$.

Theorem: Each non-empty affine manifold $M\subseteq \mathbb{Q}^n$ is parallel to a unique subspace $K$. This $K$ is given by $K=\{x-y:x,y\in M\}$

Definition: The dimension of a non-empty affine manifold is the dimension of the subspace parallel to it.


texts:
What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?

UPD:
$O^*(\cdot)$ suppresses polynomial factors.

The shortest superstring problem is a problem whose answer is the shortest string which contains each string from a given set of strings.
The question is about optimization extension of a famous NP-hard problem Shortest Superstring(Garey and Johnson, p.228).


texts:
Consider the linear program:

$$
    A x = b, ~~~~~~ x\geq 0
$$
where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$.

It is known that, if this program has a solution, then it has a basic feasible solution, in which at most $m$ variables are non-zero.

QUESTION: is there an efficient algorithm to decide whether the LP has a solution in which at most $m-1$ variables are non-zero, and find it if it exists?

The question is a special case of Min-RVLS - finding a solution with a smallest number of non-zero variables. Min-RVLS is known to be NP-hard and hard to approximate within a multiplicative factor. Finding an additive approximation is hard too.

But, here our goal is much more modest - all we want is to find a solution with one less than the maximum ($m$). Is this special case easier?

This question was previously posted in cs.SE and got no answers. I deleted it from there to avoid cross-posting.


texts:
I am currently a high school student, interested in theoretical computer science and applied mathematics. I have self taught myself linear algebra and calculus and concrete mathematics. I have a naive notion that for one to write better algorithms, one must know as much mathematics as one can because you can learn about new structures and then use those structures to form more complex and faster algorithms, now, I am not understanding what to do next. I have still an year to go to college, and in that time, I would like study some mathematics that may help me in my career. What should I start with ? Can someone please provide me with probably a list of topics that I should study now and in future.

Also are things like abstract algebra (it is too formal of a subject) and algebraic topology useful in computer science?


texts: How can I model this usage scenario mathematically?

texts:
I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system.

The system behaves as follows:

clients periodically issue multi-cast packets to a network of hosts
any host that receives the packet, responds with a unicast answer directly
the initiating host caches the responses for some given time period, then discards them
if the cache is full the next time a request is required, data is pulled from the cache not the network
packets are of a fixed size and always contain the same information
hosts are symmetic - any host can issue a request and respond to requests

I want to produce some simple mathematical models (and plotted X/Y graphs) that describe the trade-offs available given some changes to the above system:

What happens where you vary the amount of time a host caches responses? How much data does this save? How many calls to the network do you avoid? (clearly depends on activity)
Suppose responses are also multi-cast, and any host that overhears another client's request can cache all the responses it hears - thereby saving itself potentially making a network request - how would this affect the overall state of the system?
Now, this one gets a bit more complicated - each request-response cycle alters the state of one other host in the network, so the more activity the quicker caches become invalid. How do I model the trade off between the number of hosts, the rate of activity, the "dirtyness" of the caches (assuming hosts listen in to other's responses) and how this changes with cache validity period? Not sure where to begin.

I don't really know what sort of mathematical model I need, or how I construct it. Clearly it's easier to just vary two parameters, but particularly with the last one, I've got maybe four variables changing that I want to explore.

Help and advice appreciated.


texts: Path of exact cost in edge labelled DAG?

texts:
Given edge labelled directed acyclic graph with edge labels $w_i \in \mathbb{N}$ the cost of a path is the sum of the labels.

The problem is:

  Find a path from $s$ to $t$ with cost $a$.

I suppose this is NP-hard.

Some questions:

Would putting a bound $\max w_i < C$ make the problem easier?
What are the best algorithms for this?
Is the problem NP-complete?

Update
What about this modification of Number: 63 Shortest Weight-Constrained Path

To each edge associate second label weight $r_i \in \mathbb{N}$. The weight of a path is the sum of $r_i$.

Assume (possibly small) bound $C$ of the costs $w_i$ and solve:

$cost = a$ and $weight < K$.

Would it be still polynomial in $n,m,C$ or NP-hard instances exist (one can assume positive labels if this helps)?


texts: Hashing sets of integers for inclusion testing

texts:
I'm looking for a hash function over sets H(.) and a relation R(.,.) such that if A is included in B then R(H(A), H(B)). Of course, R(.,.) must be easy to verify (constant time), and H(A) should be computed in linear time.

One example of H and R is:

$H(A) = \bigvee_{x\in A}  1 << (h(x) \mod k)$, where k is a fixed integer and h(x) a hash function over integers.
R(H(A), H(B)) = ((H(A) & H(B)) == H(A))

Are there any other good examples? (good is hard to define but intuitively if R(H(A), H(B)) then whp A is included in B).

Later edit:

I'm looking for a family of hash functions. I have many sets; 3 - 8 elements in each set; 90% of them have 3 or 4 elements. The example hash function I gave is not very well distributed for this case.
The number of bits of H(.) (in my example, k) which should be small (ie. H(.) must fit in an integer or long).
One nice property of R is that if H(.) has k bits then R(.,.) is true for (3^k - 2^k) / 4^k pairs, ie. for very few pairs.
Bloom filters are especially good for large sets. I tried using BF for this problem, but the optimum results were with only one function.

(crosspost from stackoverflow, I didn't receive an answer good enough)


texts: Complexity of computing the order of a permutation group

texts: Given two permutations $g$ and $h$ over $n$ elements (i.e., members of $S_n$), what is the complexity of computing the order of the subgroup generated by $g,h$? Or just of deciding whether the subgroup is of order $n!$ (i.e., all of $S_n$)?


texts: Papers to credit for spectral partitioning of graphs

texts:
If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Where $Edges(A,B)$ is the number of edges with one endpoint in $A$ and one endpoint in $B$. Then the Edge Expansion problem is to find a set $S$ with $|S|\leq |V|/2$ that minimizes $\phi(S)$. Call $\phi(G)$ the expansion of an optimal set.

The Spectral Partitioning Algorithm for the Edge Expansion problem works by finding an eigenvector $x$ of the second largest eigenvalue of $A$, the adjacency matrix of $G$, and then considering all the ``threshold sets'' $S$ of the form $\{ v : x(v) \leq t \}$ over all thresholds $t$. If we let $\lambda_2$ be the second largest eigenvalue of the  matrix $\frac 1d \cdot A$, then the analysis of the Spectral Partitioning Algorithm shows that the best threshold set $S_{SP}$ found by the algorithm satisfies

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

Which follows from the Cheeger's Inequalities

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

and

$1-\lambda_2 \leq 2 \phi(G)$

What is the first paper to make such a claim? What papers are to credit for the ideas? Here is what I have got:

N. Alon and V.D. Milman. $\lambda_1$, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory, Series B, 1985, 38(1):73-88

Prove a result in the spirit of the "simple" Cheeger inequality $1-\lambda_2 \leq 2\phi(G)$, but for vertex expansion instead of edge expansion. Recognize that the relation between edge expansion and eigenvalues is the discrete version of a problem studied by Cheeger in

J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis, 1970.

N. Alon. Eigenvalues and expanders. Combinatorica. 6(2):83-96, 1986.

Proves a result in the spirit of the difficult Cheeger inequality $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$ but for vertex expansion instead of edge expansion.

A. Sinclair, M. Jerrum. Approximate counting, uniform generation, and rapidly mixing Markov chains. Information and Computation 82:93-133, 1989 (Conference version 1987)

Prove the Cheeger inequalities as stated above. (Their paper studies _conductance_ of time-reversible Markov chains, which happens to equal _edge expansion_ in regular graphs.) They credit the work of Alon and Milman and of Alon for the techniques. They also credit Aldous for a related bound between mixing time and edge expansion in regular graphs.

M Mihail. Conductance and convergence of Markov chains-a combinatorial treatment of expanders. FOCS 1989, pages 526-531

While the main point of the paper is that its techniques apply to non-time-reversible Markov chains, when it is applied to regular undirected graphs it has an advantage over previous work: it shows that if one runs the spectral partitionig algorithm with an arbitrary vector, one still obtains the inequality $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$ where $\lambda'$ is the Rayleigh quotient of the vector. The arguments of Alon, Milman, Sinclair and Jerrum require an actual eigenvector. This is relevant to fast spectral partitioning algorithms that use approximate eigenvectors.

Are there other papers that should be credited in terms of proof techniques?

When is the algorithmic significance of the above results, as graph partitioning algorithms, first recognized? The above papers have no such discussion.


texts: References on model checking and pi calculi

texts:
I'm a mathematician and it looks like I need to learn about these topics. What would be good references that go into the technical details of the following topics?

(s)pi calculus

model checking

I'm not really interested in applying these tools, but in their actual mathematical constructions, since it looks like they might contain ideas that I'm looking for.


texts: Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?

texts:
I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function.

Is there any modification of gradient descent which allows to find absolute minimum (maximum), where function has several local extrema?

Are there any general techniques, how to enhance an algorithm which can find local extremum, for finding absolute extremum?


texts:
I am curious to know when open problems have been solved by expressing them in a specific logic, and then showing that this logic is decidable.

I have two distinct cases in mind:

The problem is about decidability of something, and it can be reformulated in a decidable logic.
The conjecture is just a yes/no property about some mathematical object, like twin-prime conjecture. Turn it into a decidable logical sentence, and run the algorithm to know the answer.

In both cases, it would be interesting if the logic is created and shown decidable just to fit the problem.


texts: What is known about the H-factor problem?

texts:
Background
The $\mathcal{H}$-factor problem (a.k.a. the degree prescribed factor problem, or the degree prescribed subgraph problem) is defined as follows:
Given a graph $G=(V,E)$ and a set $H_v \subseteq \mathbb{N}$ for each vertex $v \in V$, does $G$ contain a spanning subgraph $F$ such that $\operatorname{deg}_F(v) \in H_v$ for all $v \in V$?
(I would also say that $H_v \in \mathcal{H}$ for all $v \in V$, but I have never seen it stated this way. Thus, the $\mathcal{H}$-factor problem is defined by $\mathcal{H}$ and the input is a graph $G=(V,E)$ and a mapping $f : V \to \mathcal{H}; v \mapsto H_v$.)
A spanning subgraph is also known as a factor, hence the name. This framework of problems captures many classic problems. For example, when $H_v = \{1\}$ for all $v \in V$, the problem is to determine if $G$ contains a perfect matching, also called a 1-factor.
Question
What is currently known about the complexity of this problem for different $\mathcal{H}$?
What about the special case when $\mathcal{H}$ is a singleton set (so $H_v$ is the same for all $v \in V$)?
Strongest Results I Know
Tractability:
If each set in $\mathcal{H}$ does not contain two consecutive gaps, then the $\mathcal{H}$-factor problem is in P (Cornuejols 1988). A integer $h$ is a gap in $H \subseteq \mathbb{N}$ if $h \not\in H$ but $H$ contains an element less than $h$ and an element greater than $h$.
Hardness: There exist some $\mathcal{H}$ such that the $\mathcal{H}$-factor problem is NP-hard (Lovasz 1972).
See (Szabo 2004) for a modern reference that cites these two results.


texts:
Being a professional software engineer, i have seen a lot of really interesting technical work, many of it is published as technical articles in technical journals and websites like http://www.drdobbs.com and http://www.codeproject.com and many others, here is a few examples in some areas of interest:

Algorithm engineering and implementation:

http://www.codeproject.com/Articles/18113/KD-Tree-Searching-in-N-dimensions-Part-I
http://www.codeproject.com/Articles/9021/Simple-and-fast-Huffman-coding
http://www.drdobbs.com/cpp/sorting-an-immutable-list/240163397
http://www.codeproject.com/Articles/33781/Calculate-Percentiles-in-O-1-space-and-O-n-time

Data structures:

http://www.codeproject.com/Articles/43103/SlimList
http://www.codeproject.com/Articles/2839/C-AVL-Tree-Template
http://www.codeproject.com/Articles/9138/Fast-Binary-Tree-Operations
http://www.codeproject.com/Articles/23198/C-String-Toolkit-StrTk-Tokenizer
http://www.codeproject.com/Articles/11274/Implementing-a-memory-efficient-search-tree-for-a

Text search:

http://www.codeproject.com/Articles/198236/Boolean-text-search-queries-and-their-processing
http://www.codeproject.com/Articles/20423/N-gram-and-Fast-Pattern-Extraction-Algorithm

Object oriented and generic programming:

http://www.codeproject.com/Articles/16006/Dynamic-Inheritance
http://www.codeproject.com/Articles/19444/Interface-Detection
http://www.codeproject.com/Articles/20085/Superior-container-classes-Smaller-faster-flexible
http://www.drdobbs.com/cpp/theory-versus-practice-the-great-divide/240160938

Database optimization:

http://www.codeproject.com/Articles/25728/Database-Virtual-Cursor

Real time processing:

http://www.codeproject.com/Articles/224733/Shared-Queue

This level of work is considered highly innovative from the technical/engineering point of view.

I wonder if any technical work can be considered an academic achievement and can be deployed in research papers as well as technical articles.

In other words:
When can a technical article be published as a research paper, in which areas? any examples?

Thanks


texts: Are there published algorithms for on-line creation of AVL trees from ordered streams?

texts:
Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time.  More specifically this is possible using only O(log n) additional storage, and only O(log n)-time after then end-of-stream is discovered.  The technique involves pennants and the 1-2 binary representation of n.

The technique needs to be modified for AVL trees, and I haven't seen referneces to an on-line algorithm for creating AVL trees.  Does anyone know of such a published algorithm?


texts: Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices

texts:
Suppose we have a multigraph with vertex set $V$ where for each $v \in V$, $d_v > 0$ is the diameter of the vertex. We want to put a linear ordering on the set of vertices such it minimizes ($L_1$ or $L_2$ norm of) the sum of edge length when vertices are drawn on a line (according to that linear ordering). The vertices are non overlapping circles with diameter $d_v$ and each edge can start anywhere in the respective circles as long as it is confined to the boundary of the given circles and all the other edges start at the same position.

A physical interpretation of this would be that there are N balls connected with ropes (the rope can start anywhere inside the ball but every rope connected to that same ball must start from the same place too) We want to place the balls on a line such that the total length of the ropes used in minimized.

Is there any efficient algorithm known for this type of problem? How about approximation algorithms?


texts: How to succeed in remote TCS research as undergraduate

texts:
I am participating in a remote summer research program in theoretical computer science due to the current pandemic. I recognize that given the current situation, it may be harder to collaborate with my advisor. Additionally, another benefit of these programs is the social interactions with other undergraduates doing similar research, but this will clearly be hard to recreate, if at all.

Given these limitations, what advice do you have to be successful during the summer research program? Anything from work habits to preparations and tools for weekly meetings would be helpful. Any other tips or advice would be very helpful, too.


texts: Are deterministic context-free languages closed under outfix (or other erasing operations)

texts:
Define the outfix of a language $L$ to be
$Outf(L) = \{xy \mid \exists z. xzy \in L \}$.

Are any known results about whether deterministic context-free languages are closed under this operation, or other similar "erasing" operations?

My preliminary search has not turned up anything, but I thought someone who had knowledge of the area might know of a reference.


texts: Complexity of a certain leaf language with Prime & Composite number of accepting paths.

texts:
Given a non-deterministic Turing Machine that runs in polynomial time, it accepts if the number of accepting paths are composite, it rejects if the number of accepting paths are prime and it outputs I do not know if the number of accepting paths are {0,1}.

Lets call the Above language CA-PR (Composite Accept - Prime Reject).

Then we have co-CA-PR = PA-CR(Prime accept, composite reject).

Both of the above languages output DON'T KNOW when the number of accepting paths are {0,1}.

Questions:

Do CA-PR & PA-CR not contain UP?
A #P Oracle can definitely solve these problems, can a PP oracle too? How about a ParityOracle?
What can we say about the intersection and union of these languages?
Where can we place this complexity class? Is it in the polynomial hierarchy?


texts: Locally-nameless representation: normal order & opening with a bound variable

texts:
This question concerns the representation used in Arthur Charguéraud's paper “The locally nameless representation” and is somehow a follow-up on this question, where it is asked about the normalization of terms under a binder, at the example of the following term (for technical reasons, I use one based indices):

$$\lambda((\lambda\lambda(2 \; 1)) \; 1)$$

Beta-reductions in this representations supposedly (and contrary to the answer to the linked question) are done without need of introducing fresh variable names, because we can replace a variable opening + substitution combination

$$((\lambda \; t ) \; u)  \longrightarrow_\beta [x \mapsto u] \; t^{x} \qquad (x \text{ fresh in } t)$$

by simple “term” opening

$$((\lambda \; t ) \; u)  \longrightarrow_\beta t^{u},$$

where $t^{u} = \mathtt{open}(1, u, t)$ (see p. 10 in the paper).  open can be implemented as follows, trying to exactly follow the definition there and Charguérot's reference implementation in Coq:

open k u (Bvar i)    = if k == i then u else (Bvar i)
open k u (Fvar x)    = Fvar x
open k u (Abs t1)    = Abs (open (k + 1) u t1)
open k u (App t1 t2) = App (open k u t1) (open k u t2)

Now, reducing the example term in (what I think is) normal order will result in the following steps:

\begin{align*}
\mathtt{reduce}\; \lambda((\lambda\lambda(2 \; 1)) \; 1) &= \lambda(\mathtt{reduce} \; ((\lambda\lambda(2 \; 1)) \; 1)) \\
&= \lambda(\mathtt{open} \; 1 \; 1 \; (\lambda(2 \; 1))) \\
&= \lambda( \lambda (\mathtt{open} \; 2 \; 1 \; (2 \; 1))) \\
&= \lambda( \lambda ((\mathtt{open} \; 2 \; 1 \; 2) \; (\mathtt{open} \; 2 \; 1 \; 1))) \\
&= \lambda \lambda (1 \; 1)
\end{align*}

This is, however, the wrong result -- the answer should have been $\lambda \lambda (2 \; 1)$ (essentially, just eta converting the term).  The problem lies in the second-last line, where the bound $1$ from outside  replaces the inner $2$ without being properly changed.

Appearently, open in this form is not made for normal order, due to the fact that unlike evaluation in de Bruijn representation, the substituted term is not shifted.  In fact, I found the following comment on top of Charguéraud's implementation of open (called open_rec there):

  We make several simplifying assumptions in defining [open_rec]. First,
  we assume that the argument [u] is locally closed.  This assumption
  simplifies the implementation since we do not need to shift indices in
  [u] when passing under a binder.  Second, we assume that this function
  is initially called with index zero and that zero is the only unbound
  index in the term.  This eliminates the need to possibly subtract one
  in the case of indices.

Of course, the assumption of local closedness holds only when we do something like call-by-name, where terms under binders are not reduced.  My solution was to change open to the following open', which “inlines” shifting of bound variables when they are inserted (which can be done easily, since we keep track of the number of binders anyway with k):

open' k (Bvar j) (Bvar i) = if k == i then (Bvar j + k - 1) else (Bvar i)
open' k u (Bvar i)    = if k == i then u else (Bvar i)
open' k u (Fvar x)    = Fvar x
open' k u (Abs t1)    = Abs (open' (k + 1) u t1)
open' k u (App t1 t2) = App (open' k u t1) (open' k u t2)

The questions I have are:

Is my reasoning correct?
Does open' correctly fix the problem when the assumptions do not hold (ie, when used in normal order reduction)?
Does open' preserve the properties and correctness of open when the original assumptions hold?


texts: Bipartite graph projections, with threshold

texts:
Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked together if they have a common neighbor in $G$.
Weighted projections are defined by adding the following weight function: $\omega(u,v)$ is the number of common neighbors of $u$ and $v$ in $G$.
For any $k$, the $k$-projections $G^k_\bot = (\bot,E^k_\bot)$ and $G^k_\top = (\top,E^k_\top)$ are defined as follows: two vertices are linked together if they have at least $k$ common neighbors in $G$.
Assume that both $G$, $G_{\bot}$, and $G_{\top}$ are sparse.
Questions:

What is the (time and space) complexity of building $G_\bot$ and $G_\top$?
Is it possible to build their weighted version with same complexity?
Is there a significantly better way to build $G^k_\bot$ and $G^k_\top$ than first building weighted $G_\bot$ and $G_\top$ and then removing the edges of weight lower than $k$?

These questions are important in social network analysis and related fields. For instance, many studies consider co-authorship networks: $G$ is graph where authors are linked to papers, and $G^k_{\bot}$ is the graph of authors who co-signed at least $k$ papers.


texts: Refinements of pair approximation for network analysis

texts:
When considering interactions on networks, it is usually very hard to calculate the dynamics analytically, and approximations are employed. Mean-field approximations usually end up ignoring the network structure completely, and so are seldom a good approximation. A popular approximation is the pair approximation, which considers the correlations inherent between adjacent nodes (intuitively we can think of it as a type of mean-field approximation on edges).
The approximation is exact if we are considering Cayley graphs, and very good if we are looking at $k$-regular random graphs. In practice it also provides good approximations for cases when we have a random graph with average degree $k$ and a tight distribution of degree around $k$. Unfortunately, a lot of the networks and interactions that are of interest, are not well modeled by these sort of graphs. They are usually well-modeled by graphs with very different degree distributions (like scale-free networks, for instance), with specific (and high) clustering coefficients, or specific average shortest-path distance (for more, see Albert & Barabasi 2001).
Are there refinements of pair approximation that work well for these types of networks? Or are there other analytic approximations available?

An example of interactions on networks
I thought I would give an example of what I mean by interactions on networks. I will include a relatively general example from evolutionary game theory.
You can think of each node as an agent (usually represented just by a strategy), that plays some fixed game pairwise with each other agent it has an edge to. Thus, a given network with a some assignment of strategy to each node produces a payoff for each node. We then use these payoffs and the network structure to determine the distribution of strategies among the nodes for the next iteration (A common example might be for each agent to copy the neighbor with the highest payoff, or some probabilistic variant of this). The questions we are usually interested in corresponding to knowing the numbers of agents of each strategy and how that changes overtime. Often we have stable distribution (which we then want to know, or approximate) or sometimes limit-cycles or even more exotic beasts.
If we do mean-field approximation on this sort of model, we use get the replicator equation as our dynamic, which blatantly ignores the network structure and is only accurate for complete graphs. If we use pair approximation (as Ohtsuki & Nowak 2006) we will get slightly different dynamics (it will actually be replicator dynamics with a modified payoff matrix, where the modification depends on the degree of the graph, and the specifics of the update step) which matches simulation well for random graphs, but not for other networks of interest.
For a more physics like example: replace the agents by spins and the call the payoff matrix an interaction Hamiltonian, then cool your system while performing periodic random measurements.
Notes and related questions

Straightforward generalizations of pair approximation of the sort that consider a type of mean-field approximation on triples, or quadruples of nodes) are unwieldy and still don't take into account very different degree distributions or average shortest-path distance.

Sources for Algorithmic Evolutionary Game Theory


texts: Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?

texts:
There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points.

Let $D$ be the distance matrix between all pairs of points, such that entry $D_{ij}$ corresponds to the distance between points $i$ and $j$. This matrix is of size $n \times n$ and the upper-triangle contains the distances between unique pairings of points.

Now imagine I put the elements from the upper triangle into a set, such that you no longer know which pairs of points produce the distance values. This is essentially the set of edge weights, with no information regarding the relationship between the weight and the edge the weight belongs to.

If you are given two sets and they are identical, does this imply the graphs corresponding to each set are also essentially the same?


texts: Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic

texts:
In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ its state set, $E \subseteq Q\times A \times Q$ the transitions and $A$ its alphabet. It is called deterministic if for every $q \in Q$, $a \in A$ there is at most one state $q' \in Q$ such that $(q, a, q') \in E$ and $|I| = 1$. And it is called complete if there exists at least one $q' \in Q$ such that $(q,a,q') \in E$. Then on page 21 (section 7.1) the following further definitions are made:

A path is called initial if its first state is in $I$, a state is called accessible if there exists a initial path to it, and it is called co-accessible if there exists a final path starting at this state. An automaton is called trim if every state is accessible and co-accesible. The above notion of determinism is called local determinism, and a global notion is defined as $|I| = 1$ and if every word is the label of at most one initial path. Similarly a trim automaton is globally co-deterministic if every word is the label of at most one final path. And it is called locally co-deterministic if all transitions are co-deterministic, which means that we have no two transitions starting in different states, with the same letter that lead to a common state.
Then they write:

  The local and global notions of co-determinism [...] are equivalent for finite words [page 23]

But what about for example the automaton with three states $q_0, q_1, q_2$, where $q_0$ is initial, $q_1$ and $q_2$ are both final and transitions
\begin{align*}
 q_0 & \quad \mathrel{\mathop{\rightarrow}^{a}} \quad q_1 \\
 q_0 & \quad \mathrel{\mathop{\rightarrow}^{a}} \quad q_2.
\end{align*}
This is not deterministic surely, but it is trim, it is locally co-deterministic but it is not globally co-deterministic as $a$ is the label of two final paths?

  So do I interpret these notions wrongly? Why are the global and local notions of co-determinism equivalent for finite words, i.e. an automaton is locally co-deterministic if and only if it is globally co-deterministic on finite words?

I see that for the notions of determinism both variants are equivalent (for finite and for infinite words), but for this equivalence it is crucial that determinism also requires exactly one initial state, but in general we have more than one final state.


texts: Given $m, n, k$, how many of $k$-DNFs with $n$ variables and $m$ clauses are tautology? (or how many $k$-CNFs are unsatisfiable?)


texts: Evaluation contexts: outside-in vs inside-out

texts: I heard that there exist two styles to define an evaluation context: outside-in and inside-out.  Can someone give the definitions?  Why are they so named (inside-out and outside-in)?  What is the difference?  Some examples would be appreciated.


texts: Translating pure literal elimination into rup

texts:
I'm exploring building a CDCL SAT-solver with interesting reduction rules. I have two rules based on pure literal elimination, but if either of these rules generate a conflict, I don't know what to report for an RUP (reverse unit propagation) proof.
The first is pure-literal elimination over "base" clauses. That is, if a literal shows up with only one sign among the original clauses (but can still have the opposite sign in learnt clauses), then we set it.
The second is "would-be" pure-literal elimination binary clauses. If, among base (not learnt) clauses, literal A dominates literal B (but does not dominate -B) in the sense that every remaining unsatisfied rule containing B also contains A, then temporarily (while searching this branch) add the rule -A \/ -B since by setting A we would infer -B via pure literal elimination.
For both of these operations, it's easy to show that if a solution exists, then a solution still exists after applying the operation. But these rules can't be inferred via RUP and so it's unclear what to do in terms of providing a proof when they show up in a conflict.


texts: Post Correspondence Problem "binary" variant

texts:
Bounded Post Correspondence Problem is defined as follows:
given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k}$. It is obviously NP-complete.

Consider another constraint: the indexes has to be unique, which each pair may appear at most once in the concatenation.
I have constructed simple reduction from 3-PARTITION. The 3-PARTITION instance is given by number $B$ and list $A=(a_1, \ldots ,a_{3m})$ of $3m$ integers. The problem is to find 3-element disjoint subsets $S_1, \ldots, S_m$ such, that the sum of the numbers in each subset is equal $B$.

The reduction to 3-PARTITION is to construct following pairs:

$(0,0\{\#^{B}1\}^{m} )$
$m$ pairs of form: $(1,2)$
$( \# ^{a_i},* ) $ for each $a_{i} \in  A$
$(\{ *** 2\}^{m} 0,0)$

So the numbers from A are coded in unary form. We may do so, since 3-PARTITION is NP-complete in the strong sense.

It is supposed to work as follows: first the (1) block is used. Then for some subset $S_l=(a_i,a_j,a_k)$ the corresponding (3) blocks are added and the separator block (2) next. After all subsets are used, the ending (4) block has to be added.

Suppose now, that the index sequence is found. Using it we can construct solution of the 3-PARTITION since the pairs corresponding to element of A must form 3-element groups and all of them must be used to 'fill' the (1) block.

Is there any simple connection between the standard and the modified PCP?
Is there any simple reduction from the modified to the standard problem?
Can we say that the modified version is in some sense a special case of the standard problem?


texts: Constructing a k-perfect permutations family

texts:
I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, there exists a permutation $P \in\mathcal{P}, $ such that $P(x_1)<P(x_2)<...<P(x_k)$.

A simple probabilistic argument can show that such family of size $r=k!\cdot k\cdot log(n)+1$ exists:

Suppose we draw $r$ random permutations.
The chance that some specific $<x_1,...,x_k>$ is not ordered by non of the permutations is $(1-\frac{1}{k!})^r$.

Using the union bound, the chance that any ordered k tuple will not be ordered is bounded by:

$(1-\frac{1}{k!})^r\cdot$$ n\choose k$$\cdot k!<(1-\frac{1}{k!})^r\cdot n^k < n^k\cdot e^{-r/k!}$

If we demand that the probability will be less than 1 (which ensures such family exists), we get the desired size, $r>k!\cdot k\cdot log(n)$.

The question is:

Is there an explicit build for such family? is it computable in $O(k!\cdot poly(n))$ time?

This question might have been referred to somewhere in a different name, so if anyone is familiar with it, a reference will be great.

Edit: Andreas gave a nice build for parametric $k$.

What about the case that $k$ is a small, fixed number?

If $k=2$, then it's easy: take $\mathcal{P}=\{<1,2,...,n>,<n,n-1,...,1>\}$.

Can we build $O(1)$ sized 3-perfect permutation family? higher fixed $k$?


texts: How to solve such a graph optimization problem?

texts:
I have a graph optimization problem which is hard to describe in the title.

There is a component based system which consists of components and data transmissions between components(components and data transmissions will be represented by BC for short). The system has only one entry and one exit which means the system will always execute from the start component to the end component. Suppose the system only has sequence and concurrence structures. In sequence structure, the components execute one by one. In concurrence structure, components in different branches execute at the same time.

Each component and data transmission has a response time $a_i$. Now I have $k$ resources. Each resource can only be allocated to one BC. If a BC has a resource, its response time will drop from $a_i$ to $b_i$. I can calculate the response time of the system because response time in sequence structure can be added up and it will be the max in concurrence structures. So I can get the system response time if I know all the BC's response time.

Now I need to know what is the best resource allocation strategy to make the system response time minimum?

The system can be represented as a graph $S$ which has $n$ nodes and edges(BC for short). The nodes represent components and the edges represent data transmissions. The graph has only one entry and one exit and all the edges are in one direction. $S=\{BC_1,BC_2,\ldots, BC_n\}$. $BC_i$ has two values $a_i, b_i$. $a_i$ means the normal response time. $b_i$ means the response time when allocated a resource.

I have a function to calculate the response time of any graph $G$ which time complexity is $O(n)$ (n is the number of edges and nodes it contains). A naive method is choose the best from $\binom nk$ different allocations. So the time complexity is $O(n \cdot \binom nk)$.

Now I think I can use dynamic programming to solve this problem. My idea is to treat a complex structure as a node then some intermediate results can be cached. I have some images to describe my idea. For example, the graph $S$ can be represented as $N_1,E_A,N_A,E_B,N_3$. The best allocation must come from the 11 different allocations. I can cache the result of allocating $0,1,2$ resource to $N_A$ to avoid repetitive computation. If not, $F(N_A, 0)$ will be calculated 6 times by simply enumerating.

I think my solution's time complexity is better than $n \cdot \binom nk$. However I don't know how to prove it. Intuitively I think my solution is solvable in polynomial time.


texts: Tarjan Strongly Connected Components Question

texts:
Below is Tarjan's SCC algorithm as described in wikipedia.

Input: Graph G = (V, E)

1.  index = 0                                         // DFS node number counter
2.  S = empty                                         // An empty stack of nodes
3.  for all v in V do
4.   if (v.index is undefined)                       // Start a DFS at each node
5.     tarjan(v)                                     // we haven't visited yet

6.  procedure tarjan(v)
7.   v.index = index                                 // Set the depth index for v
8.   v.lowlink = index
9.   index = index + 1
10.  S.push(v)                                       // Push v on the stack
11.  for all (v, v') in E do                         // Consider successors of v
12.    if (v'.index is undefined)                    // Was successor v' visited?
13.        tarjan(v')                                // Recurse
14.        v.lowlink = min(v.lowlink, v'.lowlink)
15.    else if (v' is in S)                          // Was successor v' in stack S?
16.        v.lowlink = min(v.lowlink, v'.index)      // v' is in stack but it isn't in the dfs tree
17.  if (v.lowlink == v.index)                       // Is v the root of an SCC?
18.    print "SCC:"
19.    repeat
20.      v' = S.pop
21.      print v'
22.    until (v' == v)

In line 16, I could not determine why I could or could not replace line 16 with that of line 14. In other words, it seems to me that taking the min(v.lowlink, v'.lowlink) is the proper approach as opposed to min(v.lowlink, v'.index) in the above example. I have seen one other example on the web that mimics the pseudocode above.

I have considered the unusual use of stack S in the algorithm above in which S may contain items from previous "dead" stack frames. These leftover items aren't removed because they are not the roots of their own strongly connected component.


texts: How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming?

texts: Edges are given in form of $X_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.


texts: NP completeness of linear $0-1$ assignment problem

texts:
Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each.

Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables each.

Make another partition $\Pi_2$ the following way. Pick $1$ variable in every disjoint set of variables in $\Pi_1$ form a new subset of variable of size $n$.  Pick $1$ variable in every disjoint set of variables in $\Pi_1$ not picked before to form a new subset of variable of size $n$. So we have another disjoint partition into $n$ disjoint sets of $n$ variables each.

(1a) Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set?

(1b) Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment that satisfies exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set $\Pi_1$ AND with exactly $1$ assignment per disjoint set $\Pi_2$?

Does subset sum reduce to both of these?

What is a good reduction from any $\mathsf{NP}$-complete problem?

It seems to me that the problem (1a) and (1b) qualify as some restricted version of $n$-sum problems. This seems to imply problem is $\mathsf{NP}$-complete. That is it is likely that some special case of $n$-sum reduces to these problems. Since $n$ is a function of number of variables $n^2$ are these problems $\mathsf{NP}$-complete?

What if we add the promise that any satisfying assignment will have exactly $n$ $1$s?

(2) Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ (without regard to partition)?

has a trivial reduction as shown by Michael Wehar.

A guess that we can think of (1a) as following:

Consider problem:

(3) Given $n^2$ integers is there a way to partition the integers into disjoint subsets of size $n$ such that at least one of the subsets sum to $0$?

This problem sounds much similar to problem in definition $2$ in section $1.2$ here http://dreamboxx.com/mark/data/njc08.pdf.

May be we can show (3) is $\mathsf{NP}$-complete and find a way to reduce (1a) to (3)?


texts:
I was going over this paper and I don't understand a certain proof (section five phase 2).

Given a graph G=(V,E) partitioned into the sets of vertices L and H. The vertices in L are at most D where D is an arbitrary number and the rest of the vertices are in H.

If we take a closer look at Phase 2 (Theorem 5). For each vertex x in L compute the square of the adjacency matrix of G[N(x)] to decide whether G[N(x)] contains a triangle.

We know that the fastest way to find a triangle in a graph is using fast matrix multiplication algorithm which is $O(n^\alpha)$. So, we can define a running time of $\sum_{x \epsilon L}^{ } d(x)^\alpha$. Since we know that |L| can be at most e (number of edges) if we choose a bad D and d(x) is at most D, why Phase 2 can be done in $O(D^{\alpha-1}e)$. I was under the impression that it was $O(D^{\alpha}e)$ i.e. where is the $\alpha-1$ coming from? I'm pretty sure it's trivial, but I'm missing the point.


texts: Are there any known Chernoff/Hoeffding bounds for the case of "almost independence"?

texts:
The usual statement of a Hoeffding bound (e.g. https://sites.math.washington.edu/~morrow/335_17/ineq.pdf) requires independent random variables.
My question is: Do there exist bounds similar to Hoeffding's that apply in the case that, for Bernoulli R.V. $X_i$ for $i \in [n]$
$\Pr\left[\bigcap_{i}X_i\right] = \left(\prod_i \Pr[X_i]\right) + \delta$ for $\delta << 1$, maybe specifically for the case that $\delta$ is a negligible function on $n$?
Thanks.


texts:
This question is primarily related to a practical software-engineering problem, but I would be curious to hear if theoreticians could provide more insight in it.

Put simply, I have a Monte Carlo simulation that uses a pseudorandom number generator, and I would like to parallelise it so that there are 1000 computers running the same simulation in parallel. Therefore I need 1000 independent streams of pseudorandom numbers.

Can we have 1000 parallel streams with the following properties? Here $X$ should be a very well-known and widely-studied PRNG with all kinds of nice theoretical and empirical properties.

The streams are provably as good as what I would get if I simply used $X$ and split the stream generated by $X$ into 1000 streams.
Generating the next number in any stream is (almost) as fast as generating the next number with $X$.

Put otherwise: can we get multiple independent streams "for free"?

Of course if we simply used $X$, always discarding 999 numbers and picking 1, then we certainly would have property 1, but we would lose in the running time by factor 1000.

A simple idea would be to use 1000 copies of $X$, with seeds 1, 2, ..., 1000. This certainly would be fast, but it is not obvious if the streams have good statistical properties.

After some Googling, I have found, for example, the following:

The SPRNG library seems to be designed for exactly this purpose, and it supports multiple PRNGs.
Mersenne twister seems to be a popular PRNG nowadays, and I found some references to a variant that is able to produce multiple streams in parallel.

But all this is so far from my own research areas, that I couldn't figure out what is really the state-of-the-art, and which constructions work well not only in theory but also in practice.

Some clarifications: I do not need any kind of cryptographic properties; this is for scientific computation. I will need billions of random numbers, so we can forget any generator with a period of $< 2^{32}$.

Edit: I cannot use a true RNG; I need a deterministic PRNG. Firstly, it helps a lot with debugging and makes everything repeatable. Secondly, it allows me to do, e.g., median-finding very efficiently by exploiting the fact that I can use the multi-pass model (see this question).

Edit 2: There is a closely related question @ StackOverflow: Pseudo-random number generator for cluster environment.


texts: Ref question: K-nearest neighbours in a graph

texts:
Given an undirected  graph $G$  with $n$ vertices,  $m$ edges, and positive weights on the edges, I am interested in the problem of computing for each vertex the $k$ distinct vertices in $G$ that are closest to it on the shortest-path distances in $G$. There is a solution that follows by modifying Dijkstra, where the running time is $k$ times the running time of the standard Dijkstra. Anybody knows a ref to this result? Should I bother to write this down?

thanks....

Update: I wrote down my algorithm in case anybody is interested...
http://sarielhp.org/p/14/k_nn/


texts:
Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $V \in \mathcal{V}$, there is a weight $W(V)$.

For a clique $Q=(Q_V,Q_E)$ where $Q_v \subset \mathcal{V}$ and $Q_E \subset \mathcal{E}$, the weight of clique $Q$ is defined as $W(Q) = \max_{V \in Q_V}W(V)$.

Now, we want to find a set of cliques covering all vertices $\mathcal{V}$ such that the sum of weights of these cliques are minimum.

In this problem NP-hard?
I think since the graphs are general, when the weights are equal, then the problem become minimum clique cover problem in which we want to cover the graph $\mathcal{G}$ with minimum number of cliques. Since this problem is NP-hard, the problem with arbitrary weights is also NP-hard. Am I right?

How can we find an approximation algorithm for this problem?
I think the most trivial algorithm that comes to mind is this but I don't know how good it is.

Sort the vertices based on their weights in decreasing order (the first one has the highest weight) and if two have the same weight we sort them based on the number of edges of them. Assume the sorted list of vertices is $V_1, \ldots, V_{10}$. Now, we start from the clique $C = V_1$ and check the list $V_2, \ldots, V_{10}$ from left to right. For each element, we check whether adding $V_j$ to $S$ results in a clique or not. If yes, we form a clique of $S$ and $V_j$, and remove $V_j$ from the list. We continue this process (now for $S = \{V_1,V_j\}$) until we reach the end of list $V_2, \ldots, V_{10}$. Now we remove the vertices of set S, from $V_1, \ldots, V_{10}$, and repeat the above procedure for the first element of $V_1, \ldots, V_{10}$ minus the set $V$.


texts: Hardness of an extended maximum set packing problem

texts:
(Edited)

The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$.

The requirement in this problem is that the sets in the solution will be pair-wise disjoint. In other words, one have to find as many as possible sets taken from the sets in the problem (each containing $k$ elements) such that no two sets share one element or more.

Let us now consider a modified version of the $k$-set packing, which we will call Problem A. Instead of finding the maximum number of pair-wise disjoint sets, we have to find the maximum number of subsets of the original sets, such that each subset contains at least $l$ elements not shared by any other subset. For $l=k$, we get the maximum $k$-set packing. Is Problem A NP-hard for $l<k$?

Formally:

Input: A collection $A_1,A_2,...,A_n$ of sets of size $k$ each and an integer $l$, $1 \le l \le k$.

Output: The maximum number of subsets $A'_i \subseteq A_i$ such that $\left| {A{'_i}} \right| \ge l$ and $\left| {A{'_i} \cap A{'_j}} \right| = \emptyset$.

Note that for $l=1$ (for any $k$ such that $l \le k$), we can transform our problem to the maximum bipartite matching problem, so in this case Problem A is solvable in polynomial time. Thus, I ask about the NP-hardness of Problem A in the case $1 < l < k$.

Examples:

${A_1} = \left\{ {1,2,3} \right\}, {A_2} = \left\{ {1,2,3} \right\}$ ($k=3$) and $l=1$. Then $A'_1={1}, A'_2={2}$ is a valid solution. This can be achieved by considering $A_i$ as one group of nodes in a bipartite graph, and the elements as the other group, and then looking for maximum matching. Note that for $l=2, l=3$ only one set can be obtained as a solution.
${A_1} = \left\{ {1,2,3} \right\},{A_2} = \left\{ {2,4,5} \right\},{A_3} = \left\{ {3,4,5} \right\}$ (again, $k=3$). For $l=1$, one possible solution is $A{'_1} = \left\{ 1 \right\},A{'_2} = \left\{ 2 \right\},A{'_3} = \left\{ 3 \right\}$. For $l=2$, only $2$ sets can be chosen: $A'{'_1} = \left\{ {1,2} \right\},A'{'_2} = \left\{ {4,5} \right\}$. For $l=3$, one of the original sets can serve as a valid solution. That is, for $l=1$ we get a solution of cardinality (number of sets) $3$, for $l=2$ the cardinality is $2$ and for $l=3$ the cardinality is 1.


texts: Ordering tours in a Euclidean TSP according to (strictly) increasing length

texts:
Let $H$ be the set of all Hamiltonian cycles on the complete graph $K_n$ associated with a set of $n \geq 4$ points $P$ in the plane where edge weights are defined using the Euclidean distance between pairs of points in $P$. Suppose that $h_1 \in H$ is an optimal tour with length $d(h_1)$ and that the tours are numbered in order of increasing length so that:
$d(h_1) \leq d(h_2) \leq \cdots \leq d(h_{|H|})$.

Question: Is there a set of conditions on the set of points in $P$ that would result in the ordering above being a sequence of strict inequalities? I am interested in finding a lower bound $\lambda < 1$ that characterizes the ratio $d(h_1) / d(h_2) < \lambda$ given some distribution of points, if possible. Intuitively it seems this may be related to the minimum distance between any pair of points in $P$, or the minimum difference in tour length resulting from an edge swap.  Perhaps there are some other well known results on the distribution of tour lengths that might be related. I would be grateful for any references that come to mind on topics related to this question.


texts: Removing recursion - a look into theory behind the scenes

texts:
I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make a long story short, I would like a more detailed answer to the following if this question is acceptable on this site.

So, I know that every recursive program has an iterative analog and I kind of understand the popular explanation that is offered for it by maintaining something similar to the "system stack" and pushing environment settings like return address etc. I find this kind of handwavy.

Being a little more concrete, I would like to (formally) see how does one prove this statement in cases where you have a function invoking chain $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$. Further, what if there are some conditional statements which might lead an $F_i$ make a call to some $F_j$? That is, the potential function call graph has some strongly connected components.

I would like to know how can these situations be handled by let us say some recursive to iterative converter. And is the handwavy description I referred to earlier, really enough for this problem? I mean then why is it that I find removing recursion in some cases easy. In particular removing recursion from pre-order traversal of a Binary tree is really easy - its a standard interview question but removing recursion in case of post order has always been a nightmare for me.

What I am really asking is $2$ questions

(1) Is there really a more formal (convincing?) proof that recursion can be converted to iteration?

(2) If this theory is really out there, then why is it that I find, for eg, iteratizing preorder easier and postorder so hard? (other than my limited intelligence)


texts: Is there a notion of indistinguishability obfuscation for almost equivalent circuits?

texts:
In the definition of indistinguishability obfuscation (iO), we have a probabilistic algorithm Obs that receives as input a circuit C, such that $i)$ the output Obs(C) is a circuit with the same functionality as C and $ii)$ for any $C_1$ and $C_2$ with the same functionality, we have that Obs($C_1$) is indistinguishable from Obs($C_2$).

Has a similar notion (and candidate construction) for a similar concept where the security holds for $C_1$ and $C_2$ are almost the same (i.e., they agree on all except a negligible fraction of the inputs, and it is computationally hard to find the points where they differ).


texts: Comparing $\mathbf{NP}$ and $\mathbf{E}$

texts:
We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$.

The complexity zoo states that $\mathbf{E}$  does not equal $\mathbf{NP}$, and cites the following paper:

R. Book. On languages accepted in polynomial time. SIAM Journal on Computing, 1(4):281–287, 1972.

I have not read the formal proof; though I want to know why the following "intuition" fails:

Intution: Every $\mathbf{NP}$ language is solvable in $O(2^n)$ time, where $n$ is the size of the input.

Proof: Assume that $L \in \mathbf{NP}$. There's a poly-time Karp reduction from $L$ to $3SAT$, and a $3SAT$ formula with $n$ variables can be decided via exhaustive search in $O(2^n)$ time.


texts: Are there any known functions in NC2 but not in TC1?

texts:
Uniform TC1 is known to be in Catalytic Logspace. To improve the lower bound, we are looking for some functions known to be in NC2 but not in TC1.

Also, what are some of the natural functions known in TC1?


texts: Example of context-free tree language which can not be generated by monadic CFTG

texts:
Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (MCFTG).

In other words, I am looking for such a non-monadic CFTG for which it is not possible to construct an equivalent (MCFTG).

The all examples of CFTG's which exist in papers are essentially monadic CFTG.

I am still trying to build such a grammar by myself. But may be somebody already knows such an example and could share it as an answer. I deeply appreciate any help.


texts:
What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but composite (so computations are performed in ring, not a field).

As far as I know (read below), most algorithms are modifications of Gaussian elimination. The question is about the computational efficiency of these procedures.

If it happened that there is some different approach, I also curious about it.

Thanks in advance.

Update:

Let me explain the source of this question. Assume, $m$ is a prime number. So $\mathbb{Z}_m$ is a field. And in this case we can perform all computations using numbers less than $m$, so we have some nice upper bound on all operations on numbers: addition, multiplication and inversion --- all needed operations to run Gaussian elimination.

On the other hand we can not perform inversion for some numbers in case $m$ not a prime. So we need some tricks to compute determinant.

And now I am curious what are the known tricks to do the job and whether such tricks could be found in and papers of books.


texts: Minimal-size extending set in a directed graph

texts:
Let $G=(V,E)$ be a directed graph, i.e. $V$ is a finite set and $E\subseteq V\times V$.

We call a subset $J\subseteq V$ extending if for every $v\in V\setminus J$ there is a directed path from some vertex $j\in J$ to $v$.

Is there a polynomial-time algorithm to find an extending subset of minimal size?


texts: Can relativization change the direction of separation?

texts:
Are any $A$, $B$, and $O$ such that:

$O$ is a set (for oracle),
$A$ and $B$ are the names of two known complexity classes,
$A^X$ and $B^X$ have well-defined accepted meanings,
$A=A^\emptyset\subset B^\emptyset=B$, i.e. $A$ is strictly contained in $B$,
$A^O\supset B^O$, i.e. $A^O$ strictly contains $B^O$.

In the case of $\mathsf{P}$ and $\mathsf{EXP}$, it's impossible to find an oracle $O$ relative to which $\mathsf{P}^O$ strictly contains $\mathsf{EXP}^O$ since a $\mathsf{EXP}^X$ can completely simulate every step of any turing machine in $\mathsf{P}^X$ (i.e. the time hierarchy theorem relativizes).

I'm wondering if there are complexity classes $A$, $B$ s.t. $A \subset B$, yet for some oracle $O$, $A^O \supset B^O$. In other words, can the direction of strict inclusion change when complexity classes are relativized?


texts: Conclusions from reverse mathematical strength of graph minor theorem

texts:
Say we have a graph property which can be checked in nondeterministic polynomial time, and a proof in a weak formal system (say RCA0) that the property is minor closed. Can we say anything about the strength of a formal system, which is able to prove that a given finite set of excluded-minors characterises the given graph property?

Context It is well known that already a simple version (without well-quasi-ordered set of labels) of Kruskal's tree theorem is unprovable in ATR0 and the graph minor theorem is a generalisation of that theorem which isn't even provable in Π11-CA0. Friedman used that simple version of Kruskal's tree theorem to construct the fast growing TREE(n) function, and used the graph minor theorem to construct the even faster growing SSCG(n) function. Those are nice demonstrations of conclusions about computational content from reverse mathematical strength, but those leave the more direct question posed above unanswered.

Namely, related to the graph minor theorem is the proof that minor closed properties can be tested in deterministic cubic time, if one knows the list of excluded minors for that property. Hence it is natural to wonder just how "impossible" it is to prove that one has found all excluded minors for a given "easy" (as made precise in the question) minor closed property. Since this is a "non-uniform" task, it is not clear to me whether the "impossibility" of this task is related at all to the "difficulty" (i.e. reverse mathematical strength) of proving the graph minor theorem itself.

Since the simple version of Kruskal's tree theorem poses exactly the same questions as the graph minor theorem, answers may focus on that simpler problem, if they want. I just used the graph minor theorem, because the question feels more natural that way. (It is possible that this question might have been more suitable to MSE or MSO, at least with respect to getting a definite answer. But the motivation of this question is more related to TCS, so I decided to ask it here.)


texts: Which models of computation can be expressed through grammars?

texts:
This is a reformulation of Are grammars programs? previous asked by Vag and with many suggestions from the commenters.

In what way can a grammar be seen as specifying a model of computation?
If, for example, we take a simple context-free grammar such as

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

Assuming that the parser does not differentiate between terminal and nonterminal symbols as I've demonstrated here, then it is possible to perform simple arithmetic for numbers up to 3.

For example, take the string

"2 + 0 + 1"

Running a LR(1) parser on this string should give us the following concrete syntax tree where the result of the computation is stored at the root of the tree:

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0'

Thus, if we take a grammar to be a program and a parser generator to be a compiler, could we see the grammar specification language as a programming language?

Furthermore, could we build Turing-complete programs by specifying grammars similar to how you could build turing complete programs with celullar automata or the lambda calculus?

In other words, it is known that in the sense of recognizing a language, regular languages correspond to finite state automata, context-free languages correspond to push down automata, and context-sensitive languages correspond to linear bounded automata. However, if we look at grammars as computational devices (i.e. programs in the sense of the example above), then how do we classify the computational strength of each class of grammars in the Chomsky hierarchy?

Regular grammars
Context-free grammars
Context-sensitive grammars
Unrestricted grammars (for recursively enumerable languages)

Also, how about the lesser known subclasses of grammars such as

Deterministic context-free grammars (also LR(k)/LL(k)/SLR/LALR etc)
Nested word grammars
Tree adjoining grammars
Indexed grammars

EDIT: By the way, this is a nitpick on my own question but I didn't mention that I gave no starting symbol for the example grammar and hand-waved at the need to distinguish between terminals and nonterminals. Technically or traditionally I think the grammar would probably have to be written in a more complicated form like this one (where S is the starting symbol and the \$ represents the end-of-stream terminal):

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

...not that it really changes anything, but I thought I should mention it.

EDIT: Something else that came to mind when I read gasche's answer is that each branch in the tree in my example represents a sub-computation. If you look at each production rule as a function where the LHS represents the result and the RHS represents its arguments, then the structure of the grammar determines how functions are composed.

In other words the context of the parser together with its lookahead mechanism helps to determine not only which functions to apply ('kinda' like parametric polymorphism) but how they should be composed together to form new functions.

At least, I guess you could look at it this way for unambiguous CFG's, for other grammars the mental gymnastics is a little bit too much for me right now.


texts: Support size lower bound for $k$-wise uniform distribution

texts:
So I have this question which I can't seem to find a solution to:

  Prove that if $X = (X_1, ... X_n)$ is $k$-wise uniform* and each $X_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \mathbf B(\frac{k}{2}, n)$, where $\mathbf B(r, n)$ is the number of words of weight at most $r$.

$*$ Where $k$-wise uniform means that, for each subset $S=\{i_1,\dots, i_s\}\subseteq [n]$ of size $s\leq k$, the distribution of $(X_{i_1},\dots,X_{i_s})$ is uniform.


texts:
Consider the problem of finding the maximum number of knights that can be placed on a chessboard without two of them attacking each other. The answer is 32: it's not too difficult to find a perfect matching (the graph induced by knight moves is bipartite, and there's a perfect matching for a 4 × 4 board), which is obviously a minimum edge cover. It's also not difficult to prove that the answer is $\left\lceil \frac{mn}{2} \right\rceil$ for an $m \times n$ chessboard whenever $m,n \geq 3$: it suffices to show matchings for $3 \leq m,n \leq 6$ and do a bit of induction footwork.

On the other hand, if the chessboard were toroidal and $m, n$ were even, the proof wouldn't even require showing a matching for small boards: the map $(x, y) \rightarrow (x+1, y+2)$ has only even-length cycles so there must be a perfect matching.

Is there any equivalent for rectangular chessboards, i.e. is there any simpler way to show that for sufficiently large $m, n$ there is always a perfect matching of the chessboard? For large boards, the rectangular board and the toroidal board are almost equivalent in the sense that the fraction of missing edges goes to zero, but I'm not aware of any theoretical results that would guarantee a perfect matching in that case.

What if, instead of jumping $(1, 2)$ in either direction, a knight jumped $(2, 3)$ squares in either direction? Or, for that matter, $(p, q)$ squares, with $p+q$ odd and $p, q$ coprime? If there is a simple way of proving that the answer is $\left\lceil \frac{mn}{2} \right\rceil$ for sufficiently large $m, n$ (say, $m, n \geq C(p, q)$), what does $C(p, q)$ look like?


texts: Is the complement of { www | … } context-free?

texts: It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?


texts: Fastest Algorithm for the Minimum Edge Covering Problem

texts:
Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints:

G' must include all the vertices of G.
All vertices must be connected to at least one vertex of G'.  In other words the edges of G' must cover all the vertices of G'.
The total weights of all edges in G' must be as low as possible.

In other words, this is the minimum weighted edge cover problem.

So, my question is, in terms of time complexity with respect to the number of vertices and edges, what is the fastest known algorithm for finding the correct answer?

What I've done so far:

I've found some resources online, but they often seem to say contradictory things.

I was able to find one post that pointed out that this problem can be reformulated as a maximum matching problem (see here).

In that case, I've found references to Edmond's Algorithm, which can run in O(V^2*E) or O(V^3) time.  There are references to improved versions of this algorithm, but as far as I can tell, these only deal with unweighted graphs, not weighted ones.  So, as far as the known solutions go, is O(V^2*E) or O(V^3) time complexity the best we can get?


texts:
Given a complete, positively weighted, bidirectional graph with $n$ nodes without self-loops. Hence the corresponding adjacency matrix $A$ is positive, symmetric, and has zero main diagonal. I am searching for a subgraph with $k$ nodes such that the sum of weights is minimal.

In terms of the adjacency matrix, this is:
$$
\min_{K \subset \{1,2,\dots,n\}, |K| = k} \sum_{i,j \in K} A_{ij}
$$

Is there a solution better than testing all $K$?
Is there a related problem where I can start my search?


texts: How to find a non-zero point of a non-zero polynomial of low degree?

texts:
Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one deterministically find another point $X' \neq X$, such that $P(X') \neq 0$.

Basically, it is a standard Polynomial identity testing with only one new twist: we know that the solution exists. You can say that it is in some sense problem from $FRP \cap PPP$ (this is very informal statement, I am not sure that this problem is in $PPP$, but it has the same flavor).

I would be glad if someone can point to some positive or negative results about this problem.


texts: Are there any known NP problems which are conjectured to be exponentially hard on average?

texts:
ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average case?

Take average case to mean average running time with uniform distribution on the inputs.


texts:
In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the following question.

  Given a FSM transducer, how does one find a "minimal" equivalent transducer?

Note that there are possibly multiple reasonable ways to define the minimal transducer. The literature maybe hasn't settled on one. Also, I'm looking for applications if some are known.


texts: Statistical Algorithms vs Convex Relaxations - Planted Clique

texts:
I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ?

A recent paper by Feldman, Perkins and Vempala builds the connection between Statistical Algorithms and Convex Relaxations by showing that for detecting planted k-CSPs, lower bounds on the complexity of Statistical Algorithms can be translated to lower bounds on the dimension of canonical convex relaxations.

I was wondering if a similar thing can be said about Planted Clique lower bounds for Statistical Algorithms (which were proven here). In particular what kind (if any) of lower bounds on Convex Relaxations do these imply?


texts: Pursuing Theoretical Computer Science after CS major

texts:
So I am currently a sophomore majoring in Computer Science. In the Data Structures course that I am currently studying, I studied the basics of complexity of a program and big O-notation, etc. That got me interested in complexity theory and maybe pursuing TCS later on.
I have always had a great interest in mathematics and although I chose not to major in it (The math department at my university is not very good), I still plan to take some courses like Analysis, Abstract Algebra etc. (I have already taken Discrete Mathematics).  Initially, I started as a physics major so I have also taken two Quantum Mechanics courses.
I was just wondering if graduate admissions in TCS require a minor or major in mathematics or just some specific courses. Because, as far as my mathematical knowledge/skill is concerned, I think I have a strong background since I have always enjoyed solving problems involving proofs (although maybe not very formal ones) and sometimes just solving questions as a hobby.
Which courses are recommended to take if I want to maybe go into TCS later? Considering that I have 2 years left for my undergrad. Also, what are other possible sub-fields in TCS that I could consider?
The math/phy courses I have already taken are: LA, Calc 1 and 2, Discrete math, QM 1 and 2, Probability.


texts: Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?

texts:
This paper gives example
of polynomial GI for certain graphs.

Probably I am misunderstanding the paper, but appears
to me it implies polynomial GI for cubic, $4$-regular
and probably higher degree regular graphs.

GI for regular graphs is GI complete.

On p. 7 the graphs $H(a,b,c)$ are defined. They are a claw with
$a+b$ leaves, $a$ edges are subdivided and $c$ isolated
vertices are added.

On p. 8 Theorem 4. Isomorphism of $(H(0, b, c), \overline{H(0, b' , c' ))}$-free graphs is in $P$ when:

(2.) $c, c′ \le 1$ and $b, b' \ge 1$.

Take $c=c'=1,b=b'=5$.

$H=H(0,5,1)$ is $K_{1,5} + K_1$.

Both $H$ and $\overline{H}$ have degree $5$ vertex,
so neither can be induced subgraph of cubic or
$4$ regular graph.

By taking larger $b$ this works for higher
degree regular graphs.

Does the paper imply GI is in $P$ for cubic
and $4$-regular graphs?
Does the paper imply GI is in $P$ for higher
degree regular graphs (the running time might
depend on $b$, not sure)?