texts: Is it easy to "fit a wrapped chain in a graph"?

texts:
Given a directed graph $G=(V,A)$ with a unique source node $s$ (a node without incoming edges) and a unique sink node $t$ (a node without outgoing edges).

Given a sequence of variables $SEQ = (x_{i_1},x_{i_2},...,x_{i_m})$ with $|SEQ| > 2$ and each $i_j \in [1..m]$

For example $SEQ = (x_1,x_2,x_3,x_4,x_2,x_3,x_5)$ (m=5).

A node assignment is a function $f: \{x_1,...,x_m\} \rightarrow V$ such that if $i \neq j$ then $f(x_i) \neq f(x_j)$ (it maps each $x_j$ to a different node of the graph). Now, if in $SEQ$ we substitute $x_j$ with $f(x_j)$ we obtain a sequence $NODESEQ$ of nodes.

We want to start from $s$ and end in $t$ so trivially $x_1 = s, x_m = t$.

For example: $NODESEQ = (s,v_1,v_7,v_9,v_1,v_7,t)$

A valid node assignment is an assignment such that if we substitute each $x_{i_j}$ with $f(x_{i_j})$ in the sequence $SEQ$ we obtain a valid path from $s$ to $t$.

Problem 1:

Given a directed graph $G$ with one source and one sink and a sequence of variables $SEQ$ check if a valid node assignment exists.

I'm not an expert, but if we take $m=n=|V|$ and $SEQ=(x_1,...,x_n)$ then the problem becomes the Hamiltonian Path problem. Informally HAM-PATH can be reduced to Problem 1, adding a source node $s$ and a sink node $t$, two extra variables at the beginning and end of $SEQ$: $(x_s,x_1,...,x_n,x_t)$ and edges $(s,u), (v,t)$ for every $u,v \in V$, (hence Problem 1 is in NPC).

But we can modify it and drop the condition that if $i \neq j$ then $f(x_i) \neq f(x_j)$ i.e we can assign the same node $v$ to more than one $x_i$ (I call it relaxed node assignment). We get an (apparently) simpler problem.

Problem 2:

Given a directed graph $G$ with one source and one sink and a sequence of variables $SEQ$ check if a valid **relaxed node assignment** exists.

An informal way to describe the problem: we have a chain made of segments. Now we wrap it up in some casual order and join some innermost endpoints. The problem 2 consists in checking if such wrapped chain can "fit" in a given graph.

Is this problem known?

Is it still an NPC problem?


texts: Insecurity of Schnorr's Signature Scheme

texts:
How is the Schnorr Signature insecure in the following 2 scenarios:

When there is no hash function used,
s = k-x*m mod q   instead of  s = k-x*H(m||r) mod q
When a hash function is defined as H(m) instead of H(m||r)

Ref: Schnorr Signature


texts: Can Bin-Packing Algorithm allow to put the item on hold?

texts:
I am searching for research that shows that Bin-Packing allows an item to put "on hold" when the solution returned is in a very bad position and places the item later if there is an available solution that is not bad.
I am working on an online version 2d/3d bin packing method, and I want a reference to prove my claim above.
I know that it would require additional space, but it somehow took the advantage of not placing the item in a very bad position.
Do you know some research for this claim? I can hardly find the right term for this word - "on hold".
If there is none, is it a valid approach in Bin-Packing? and why?


texts:
I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at http://www.cs.nyu.edu/~mohri/pub/ (they are virtually identical so which of them doesn't matter).

Could  anyone help me understand the main differences between the algorithm for the tropical semiring and that for the probabilistic semiring?

Right now I could, maybe, basically explain what happens, but I can't explain the idea behind it. Thank you so much!


texts: Convergence speed in Lévy’s continuity theorem

texts:
I suppose the answer to my question follows from the proof of the Lévy’s continuity theorem,
but probably one could suggest me a direct reference to the corresponding answer.

The question is as follows. Suppose the sequence of characteristic functions (c.f.) $\phi_n$ of random variables $X_n$ converge point-wise to some c.f. $\phi$ of random variable $X$ with convergence rate $\alpha(x,n)$, i.e. $\phi(x) = \phi_n(x) + O(\alpha(x,n))$ where $\alpha(x,n)$ tends to $0$ while $n$ tends to infinity. Does this implies that $P(X_n \leq x) = P(X \leq x) + O(\alpha(x,n))$?


texts: Partition a graph into 2 connected subgraphs

texts:
I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are $m$ vertices in $G$, subgraphs $G_{1}$ and $G_{2}$ should have

\begin{equation}
|V_{1}| + |V_{2}| = |V|
\end{equation}
\begin{equation}
(|V_{1}| - |V|/2)^{2} \leq \epsilon^{2}, (|V_{2}| - |V|/2)^{2} \leq \epsilon^{2}
\end{equation}

and $V_{1}$ and $V_{2}$ should be disjoint.

Anyone know a quick way to compute if this exists and what the partition should be? I know that partitioning in general is NP-hard but I didn't know if it was for this special case.


texts: Is the Selflet system used for any active research?

texts: Is the Selflet system (referenced in this paper - http://portal.acm.org/citation.cfm?id=1365562.1365597 for example) still seeing active research?


texts: Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?

texts:
A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover).

Does anyone know of a problem which is polytime solvable for $R^1$ and $R^2$, but NP-complete for $R^d,d\geq3$?

More generally, do problems exist which are NP-complete for $R^k$ but polytime solvable for $R^{k-1}$, where $k\geq3$?


texts: The Stalin compiler brutally optimizes, but how?

texts:
J.M. Siskind's research statement states:

Stalin is an optimizing compiler for Scheme that performs whole-program static analysis and uses the results of that analysis to generate extremely efficient code. Stalin utilizes a large collection of static-analysis techniques. It performs a novel form of polyvariant flow analysis that uses iterated monovariant flow analysis to perform flow-directed splitting: cloning of specialized copies of procedures and per-call-site assignment of targets to such clones. It uses the results of flow analysis to perform life-time analysis, escape analysis, points-to analysis, and must-alias analysis. These analyses support a novel form of lightweight closure conversion that eliminates most closure slots, using techniques such as variable globalization and localization, compresses the static backchain, and usually eliminates most closures from programs. It also uses the above analyses to support flow-directed region-based storage management, where run-time garbage collection is replaced with static allocation and deallocation on a per-abstract-value and per-program-point basis. It also performs flow-directed lightweight CPS conversion, using extensions of the techniques pioneered with Screamer, to support extremely efficient first-class continuations. Finally, it supports flow-directed inlining and low-level representation selection to choose the implementation (or nonimplementation) of tags, tag checking, and tag dispatching on a per-abstract-value and per-program-point basis. This eliminates most run-time tags, tag checking, tagging, tag stripping, tag dispatching, boxing, and unboxing from programs. These analyses and optimizations allow Stalin to generate extremely efficient code that outperforms all other Scheme compilers by factors ranging between two and one hundred, particularly for numerically intensive code. Stalin often generates code that outperforms handwritten c and Fortran code.

I was able to find the following very interesting paper on closures/function calls implementation: Flow-Directed Lightweight Closure Conversion. I've also emailed the author to ask about the papers on the other topics, which are mentioned as to be written in the closure conversion paper:

Siskind, J. M. 2000a. Flow-directed lightweight CPS conversion. In preparation.
Siskind, J. M. 2000b. Flow-directed polyvariance. In preparation.
Siskind, J. M. 2000c. Flow-directed representation selection. In preparation.
Siskind, J. M. 2000d. Flow-directed storage management. In preparation

Unfortunately, he never got around to writing those papers. My question to you is: are there any alternative or related papers that cover these topics? I'm very interested to learn how Stalin (or other compilers) can compile such a high level language as Scheme that is garbage collected, dynamically typed, supports first class functions, and even first class continuations, can be statically compiled to such efficient code. Although papers on flow analysis are quite abundant, papers on using the results of such an analysis to do the optimizations mentioned above aren't.


texts: Questions on unification theory (and its application to DAG isomorphism )

texts:
While looking looking for an efficient and simple algorithm for directed acyclic graph isomorphism, I stumbled upon this which points out the similarity between DAG isomorphism and unification.  After learning a bit on the subject, I still have many questions about the relationships between the subjects.

Unification is said to be efficient on first order logic term. How efficient is it, exactly?
In my first analysis, it seems like DAG isomorphism should be reducible to unification, yet unification is efficient and DAG isomorphism is not. What am I missing? (I am of course assuming that every DAG can be transformed "efficiently" into a valid set of first order logic "expressions"... Is that correct?)
Is there a reference where the relationship between the subjects are explored?
How far can semantic unification go while staying efficient? Associations? Commutativity? Something else? Are there any papers on a real word application?

To give some context, the DAGs I am looking into are basic blocks DAGs from MIPS assembly language (or something close). I am working on the custom instruction selection problem where the goal is pretty much to identify subgraphs of the basic block DAG which should be implemented in hardware. I need to check for isomorphism to avoid having two separate hardware units performing the same operation.

Given my use-case, can someone point me in the direction of the best "isomorphism framework" (DAG isomorphism, unification, something else, etc...) to use?


texts:
Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor.  How quickly can we compute the exact effective resistance between two vertices in G?  Equivalently, how quickly can we compute the exact current flowing along each edge if we attach a 1V battery to two vertices in G?

Kirchhoff's well-known voltage and current laws reduce this problem to solving a system of linear equations with one variable per edge.  More recent results — described explicitly by Klein and Randić (1993) but implicit in earlier work of Doyle and Snell (1984) — reduce the problem to solving a linear system with one variable per vertex, representing that node's potential; the matrix for this linear system is the Laplacian matrix of the graph.

Either linear system can be solved exactly in $O(n^{3/2})$ time using nested dissection and planar separators [Lipton Rose Tarjan 1979].  Is this the fastest algorithm known?

Recent seminal results of Spielman, Teng, and others imply that the Laplacian system in arbitrary graphs can be solved approximately in near-linear time.  See [Koutis Miller Peng 2010] for the current best running time, and this amazing article by Erica Klarreich at the Simons Foundation for a high-level overview.  But I'm specifically interested in exact algorithms for planar graphs.

Assume a model of computation that supports exact real arithmetic in constant time.


texts: Enumerate all allocations of points in a simplex

texts:
Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$.
Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process:

