texts: Best approximation for a HYPERGRAPH-MAXDICUT problem

texts:
Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every vertex $i_1$ has only $1$ outgoing hyperedge $\{i_1\rightarrow i_2,i_3,i_4,\dots,i_{c^a}\}\in\mathcal{E}(\mathcal{H}(a))$ which has $c^a$ vertices and every vertex is on $(c+d)^a$ hyperedges).

Consider the NP-complete HYPERGRAPH-MAXDICUT problem of given an integer $t$ and a hypergraph $\mathcal{H}(a)$ with above parameters, one has to decide if there is a subset $S \subset \mathcal{V}(\mathcal{H}(a))$ such that $$|\{\mathcal{I}=\{i_1\rightarrow i_2,i_3,i_4,\dots,i_{c^a}\}\in\mathcal{E}(\mathcal{H}(a))\mid i_1\in S \text{ and } \mathcal{I}\setminus i_1\cap S=\emptyset\}|\geq t$$

Can there be a $c^{a^{\beta}}$ approximation algorithm to HYPERGRAPH-MAXDICUT where $\beta\in(0,1)$? For which classes of $\mathcal{H}(a)$ could we have such approximation?

If $n$ is variable how does the factor depend on both $a$ and $n$?


texts: What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

texts:
Input: a graph with n nodes,
Output: A clique of size $O(\log n)$,
Providing links to references would be great


texts: Extended Church's thesis and internal parametricity

texts:
I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here.

Does $Internal\ parametricity \implies ECT$ hold?
For forumlation of ECT see https://en.wikipedia.org/wiki/Church%27s_thesis_(constructive_mathematics), also I am wondering about the internal version of it. In particular the formulation as stated in this paper in the form compatible with univalence axiom.

This question is motivated by the results in Parametricity and excluded middle, which shows that failures of parametricity are related to axioms without computational content such as Law of excluded middle and that ECT also implies failure of Law of excluded middle.

By internal parametricity I mean the internalization of this concept ala A computational interpretation of parametricity.

I am quite sure that the opposite direction, doesn't hold. Let me outline my reasons for this
for a function $f:\forall a.a \rightarrow a$, then if internal parametricity fails for this type, $ECT$ might still hold, i.e. if $f$ analyses type of its argument and acts as $\neg$ only for bools and $id$ everywhere else, all functions should still be computable and thus $ECT$ can still be admissible.


texts:
Suppose, we are given a graph $G = (V,E,d)$, where $V$ is the set of vertices, $E$ is the set of edges, and $d$ is a distance function $d: E \mapsto \mathbb{R^+}$. Let $S$ be the set of source vertices and $EX$ be the set of exit vertices in $G$. Further, we are given the integers $k, \gamma$ and $\delta$. A $(k, \gamma, \delta)$-hub is a set of vertices $H \subseteq V \setminus (S \cup EX)$ such that:

For any source vertex $s_i \in S$, there exists an exit vertex $t_j \in EX$ and a hub vertex $h_{ij} \in H$ such that $d(s_i,h_{ij}) \le \gamma$ and $d(h_{ij},t_j) \le \delta$,
$|H| \le k$, i.e., there are at most $k$ hub vertices.

Intuitively, a hub is a small set of vertices such that for any source vertex, there is a short path to some exit through an intermediate hub vertex.

An optimization problem is: given $\gamma$ and $\delta$, find the minimum $k$ such that there exists a $(k, \gamma, \delta)$-hub (or show that none exists). This problem is likely to be NP-hard, but I could not find a reduction from an existing NP-hard problem.

Is there any known hardness result or approximation algorithm for this problem?


texts: Explicit Ramanujan graph families (Reference Request)

texts:
I am looking for a reference for explicit families of $d$-regular Ramanujan graphs for fixed $d.$ In particular, I am looking for a family of $d$-regular graphs such that the associated reversible random walk on any such graph has eigenvalues $\lambda_1 = 1\geq \lambda_2\geq \ldots \geq \lambda_k$ with

$$\max_{2\leq i\leq k} |\lambda_i|\leq \frac{2\sqrt{d-1}}{d}~.$$

I want the absolute spectral gap bounded in this way, and therefore bipartite expanders won't do for me (since then, $\lambda_k = -1$).


texts: What would be the consequences of PH=PSPACE?

texts:
A recent  question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing plenty of reasons to believe $NP\neq PSPACE$.

What would be the consequences of the somewhat less dramatic collapse $PH=PSPACE$?


texts:
Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$?

It does not seem obvious to me how to use the above problem as an oracle to construct a coloring, so it is conceivable that this problem is efficiently decidable.  On the other hand, minor variants of NP-hard problems, such as this one, typically remain NP-hard.  But most of all, I do not know what problem is a good choice to reduce from.

Any thoughts?


texts: Termination checking for Scott-encodings in System F with positive-recursive types

texts:
Is there any research on termination analysis on Scott-encodings in System F with positive-recursive types.
All papers I have found use languages with constructors and case analysis (for example foetus).
But given that we can encode any ADT as pure lambdas, by defining an ADT as it's case analysis function, is it still possible to do termination checking similar to how it is done for ADTs?

For example we can encode the natural numbers as:

type Nat = forall t. t -> (Nat -> t) -> t
zero = \z s -> z
succ n = \z s -> s n

and then define addition like:

add n m = n m (\n' -> succ (add n' m))

Is it still possible to analyze the recursive calls for termination?
I am aware of Church-encodings but I am interested in structural recursion specifically.


texts: Being from Physics, I have been trained to look into a lot of problems from a geometrical point of view. For example the differential geometry of manifolds in dynamical systems etc. When I read the foundations of computer science, I always try to find geometric interpretations. Like a plausible geometric interpretation of recursively enumerable sets (I worked on a part where I tried to connect them with Algebraic Geometry by exploiting equivalence with Diophantine Sets but the connection seemed forced and I could not find a "natural" expression of the facts in that formulation) or a beautiful geometric result for a simple algorithm for sorting numbers. Though I am not an expert I have read surveys on Geometric Complexity Theory and it is surely an interesting program but I am more interested in having a geometric view of extremely fundamental concepts like the dynamics of a Turing Machine, Lambda Calculus or the structure of (un)computable sets (rather than specific problems). Is it a hopeless job to find geometrical structure in these objects or can one expect some intricate results? Is there any formulation of TCS which treats it geometrically?


texts: Approximating the value of k in $k$-mean clustering problem

texts: Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by sampling $poly(\frac{1}{\epsilon},\mathcal{o(n)})$ points from the set, algorithm outputs some good enough approximation of $k$ i.e., $\lceil{k(1+\epsilon)\rceil}$.


texts: Why can Lambda Calculus not represent some combinators?

texts: This paper suggests that there are combinators (representing symbolic computations) that can not be represented by the Lambda calculus (if I understand things correctly):


texts: Factoring with LLL when the form of the factors is given

texts:
Given a degree $2k$ reducible polynomial

$$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$

with

$$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $f_1(x)f_2(x)$ with $\text{deg}\big(f_i(x)\big)=\frac{\text{deg}(f(x))}{2}=k$ and each $f_i(x)$ irreducible.

Can the LLL algorithm be used to factor $f(x)$ in polynomial time and what is the complexity?

Note that $\text{gcd}(a_{2k},\dots,a_0)=1$ makes $f(x)$ primitive.

This answer tells that such polynomials have efficient factorization algorithms. Although the precise method is not mentioned there I belive LLL suffices and hence the question here. If LLL does do the job, can its complexity be improved from $(2k)^{6+\epsilon}$ arithmetic operations which is needed if the form of the factors are unknown.

Refer here for complexity of factoring primitive polynomials with integer ocefficents where the phrase

  We also mention Schönhage's method using $O(n^6+n^4\log_2^2l)$  bit operations for factoring polynomials with integer coefficients ($l$ is the length of the coefficients)

is used. $n$ is the degree and it corresponds to $2k$ here.


texts: What greedy algorithm satisfies greedy choice property but does not have optimal substructure?

texts:
Based on the textbook Introduction to Algorithms, the correctness of a greedy algorithm requires a problem to have two properties:

greedy choice property
optimal substructure

It is easy to come up with counter examples for which a greedy solution fails due to the lack of the greedy choice property, e.g. the 0/1 knapsack problem. But I find the other possibility pretty hard to imagine. Can anybody give me a problem and a corresponding greedy algorithm which satisfies the first property but not the second?


texts: Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

texts:
Say I have $n$ independent Bernoulli random variables, with parameters $p_1,\ldots,p_n$. Say, also, that I wish to decide whether their sum exceeds some given threshold $t$ with probability at least $0.5$. What is the computational complexity of this decision problem, when $p_1,\ldots,p_n$ and $t$ are represented in binary and given as input?

More generally, I'm interested in the generalization of this problem to (non-Bernoulli) discrete distributions. Specifically, there are $n$ independent random variables, each supported on at most $m$ rational numbers, with each variable's probability histogram given explicitly in the input. In this case, also, I want to decide whether the sum of these variables exceeds $t$ with probability at least $0.5$.

I have a feeling this problem is PP-hard, though I can't quite prove it. I wonder what the answer is, and whether it's already known.

Note that I'm not looking for approximation algorithms for this problem. It's clear that monte carlo methods yield positive answers to approximate versions of this decision problem. I'm interested in the exact decision problem as stated above.


texts: Is refuting candidate deciders of the halting problem computable?

texts:
No Turing machine can decide whether any given Turing machine will halt for a given input. That is:

If you give me a Turing machine which you claim can take a Turing machine and an input for that machine and will tell me whether the machine will halt,
There is some counterexample TM/input pair I can provide to that machine for which it will fail.

This is the undecidability of the halting problem. Old news.

My question is: Can such a counterexample be computed for any candidate decider of the halting problem?

That is, is there a Turing machine which can take as input some Turing machine and compute a TM/input pair for which the given Turing machine fails to decide the halting problem?

