texts: Natural Language Processing. Where to start?

texts: Natural Language Processing is an area which interests me. I know little about it and I'm hoping somebody can suggest a starting point. Basically I'd like to develop a search algorithm specific for natural languages. One that deals with ambiguities in an intelligent fashion. Where would be a great starting point? Can anyone recommend some good papers or other resources to help me get started?


texts: kmeans++ for arbitrary metric spaces and general potential function

texts:
I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question can be answered.

I found two versions of the paper (which I find contradictory):

http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf
https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf

I have a problem with section 5 ("Generalization") of the paper. The section describes a generalization of the kmeans++ algorithm for an arbitrary metric space with a general potential function $ \Phi^{[\ell]} \equiv \sum_{x \in \mathcal{X}} min_{c \in \mathcal{C}} \| x-c\|^{\ell}$, where $||x-c||$ denotes the distance in any metric space, $\mathcal{X}$ is the data-set, and $\mathcal{C}$ is the center set of size $k$.

Consider Lemma 5.3, of the first version. It says that
-"For a cluster $A$, if we choose a point $p$ uniformly at random, then the expected cost of the cluster(with $p$ as a center) is at most $4 \cdot OPT(A)$".
Before stating this lemma, they explicitly say that this result is independent of the value of $\ell$.

However, a contradictory result is mentioned in lemma 5.1 of the second version, which says that
"For a cluster $A$, if we choose a point $p$ uniformly at random, then the expected cost of the cluster(with $p$ as a center) is at most $2^{\ell} \cdot OPT(A)$"

So far, I agree with the second version of the paper. However, it is possible that the first version came later with corrections. If the first version result is also correct, how to prove this result?

Note: Both these versions are highly cited and appear at the top in the google search. So I doubt if they are incorrect. Also, none of the versions mention anything about the corrections made in the paper.


texts: What would it mean to disprove Church-Turing thesis?

texts:
Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why?

Turing, Rosser etc used different terms to
differentiate between: "what can be computed" and "what can be
computed by a Turing machine".

Turing's 1939 definition regarding this is:
"We shall use the expression "computable function" to mean a function
calculable by a machine, and we let "effectively calculable" refer to
the intuitive idea without particular identification with any one of
these definitions".

So, the Church-Turing thesis can be stated as follows:
Every effectively calculable function is a computable function.

So again, how will the proof look like if one disproves this conjecture?


texts: Lower bounds and impossibility results for distributed transactions

texts:
I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations.

To avoid unnecessary efforts, I would like to know that

  What are the known (or conjectural) impossibility results and lower bounds on the complexity of implementing distributed transactions conforming to some correctness criterion and/or some progress condition?

For example,

  Is it possible to implement SI in a wait-free/lock-free manner in replicated settings?


texts:
This question was previously posted to Computer Science Stack Exchange here.

Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.

Problem: How should your fly your helicopter to minimize travel distance?