Fix two positive weights $(w_x,w_y)$;
For each point $(x,y)\in M$, calculate $w_x x$ and $w_y y$;
If $w_x x > w_y y$ then give the point to X; else give the point to Y.

From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why? Because if a point $(x_1,y_1)$ is given to X, then all the points $(x_2,y_2)$ with $x_2>x_1,y_2<y_1$ are given to X too. Thus, each allocation can be found by cutting the line at some point,  giving to X all the points between the cut and $(1,0)$, and giving to Y the remaining points. Thus, it is easy to enumerate all possible allocations.

The question is: what happens when we move to a higher-dimensional simplex? For example, consider the standard 3-simplex $\{(x,y,z)~|~x+y+z=1~;~ x,y,z\geq 0\}$.
Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y or to Z by the following process:

Fix 3 positive weights $(w_x,w_y,w_z)$;
For each point $(x,y,z)\in M$, calculate $w_x x$ and $w_y y$ and $w_z z$;
If $w_x x$ is larger than the other two - give the point to X; else, if $w_y y$ is larger than $w_z z$ - give the point to Y; else, give the point to Z.

What is an efficient algorithm, with run-time polynomial in the output size, for enumerating all and only the allocations attainable by the above procedure?


texts: What are the problems in EXPSPACE \ EXPTIME?