(Incidentally, I'm slightly over my head here, so I may be asking my question wrong, or asking a wrong question. Thoughts and pointers are welcome.)


texts: Combining subset sum and subset product problems

texts:
The subset sum problem and subset product problem are NP-complete.
Is the following problem polynomial-time solvable: given a set of positive integers, find a subset whose sum is $S$ and whose product is $T$.


texts: Looking for papers and articles on higher-order sequent systems

texts:
I am looking for work on systems that are similar to K. Dosen's higher-order sequents ("Sequent Systems for Modal Logic", JSL 50).  The only work that I am aware of is recent work by Iemhoff and Metcalfe ("Proof theory for admissible rules", Annals of Pure and Applied Logic 159 (1-2), 2009).

Are there other papers on such systems?


texts: Rounding to minimise the sum of errors in pairwise distances

texts:
What is known about the complexity of the following problem:

Given: rational numbers $x_1 < x_2 < \dotso < x_n$.
Output: integers $y_1 \le y_2 \le \dotso \le y_n$.
Objective: minimise $$\sum_{1 \le i < j \le n} e(i,j),$$ where $$e(i,j) = | (y_j-y_i) - (x_j-x_i)|.$$

That is, we would like to round the rational numbers to integers so that we minimise the sum of errors in pairwise distances. For each pair $i, j$ we would like to have the rounded distance $y_j-y_i$ as close as possible to the true distance $x_j-x_i$.

Motivation: a boring metro trip, and a poster that shows the "locations" of the stations at the resolution of one minute of travelling time. Here we are minimising the error that people make if they use the poster to look up the travelling time between stations $i$ and $j$, averaging over all pairs $i<j$.

(source)

For example, here we can read the following approximations of the pairwise distances between the four stations (using A, B, C, D for brevity):

A–B ≈ 1 minute, B–C ≈ 2 minutes, C–D ≈ 2 minutes
A–C ≈ 3 minutes, B–D ≈ 4 minutes
A–D ≈ 5 minutes

Is this the best possible approximation? If you knew the actual travelling times, could you find a better solution?

At first, this sounded like a simple exercise in dynamic programming, but now it seems that some amount of actual thinking is required.

Does anyone recognise this problem? Or see a clever algorithm for solving it?

Edit: There are some natural variants of the question that have been mentioned in the comments; let's give them some names:

floor/ceil version: it is required that $y_i \in \{ \lfloor x_i \rfloor, \lceil x_i \rceil \}$ for all $i$.
integer version: it is sufficient that $y_i \in \mathbb{Z}$ for all $i$.
monotonic version: it is required that $y_1 \le y_2 \le \dotso \le y_n$.
non-monotonic version: we can have $y_i > y_j$ for $i < j$.

The original question considers the monotonic integer version, but answers related to any of these versions are welcome.


texts:
Heller (Theorem 6) gave an oracle relative to which $NP=EXP$, and Homer & Selman gave an oracle relative to which $P=UP$ and $\Sigma_2^P=EXP$.
Beigel, Buhrman, Fortnow (freely available author's version) gave an oracle in which $P=\oplus P$ and $NP=EXP$ holds.

Is there an oracle that gives $P\neq UP=coUP=NP=coNP=\oplus P=EXP$?

Is there an oracle that gives $P=UP=coUP\neq NP=coNP=\oplus P=EXP$?

Or is it known $UP\neq EXP$ unconditionally?


texts: finding permutations which fulfills given conditions

texts:
Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill  the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be a finite set.
Let $g\colon K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_1$ and $>_2$ on $K$ such that
$$s \, >_1 \,\, t \text{ and } x \, >_2 \,\, y$$ if and only if
$$g(s,x) + g(t,y) \ge g(s,y) + g(t,x).$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?


texts: Show that minimal CFG is undecidable via mapping reduction

texts:
Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE.
The question itself was asked on Math.SE:

Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\textsf{CFG}}$ = $\{\, \langle G \rangle \ | \ G$ is a minimal CFG$\}$.
a) Show that $MIN_{\textsf{CFG}}$ is Turing-recognizable.
b) Show that $MIN_{\textsf{CFG}}$ is undecidable.

The OP figured out a), the relatively simple part, by himself. And I answered b) few days ago, by reducing to $ALL_{\textsf{minCFG}}$:

It suffices to focus on the case $\Sigma = \{0,1\}$. We argue that $ALL_{\textsf{minCFG}} \leq_T MIN_{\textsf{CFG}}$. That is, we can determine whether a minimal CFG can generate all possible strings, by using the oracle for $MIN_{\textsf{CFG}}$.
Let $G$ denote the minimal CFG we are interested. Since $G$ is minimal, there exists a length $p$ such that, for each rule $R$ in $G$ there exists a string $w_R$ with $|w_R|<p$ that can be generated by $G$, but not with $R$ deleted.
Note here that $p$ is computable in a brute force manner.
Construct $G^+_{a_1a_2\cdots a_p}$ where $a_i \in \Sigma$, by adding following rules in $G$:
$$
S \to a_1 a_2 \cdots a_pT \\
T \to T0 \ | \ T1 \ | \ \epsilon
$$
First, consider what will happen if $G^+_{a_1a_2\cdots a_p}$ is not minimal, thus, there exists a rule $R$ in $G^+$ being dispensable. By our construction it is clear that each rule $R$ in $G$ is indispensable.

If $S \to a_1 a_2 \cdots a_pT$ or $T \to \epsilon$ is dispensable, then we have $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$.
If $T \to T0$ is dispensable, then we have $(a_1 a_2 \cdots a_p \Sigma^* - a_1 a_2 \cdots a_p 1^*) \subseteq L(G)$. Because whether $a_1 a_2 \cdots a_p1^* \subseteq L(G)$ is easy to determine by some classical algorithm, we can also determine whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$.
It is similar for $T \to T1$.

Therefore, if $G^+_{a_1a_2\cdots a_p}$ is not minimal, we can determine whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$. What if it is minimal? In this case we will immediately know $L(G) \neq \Sigma^*$. So we can suppose that all possible $G^+_{a_1a_2\cdots a_p}$ is not minimal. Then by checking whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$ one by one and checking those strings of less-than-$p$ length, we can still decide whether $L(G) = \Sigma^*$.
Update. (Oct 12, 2020) After a short discussion with @xdavidliu I realized that the argument above can directly prove what we want, without a justification of uncomputability of $ALL_{\textsf{minCFG}}$. Recall that the reduction we have established achieves the following: Given a minimal CFG $G$, determine whether $L(G) = \Sigma^*$. Now if we want to decide whether $L(G_0) = \Sigma^*$ for an arbitrary CFG $G_0$, just simply feed into the (reduction) algorithm all minimal sub-CFG (test each sub-CFG by the $MIN_{\mathsf{CFG}}$ oracle to determine whether it is minimal) of $G_0$ and see if there is one that generates all strings.

However, there are still two questions:

Can we find a simple proof for undecidability of $ALL_{\textsf{minCFG}}$?

Since this problem appears in Chapter 5, in which Turing reduction has not introduced. I personally believe that there is an elegant proof using only mapping reduction. Can we do it?

Update. (Nov 5th, 2017) We found that, roughly speaking, we could prove $A_{\textsf{TM}} \leq_T ALL_{\textsf{minCFG}}$ by the same way as one for $A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$, just adding some stuff to show that the grammar we used in proving $A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$ is already minimal. However, I could not assert that this way is quite simple.
Comment. @Sylvain gives an elegant proof below, by showing
$$ PCP \leq_T FullPCP \leq_m MIN_{\textsf{CFG}}$$
in which I personally thought the key is that context-free language is closed under $h^{-1}$ he defined.


texts: Parametrized complexity of the 2-Long Paths Problem

texts:
Consider the following problem:

  Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$ to $t$, each of length $\ge k$.

Is there an FPT time algorithm for the above problem?

The problem of a single long path is known to be FPT, and so is deciding whether there exists two paths of length exactly $k$ from $s$ to $t$.

What happen if we combine both?


texts: Computational Complexity of the Frobenius Problem

texts:
The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\cdots+a_nx_n$ with non-negative integers $x_1,\ldots,x_n$; this largest integer $F$ is the so-called Frobenius number $F(a_1,\ldots,a_n)$.

Jorge Ramirez Alfonsin (Complexity of the Frobenius problem. Combinatorica 16(1):143-147, 1996) has shown that it is  NP-hard to determine the Frobenius number (under Turing reductions).

There is an unpublished manuscript by Shunichi Matsubara that seems to prove that the decision version of the Frobenius problem is $\Sigma_2^p$-complete under Karp reductions:

  The computational complexity of the Frobenius problem,
  S Matsubara - arXiv preprint arXiv:1602.05657, 2016 - arxiv.org

The paper by Matsubara has only a single citation on google scholar, and this is from another paper by the same author.  There is no conference version of the paper, and I also cannot find any journal version of this paper. The result (if correct) is important.

  My question is: What's going on with this paper? Has it been verified? Does it perhaps contain a gap? Is it under submission to some journal? Or is the result already known?


texts: How to write the introduction of a research paper?

texts: Apologies if this is too broad a question for this forum, but I'm interested in specific tactics and tips that researchers (in TCS) use to write the introduction of a research paper.


texts: Implications of unprovability of $P\neq NP$

texts:
I was reading "Is P Versus NP Formally Independent?" but I got puzzled.
It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not provable (say in $ZFC$). (Let's assume that we only find out that $\mathsf{P} \neq \mathsf{NP}$ is independent from $ZFC$ but no further information about how this is proven.)
What will be the implications of this statement? More specifically,
hardness
Assuming that $\mathsf{P}$ capture the efficient algorithms (Cobham–Edmonds thesis) and $\mathsf{P} \neq \mathsf{NP}$, we prove $\mathsf{NP\text{-}hardness }$ results to imply that they are beyond the present reach of our efficient algorithms. If we prove the separation, $\mathsf{NP\text{-}hardness}$ means that there is no polynomial time algorithm. But what does an $\mathsf{NP\text{-}hardness }$ result mean if the separation is not provable? What will happen to these results?
efficient algorithms
Does unprovability of the separation mean that we need to change our definition of efficient algorithms?


texts: Upward confluence in the interaction calculus

texts:
The lambda calculus is not upward confluent, counterexamples being known for a long time. Now, what about the interaction calculus? Specifically, I am looking for configurations $c_1$ and $c_2$ such that $\exists c: c_1 \rightarrow^* c\ \wedge\ c_2 \rightarrow^* c$, but $\nexists c': c' \rightarrow^* c_1\ \wedge\ c' \rightarrow^* c_2$.

Update: a necessary and sufficient condition for strong upward confluence discussed in arXiv:1806.07275v3 which also shows that the condition is not necessary for upward confluence by showing upward confluence for the interaction system of the linear lambda calculus.


texts: Is joint Kolmogorov Complexity order invariant?

texts:
Due to the symmetry of information, it follows up to an additive constant that

K(X,Y) = K(Y,X)

Does this hold for more than two data objects as well?


texts: Number of circuits computing a given function

texts:
Let's say we have some function that can be computed by a minimal circuit of size $m$ (using some metric, say, the number of gates). Other than this minimal circuit, there will be many other circuits computing the same function. Is anything known about how the number of circuits computing the function grows as you increase the allowable size? Does this depend greatly on the function?

Also, I would be interested in any relationship between the size/runtime of smallest programs computing function and the number of circuits computing it.


texts: Max-sum graph-partition for maximizing intra-edge weights?

texts:
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.

Input: A graph G with negative or non-negative integer weights on edges.

Output: A partition $P=\{P_1, ..., P_K\}$ of $V(G)$

Measure (to maximize): The sum of the weights for the edges with both endpoints in the same set of P, i.e.:

$$
M(P)=\sum_{i=1}^k \sum_{u,v\in P_i} w\left( u,v \right)
$$

where $w$ is the edge-weight function.

Thanks in advance for any suggestion.


texts: Best complexity bound for parallel matrix-vector product?

texts:
I'm looking for the best known complexity (and a bound for the number of processors invoved) to do the calculation of a $(n,n)$ matrix-vector product.

Thank you


texts:
Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.

For instance, the Approximation Algorithms entry of the above post cites a 2011 book (yet to be published) titled The design of approximation algorithms.

I think knowing recent works is really useful for whoever wants to get a taste of TCS trends. When drafts are available, one can check the books before actually buying them.

So,

  What are the recent TCS books whose drafts are available online?

Here, by "recent", I mean something that's no older than ~5 years.


texts:
I would be very much interested in references to the theory of submodular functions (from basics to advanced).

In particular, I am studying approximations to hard optimization problems and I want to develop my foundations in submodular functions as they are relevant to the optimization problems I have been studying.

Thanks in advance.


texts: Randomized Parallel Algorithm for Maximal Independent Set

texts:
There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized parallel algorithm for the maximal independent set problem.

These algorithms were the (or one of the) first examples where $k$-wise independent events/random variables are used to derandomize parallel algorithms. One algorithm (which is described here in the chapter "Fast MIS v2") works as follows:

The algorithm operates in synchronous rounds, grouped into phases.
A single phase is as follows:
1) Each node v chooses a random value r(v) from [0,1] and sends it to its
neighbors.
2) If r(v) < r(w) for all neighbors w in N(v), node v enters the MIS and
informs its neighbors.
3) If v or a neighbor of v entered the MIS, v terminates (v and all edges
adjacent to v are removed from the graph), otherwise v enters the next phase.