More precisely, given a real number $R>0$ and $N$ distinct points $\{p_1, p_2, \ldots, p_N\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.

Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.


texts: Is simply typed lambda calculus equivalent to primitive recursive functions

texts:
It's well known that the computation models untyped lambda calculus and $\mu$-recursive function are equivalent in terms of computability (in fact they are both Turing complete.) It is also well known that, among some of the variations of them, the simply typed lambda calculus ($\lambda_{\rightarrow}$) and the primitive recursive function ($R_p$), are less powerful (i.e. neither of them is Turing complete.)

Since the intuition of the essential restrictions applied in both cases feels similar, I have the instinct that the class of functions computable by either of them is the same, i.e. $\lambda_{\rightarrow} \cong R_p $; but I cannot find any literature discussing this issue myself after a quick search.

Thus, I'd like to ask 1) whether simply typed lambda calculus and primitive recursive function are equivalent and 2) if so, is there any literature that I can have a look at discussing this?


texts:
It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity.

Should one expect this to be close to optimal?
In fact, is it possible, that random MAX-k-SAT instances can be approximated within any desirable fraction w.h.p.?
At least on the face of it - this should not contradict the PCP theorem, whose output SAT instances are very construction-specific (Dinur) and are thus sets with negligible probability in this respect.


texts: What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices

texts:
A chordal Graph is a connected graph which contains no chord-less cycle of size greater than three.
They are also called as Triangulated graphs.

All Paths are Chordal Graphs (No cycles).

All Trees are chordal Graphs (No cycles).

All cliques are chordal graphs.

A Path contains the minimum no of edges and a clique contains the maximum number of edges of a given n vertices chordal graph

Wiki Link for more explanation of chordal graphs

So for a fixed number 'n', what is the algorithm to find all the possible chordal graphs of n vertices?

For example:

n= 2, Answer = 1 chordal graph.
n= 3, Answer = 2 chordal graphs,
n= 4, Answer = 5 chordal graphs,
n= 5, Answer = 15 chordal graphs.

The above are determined by drawing all possible examples. Any algorithm?


texts: Which model of computation to simulate to prove universality?

texts:
I am starting out in theoretical computer science.

I have a model of computation based on observations of auto-associative memory in the brain.  I believe (with little evidence) that I can do anything in this simple model.  I understand the primary way of proving universality is to show that your model can simulate another universal model, especially a turing machine.

I would like to request the following information:

References to clear and easy to follow proofs of universality of a computational model, graspable by an able beginner such as myself.
Guidance as to what model would be easiest model to attempt to simulate.  I imagine the answer to this may be 'it depends'.  Currently it appears my model bears some semblance to lambda calculus.


texts: 3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

texts:
I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from planar separator results, yet in wikipedia, it only mentions independent sets, Steiner trees, Hamiltonian cycles, and TSP. Below I include some reasoning which I think almost does achieve this bound.

With a zero reduced decision diagram, (ZDD), I believe you can get $O\left(c^{O(log_2(n)\sqrt{n})}\right)$, and I was curious how I could do better. What I came up with is rather rudimentary. Note: throughout, the ZDD I describe is ternary, but I don’t think that greatly matters. For the ZDD, given an ordering, $L = \{v_1 \dots v_n\}$, of vertices to color, the number of nodes at step $i$ will be exponential in respect to the size the frontier, $F_i = \{v_k | k < i \land v_k~v_j, j \geq i \}$.

To create your ordering $L$, you may create an optimal branch-decomposition tree, $b$, in polynomial time, which has width at most $\sqrt{n}$. Then, select a random leaf $v’$ of $b$ to be your root. With a BFS, weight each edge $e$ by the number of leaves not connected to $v’$ if you were to remove $e$ from $b$. Then, do a DFS to finally create $L$, always going down the edge furtherest from $v’$, choosing the one with least weight if there is a tie, and choosing arbitrarily if there is still a tie. When we reach a leaf, $(u,v)$ add $u$/$v$ to $L$ if either is not in $L$. Let $c_i$ be the component induced in $b$ by the vertices visited when we added $v_i$ to $L$. Then, $F_i$ is bounded by the branch width times the number of edges $x_i$ needs to be removed from $b$ to get the component $c_i$. $x$ is bounded roughly by $log_2$ of the vertices in $b$, which is linear to $n$ since we’re dealing with planar graphs.

With that, you check all three colors for each node for each of the $n$ frontiers and you’re done.


texts: The computational complexity of matrix multiplication

texts:
I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by $B \in \mathbb{R}^{n \times p}$ is $O(mnp)$ (schoolbook multiplication).

I have a case where $m$ and $n$ are much smaller than $p$, and I was hoping to get better complexity than linear in $p$, on the expense of making the dependence on $m$ and $n$ worse than linear.

Any ideas?

Thanks.

Note: the reason I am hoping for it to be possible is because of the well known result of less than cubic dependence in $p$ if $m=n=p$ (when matrices are all squares).


texts: Formalized configuration of Subset sum problem Worst-case ?

texts:
Is there a formal proof of the worst-case configuration of the subset sum problem?

In other words - is there a set proven to be the hardest to find a subset equals to 0 from?

thanks


texts:
This may be a very simple question.

But what is the difference between types and sorts?

My current understanding is that you have a type theory with type rules that give a notion of a well-typed statement but sorts are more basic, differentiating symbols into different sorts of symbols and introducing basic rules on function application etc.

Perhaps there is little difference, maybe they just come from different fields. But I can't seem to find a clear description of their relation.


texts: Cayley subgraph isomorphism and complexity of linear subcode decision

texts:
Let $G$ be an undirected Cayley graph over an abelian group. Let $H$ a regular graph whose independence number and chromatic number are known. Let $inj(G,H)$ be the number of injective homomorphisms from $G$ to $H$. It is known SUBGRAPH ISOMORPHISM is NP-complete. Consider the CAYLEY SUBGRAPH ISOMORPHISM problem:

Given an undirected Cayley $G$ and a regular $H$, is inj(G,H)>0?

Is the above problem NP-complete?

Since linear codes are abelian, I am extending the question. Given two $[n_i,k_i,d_i]$ linear codes $C_i$ for $i=1$ and $2$ and $n_1<n_2$, is deciding $C_1\cong D \subset C_2$ NP-complete? Note that code isomrphism is similar to graph isomorphism.


texts: Finding a biased coin using a few coin tosses

texts:
The following problem came up during research, and it's surprisingly clean:

You have a source of coins. Each coin has a bias, namely a probability that it falls on "head".
For each coin independently there's probability 2/3 that it has bias at least 0.9, and with the rest of the probability its bias can be any number in [0,1]. You don't know the biases of the coins. All you can do at any step is toss a coin and observe the outcome.

For a given n, your task is to find a coin with bias at least 0.8 with probability at least $1-\exp(-n)$. Can you do that using only O(n) coin tosses?


texts: Sparse-cut approximation for well connected graphs

texts:
Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most  $\sqrt{2\big(1 − \lambda(G)\big)}$.

If I understand UGC correctly, the above result is tight for general graph under UGC.

Question: Can we obtain a better approximation if we have the promise - $mincut(G) = O(\log n )$?


texts: In regards to the tautologies of a polynomially-bounded propositional proof system

texts:
In the book 'Logical Foundations of Proof Complexity', co-authored by Stephen Cook, the following definition is given:

A proof-system $F$ is said to be polynomially-bounded if there is a polynomial p(n) such that for all tautologies $A$, there is a proof $X$ of $A$ in $F$ such that |x| $\leq$ p(|A|). Informally, a proof system is polynomially-bounded if every tautology has a short proof in F.

My question is in regards to what "all tautologies" means. Is it in regards to every tautology in $F$ or any tuatology in in any adequate proof system, which first needs to be converted to an equivalent formula in $F$?

For example, let's say we are dealing with 2 very different proof-systems, A and B. Let's just assume for the moment that B is polynomially-bounded. Then every tautology in B has a short proof.

My question is: Given a tautology in system A--denoted as $\phi$--, is it necessary that the conversion from $\phi$ in A to its equivalent formula $\phi'$ in B happens in polynomial-time?

Or is the only thing that is necessary for B to be considered a polynomially-bounded proof system this: that once $\phi$ is represented in the system B (regardless of how long this conversion takes place), then this formula has a short proof in B?

So if it was inefficient to convert $\phi$ to $\phi'$, yet $\phi'$ nonetheless still had a short proof in system B, is B still considered a polynomially-bounded proof system?


texts: Election algorithm with unreliable messages and a certain timestamp

texts:
I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows:

Messages are sent unreliably with an at-most-once sending
Nodes are only eligible if they are available and have the most current timestamp of all available nodes within the set. Each node has a timestamp, representing the last update operation.
Each node has a weight, each weight is unique (= the nodes are strictly ordered in terms of the weight).
The eligible node with the highest weight should win the election.
My system uses timeouts to detect failures.
Each node knows the weight of each other node in the set.

I had a look especially at Bully algorithms, originally given by Garcia-Molina and a modified version. I have no problem adapting them to the unreliable message sending using ACKs. However, I struggle as I have one assumption which is quite different: I do have timestamps at each node, which are not known to every node.


texts: Solve multiple instances of SAT with a 2-approximating #SAT query

texts:
Assume we have some oracle $A$ such that when given as input a Boolean formula $\phi$, it outputs a 2-approximation to the number of satisfying assignments of $\phi$. If we are given multiple SAT instances $\phi_1,\ldots, \phi_m$ (where $m$ is a small constant such as 10, 5, or even 2), using only one query to $A$, how could I show in polynomial time which formulas are satisfiable?

Note that $\phi$ is unsatisfiable if and only if $A$ outputs 0 on input $\phi$.


texts: Graph optimization problem with multiple objectives/constraints

texts:
Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We can divide vertices in two subsets $V_a$ and $V_b$, such that $V_a \cap V_b = \emptyset$ and $V_a \cup V_b = V$. A set of edges $E_{ab}$ between the two sets is defined as $(u,v) \in E_{ab}: (u \in V_a, v \in V_b) \lor (u \in V_b, v \in V_a)$

The cost function $C$ is described as follows:

$$C = \sum_{v \in V_a}{w_a(v)} + \sum_{v \in V_b}{w_b(v)} + \sum_{(u,v) \in E_{ab}}{t(u,v)}$$

We can also define the cost $C_P$ of a path $P : v_1, v_2, \dots, v_n$ using the same rules:

$$C_P = \sum_{v \in V_a \land v \in P}{w_a(v)} + \sum_{v \in V_b \land v \in P}{w_b(v)} + \sum_{(v_i, v_{i+1}) \in E_{ab} \land v_i \in P \land v_{i+1} \in P}{t(v_i,v_{i+1})}$$

Now, thanks to the user saisandeep, I know that the problem of finding the subsets $V_a$ and $V_b$ such that the $C$ function is minimized can be reduced to minimum cut, so it's in P.

I've also managed to come up with the solution to find the subsets with the shortest and longest possible path (or at least I hope that I did): we can transform the graph $G$ to graph $G'$ in such a way that for every vertex $v$ we create two vertices $v_a$ and $v_b$ with appropriate weights (from $w_a$ and $w_b$ functions respectively), and for every edge $(u,v)$ we create two edges with weight $0$: $(u_a,v_a)$, $(u_b,v_b)$; and two edges with weight $t(u,v)$: $(u_a,v_b)$, $(u_b,v_a)$. In other words, we're creating graph $G'$ that covers every possible path for every division of $V$.

The graph $G'$ is still a DAG, so both shortest and longest path can be found in polynomial time.

But what happens if I want to minimize the cost $C$ and at the same time restrict that the cost $C_P$ of the longest path must be below some maximal acceptable cost $c_{max}$?

Or the other way around: minimize the cost $C_P$ of the longest path, but keep the overall cost $C$ below $c_{max}$?

How should I approach this problem? Are there any generic ways to prove complexity of such multi-objective problems?

The best answer that I've found in literature is that "multi-objective optimization problems are generally hard" which is not very helpful.

My real-life application of this problem is to allocate software components on two heterogenous machines (hence two weight functions) connected via network (hence edge weights) and minimize both energy use (the $C$ function is basically the CPU time + transfer time) and the computation time (the longest path).

Thanks in advance for any help.


texts: Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

texts:
I am asking this question from the context of parameter preserving reductions which has implications for kernelization (See Theorem 18 of [1] for an example). For simplicity, here I am assuming that the host graph $G$ is regular. It seems to me that the game theoretic definition of treewidth is more useful here (See Section 2 of [2]).
Let $G$ be a regular graph with maximum degree $\Delta$. Let $H$ be a graph with $\Delta$ marked vertices. Let $G^*$ be the graph obtained from $G$ by replacing each vertex $v$ of $G$ by a copy of $H$ (say, each marked vertex of $H$ takes one neighbor of $v$ each).
Can we say that treewidth of $G^*$ is at most $\max\{tw(G)+\Delta,tw(H)+\Delta\}?$
(Let's use $tw(J)$ to denote the treewidth of a graph $J$.
For the special case $tw(H)\leq tw(G)$, we get the question in the title).
In [1], they consider the case when $H$ is sunlet$_6$ (i.e., $C_6$ plus a leaf attached to each vertex). In that paper, it is claimed that $tw(G^*)\leq tw(G)+2$. Is this claim correct?
(Disclaimer: it is possible that their claim is correct, but my idea of the generalization given as the first question is wrong).
The presentation in [1] gave me the feeling that the answer to the first question is yes. But, I couldn't find a reasonable explanation. I would like to know whether I am overlooking something well-known here.
Similar Situations
We can say the following.

If one vertex $v$ of $G$ alone is replaced by a copy of $H$, then the treewidth of the resultant graph is at most $\max\{tw(G)+\Delta,tw(H)+\Delta\}$.

Idea (in terms of cops and robber game): In an optimal cop strategy of $G$, whenever there is a cop at $v$, place $\Delta$ cops at marked vertices of $H$. Also, choose one of those points, make a new branch there which raids $H$. This forms a cops strategy for the resultant graph.
(Idea in terms of tree-decomposition: In the tree-decomposition of $G$, in each bag containing $v$, replace $v$ by marked vertices of $H$. Also, choose one such bag $B$ and append a new branch there that 'raids' $H$; in other words, take the tree-decomposition of $H$, add marked vertices of $H$ to each bag, and append this as a branch to the vertex associated with the bag $B$.)

Let $K$ be a graph with two marked vertices. Let $G'$ be the graph obtained from $G$ by replacing each edge $e$ of $G$ by a copy of $K$ (say, each marked vertex of $K$ takes one incident vertex of $e$ each). Then, the treewidth of $G'$ is at most $\max\{tw(G)+\Delta,tw(K)+\Delta\}$.

Idea (in terms of cops and robber game): Consider an optimal cops search strategy. For each edge $e=uv$ of $G$, choose a point in the strategy when edge $e$ is searched (i.e., there is a cop at $u$ and a cop at $v$) and raid $H$ at that point. This forms a cops strategy for $G'$.
Thank you.
References
[1] Lauri, Juho; Mitillos, Christodoulos, Complexity of fall coloring for restricted graph classes,  ZBL07173544.
[2] Langer, Alexander; Reidl, Felix; Rossmanith, Peter; Sikdar, Somnath, Practical algorithms for MSO model-checking on tree-decomposable graphs, Comput. Sci. Rev. 13-14, 39-74 (2014). ZBL1302.68184.


texts: Minimum infeasible subgraph in assignment problem

texts:
Given a bipartite graph $G$ with node set $(X+Y)$. Each node $x \in X$ has to be assigned to 1 node $y \in Y$. Assignment is only possible if there is an edge between $x \in X$ and $y\in Y$. Furthermore, each node $y\in Y$ can only handle $d_y$ assignments.

Let us assume that for a given graph such an assignment is not possible. Now I would like to compute the minimum induced subgraph of $G$ which is still infeasible. Are you aware of any related problems, or pointers on how to solve this efficiently?

Example. Given the graph below, and the following weights: $d_a=3, d_b=2, d_c=d_d=1$

1 - a
  /
2 - b
  \
3 - c
  /
4

5 - d

There does not exist an assignment of the nodes 1-5 to a-d. Clearly we can remove nodes 5, d from the graph because the resulting subgraph is still infeasible. Similarly we can remove the nodes 1,a,2,b. The minimum induced infeasible subgraph here is composed of the nodes 3 and 4 and c . How can I compute this efficiently?

Very much related is the following problem:

$max \sum_{i\in X}x_i-\sum_{j\in Y}d_jy_j$
$y_j \geq x_ie_{ij} \;\;\;\forall i\in X,j\in Y$
$x_i,x_j\in \{0,1\}$

Here $x_i$ is a variable indicating whether we take a vertex from partition X. Similar for $y_j$. $e_{ij}$ is a parameter indicating whether there is an edge between $i\in X$ and $j\in Y$. Note that when $x_i=1$, then all neighbors of $i$ in partition $Y$ are also 1. $d_i$ is the supply provided by node $i\in Y$. Is this integer program a known combinatorial optimization problem?


texts:
What are some good examples for analysis of a class's Fat-Shattering dimension?

By (Alon et al) I know that the Fat-Shattering Dimension characterizes the learnability of real-valued function classes but I didn't find any proper examples of function class with a proof for a bound on the Fat-Shattering Dimension of the class.


texts: How to define list zipping categorically/inductively?

texts:
Lists and fixpoints

The type of $A$-lists is defined as $\mu F_A$, where $F_A(X) = 1 + A \times X$ is the "cons-or-nil"-functor and $\mu$ is the least fixpoint operator. In Haskell syntax, this would correspond to:

data List a
   = Nil
   | Cons a (List a)

Here, Nil is the sole inhabitant of $1$, and Cons a as corresponds to A \times X. The fact that lists are fixpoints is reflected in the recursive definition of List a.

Initial algebras

It is well known that least fixpoints have semantics in initial algebras.
See e.g. Brian Howard's thesis. For our purposes, the type of $A$-lists is the initial algebra of the functor $F_A$.

Algebra map

Being an algebra, lists come with the algebra map $\phi\colon F_A (\mu F_A) \to \mu F_A$. It an isomorphism, so if we unpack we have $1 + A \times \mu F_A \cong \mu F_A$. In words, a list is either empty or consists of an $A$ and another list.

Universal property

Since $\mu F_A$ is initial, there is a unique algebra map from $A$-lists to any $F_A$ algebra. That is, if there is a morphism $\beta\colon F_A B \to B$, there is a unique algebra map $\mathrm{it}(\beta)\colon \mu F_A \to B$.

Warm up: Unzip

unzip takes a list of pairs $\mu F_{A \times B}$ and produces a pair of lists $\mu F_A \times \mu F_B$. It is thus a function from a list into something else, and could thus be defined via the universal property. All we need to do is to give $\mu F_A \times \mu F_B$ the right $F_{A \times B}$-structure:

$$F_{A \times B} (\mu F_A \times \mu F_B) = 1 + A \times B \times  \mu F_A \times \mu F_B$$
$$\hookrightarrow 1 + A \times \mu F_A + B \times \mu F_B + A \times B \times \mu F_A \times \mu F_B$$
$$\cong (1 + A \times \mu F_A) \times (1 + B \times \mu F_B) = \mu F_A \times \mu F_B$$

One can see that we inject into either the case "both lists stop" or "both lists continue". Apply the universal property, and you have unzip.

Puzzle: Zip

Now we would like to do the reverse. Given two lists, create a list of pairs. The Haskell version is simple:

zip (Cons a as) (Cons b bs) = Cons (a, b) $ zip as bs
zip _ _ = Nil

But now we need to write a function into a list. This suggests using the algebra morphism, but I can't figure out how. Alternatively, one might want to create an algebra structure for $\mu F_{A \times B}$ for some other functor, but I don't know which, and I don't know how to map from two fixpoints into a single one.


texts: Reference: Cancellability of the Dyck congruence

texts:
I consider the Dyck congruence $\equiv$ on a parenthesis alphabet $\Sigma = \{a, \bar a, b, \bar b\}$, i.e. the least congruence on $\Sigma^*$ such that $a \bar a \equiv \varepsilon $ and $b \bar b \equiv \varepsilon$.

It appears that $\equiv$ can be cancelled, i.e. for every $v$, $w_1$, $w_2 \in \Sigma^*$, if $vw_1 \equiv vw_2$, then $w_1 \equiv w_2$ (and analogously for cancellation from the right).

Does someone know a literature reference for this property?  I wasn't able to find anything along those lines.


texts: Hardness of Subgraph isomorphism problem for sparse pattern graph

texts:
Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ time assuming ETH. The easiest way to see this is to consider $G$ to be a clique and recall that $k$-clique problem requires $n^{\theta(k)}$ under ETH [1].

On the positive side, if $G$ is a path, a tree or a collection of small identical graphs we know how to solve Subgraph isomorphism in $f(|G|) |H|^{O(1)}$ time [2,3]. All these graphs are sparse, however I'm unaware of a general algorithm that runs in time $f(|G|) |H|^{O(1)}$, for all sparse graphs $G$.

My question is: do we know any conditional lower bounds for Subgraph isomorphism for sparse pattern graphs?

[1]Chen, Jianer, et al. "Tight lower bounds for certain parameterized NP-hard problems." Information and Computation 201.2 (2005): 216-231.

[2]Koutis, Ioannis, and Ryan Williams. "Limits and applications of group algebras for parameterized problems." International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg, 2009.

[3]Fellows, Mike, et al. "Finding k disjoint triangles in an arbitrary graph." International Workshop on Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2004.


texts: Can we get a sorted list from a sorted matrix in $O(n^2)$

texts:
I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$.
I proceed by assuming that it can be done faster than $n^2\log n$ and try to violate the $\log(m!)$
lower bound for comparisons needed to sort m elements.
I have two conflicting answers:

we can get a sorted list of the $n^2$ elements from the sorted matrix in $O(n^2)$
https://math.stackexchange.com/questions/298191/lower-bound-for-matrix-sorting/298199?iemail=1#298199
you can't get a sorted list from the matrix faster than $Ω(n^2\log(n))$
https://stackoverflow.com/questions/4279524/how-to-sort-a-m-x-n-matrix-which-has-all-its-m-rows-sorted-and-n-columns-sorted

Which one is right?


texts: Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?

texts:
I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).:

  If A and B are disjoint, nonempty sets of lambda terms which are closed under equality, then A and B are recursively inseparable. It follows that if A is a nontrivial set of lambda terms closed under equality, then A is not recursive. So, we cannot decide the problem "M=x?" for any particular M. Also, it follows that Lambda has no recursive models.