texts: Based on the diagram below (from Papadimitriou's book) we can see that PSPACE ⊆ EXPTIME ⊆ EXPSPACE. We know that PSPACE ⊊ EXPSPACE, which means that there are problems that can be solved in polynomial bounded space and problems that are only solvable in exponential bounded space. These latter problems are outside PSPACE, so they must be either inside EXPTIME or outside of it. The ones inside are problems that need exponential time to be solved, but not necessarily exponential space. The ones outside are problems that require exponential space to be solved and, since a machine can only do a constant number of movements per transition, they also require exponential time. So my question is: shouldn't this put them all back inside EXPTIME? It doesn't make sense to me that there are problems inside EXSPACE but outside EXPTIME, i.e. problems that require exponential space without requiring exponential time. What are the problems in EXPSPACE outside EXPTIME?


texts: Reconstructing a string from random samples

texts:
What is known about the following problem?

  Reconstruct a string $\sigma$ of known length $n$ over a known
  alphabet $\Sigma$ from a collection of uniformly and independently
  chosen $k$-long subsequences of $\sigma$ where $k$ is fixed between
  $0$ and $n$.

Recall that a $k$-long subsequence of $\sigma=\langle \sigma_1,\ldots,\sigma_n\rangle$ is a sequence $\langle \sigma_{\varphi(1)},\dots,\sigma_{\varphi(k)}\rangle$ where $\varphi$ is an increasing function from $\{1,\ldots,k\}$ to $\{1,\ldots,n\}$.


texts: Computing chromatic number of subcubic graphs

texts:
According to graphclasses.org, the chromatic number of a subcubic graph can be computed in linear time (because the decision problem COLORABILITY can be solved in linear time). The reference given the website is M. Chlebik and J. Chlebikova, "Approximation hardness of dominating set problems in bounded degree graphs".
Which result of this paper solve the COLORABILITY problem of subcubic graphs in linear time?
The chromatic number of a subcubic graph is 3 unless it is bipartite or $K_4$ is a component by Brook's theorem. Then, why that particular reference is given? Is this simply a case of wrong reference?
Def. A graph with maximum degree at most three is called a subcubic graph.


texts: How are safety/liveness languages defined on the set of finite or infinite words?

texts:
Let $Σ$ be an alphabet (e.g., the powerset of atomic propositions coming from some Kripke structure, though such details are irrelevant here).

For infinite words, a language $P\subseteq Σ^ω$ is called a safety language iff every word $σ ∈ Σ^ω \setminus P$ has a finite prefix $σ̂$ such that $P ∩ \{σ' ∈ Σ^ω \mid σ̂\ \text{is a prefix of}\ σ'\} = ∅$.

Is there an accepted, meaningful definition of safety languages for finite words, i.e., "A set $P\subseteq Σ^*$ is called a safety language iff …"?
Is there an accepted, meaningful definition of safety languages for finite or infinite words, i.e., "A set $P\subseteq Σ^ω ∪ Σ^*$ is called a safety language iff …"?

For infinite words, a language $P\subseteq Σ^ω$ is called a liveness language iff each finite word from $Σ^*$ is a prefix of a word from $P$.

Is there an accepted, meaningful definition of liveness languages for finite words, i.e., "A set $P\subseteq Σ^*$ is called a liveness language iff …"?
Is there an accepted, meaningful definition of liveness languages for finite or infinite words, i.e., "A set $P\subseteq Σ^ω ∪ Σ^*$ is called a liveness language iff …"?

In cases 2 and 4, the definitions for finite-or-infinite words should be (intuitively speaking) compatible with the standard definitions for infinite words.

Of course, some folks prefer to speak about safety/liveness properties, which are predicates $(W)→\{0,1\}$, rather than about safety/liveness languages, which are subsets of $W$, where $W$ is the corresponding set of words ($Σ^ω$, $Σ^*$, or $Σ^ω∪Σ^*$). For this question, the preferred framework (predicates on the powerset vs. subsets) is irrelevant.

Needless to say: in case of a negative answer, please substantiate your concerns.

Crosspost: https://cs.stackexchange.com/questions/115156


texts: Approximation class of finding decision trees with minimal depth

texts:
We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i? $" for some $i$, taking the left branch means "yes", taking the right branch means "no", and leaves are such that, for all $x \in A \cup B$, the answers appearing along the path from the root to the leaf imply that $x$ necessarily belongs to A or necessarily belongs to B. What is the approximation class of finding the decision tree with minimal depth?

This question was already asked in Algorithm for optimizing decision trees, but it seems that all answers given there concern constructing decision trees with minimal size (minimal number of nodes or leaves), not trees with minimal depth (e.g. Sieling'08 tackles the problem of minimizing the size).

It's very easy to AP-reduce (even S-reduce) Set Cover into this problem, so it's at least Log-APX-hard, but I couldn't find any Log approximation. May it be worse than Log-APX-hard?


texts:
We know that DCFL is not closed under the union operation and
CFL is closed under union and contains the union of DCFLs.

Is there a characterization of finite unions of DCFLs?


texts: Exponential gap on neural network layers

texts: I read it here that there are function families which need $\mathcal{O}(2^n)$ nodes on neural network with at most $d - 1$ layers to represent the function while need only $\mathcal{O}(n)$ if the neural network has at least $d$ layers. It was referring to a paper by Hastad. I didn't find it. Could someone tell me the title of the paper? I think this is a really fascinating theoretical result.


texts:
Programming languages with dependent types and/or higher-kinded types feature what might be called compile-time computation at the type-level.  This is usually defined as follows (I'm omitting some details for simplicity), see e.g. [1, 2, 3].

A notion $\equiv_{type}$ of type-equivalence is defined on types, e.g. $(\lambda x^{K}.\alpha)\beta \equiv_{type} \alpha[\beta/x]$  or $(\Pi x^{\alpha}.\beta)M \equiv_{type} \beta[M/x]$, where $M$ ranges over programs, $K$ over kinds, and $\alpha, \beta$ over types.
Then the typing system is enriched with a variant of the following rule.
$$
\frac{
\Gamma \vdash M : \alpha
\quad
\alpha \equiv_{type} \beta
}{
\Gamma \vdash M : \beta
}
$$

However, we can easily extend the relation $\equiv_{type}$ to typing environments $\Gamma$ pointwise,
and also to programs, e.g. $\lambda x^{\alpha}.M \equiv_{type} \lambda x^{\beta}.M$ whenever $\alpha \equiv_{type} \beta$, leading to a rule

$$
\frac{
\Gamma \vdash M : \alpha
\quad
\Gamma \equiv_{type} \Delta
\quad
M \equiv_{type} N
\quad
\alpha \equiv_{type} \beta
}{
\Delta \vdash N : \beta
}
$$

I have never seen this done. I assume that it's just a question of convenience and that both approaches are equally expressive, but I am not sure! Is there some problem with the second approach?

H. Barendregt, Introduction to generalised type systems.
H. Barendregt, Lambda Calculi with Types.
B. C. Pierce, Types and Programming Languages.


texts: Detecting undirected cycles in logarithmic space

texts:
I have a lot of difficulties with constructing algorithms that use $O(\log n)$ space, as I am unsure about how much can be stored on the worktape.

I am trying to figure out an algorithm for the problem:

UCYCLE = {<G>|G is an undirected graph that contains a simple cycle}

I can't seem to understand how to create an algorithm in logspace that can solve this problem. In my head, it has to store all the previously visited nodes (since it can't visit the same node twice). Also, I am really stuck on how to start searching, when I can't use non-determinism. Can someone help me with some pointers on how to go forward so I can figure out an algorithm?

(PS: This is not homework, but I need to understand how to create algorithms for problems in L and NL)


texts: In a resistor network, is there any relation between the shortest path and the maximum electric current path?

texts:
Consider a shortest path problem between the source $s$ and sink $t$ in an undirected weighted graph. There's a well known algorithm such as Dijkstra's algorithm that solves this problem.

Naturally, this graph can be considered as a resistive network where each edge $e$ with distance (or a cost) $d_{e}$ corresponds to a resistor with resistance $d_{e}$ or conductance $1/d_{e}$. From a physical point of view, assume that we send one unit of current from s to t, say by attaching $s$ to a current source and $t$ to ground. It will induce a certain electric flow in $G$ and this flow is unique. And the approximated solution (or the approximate electric flow) can be obtained in time $\tilde{O}(m)$ where $m$ is the number of edges in the graph.

My question: what is the relation between the shortest path in a graph and the path in an electric network where the max electric current flows? Is it true that two paths are always the same when there exists a unique shortest path from $s$ to $t$?

The intuition: The electric current tends to flow through the path with the least resistance, and the least resistance between $s$ to $t$ may be interpreted as the shortest path between $s$ to $t$.

updated

8--R--7--R--+
|     |     |
|     R     |
|     |     |
+--R--6--R--+
|     |     |
|     R     |
|     |     |
+--R--5--R--+
|     |     |
|     R     |
|     |     |
+--R--3--R--4
|     |     |
|     R     |
|     |     |
+--R--2     R
|           |
|           |
|           |
+--R--1--R--0

@MarzioDeBiasi: Thank you for the picture and actual current computation. But ironically, your answer only fortifies my conjecture about the shortest path and max current path. (I apologize for not explaining my conjecture clearly if that causes some confusion.)

As you pointed out, we have the current of 33.9 mA from 4 to 0, but that's due to the superimposition of many currents. For example, the current flows 8 - 2 - 3 - 4 - 0, 8 - 3 - 4 - 0, 8 - 5 - 6 - 7 - 4 - 0 and 8 - 7 - 4 - 0 contribute to the current flow from 4 to 0. And none of them are larger than the curent of 25mA on the path of 8 - 1 - 0. On the other hand, there's only one path for the flow 8 - 1 - 0 and it sends the largest amoun of current in the circuit.


texts: Computationally bounded version of Nash equilibrium?

texts:
I'm wondering if there is a computationally bounded version of the Nash equilibrium concept, something along the following lines.

Imagine some kind of two-player perfect information game which is played on an $n\times n$ board, and which is complex in the sense that optimal play is EXPTIME-hard.  Suppose also for simplicity that draws are not possible.  Imagine a pair $(A, B)$ of randomized polynomial-time Turing machines playing this game against each other.  For each $n$, let $p_{A,B}(n)$ be the probability that $A$ beats $B$ at the order-$n$ game.  (For concreteness, let's say that $A$ gets to play first with probability 0.5.)  What I think would be cool is if one could prove the existence of a pair $(A,B)$ with the property that no randomized polynomial-time Turing machine $A'$ dominates $A$ (where "$A'$ dominates $A$" means $p_{A',B}(n) > p_{A,B}(n)$ for all sufficiently large $n$), and similarly no randomized polynomial-time Turing machine $B'$ dominates $B$ (where "$B'$ dominates $B$" means $p_{A,B'}(n) < p_{A,B}(n)$ for all sufficiently large $n$).

Somehow, I suspect that this is too much to hope for, but is there any hope for something like this to be true, perhaps for a restricted class of games?

One motivation for this question is that I am looking for a way to formalize the notion that a given chess position is "advantageous for White."  Classically, a position is either a win for White or it isn't.  However, chess players, both human and computer, have an intuitive understanding of what it means for White to have an advantage.  It seems to have something to do with the probability that White will win, given that the players are computationally bounded and have to guess at the best move.  For a specific pair of randomized algorithms one can of course talk about the probability that White will win, but what I'm wondering is if there can be, in some sense, a canonical pair of computationally bounded players whose winning probabilities yield a value for the position that depends only on the game itself and not the idiosyncrasies of the players.


texts: Can all structurally recursive functions be written without explicit recursion using a catamorphism/fold?

texts:
In particular, I am thinking of a function which involves conditionals changing the recursive behavior and multiple F-algebras.

halting_search :: int -> (a -> bool) -> (a -> a) -> a -> Maybe a
halting_search 0 f_test f_next_candidate candidate = Nothing
halting_search (S n) f_test f_next_candidate candidate = case (f_test candidate) of
  true => Just candidate
  false => halting_search n f_test f_next_candidate (f_next_candidate candidate)

Is this capable of being written just using the cata operator?  The reason I'm asking is because I want a functional language that is fairly expressive but not overly expressive, and it seems like one way to do that might be to not allow explicit recursion but make cata a primitive function.


texts: Runtime of Gomory's Cutting Plane Algorithm

texts:
I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown to quite effective for certain problems (especially when paired with another hueristic such as branch and bound).

Is there any literature out there that gives strong upper and lower bounds on the performance of the Cutting Plane Algorithm?

Wiki references, didn't lead to anything and I dug around a bit more but still couldn't find an answer. I think if I have Gomory's original paper, where he proves the algorithm must converge in a finite number of steps, that would naturally lead to a start for an upper bound on runtime


texts: Constructively efficient algorithms without efficient correctness and efficiency proof

texts:
I am looking for natural examples of efficient algorithms (i.e. in polynomial time) s.t.

their correctness and efficiency can be proven constructively (e.g. in $PRA$ or $HA$), but
no proof using only efficient concepts is known (i.e. we don't know how to prove their correctness and efficiency in $TV^0$ or $S^1_2$).

I can make artificial examples myself. However I want interesting natural examples, i.e. algorithms studied for their own sake, not created just to answer this type of questions.


texts: Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

texts:
Let $Q$ be a hereditary class of graphs. (Hereditary = closed with respect to taking induced subgraphs.) Let $Q_n$ denote the set of $n$-vertex graphs in $Q$. Let us say that $Q$ contains almost all graphs, if the fraction of all $n$-vertex graphs falling in $Q_n$ approaches 1, as $n\rightarrow\infty$.

Question: Is it possible that a hereditary graph class $Q$ contains almost all graphs, but for every $n$ there is at least one graph that is not in $Q_n$?


texts: Descriptive model theory classification of Counting hierarchy

texts:
Descriptive model theory uses logic to characterize complexity classes

How to model

Counting Hierarchy
PSPACE

in descriptive model theory?


texts: application for the Kchinchine inequality in Computer Science

texts:
The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has
$$
E(|\sum_{i=1}^{2m}r_ia_i|^p)^{1/p}\leq C\sqrt{p}\|a\|_2,
$$
where $C$ is some (known) constant.
Note, Rademacher random variables are such that $P(r_i=1)=P(r_i=-1)=1/2, i=1, \ldots 2m$.

My question: Suppose we have dependent Rademacher random variables. Say, we have extra assumption that the sum $\sum_{i=1}^{2m}r_i=0$. Is there some application in the Computer Science of the Khinchine inequality with this extra condition on the dependence of the Rademacher random variables?

Thank you.


texts:
In the paper "On Interprocess Communication", the author Leslie Lamport have developed a formalism for interprocess communication via shared registers based on lower-level, non-atomic operations and have proposed the definitions of safe, regular, and atomic registers. Also Lamport's description for the "interprocess" publication.

For safe registers, a read that overlaps a write operation is allowed to return any one of the possible values of the register.

My problem is

  How practically relevant is this specification of safe registers?

Particularly, is it possible for a read of an actual register/memory unit in a multiprocessor computer to return an arbitrary value when it is concurrent with a write?

What about going to a lower level such as circuits/flip-flop?

In what sense, does a safe register exist?


texts: Does zero integrality gap imply zero duality gap for certain problems?

texts:
We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the relaxation, both admit integral solutions (zero "integrality gap"). I want to know if the converse holds, at least in some cases.

Suppose I have a 0-1 integer program $P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$, where the matrix $A$ is a $0-1$ matrix. Suppose the linear programming relaxation $P'$ of $P$ has an integral optimal solution. Then does the linear programming dual of $P'$ also admit an integral solution?

I would appreciate any counter-examples or pointers..


texts: Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

texts:
Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$, while minimizing the size of $S$.

From what I have checked so far, I got the following: There is this related problem of finding a $(k,r)$-center in a graph which is a subset $S$ of size at most $k$ such that all the vertices in the graph are at a distance of atmost $r$ from some vertex in $S$(here both $|S| \leq k$ and $r$ are parts of the input) for which Demaine et al. have a FPT algorithm for planar graphs. Otherwise the problem is $W[2]$-hard for even $r = 1$.

Is anything known about the exact complexity of $r$-domination problem for bounded tree width graphs or even just trees? (Is $r$-domination MSO definable? the usual $k$-dominating set problem is MSO definable -- which then would allow one to use Courcelle's theorem to conclude that there is a linear time algorithm for the problem). Are there any conditional hardness results known regarding this problem?


texts:
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(2k-1)$-approximate distance between any pair of  vertices in the graph.

At a fundamental level, this construction achieves a space-approximation trade-off --- one can reduce the space requirements at the cost of a lower "quality" of the solution.

  What other graph problems exhibit such a trade-off between space and approximation?

I am interested in the case of both static and dynamic, weighted and unweighted, undirected and directed graphs.

Thanks.


texts: NP-complete graph property that is hereditary, but not additive?

texts:
A graph property is called hereditary if it closed with respect to deleting vertices (i.e., all induced subgraphs inherit the property). A graph property is called additive if it is closed with respect to taking disjoint unions.

It is not hard to find properties that are hereditary, but not additive. Two simple examples:

$\;\;\;$ (1) The graph is complete.

$\;\;\;$ (2) The graph does not contain two vertex-disjoint cycles.

In these cases it is obvious that the property is inherited by induced subgraphs, but taking two disjoint graphs that have the property, their union may not preserve it.

Both of the above examples are polytime decidable properties (although for (2) it is somewhat less trivial). If we want harder properties, they could still be created by following  the pattern of  (2), but replacing the cycles with more complicated graph types. Then, however, we can easily run into the situation where the problem does not even remain in $NP$, under standard complexity assumptions, such as $NP\neq coNP$. It appears less trivial to find an example which stays within $NP$, but it is still hard.

  Question: Do you know a (preferably natural)  $NP$-complete graph property that is hereditary, but not additive?


texts: Counting vertex covers on a chain of k nodes that do not contain a sub-chain of length >=3

texts:
By a "chain of k nodes", I mean k nodes lined up like a linked-list:  o-o-o.....-o . By "do not contain a sub-chain of length >=3", I mean that no cover should contain two edges that shares a node. Lastly, we are interested in all such covers that meet this constraint, not just the optimal cover(s).

My current approach is as follows: Initialize two sets P = {1} and Q = {2} containing the first and second nodes respectively (labelled WLOG from left to right). Define N(P) and N(Q) to be the # of unique VC (satisfying sub chain constraint) that we can generate with P and Q. N(P) + N(Q) is what we want. Further, for any partial cover S ending with node i, N(S) = N(S U {i+2}) + N(S U {i+1, i+3}). I was curious if anyone knew what this count would analytically be in terms of k? Is it polynomial in k or exponential (or worse) in k?


texts:
Let $p_1,...,p_n$ be a list of numbers, each specified by $n^{O(1)}$ bits. Let $\mu = \sum_{i} p_i$ be the sum of all numbers in the list. I want to sample from the set $\{1,...,n\}$ where each $j$ is drawn with probability $p_j/\mu$.

I'm looking for a reference where the complexity of this problem is analyzed explicitly taking the bit size of the numbers into consideration?

I was only able to find references where the numbers $p_j$ are treated as ideal real numbers. In this case, on a turing machine operating over the reals, the complexity seems to be $O(n)$ pre-processing time and $O(\log n)$ per sample.


texts: How to define eta-equivalence for F-omega types?

texts:
There are (at least) two styles for defining a (declarative) equivalence judgement for a typed lambda calculus:

via a plain relation  $t_1 = t_2$,
via an indexed relation $\Gamma \vdash t_1 = t_2 : T$.

Barendregt [1] e.g. uses the simpler former style, while other sources often seem to be preferring the latter.

I have only seen the first style being used for the case of simple beta equivalence (as in Barendregt). Is it possible to use this style even in the presence of an eta-rule, esp considering that eta-expansion does not necessarily preserve well-formedness?

More specifically, I'm interested in the (simple?) case of eta-equivalence for F-omega types. Any pointers are welcome.

[1] H. Barendregt, Lambda Calculi With Types. In: Handbook of Logic in Computer Science, Vol 2. Oxford University Press 1992


texts: Probability of two vertices being connected by some path in a random directed graph

texts:
Define $G(n, p)$ as a random directed graph ($n$ vertices; we put edge between two vertices with probability $p$).

What are the known results for the following problem:

Fix two vertices $v$ and $u$. What is the probability that there is at least a path (of length at most $k$) between $u$ and $v$?  (clearly the result should be a function of $n$, $p$ and $k$). Upper-bound would work too, if there is no known exact answer.


texts: What is the minimum number of bits required to store a sudoku puzzle?

texts:
Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved sudoku puzzle.

I was wondering this, but I couldn't think of an answer that I was content with. A naive solution would use one byte for each cell (81 cells), totalling 648 bits. A more sophisticated solution would store the entire sudoku puzzle in a base-9 number (one digit per cell) and require $\lceil\log_2(9^{81}))\rceil = 257$ bits.

But it can still be improved, for example, if you know 8 of the 9 numbers in a 3x3 subgrid you can trivially deduce the 9th. You can continue these thoughts to the point where this question boils down to What is the amount of unique solved sudokus? Now you can use a huge lookup table that maps each binary number to a sudoku puzzle, but that wouldn't be an usable solution.

So, my question:

Without using a lookup table, what is the minimum amount of bits required to store a sudoku puzzle and with what algorithm?


texts:
I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas?
Thank you!


texts: What are good set size estimation algorithms for small sets (around 10-50 elements)?

texts:
I'm trying to implement an online distinct counting algorithm, and I have thousands of small sets of 32 bit IP addresses whose sizes I want to estimate with high accuracy (1-5%).

I came across quite a few algorithms such as linear counting$^1$, PCSA$^2$, HyperLogLog$^3$ etc. According to their papers, their space needed varies with relative error as $1/\epsilon^2$. For my purpose, this seems really wasteful e.g., PCSA needs > 10,000 bits when the set size is 50 and $\epsilon$ is 1%.

Is there any reason why in practice, we may not need that many bits? Is there any algorithm that uses little space to estimate the size of small sets with high accuracy?

Thanks!

References:

[1] Linear Counting: Kyu-Young Whang, Brad T. Vander-Zanden, and Howard M. Taylor. 1990. A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst. 15, 2 (June 1990), 208-229. DOI=10.1145/78922.78925 http://doi.acm.org/10.1145/78922.78925

[2] PCSA: Philippe Flajolet and G. Nigel Martin. 1985. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31, 2 (September 1985), 182-209. DOI=10.1016/0022-0000(85)90041-8 http://dx.doi.org/10.1016/0022-0000(85)90041-8

[3] HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm, by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Proceedings of the AofA07 Conference (Analysis of Algorithms-2007), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AH, pp. 127--146 (2007).


texts: efficiently computing a sum of products of polynomials

texts:
Let $F$ be a prime finite field. Let $d$ be a power of two dividing $p-1$. Suppose I have $d$ pairs of univariate polynomials $f_i,g_i$ over $F$ for $i=1,\ldots,d$. All have degree less than $d$.
I want to compute the coefficients of the polynomial
$$h(X)\triangleq \sum_{i=1}^d f_i(X) g_i(X) $$
I can do this in $O(d^2\cdot \log d)$ operations by computing each product using FFT techniques in time $O(d\log d)$ and then summing the $d$ products.
Can I do this in time $O(d^2)$ somehow? Is there an indication that would contradict some conjectured lower bound?
I don't mind computing $h$ in any basis, doesn't have to be the monomial basis.


texts: What is the relation/difference between axiomatic and denotational semantics one one side, and the data flow analysis(DFA) on the other sied?

texts:
I am supposed to write a small paper about DFA in OOP for a CS class in theory. But I am required to connect that (DFA) to axiomatic and denotational semantics!
I read few resources about axiomatic/denotational semantics but no one is talking specifically about their relation to Data Flow Analysis.
Can you please guide me about that, or at least guide me to a book, chapter or a paper that talks about that?


texts: Equivalence problem for one-counter automata

texts:
I know that the equivalence problem for deterministic one counter automata is decidable, however does anyone know whether it is decidable for all one counter automata or just the deterministic ones?

Any information would be useful, I don't know if this is an open problem or if it has a solution. If there is a known proof (of either decidability or undecidability) then a reference would be greatly appreciated.


texts:
I have the following problem which came as a subproblem in some work I was doing and I am completely stuck.
Note that I am interested in it only in terms of worst case time complexity (not heuristics or anything else).

Given is a set $\mathcal{P}$ of $m$ convex polygons with $n$ overall vertices.

PROB: Find the set $Z \subset \mathcal{P}$, such that for any $Q \in Z$, there exists a $P \in \mathcal{P}\setminus \{Q\}$ with $P$ contained in $Q$. (i.e. "Find the polygons which contain at least one polygon")

In the following example, the set Z would consist of the 4 highlighted polygons

Some thoughts I had were:

A first idea was to plane sweep with all vertices as events. Every time an event would come we would check the polygons it belongs to and mark them. When the event would be the end of a polygon we could verify that if this belongs to any polygon or not.
The problem is that a query event could take $O(m)$ as it could be inside $O(m)$ polygons (assuming an interval tree DS where an "all_overlap" operation takes $O(\min\{m,c\cdot \log m\})$ time, where $c$ is the number of overlaps - containing polygons). Moreover, I believe we can create a worst case instance where $O(n)$ events have $O(m)$ overlaps. So, with this approach it seems that we could end up with an $O(mn + n\log n)$ time complexity.
I started having some thoughts for a more elaborate plane sweep to use the pairwise polygon intersections but since this can be $\Theta(m^2)$ in the worst case, I didn't further look on that.
Another thought was to make an algorithm using range search queries for the convex polygons. If we triangulated every polygon, having $O(n)$ triangles, we could check the containment. Unfortunately, taking a "brief look", I didn't find very "positive" results for answering fast range queries with anything different than rectangles, e.g. triangles. Although I didn't yet delve very deep into it.

I would be extremely happy to have an $O((1+|Z|) n\log^2 n)$ time algorithm. I am not positive about that anymore. So, I would be happy with any algorithm or ideas how to further proceed.

Finally, and perhaps as a starting point, one could consider the simplified decision problem.

PROB*: Does there exist $Q \in \mathcal{P}$ such that there exists a $P \in \mathcal{P}\setminus \{Q\}$ with $P$ contained in $Q$.

What would be an efficient algorithm for that?


texts:
In Winskel's The formal semantics of programming languages 1993,   Ch14 Nondeterminism and parallelism  says

This  chapter  is  an  introduction  to  nondeterministic  and
parallel  (or  concurrent)  pr<r  grams and systems,  their semantics
and logic.  Starting with communication via shared  variables it leads
through Dijkstra's language of guarded commands to a language closely
related to Occam and Hoare's CSP, and thence to Milner's CCS. In the
latter languages  communication  is  solely  through the synchronised
exchange of values.  A  specification  language consisting of a simple
modal logic with recursion is motivated.  An algorithm is  derived
for  checking whether or not  a  finite-state  process satisfies  a
specification.  This  begins a study of tools for the verification of
parallel systems of the kind supported by the  Edinburgh-Sussex
Concurrency Workbench and the Aalborg TAV  system.  The chapter
concludes with an indication of other approaches and some current
research issues in the  semantics and logic of parallel processes.

Are CCS and CSP are still worth studying? Are they useful in real world, or can they be?   (I saw a course using that book as one of its textbooks talked about pi calculus instead of CCS and CSP.) If not, what should one study instead?


texts: Reference for computing the rank of a matrix in polynomial time

texts: In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as long as the algorithm is polynomial with respect to dimensions of the matrix and lengths of representations of the entries (I know that obtaining the best possible bounds is an active research area, as described here). I also know that Gaussian elimination can be made to work in polynomial time and that several other methods are possible (as discussed here). However, I'm not particularly concerned about which particular method is used, just that there exists a polynomial algorithm. I suppose what I'm ultimately looking for is a reference to a standard textbook or a classical paper, but as a person coming from a different field (mathematics), I'm not sure which source to cite. Any help would be very much appreciated!


texts: Which complexity information of Ising model is more important?

texts:
In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using Google scholar, it appears that the previous and weaker result has 647 citations while on the other hand the more recent and stronger result has 109 citations.

Shouldn't it be the other way round? Isn't a stronger result more useful?


texts: What is a good route for a math student to self study computer science systematically and efficiently?

texts:
I decided to ask this question after being attracted by how much one can do with the knowledge in computer science, including iOS application development, game(or mods) development, website creating, etc., but having trouble with matching what I learned with what I really understood.

Realizing the lack of knowledge in programming, I once decided to learn programming in a specific language, like Objective-C and Swift. After I tried every single textbook on OC programming, I found myself wasting time in the "explanation" part and getting lost with the real "theoretical" part. It seems to me that those textbooks prefer a long and loose explanation in describing a concept without telling me what exactly it is(Like the notion of "Object" and "Pointer") and skip the real important "thinking" before the implementation of the code. Although after many times of reading I could create a very simple application(like a simple calculator), I was still very lost in how it really works.

That reminds me how I began to learn mathematics. In middle school "function" is just "$y=f(x)$", where $f(x)$ can be $x^2$, $\sin(x)$, and other operations about $x$. However, now for me $f$ is a set of tuples satisfying the unique mapping property, or an arrow with domain and codomain. More generally, I can give a affirmative response to every question like "what is (the definition of) this?(in a math sentence.)" So I asked myself, "what is most basic among all subjects in computer science"?

Based on the belief that computer system and programming can be completely theoretical, I decided to learn from the very basic. That's when I began to have trouble because of the lack of knowledge in the computer science world. Where is the code for my programming environment?(For me, Xcode) and how can I understand it? What is a computer made of (up to the transistors), and how do them work together?
But then I found out that there is no book with the name similar to "how a computer works" that reach my satisfaction, which I thought is my vocabulary problem.

I hope that in the book I'm looking for, every keyword is rigorously defined, and without any waste of time in explaining what a notion "means" or how it is developed stage by stage historically. I expect that it gives only the goals(like the adding machine) and how to build it from the given definitions(a graph with the nodes of value "0" or "1"). Every textbooks in mathematics(like the GTM series) reach this goal, and for me, that is MUCH easier to read and understand. I think most of the math student like me will prefer this style of learning.

What is a good (book) route for a math student to self study computer science from the basic? I wish there are some theoretical textbooks that build the whole operation system, compiler, or some of this kind, that is readable to math students. Any answer would be much appreciated. Thank you.


texts: Completeness under injective Karp reductions

texts:
Karp reduction is polynomial time computable many-one reduction between two computational problems. Many Karp reductions are actually one-one functions. This raises the question whether every Karp reduction is injective (one-one function).

  Is there a natural $NP$-complete problem that is known to be complete only under many-one Karp reduction and not known to be complete under injective Karp reduction? What do we gain (and lose) if we define $NP$-completeness using injective Karp reduction?

One obvious gain is that sparse sets can not be complete under injective Karp reductions.


texts:
It is well-known in functional analysis that an inner product always induces a norm and a norm always induces a metric, and the reverse directions do not hold in general. I am wondering if a similar claim can be made about learning from features vs. from a metric (say, via a nearest-neighbor classifier).

For example, realizable SVM is a feature-based algorithm, but can be interpreted in the language of metrics as follows. Take the sample and construct the convex hulls of the positive and negative parts of the sample (either in explicit feature space or in the reproducing kernel Hilbert space). Then we can classify test points by their closest distance to either convex hull.

On the other hand, consider the edit distance over strings. One can certainly do supervised learning via nearest-neighbor methods, but feature-based learning runs into a problem: the edit distance only embeds into Hilber or $\ell_p$ spaces with a large distortion, potentially corrupting the data geometry before the learning process has even begun. (https://dl.acm.org/citation.cfm?id=1958047)

Has anyone ever tried to formalize this line of reasoning?


texts:
As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals  or the computation models over reals is not in such a case. We know Blum and Smales' model and model in the book Computable Analysis. And seemingly, model in Computable Analysis is consistent with the classic model, but the definition of computational complexity of reals can not transplanted into classic model.

How to judge the definition of computational complexity of reals is natural or suitable?

And how to transplant the definition of computational complexity of reals  into classic model?


texts: Hardness in P: methods to show optimality of $O(m^2n)$-like time?

texts:
In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in $O(|V|^{3-\epsilon})$ time" and others.

Now suppose we have a problem whose input data is naturally arranged in an $m\times n$ array, and there is a plausibly-optimal known $O(m^2n)$ algorithm solving it. Are there any techniques around that could be used to prove matching (conditional) lower bounds of this form?

The existing results seem to me to mainly focus on "1-dimensional" running times, i.e. proving optimality of time quadratic-in-input-length or cubic-in-input-length (or alternatively in the number of vertices of a graph, but assuming it to be either dense or sparse).


texts: Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

texts:
Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is poly-time solvable for degree-$3$ bounded graphs and is NP-complete for degree-$4$ bounded graphs. But I have not been able to find any proof for this anywhere. Is it true?

What is the minimum $d$ such that FVS in degree-$d$ bounded graphs is
NP-complete?


texts: SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?

texts:
Do we know of instances of $Max-2-Lin(\mathbb{Z}_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations?

Or if we specialize to Max-CUT do we know of graphs whose Max-CUT polynomial needs high SOS degree to be solved? (Or if we at least know of integrality gaps for it for high SOS degree)


texts: What's "pseudo time" when used in comparison with semaphores

texts:
I'm currently listening to Alan Kays' talk "Is it really complex or did we just make it complicated ?" (https://www.youtube.com/watch?v=ubaX1Smg6pY&= ) where he says that "semaphores were a bad idea and there was something called pseudo time that was superior" (at 51:40 on the linked video).
Maybe I misunderstood the word "pseudo time", but do you know anything about those ?


texts: Memory requirement for fast matrix multiplication

texts:
Suppose we want to multiply $n \times n$ matrices. The slow matrix multiplication algorithm runs in time $O(n^3)$ and uses $O(n^2)$ memory. The fastest matrix multiplication runs in time $n^{\omega + o(1)}$, where $\omega$ is the linear algebra constant, but what is known about its memory complexity?

It seems that it may be possible a priori that fast matrix multiplication consumes $n^{\omega}$ memory. Is there are any guarantee that it can be done in $O(n^2)$ memory? Is it the case that the currently-known matrix multiplication algorithms use $O(n^2)$ memory?

(I am actually interested in rectangular matrix multiplication, but I assume that the answer would be the same in that case as for the square case, and the square case is better studied.)


texts: Are the Actor Model and Process Algebra "equivalent"?

texts: I often see casual mention that the Hewit/Agha Actor Model is equivalent in capability to process algebra, like CSP, CCS and ACP. Ie, one can be implemented in the other. Is there a paper that actually contains the proof of this? I'm specifically looking for a citable reference.


texts: Vector Addition Systems with finite "obstacles"

texts:
A Vector Addition System (VAS) is a finite set of actions $A \subset \mathbb{Z}^d$. $\mathbb{N}^d$ is the set of markings. A run is a non-empty word of markings $m_0 m_1\dots m_n$ s.t. $\forall i \in \{0, \dots, n-1\}, m_{i+1}-m_i \in A$. If such a word exists we say that $m_n$ is reachable from $m_0$.

The problem of reachability for VASs is known to be decidable (but its complexity is an open problem).

Now let us assume that a finite set of forbidden markings (the obstacles) is given. I would like to know if the problem of reachability is still decidable.

Intuitively, the finite set of obstacles should interfere with paths only locally, so the problem should remain decidable. But it does not seem trivial to prove it.

EDIT. I will keep @Jérôme's answer as the accepted one, but I would like to add a follow-up question: what if the set of markings is $\mathbb{Z}^d$?


texts:
I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and also discusses on treewidth in isolation.

The book I found is Treewidth: Computations and Approximations, by Ton Kloks. This book approaches treewidth from a structural point of view (partial $k$-tree, chordal completion) and also algorithmic point of view. It covers treewidth computation and approximation in special graph classes, and talks about treewidth bounded graphs.

Is this book a must-read? Or is there any other choice out there?

I liked the game theoretic definition of treewidth in the survey Practical algorithms for MSO model-checking on tree-decomposable graphs, Langer et. al. It is equivalent to the traditional tree-decomposition based definition in a natural way (As a sidenote, now there is a game theoretic approach to MSO model checking).

Could you point out a book/paper on treewidth that keeps multiple appraches to it in mind?

Thank you


texts: Collision Attacks, Message Digests and a Possible solution

texts:
I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 certificate duplicate.

From what I can tell in the case of the postscript attack, specific data was generated and embedded within the header of the postscript (which is ignored during rendering) which brought about the internal state of the md5 to a state such that the modified wording of the document would lead to a final MD equivalent to the original. The X.509 took a similar approach where by data was injected within the comment/whitespace of the certificate.

Ok so here is my question, and I can't seem to find anyone asking this question:

Why isn't the length of ONLY the data being consumed added as a final block to the MD calculation?
In the case of X.509 - Why is the whitespace and comments being taken into account as part of the MD?

Wouldn't a simple processes such as one of the following be enough to resolve the proposed collision attacks:

$MD(M + |M|) = xyz$
$MD(M + |M| + |M| * magicseed_0 +...+ |M| * magicseed_n) = xyz$

where :

M : is the message
|M| : size of the message in bits
MD : is the message digest function (eg: md5, sha, whirlpool etc)
xyz : is the pairing of the acutal message digest value for the message M and |M|. <M,|M|>
$magicseed_{i}$: Is a set of random values generated with seed based on the internal-state prior to the size being added.
'+' : is a concatentation operation A+B+C = ABC

This technqiue should work, as to date all such collision attacks rely on adding more data to the original message.

In short, the level of difficulty involved in generating a collision message such that:

It not only generates the same MD
But is also comprehensible/parsible/compliant
and is also the same size as the original message,

is immensely difficult if not near impossible. Has this approach ever been discussed? Any links to papers etc would be nice.

Further Question: What is the lower bound for collisions of messages of common length for a hash function H chosen randomly from U, where U is the set of universal hash functions ?

Is it $1/N$ (where N is $2^{|M|}$) or is it greater? If it is greater, that implies there is more than 1 message of length |M| that will map to the same MD value for a given H.

If that is the case, how practical is it to find these other messages? bruteforce would be of $O(2^N)$, is there a method of time complexity less than bruteforce?

Links:

Postscript: http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html
X.509: http://www.win.tue.nl/~bdeweger/CollidingCertificates/

Note: This question is NOT as easy as it seems. Please read it very carefully and make sure you have understood exactly what is being asked. The answer will require understanding of martingales and distribution ensembles. If you are unsure what these are or how they apply to this particular problem then please do not post answers. Prior knowledge of this class of attack is required, please access the links above and the following: csse question. Please DO NOT focus on answers that relate to generating messages of length different from the original message as any such solution is invalid.


texts: How to specify and verify Horn clauses (logic programming programs)? Semantics of Horn clauses

texts: There are lot of applications of Horn clauses (notable examples include use of rules in cognitive architectures and knowledge bases, as well as use of rules in business rules programs). Are there formal methods that can help specify and verify Horn clauses. Is there semantics of Horn clauses. One can perceive Horn clauses as something similar to programming code of traditional programming languages and therefore one can expect the denotation, operational and similar semantics as well for Horn clauses.


texts: Nondeterministic speed-up of deterministic computation

texts:
Can nondeterminism speed-up deterministic computation? If yes, how much?

By speeding-up deterministic computation by nondeterminism I mean results of the form:

  $\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$

E.g. something like

  $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

What is the best known speed-up result of deterministic computation by nondeterminism?
What about $\mathsf{\Sigma^P_kTime}(n)$ or even $\mathsf{ATime}(n)$ in place of $\mathsf{NTime}(n)$?

Assume that complexity classes are defined using multiple-tape Turing machines
to avoid the well-know peculiarities of
the sub-quadratic time single-tape Turing machines.


texts:
I would be interested in some References (books or articles) concerning an answer to the following question :

what is more difficult to calculate from the viewpoint of a computer : the "sum" or the "maximum" of a finite set of numbers ?

My guess is that "sum" and "maximum" are of the same level of difficulty, but I would like very much to know References concerning this question.

Thank you in advance.

George


texts: Reference Request: Application of Block Designs to Software Testing

texts:
I've started looking at incidence structures and combinatorial designs (possible motivation: to upper-bound some structures in generalized self-assembly), and the Wikipedia article makes the following interesting-yet-unexplained statement: block designs have application to software testing.  (The Wikipedia page with the claim is here).

My google-fu doesn't pick up a good reference for this application.  Can anyone give me a lead?


texts: Complexity of recognizing generalized graph join

texts:
A join of two graphs is the union of both graphs with additional edges such that every vertex of the first graph is connected to every vertex of the second graph. There is a generalization of this, which I will call the $G$-join. For a given graphs $G$ and $G_1, G_2 \cdots G_{v}$, where $v$ is the number of vertices in $G$, the $G$-join of the graphs is the union of all of them such that every vertex of $G_u$ is connected to every vertex of $G_v$ if there is an edge between $u$ and $v$ in $G$. So the original graph join is just a $P_2$-join.

How fast can we recognize whatever a graph is $G$-join? What if we fix $G$ to a specific graph?

The only algorithm I could think of is the obvious one, iterate over all partitions and check the edges.


texts:
It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are

Quantum computation
Statistical mechanics results used in complexity analysis/heuristic algorithms.

So my question is are there any major areas I am missing?

My motivation is very simple: I'm a theoretical physicist who has come to TCS via quantum information and I am curious as to other areas where the two areas overlap.

This is a relatively soft question, but I don't mean this to be a big-list type question. I'm looking for areas where the overlap is significant.


texts: Language and automata textbook, free or low cost?

texts:
I'll be teaching a standard undergraduate class on languages and automata next semester, and would prefer to use a legitimate free or low-cost text. Any suggestions?

I love the Sipser text but the latest edition costs $196, which is hard to say with a straight face in the age of free courses.


texts: About estimating escape time of gradient Langevin dynamics

texts:
I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly different notation than them.

Here we are given $F : \mathbb{R}^d \rightarrow \mathbb{R}$ a convex, differentiable and $L-$smooth function with a minimizer at $x^*$ and 3 constants : $r$ and $C_\xi$ and $i_{max}$ (a positive integer). Now for $\xi_{t,1}$ a sequence of bounded random variables and $\xi_{t,2}$ a sequence of Normally distributed random variables we have the following dynamics happening,

$$x_{t+1} = x_t - \eta_t (\nabla F(x_t) + \xi_{t,1}) + \sqrt{\eta_t} \xi_{t,2}$$

which starts from $x_0$ s.t $\Vert x_0 - x^* \Vert \leq r$

Now they consider a coupled toy Markov chain $x'_t$ s.t $x'_0 = x_0$ and,

$$\text{if } \Vert x_t' - x^* \Vert \geq r \text{ then } x'_{t+1} = x'_t  $$
and $\text{if } \Vert x_t' - x^* \Vert < r \text{ then } x'_{t+1} = x'_t - \eta_t (\nabla F(x_t') + \xi_{t,1}) + \sqrt{\eta_t} \min (C_\xi, \Vert \xi_{t,2} \Vert) \frac{\xi_{t,2}}{\Vert \xi_{t,2} \Vert} $

Hence it seems that the primed sequence is designed s.t it never comes back into the ball once it leaves the interior of the $r$ sized ball around the global minimum of the function.

Now the main technical claim they make to relate the primed and the unprimed sequence is this : say the event $E := \{ \exists i \in \{1,\ldots,i_{\max}\} s.t \Vert x_i - x^*\Vert > r\}$ then some curious union bounding is giving them,

$$\mathbb{P} \left [ E \right ] \leq \sum_{i=1}^{i_{max}} \left ( \mathbb{P} [\Vert x_i'-x^*\Vert^2 \geq r^2] +  \mathbb{P} [ \Vert \xi_{i,2} \Vert \geq C_\xi ] \right )$$

Can someone kindly explain why is the above inequality true?


texts: Oracle complexity classes and hardness under different notions of reduction

texts:
Let C be a complexity class, and let L be a language such that PC ⊆ PL. Then it’s natural (and easy to prove) that L is C-hard with respect to Cook reductions (polytime Turing reductions).

This fact is not (known to be) true for Karp (polytime many-one) reductions: for instance, we have PNP ⊆ PUNSAT, but UNSAT is not NP-hard under Karp reductions (unless NP = coNP). On the other hand, most of the times we use Karp reductions to order problems by hardness, since they seem to provide a finer structure.

  Are there some “natural” or “interesting” sufficient conditions for PC ⊆ PL to imply that L is C-hard under Karp reductions?

If that implication held for all C and L, then the two notions of reducibility would coincide (see Tsuyoshi Ito’s comment below); I would be interested in knowing about any interesting class of problems where this happens, if any is known.


texts: Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?

texts: Brzozowski's method of derivatives is a very pretty technique for building deterministic automata from regular expressions in a nicely algebraic way. I've worked out some cute generalizations of this technique to handle some larger classes of grammars, but the algorithms are straightforward enough that it seems quite possible that they've been discovered before. But Googling references to descendants of this technique doesn't seem to turn up much. Anyone know of anything?


texts: Algorithm for Max Network Flow with lower bounds and its complexity

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


texts: PTIME or NP-Hardness of stochastic objective function

texts:
I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is a much simpler setting where showing hardness should be easier. Please let me know if I should amend the original question instead.

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. We will restrict $G$ to be a cycle where every vertex has degree $2$ (and $m = n$).

The challenge is to assign weights $w_e$ to each edge to maximize the
objective function $E = \sum_{e = \{i,j\}} w_e \Pr[X_i + X_j \geq w_e]$ where $\Pr[X_i + X_j \geq w_e]$ denotes the probability that that the sum of values taken by vertex $i$ and $j$ is greater than $w_e$. The additional constraint is that the weights $w_e$ need to be sub-additive, i.e., for any two edges $e'$ and $e''$ that "cover" edge $e$ meaning $e'$ and $e''$ include the vertices that make $e$, it holds that $w_e \leq w_{e'} + w_{e''}$.

Observe that the deterministic version where $p_i = 1$ is trivial. Any suggestions on possible directions for hardness or PTIME algorithm would be very helpful!


texts:
Let matrix $M \in \{0,1\}^{r \times s}$ ($s>r$), let function $f:\Bbb Z^{} \rightarrow \pm1$ and let $\alpha \in \Bbb Z \cap (0,s)$ be given.

Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ with $v=uM$: $|f(v)| = {\sum_{i=1}^{s}f(v_{i})^{}} \geq \alpha$?


texts: One-way randomized complexity of (variants of) Gap-Hamming-Distance?

texts:
The $\textsf{GapHammingDistance}$ problem over $\{0,1\}^n$ is defined as follows: Alice (resp. Bob) is given an input $x\in\{0,1\}^n$ (resp, $y\in\{0,1\}^n$), under the promise that their Hamming distance satisfies
$$
\operatorname{d}_H(x,y) \in \left\{0,\dots,\frac{n}{2}-\sqrt{n}\right\}\cup\left\{\frac{n}{2}+\sqrt{n},\dots,n\right\}.
$$
Their goal is to decide, wth probability at least $2/3$, whether $\operatorname{d}_H(x,y) \leq \frac{n}{2}-\sqrt{n}$; or $\operatorname{d}_H(x,y) \geq \frac{n}{2}+\sqrt{n}$.

A lower bound of $\Omega(n)$ is know for the one-way communication (randomized) version of this problem, as well as for the unbounded two-way communication.

Now, I am interested in the following two variants: is a linear lower bound (or a lower bound) known for the one-way randomized communication complexity of this problem, under the additional constraints:

(dominated version) $y \preceq x$, i.e. $y_i \leq x_i$ for all $i\in[n]$; or
(one-sided version) $\operatorname{d}_H(x,y) = \frac{n}{2}$; or $\operatorname{d}_H(x,y) \geq \frac{n}{2}+\sqrt{n}$

(I am mostly interested in the first)

I apologize if this is obvious, or follows easily from the proofs of the lower bounds for Gap-Hamming of Woodruff or Jayram-Kumar-Sivakumar; or the more recent ones for two-way communication. As far as I could tell, these proofs move the problem to the continuous, Gaussian setting, and it was unclear to me how to get the continuous version of the variants above.

The One-Way Communication Complexity of Hamming Distance, by T. S. Jayram, Ravi Kumar, and D. Sivakumar (2008)
The Communication Complexity of Gap Hamming Distance, by Alexander A. Sherstov (2012)

Edit: As pointed out in the comments by Denis Pankratov, the first variant admits a trivial $O(\log n)$ upper bound (sending $\lvert x\rvert$ to Bob is enough).


texts: Complexity of the Fisher-Yates Shuffle Algorithm

texts:
This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).

In each iteration i, a random integer is chosen between 1 and i. Simply writing the integer in memory is O(log i), and since there are n iterations, the total is

O(log 1) + O(log 2) + ... + O(log n) = O(n log n)

which isn't better the the naive algorithm. Am I missing something here?

Note: The naive algorithm is to assign each element a random number in the interval (0,1) , then sort the array with regard to the assigned numbers.


texts:
We know that the existence of good pseudorandom generators (PRGs) does not only imply $P=BPP$, but also $PromiseP=PromiseBPP$.

Let us assume $PromiseP\ne PromiseBPP$. Then good PRGs do not exist. However it is still possible that $P=BPP$ holds. If good PRGs do not exist then does $P=BPP$ imply $P=NP$ or is there a possibility $P\neq NP$ still might be true?

Is it possible to have $P=BPP$ without good PRGs and with $P\neq NP$ and with $PromiseP=PromiseBPP$?


texts: Calculus of Constructions: compress expression to its smallest form

texts:
I'm aware that the Calculus of Constructions is strongly normalizing, meaning every expression has a normal for that cannot be beta,eta-reduced further. So in fact this is the most efficient expression that calculates the same value as the original expression.

But in certain cases, normalization may reduce a small expression to a huge expression (in terms of size).

Is there a smallest-form of expressions? A form that calculates the same value with the smallest size.

In other words, instead of a time-efficient normal-form, a space-efficient one.


texts: Can type inference be classified in two groups: unification-based and control-flow-based?

texts:
I recently came across the 1995 paper Safety analysis versus type inference (pdf link) by Palsberg and Schartzbach that contrasts unification-based type inference and static analysis methods based on control-flow analysis. According to the paper:

In unification based type inference each identifier is related to a type variable ranging over type schemes, such as $int$ and $\forall a b . a \rightarrow b$. In control-flow static analysis the identifiers get related to variables ranging over what primitive types and other values in the source program can flow into the identifier.
Unification-based type inference is "local" and can be performed one module at a time. Control-flow analysis tends to be global and require the whole program to be analyzed at once.
Damas-Milner unification is a linear time algorithm (for typical programs) while control-flow analysis tends to have worse case running times that are cubic or worse (and at least quadratic in practice).
Control-flow analysis can reason about program safety more precisely than unification-based inference (for example, it can detect some instances of dead code)

My question is: is this classification complete or are there other kinds of type inference that they did not mention?


texts: Is the Cheeger constant $\mathsf{NP}$-hard?

texts: I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for this statement. Whom should I give credit for it? In an old paper (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar only proves this assertion "for graphs with multiple edges".


texts:
The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann.
$$\alpha_1(n) = [n/2]$$
$$\alpha_2(n) = [\log_2 n]$$
$$\alpha_3(n) = \log^* n$$
$$...$$
$$\alpha_k(n) = 1 + \alpha_k(\alpha_{k−1}(n))$$
and
$$\alpha(n) = \min\{k: \alpha_k(n)\leq 3\}$$
[Notation: [x] means that we round up x to the nearest integer, while log∗ is the iterated log function discussed here: http://en.wikipedia.org/wiki/Iterated_logarithm ]

My question is: What is the function
$$k(n) = \min \{k: \alpha_k(n) \leq k\}$$
Clearly $1\ll k(n) \leq \alpha(n)$. What tighter bounds can one give on $k(n)$? Is $k(n) \leq \log\alpha(n)$?


texts: Does $\Sigma(n+1)-\Sigma(n)$ eventually dominate every computable function?

texts:
Let $\Sigma$ be Radó's Busy Beaver function, and define  $\Delta(n) \ = \ \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$.

Question: Does the function $\Delta$ eventually dominate every computable function $f: \mathbb{N} \rightarrow \mathbb{N}$?

Sources: "A note on Busy Beavers and other creatures" (1996), by Ben-Amram, Julstrom, and Zwick, contains the conjecture that for any computable function $f$, there exists a constant $N_f$ such that $\forall n \gt N_f, \Sigma(n+1) > f(\Sigma(n))$. In support of this they prove the weaker result that for any computable function $f$, $\Sigma(n+1) > f(\Sigma(n))$ for infinitely many values of $n$. (Considering $f(x) = 2x$, for example, the conjecture implies an affirmative answer to the title question.)

NB: This question is the most elementary case of one that I posted on math.SE two weeks ago, but which has received no satisfactory answer.


texts: What are good journals for publishing a paper?

texts: I wish  to publish my research work. But do not have a good idea about how and where to publish.


texts: Non-deterministic logspace with two-sided error

texts:
The class BPL is the set of all problems solvable by a Turing machine running in logarithmic space and polynomial time with two-sided error; that is, if $x\in L$ then the machine accepts with probability at least $2/3$, whereas if $x\notin L$ it accepts with probability at most $1/3$.

What is the immediate non-deterministic complexity class containing BPL? That is, what is the logarithmic-space analog of MA? It seems that NL cannot suffice in this case, and DSPACE($\log^2(n)$) seems too far away up the ladder.
Can one define this class using the following?
We have a read-once "witness" tape of polynomial size, a read-once "random" tape of polynomial size, a read-only input tape, a write-only output tape, and a read-write logarithmic-size work tape.  The verifier then has to decide with completeness/soundness error at most $1/3$.

At first sight, this might seem reasonable.
Yet, unfortunately it already contains iterated multiplication
of integer matrices (which is complete for the class DET):
Given a matrix $A$, compute $A^n$:
We simply ask the prover to provide the sequence of matrices $A,A^2,...,A^n$,
we then randomly choose a matrix $A^i$, and verify that $A^i = A^{i-1} \cdot A$,
which can be done in logspace.
Hence, the question is, is the bounded-error class simply "not-interesting" in the restricted memory model, because it seems to group together space-"hard" with space-"easy" problems?


texts: Syntactic characterisation of the intersection of CTL and LTL

texts:
The Baier and Katoen textbook references this paper

  E. M. Clarke and I. A. Draghicescu. Expressibility results for
  linear-time and branching-time logics, pages 428–437. Springer Berlin
  Heidelberg, Berlin, Heidelberg, 1989.

to say that, given a CTL formula P, if there exists an equivalent LTL one, it can be obtained by dropping all branch quantifiers (i.e. A and E) from P.

Is there a syntactic criterion that provides a guarantee that if a CTL formula passes the test, then an equivalent LTL formula does exist?


texts: Semantic distance between excerpts of text.

texts:
I'm wondering how far along the natural language processing is in determining the semantic distance between two excerpts of text.

For instance, consider the following phrases

Early this morning I got up and washed my car.
I cleaned my truck up this morning.
Bananas are an excellent source of potassium.

Clearly (to the human reader) the first two statements are much more similar to one another than they are to the third statement.  Does there exist any theory that would allow a computer to draw the same conclusion?  What about if we allow longer excerpts such as new articles?

Meta info: this is my first post here, so feel free to direct me to a better forum for asking such a question if this isn't where I should be.  Also, feel free to retag my question with anything more appropriate.


texts: Complexity class of MCS and relation to #p

texts:
I was looking for the complexity class of computing MCS:
Given a boolean formula $\mathcal{F = c_1 \wedge c_2,...,\wedge c_m}$ represented in CNF, a MCS is a subset of the set of clauses $\mathcal{C}$ such that $\mathcal{F} \backslash \mathcal{C} \in SAT$ but $\forall c \in \mathcal{C}, F \backslash(\mathcal{C}\backslash c) \in UNSAT$.
My first question is to which complexity class does this problem belong?
Second, what is the relation between this complexity class and $\sharp P-complete$ problems? i.e. does it make sense to use MCS in order to solve problem which is in sharp p complete?


texts: Efficient synchronization of two instances of an ordered list

texts:
What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move items in the list. Occasionally they will be online to synchronize the list. The algorithm should minimize the amount of changed items or "diffs" that need to be communicated.

For an unordered list we would simply use a modification timestamp and UUID for each item to detect edits respectively inserts/deletions. But what data structure can we use for an ordered list? Using an integer rank would require renumbering all successors after an insert, and thus result in many "diffs" when comparing items in both lists. Using a floating-point rank (having the average of the predecessor and successor ranks) would have accuracy problems after inserting many new items.

Using a doubly linked list (i.e. referencing the UUID of the predecessor and successor item) would result in two changed items and one new item for each insert, thus 3 "diffs" when comparing items in both lists.

Any suggestions, pointers to literature or Google search terms about this subject?


texts:
I am interested in the set of the variables that satisfy the following properties. I would like to find a proper name for them.

We assume that a program $\phi$ has a set of variables $v_0, \ldots, v_n$. I am interested in a subset $S$ of $\{v_0; \ldots; v_n\}$, that informally speaking impacts the execution of the program (i.e., any execution of its statements). For instance

1) For the statement $v_0 := v_1$ that may be executed, $v_1$ impacts the execution of the statement. Thus, $v_1 \in S$ and $v_1 \in SY$.

2) For the statement $v_0 := v_1 * 0$ that may be executed, $v_1$ impacts the execution of the statement, because if $v_1$  is a string value, the multiplication of string and $0$ raises a type error. Thus, $v_1 \in S$ and $v_1 \in SY$.

3) In the statement "If true Then $v_1$ := 1 Else $v_1$ := $v_2$ End", $v_2$ does NOT impact the execution of the statement, because the else branch of the statement will never be executed; the value of $v_2$ will never be read here. Thus, $v_2 \notin S$, but $v_2 \in SY$.

I will define the semantics properly, but before that I would like to find a proper name for the set $S$ that fits the convention. I am thinking of read variables? input variables? possible input variables? precedent variables? dependancy variables? or supporting variables?

Could anyone help?

Edit 1:

Thanks for all the comments, they are really helpful. I decide to edit the OP to make the question clearer.

Actually, I planed to introduce the notion of a set S about semantics, and then another set SY about syntax that is always a superset of S (because S is hard to analyse). Then, I will make a static analysis to over-approximate SY, thus it over-approximates also S. My question here is about a consistent terminology about S and SY (for the case of read/input).

I have added the case for SY in the 3 examples above. You mentioned another 2 examples:

4) For "If factorial(3)==6 Then v_1 := 1 Else v_1 := v_2 End" (babou), we have $v_2 \notin S$ and $v_2 \in SY$.

5) For "x := x" (Martin Berger), one understanding is that the value of x is first still read, then be assigned to x, so $x \in S$; another understanding is that the value of x does not impact the execution of this statement, so $x \notin S$. I will be OK with both of them (though personally I prefer the latter), as long as if I give a terminology and a definition to S, it is consistent for all the examples. In any case, based on the syntax, we always have $x \in SY$.

Regarding "live variables" (Klaus Draeger), indeed, as babou understood, I am not concerned about "a point in the program regarding what variables are still be needed to finish execution from that point".

Regarding "use-define or use-definition" (babou), from that web page, my understanding is UD is about syntax, and it is what I am going to do with SY (e.g., see what is on the left-hand/right-hand side of an assignment). If I call SY used variables, what should I call S?


texts: Constructing uniquely satisfiable formulas

texts:
Unique SAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. I recall reading that P=NP iff Unique SAT is in P (I don't remember where I read it. Notice that Unique SAT is CoNP-hard and Unique SAT= SAT\ Double SAT where Double Sat={$\phi$| $\phi$ has two or more satisfying assignments})

I'm looking  for an efficiently computable function $f(s_n)= \phi$  such that formula $\phi$ is uniquely satisfied by assignment $s_n$ where $n$ is the number of variables.

Also, Can $f$ be made a bijection?

Edit 1: Input is a binary string $s_n$, output is a 3SAT formula in CNF.

Basically, I'm looking for an efficient algorithm that computes $f$. Ideally, such algorithm would allows us to construct hard instances for Unique SAT.

EDIT 2: I'm seeking an algorithm that is able to generate all uniquely staisfiable instances not just the easy cases given so far.


texts: Formal Definition/counter part in mathematics for “Objects” of Object Oriented Models

texts:
This is a question I asked in mathematics SE forum, and I was referred here. So here is the question-

I'm a newbie in both formal mathematics and theoretical computer science, so please bear with me if you find my question is not properly framed. Object Oriented Modeling seems very useful in defining complex interactions when simulating real world. But it's mostly used in programming. I was wondering if we have a similar concept in mathematics. When we're doing programming, we can understand the concept of "Objects" and "Object Oriented Programming" and just implement it. But do we have formal definition of "Objects" in terms of Set Theory? Or for that matter, any other formal mathematical theory?

Can we implement/ formally define three primary object orient modeling concepts- 1. Encapsulation 2. Inheritance 3. Polymorphism

I know question is too broad, but would really appreciate if you can provide some pointers as well so that I can understand these concepts better.


texts: Proof Complexity and Circuit Lower bound for coNP

texts:
I have two questions

(1)Circuit lower bound for coNP

TAUT is a set of formulae such that any formula in TAUT is satisfied for all boolean assignments.
UnSAT is the complement problem of SAT.

It is known that if NP$\neq$coNP then P$\neq$ NP, and that solving NP vs coNP problem is harder task than proving circuit lower bound of NP-complete problems.

Is the following statement true?

Proving NP is not equal to coNP by showing a super-poly lower bound of proof size is "harder" task than deriving super-poly circuit lower bounds for a coNP-complete problem such as TAUT or UnSAT.

I think that this is true because NP and coNP has a "symmentric" relation.

(2)Uniform theory of  proof complexity

There are two streams of circuit complexity. First one is concrete complexity lower bounds for Non-uniform models like Sipser's PARITY lower bounds for constant depth circuit. Second one is simulation based lower bounds which is intensively argued in a book of Introduction to Circuit Complexity: A Uniform Approach by Vollmer.

Can we construct a simulation based uniform theory of proof systems and deriving structural separatins beween two classes of proof systems ?


texts: Expected running time of Clique on uniform graph

texts:
Problem:

Input is (G, k) where

k is chosen uniformly from [1..n]
G is chosen by, for each edge, flipping an independent coin, and adding the edge to G w/ prob 1/2

Question: Does G have a clique of size k?

We want to solve this in expected time n^{2 log n}.

What I currently know:

There are papers from 1976 proving that the expected size of the clique in a random graph (as described above) is approximately log n).

For k < 2 log n, I can just brute force the entire graph in n^{2 log n} time.

Also, by the union bound, the probability of having a clique bigger than 2 log n is ~ (e / k )^{log n}.

However, I need to push that probability down to something that looks like 2^{-n^2} (the time required to brute force the entire graph.)

Questions:

1) Should I go read the Bollobas /Erdos (Cliques in random graphs), or is there an elementary way to prove this without citing their theorems?

2) If there ia an elementary way; what is it?

Thanks!


texts:
Original question:

Base problem:
Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose subsets
$s_i$ ($i=1,...,N$) from $A$. Elements cannot be repeated within any sets, e.g. $|s_i \cap A| = |s_i|$, where
$|.|$ stands for set cardinality. The cardinalities of sets $s_i$ may differ. The problem is to find sets $s$
composed from $A$ so that

i) $|s_i \cap s| \ge p|s|$, for all $i=1,...,N$, where $p\in [0,1]$ is fixed.

ii) $|s|$ is maximal.

First variant:
Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose sets
$s_i$ ($i=1,...,N$) from $A$ so that $|s_i \cap A| = |s_i|$,
that is, an $s_i$ set contains different elements. We also compose sets
$c_j$ ($j=1,...,M$) from $A$ so that $|c_j \cap A| = |c_j|$,
that is, a subset $c_j$ contains different elements. The cardinalities of the sets $c_j$
may differ.
The problem is to find sets $s$ composed from $A$ so that

i) $|\{i : |s_i \cap s| \ge p|s|\}| \ge qN$, where $p,q\in [0,1]$ is fixed.

ii) $|\{j : |c_j \cap s| \ge p|s|\}| \le q'M$, where $p,q'\in [0,1]$ is fixed.

iii) $|s|$ is maximal.

Interpretation for better understanding:
The $a_k$ elements are different mutations that we can represent e.g. with different
natural numbers. We have samples for two populations,
$\{s_i\}$ are the diseased persons, $\{c_j\}$ are the average ones, and we know
that $q'*100\%$ is the presence of the disease on average. We want to find characteristic mutation patterns (sets $s$)
that are characteristic for the diseased (at least $q*100\%$) but less characteristic (only up to $q'*100\%$) for the average population.
We say that $s$ is characteristic if at least its $p*100\%$ portion appears in a diseased person.

We would need known theoretical results, complexity of the algorithm and algorithmic approaches for the search.

Question 2 (new constraint added):

Jukka Suomela has given a correct answer for the Base problem in the Original question. Regarding his answer and also since from practical point of view it is reasonable, an extra constraint can be added to the problem as:

In Base problem:

iii) $|s| < |s_i|$, for all $i=1,...,N$.

In First variant:

iv) $|s| < r|s_i|$, for all $i=1,...,N$, where $r\in [0,1]$ is fixed.

The questions regarding the problems remain the same.

Interpretation for better understanding of this new size constraint:
We can estimate the number of mutations for a person to be approx. 1 million (that is, $|s_i|,|c_i| \approx 10^6$), while disease-sepcific mutation patterns are expected to be much smaller (say $|s|\approx 50$, but we do not know). This is the reason for the size constraints for $s$ in the problem.


texts: Running time of Tarski Quantifier Elimination

texts:
I'm looking for some formula/expression in a citable resource, that gives the running time for Tarski's quantifier elimination.

In my search, I only found the statement "it's not elementary" on several pages and papers.
But given the explanation on https://en.wikipedia.org/wiki/ELEMENTARY, this could allow for a "power tower" like $\exp^n(2) = \exp(...(\exp(2))$.

Especially from the view of parametrised complexity, this would be interesting.

I'm aware, that these problems can also be solved via Cylindrical Algebraic Decompositions, but I'am really interested in the running time of the original method.

The comments already mention how the formula roughly looks like, but don't give a source.


texts: Determining how n-tuples are sorted as you search them?

texts:
I have a sorted list of $N$ n-tuples, but I do not know exactly how they were sorted. The person who sorted them did so by lexicographically ordering some permutation least-to-greatest. For example, if I see the list [(53,10),(10,53)], I can conclude that they must have been swapping the elements before comparing them. If I see the list [(1,2,3),(10,20,0),(2,30,20)], I can conclude that they must have permuted the tuples so that the second element was first.

It takes $\log_2 n! \approx n \log_2 n$ bits to describe the permutation, and I would expect to discover one bit with every comparison. If that's true, then it seems like there could be a manageable algorithm for searching lists that have been sorted in an unknown way. What is the complexity of searching this kind of list? What algorithm might be able to achieve it?


texts: Data structures in programming language with linear types

texts:
Assume we are dealing with a programming language that has support for linear types (terms of linear type can be used at most once, so to say). This allows for treating some computational effects (such as mutation, even changing the type of the operand) in a way that is problematic for languages, the type systems of which operate only on "eternal truths".

Many data structures can be characterized with inductive types (lists and trees are canonical examples). If we add linear inductive types to the mix, we can also handle mutable data structures.

However, it is not clear to me how to represent data structures that exhibit sharing and cyclic references in a programming language with linear types (examples of such data structures are DAGs and other graphs, represented by adjacency lists or something else, cyclic lists). Can we do that? If it isn't possible, in which way should we extend the language so as to accommodate such data structures?

The most involved example I've found so far is a doubly-linked list. Are there other examples?


texts:
Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function.  I want to find the smallest $x$ such that $f(x) \ge 1/2$.

If I had a way to compute $f(x)$ given $x$, I could simply use binary search on $x$.  However, I don't have a way to compute $f(x)$.  Instead, I have a black box that, on input $x$, flips a biased coin and outputs 1 with probability $f(x)$ and 0 with probability $1-f(x)$.  I can invoke the black box as many times as I want.

I'm looking for a query-efficient strategy to approximate $x^* = \min \{x : f(x) \ge 1/2\}$.  Is there an efficient algorithm?  I would be happy with strategies where we assume a fixed upper bound on $f'(x)$.

Informally, we can summarize the problem as: I have a coin whose heads probability depends in some unknown but monotonic way on a parameter; how can I choose the minimum value of that parameter to ensure the coin is biased in my favor?

A naive approach is to estimate $f(x)$ for any $x$ by invoking the black box $k$ times on the same input $x$, then use binary search with this estimator.  However, I suspect this makes more queries than necessary.  Intuitively, it makes many queries in regimes where $|x-1/2|$ is large, and the estimator for $f(x)$ doesn't use information from the black box on queries $x'$ that are near to $x$.

I suspect something like the following might be better, for some constant $1/2 < \alpha < 1$:

Set $x := 1/2$ and $d := \alpha$.
Repeat some fixed number of times:

Query the black box on $x$.  If it returns 1, set $x := x + d$, otherwise set $x := x - d$.
Clip $x$ to the range $[0,1]$.  Set $d := \alpha d$.

However I'm not sure how to set $\alpha$ or how to analyze this approach.  (Note that if $\alpha=1/2$ and the black box returned whether or not $f(x)\ge 1/2$, this strategy would devolve to binary search.)

Is there a good way to choose $\alpha$?  Or, is there a better strategy?