My question: Is it known that this algorithm also works if the random values are $k$-wise or even pairwise independent?

I didn't find anything in the literature but maybe I just miss something.


texts:
Background: I have been working on the following problem and was curious if this has come up before, what is it called in the literature, and what are previously tried methods? The motivation for working on this is involved with a certain sequence assembly problem I am working with in bioinformatics.

Problem:
Given a complete bipartite graph $G = (A, B, E)$ and positive integer weights, label edges (with non-negative integers) such that,

$\sum_j w_{ij} = w_i$

That is, for each vertex $i$, label incident edges such that their sum is equivalent to $w_i$.

Does a given instance have a solution?
(Sketch) Split each vertex $i$ with weight $w_i$ into $w_i$ copies of weight 1. So long as a perfect matching exists, we can solve the above equation.

How to solve?
Since the rank of bipartite graphs is $n - 1$ we can see that there exists a solution with at most $n - 1$ edges that will receive non-negative labels.

A simple greedy algorithm can produce a solution by simply matching the maximum vertices, labeling the edge as the min of the two, reducing the counts, and continuing on the remaining vertices.

But these solutions assume that the sums of the weights in $A$ and $B$ are equivalent. So how can we generalize when the weights are uneven? And furthermore, what if we want to maximize the number of 0 labelings?

Generalized Approach:
If we set weights in $A$ to positive values and weights in $B$ to negative values we may solve with a dynamic programming solution to minimize the absolute value of the sum of each connected component.

$\text{MinForest}(S, v) =
\begin{cases}
    \infty \text{ if } v \text{ is not valid in } S \\
    w(v) + min_{S’ = \text{ partitions of S with respect to r}} \text{MinForest}(S’ - \{r\}, i) \forall i \in S & \text{ otherwise}
\end{cases}$

where a vertex $v$ is valid iff $w(v) + \sum_{u \in \text{children}} w(u)$ is between 0 and $w(v)$. Any unlabeled edge will be assigned a value of 0.

Alternatives?
Now it appears similar to edge-graceful labelings, but without the modulo requirement. Are there other edge labeling problems similar to this? Additionally, do these current approaches seem sound?


texts: Locating a point inside a union of simple polygons

texts:
I have a set of polygons (convex, concave – non-convex, not self-intersecting) in a plane. There may be intersections between polygons.

Polygon is defined by points (cartesian coordinate system).

Please see the example image:

There is 2 polygons: the first is { A, B, C, D } and the second is { E, F, G }.

Question

How can I detect bounding "face" by the given point?

Solution for point 1 is { A, B, the intersection between |BD| and |EF|, F, the intersection between |FG| and |DC|, C, A }.

My idea

I tried some alghoritmus for boolean operations on polygons, but I think that this is not the right approach.
I can insert intersection points into original polygons and subdivided the original edge. After that, there is no intersection between polygon's edges.
Can I use some graph theory algorithm or algorithm for space partitioning?


texts: Implementation of surreal numbers for games

texts:
There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they do not form a set but a class).

See for instance this pdf or Wikipedia for an introduction.

They can be even more generalized to so-called "games", which are originally introduced to study combinatorial games. The original motivation of Conway was to analyze the game of Go, in particular the endgame is especially suited to be modeled with "surreal games".

My question is: do you know if anybody has implemented this approach in an AI (i.e. computer player) to improve its level at a game? I am especially interested in the case of Go, but others as well. If not, is there an obstacle or a reason why it would not be a good idea?


texts: What is known about the effectiveness of reliable computing?

texts:
How well has the following problem been investigated in TCS?
(I apologize if the problem statement sounds vague!)

Given a Model of Computation MC (Turing Machine, Cellular Automata, Kolmogorov-Uspenskii Machine ... etc.) and a  Model of Noise that could affect the computation of MC, is there a way of recovering from the errors caused by this noise in an effective way? For instance, say some type of noise affects a Turing Machine M, could one devise a Turing Machine M' that simulates M without a major cost and is reliable (which means that M' is tolerant to this noise)?

It seems that some models of computations are better than others in doing this: Cellular Automata for instance.
Any results if the noise is replaced by an adversary model?

Sorry for the tag! I don't have enough reputation to put a suitable tag (reliable-computing, fault-tolerant-computing ... etc.)


texts: What is the state of the art in cache algorithm theory?

texts:
I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a given memory segment and the speed of accessing it.

The familiar example is a program deciding when to read from / write to the processor cache, RAM and hard drive (via virtual memory).

I am particularly interested in the special case where the amount of data (including the program itself) that needs to be loaded significantly exceeds the capacity of the fastest storage available (i.e. the trivial solution of "just load up everything" is inapplicable).

I found that a Wikipedia page describing some common cache algorithms, which is almost what I want. Unfortunately, these are a bit low-level:

Many, such as LRU or MRU only make sense if you have subroutines that get accessed many times. If I have a program with a large number of subroutines, some of which are never accessed in a given run, and some of them are accessed one or two times, this strategy will never work because it can't build up enough data on what is commonly used and what is not.
Others, such as CLOCK, seem to deal with the peculiarities of implementation, rather than actually attacking the root of the problem.
I know there is a strategy where one first profiles a program during a test run, then provides the profile for the operating system to optimize accordingly. However, we must still solve the problem of providing a truly representative "example usage" while building the profile.

What I really want to learn about is this:When we abstract away all the technicalities of hardware and software, and speak in a purely theoretical context, is it possible to somehow analyze the structure of an algorithm, to work out an effective cache strategy for it based on high-level comprehension of what the algorithm is doing?


texts: Proving P-Isomorphism between two languges

texts:
The famous Isomorphism Conjecture states that all NP-complete problems are isomorphic via polynomial-time computable and invertible bijections (reductions). Padability is the only property that I know which can be used to show P-isomorphism between two languages (The most direct way is to present the reduction). My intuition suggests that two p-isomorphic languages are two different labelings for some language and should be related via permutations.

  What other techniques (or properties) can be used to show that two languages are P-isomorphic?

Motivation: I am trying to extend an analogy from GI. If two graphs are isomorphic then they are just two different labelings of the same mathematical structure. I guess there should be more natural and direct way than padability.


texts:
There are several algorithms to match a (simple) string against a regular expression (see here).
But if we have a lot of regexes, can we find one of them that matches the given string faster than checking the string with all of the regexes, one by one?
For example, if we have $k$ regexes, each with a length of $m$ and a string of length $n$, using the $O(mn)$ algorithm to match a string with a regex $k$ times gives us a running time of $O(kmn)$. Can we do better than this?
If you have an answer which requires some assumptions, please explicitly tell them.


texts: Is there an algorithm to generate proof in Coq?

texts:
I try to imagine using Coq to implement large and complicated software with specifications and proof. However, the manual work of writing proof is daunting. As a Coq newbie,  to specify an insertion sort algorithm costs me a week and nearly one thousand lines accounting for specifications and proof.

Is there possibly to relieve the developer's burden and make computer prove arbitrary theorem, which is much stronger than 'auto' tactic? If not, what is the unsolved question in it?


texts: Barendregt's proof of subject reduction for $\lambda2$

texts:
I found a problem in Barendregt's proof of subject reduction (Thm 4.2.5 of Lambda calculi with types).

The last step of the proof (page 60), says:

"and hence by Lemma 4.1.19(1), $\quad\Gamma,x:\rho\vdash P:\sigma'$."

However, according to Lemma 4.1.19(1) it should be $\Gamma[\vec{\alpha}:=\vec{\tau}],x:\rho\vdash P:\sigma'$, since the substitution is made to the whole context, not only to $x:\rho'$.

I guess the standard solution may be to somehow prove that $\vec{\alpha}\notin FV(\Gamma)$, but I am not sure how.

I had a proof simplifying it by relaxing the generation lemma of abstractions, but I recently found that there was a mistake and my proof is wrong, so I am not sure how to solve this problem any more.

Can somebody, please, tell me what I am missing here?


texts: Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$

texts:
For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not be induced, so that I want to return success also for instance in the case that G contains a $k$-clique.
I considered first a well known much simpler case, which is testing if $G$ is in fact a $k$ cycle. This can be done using $O(\log k)$ variables: Assume for simplicity for the moment that $k=4m$. Such an algorithm then boils down to the fact that we can test if two vertices have distance $t$ in space complexity $O(\log t)$. Then we test to see if there are four vertices $x_1,x_2,x_3,x_4$ such that $d(x_1,x_3)=d(x_2,x_4)=2m$ and all other distances between the $x_i$ are $m$.
Note crucially that this algorithm will fail to report true if the graph $G$ has $k$ vertices and contains a cycle, but also some additional edges.
My question now is the following: Is there a similar (or completely different) algorithm that detects when a graph $G$ of potentially large size, contains a $k$ cycle that is not necessarily induced, that has $O((\log k)^d)$ space complexity for some fixed $d \geq  1$? Clearly such an algorithm with space complexity $ k $ exists, but I would like to do better.
P.S. I don't know if it makes much of a difference, but in the applications I am looking at, $k$ will itself be of the order $(\log n)^2$ where $n = |G|$.
P.P.S Also, the graph $G$ that I am looking at will be sparse, they are Erdos-Renyi random graphs in $\mathbb{G}(n,n^{-c})$ for some $c\in (0,1)$.