If we have a normalizing system, such as System F, then we can decide $\beta$-equivalence "from outside" by reducing the two given terms and comparing if their normal forms are the same or not. However, can we do it "from inside"? Is there a System-F combinator $E$ such that for two combinators $M$ and $N$ we have $E M N = \mbox{true}$ if $M$ and $N$ have the same normal form, and $E M N = \mbox{false}$ otherwise? Or can this be done at least for some $M$s? To construct a combinator $E_M$ such that $E_M N$ is true iff $N\equiv_\beta M$? If not, why?


texts: What are some applications and algorithms for optimizing an unknown objective function with only first-order feedback?

texts:
I am thinking about the optimization problem where you are learning to optimize an unknown convex objective function. Each time step, you choose $x_t$ and receive feedback $\nabla f(x)$ only. I think most machine learning problems we study have a known loss function, and then we optimize that predefined loss function. Every time we choose an action, we would observe the corresponding loss.
The application I am thinking is that we need to optimize an unknown objective function with only first-order feedback. To be more specific, I know the similar problem that optimizing an unknown function with only zeroth-order feedback is well-studied. For example, I think bandit learning might be a good example for optimizing an unknown objective function with only zeroth-order feedback. Then what about first-order?
Besides the real-world applications which require us to optimize an unknown function with only first-order information, are there any algorithms besides gradient descent that can be used to do optimization with only first-order feedback?
Update: found some applications for optimizing  an unknown objective function with only zero-order feedback by Sebastien Bubeck (https://blogs.princeton.edu/imabandit/2013/05/02/orf523-optimization-with-bandit-feedback/) Again, I am citing this example only for showing what kind of problem I am thinking. Are there similar research done with first-order instead of zeroth-order?

Indeed there are many situations where the function f to be optimized is not known, but one can simulate the function. Imagine for example that we are trying to find the correct dosage of a few chemical elements in order to produce the most effective drug. We can imagine that given a specific dosage one can produce the corresponding drug, and then test it to estimate its effectiveness. This corresponds precisely to assuming that we have a noisy $0^{th}$-order oracle for the function $\mathrm{dosage} \mapsto \mathrm{effectiveness}$.

Update: I am giving optimizing unknown function with zeroth-order information only as an example of what kind of problem I am thinking. So it seems to me that optimizing with zeroth-order feedback is a well-studied area, and I am looking for some similar work on optimizing with first-order information instead.


texts: Zero knowledge verification of an encryption protocol

texts:
This seems like a straightforward application of zero knowledge techniques, but an answer eludes me.

Alice and Bob claim to have devised an encryption scheme: specifically, they claim to possess functions $E()$ and $D()$ to encrypt and decrypt arbitrary $n$-bit messages.

Charlie wishes to verify this claim, but Alice and Bob don't want Charlie to learn anything about the method.

Can Charlie verify that Alice and Bob can indeed encrypt and decrypt in a zero knowledge fashion ?


texts: Maximizing the number of selected edges with opposing requirements

texts:
Consider the following problem:

Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$.
Output: a subset of vertices $W$ of size $k$ which maximizes the following:

  number of black edges with both endpoints in $W$ + number of white edges with at most one endpoint in $W$

What is the complexity of this problem?
Is there a polynomial time algorithm (exact or approximate) for the problem? Could this problem be reduced to any classic Thoeretical CS problem, like the Max-Cut?


texts: Why do we believe $\mathsf{fewP \ne NP}$?

texts:
$\mathsf{fewP}$ ($\mathsf{NP}$ with few witnesses, see the zoo) is one of the important ambiguity-bounded sub-classes of $\mathsf{NP}$. There are interesting natural problems in this class that are believed to be good candidates for problems in $\mathsf{NPI}$-intermediate such as Beltway problem and the Turnpike problem. Informally, $\mathsf{fewP}$ is the class of $\mathsf{NP}$ problems with polynomialy-bounded number of solutions.

$\mathsf{FewP}$ is defined as:

  The class of decision problems solvable by an $\mathsf{NP}$ machine such that
  If the answer is 'no,' then all computation paths reject.
  If the answer is 'yes,' then at least one path accepts; furthermore, the number of accepting paths is upper-bounded by a polynomial in n, the size of the input.

We known that $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{fewP}\subseteq \mathsf{NP}$.
It is an open problem whether any inclusion is strict. Specifically, $\mathsf{fewP}$ vs. $\mathsf{NP}$ is an open problem. The Complexity Zoo cites oracle results suggesting that all inclusions are strict and that $\mathsf{fewP}$ does not have a Turing-complete set.

  Why do we believe that $\mathsf{fewP \ne NP}$?

Is there any unexpected consequence that follows from $\mathsf{fewP=NP}$ such as the collapse of the polynomial hierarchy or disproving any other widely believed complexity-theoretic conjecture?


texts: A coupon collector type problem with changing probabilities

texts:
Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\frac{1}{\sqrt{t+1}}$ and so on... What is the expected number of flips until the coin lands heads? In particular I would be interested in an upper bound on the expectation.. If this is difficult suppose we also make the assumption that it is bounded by $T$, e.g. there at most $T > t$ coins.

If the probabilities are constant at $p$ at each round, the expected value  is $1/p$ which is like one coupon being collected in the coupon collector problem. Since the probability of heads is less than $1/\sqrt{t}$ at each round, $\sqrt{t}$ is a lower bound for the expectation. On the other hand, the probability is greater than $1/\sqrt{T}$ in the bounded case, and so $\sqrt{T}$ is an upper bound. The question is where in this regime $[\sqrt{t}, \sqrt{T}]$ does the expectation fall..


texts:
Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members.

Let $\mathcal{C}$ be a class of graphs and let $\mathcal{B}$ be the class of bipartite graphs. We say that $\mathcal{C}$ is biparted if $\rho(\mathcal{C}) > \rho(\mathcal{B}\cap\mathcal{C})$ (where $\rho(\mathcal{C})$ is defined below) i.e. the asymptotic density of arbitrary graphs in the class is larger than the asymptotic density of the bipartite graphs in the same class.

Examples of biparted graphs are:

Planar Graphs ($\rho(\mathcal{C}) = 6 > 4 = \rho(\mathcal{C}\cap \mathcal{B})$)
Graphs of finite genus (same parameters as above)
Subclasses of planar graphs e.g. outerplanar graphs

My question is:

  Are there any other natural classes of biparted graphs?

For a graph $G$, let $\rho(G) = \frac{2|E(G)|}{|V(G)|}$ be the average degree of a vertex. We say that a class of graphs $\mathcal{C}$ is maximally $\rho$-sparse - written as $\rho = \rho(\mathcal{C})$ i.e. the maximum of average density (with maximum taken over all graphs from $\mathcal{C}$ with sufficiently many vertices) approaches $\rho$.

Note: Planar graphs can be proved to be biparted because Euler formula holds. The same is the case with bounded genus graphs. What about bounded tree-width graphs, graphs excluding a finite set of fixed minors,...?


texts: Inverting Kronecker product on vectors is in P?

texts:
Problem: Given a vector V of positive integers, find two vectors v1 and v2 such that the Kronecker product of v1 and v2 is equal to p(V) (where p(V) is a suitable permutation of V).
Example:
Input: V={8,4,18,9,12,24,36,16,48}.
Output: v1={4,9,12}, v2={2,4,1}
Kronecker product of v1 and v2 is {8,16,4,18,36,9,24,48,12}
which is a permutation of V.
I do not know whether this problem is NP-hard or can be solved in polynomial time.


texts: Problems that are NP-hard to approximate even when the input graph is regular

texts:
Are there graph problems which are NP-hard to approximate even when the input graph is regular?

For instance, are there optimization problems that are NP-hard to approximate within $O(n^\epsilon)$ even when the input graph is regular?

PS: The input graph is a simple undirected graphs


texts: Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits

texts:
Beigel and Tarui's transformation of $\mathsf{ACC}^0$ circuits to depth 2 circuits with a polylog symmetric function on top is one of important results in the circuit complexity. For example, the recent breakthrough separation between $\mathsf{NEXP}$  and $\mathsf{ACC}^0$ by Ryan Williams uses this transformation to design a fast $\mathsf{ACC}^0$-CircuitSAT algorithm.

I think the proof in their paper is a little complicated and too technical for me. Is there a simpler proof of their result?


texts: Cryptographic systems that don't leak linear combinations of encrypted bits

texts:
Various encryption schemes would be considered broken if an adversary could have a non-negligible edge in predicting the first (or any) bit of an encrypted message.  I am looking for a slightly stronger guarantee.

In particular, does any cryptographic system or crypto assumption (that relies on keys, not a one time pad) guarantee that any linear combination of the encrypted bits cannot be predicted after an adversary sees only a polynomial number of messages (possibly of his choosing)?

Note -- I am not at all an expert in cryptography, and this may be considered trivial.


texts: Why non-uniform learnability does not imply PAC learnability?

texts:
PAC guarantees provide us a a learning algorithm $A_n(\cdot)$ and sample complexity bound $n_{\mathcal{F}}(\epsilon,\sigma)$ that ensures
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\geq 1-\sigma
$
when $n>n_{\mathcal{F}}(\epsilon,\sigma)$.

On the other hand we say that the hypothesis class $\mathcal{F}$ is non-uniformly learnable if we can provide a sample complexity $n_{\mathcal{F}}(\sigma,\epsilon,f)$ and a learning algorithm $A(\cdot)$, such that
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f)\leq \epsilon\right]\geq 1-\sigma
$ when $n>n_{\mathcal{F}}(\sigma,\epsilon,f)$.