texts: Compression algorithms for low-complexity strings?

texts:
Let $s$ denote a string over a finite alphabet, $n_s = |s|$ be the length of $s$, and $n_s^{*}$ denote the minimum description size of $s$ under a given computational model (TM, CFG, etc.). Are there compression algorithms that, when restricted to input $s$ where $n_s / n_s^*$ is large, achieve provably tighter approximations than algorithms with unrestricted input?

In other words, can a compression algorithm specifically tailored for low complexity inputs outperform the best general input algorithm on inputs of low complexity?

Admittedly, the question isn't completely precise, but I'm hoping to find results of roughly the same flavor.

Edit: See domotorp's answer below for a proof of the impossibility of a large class of low-complexity compression algorithms under the TM model. Note that this result does not bar the possibility of compression algorithms where the function $A$ (see the answer for context) is non-computable. For example, setting $A(|x|) = 100*BB^{-1}(|x|)$ where $BB^{-1}$ is the inverse busy beaver function, could make for a useful compression algorithm and is not covered by the proof.


texts:
Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $P_{i,\epsilon}$ be minimum multivariate polynomial such that $P_{i,\epsilon}=i\iff f=i$,  $P_{i,\epsilon}\in(i-\epsilon,i+\epsilon)\iff f=1-i$ where $\epsilon\in(0,1)$ at each $i\in\{0,1\}$.

Is atleast for one of $i\in\{0,1\}$,  degrees of $P_{i,\epsilon},P_{i,\epsilon/2}$ polynomially always related? They should be, however I cannot find a reference.

Straight forward interpolation arguments seems to fail as $\epsilon$ gets closer to 1 (but not exactly $1$).


texts:
Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each positive literal $x_i$ and for each negative literal $\overline{x_i}$. A literal is adjacent to a clause if and only if this clause contains the literal. $\phi$ is a planar instance If $G_\phi$ is planar.

Max planar 3-SAT is defined as the restriction of Max 3-SAT to planar instances.

This problem is known to be NP-hard. Is this problem also APX-Hard or there exists a known PTAS for this problem ?


texts:
It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers.

Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds?
Does $BPP$ in $P^{NP}$ and $SAT$ is in $2^{n}/f(n)$ at a superpolynomial $f(n)$ give anything for $BPP$ other than $BPP\neq NEXP$ ($NEXP\not\subseteq P/poly$ would hold)?
$BPP\neq EXP^{NP}$ and $BPP\neq NEXP$ mean $BPP\neq EXP^{NP}\cup NEXP$. What does this mean for lower bounds?
How far would we be away from $BPP\neq EXP$? Does this truly need good $PRG$s if $BPP\neq EXP^{NP}\cup NEXP$ is achieved without constructing good $PRG$s?


texts: Approximating the clique size of the graph

texts:
Let $G=(V,E)$ be a graph. For a given $\rho \leq |V|$ and $\epsilon$ with $(0<\epsilon<1)$, is there any sublinear query algorithm known/possible to decide if the graph has a clique of size $\rho$, or all the cliques are of size at most $\rho(1-\epsilon)$.

More precisely, for a given probability tolerance $\delta$ and error tolerance $\epsilon$, algorithm queries $f(\frac{1}{\epsilon}, \frac{1}{\delta}).o(n^2)$ many position of the corresponding adjacency matrix of the graph, and accept with probability at least $1-\delta$ if the graph has a clique of size $\rho$, or reject probability at least $1-\delta$ if all the cliques are of size at most $\rho(1-\epsilon).$

Thanks in advance.


texts:
I have been struggling with the technical details of a proof concerning auction theory in this paper:  http://users.eecs.northwestern.edu/~hartline/omd.pdf

Specifically, Theorem 2.5:  The necessary and sufficient conditions for a truthful mechanism.

Even more specifically, the forward direction of the proof, given on page 6.  Defining a truthful value as $v_i$, and a general, possibly false, value (e.g., a bid) as $b_i$, the author goes on to postulate two additional quantities, $z_1$ and $z_2$.

He then stipulates that $v_i = z_1$, $b_i = z_2$, which yields an inequality based on the previous work of the paper.

He also stipulates that $v_i = z_2$, $b_i = z_1$, which yields a similar but different inequality based on the previous work of the paper.

Okay, fair enough.  He then subtracts one inequality from the other and proceeds to derive his desired result on the basis of the consequent algebra.  I don't understand why that subtraction is justified-- he seems to be subtracting two inequalities that are based on entirely different (in fact, opposite) assumptions, and every time I see it I am thrown violently out of the train of thought.

I'm pretty sure I've seen this basic approach else (Shoham and Leyton-Brown's book?  I don't have it close at hand to check) so it seems to be a common idea, but I cannot get past it.  Can anyone help me to understand why that is valid, or explain to me what I am missing?

(I've tried proving the desired result by assuming three values-- a true value $v_i$, and two bids, $b_1$ and $b_2$-- to get his desired result, but also failed.  So it may not only be common, but necessary to do it the author's way.  But I still don't understand it.)

Update:  I knew I had seen something similar in Shoham and Leyton-Brown's book.  It is not exactly the same, but it is very similar and deals with the same equation and subject matter.  It is Case 1 of Theorem 10.4.3.

Starting from the context of truthful mechanisms, they first assume a truthful $v_i$ and a false $v_i'$ and derive that the payment based on $v_i$ is lesser than or equal to the payment based on $v_i'$, e.g., $P_i(v_i) \leq P_i(v_i')$.  They then assume the opposite, a truthful $v_i'$ and a false $v_i$, and derive the opposite result, that the payment based on $v_i'$ is less than the payment based on $v_i$, e.g., $P_i(v_i') \leq P_i(v_i)$.  Okay, that makes sense.

They then hold that the payments based on $v_i$ and $v_i'$ must be equal, as though they are saying that $P_i(v_i) \leq P_i(v_i')$ and $P_i(v_i') \leq P_i(v_i)$ are simultaneously true, even though they are the result of not just different, but opposite assumptions.


texts:
Consider the following problem. We are given a set of words $W \subseteq \Sigma^*$ and a set of sentences $S \subseteq W^*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^*$, to enumerate the sentences $s \in S$ that parse to $w$ (meaning that $s$ consists of the letters $w_1,\ldots,w_k$ and $w$ is the concatenation of the corresponding words).

The problem has an interesting variant which is the search of spoonerisms: we now allow some number $M$ of letters swap, and we want to enumerate the valid sentences obtainable from $w$ with at most $M$ swaps.

So my question is: under what condition on the language $S$ can the above  problem be solved in linear time? By this I mean time $O(|W|+|S|+|w|+c)$ where $c$ is the number of solutions.

(NOTE ADDED: in response to the comments below, the vocabulary $W$ is assumed to be finite, and the set $S$ can be infinite but "finitely described" by some device $\Delta_S$. As we can report all meaningful subwords of $w$ in $O(|w|)$ time, it may be possible to reduce my question to the enumeration of the accepting paths of a non-deterministic automaton or the derivations of an ambiguous grammar. What I am looking for is restricted models that allow a linear or amortized-constant delay enumeration of the parsings.)


texts: On the relation for the Myhill-Nerode theorem/syntactic monoid of a language

texts:
In order to characterize regular languages one finds the following definition useful:

  Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and write $x\equiv_L y$ if for all $z\in\Sigma^*$, $xz\in L$ if and only if $yz\in L$.

This is useful because $\equiv_L$ is an equivalence relation for every language $L$, and a language is regular if and only if the index of $\equiv_L$ (that is, the number of equivalence classes) is finite, as per Myhill-Nerode.

Now, I would like to define a binary operation $\cdot$ on $\Sigma^*_{/\equiv_L}$ as: $[x]\cdot[y]=[xy]$, where $[x]$ is the $\equiv_L$-equivalence class of $x$. This $\cdot$ will be operation that will give $\Sigma^*_{/\equiv_L}$ the structure of a monoid.

My question is: Is $\cdot$ well defined for an arbitrary language? How do I prove it?

So far, my approach has been trying to prove that the definition above is equivalent to:

  Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\sim_L$-related, and write $x\sim_L y$ if for all $w,z\in\Sigma^*$, $wxz\in L$ if and only if $wyz\in L$.

This is simple for regular languages, since one can take a minimal DFA and analyze its behaviour with strings that are $\sim_L$-related, but I'm struggling with a general proof. Maybe I'm missing something really simple, but in the paper where I found the "definition" of syntactic monoid, they just take $\Sigma_{/\equiv_L}$ and say "this is the monoid" without specifying the operation, and now that I'm trying to do it with full detail I'm completely stuck. Thanks in advance for your help!


texts: approximating problems described by multiple parameters

texts:
If I am given an optimization problem $L$, and a problem instance of $L$, which is of size $(m,n)$ (i.e. it depends on more than one parameter) then what does it mean to have, let's say, a linear-approximation algorithm?

Do I then mention whether it is linear in $m$ or $n$?

On the other hand I might be allowed to set $m$ equal to $n$ and thereby I would be obsolete to mention in which parameter the problem is linearly approximated.


texts: How to find the second smallest cut in a graph?

texts: For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, where $p$ is the size of the smallest cut?


texts: Can Category Theory help us prove P != NP?

texts:
Scott Aaronson, in this funny April Fools’ Day post, introduces a fictionalized $P \neq NP$ Proof and, among other things, he says that the proof make use of

Higher topos theory to solve the biggest problem there was.

More and more often I hear about  Category Theory (of which the former Higher Topos Theory is part) . Some say it is one of the branches of pure mathematics that is undergoing the most dramatic developments in recent years (some say it will replace set theory as the foundation of mathematics), while others are still a bit skeptical.
I am not aware of an extensive use in Computer Science, but (it seems that) it is becoming more and more present (functional programming, type theory, data structures, etc.).
Furthermore, I do not believe that Scott Aaronson mentioned it at random as a tool used for a possible proof of $P \neq NP$: the bird eye view it provides on mathematical and logical entities could be extremely important and help us to identify some common properties that we have never been able to see because we lacked the right tools.
My question is the following:
have there been researchers who have achieved important results in the field of computational complexity using the tools of category theory?
How do theoretical computer scientists see this theory?


texts: Complexity class separations without hierarchy theorems

texts:
Hierarchy theorems are fundamental tools. A good number of them was collected in an earlier question (see What hierarchies and/or hierarchy theorems do you know?). Some complexity class separations directly follow from hierarchy theorems.  Examples of such well known separations: $L\neq PSPACE$, $P\neq EXP$, $NP\neq NEXP$, $PSPACE\neq EXPSPACE$.

However, not every separation follows from a hierarchy theorem. A very simple example is $NP\neq E$. Even though we do not know if any of them contains the other, they are still different, because $NP$ is closed with respect to polynomial transformations, while $E$ is not.

Which are some deeper, unconditional, non-relativized complexity class separations for uniform classes that  do not directly follow from some hierarchy theorem?


texts: Separation of  space complexity classes: differeces between uniform class and nonuniform one as an analogy of circuit lower bounds project

texts:
Boolean circuit is used to measure  time in a nonuniform way, which Pippenger showed the relation between a time complexity of uniform model (Turing Machines) and size complexity of boolean circuits.  In the theory of space complexity, branching programs are considered to measure nonuniform space complexity.

I want a survey to answer the following question. My motivation came from the state of the art of attempts for separation between NL and L, that is , proving L vs NL problem. I would like to know whether there is any analogous approach for proving separation between  time complexity classes (deriving circuit lower bounds is useful for separation of time complexity classes because this approach is supported by Pippenger's theorem).  Thus I would like to know whether there is an analogue of Pippernger's theorem which would support non-uniform approaches for separation of the space complexity classes like circuit lower bounds.

Question:

  Is there a Nondeterministic polynomial size branching program solving
  an NL-complete problem  if we take a Nondeterministic Turing Machine
  solving the same problem ?

Reference:

N.Pippenger and M.Fischer, Relations among complexity measures, J of ACM, 1979.


texts: Characterization of deterministic pushdown automata

texts:
Is there any known characterization for deterministic pushdown automata (DPDA)?
For example, visibly pushdown automata(VPA) is a subclass of DPDA, which is characterized by following syntactic condition: push or pop decision depends on the input symbol.
Similarly, is there any either syntactic or semantic condition, which when satisfied by a given non-deterministic PDA, guarantees its determinizability?


texts: Reducing one problem to another are well known in various settings, such as many-one, randomized, truth-table, logspace or a whole slew of other reductions. Descriptive complexity can alternately characterize problems in $\mathsf{NP}$ using Logics, like e.g. extensions of first-order logic and others (see here for an introduction). So, it is natural to ask how to approach reductions in this context. Are there reductions, based on first-order, or second-order logics used in Descriptive Complexity, or even completeness under these reductions for descriptive complexity?


texts:
Is there a setting in which finding eigenvalues/eigenvectors is computationally hard? Or at least, not known to be computationally easy?

For example, how computationally hard or easy is it to find eigenvalues/eigenvectors of matrices over finite fields?  Suppose the field has size exponential in the dimension.  (Does the QR algorithm still converge?)

How about finding eigenvalues/eigenvectors of sparse matrices?


texts: Program inversion algorithms for higher-order programs

texts:
The term program inversion
has multiple shades of  meaning, but probably got started with
J. McCarthy's 1956 work The Inversion of Functions Defined by Turing Machines in the context of AI. By now many
connections between program inversion and other fields have been discovered, e.g. reversible
programming (physical and logical), partial evaluation, verification,
bidirectional programming, logic programming, and machine learning.

What is program inversion? In first approximation it's something like
this: Given a program $P : A \rightarrow B$ taking arguments of type
$A$ and returning results of type $B$, produce a program $P^{-1}$ that
is "somehow" the inverse of $P$. I'm deliberately being vague here,
since the concept can be (and is) clarified in various ways: e.g. is $P$ required to be injective?  Should
$P^{-1}(b)$ return all or just some $a$ such that $P(a) = b$?

There are generic ways of inverting a program, e.g. using
diagonalisation as already pointed out by McCarthy, or using partial
evaluation, but they tend not to be efficient. Also most work on
program inversion I'm familiar with does not seem to deal with full
higher-order programming languages (i.e. $\lambda$-calculi).

Reference request. What is the state-of-the-art in explicit algorithms for program
inversion of $\lambda$-calculi (with no restriction on higher-orderness)?


texts:
I'm trying to relate some notions of set theory to POVMs. I firstly explain the scenario with set theory and then in the POVM setting.

For some finite $N \in \mathbb{N}$, let $A_i$ and $B_i$ for $i=1,...,N$ be sets and assume there is some larger set $C$ such that $A_i\subset C, B_i\subset C$ for all $i$. Let's say for $J=\{1,...,N/2\}$ (just take $N$ even), I'd like to compute
$$  \left(\bigcup_{i\in J} A_i\times B_i\right)^c.$$

By De Morgan's laws we can write, $$\left(\bigcup_{i\in J} A_i\times B_i \right)^c =  \bigcap_{i\in J} (A_i\times B_i)^c  = \bigcap_{i\in J} A_i^c\times B_i \cup A_i\times B_i^c \cup A_i^c \times B_i^c$$

Now I'd like to do something similar for POVMs. Let's say I have two POVMs, $A = \{A_1,...,A_N \}$ and $B=\{B_1,...,B_N\}$.

For either POVM, I think it's clear how to define a complement for a subset. For example, if I want the complement of $\{A_2, A_3\}$, then I can do $\mathbb{1} - A_2 - A_3$. My interpretation is,  $\mathbb{1} - A_2 - A_3$ encompasses all events except $A_2$ or $A_3$. Now I want to define a (or be given a known) complement for a joint measurement.

Let's again say I have some $J = \{1, ..., N/2\}$ and I want to determine the complement of the sum joint measurements indexed over $J$. That is, I want somehow to define

$$\left(\sum_{i\in J}A_i \otimes B_i\right)^c$$

My first thought was to have

$$\left(\sum_{i\in J}A_i \otimes B_i\right)^c = \mathbb{1} - \sum_{i\in J}A_i \otimes B_i$$

But this only encompasses the analog of $\bigcup_{i \in J} A_i^c \times B_i^c$ and misses the analogs of $A_i^c \times B_i$ and $A_i\times B_i^c$.

Then I thought, in a De Morgan sense

$$\left(\sum_{i\in J}A_i \otimes B_i\right)^c = \prod_{i\in J} (A_i \otimes B_i)^c = \prod_{i\in J} (\mathbb{1} - A_i)\otimes B_i + A_i \otimes (\mathbb{1}-B_i) + (\mathbb{1} - A_i)\otimes (\mathbb{1}-B_i)$$

This I think is logical, but I've not yet convinced myself that it's true. Has anyone had a similar scenario?

Thanks for your time and sorry if the question isn't clear.


texts: Missing proof in Salil Vadhan's monograph on pseudorandomness, Random Walks and S-T Connectivity

texts:
In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing
http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf .

I don't state the full lemma as it appears at the above link. I only mention that I don't understand how to prove the first inequality
$$
  \left\Vert \pi M^t-u \right\Vert \leq \lambda(G)^t \left\Vert \pi -u \right\Vert
$$
According to the monograph it follows from definition of $\lambda(G)$ and induction, but I don't know how to prove the induction step.

If someone is familiar with this monograph, I'll appreciate any lead.


texts: Is deciding whether all satisfying assignments are NAE assignments coNP-complete?

texts:
Let the language $L$ consist of the $k$-CNF formulas $\phi$ with the property that any satisfying assignment $x$ of $\phi$ is a Not-All-Equal (NAE) assignment, i.e. every clause of $\phi$ has at least one false literal under $x$. Equivalently, $L$ includes those $k$-CNF formulas $\phi$ for which $\phi(x) \implies \phi(\neg x)$.

Clearly $L$ is in coNP, since a certificate for a "no" instance is given by a satisfying assignment which is not a NAE assignment. Is $L$ also coNP-complete for $k > 2$?

As a simple example consider the $2$-CNF formula $(a \vee b) \wedge (\neg a \vee \neg b)$ whose satisfying solutions have exactly one of $a$ or $b$ true, but not both.


texts: The complexity of comparing a power to some threshold

texts:
Consider the following simple problem:

  Given fractions $a/b$, $c/d$ with $a/b<1$ and $c/d<1$, and natural
  number $e$, both encoded in binary (so the problem size is
  $\log(a)+\log(b)+\log(c)+\log(d)+\log(e)$, decide whether
  $$(\frac{a}{b})^e \geq \frac{c}{d}$$.

What's the precise complexity of this problem? Note that one can simply compute $(\frac{a}{b})^e$, as it might require $e\cdot (\log(a)+\log(b))$ bits to store.

Any upper/lower bound? Do I miss something here?


texts: What is the role of predicativity in inductive definitions in type theory?

texts:
We often want to define an object $A \in U$ according to some inference rules. Those rules denote a generating function $F$ which, when it is monotonic, yields a least fixed point $\mu F$. We take $A := \mu F$ to be the "inductive definition" of $A$. Moreover, monotonicity of $F$ allows us to reason with the "principle of induction" to determine when a set contains $A$ (i.e. when a property universally holds on $A$).

In Coq this corresponds to writing an $\mathtt{Inductive}$ definition of $A$ with explicit introduction terms. While this definition denotes a particular function $F$, that function is not necessarily monotonic. Coq therefore employs some syntactic checks to guarantee the "well-formedness" of the definition. To some approximation, it rejects occurrences of $A$ in negative positions in the types of the introduction terms.

(If my understanding up to this point is flawed, please correct me!)

First, some questions in the context of Coq:

1) Does the syntactic check in Coq merely serve to ensure that the definition of $A$ is predicative? (If so, is impredicativity the only way in which the definition would be ill-defined?) Or is it checking for monotonicity? (Correspondingly, is non-monotonicity what might kill it?)

2) Does such a negative occurrence of $A$ necessarily imply that $A$'s definition is impredicative/non-monotonic? Or is Coq simply unable to verify that it's well-defined in that case?

And more generally:

3) What is the relation between predicativity of an inductive definition and monotonicity of that definition's generating function? Are they two sides of the same coin? Are they unrelated? Informally, which one matters more?


texts: Complexity of counting products of commuting operators drawn from a specific set.

texts:
I have run into the following problem in the course of trying to solve another problem, and have been unable to come up with a decent answer. This may reduce trivially to a known problem, but if so I am not seeing it, and would be extremely thankful if someone could point me in the right direction.