Non-uniform learnability is a relaxation of PAC learnability since
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\geq 1-\sigma \implies P\left[L_P(A(\mathcal{D}^n))-L_P(f)\leq \epsilon\right]\geq 1-\sigma
$
but the contrary is not true, namely $\mathcal{F}$ may be non-uniform learnable but not PAC learnable. My question is, if we are given a non-uniformly learnable class $\mathcal{F}$ and we define $n_{\mathcal{F}}(\sigma,\epsilon)=\sup_{f \in \mathcal{F}} n_{\mathcal{F}}(\sigma,\epsilon,f)$, does it become PAC learnable? or the supremum over an uncountable set nullifies the implication? Making the complexity bound vacuous?

Thanks for any clarification


texts:
I taught $AC^0$ lower bounds today, and one of the students asked about the reason for the name $AC$.
The official explanation is that the "A" stands for "Alternation".

I vaguely remember being told many years ago that Nick Pippenger Steve Cook named $NC$ after Nick Pippenger (Nick's class), and later Nick named $SC$ after Steve (Steve's class).

The $NC$ part of the story is documented, e.g., in Wikipedia and in the complexity zoo, the story for $SC$ is told here.

I wonder whether $AC$ has a similar history, but I couldn't find any reference to $AC$'s inventor.

Does someone know who defined $AC$?


texts: iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

texts:
A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition without an output symbol). Its not complicated but not trivial either; it seems to be rarely taught, and also shows a close relationship between FSMs and TMs. It also shows up as a somewhat/seemingly natural mechanism for studying the Collatz conjecture by linking to questions on automata.[2]

Take any TM and consider the sequence of IDs, instantaneous description strings, associated with the TM tape and current state, also called a "computational tableau". (Details of the ID format/encoding are not nec so important but one simple method is to have the current TM state located embedded in the string at the current head position.) The sequential results of the TM after each TM step, $d_1, d_2, ... d_n$ can be computed by a FSM transducer with $\epsilon$-transitions, working left-to-right. am interested in answers to any of the following questions.

  What are some refs that refer to this correspondence/construction (computation of TM tableaus by FSM transducer iterations)?
  What is the earliest one to point it out?
  What are some notable results (if any) related to it?

Note, FSM transducers were also called "generalized sequential machines" in early automata theory from the 1960s.

[1] What is the enlightenment I'm supposed to attain after studying finite automata?

[2] Collatz Conjecture & Grammars / Automata


texts: Complexity involving connected components of 0/1 matrix

texts:
Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you step on another $1$ and one can shown there that there are matrices that cannot be brought to one component.

  Is the decision problem "Can a given matrix $A$ be permuted into at most $k$ components?" in $coNP$ (it is clearly in $NP$ ("YES" certificate is a permutation with $\leq k$ components)) and could it be $NP$-complete (I think this problem is in $NPI$)? $k$ is part of input.

I do not have explicit matrices but a counting argument will easily give you existence.


texts: On preprocessing a convex polyhedron prior to sampling

texts:
Most of the algorithms for estimating the volume of a convex polyhedron $K \subset R^d$ assume the existence of an affine transform $T$ with the property that

$$ B \subset TK  \tilde{\subset}\  \sigma B$$

where $B$ is the unit ball in $d$ dimensions, and $\sigma$ is $O(\sqrt{d})$.

(Update: the $\tilde{\subset}$ indicates that the containment is true except for an $\epsilon$-fraction of $K$)

The algorithms that I've seen for computing this transform are quite tricky. They require a bootstrap sampling process to extract a few points from inside $K$ which are then used to define the transformation.

However, the fact that such a transformation exists is folklore, and my question was:

  Is there a simple algorithm (with possibly a weaker bound on $\sigma$)
  to compute the affine transform, given only a membership oracle for
  $K$ ?


texts: $\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?

texts:
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\oplus\mathsf{L}\subseteq\mathsf{P}$$
$$\mathsf{PP}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^0$$
$$\mathsf{DeterminantMod2}\in\oplus\mathsf{L}$$
where $\mathsf{C}\in\{\mathsf{P},\mathsf{LOGSPACE},\mathsf{DLOGTIME}\}$ and where $\mathsf{DeterminantMod2}$ is the problem of finding determinant of a $0/1$ square matrix modulo $2$.
It is possible $\mathsf{Permanent}$ could reduce to $\mathsf{P}$ by reduction via problems in $\mathsf{DeterminantMod2}$.
So how bad of collapse can we prove to avoid so far?

Is it known