Given a set of unique $n \times n$ matrices $\{\lambda^{i}\}$ of the form $\lambda^{i}_{jk} = \delta_{jk} (1-2\delta_{x_i j}-2\delta_{y_i j})$, where $1\leq x_i < y_i \leq n$, is there an efficient way to calculate $N_D$, the number of operators of the form $C_b = \prod_i \left(\lambda^i \right)^{b_i}$ which satisfy $\mbox{Tr}(C_b) = D$? Here $b_i \in \{0,1\}$. I would be interested to know if there is any polynomial time algorithm, or even if it is in P/poly, or alternatively, if this reduces to some more studied open problem.

As things stand, I can currently obtain $\sum_D N_D$ and $\sum_D N_D D$, but not enough other linearly independent equations to be able to solve individually for each $N_D$.


texts: Subset sum vs. Subset product (strong vs. weak NP hardness)

texts:
I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard.

Subset Sum: Given $X = \{x_1,...,x_n\}$ and $T$, does there exist a subset $X'$ such that $\sum_{i\in X'}x_i = T$.

Subset Product: Given $X = \{x_1,...,x_n\}$ and $T$, does there exist a subset $X'$ such that $\prod_{i\in X'}x_i = T$.

I always thought the two problems were equivalent -- an instance of SS could be transformed to an instance of SP via exponentiation and an instance of SP to SS via logarithms. This led me to conclude that they both belonged to the same class of NP-hard -- i.e., they were both weakly NP-hard.

Further, it appears that the same recurrence could be used to solve both problems using dynamic programming with a very small change (replacing subtraction in SS with division in SP).

That was until I read chapter 8 of "Theory of Computation" by Bernard Moret (for those without the book, it has a proof of hardness of subset product via X3C -- a strongly NP-hard problem).

I understand the reduction, but cannot figure out what was wrong with my earlier conclusion (equivalence of the two problems).

UPDATE: Turns out that subset product is only weakly NP-complete (the target product is exponential in $\Omega (n)$). Gary and Johnson published this in their NP-completeness column in 1981, but I guess it was less visible than their earlier claim in their book.


texts: I am currently an undergraduate heading into my senior year. I've taken some theory/math classes (algorithms, and set theory/topology) in the past year and am taking quite a few more this year (more algorithms, abstract algebra, graph theory). My theory classes were the first classes in college I truly enjoyed. I definitely have an interest/passion for more theoretical and mathematical areas of computer science. I am pretty set on going to grad school/getting a PhD and if had the option, I would want to do research in an algorithms/theory group. However, I am wondering how can I assess if I have what it takes to succeed. Success in the case equates to getting a PhD --not necessarily at the most prestigious university -- but just making my contribution (as tiny as it may be) to the field. The reason I am asking this is because I am not some whiz kid who aces their classes with no sweat. I don't struggle by any means, but considering that algorithms/theory is a very intellectually challenging field, do you think hard work and passion for a subject can allow me to achieve my goal? Essentially, I don't want to put limitations on myself and regret not pursuing something I truly enjoy. However, at the same time, I want to be realistic with myself. Would love to hear your thoughts/experiences with this subject matter.


texts: When can we say that two programs are different?

texts:
Q1. When can we say that two programs (written in some programming language like C++) are different?

The first extreme is to say that two programs are equivalent iff they are identical. The other extreme is to say two programs are equivalent iff they compute the same function (or show the same observable behavior in similar environments). But these are not good: not all programs checking primality are the same. We can add a line of code with no effect on the result and we would still consider it the same program.

Q2. Are programs and algorithms the same kind of object? If not, what is the definition of an algorithm and how does it differ from the definition of a program? When can we say two algorithms are equivalent?


texts: A curious Wilf equivalence class of function compositions

texts:
I was enumerating pairs of functions from a size $n$ set into itself, and ran into these three relations which all generate the same integer sequence starting at index zero:  1, 1, 6, 87, 2200, 84245. $$f(f(f(x))) = g(f(x))$$
$$f(g(x)) = g(x)$$
$$f(g(x)) = g(g(x))$$

There is a deep theorem on trees in there but it isn't jumping out at me. Anyone have a reference in the literature?


texts: A "simple" language outside $CFL \cup coCFL$?

texts:
I am looking for a language L with the following properties:

L should not be context-free.
L's complement should not be context-free. (Everything you see in textbooks as prime examples of non-context-free languages seem to fail this second requirement.)
L shouldn't be too hard, For example, I know that undecidable languages fit the first two requirements, but what I want is a simpler language which can be recognized by a slightly "improved" automaton model, e.g. a probabilistic pushdown automaton.


texts: How fast can we compute the set inclusion poset of a set family?

texts:
Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.

I am looking for a data-structure that will allow me to quickly answer this.
My application is from graph theory where I want to see if deleting a vertex and its neighbourhood leaves any isolated vertices, and for each vertex list all isolated vertices it leaves.

I want to create the complete poset or eventually a $|\mathcal{F}|^2$ table storing true false telling exactly which sets are subset of eachother.

Let $m = \sum_{S\in \mathcal{F}} |S|$, $u = |U|$ and $n = |\mathcal{F}|$, assume $u,n \leq m$

We can generate the $n \times u$ containment matrix (the bipartite graph) in $O(un)$ time and then can create the table of all $n^2$ comparisons in $O(nm)$ time by for each set $S \in \mathcal{F}$, loop through all elements of all other sets and mark the set as not a subset of $S$ if they the element is not in $S$.
In total $O(nm)$ time.

Can we do anything faster?
In particular, is $O((n+u)^2)$ time possible or not?

I found some related articles:

A Simple Sub-Quadratic Algorithm for Computing the Subset Partial Order (1995)
which give an $O(m^2 / log(m))$ algorithm.

The Subset Partial Order: Computing and Combinatorics slightly improves the above but also claim that the above paper solves the problem in $O(md)$ time where $d$ is the max number of sets sharing a common element, but I could not understand this result.

In the article Between $O(nm)$ and $O(n^{\alpha})$ the authors show how to in a graph find the connected components after deleting the closed neighbourhood of a vertex by using matrix multiplication. This can be used to compute the set inclusion poset by finding all the components which are singletons with a runtime of $O((n+u)^{2.79})$.

Also this forum discussion is related:
What is the fastest way to check for set inclusion?
which implies a lower bound of $O(n^{2-\epsilon})$.


texts: Is $IP$ only interesting because of the equality to $PSPACE$?

texts:
I try to understand the advantages of using a probabilistic polynomial-time verifier instead of an determininistic one. I use as literature "Arora, Barak: Computational Complexity", in which the class $dIP$ is defined as languages where a deterministic polynomial-time proof system exists. I also undestand that $dIP = NP$. Now, the class $IP$ is defined as class where the languages have an interactive polynomial-time proof system, where the verifier works probabilistic. Shamir proved, that $IP = PSPACE$, this means, all PSPACE problems can be interactive proved in probabilistic polynomial time

Now, I am still asking myself if there are any advantages of class $IP$ without looking at $PSPACE$ problems? By knowing that $dIP = NP \subseteq IP = PSPACE$, I can use a deterministic polynomial-time interactive proof system and also a probabilistic polynomial-time proof system for a language in $NP$. The deterministic version would take one-round, because the verifier can ask the prover for the whole $NP$ witness. But, $NP$ witness are not "short", so, would be a probabilistic system with multiple rounds but shorter size (thus not the complete $NP$ witness) better?


texts: A 3-CNF formula that requires resolution width $5$

texts:
Recall that the width of a resolution refutation $R$ of a CNF formula $F$ is the maximal number of literals in any clause occurring  in $R$. For every $w$, there are unsatisfiable formulas $F$ in 3-CNF s.t. every resolution refutation of $F$ requires width at least $w$.

I need a concrete example of an unsatisfiable formula in 3-CNF (as small and simple as possible) that has no resolution refutation of width 4.


texts: Complexity of planted root of a system of quadratic homogeneous polynomials?

texts:
Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=0$ has an unique common root in $\mathbb Z^{2n}\backslash\{{(0,\dots,0)}\}$ upto sign and exchange of $x$ and $y$ variables we can extract the root with elimination theory in $2^{O(n)}poly(\max\log\|f_i\|_\infty)$ time if $m=2n$ holds. Assume we have $m=poly(n)$ random equations (note only any $2n$ of them can be algebrically independent and they will be so with high propbaility).

Is there an approach that can give $O(poly(n)poly(\max\log\|f_i\|_\infty))$ time?
What conditions are on the polynomials are needed to extract the unique root in $O(poly(n))poly(\max\log\|f_i\|_\infty)$ time in case roots 1. does not have a general algorithm?

Is this approachable using Sum-of-squares? Note $f_i^2$ are all non-negative and have same integer roots.


texts: Is there a model theory for Haskell type classes?

texts:
I am trying to understand the semantics of Haskell’s type classes (TCs) from a model-theory point of view. It might difficult to give precise model theoretic semantics to type classes (see 1, and 2).  I am aware that the primary purpose of TCs is to handle overloading effectively.  However, TCs also provide a means of specification which is broadly similar to signatures in algebraic specification languages (e.g. CafeOBJ or Maude).

The intuition is that TCs are roughly analogous to loose specifications and the instances are analogous to implementations. With the caveat that the equations are definitional in Haskell, axiomatic properties cannot be expressed.

Some rough, but correct, correspondence will do for my current research question.

Given a parameterized class (class Stack x ...), we can instantiate the formal parameter x with an actual parameter, say instance Stack [] =... (see below) The signature of the class methods and their type constraints are mapped to the more concrete instance (ignoring default implementations for the moment).

The instance (Stack []) could be regarded as a refinement of (Stack x) specification, the container part is fixed with [], but the type of the elements is left open.

Are the model classes of (Stack x) and (Stack [])  related by a reduct or forgetful functor from (Stack []) to (Stack x)?

Could I say (Stack []) implements (Stack x)?

Here is my attempt to relate models of TCs with  models of their instances.

Models specified in TC           =                      Set of models in instances

 $\mathcal{Mod}(\Sigma_c,\epsilon_c,\delta_c) =  \left\{\mathcal{Mod}_i(\Sigma_i,\epsilon_i,\delta_i)\right\}$

 The mappings could be interpreted as:

$\Sigma_c \rightarrow \Sigma_i $ identity signature morphism

$\epsilon_c \rightarrow \epsilon_i $ No default equations, mapping is from $\emptyset$ of sentences to implementaions.

$\delta_c \rightarrow \delta_i $ empty data type to concrete data type.

I do not think that there is any relation between the set of instances ({model1,model2,..} where each model in represented by a Haskell instance)

Any feedback on this posting would be most welcome.

Regards,

Pat

[1] A mathematical (categorical) description of type classes

[2] http://lambda-the-ultimate.org/node/3215#comment-47273

module StackTypeClass where

newtype V2 a = V2 (a, a) deriving Show

-- Specification

class Stack s where

  empty :: s a

  push  :: a -> s a -> s a

  top   :: s a ->  a

  pop   :: s a -> s a

-- Implementation or refinement 1

instance Stack [] where

  empty = []

  push  s xs   = s:xs

  top   xs     = head xs

  pop  xs    =  tail xs

-- Implementation or refinement 1

instance Stack (V2 ) where

  empty = V2 (undefined,undefined)

  push  s (V2 (a,b)) = (V2 (s,b))

  top  (V2 t)   =  fst t

  pop  (V2 (a,b))   =  (V2 (b,b))

{-

Tests

push (1::Int) (V2 ((6::Int),(1::Int)))

pop (push (7::Int) (V2 ((1::Int),(1::Int))))

top (V2 (6,5))

:t (empty::(V2 (a,a)))

:t (empty::([a])

-}


texts: Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

texts:
Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing machine) returns YES with probability ..." be always well defined in that case? Or would there only be upper and lower bounds for that probability? Or would there only always be some probabilistic Turing machine, for which the probabilities would be well defined (or at least the lower bound which should be bigger than 1/2)?

The class RP here is relatively arbitrary, and one could also ask this question for weaker notions of (pseudo-)randomness than Kolmogorov randomness. But Kolmogorov randomness seems to be a good starting point.

Making sense of the word "probability" would be part of an attempt to show that Kolmogorov randomness works for RP. However, let me try to describe one possible approach, to clarify what it could mean, and why I talked about upper and lower bounds:

Let $s$ be a (Kolmogorov random) string. Let $A$ be a the given probabilistic Turing machine corresponding to a language from RP. Run $A$ with $s$ as source for random bits $n$ times, continuing to consume previously unconsumed bits from $s$ one after the other.

For $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$, let $p_+^s:=\limsup_{n\to\infty}p_n^s$ and $p_-^s:=\liminf_{n\to\infty}p_n^s$. Observe that $p_+^s$ and $p_-^s$ are well defined for a given string $s$, even if it would not be random. But one may wonder whether $p_+^s=p_-^s$ in case $s$ is Kolmogorov random, or whether $p_-^{s_1}=p_-^{s_2}$ for two arbitrary Kolmogorov random strings $s_1$ and $s_2$. Or whether there exists a $p\geq 1/2$ such that $p\leq p_-^s$ for any Kolmogorov random string $s$.


texts: Complexity of bounded degree full contraction

texts:
This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows:

Instance: A graph $G$ and two integers $d$ and $k$.

Question: Is there a graph $H\in \mathcal{H}_{\le d}$, where $\mathcal{H}_{\le d}$ denotes the class of graphs that have maximum degree at most $d$, such that $G$ is $k$-contractible to $H$?

Theorem 3 of that work states that $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ is NP-complete for any fixed $d\ge2$.

I am interested in the similar problem, which one might call $\mathrm{B{\scriptsize OUNDED}\ D{\scriptsize EGREE}\ F{\scriptsize ULL}\ C{\scriptsize ONTRACTION}}$:

Instance: A graph $G$ and an integer $d$.

Question: Can $G$ be fully contracted (reduced to a single vertex) ensuring that $H\in \mathcal{H}_{\le d}$, for every intermediate graph $H$ generated in the contraction sequence?

Has this problem ever been studied? Is it NP-complete in general for connected graphs? Is it easier for any well-studied classes of graphs (for which the decision is not immediately obvious, e.g., cycles)?


texts: Computing the Fourier-Walsh coefficients of an arithmetic circuit

texts: Given an $f$-fan in arithmetic circuit of depth $d$ over $GF(q)$ (for some prime $q$) and the set of variables $(x_1,\ldots,x_n)$, what is the state of the art upper bound for calculating the Fourier-Walsh coefficients of the polynomial it represents ?


texts: What kind of optimization problem is that?

texts:
I am new here as a writer but I read this group from time to time.
I am thinking about the following problem.

Problem description:

Assume we have an area $A$ of size $1000 \times 1000$ cells.
One cell is addressed with $(x,y)$ pair, where $x$ and $y$ are positive integers.
We are given the set of points (locations) on area $A$, lets say we have $N$ locations. These locations are fixed and given as an input. In practice N is lower than 1000.
In each location we can build a sender station that sends some signal. Sender stations can have 4 levels: 0,1,2,3. Building a sender station with proper level costs: $c_0=0$, $c_1>0$, $c_2>c_1$ and $c_3>c_2$ respectively. Costs are equal for each location. Moreover costs are fixed and given as an input. Each sender station covers given circular area with signal. Radius are following: $r_0=0$, $r_1>0$, $r_2>r_1$, $r_3>r_2$. Radius is fixed and given as an input.

Question: What level of sender station should be build in each location in such a way, that: all locations are covered with signal and the total cost of building is minimized?

My question to that is: what kind of theoretical problem is that? Is there some easy transformation to some well known optimization problem?

This is not a homework from university, just my own riddle :)


texts: Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

texts:
Roughly speaking, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.

The algorithm specifies splitting the edges at their midpoint (except in the case of small input angles where concentric circular shells are suggested. This question is unrelated to these cases.)

In certain domains, given a segment, there are points on the segment that I would prefer to split on that are not necessarily the midpoints (unrelated to the concentric shell trick). These points are chosen based on some domain specific underlying data (considerations beyond the graph structure the algorithm is aware of).

What are the implications of splitting on non-midpoints?
What needs to be taken into consideration when selecting among several non-midpoint candidates?
Does splitting on non-midpoints affect any of the convergence properties
of the algorithm?

Another way to ask this is: Are there split points that are better (by some interesting measures) than the a-priori selected midpoints?


texts: Can "$x(\lambda y.P\;)z$" be $\beta$-reduced?

texts:
Consider the untyped $\lambda$-calculus expression

$$x(\lambda y.P\;)z$$

...where (FWIW) $z$ is not free in $P$, and $P$ does not contain a redex.  Can this expression be $\beta$-reduced?  I've consulted several textbooks, but they are all silent on this point (as far as I can tell).  Application is left-associative, so the fully-parenthesized rendition of the expression above would be

$$((x(\lambda y.P\;))z)$$

The formalism, as given in all the textbooks I've consulted, specifies a $\beta$-reduction for $((\lambda y.P\;)z)$, namely $((\lambda y.P\;)z)\; \triangleright_{\beta} \;([z/y]P\;)$, but not one for $((x(\lambda y.P\;))z)$.  Therefore, the answer to my question would appear to be "no", but a derivation I'm working my way through seems to require an invalid-looking $\beta$-reduction of the form

$$((x(\lambda y.P\;))z) \;\; \triangleright_{\beta} \;\;(x([z/y]P\;))\;.$$

Any help with this would be appreciated.  In particular, reference to a treatment of the $\lambda$-calculus that explicitly adjudicates this question would be very helpful.  Thanks!


texts: How to find a merge tree for a set of words?

texts:
Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider the following random process which labels the nodes of $T$ in a bottom-up order. Given an unlabeled node $x$ whose children $y,z$ have been labeled with words $w_y,w_z$, we assign to $x$ a word $w_x$ as follows:

  For each $i \in [n]$:

  (1) if $w_y[i], w_z[i]$ are equal to the same letter $a$, then set $w_x[i]$ to $a$;

  (2) if $w_y[i], w_z[i]$ are equal to different values $a,b$, then set $w_x[i]$ to $a$ with prob. $p(a)/(p(a)+p(b))$, and to $b$ otherwise.

Let $w_r$ be the random word assigned to the root at the end of this process. Can we devise a polynomial-time strategy to maximize $Var(w_r) = \sum_{i \in [n]} Var(w_r[i])$? This could be done either 'globally' (by constructing the tree at once) or 'online' (by selecting a 'locally optimal' matching for each generation).

The intuition is that a node $u$ represents a 'genetic group' which profiles is described by the distribution of $w_u$, and that we would try to mix groups at each generation in order to maximize the genetic diversity. This is probably NOT desirable in practice due to the possible effects of dominant/recessive mutations.


texts: Data structure for dynamic memory allocation

texts:
Think of the cell-probe model.  Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and executes every operation in worst-case deterministic O(log n) time where n is the total size of the memory?

By avoiding memory segmentation I mean that if the total number of free cells is F, then I should be able to allocate a contiguous segment of F cells or about F cells.


texts: Definition of convex optimization problem by Stephen Boyd and Lieven Vandenberghe

texts:
Boyd and Vandenberghe say that a convex optimization problem is one of the form:

  minimize $f_0(x)$ subject to
  $$f_i(x)\le 0,  i=1,\ldots m$$
                $$a_i^\top x=b_i, i=1,\ldots p$$

where $f_0, \ldots,f_m$ are convex functions and the equality constraint functions must be affine.

My question is, what stops me from converting the equality constraint functions into inequalities so that I am no longer restricted to affinity with those functions? (any equality $a=b$ can be expressed as $a\le b$ and $a \ge b$).


texts:
Given a connected arbitrary network $G = (V,E)$, where $V$ is a set of nodes (processors) and $E$ is the set of edges between the nodes. Each node $v _i$ is assigned a non-empty set $S(v _i)$, where $\bigcup _i S(v _i) = S$. The set $S$ is a universe of size $k$. The objective is to let each node  $v _i$ find  a subset $S'(v _i) \subseteq S(v _i)$ such that (by simply communicating with each other).

$\bigcup _i S'(v _i) = S$
For each $v_i$ and $v _j$ such that $i \neq j$, $S'(v _i) \cap S'(v _j) = \emptyset$.

The idea is that no two set $S'(v_i)$ and $S'(v _j)$ share any common elements, while a set $S'(v _i)$ may be empty. Yet, every element of $S$ must be in a set $S'(v _i)$.

The problem is quite simple as you notice. The problem is at least as costly as election. My questions though:

Are there similar problems to this problem (note that the sets are not processors !)
Do you think there are efficient randomized distributed algorithms for this problem ?  Any hints for some techniques that may help break the election bound. (By randomized: I mean I may relax the Req2. such that some nodes have intersecting sets, but not many of them).

Note: any computational model would be accepted (I m just looking for hints). But asynchronous computational model with unique ID's is perhaps the most preferred.


texts: Is there a survey of the semantics of various programming language features?

texts:
Is there a survey (from paper, book chapter, tutorial, links, ...) of the semantics of various programming language features? I was originally overwhelmed by the features of D in here http://www.digitalmars.com/d/2.0/comparison.html

I would like to see what I could possibly get from here, although I have asked a similar question on stackoverflow and understand these two sites have different perspectives.

Really appreciate your reply! Thanks to Dave Clarke for his suggestion on meta！