$$\mathsf{CH}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^{{0}^{^{^{\mathsf{C'uniform}\mbox{ -}\oplus\mathsf{L}}}}}$$
and/or
$$\mathsf{CH}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{ACC}^{{0}^{^{^{\mathsf{C'uniform}\mbox{ -}\mathsf{NC}^1}}}}$$
for any $\mathsf{C'}\in\{\mathsf{P},\mathsf{LOGSPACE},\mathsf{DLOGTIME}\}$?

In other words is it known there cannot be a $\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{ACC}^0$ algorithm utilizing $\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{NC}^1$ oracle which computes the permanent?
It is known http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html provides
$$\mathsf{PP}\not\subseteq\mathsf{DLOGTIMEuniform}\mbox{ -}\mathsf{TC}^{{0}}.$$
It is unknown if
$$\mathsf{PP}\not\subseteq\mathsf{LOGSPACEuniform}\mbox{ -}\mathsf{TC}^{{0}}$$
holds (What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?).
Possibility of 2. is the deeper collapse.
Update The comments below indicate following collapse is not ruled out:
$$\mathsf{CH}\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{TC}^0\subseteq\mathsf{LOGSPACEuniform}\mbox{-}\mathsf{ACC}^0.$$


texts:
Denote by  $\delta^+(G)$ the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.
In a related question, I've mentioned the Ghouila-Houri extension of Dirac's theorem on Hamiltonian cycles, which suggests that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian.
In his comment, Saeed have commented on a different extension that seems stronger, except it requires the graph to be strongly connected.
The strong connectivity was proven redundant for the Ghouila-Houri theorem about 30 years after it was first published, and I was wondering if the same holds for the extension Saeed presented.
So the question is:

Who proved (can anyone find the reference) that $\delta^+(G)+\delta^-(G) \geq n$ implies $G$ is Hamiltonian, given that $G$ is strongly connected?

Is the strong connectivity redundant here as well, i.e. Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

(Note that while the graph obviously has to be strongly connected for it to be Hamiltonian, I'm asking whether this condition is implied by the degree conditions).


texts: Impacts of quantum computing on Theoretical Computer Science

texts:
Using quantum computers we can do calculations very fast.

However from a layman's view, I want to know the impact of quantum computers have on Theoretical computer science.


texts: There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.


texts: Bound on a graph diameter, considering the minimal vertex degree

texts:
Let $G$ be a connected (strongly connected) graph (digraph).

Assume that the minimal vertex degree (in/out degrees) of the graph is $\delta$ (are $\delta^-,\delta^+$).

What is the maximal diameter possible for such graph?

For example, if $\delta \geq \frac {n}{2}$ ($\delta^- + \delta^+ \geq n-1)$, then the graph is of diameter at most 2.

Also, it seems that $\delta \geq c\cdot n$ gives an upper bound of $\lceil \frac{2}{c} \rceil - 1$ on the diameter, but I'm not sure it's tight (also, haven't tried proving it yet, so I might be wrong).

(For $c=\frac{1}{2}$ it's definitely not tight).

What other bounds can we get?


texts: Permanent as projection of determinant and another permanent

texts:
I am looking for explicit examples where permanent of a given matrix $A$ is given by a determinant of a larger matrix $B$ (projection in the sense of Valiant). Is there any reference where I can find such an example for $n \times n$ matrix $A$ for say $n \le 5$.

Also are there examples where permanent of a given matrix $A$ is given by permanent of a larger matrix $A$? Again any explicit example for $n \times n$ matrix $A$ for say $n \le 5$ would help.


texts: Algorithm for computing unordered tree edit distance

texts:
I am trying to compute the edit distance between two dendrograms, one produced from hierarchical clustering, and the other manually constructed from some tree structure. In this setting, the rename operations on leaves of the tree are not allowed, and renames of other nodes (parent nodes) is free.

The tree edit distance for rooted ordered trees has been well studied, but this problem should be considered for the case where input trees are unordered. For the general case, it is known that tree edit distance problem for unordered trees is NP-hard. However, I don't seem to find an algorithm to find the unordered tree edit distance.

Any pointers or insights into this problem is highly appreciated.


texts: Complexity Classes - separations and inclusions

texts:
What are the basic complexity class seperation and inclusion results that everybody should know? (I mean specifically results that are known, and the proofs can be understood by a non-expert)

It would be great to have a book or paper (or set of papers) which go through and prove all the simplest and most fundamental results in this area. Where could I find it?

Thank you.


texts: reduction from SAT to approximate set cover

texts:
I read this neat result proved in the early 90s:

For any $c>1$, There's a poly time map from boolean formulas $\varphi$ to
pairs $K, \mathcal S$ where $K$ is a positive integer and $\mathcal S$ is an instance of set-cover (i.e. $\mathcal S = (U, \{T_1,...,T_n\}\subset 2^U)$) such that

If $\varphi$ is satisfiable, $\mathcal S$ has an exact (i.e pair wise disjoint) cover of size $K$
If $\varphi$ is not satisfiable, $\mathcal S$ has no cover (exact or otherwise) of size smaller than $c\cdot K$.

The result is simple enough but its proof is based on the class MIP which i don't  know much about and it's also (for someone of my limited background) strewn across a few different papers.

Has a more straightforward proof been discovered since 1993 or is there somewhere were i can read a more self contained proof of this or approximation results like this?


texts: Is there a simple algorithm for proof search on CoC?

texts:
Given the usual Calculus of Constructions with an extra primitive, _, that stands for "attempt to fill this location in a way that type-checks", is there any simple/elegant algorithm capable of solving this problem for a large class of terms? For example, given the term below:

λ (N : Type)
λ (S : {x : N} N)
λ (Z : N)
λ (A : {x : N} Type)
λ (B : {x : N} (A x))
λ (C : {x : (A (S (S (S Z))))} Type)
(C _)

The algorithm would replace _ by (B (S (S (S Z)))),  as it is the only substitution that makes the resulting term well-typed. I'm specifically looking for keywords / references, as I believe this is a pretty well-researched subject (given that most theorem provers feature proof search), but I've never seen an algorithm described in a simpler setup (like plain CoC).


texts:
I'd like to write mathematical proofs using some proof assistant. Everything will be written using first order logic (with equality) and natural deduction. The background is set theory (ZF). For example, how could I write the following proof?

Axiom: $\forall x\forall y(x=y\leftrightarrow\forall z(z\in x\leftrightarrow z\in y))$

Theorem: $\forall x\forall y(\forall z(z\notin x)\land\forall z(z\notin y)\rightarrow x=y)$

That is, the empty set is unique.

It's trivial for me to accomplish that using paper and a pen, but what I really need is a software to help me checking proof for correctness.

Thank you.


texts: Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?

texts:
Chaitin's incompleteness theorem states for any formal system $F$ (which satisfies various criteria), there is a $L$ such that for any $s$ the statement $$K(s) \ge L_F$$ is unprovable in that formal system. My question is, do we know what that constant is for ZFC. (Note that, like all questions involving Kolmogorov complexity, the specific value depends on the description language, but only up to an additive constant. If you want a specific language, you can use Binary combinatory logic, but once you find a $L_{ZFC}$ in one language, its trivial to find it in another.)

Note: I am not asking for the minimum $L_{ZFC}$, just any $L_{ZFC}$. In other words, I'm looking for an upper bound on the minimum $L_{ZFC}$.


texts: How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

texts:
A lot of pathfinding algorithms have been developed in recent years which can calculate the best path in response to graph changes much faster than A* - what are they, and how do they differ?  Are they for different situations, or do some obsolete others?

These are the ones I've been able to find so far:

D* (1994)
Focused D* (1995)
DynamicSWSF-FP (1996)
LPA (1997)
LPA*/Incremental A* (2001)
D* Lite (2002)
SetA* (2002)
HPA* (2004)
Anytime D* (2005)
PRA* (2005)
Field D* (2007)
Theta* (2007)
HAA* (2008)
GAA* (2008)
LEARCH (2009)
BDDD* (2009 - I cannot access this paper :|)
Incremental Phi* (2009)
GFRA* (2010)
MTD*-Lite (2010)
Tree-AA* (2011)

I'm not sure which of these apply to my specific problem - I'll read them all if necessary, but it would save me a lot of time if someone could write up a summary.

My specific problem:  I have a grid with a start, a finish, and some walls.  I'm currently using A* to find the best path from the start to the finish.

The user will then move one wall, and I have to recalculate the entire path again.  The "move-wall/recalculate-path" step happens many times in a row, so I'm looking for an algorithm that will be able to quickly recalculate the best path without having to run a full iteration of A*.

Though, I am not necessarily looking for an alteration to A* - it could be a completely separate algorithm.


texts: Minimal non-negative linear combination of positive integers larger than a positive integer

texts:
The problem is the following:

We have a positive integer $w$. A set of positive integers $A$ such that $\forall a \in A$ it's true that $a \leq w$. We search for the minimal integer $x$ such that $w \leq x$ and there is a convex integer combination of the elements of $A$ that is equal to $x$. The problem can clearly be written as an integer program but that's not much help.

My best approach is $O(w)$ in both time and space similar to knapsack's dynamic programming solution.

Could someone suggest a better one?

EDIT: I made 2 mistakes in the formulation. The first is that the combination is not convex only non-negative. The second is the algorithm I mentioned is not $O(w)$ but $O(|A|w)$.

The algorithm is like make an array size of $w$, sign $0$ in it and unsign everything else. Set a variable $\min$ to "infinite". Go through the array and to each signed element add each element of $A$. If it's not smaller than $w$ but smaller than $\min$ it's the new $\min$. If it's smaller than $w$ sign the according element. When we reach the end of the array $\min$ holds the $x$ in question.

Also the problem can be reformulated as a series of $n$ variable diophantine equation so if $A = \{a_{1}, \ldots, a_{n}\}$ and $d = \gcd(a_{1}, \ldots, a_{n})$ then we only need to check for $x \in \mathbb{N}, w \leq x, d \mid x$ if the diophantine equation $\sum_{i = 1}^{n}y_{i} a_{i} = x$ has an all non-negative $Y = \{y_{1}, \ldots, y_{n}\}$ solution.

I don't know the complexity for this second approach. I don't know how long the series can be.

EDIT.2: The length of the series is the smaller problem. Solving any of the above diophantine equations is like solving the subset-sum problem so this approach is not good either.


texts: Oracle for Hamming distance to a secret bitvector

texts:
Let $s \in \{0,1\}^n$ be a secret bitvector.  Define $f(x)$ to be the Hamming distance between $x$ and $s$.   Suppose I am given an oracle for $f$, and I want to find $x$.  How many queries to the oracle are needed to determine $x$?  I want an algorithm that is efficient (running time polynomial in $n$, say).  I am fine with average-case complexity (over a uniform distribution on $s$).

Information theoretically, $\Theta(n/\lg n)$ randomly chosen queries $x_i$ should suffice, but I can't think of any efficient algorithm to recover $s$ from the values of $f(x_i)$.  Obviously $s$ can be efficiently recovered given $n$ queries or so.  How much better can we do?


texts: Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

texts:
The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices.  A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ is adjacent to $c$, and $c$ is adjacent to $a$.
It is known that Triangle Finding is closely related to Boolean matrix multiplication and that Triangle Finding is deterministically solvable in $O(n^{\omega})$ time where $\omega$ is the matrix multiplication exponent.  Also, it is known that $\omega < 2.373$.
My Question: Is the complement of Triangle Finding solvable more efficiently with nondeterminism?  In particular, is Triangle Finding in $coNTIME(\tilde{O}(n^2))$?  If this is not known, would there be any interesting implications if it was true?


texts:
So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding.

Basically, he considers the parity check matrix $H$ as a Tanner graph. For each check node $j$ and its neighboring variable node set $N(j)$, he considers the set of all even-sized subsets $S$ of each $N(j)$ and introduces an auxilliary indicator variable $w_{j,S}$ that is one if and only if each variable in $S$ is set to one. He then requires that at least one of these is set to one (or that $w_{j,\emptyset}$ is set to one) and that $x_i = \sum w_{j,S}$, i.e. $x_i$ is one iff its included in some even sized subset $S$ with $w_{j,S} = 1$.

Clearly, this results in a highly exponential algorithm for non-LDPC codes, but ok. What I'm wondering is why the 'first thing that pops into your mind' doesn't work.

What I mean by that is that we have constraints like the following:

$$x_1 + x_2 + x_3 = 0 \text{ (mod 2)}$$

It's easy to check that the convex hull of this corresponds to four hyperplanes in $\mathbb{R}^3$. I haven't calculated it for degree four explicitily, but say a degree four equation would correspond to $M$ linear inequalities in $\mathbb{R}^4$.

Given that we have an LDPC code with $m$ parity check equations, each of degree four or less, the complexity of calculating the convex hull by explicitly producing the corresponding linear inequalities would be $\mathcal{O}(m)$ - still linear.

So why go through all the trouble of introducing an auxilliary variable at all? What's the problem with computing the convex hull directly?


texts: Does the infinite graph of diagonals have an infinite component?

texts:
Suppose we connect the points of $V = \mathbb{Z}^2$ using the set of undirected edges $E$ such that either $(i, j)$ is connected to $(i + 1, j + 1)$, or $(i + 1, j)$ is connected to $(i, j + 1)$, independently and uniformly at random for all $i, j$.

(Inspired by the title and cover of this book.)

What is the probability that this graph has an infinitely large connected component?
Similarly,
consider $\mathbb{R}^2 \setminus G$, the complement of the planar embedding of the graph.
What is the probability that the complement has an infinite connected component?

Clearly, if all the diagonals point the same way, both the graph and its complement have an infinite component. How about a uniform random graph of the above kind?


texts: Tractability of mutual information-augmented ensemble classification algorithms

texts:
I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an approach is both tractable and offers an improved convergence time over bruteforce methods and random forest classification on its own without a major reduction in classification.

Suppose we have a collection of data sets, $K$, that contains rows $\{k1, k2, ..., kn\}$. Each of these rows carries an unknown language $L$ in the context of an unknown, uniformly-applied noise function. Our hypothesis is that at least some subset of these data rows share information: that is, for some rows, $I(kx,ky) > 0$ for ${kx,ky} \in K$. Additionally, we hypothesize that multivariate mutual information $I(kx,ky,...) \not= 0$ for some set of multivariate relations. That is, that our graph contains compositions that are more informative in the context of multiply-chained relationships, or contain some XOR-shaped relationship.

If we attempt to bruteforce this space, because mutual information is commutative, we require n-binomial-n time and space. That is to say, to compute the mutual information of all combinations within collection $D$, we require $\sum\limits_{x=1}^n\binom{n}{x}$ time, assuming for simplicity that the comparison of each row is an $O(1)$ operation.

We would then prune output data set using a fixed cutoff value, $v$, retaining only connections where $I(kx,...) > v$. We would then sort this set in descending order of the number of terms and use this to construct an undirected graph, by connecting features that share positive mutual information and forming branches when multivariate mutual information is negative.

The obvious reduction to this complexity, at an error-bound cost in robustness, is to use random forest analysis. I wish to simplify this computation further, by computing the pairspace mutual information for each pair of rows, then using a cutoff value similar to $v$, construct sets that only contain the participating nodes of each of these graphs. These sets would then be fed into our random forest classifier to determine the shape of the graphs, at an expected reduced time for convergence.

Is this approach tractable? Even if so, are there better approaches to the pruning stage of this problem?

(Crossposted to Stats.SE)


texts: Number of different cycles in cyclic codes with length n

texts:
I am studying Information theory, coding theory in particular at the moment, and I am having trouble determining how many different cycles are defined by a certain generator polinomial?

Given a polinomial, for example $g(p)=p^6+p^3+1$, and the length of the code $n = 9$ how can I determine the number of different cycles that are defined? Everything is in modulo 2 arithmetics.

I know that the cycles (001)(010)(100) and (011)(110)(101) are defined, but how can I find the rest of them?

I also wonder if there is an explicit formula that can return me the result, maybe based on the different powers in the generating polinomial?

Thank you for helping me.


texts: How to translate general recursion into a set of $\mu$-recursive operator applications?

texts:
I'm trying to find a scheme to translate a functional language with let rec into a set of primitives called "generalized arrows", i.e. $\kappa$-calculus with extensions. The problem is that general recursion is not expressible in $\kappa$-calculus, so I had to extend it with minimization operator.

There is a previous question asking about translation of Ackerman function into $\mu$-recursive operators, but the solution of Klaus Draeger doesn't seem to me to be generalizable.

Is there any previous work on translating general recursion into a set of $\mu$-recursive operator applications?


texts:
Thanks for the comments, I refined the question.

What is the complexity relationship between counting and enumeration problems?
If a counting problem is #P-complete, it means that the enumeration version is #P-hard.

How about problems that can be solved in polynomial time? For example, do counting triangles and enumerating triangles in a graph have the same complexity lower/upper bound?

More specifically,

  Given an algorithm that can solve the counting problem in $O(f(n))$ time, can we also solve the corresponding enumeration problem in $O(f(n))$ time? Assume that the output size of enumeration problem is $O(f(n))$ or somehow can be compressed using $O(f(n))$ storage.

For example, we may use cliques instead of triangles to represent the output results of triangle enumeration to reduce the output size. It may be not an appropriate example since it may not reduce the worst case space complexity. But for some enumeration problems, I think it may be possible.

Could anyone give any explanations or references?


texts: What is known about matrix multiplication, and matrix circuits?

texts:
So I'm wondering, first off, where I can read up to get a feel for state-of-the-art matrix multiplication concepts.  I'll try to be more specific:

I'm wondering if there has been research on circuits that compute a pre-defined matrix function.  For instance, if we have a function such as $(AB)+C+(DEF)(AB)$, where all the variables are matrices with given sizes, how efficient can we make a circuit that computes this function?  I've been toying with an idea in which the entries are all computed modulo $p$.  So I'm wondering, broadly, what I can read up on to be up-to-date.


texts:
Does anyone know of interesting applications of Gröbner bases to theoretical computer science?

Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was wondering whether some tractable special cases were used to provide efficient algorithms/constructions/proofs in TCS or TCS-related areas (combinatorics, coding theory).


texts: Theoretical study of coordinate descent methods

texts:
I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ has the property that restricted to any single variable, it is easy to optimize. So coordinate descent proceeds by cycling through the coordinates, fixing all but the chosen one and minimizing along that coordinate. Eventually, improvements slow to a halt, and you terminate.

My question is: is there any theoretical study of coordinate descent methods that talks about convergence rates, and properties of $f$ that make the method work well, and so on ? Obviously, I'm not expecting fully general answers, but answers that illuminate cases where the heuristic does well would be helpful.

Aside: the alternating optimization technique used for $k$-means can be seen as an example of coordinate descent, and the Frank-Wolfe algorithm seems related (but is not a direct example of the framework)


texts:
Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently the rows of $A$ form a basis of the cocycle space of $G$ over $GF(2)$).

My question is: What additional criteria must be assumed (if any) to guarantee there is an $(m-1)$-dimensional subspace of $GF(2)^{m+1}$ which does not contain any column of $A$?

Any relevant references would be much appreciated.


texts: Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants

texts:
Let $A$ be a $3 \times 3$ or a $4 \times 4$ matrix with entries $a_{ij}$. Can someone provide me a matrix $B$ so that $\operatorname{per}(A) = \det(B)$? What is the smallest explicit $B$ that is known such that $\operatorname{per}(A) = \det(B)$? Any references on this with explicit examples?

Some restrictions could be the following cases:

Case $(1)$ Only linear functionals are allowed as entries of $B$.

Case $(2)$ Non-linear functionals are allowed provided each term has atmost $O(log(n))$ degree (degree is sum of degree of variables) where $n$ is the size of the matrix involved. In our case, upto degree $2$.


texts: How to prove relations between "classes" of types?

texts:
After reading Effects as Sessions, Sessions as Effects, I was wondering how would a proof of equivalence between both take place, or even, a proof of Sessions types being a Type and Effect System.

In a more generic fashion, how one can prove a relation (e.g. equivalence) between different "classes"* of types? Would that expressiveness test as done by Orchard and Yoshida be enough?

[*]: I don't know how to correctly define it, I don't want to use "kinds of types" or "types of types".


texts: Alternative exponential definition of Kolmogorov complexity

texts:
In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined as
$$ K(x) = \mu e (\varphi_e(0) \simeq x) \, , $$
the smallest $e$ such that the $e$-th program (in some enumeration) outputs $x$ on input $0$. This seems to give exponentially larger outcomes then the more common (rough) definition of $K(x)$ as "the length of the smallest computer program running on some fixed universal TM that returns $x$". How does Kikuchi's definition match up with the usual KC definition? Is this a common alternative? Does any major result in KC change/not work under this new definition, or can we just move everything by an exponent and rely on its monotonicity?
This is a cross post from MO. Since it isn't being answered there (even after setting a bounty), it was suggested I try asking it here.


texts: Total number of spanning trees of a set of graphs

texts: Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree theorem. Now consider a more complicated setting, in which each of the $n$ nodes in the graph has $m$ versions and each version has different connectivity with the other nodes of the graph. The connectivity between different versions of different nodes can be encoded with a 4-dimensional array A where A[i][k][j][l] is 1 iff the $k$-th version of node $i$ is connected by an edge with the $l$-th version of node $j$. Therefore we have $m^n$ different graphs. We want to compute the total number of spanning trees in these $m^n$ graphs. The brute-force approach that computes the number of spanning trees in each graph separately would require exponential time. My question is whether there is a polynomial-time algorithm.


texts: Is true randomness and the physical Church-Turing thesis incompatible?

texts:
As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are incompatible? The reason is that there is a physical process which can generate a random sequence of digits (i.e. a random oracle), but a Turing machine can not. Moreover, generating a random sequence of digits should never hit a "wall". We can continue generating them forever without issue. Once the heat death of the universe hits, random numbers will be generated automatically.

Of course, this might be like asking if Turing machines can toast toast, but I don't think so. Generating a sequence of numbers if a purely computational task, and it would seem that if a Turing machine can not generate a physically realizable sequence of numbers, then that would disprove the physical Church-Turing thesis. Also, it is normally assumed that the physical Church-Turing thesis implies that the universe is simulatable (it a Turing machine can't toast toast, but it can simple toasting). Randomness seems to forbid this.

So, are the physical Church-Turing thesis and true-randomness incompatible, or not?


texts:
I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed some paper or help analyze the problem?

Consider two sets of nodes, $U$ and $V$. $f_u(v)$ is the non-negative (integer) preference function of $u\in U$ towards $v\in V$. Similarly, $f_v(u)$ is for $v\in V$ towards $u\in U$. Let $E\subseteq U\times V$ be a set of pairs. Each pair $(u,v)\in E$ indicates that we can never allocate  one to the other.

$\pi$ is an allocation where $\pi(u)\in V$ is the node allocated to $u$ and $\pi(v)\in U$ is the node allocated to $v$. $\pi$ is weak-stable if there does not exist a pair ($u,v$) such that $f_u(v)>f_u(\pi(u))$ and $f_v(u)>f_v(\pi(v))$, which means that $u$ prefers $v$ to $\pi(u)$ and $v$ prefers $u$ to $\pi(v)$ simultaneously.

I want to compute a stable matching with maximum size, i.e. $maximize_{\pi}|\pi|$. Notice that, ties are allowed in any preference function.


texts:
Let $C$ be an arithmetic circuit that represents a polynomial $f\in\mathbb K[x_1,\dotsc,x_n]$, with the promise that $f$ has at most $k$ nonzero terms. What is (known about) the complexity of computing $f$ in its sparse representation, given $C$?

I am interested in deterministic and randomized complexity, and in the link with PIT. In particular, does the promise that $f$ is sparse imply good algorithms? A priori, I am more interested in the case of $\mathbb K$ being some finite field, though results over other fields may be relevant.


texts:
Possible Duplicate:
  Does $VP \neq VNP$ imply $P \neq NP$?

In his GCT papers Mulmuley first starts with the #P/NC question. And then gets into setting up a roadmap for how to show obstructions ( some sort of Weyl modules I gathered, if they can be constructed) could potentially rule out embedding of a class variety into another.

Is it clear, and almost obvious how that chain of argument ( if and when fleshed out) will automatically extend for P/NP separation? I am not a TCS expert - so I wonder if I am missing something obvious.


texts:
I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as $k \times n$ matrix over a finite field $\mathbb{F}_p$ (where $p$ is large prime), test if the matroid is isomorphic to the uniform matroid with $n$ elements and rank $k$. In other words, test if all $k \times k$ submatrices have rank $k$.
Is there some algebraic software that can solve this problem potentially much faster than brute-force? In particular I am interested in methods that are able to beat the ${n\choose k}$ brute-force on at least some yes-instances.
I have tried reducing to integer programming and solving with CPLEX, but it is worse than brute-force already on two-digit primes.


texts: What is the complexity of model checking Process Logic (LTL fragment)?

texts:
Process Logic is a modal logic allowing to reason about temporal properties of programs. Its formulae take the form similar to (Propositional) Dynamic Logic $[P]\phi$, with $P$ being a program (think regular expression) and $\phi$ being another process logic formula, however unlike PDL, it can contain temporal LTL-style modalities. Unlike LTL, the formulae are read as follows "along traces resulting from execution of $P$, $\phi$ holds", or plainly "during execution of $P$, $\phi$ holds". Temporal modalities correspond to an extension of LTL with a chop and slice operators.

I am interested in a fragment of Process Logic where $\phi$ wouldn't be a full PL formula, but rather a plain LTL formula without modalities of the form $[P]$.

Question: Are there complexity analysis results relevant to model-checking formulae of Process Logic, or related formalisms? I am interested in both, the the complexity analysis, as well as some ideas for algorithms for doing it.


texts: Minimising the maximum distance to the centre of a cluster of points

texts:
I have a set of points $C_i$ on a two dimensional plane and I want to find a point $P$ such that the maximum distance from $P$ to any of the points is minimised, i.e. minimise(max($||P-C_i||$)).

I've found that the centroid of $C_i$ gives a reasonable approximation, but does not find the optimal solution for $P$. I've also tried a few other options like finding the centroid of the convex hull of $C_i$ and they have all produced comparable or worse results.

I've come to the realisation that there's almost certainly not an analytic solution to my case, so I'm looking for an algorithm that would be faster than just doing a grid search around the area near the centroid.


texts: What good notations for deterministic context-free and visibly pushdown languages exist?

texts: Deterministic context-free languages (DCFL) and visibly pushdown languages (VPL) are both sets of formal languages between context-free languages (CFL) and regular languages (REG). Is there a readable notation that can be expressed in plain ASCII like Backus-Naur-Form for CFL and regular expressions for REG?


texts: More efficient non-uniform derandomization ?

texts: Adleman, FOCS'78 showed that any randomized circuit for inputs of length $n$ can be non-uniformly derandomized. However, the construction effectively duplicates the original circuit  $O(n)$ times, so the derandomized circuit is larger than the original one by a factor of $O(n)$. Is there any more efficient construction out there that multiplies the circuit size by a smaller factor  ?


texts: Does there exist a polynomial time algorithm to determine whether an equation is a consequence of (x+y)*(y+z)=(x*y)+(y*z)?

texts:
Consider the identity $C$
$$(x+y)\times(y+z)=(x\times y)+(y\times z).$$

Is the problem of determining whether an identity is a consequence of $C$ in universal algebra a polynomial time problem? This problem is in PSPACE since if $p=q$ is a consequence of $C$, then the terms $p$ and $q$ must have the same length and $q$ can be obtained from $p$ by just repeatedly replacing the operation $+$ with $\times$ and vice versa.

Algebras that satisfy identity $C$ are precisely the algebraic structures that can be used to produce commuting one-dimensional cellular automata (these cellular automata have two dimensions of time).

Note: We do not assume that the operations $+,\times$ are associative, commutative, or distributive in any way.

Moore, Cristopher; Boykett, Timothy. Commuting cellular automata. Complex Systems 11 (1997), no. 1, 55–64.


texts: Minimum weight matching in general graphs with additional input specifying the number of matched edges

texts:
We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of edges that the matching can use. In other words, given a graph G=(V,E) with
m=|E| and an integer k, where m and k are different in general, we need to find a matching of minimum weight that uses exactly k edges.

What is known about the problem? Do we have a polynomial time algorithm for the problem?


texts: Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?

texts: Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that once you get a solution, you use LDI to prove that it is optimal?? Any example?


texts: Consequences of Complete problems for NP intersects coNP

texts: What are the consequences of having complete problems in $NP\cap coNP$?


texts: A reasonable proof strategy for formally verifying Ukkonen's algorithm?

texts:
What's a reasonable proof strategy to formally verify Ukkonen's algorithm in, say, Coq? The ingredients as far as I can tell would be:

some form of separation logic to be able to reason about the state of the array as we are building up the data
separation logic to reason about suffix links and their validity
LOTS OF case analysis to prove that the invariants hold?? For example, this paper on 'Efficient Representation for Online Suffix Tree Construction' lists the cases in Ukkonen's algorithm --- this lists heavy cases anysis.

The #3 is the most finicky part of the whole enterprise; It seems like there ought to be a more 'principled' way to build the algorithm rather than the monolithic all-or-nothing proofs that we currently see?


texts: Complexity of $r$-sum as a function of integer sizes

texts:
Given $n$ distinct integers whose absolute value is of size $c_{n,k}=\lceil n^{1/k}\rceil$ bits ($c_{n,k}$th bit position is always $1$ for absolute value) we know that using dynamic programming we can find if there is a subset that sums to $0$ in $2^{O(n^{1/k})}$ time.

Given $r\in\Bbb N$ what is best known algorithm for complexity of $r$-sum on such situations for case (1) fixed $k>1$ and for case (2) $k=\theta((\log n)^\alpha)$ for some fixed $\alpha\in(0,1)$?

What happens at limit $\alpha\rightarrow1-$?


texts: What are semantic classes that have a syntactic equivalent?

texts:
This question is related to Benefits for syntactic and semantic classes.
As mentioned there, $\mathsf{PSPACE} = \mathsf{IP}$, which can be interpreted as the semantic class $\mathsf{IP}$ obtaining a syntactic definition.
What are other non-trivial examples for "syntacticizing" a class?


texts:
I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by    Umesh Vazirani and Thomas Vidick. They have used entangled particles as shared resources for a quantum nonlocal game aka CHSH game. Because of the acronym CHSH I assumed that the game was proposed by Clauser et al. in their famous paper, Proposed Experiment to Test Local Hidden-Variable Theories. But it looks they proposed only the famous inequality not the game. So, I am trying to trace the evolution of intuitions, ideas and results of the researchers which link the CHSH game with CHSH inequality.

The usual form of CHSH inequality is as follows.

$$-2 \le S \le 2$$

where,
$$S = E(a, b) − E(a, b') + E(a', b) + E(a' b')$$

Here $a$ and $a'$ are detector settings on side $A$, $b$ and $b'$ on side $B$, the four combinations being tested in separate subexperiments. The terms $E(a, b)$ etc. are the quantum correlations of the particle pairs, where the quantum correlation is defined to be the expectation value of the product of the "outcomes" of the experiment, i.e. the statistical average of $A(a)·B(b)$, where $A$ and $B$ are the separate outcomes, using the coding $+1$ for the '$+$' channel and $−1$ for the '$−$' channel.

In the original paper the inequality is Equation 1b which is as follows.

$$|P(\alpha) - P(\alpha + \beta)| \le 2 - P(\gamma) -P(\beta + \gamma)$$

As mentioned on page 883 of the paper greatest violation occurs when $\alpha = 22.5^\circ$ , $\beta = 45^\circ$, and $\gamma = 157.5^\circ$.

But the paper doesn't describe a nonlocal game. Even the later survey, Bell's theorem. Experimental tests and implications, by Clauser et al. also doesn't describe any nonlocal game.  So, my understanding is that the CHSH inequality is just a component of the CHSH game which was later defined by someone else.

After googling and tracing through the bibliographies of the papers for a while I found the paper, Consequences and limits of nonlocal strategies, by Cleve et al. In section 3.1 they have defined the CHSH game formally. I assume this is the first formal description of the game.

CHSH game is just another nonlocal game with two provers. In a CHSH game the contribution of the CHSH inequality is in the strategy of the game. For the nonlocal game the players, Alice and Bob employ strategies in answering to the referee. The strategies are quantum. The possible answers are boolean values. The probability distribution over the answers are the probability distribution retrieved from the measurements performed by them on a shared Bell state. This probability distribution is defined by the CHSH inequality. It's optimality is given by the Tsirelson's equality defined in Quantum generalizations of Bell's inequality  (4th condition of the theorem 1) by Tsirelson and Quantum and quasi-classical analogs of Bell inequalities by Khalfin and Tsirelson (Equation 2).

My question is : Am I able to trace the evolution of the ideas, intuitions and results between CHSH inequality and CHSH game correctly? Did I miss anything?


texts: Subset sum problem with at most one solution for any target

texts:
This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there.

We first consider the search version of the subset sum problem: Given a set $S$ of $n$ naturals, find a subset of $S$ that sums to exactly $W$. My question concerns this problem, with an additional restriction on set $S$: For all possible values of $X$, there exists at most one subset that sums to $X$ (in other words, no two subsets of $S$ sum to the same value). Can we find a polynomial time algorithm for this problem given this restriction?

My thoughts: The reason I think this may be possible is because this is an extremely strong restriction on $S$. Most sets are very far from having this property. The construction of an algorithm would likely begin with a strong characterization of the sets that even have this property, and work from there. However, I'm having trouble proving strong theorems about the sets that obey this restriction.


texts: Is there a non-deterministic version of the complexity class PP?

texts:
From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)

Edit: Perhaps I phrased the question poorly: I was thinking more along the lines of BPP's relation to MA? Is there an equivalent version of an interactive proof system where Merlin needs only convince Arthur with probability >1/2?


texts: Complete combinator basis for System F-omega

texts:
The S and K combinators form a complete (and Turing complete) basis when untyped. Within the Hindley-Milner type-system, and I believe within system $F$ as well, S and K can encode any well-typed function and, with the addition of the Y combinator, you gain Turing completeness (and adding other recursion combinations yields different recursive classes).

I highly suspect that the same can be done for System $F_{\omega}$ but I'm not sure how quite to do this. Is there a set of combinators that form a complete basis typed under system F-omega?

Additionally, in system $F$ type checking is only decidable with type hints (Church style). Would a combinator basis for system $F$ still have decidable type checking? If true would this still also be true of a complete basis for system $F_\omega$?

What about complete basis and decidability of type checking for Per Martin-Löf typing systems?


texts: Numerical precision in sum-of-squares method?

texts:
I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the rug.

From my (admittedly limited) understanding of the method, the following should be true:

  Given any system of polynomial equalities $E$ over real-valued variables $x \in \mathbb{R}^n$, where all parameters are $O(1)$ ($n$, $|E|$, and degree of each constraint), the degree-"$2n$" ($=O(1)$) SOS method finds a satisfying assignment of the variables or proves none exists in $O(1)$ time.

My first question is whether the above claim is true (is there a naive argument that doesn't use SOS to solve this?). The second question is where numerical accuracy fits in. If I want to get an assignment that satisfies all constraints to within additive $\varepsilon$ accuracy, how does the runtime depend on $1/\varepsilon$? In particular, is it polynomial?

The motivation for this is to, say, apply a divide-and-conquer approach on a large system until the base case is an $O(1)$-size system.

EDIT: From Barak-Steurer, it appears that the "degree $l$ sum-of-squares algorithm" on p.9 (and the paragraphs leading up to it) all define problems for solutions over $\mathbb{R}$, and in fact the definition of a pseudo-distribution in section 2.2 is over $\mathbb{R}$. Now I am seeing from Lemma 2.2, however, that one is not guaranteed a solution/refutation at degree $2n$ without binary variables.

So I can refine my question a little bit. If your variables are not binary, the worry is that the sequence of outputs $\varphi^{(l)}$ is not finite (maybe not even monotonic increasing?). So the question is: is $\varphi^{(l)}$ still increasing? And if so, how far you have to go to get additive accuracy $\varepsilon$?

Though this likely does not change anything, I happen to know my system is satisfiable (there is no refutation of any degree), so I am really just concerned about how large $l$ needs to be. Finally, I am interested in a theoretical solution, not a numerical solver.


texts: Trade off between time and query complexity for total functions

texts:
This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms:

The best query algorithm: this algorithm uses the minimal number of queries and then optimizes to reduce total time, while preserving queries (this has query complexity $Q_1$ and time complexity $T_1$).
The best time algorithm: this algorithm uses the minimal amount of time and then optimized to reduce total queries, while preserving time (this has query complexity $Q_2$ and time complexity $T_2$).

We saw that for partial functions, we can have arbitrarily large seperations between $T_1$ and $T_2$ and $Q_1$ and $Q_2$. However, this approach only works for partial functions.

For total functions, we can use the approach in this question to show that $T_1 \in O(n!2^n T_2)$ and for queries we can show $Q_2 \in O(2^{Q_1})$. Thus for total functions there seems to be a bound on the total separation. Can we improve it? Or come up with total functions with provable separations?

(We have a potential candidate for a separation in this answer but no provable results)


texts: Approximation algorithms for multicut for special classes of graphs

texts:
The multicut problem is the following.

Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of edges $F \subseteq E$ of minimum cost, such that in the graph $H=(V,E \setminus F)$, no terminal pair $s_i,t_i$ are in the same connected component. In other words, deleting the edges in $F$ will remove all paths between any terminal pair $s_i,t_i$.

This problem is NP-hard. For general graphs, an $O(\log k)$-approximation is known. For trees, a 2-approximation is known. It is also known to be APX-hard. Is there any other results known for special classes of graphs?

I am particularly interested in the following graphs, but other classes of graphs will also be informative.

Paths
Cycles
$n \times n$ grids
Outerplanar graphs
Planar graphs
Series-parallel graphs

Any reference or survey paper will be highly appreciated.


texts: Formal proof of correctness of Levenshtein distance

texts:
Has anyone formalized, in a proof assistant (constructively!) the correctness of the computation of Levenshtein distance ? The related Q&A on here is about paper proofs.  Searching around did not come up with any leads.
Note that I'm equally interested in correctness as that of a proof of optimality, i.e. knowing that an algorithm returns a correct sequence of edits, from which the distance is trivially computed, is quite interesting too. That the sequence is optimal can be a second step.


texts:
There are problems that are NP-Hard on undirected graphs(maximum weight independent set and graph coloring) but are polynomial time solvable on trees. Tree decomposition is a good tool to talk about the ground between a graph and a tree for undirected graphs with notion of treewidth. When graphs are relaxed to bounded treewidth graphs, they give a poly-time solution.

When the graph is directed there are notions like DAG-width, D-width etc. But if we have a problem which is Strongly NP-Hard on DAG and weakly NP-Hard on tree. I want to see what could be on the ground between the DAGs and trees?

Is there a notion of defining the ground between a DAG and a Tree( like bounded treewidth graphs are between a graph and a tree).

I need some pointers if available. I am currently at treewidth generalization for directed graph in this paper.


texts: Is this variant of bitwise cyclic tag Turing-complete?

texts:
Cross-posted to MathOverflow.

CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply of a string of 3 commands that operate on a queue of bits:

Command
Description

A
pop

B
push 0 if front is 1

C
push 1 if front is 1

These commands are executed in cyclic order from left to right. The queue is initialized with a single 1. If the queue becomes empty, the program terminates.
Let CT2 be the language that replaces command B with "push 0" (unconditionally). Is CT2 Turing-complete? One way to prove this would be to find a way to simulate CT or arbitrary tag systems in it, perhaps through some clever encoding.
Here are the busy beaver sequences for both languages with a 10K-step runtime limit (runtimes exceeding this are considered non-terminating):

Program length
CT
CT2

0
0
0

1
1
1

2
4
1

3
9
3

4
16
8

5
25
19

6
36
17

7
49
49

8
399
899

9
2159
1367

10
1407
300

11
7490
9893

12
9130
3348

Notice that CT2 also exhibits a rapid growth that is suggestive of Turing-completeness.


texts:
Given matrix $M\in\{0,1\}^{n\times n}$, let the minimum number of monochromatic rectangles it can be partitioned be $p$. Let the positive rank of $M$ be $\sigma$ and the rank be $r$. Is it known either $$p<r^{\log^dr}\mbox{ or }p<\sigma^{\log^c\sigma}\mbox{ or }p<(\sigma^{\log^c\sigma}r^{\log^dr})$$ hold true for some $c,d>0$?

Can $p<\sigma^{c}$ be true?


texts: How easy is it to switch the area of research in CS (going from M.Tech to PhD)?

texts:
I'm faced with a rather tough dilemma :-

I had completed M.Tech in CS 2 years back, completing my dissertation in the field of VLSI Testing. While I liked my work, I don't wish to go back to pursue my PhD in that - I've been strongly wanting to pursue a theoretical course (in approximation/online algorithms) as means for obtaining my doctoral degree.

However, since I've had no research experience in TCS(Theoretical Computer Science), I'm afraid that would hurt my chances of getting admission to a reasonably good school in the US - whereas, the research experience in VLSI (as well as the LORs from my adviser/committee members, who are well known in the field of VLSI) would have helped me get into a good program (but my enthusiasm in that field has already petered out).

That's why, I wanted to hear from people who have successfully migrated from their initial research field (in UG/MS level) and have been able to embark on a completely different field for their PhD - how did you explain the reason for your shift in the SOP, whether that affected their chances in getting into a top school etc. Also, for any academics browsing the question, what would be your take on it - do you always prefer students who have a background matching your interests only ?


texts:
Impagliazzo, Paturi and Calabro, Impagliazzo, Paturi introduced Exponential-Time Hypothesis (ETH) and Strongly Exponential-Time Hypothesis (SETH). Roughly, SETH says that there is no algorithm which solves SAT in time $1.99^n$.

I was wondering what would that mean to break SETH. We definitely need to find an algorithm which solves SAT in fewer than $2^n$ steps, but I don't quite understand what computational model we should use. As far as I know, results based on SETH (see, e.g., Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom) don't need to make assumptions about the underlying model of computation.

Assume, for example, that we found an algorithm which solves SAT in time $1.5^n$ using space $1.5^n$. Does it automatically imply that we can find a Turing Machine which solves this problem in time $1.99^n$? Does it break SETH?


texts:
Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. Suppose that $p$ and $t$ are specified with $O(n)$ bits -- this precision level is sufficient to describe all of the outputs in the range of $F$. I strongly suspect that there is no poly(n) time algorithm for computing $F$ exactly; is there any formal evidence of this?

Edit. As pointed out in the comments, the function above is of course computable in polynomial time. How about the following variant: $X_i$ are independent symmetric Bernoulli variables and $w_i\in[0,1]$ are weights specified with $O(n)$ bits each. Define the function
$$ F(w,t):=P( \sum_{i=1}^n w_i X_i > t) .$$
Hoeffding's inequality provides exponential bounds on $F$; what is the complexity of computing $F$ exactly?