texts:
It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$.

Moreover, a graph $G$ has one of $K_{3,3}$ or $K_5$ as minor if and only if it has one of $K_{3,3}$ or $K_5$ as topological minor.

Furthermore, in a writeup by Bruce Reed i saw the following theorem.

Theorem: For any graph $H$, there is a finite set $\mathcal{Z}(H)$ of graphs such that $G$ has $H$ as a minor if and only if $G$ contains a subdivision of some element of $\mathcal{Z}(H)$.

So, my question is under what condition $\mathcal{Z}(H)=\{H\}$ or in other words, what properties must $H$ have so that $\mathcal{Z}(H)=\{H\}$ ?


texts: Face-walks in rotation systems for graphs

texts:
Given a graph $G$, a rotation system for $G$ is composed of two elements:

$\pi = \{\pi_v: v\in V(G)\}$, where $\pi_v$ is a cyclic permutation of the edges incident on $v$. Thus if $e$ is an edge incident on $v$, $\pi_v(e)$ is another edge incident on $v$, and we say that $\pi_v(e)$ comes after $e$ at $v$.
$\lambda:E(G)\rightarrow \{-1,1\}$ is a function that assigns to each edge a sign $\pm 1$.

Given a rotation system for a graph $G$, we define a face-walk as a walk in $G$:

$$v_0e_1v_1e_2v_2...e_nv_0$$

such that:

$e_{i+1}=\pi_{v_i}^{r_i}(e_i)$ for $1\leq i<n$;
$e_1=\pi_{v_0}(e_n)$;
$\lambda(e_1)\lambda(e_2)...\lambda(e_n)=1$.

Here, $r_i=\lambda(e_1)\lambda(e_2)...\lambda(e_i)$ and $\pi_v^{-1}$ denotes the inverse cyclic permutation to $\pi_v$ (that is, $\pi_v^{-1}(e)$ gives the edge that comes before $e$ at $v$).

According to Theorem 3.2.2 in Topological Graph Theory by Gross and Tucker:

  Every rotation system on a graph $G$ defines (up to equivalence of imbeddings) a unique locally oriented graph imbedding $G\rightarrow S$. Conversely, every locally oriented graph imbedding $G\rightarrow S$ defines a rotation system for $G$.

In the same book, an algorithm is given to trace the faces of the embedding. One starts with any vertex $v_0$ and any edge $e_1$ incident on $v_0$ and proceeds to complete a face-walk. They claim that this will give a face boundary of the embedding. To understand this, I need to see a proof for the following two statements:

Given any vertex $v_0$ and any edge $e_1$ incident on $v_0$, one can complete a face-walk starting at $v_0e_1$. Clearly a sequence $v_0e_1v_1e_2v_2...$ can be extended indefinetely. The question is whether this sequence will be periodic.
Each edge either belongs to exactly two distinct face-walks (and appears once in each), or it appears exactly twice in one face-walk.

Neither of these claims is proved in the book.


texts: Algorithmic advantages of pathwidth over treewidth

texts:
Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth $k$, it also has treewidth at most $k$, while in the converse direction, treewidth $k$ only implies pathwidth at most $k\log n$ and this is tight.

Given the above, one may expect that there may be a significant algorithmic advantage to graphs of bounded pathwidth. However, it seems that most problems which are FPT for one parameter are FPT for the other. I'm curious to know of any counter-examples to this, that is, problems which are "easy" for pathwidth but "hard" for treewidth.

Let me mention that I was motivated to ask this question by running into a recent paper by Igor Razgon ("On OBDDs for CNFs of bounded treewidth", KR'14) which gave an example of a problem with a $2^{k}n$ solution when $k$ is the pathwidth and a (roughly) $n^k$ lower bound when $k$ is the treewidth. I am wondering if there exist other specimens with this behavior.

Summary: Are there any examples of natural problems which are W-hard parameterized by treewidth but FPT parameterized by pathwidth? More broadly, are there examples of problems whose complexity is known/believed to be much better when parameterized by pathwidth instead of treewidth?


texts: Circuit complexity lower bounds and uniformity

texts:
I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results.

For example, the word problem for regular languages is known to be $NC^1$-complete under $AC^0$-reductions and in ALogTime, which equals DLogTime-uniform $NC^1$. But the latter is not known to equal $NC^1$. Maybe I am misunderstanding something about the $AC^0$-reduction, but I would not think that it is powerful enough to "handle" the non-uniformity? This would be the only explanation I can come up with.


texts: Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?

texts:
In many publications on the computational complexity of Sum of Squares (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g.

Rounding Sum-of-Squares Relaxations
Sum-of-Squares Lower Bounds for Sparse PCA

I was curious why this number $4$ seems so crucial here. What is the difficulty of higher order SoS relaxations?


texts: Practical algorithms for finding small arithmetic circuits

texts:
I have a multivariate integer polynomial $f : \mathbb{Z}^n \to \mathbb{Z}$ given as either as a circuit or as a list of monomials.  I am interested in practical (though obviously exponential time) algorithms for finding smaller circuit representations of $f$.

The application is finding succinct representations of geometric predicates obtained by factoring other geometric predicates.  Typically the input is a predicate with a succinct circuit, and for geometric reasons the factors are likely to have succinct circuits as well even if factoring algorithms produce monomials.  The first predicates I want simplified have degrees up to 8 and minimal circuit size in the low 10s.  Somewhat expensive is okay: I can afford to wait a day for the answer.

Three questions:

For the promise problem where we know a succinct circuit of given size exists, what is the best worst case algorithm?  Is it possible to do significantly better than enumerate-all-circuits?
Are there practical circuit simplification algorithms which are both incremental and complete, in that they start with simple transformations (removing partial common factors, etc.) but are guaranteed to eventually find the minimal circuit?
Do the lifting techniques used to reducing polynomial factoring and irreducibility testing to bivariate polynomials extend to finding circuits in any useful way?


texts: Commonality of minimal Kolmogorov structure functions

texts:
A typical $B$ is difficult to define precisely.  Intuitively, it is the sort of bitstring that will be generated most of the time by randomly drawing 0s and 1s.  However, the concept can be clarified by examining properties.  A property $p$ applies to typical $B$s if the proportion of $B$s having that property is greater than or equal to 0.5,
\begin{align*}
\frac{|\{B: p(B)\}|}{|\{B\}|} \geq 0.5.
\end{align*}

For instance, a typical $B$ has the property that $K(B) = \ell(B)$.  In other words, a typical $B$ is not compressible.

Is the minimal Kolomgorov structure function (MKSS) a typical bitstring in some TM encoding?  In other words, is there some TM encoding such that a bitstring generated by randomly drawing 0s and 1s likely to be a MKSS?

I think the answer is no, because incompressible bitstrings do not have a nontrivial MKSS, and most bitstrings are incompressible.


texts: Finding 3SUM witness when promised a solution

texts: Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $O(n^2)$ (modulo logarithmic improvements) solution still the best algorithm or is there a sub-quadratic algorithm known?


texts:
I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting counter-evidence. Here are two examples:

Random oracle hypothesis: relationships between complexity classes that hold for almost all relativized worlds, also hold in the unrelativized case. This was disproved by the result $IP=PSPACE$, and by showing that $IP^X\neq PSPACE^X$ holds for almost all random oracles $X$, see The Random Oracle Hypothesis is False.
Bounded error randomness properly extends the power of polynomial time (i.e., $P\neq BPP$). This was believed for a while, but later, due to sophisticated derandomization results and their connections to circuit complexity,  the opposite conjecture ($P=BPP$) has become prevalent (although still open).

Which are some other conjectures that failed the test of time?


texts: What can we say about a fixed point for a provability predicate in deductively defined theory that satisfies diagonalisation lemma

texts:
I am wondering whether this is the right site to ask this question, but since it involves proof and diagonalisation, hopefully it is the right place.

I am curious and trying to reason about what consequences we get if we use the predicate in the diagonalisation lemma as the provability predicate. I don't think I succeeded, I would appreciate if anyone could lend some help.

So here it is:

  Suppose Pr is a provability predicate for a deductively defined theory T, where T is a theory satisfying the diagonalisation lemma. Suppose A is a FIXED POINT for Pr in T, that is, that $T\vdash Pr(\ulcorner A\urcorner)\equiv A$.

My question is: What can we say about the formula A? Is it provable in the theory T? Is it refutable in the theory T? (That is, is its negation provable in T?) Could it be either provable or refutable?

I tried to reason as follow: (To be honest I have not yet got the hang of it, I find this topic a bit confusing, so there should be many flaws in my reasoning, please kindly correct my mistakes)

Since $T\vdash Pr(\ulcorner A\urcorner)\equiv A$ so $T\vdash A$. In words, since T can show that $\ulcorner A\urcorner$ is provable iff $A$, so T can show A. So A is provable in T. I don't think it sounds correct, but I have no idea how to fix it.

To grasp the concept better, I think it is easier for me to think of an example, but I am still struggling to find one. I am trying to find examples of formulas which are fixed points for Pr in the theory of Peano Arithmetic.

What I can think of about properties of numbers are like eveness, primeness. So suppose Pr represents there is a proof that $\ulcorner A\urcorner$ is even, and A is "I am even". Is my example correct? Again, I am really doubtful about my own example.

Also, if anyone has any better way to understand the topic, I would be more than happy to learn.

Many many thanks in advance, I really appreciate any helps.


texts: moments of complexity for random restriction

texts:
Suppose C is a large circuit computing a function $f:2^n \rightarrow 2^m$. For a function $g$ let $B(g)$ denote the size of the minimal Boolean circuit computing $g$. What can be said about the moments of $B(g)$ for $g$ a random restriction of $f$? What about the same question for the concatenation of $k$ random restrictions for some fixed $k$?

Apologies if this question is too basic, but I haven't found a source that directly addresses this question, if you know of one please let me know.


texts: What is the complexity of rectangle packing when rotations are allowed?

texts:
In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$.  The task is to find a placement of  $r_1,\ldots,r_n$ inside $R$ such that none of the $n$ rectangles overlap.
Generally, the orientation of each rectangle $r_i$ is fixed.  That is, the rectangles cannot be rotated.  In this case, the problem is known to be NP-complete (see, e.g., Korp 2003).

What is the complexity of the rectangle packing problem if rectangles can be rotated by $90$ degrees?

Intuitively, allowing rotations should only make the problem harder since one should first choose an orientation for each rectangle, and then solve the no-rotation packing problem.  But the NP-hardness proof of the no-rotation case is a reduction from bin-packing and seems to critically depend on the fixed orientation of each rectangle in order to construct the bins.
I have not been able to find a corresponding NP-hardness proof for the case in which rotations are allowed.