texts:
Let us define a class of functions over a set of $n$ bits. Fix two distributions $p, q$ that are "reasonably" different from each other (if you like, their variational distance is at least $\epsilon$, or something similar).

Now each function $f$ in this class is defined by a collection of $k$ indices $S$, and is evaluated as follows: If the parity of the selected bits is 0, return a random sample from $p$, else return a random sample from $q$.

Problem: Suppose I'm given oracle access to some $f$ from this class, and while I know $\epsilon$ (or some other measure of distance), I don't know $p$ and $q$.

  Are there any bounds on the number of calls I need to make to
  PAC-learn $f$ ? Presumably my answer will be in terms of $n, k$ and $\epsilon$.

Note: I didn't specify the output domain. Again, I'm flexible, but for now let's say that $p$ and $q$ are defined over a finite domain $[1..M]$. In general, I'd also be interested in the case when they are defined over ${\mathbb R}$ (for example, if they're Gaussians)


texts: Does Huffman coding always produce shorter codes than the Shannon code?

texts:
Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$.
Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and
let $L(C)$ be the expected length of the code.
The Shannon code produces a prefix code $C_{Sh}$ with
the lengths of the codewords $l_i =\lceil \log_2 \frac{1}{p(i)}\rceil $.
The Huffman code produces a prefix code $C_{Hu}$ which
is minimal in expected length, but
with non-explicit individual codeword lengths.
Let $H(X)$ be the entropy of $X$.
We have
$$H(X)\leq L(C_{Hu}) \leq L(C_{Sh})\leq H(X)+1.$$

My Question:
Though Huffman code produces expected lengths at least as low as
the Shannon code, are all of it's individual codewords shorter?

Follow-up Question:
If not, do the lengths of all the codewords in a Huffman code
at least satisfy the inequality:
$$ l^{Hu}_i<\log_2 \left(\frac{1}{p_i}\right)+1 ? $$

(I'm looking for proofs/counterexamples.)


texts: Complexity of edge coloring in planar graphs

texts:
3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable".

  What is the complexity of 3-edge coloring of cubic planar graphs?

Also, It is conjectured that $\Delta$-edge coloring is $NP$-hard for planar graphs with maximum degree $\Delta \in${4,5}.

  Has any progress been made towards resolving this conjecture?

Marek Chrobak and Takao Nishizeki. Improved edge-coloring algorithms
for planar graphs. Journal of Algorithms, 11:102-116, 1990


texts: Is there a relativized form of Rice Theorem?

texts:
Suppose $P_1$ and $P_2$ are nontrivial semantic properties of Turing Machines, and suppose that $P_1\wedge P_2$ is nontrivial given $P_1$.  Can one claim that $P_1\wedge P_2$ is undecidable given an oracle for $P_1$?

A specific example: Let $P_2$ be a nontrivial property of total functions.  Is it undecidable when inputs are restricted to machines which are known to compute total functions?

The usual proof of Rice Theorem, via reduction from the Halting Problem, does not seem to work in this case.


texts: Determining the number of clusters using property testing algorithm

texts:
We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of the above problem. The algorithm samples $O(\frac{kd}{\epsilon}\log \frac{kd}{\epsilon})$ many points from the set, and distinguish between following two cases with probability at least $\frac{2}{3}$:

-algorithm ACCEPTS, if all the points are $k$-clusterable.

-algorithm REJECTS, if points are $\epsilon$-far from $k$-clusterable, i.e. any $k$ unit balls covers at most $(1-\epsilon)n$ points.

Now, using the above algorithm as a subroutine can we approximate the value of $k$ (number of clusters), i.e., if we can ignore at most $\epsilon n$ points (because now we don't have the promised version of the input) from the input,
then we need to determine the number of clusters in the input.

(I was thinking to do some kind of binary search over $k$, start with k=2, if algorithm ACCEPTS then k=2, if REJECTS then try for k=4 and so on.)

Pls let me know if there is any confusion in the problem.


texts: Program equivalence wherein the programs are known to always halt

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

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


texts:
In parametrized complexity, $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$. It is conjectured that each of the containments is proper.

If $\mathsf{FPT}=\mathsf{W}[P]$ then $\mathsf{P}=\mathsf{W}[P]$.

But does it follow that

If $\mathsf{FPT}=\mathsf{W}[1]$ then $\mathsf{FPT}=\mathsf{W}[P]$ ?
or
If $\mathsf{W}[t-1]=\mathsf{W}[t]$ (for some t) then $\mathsf{FPT}=\mathsf{W}[P]$ ?


texts: What is the difference between standard SIFT descriptor and upright SIFT descriptor?

texts:
I am conducting a research on the topic of mobile location recognition and recently I have reached the issue of extracting discriminative features. I've read that for upright images is strongly suggested using upright keypoints since they are more discriminative. My problem is that I don't understand clearly what is exactly an upright SIFT descriptor, the reference I found coining the term is:

Handling Urban Location Recognition as a 2D Homothetic Problem

Concretely in the reference they say the following:

  ... for images in which gravity direction information exist we project
  the gravity direction onto the facade and align the keypoints with
  this direction (upright SIFT) ...

My only clue is an implementation of this upright SIFT descriptor as part of an academic project from a course of Digital Image Processing at Stanford

Thank you very much, I would appreciate any insight.


texts: Hardness of approximately counting independent sets with a PRAS, rather than FPRAS

texts:
It is known that approximately counting the independent sets of a graph is hard, even if randomness can be used, and even if we restrict ourselves to bounded degree graphs with degree bound at least 6. Specifically, if an FPRAS exists for such a graph class, it is known to imply the unlikely collapse $\mathsf{NP}=\mathsf{RP}$.

My question is: what happens if we are satisfied with a PRAS, rather than FPRAS? That is, in the same setting, we only require that the algorithm runs in polynomial time for any fixed error parameter $\epsilon>0$, but does not have to be polynomially bounded in $1/\epsilon$. Is there any hardness result known with this weaker assumption?


texts: How efficiently can circuits over sets of naturals be transformed to boolean circuits?

texts:
I am interested in reducing a circuit over sets of naturals (see here for some basic notions about this type of circuits) to a boolean circuit computing the same output. A very basic circuit of this type is a circuit $C_s$ defined over a beginning subset of $\mathbb{N}$ (i.e., $\{0,...,n\}$) containing only $\{\cap,\cup\}$ gates. My question is how efficiently can a boolean circuit $C_b$ be constructed that computes the same output as $C_s$ and whether there exists a lower bound on the size of such a $C_b$.

The simplest way I can think of, in order to achieve the above, would be to represent a set $S$ by a binary array $\mathbf{s} = s_1,...,s_n$ of size $n$ where a 1 in position $i$ would signify that element $i \in S$. With this representation in mind, a union operation between sets $S,P$ can be implemented by $n$ OR gates by performing a point-wise OR for arrays $\mathbf{s}$ and $\mathbf{p}$. Likewise, intersection would be captured by point-wise AND. This approach would imply that $|C_b| \in O(n)$ and likewise for the reduction time (with a multiplicative factor of $|C_s|$).

Can someone point out whether this approach is optimal or whether there is a better way to achieve the above? More importantly, is there a known lower bound for transformation of circuits over sets of naturals to boolean circuits? My research is security-motivated and the problem is governed by a security parameter $\lambda$ such that $n \in O(2^{\lambda})$ hence my approach is infeasible as it yields exponential size $C_b$. (EDIT: Assume each set $S$ is of size only $O(poly(\lambda)$)


texts:
Planar graphs are $K_{3,3}$-free. Such graphs can be decomposed into tri-connected components, which are known to be either planar or $K_5$ components.

  Is there such a "nice" decomposition of graphs of genus one ?

In their seminal work on graph minors, Roberston and Seymour showed that every minor-free graph can be decomposed into a "clique-sum" of "almost planar" graphs. This, of course, applies to bounded-genus graphs also. I am looking for decompositions specific to graphs of genus one, to better understand their structural properties.


texts: What makes a language (and its type-system) capable of proving theorems about its own terms?

texts:
I've recently attempted to implement Aaron's Cedille-Core, a minimalist programming language capable of proving mathematical theorems about its own terms. I've also proven induction for λ-encoded datatypes on it, which made clearer why his extensions would be necessary.

Nether less, I'm still left wondering where those extensions came from. Why they are what they are? What justifies them? I know, for example, that some extensions, such as recursion, ruin the language as a system for proofs. If I decided to also extend CoC with other primitives, how would I justify? I understand a proof of normalization is necessary, but that doesn't prove those primitives "make sense".

In short, what specifically what qualifies a language (and its type-system) as a system capable of proving theorems about its own terms?


texts: Why is non-determinism (Push-down automata) necessary?

texts: I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such languages?


texts:
Jianer Chen's paper "Characterizing parallel hierarchies by reducibilities" Information Processing Letters 39(1991) 303-307 shows the theorem:

If $NC^{k+1} = NC^k$ then we have $NC = NC^k$

His proof is for uniform circuit classes. What is for non uniform classes? Does the result still hold?


texts: Log-space reduction from Parity-L to CNOT circuits?

texts:
Question.

In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is ⊕L-complete (under logspace reductions). It is clear that it is contained in ⊕L; how does the hardness result hold?

Equivalently: is there a logspace reduction from iterated matrix products modulo 2, to iterated products of elementary matrices (the invertible matrices which realize row transformations) mod 2?

Details

A controlled-NOT (or CNOT) operation is a reversible boolean operation, of the form
$$
\mathsf{CNOT}_{\!h,j} (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j\,, \;\ldots\;, x_n)
\;\;=\;\;
(x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j \oplus x_h\,, \;\ldots\;, x_n)
$$
where only the j th  bit is changed, and that bit is changed by adding $x_h$ modulo 2, for any distinct positions h and j. It is not hard to see, if we interpret $\mathbf x = (x_1\,, \;\ldots\;, x_n)$ as a vector over ℤ/2ℤ, that this corresponds to an elementary row transformation modulo 2, which we may represent by a matrix with 1s on the diagonal and a single off-diagonal position. A CNOT circuit is then a matrix product consisting of a product of some elementary matrices of this type.

The paper by Aaronson and Gottesman mentioned above (which, very incidentally to this question, is about a class of quantum circuits which can be simulated in  ⊕L) has a section on computational complexity. Towards the beginning of this section, they describe ⊕L as follows:

  ⊕L [is] the class of all problems that are solvable by a
  nondeterministic logarithmic-space Turing machine, that
  accepts if and only if the total number of accepting paths
  is odd. But there is an alternate deﬁnition that is probably more intuitive to non-computer-scientists. This is
  that ⊕L is the class of problems that reduce to simulating
  a polynomial-size CNOT circuit, i.e. a circuit composed
  entirely of NOT and CNOT gates, acting on the initial
  state |0...0⟩. (It is easy to show that the two deﬁnitions
  are equivalent, but this would require us ﬁrst to explain
  what the usual deﬁnition means!)

The target audience of the article included a substantial number of non-computer-scientists, so the wish to elide is not unreasonable; I'm hoping someone can clarify how this equivalence holds.

Clearly, simulating a product of such matrices can be performed in ⊕L as a special case of evaluating coefficients of iterated matrix products (mod 2), which is a complete problem (under logspace reductions) for ⊕L.
Furthermore, as the CNOT matrices just perform elementary row operations, any invertible matrix can be decomposed as a product of CNOT matrices. However: it is not clear how to me how to decompose even an invertible matrix mod 2 into a product of CNOT matrices by a logspace reduction. (Indeed, as noted by Emil Jeřábek in the comments, Gaussian elimination suffices to compute determinants mod 2, which is a ⊕L-complete problem: so a direct attack by decomposing e.g. invertible matrices as products of elementary matrices seems not to be feasible in logspace unless L = ⊕L.) To say nothing of matrix products which are not invertible. So some cleverer reduction seems to be required.

I hope someone can provide a sketch of this reduction, or a reference (e.g. a text for which this is an exercise, if it is simple).


texts: Where can I find examples of error correcting codes of the following types?

texts:
First, apologies if this question is in appropriate or trivial for this site. I'm a physicist looking for some help outside his comfort zone.

In PRL 87 167902 (2001) it is claimed that

"...for an arbitrarily small $\delta>0$ there exists an error-correcting code $E: \{0,1\}^n \rightarrow \{0,1\}^m$ with $m\leq n / \delta^c$ (for some constant $c$) such that the Hamming distance between any two distinct code words $E(x)$ and $E(y)$ is between $(1 - \delta)m/2$ and $(1 + \delta)m/2$."

In the paper, this is known because of non-constructive proofs of existence. I would like to know if any explicit examples of such codes (or similar ones, or even better ones) exist, given that paper was 16 years ago.

In particular, I'm interested in codes $E: \{0,1\}^n \rightarrow \{0,1\}^m$ where $m = O(n)$ and the Hamming distance between two distinct code words has a lower bound at least linear in $m$ (I'm pretty flexible about the behaviour with $\delta$, as I just need the $\delta = 1/2$ case).

I ask here becuse I'm sure this will be a very easy question to the correct person, but I am not that person and I'm not sure where best to start looking. Any hints of where to look would be much appreciated.


texts: Lower bound on distance from k-coloring a grid without monochromatic rectangles

texts:
This question stems from this other question: Grid $k$-coloring without monochromatic rectangles

Given a grid coloring, I want to determine the least amount of rectangles you have to leave uncolored to remove all monochromatic rectangles from the coloring. This would give a lower bound on the number of changes you have to make to the coloring to reach a coloring that has no monochromatic rectangles. As a heuristic for A*, it would be admissible and monotonic.

How would you calculate this number? My first attempt, a greedy algorithm that uncolors one of the cells which is involved in the most rectangles until there are no rectangles left, sometimes overestimates.


texts: expansion with respect to p-norms for p other than 2

texts:
Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$.

Let $x \in {\mathbb C}^n$ be a vector whose components are on the unit circle, i.e. $|x_i|=1$ for all $1 \le i \le n$.  Note that the $k$-norm of $x$ is $|x|_k^k = \sum_i |x_i|^k = n$ for any $k > 0$.  Furthermore, suppose that $x$ is perpendicular to the uniform vector, so that ${\mathbb E}_i x_i=0$.  Then

${\mathbb E}_i |(Ax)_i|^2 = \frac{1}{n} |Ax|_2^2 \le \lambda^2$.

Can we say anything about the $k$-norm of $Ax$,

${\mathbb E}_i |(Ax)_i|^k = \frac{1}{n} |Ax|_k^k$

for $k \ge 2$?  For instance, is

$\frac{1}{n} |Ax|_3^3 \le \lambda^\alpha$ for some $\alpha > 2$?

If $x_i = \pm 1$ for all $i$, then this has to do with how nonuniform the neighborhoods are.  If a $\lambda^2$ fraction of vertices $i$ have the same value of $x_j$ for all their neighbors $j$ so that $|(Ax)_i|=1$, and the other $1-\lambda^2$ fraction have half $x_j=+1$ and half $x_j=-1$ so that $(Ax)_i=0$, then ${\mathbb E}_i |(Ax)_i|^k = \lambda$ for all $k$.  But is this possible?  If there is more of a spread in the fraction of neighbors $j$ with $a_j=+1$, then perhaps an nice inequality holds.

I am especially interested in the case of Ramanujan-like graphs, where $\lambda = O(1/\sqrt{d})$.

Thanks!
- Cris


texts: Fixed parameter tractable algorithms for graph isomorphism

texts:
What are the future directions in fixed parameter tractability of graphs isomorphism after these two recent papers:

Reduction Techniques for Graph Isomorphism in the Context of Width Parameters,  Yota Otachi, Pascal Schweitzer
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth,  Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh


texts: Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences

texts:
Given an Graph $G(V,E)$ with $|V|=n$ and $|E|=m$.

The goal is to find a vertex ordereing $\sigma$ of V such that for each vertex $v\in V$, all neighbours of $v$ occur in $O(\sqrt{m})$ sequences in $\sigma$.
That is if I locate all neighbours of $v$ in $\sigma$ I find all the neighbours present in chunks in $\sigma$, where number of such chunks is $O(\sqrt{m})$.

Clearly any vertex with degree $<\sqrt{m}$ does not voilate any vertex ordering as even if all its neighbours are separated in $\sigma$ the number of sequences/chunks cannot exceed $degree$ of the vertex.

Does such an ordering always exists?Can I find such an ordering efficiently?

Best case would be to find such an ordering in $O(m)$ time. Also is it possible for find such an ordering for smaller number of chunks/sequences?


texts: Purely(ish) functional data structure with fast append and forward iteration

texts:
I find I have need for a data structure with a specific set of requirements:

It represents an immutable sequence of values (fixed sized integers if this matters)
Appending a new value to the end (and returning a new sequence) needs to be extremely fast and memory efficient. Ideally amortised O(1) and sharing the entire prefix, but there's no specific hard complexity requirement and O(log(n)) would probably be OK too.
Getting the length of a sequence needs to be cheap (obviously I can add this in after the fact with a wrapper if necessary)
I need to be able to efficiently iterate the sequence in the forward direction
I need to be able to lexicographically compare two sequences of the same length in the forward direction efficiently (this follows from the previous property, but might have simpler implementations and has fairly specific iteration patterns)
Sharing of prefixes is very common in the expected workloads, so solutions like vlists or copy-on-append aren't practical because the workload will essentially always trigger a full copy.
(practical rather than theoretical constraint but...) The simpler the design the better, because I'm almost certainly going to have to implement this from scratch in a couple of different languages, including C (with reference counting)

Non-constraints:

Although the data structure itself has to represent immutable sequences, I don't mind a certain amount of mutation of the values if it's invisible (it would be nice to avoid)
I certainly don't mind depending on e.g. some source of randomness
It's OK if the forward iteration depends on some sort of external data structure with extra space requirements

Obviously the ideal would be to just have a length prefixed cons list, but the forward iteration requirement makes that sub-optimal.

The following are the two things I've considered so far:

Just use a cons-list anyway and reverse it in an external buffer prior to iteration. Downsides: Forward iteration becomes fairly expensive, particularly
for cases where I'm likely to stop the iteration after only one or two elements (which is a common case because of lexicographic comparison being a major use case here).
A tree of bounded balance - it stores the size efficiently, has relatively cheap append and iteration. Downsides: Kinda fiddly to implement correctly, unclear whether the relatively high constant factors and the logarithmic complexity make it a win in practice.
A skip list. Downsides: Same as the upsides really - it's about halfway between the previous two in terms of complexity and performance. Requires more book-keeping for iteration than the others, but it's probably tolerable.

So of the three the skip list looks like it might be the best option and "just use a cons list and optimise later" looks like the one I'm most likely to start with, but I'm not exactly well versed in the purely functional data structure literature, so I was hoping there were a better option I was overlooking. Any suggestions?


texts: Space complexity for multiplying $m$ matrices

texts:
Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$.

The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. I am wondering can there be any algorithm with $polylog(n,m)$ memory but still $m \cdot poly(n)$ or $poly(n,m)$ running time. It sounds like an old problem but I couldn't find any reference.

Note that using the divide and conquer technique (like in Savitch's theorem), we can achieve $polylog(n,m)$ memory and $m \cdot n^{O(\log m)}$ running time.


texts:
Def. We call $C: \mathbb R^d \to \mathbb R^d$ a $\delta$-compressor (or contractor) if for all $x$
$$\|C(x) - x\|^2 \le (1 - \delta) \|x\|^2$$
Intuitively, $C(x)$ is not too far from $x$. Note that $\delta$ can be pretty small, e.g. $\frac 1d$.
Def. For a fixed $n$ we say that function $f$ is $\alpha$-composable if there exist functions $g$ and $h$ such that for any $x_1, \ldots, x_n$ we can represent each of $f(x_1 + \ldots + x_n)$, $g(x_1), \ldots, g(x_n)$ using $\alpha$ bits and
$$f(x_1 + \ldots + x_n) = h(g(x_1), \ldots, g(x_n))$$
Intuitively, we have $n$ machines, we send $g(x_i)$ from each machine to the coordinator which computes the answer and sends it back to the machine. Moreover, for each machine (except of the coordinator) the total communication is $O(\alpha)$. The definition above was my attempt to capture this intuition, so it's possible that it's not the best one.
For $\alpha$-composability, we may also allow a polylogarithmic number of rounds to compute the answer. I.e. for $k  = polylog$ of all parameters we can have functions $h_1, g_1, \ldots, h_k, g_k$, so that in $j$-th round $g_j(x_i, h_0, \ldots, h_{j-1})$ are sent to coordinator, $h_j$ are sent back to the machines and $h_k$ must compute $f(x_1 + \ldots + x_n)$.
In both definitions, functions can be randomized. In this case, the properties must hold in expectation. All $g$ are allowed to share randomness in any way.
For example, "Communication-efficient distributed SGD with Sketching
" describes a $\tilde O(k)$-composable $\frac kd$-compressor. The main idea is to use count sketch to find heavy hitters.
Question: Does there exist a function with the following properties:

It is a $\frac cd$-compressor for some constant $c$.
It is $\tilde O(1)$-composable ($\tilde O(1)$ means polylogarithmic on all parameters)
It is Lipschitz, i.e. for some constant $L$ we have $\|C(x) - C(y)\| \le L \|x - y\|$ for all $x, y$. For randomized function, we only need Lipschitz property with respect to $x$, i.e. $\|C(x, \theta) - C(y, \theta)\| \le L \|x - y\|$ for all $x,y,\theta$, where $\theta$ is a randomness-controlling parameter and in the inequality above it's the same for $x$ and $y$.

Some weaker results (e.g. good $\frac 1 {\sqrt d}$-compressors) are also appreciated.
My thoughts: It shouldn't be possible even when we weaken $\alpha$-composability requirement to the following: "For all $x$, $f(x)$ can be stored using $\alpha$ bits". Intuitively, I expect that any such compressor must be of a heavy hitter type, and such compressors are not Lipschitz.
The composability definition essentially restricts possible solutions to linear sketches, and count sketch seems to be the only feasible solution, but, unfortunately, a corresponding compressor is not Lipschitz. However, if we allow multiple communication rounds, it's not that clear anymore.
Any ideas how to approach this are appreciated. I suspect we should leverage some communication complexity technique, but I don't know which one.


texts: Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language

texts:
Given is the language
$$L_n = \{a^n\},$$
where $n$ is a natural number and $a$ is a letter. What are the productions/rules of a minimal context-free grammar according to the number of symbols of the productions (e.g. the number of symbols of the productions $\{ S \rightarrow a, S \rightarrow aS \}$ is 7).

For $n = 1$ the (only) rule is $\{ S \rightarrow a \}$ and for $n = 2$ we get $\{ S \rightarrow aa \}$, which can be proved easily. The number of symbols are $3$ and $4$, respectively. You may think, that $\{ S \rightarrow a^n \}$ ($2 + n$ Symbols) is always the shortest rule according the number of symbols for $L_n$ but $L_{10} = \{a^{10}\}$ can be constructed by $\{ S \rightarrow A^5, A \rightarrow aa \}$ that has only $11$ symbols (instead of $2 + 10 = 12$). This looks like an optimal compression problem.


texts: Are the $\lambda_I$-Calculus and the $\lambda_K$-Calculus equivalent?

texts:
I see here and there mention of the $\lambda_I$-Calculus (in which every variable must be used at least once) and the $\lambda_K$-Calculus (in which a variable can also be unused).  Are they equivalent?  Why has the latter kinda obscured the former?

EDIT

By equivalent, I mean they have the same expressive power, namely, being universal or Turing complete.


texts: Mutually exclusive replacement paths, an existing problem?

texts:
A replacement path is a simple path allocated to an edge $e \in G$
that connects the endpoints of $e$ in $G \setminus \{e\}$.

The problem

An undirected graph $G$ is given and the task is to allocate a replacement path $P_e$ to each edge
$e \in G$ such that for any pair of edges $e_1$ and $e_2$ it holds:
if $e_2 \in P_{e_1}$ then $e_1 \not\in P_{e_2}$.
In words, no two edges use each other in their replacement path.
I call the paths $P_{e_1}$ and $P_{e_2}$ mutually exclusive.

The path length is not bounded and they can share edges. So any path allocation that satisfies the
mutual exclusion would be good.

Now the question: is there already any problem closely related to this?

One could reduce this problem to Maximum Independent Sets problem: a vertex for every $(e,P_e)$ and edges connecting conflicting pairs (i.e. pairs violating the ME). However, in order to get a polynomial size instance we need to restrict the model so that each edge gets a constant number of candidate paths.
However, this is not desired because the MIS instances seem to be NP-Hard (or not?).


texts: Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?


texts: reference request- property of subset of rows in a matrix

texts:
I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M such that the following holds: for every $i\in [n]$, there is $at$ $most$ one row in $v\in S$ such that $v_i\neq z_i$.

I was wondering if this combinatorial notion has been used to characterize some complexity in literature? Any reference/ pointer is welcome. I am not interested in an algorithm to find the largest subset, but rather if such a combinatorial notion has been used to character some "other complexity measure"


texts: Bias of a random boolean low degree polynomial

texts:
What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree?

More specifically, is it true that if we take a uniformly random function $f:\{0,1\}^n \to \{0,1\}$ among those that can be represented as a real polynomial of degree $\leq d$, then $\mathbb{E}[f]$ will be close to 0.5 with high probability?

Remark 1: Alternatively, it also makes sense to consider the following distribution: when choosing a random function of degree $d$, identify functions that are equivalent up to renaming coordinates, so a random function is in fact a random equivalence class.

Remark 2: This question is somewhat related:  Random functions of low degree as a real polynomial.


texts: Benefits for syntactic and semantic classes

texts:
This is a post separated from Consequences of UP equals NP, and also a follow-up question to Semantic vs. Syntactic Complexity Classes.

In the above post we learned about the semantic and syntactic classes. Briefly stated, when a class can be characterized as a leaf language class $\mathsf{L}[L_1|L_2]$, then a class is syntactic if $L_1 \cup L_2 = \Sigma^*$, that is, accepting language $L_1$ is the complement of rejecting language $L_2$; otherwise we called it a semantic class.
One can see that $\mathsf{P}$, $\mathsf{NP}$ and $\mathsf{PP}$ are syntactic classes,
while classes like $\mathsf{BPP}$ and $\mathsf{IP}$ are semantic classes.

Classical result like $\mathsf{PSPACE} = \mathsf{IP}$ and conjecture $\mathsf{P} \stackrel{?}{=} \mathsf{BPP}$ both can be view as semantic classes turns out to have syntactic characterizations. It seems to me that the syntactic classes are easier to handle, since they have natural complete problems. Also techniques like diagonalization is easier to be applied on syntactic classes, since they have a natural machine enumeration. But still $\mathsf{BPP}$ as a semantic class seems to have much more nice properties than the syntactic class $\mathsf{PP}$.

  What benefits do we have if we have a syntactic representation of a semantic class, or vice versa? Are there results or proof techniques only applied to syntactic/semantic classes?


texts: Why do NP-complete problems not have similar approximation ratios?

texts: Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar approximation ratios (referring to their optimization counterparts)? I guess that some constant or even polynomial drift might be understood but we have the case of constant-factor approximation algorithms for some NP-complete problems and, on the other hand, other problems that cannot be even approximated by a polynomial-ratio approximation algorithm, such as general TSP? Thank you


texts: Correcting a conference paper error in the journal version

texts:
In a conference paper, in order to prove the $\mathsf{NP}$-completeness of a problem, I wrote the stupid sentence "It is clear that the problem is in $\mathsf{NP}$. So we will prove that it is $\mathsf{NP}$-hard". In fact, it was not clear at all. It even seems to be an open problem. For the targeted audience, it's not a big deal because the main result is the $\mathsf{NP}$-hardness, and thus the impossibility "difficulty" to design a polynomial algorithm.

But, of course, I want to correct the mistake in the journal version.

  My question is: In a journal paper, how to point a mistake in the conference version and correct it?

Should I write: "There is a mistake in the conference version: ..."? Or should I  state the correct result without saying that the conference version was wrong? Any advise is welcome.


texts: For which algorithms is there a large gap between the theoretical analysis and reality?

texts:
Two ways of analyzing the efficiency of an algorithm are

to put an asymptotic upper bound on its runtime, and
to run it and collect experimental data.

I wonder if there are known cases where there is a significant gap between (1) and (2). By this I mean that either (a) the experimental data suggests a tighter asymptotic or (b) there are algorithms X and Y such that the theoretical analysis suggests that X is much better than Y and the experimental data suggests that Y is much better than X.

Since experiments usually reveal average-case behavior, I expect most interesting answers to refer to average-case upper bounds. However, I don't want to rule out possibly interesting answers that talk about different bounds, such as Noam's answer about Simplex.

Include data structures. Please put one algo/ds per answer.


texts: Powerful algorithms that are just too hard to implement-- how to be sure they are right?

texts:
I am referring to the question here: powerful algorithms too complex to implement.

If an algorithm is powerful, but too complex to implement, how can you be sure that the algorithm is correct? Without implementation you won't be able to test the algorithm in a real world scenario, and such a complex algorithm can contain bugs, which may invalidate the algorithm.

This is what I do not understand; if you have the techniques to prove the correctness of an algorithm, then you would have the algorithm to implement it already, isn't it? Or else how can we be sure that the proving technique is correct?

I'm sorry if I sound elementary!

Update from Kaveh ( reproduced here because the argument is better!):

  If you can formally prove the
  correctness of an algorithm in a
  formal system like Coq then you can
  also extract the algorithm (because
  essentially you have implemented the
  algorithm), but the key fact is that
  for most algorithms we don't give
  formal proofs of correctness for the
  algorithm, we use informal proofs of
  correctness. The proofs can be false,
  which does happen from time to time,
  and even a formal proof of correctness
  will not make us absolutely sure that
  the algorithm is correct.


texts: Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

texts:
I am considering ideas about exact quantum algorithms. In particular, I am considering likely limitations of $\mathsf{EQP}$, which consists of languages exactly decideable by polytime-uniform quantum circuit families over an arbitrary finite gate set.

The quantum Fourier transform (QFT), given by
$$ F_N = {\frac{1}{\sqrt N} \begin{bmatrix} 1 & 1 & 1 & 1&  \cdots & 1 \\ 1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \omega^6 &  \cdots & \omega^{N-2} \\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{N-3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{N-2} & \omega^{N-3} & \cdots & \omega^{(N-1)^2} \end{bmatrix}} \quad\text{for $\omega = \mathrm e^{2\pi i/N}$},$$
is a celebrated part of quantum computational theory.
In the case of $N = 2^n$, there is well-known decomposition of $F_N$ into Hadamards, SWAP gates, and diagonal gates $$\mathrm{CZ}_{2^T} = \mathrm{diag}(1,1,1,\mathrm e^{2\pi i/2^T\!})$$ for various $T \geqslant 1$, which is due to Coppersmith. If $\mathsf{EQP} \smallsetminus \mathsf{P}$ is to contain any problems, one might hope that one of these would make use of the QFTs $F_{2^n}$, in which case one would require the family of operations $F_{2^n}$ to decompose into some particular finite gate set. Using the recursive decomposition of the QFT, this is equivalent to there being a decomposition of all gates $\mathrm{CZ}_{2^n}$ into a single finite gate set.

Obviously, by the Solovay–Kitaev theorem, we may approximate the gates $F_{2^n}$ or $\mathrm{CZ}_{2^n}$ arbitrarily well with any approximately universal gate set which is closed under inverses. What I would like to know is whether there is a finite gate-set which may exactly realise these families of operators — or, what I suspect is more likely, whether there is a proof that no such finite gate-set exists.

Question.
Is there either a decomposition of $\{ F_{2^n} \}_{n \geqslant 1}$ as a polytime-uniform circuit family on a finite gate-set, or a proof that this is impossible?


texts: Request for an update on a discussion about coinductive types in HoTT (or anywhere else)

texts:
Googling something else I stumbled on a conversation titled "coinductives" initiated by Vladimir Voevodsky on Google groups in 2014. It lasted for three days, invloved a dozen people, and left on me an impression of something like a text by Conan Doyle abruptly interrupted at the most thrilling moment.
Could somebody update me on it? What happened afterwards? Most intriguing question that remains unanswered there is whether one can construct a more or less complete duality between inductive and coinductive types. The phenomenon of limit-colimit coincidence somehow suggests that in at least some circumstances that stem from endofunctors in the category-theoretic semantics, the types that correspond to initial algebras and final coalgebras of these endofunctors should be equivalent in some sense. There is a controversy in that discussion whether to expect that.
As an aside, let me remark that there does not even seem to exist any tags related to coinduction here.


texts: Can the definition of ambiguity of CFG be extended to CSG?

texts:
Usually,ambiguity of grammar is defined for constext-free languages and grammars,sometime it is extended to indexed languages and grammar,but the extension of definition of the definition is same except that the grammar and language are indexed one.

Now,let's try to extend the definition to context-sensitive grammar and language.One definition of context-sensitive grammar is as following:

The production or rewriting rule is in the form:
$$\alpha A \beta \rightarrow \alpha  \gamma \beta$$
where $\alpha , \gamma, \beta $ are string over terminal or non-terminal symbols,$A$ is non-terminal symbol.

Parsing every sentence of CSL by CSG ,we can get a tree or directed graph,the leaves or the final vertex are the terminal symbol,and the root is the $S$ symbol,the nodes or non-final vertex are non-terminal symbol.In this way,every sentence corresponds to one or more trees or directed graphs.

Now,the question: is this definition consistent with the one of CFG and CFL? If not,any suggestion for modification to make them consist to CFG or CFL?

If they are consist,now  the definition of ambiguity of CSG is:if a sentence of a CSL having been parsed by CSG corresponds to more than one trees or graphs  which are not isomorphic to each other(with labels),the CSG is ambiguous.

In this way,is there any context-sensitive language  that is inherently ambiguous?That is every CSG of the  language is ambiguous.


texts: Expressive power of (versions of) weighted average

texts:
Consider the arithmetic expressions obtained by allowing the constants 0 and 1, boolean variables, and allowing the operations $\min\{s,t\},\max\{s,t\}$, and $1-t$ where $s,t$ are expressions.
Clearly we can only get the values 0 and 1 by evaluating these expressions (with an assignment to the variables).
We wish to add a quantitative element to these expressions, by means of a weighted average. We consider the following operators:
$\oplus_\lambda$, which is defined by $s\oplus_\lambda t=\lambda s+ (1-\lambda)t$, for any $\lambda\in [0,1]$.
$\otimes_\lambda$, which is defined by $s\otimes_\lambda t=\lambda \max\{s,t\}+(1-\lambda)\min\{s,t\}$.

Intuitively, the difference is whether we attempt to interpolate between $\min$ and $\max$, or to add an addition element.

The question is: is the arithmetic with $\oplus$ strictly more expressive than $\otimes$?

Obviously, $\otimes$ can be captured by $\oplus$, since:
$$s\otimes_\lambda t=\max\{s,t\}\oplus_\lambda \min\{s,t\}$$
For the other direction, we have a partial result:
$$(s\otimes_\lambda 0)\otimes_\frac12 (t\otimes_{1-\lambda}0)=\frac12(s\oplus_\lambda t)$$
But I can't seem to be able to get rid of that $\frac12$ (recall that $\lambda\in [0,1]$), or to prove that there is an expressiveness difference.

Thanks!


texts: Partition into triangles in a 3-partite graphe

texts:
Let $G=(X\cup Y\cup Z,E)$ be a 3-partite graph such that:

$|X|=|Y|=|Z|=q$.
$2 \leq d(v) \leq 6$ for all $v \in X\cup Y\cup Z$, where $d(v)$ is the degree of v.
$\sum_{x \in X} d(x)=\sum_{y \in Y}d(y)=\sum_{z \in Z} d(z)$

Can we partition $G$ into $q$ vertex-disjoint triangles?


texts: Implementations of Dependent Type Theory

texts:
I am trying to find a minimal implementation of dependent type theory that supports

Pi Types (obviously)
Modules containing records
Inductive data types
Universe Hierarchy
A notion of equality
Termination checker
Type Inference and Resolution

I am aware of implementations based on:

Löh, A., McBride, C., & Swierstra, W. (2010). A tutorial implementation of a dependently typed lambda calculus. Fundamenta informaticae, 102(2), 177-207.

But they do not support everything in the list above.

Something even smaller than mini-Agda would be helpful.


texts: Where and how did computers help prove a theorem?

texts:
The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful

in building a conjecture that lead to a theorem,
falsifying a conjecture or proof approach,
constructing/verifying (parts of) a proof.

If you have a specific example, please describe how it was done. Perhaps this will help others use computers more effectively in their daily research (which still seems to be a fairly uncommon practice in TCS as of today).

(Flagged as community wiki, since there is no single "correct" answer.)


texts: Can we show that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$?

texts: We know by Immerman–Szelepcsényi theorem that $\mathsf{NL}=\mathsf{coNL}$? Does it follow from this theorem that  $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? Here, $\mathsf{NL}^\mathsf{NL}$ denotes the class of problems which can be solved by an $\mathsf{NL}$ machine with access to  an $\mathsf{NL}$ oracle.


texts:
Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$
we define $L(f)$ to be the straight-line complexity of $f$ over
$k$. Let $F$ be the set of monomials of $f$, namely the monomials
which appear in $f$ with non-zero coefficient.

  Is it true that $ \forall m\in F:L(m)\le L(f)$?

Even some weaker upper bound for $L(m)$ is known?


texts: Implementing D* Lite for Path-Planning - How detect Edge Cost Change?

texts:
I currently try implementing the D* Lite Algorithm for path-planning (see also here) to get a grasp on it. I found two implementations on the web, both for C/C++, but somehow couldn't entirely follow the ideas since they seem to differ more than expected from the pseudo code in the whitepapers. I especially use the following two papers:
Koening,S.;Likhachev,M. - D* Lite, 2002
Koenig & Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, June 2005

I tried implementing the optimized version of D* Lite from the first whitepaper (p.5,Fig.4) and for "debugging" I use the example as shown and explained in the second whitepaper (p.6,Fig.6 and Fig.7). All work is done in MatLab (easier for exchanging code with others).

So far I got the code running to find the initial shortest path by running computeShortestPath() once. But now I am stuck at lines {36''} and {37''} of the pseudo-code:

{36”} Scan graph for changed edge costs;
{37”} if any edge costs changed

How do I detect those changes? I somehow don't seem to have a grasp on how this is being detected? In my implementation so far, I mainly used 3 matrices.
One matrix of same size as the grid map containing all rhs-values. One matrix of same size containing similarly all g-values. And one matrix with variable row count for the priority queue with the first two columns being the priority keys and the third and fourth row being the x- and y-coordinates.

Comparing my results, I get the same result for the first run of computeShortestPath() in Step5 as seen in the second whitepaper, p.6 Fig.6. Moving the robot one step also isn't that a problem. But I really have no clue how the next step of scanning for changed edge costs should be implemented.

Thanks for any hint, advice and/or help!!!


texts: The significance of NP-Hard Problems in Cryptography

texts:
I didn't refer any literature but thought this was ideal to get views from people here..

Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can break any scheme in polynomial time.

Aren't the NP-hard problems enough to save the day? I've heard of crypto-systems based on "subset problems". Since P=NP would not affect the nature of NP-hard problems.

It would also be great if can suggest any interesting articles regarding this..

Thanks!

P.S: Please feel free to edit if you find any naive statements in the question.


texts: What are some results on algorithms that estimate polynomials over a given set of points?

texts: There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero.  Are there any results of algorithms that do some sort of estimation of polynomials over a specific set of points? This could be, for instance, approximating for what fraction of these points the polynomial evaluates to zero, or approximating the average value of the polynomial over these points?  The set of points can be specific to the algorithm.


texts:
There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, meaning accept one string but reject the other.
Here are some relevant papers 1, 2. (I have a few more but I don't have enough reputation to post them).
These all discuss the problem of separating two distinct strings. I am wondering if there been any work done in the area of separating lists of strings, meaning given two lists of strings, $A$ and $B$, what size DFA is required to accept every string in $A$ and reject every string in $B$. This problem is equivalent to regex golf.
There are some basic questions that I have been working on such as if one of the lists is of size $1$ or if all the strings are of different lengths.
I have been searching around but haven't found any papers that deal with this type of problem. Has there been any research done in this area?
Thanks in advance.


texts:
I am trying to understand co-NP and its implications properly.
The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows:
Considering a graph G, is it true that it does not have an Hamiltonian cycle?

Is this correct?
If so, then how is this complementary version a different class of complexity than the original Hamiltonian cycle problem? The decision question is the same. To put it differently, what is the difference between NP and co-NP here?
Otherwise, if this complementary version is false, what would be the correct version (if any exists)?
Update

To put it simply, returning an opposite answer for one input does not cover for all possible inputs.

In the comments of dkaeae's answer below, I say "NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian." Fact is if a P-machine can decide whether a graph is Hamiltonian or not, it can also deliver an instance of such a cycle in P-time if any exist. This does not harm the formal definition of NP.


texts: Poly-time approximation scheme for problems with pseudo-polynomial time algorithms

texts: The question is: Does a poly-time approximation scheme always exist for NP-complete problems that have pseudo-polynomial time algorithms (like knapsack for example)?


texts: Relation between group theory and information theory

texts:
Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory).

Question:
Is there any paper/survey paper on group-theoretic information theory?


texts: Understanding the Beck-Chevalley Condition

texts:
I've been reading through Bart Jacobs' "Categorical Logic and Type Theory", and lemma 1.8.9 has me stumped. The lemma is stated as follows:

Let $p : \mathbb E \to \mathbb B$ and $q : \mathbb D \to \mathbb B$ be fibrations and let $H : \mathbb E \to \mathbb D$ be a fibred functor. This functor $H$ has a fibred left adjoint if and only if both

(a) For each object $I \in \mathbb B$ the functor $H_I : \mathbb E_I \to \mathbb D_I$ restricted to the fibres over $I$ has a left adjoint $K(I)$

(b) The Beck-Chevalley Condition holds, i.e. for every map $u : I \to J$ in $\mathbb B$ and for every pair of reindexing functors $\mathbb E_J \overset{u^*}{\longrightarrow} \mathbb E_I$ and $\mathbb D_J \overset{u^\#}{\longrightarrow} \mathbb D_I$, the canonical natural transformation $K(I)u^\# \Rightarrow u^* K(J)$
is an isomorphism.

What does the canonical natural transformation $K(I)u^\# \Rightarrow u^* K(J)$ refer to? I was having a lot of fun reading this book. However, since the Beck-Chevalley condition is used throughout the rest of the book, this particular lemma has become a road block.

I'm not sure if this is considered a research level question, but I don't know where else to ask this.


texts: Minimum order of partite in a bipartite graph

texts:
I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum number of $N$ so that every pair of the $L$ vertices have a common neighbour.

A different formulation of my problem is the following:

Assume we have $L$ distinct numbers.
I want to calculate the minimum number of sets of size $a$ that are needed so that all unordered pairs of numbers are contained in at least one of the sets.
I understand that finding the sets is similar to the set cover problem: http://en.wikipedia.org/wiki/Set_cover_problem (right?), but is there an easier/faster way to calculate the minimum number without calculating the sets, given $L$ and $a$?


texts: Early References for Transition System Semantics of Programs

texts:
I am trying to trace back the origins of transition system semantics for imperative programs. I am assuming a transition system is a tuple $(\mathit{States}, \mathit{Trans})$ consisting of a set of states and a (binary) transition relation over states. By transition system semantics, I mean that there should be a mapping from programs to transition systems.

The presentation need not be exactly as I describe above and the mapping from programs to transition systems need not be completely explicit. For example, I would consider Plotkin's Structural Operational Semantics as providing transition system semantics to a formal language. Other early references I know of are due to Cousot & Cousot, and even earlier, due to Robert Keller in Formal Verification of Parallel Programs. There is earlier work by Richard Karp and Raymond Miller on reasoning about parallel programs, but their model is closer to Petri Nets and I am unsure about whether to read their paper as giving transition system semantics to programs.

Does anyone know of references from the early 80s or earlier where transition system semantics are provided for programs? Please add a few lines about the semantics and whether it is used today, and in what form.


texts: Problems or issues with a proposed circuit class?

texts:
I'm looking to use something close to the following as a definition for a circuit class. This is obviously semi-informal. I am curious if any one sees any potential problems with it, or where something in it's informal nature can potentially be a problem when it is tightened up to something more formal.  Also, I'm not aware of any vetted and accepted circuit class "like this", so pointers to something I missed are welcome as well.  In particular, the use of time is critically important to what I'm working on.  TIA.

The circuit class TLU, or Table Look Up, is defined as taking $n \ge 1$ $\{0,1\}$ inputs that produces a single $\{0,1\}$ output.

An individual $n$ input TLU gate is defined as an indexed array of $\{0,1\}^{2^n}$, where $n$ represents the index that selects a particular $\{0,1\}$ from the array.  For example, $\{1,1,1,0\}$ would represent the common $\text{NAND}$ gate.  An individual $n$ input TLU gate has a depth of $1$, a gate count of $1$, and takes atomically $O\left(1\right)$ time to produce an output from a given input.  For each $n$ input TLU gate set, there are $2^{2^n}$ possible indexed arrays.  All TLU gates advance in time atomically with respect to all other TLU gates.

For some large value of $n$, one may wish to map a large $n$ input TLU gate to a set of $\lt n$ input TLU gate primitives.  A common example would be the set of $\le 2$ input $\{\text{AND}, \text{OR}, \text{NOT}\}$ gates.  In The synthesis of two-terminal switching circuits, Shannon proved maximum worst case bounds for gates and depth for the $\{\text{AND}, \text{OR}, \text{NOT}\}$ set.  This result can be extended to make the following claim: As long as the set of primitives contains a complete boolean basis, there is guaranteed to be a maximum worst case bounds for gates and depth for that set of primitives.


texts: How to become referee for TCS papers and conferences

texts: I moved somehow from biophysics to a mixed team where we usually publish in TCS journal / conferences. For getting funding, in the European country where I live, it is advisable to show in your CV that I have refereed papers or conferences on these fields. I have more than 30 publications but never really thought about this. So my question goes, how can I become referee in these cases?


texts: NP-complete variants of undecidable problems?

texts:
Examples of bounded $NP$-complete variants of undecidable sets:

Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps}

Bounded Tiling={ $(T, 1^t)$| there is a tiling of a square of area $t^2$ by tiles from $T$}

Bounded Post Correspondence Problem={ $(T, 1^t)$| there is a matching set of dominoes that uses at most $k$ dominoes from a set of dominoes $T$ (including repeated dominoes) }

  Is it always possible to get $NP$-complete variant of every Undecidable problem by imposing some bounds on the computation? Are there other natural examples of this kind?


texts:
Consider a quantum query algorithm that takes as input $x \in \{0,1\}^n$. Denote by $X_i$ the variable that evaluates to $1$ on input $x$ if the $i$-th bit of $x$ is 1, and $-1$ otherwise. Let $X_{\vec{i}}$ be the product of the variables whose indexes are in $\vec{i}$ (for instance : $X_{\overrightarrow{4,1,3}} = X_4X_1X_3$).

The polynomial method relies on the fact that the state $|\phi_t(x)\rangle$ of the algorithm on input $x$ at time $t$ can be written as $|\phi_t(x)\rangle = \sum_u P_u(x) |u\rangle$, where $u$ ranges over all the basis states and the $P_u$'s are multilinear polynomials of degree at most $t$ in the $n$ variables $X_1, \dots, X_n$. In other words, there exist complex numbers $(a_{u,\vec{i}})$ such that for all $x$:

$$|\phi_t(x)\rangle = \sum_{u,\vec{i}} a_{u,\vec{i}} \cdot X_{\vec{i}} \ |u\rangle$$

where $P_u(X) = \sum_{\vec{i}} a_{u,\vec{i}} \cdot X_{\vec{i}}$ (for the sake of simplicity, assume from now on that the $a_{u,\vec{i}}$'s are just real numbers).

Finally, define the L2-norm $||P||_2$ of a polynomial to be the sum of the squares of its coefficients, i.e. $||P_u||_2 = \sum_{\vec{i}} a_{u,\vec{i}}^2$.

My question relies on the following observation:

$$\mathbb{E}_x (\phi_t(x)^2) = 1 = \sum_{u,\vec{i}} a_{u,\vec{i}}^2 = \sum_u ||P_u||_2$$

Indeed, $\phi_t(x)^2 = 1$ for all $x$ (recall that we took real numbers instead of complex ones, so this expresses the fact that $|\phi_t(x)\rangle$ must have norm one). And $\mathbb{E}_x (X_{\vec{i}}) = 0$ whenever $X_{\vec{i}}$ is not the constant 1.

Thus the $a_{u,\vec{i}}$'s must sum to one! In fact, I derived this equality from this paper: https://arxiv.org/pdf/1411.5729v1.pdf (p32), but I did not find any other result in quantum computing that uses it. For instance, is there a connection with the acceptance probability of the algorithm (if $u_a$ is the accepting state, can we relate the acceptance probability with $||P_{u_a}||_2$?


texts:
This question is similar to NP-hard problems on trees:

There is a large number of NP-complete problems that are tractable on cographs. Are there any known problems that remain NP-complete when restricted to cographs?

To be more precise I am interested in examples where the input consists solely of an undirected, unweighted cograph.

Two remarks:

For weighted cographs such a problem is mentioned here - TSP with two travellers
Cographs are the "base class" of clique-width such as trees are the base class for tree-width.

UPDATE

Some further thoughts (I am not quite sure about):
If the input is really just a cograph, the question has to be of the sort "Does the cograph have property X?". It would be enough if such a problem existed for trees, since then the question could be "Does the cotree of the cograph have property X?".


texts: Minimize in polynomial time a super-additive increasing function under linear constraints?

texts:
I am looking for references whether this problem can be doable in polynomial time (or other known approximation results):

Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$),
$$
\min \sum_{i=1}^n f(y_i)
$$
under the constraints
$$
Ay \geq b
$$

To answer to Peter Shor's comment, we are trying to find the vector $y=(y_1,\cdots,y_n)$, $A$ is a $n\times n$ matrix. We suppose that $k$ is a constant.

I am particularly interested in the case where $f$ is a piecewise linear function, not continuous ($\exists (a_1,\cdots,a_k),0<\alpha_1<\cdots<\alpha_k) $, such that $\forall x\in ]a_i,a_{i+1}], f(x) = \alpha_{i+1}x$).

It seems to me that the ellipsoid algorithm could work for those special functions, but I have not been able to find any references, maybe because either this is a sub problem of a known problem? Note that I am trying to solve this for any rational values.

(Note that this is a sub-question of What classes of mathematical programs can be solved exactly or approximately, in polynomial time?)


texts: Novel proof of pumping lemma for regular languages

texts:
Let $\mathcal{L}$ be the family of all languages over $\Sigma$ satisfying the pumping property of regular languages. Namely: for each $L\in\mathcal{L}$, there is an $N\in\mathbb{N}$ s.t. every word $w\in L$, $|w|> N$ can be written in the form
$ w=xyz$ where:
1. $|y|>0$,
2. $|xy|\le N$,
3. $xy^i z\in L$ for all $i\ge 0$.

It is a simple exercise[1] to prove that $\mathcal{L}$ contains the singleton languages $L=\{\sigma\}$, $\sigma\in\Sigma$, and is closed under union, concatenation, and Kleene star. It is likewise well-known that the family of regular languages is the smallest one that contains the singletons and is closed under union, concatenation, and Kleene star. Conclusion: the regular languages satisfy the pumping property.

Question: has anyone seen this proof in the literature?
[1] Proposed by D. Berend.


texts:
In our recent work, we resolve a computational problem which arose in combinatorial context, under assumption that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$, where $\mathsf{\oplus{}EXP}$ is the $\mathsf{EXP}$-version of $\mathsf{\oplus{}P}$. The only paper on $\mathsf{\oplus{}EXP}$ that we found was the Beigel-Buhrman-Fortnow 1998 paper that is cited  on Complexity Zoo. We understand that we can take parity versions of $\mathsf{NEXP}$-complete problems (see this question), but perhaps many of them are in fact not complete in $\mathsf{\oplus{}EXP}$.

QUESTION: Are there complexity reasons to believe that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$?  Are there natural combinatorial problems that are complete in $\mathsf{\oplus{}EXP}$?  Are there some references we might be missing?


texts: Approximate graph colouring  with a promised upper bound on maximum independent set

texts:
In my job the following problem arises:

Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 is a trivial lower, |V| a trivial upper bound. But are there better proven approximations under this special condition?)

What if we relax to the fractional chromatic number? And to "good" running times in average cases?


texts: Define metric for systems of set of points

texts:
Given a set of points $p_1, p_2, ..., p_n$ and a collection of sets from $n$ points $S_1, S_2,...,S_m$. The pairwise distance between any three points $(p_1, p_2, p_3)$ satisfies triangle inequality $d(p_1,p_2) + d(p_2, p_3) \geq d(p_1, p_3)$. How to define the distance between sets such that the pairwise distance between any three sets $S_1, S_2, S_3$ satisfies triangle inequality $d(S_1,S_2) + d(S_2, S_3) \geq d(S_1, S_3)$.
For example, when every set is $\textbf{pairwise disjoint}$ and has the $\textbf{same cardinality}$, we can define the distance between any two set to be the sum of the distances between elements of the two sets $$d(S_1, S_2) = \sum_{x \in S_1, y \in S_2} d(x,y)$$. we can show that the triangle inequality is satisfied for any three sets.


texts: Balls and Bins analysis in the $m \gg n$ regime: gaps

texts:
Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and $X_{\mathrm{sec-max}}$ be the second heaviest bin. Roughly speaking, $X_i - X_j \sim N(0,2m/n)$, and so we expect $|X_i - X_j| = \Theta(\sqrt{m/n})$ for any two fixed $i,j$. Using a union bound, we expect $X_{\max} - X_{\min} = O(\sqrt{m\log n/n})$; presumably, we can get a matching lower bound by considering $n/2$ pairs of disjoint bins. This (not completely formal) argument leads us to expect that the gap between $X_{\max}$ and $X_{\min}$ is $\Theta(\sqrt{m\log n/n})$ with high probability.

I am interested in the gap between $X_\max$ and $X_{\mathrm{sec-max}}$. The argument outlined above shows that $X_\max - X_{\mathrm{sec-max}} = O(\sqrt{m\log n/n})$ with high probability, but the $\sqrt{\log n}$ factor seems extraneous. Is anything known about the distribution of $X_\max - X_{\mathrm{sec-max}}$?

More generally, suppose that each ball is associated with a non-negative score for each bin, and we are interested in the total score of each bin after throwing $m$ balls. The usual scenario corresponds to scores of the form $(0,\ldots,0,1,0,\ldots,0)$. Suppose that the probability distribution of the scores is invariant under permutation of the bins (in the usual scenario, this corresponds to the fact that all bins are equiprobable). Given the distribution of the scores, we can use the method of the first paragraph to get a good bound on $X_{\max} - X_{\min}$. The bound will contain a factor of $\sqrt{\log n}$ that comes from a union bound (via the tail probabilities of a normal variable). Can this factor be reduced if we're interested in bounding $X_{\max} - X_{\mathrm{sec-max}}$?


texts:
I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences.

Say $\{G_i\}_{i=1}^k$  is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive elements $G_i$ and $G_{i+1}$ differ by an edge (i.e. either $G_{i+1}$ have one edge more than $G_i$, or one edge less than $G_i$).

Let $H$ be a graph not depending on $i$.

The problem is:

  Determine whether $H$ is a subgraph of some $G_i$.

The naive algorithm, running subgraph isomorphism from scratch on every $(G_i,H)$, has time complexity $kM$, where $M$ is the time complexity of one instance of $(G_i,H)$.

Question: Is it possible to design a deterministic algorithm faster in terms of worst-case running time? If $N(k)$ is the maximum time needed to check $k$ graphs, is it possible to achieve $\lim_{k\rightarrow\infty} \frac{N(k)}{k}<M$?

Does it help if the graphs $G$ and $H$ are very sparse (say, maximum degree≤4)?


texts: Lower bound of the time complexity of heap building

texts:
A lower bound of the needed number of comparision to build a heap is given by GASTON H. GONNET and J. IAN MUNRO as following

  THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only in the worst
  case, but also on the average to create a heap on n elements.

  Proof - A reasonably straightforward enumeration shows that there are $H(n)=
n !/\prod t_i$ valid heaps on a set on n numbers where $t_i$ is the size of the heap rooted at
  node $i$. A lower bound on the average number of comparisons required to permit one
  of $n!$ possible input sequences to one of these orders is $$\lg(n!/H(n))=\sum \lg t_i.$$

I understand how the number of valid heap is calculated. But I don't know information theory so I can't see how the last equation is the lower bound. Is there any theorem or book I can check to see how this works?


texts: Natural Proofs and methods for polylog depth circuit lower bounds

texts:
I have a question about the following question and its answer.
Status on circuit lower bounds for polylog-bounded depth circuits
In the above question, it is asked about methods to prove lower bounds for poly-log depth boolean circuits.
Jukna's kindful answer suggests two methods: one is matrix rigidity and the other is $t(G)$ which is  the smallest number $t$  such that $G$  can be written as an intersection of $t$  bipartite graphs, each being a union of at most $t$  complete bipartite graphs.
Anyone considering about proofs of circuit lower bounds can not evade the "Natural Proof". In 1994, Razborov and Rudich proved that we can not  take any approach satisfying the following three conditions:

Constructivity: hard property of $f$ which is a boolean function we try to prove its hardness for arbitrary circuit in $\mathcal{C}$ can be computed by poly-time in the size of truth table of boolean function.

Largeness: hard property of $f$ is easy to find in the sence of random function: the probability which randomly chosen boolean function from the family of all boolean function is at least $2^{-Cn}$

Useful: hard property can not be dealt with by any circuit in $\mathcal{C}$

My question is:

Question1: Can bounding the two quantity that is matrix rigidity and $t(G)$ breaking the conditions of Natural Proofs?
Question2: At this moment, is there a method which we guarantee (or may have some hope) that the way is not a kind of natural proofs, if the answer of Question1 is NO?


texts: Weighted Min-Cut in bounded-genus graphs

texts:
What is the status of the following decision problem ?

Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$

Output : Is there a cut $C\subseteq E$ with negative weight ?

Recall that $C$ is a cut in $G$ if the graph $G\setminus C$ is disconnected.

This problem can be solved in polynomial time in planar graphs. Indeed, there exists a negative cut if and only if there exists a negative cycle in the dual graph. The existance of such a cycle can be decided using Bellman-Ford algorithm.

Unfortunately, a cycle in the dual of a higher genus graph may not correspond to a cut in the primal graph, so that a generalisation of this algorithm seems difficult.


texts: Asymptotic complexity of mass production

texts:
For a function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, let $C(f)$ be the circuit complexity (for concreteness, constants and NOT gates are free, while 2-input AND gates cost 1).

Let $k{\times}f : \{0,1\}^{kn} \rightarrow \{0,1\}^{km}$ be the function which computes $k$ copies of $f$ on independent inputs, so $k{\times}f(x_1, ..., x_{kn}) = (f(x_1, ..., x_n), ..., f(x_{(k-1)n+1}, ..., x_{kn}))$. For instance, $2{\times}{\oplus}(x,y,z,w) = (x\oplus y, z\oplus w)$.

Define the asymptotic mass production complexity of $f$ to be $C_a(f) = \lim_{k\rightarrow\infty} \frac{C(k{\times}f)}{k}$ (since $C(k{\times}f)$ is a subadditive function of $k$, the limit always exists and is equal to the $\inf$). For example, it's possible to show that $C_a(\oplus) = C(\oplus) = 3$. A less trivial example is given by random linear functions: if $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ is a random linear function, then $C(f) = \Omega(\frac{n^2}{\log(n)})$ by a standard counting argument, while $C_a(f) \le \frac{C(n{\times}f)}{n} = O(n^{\omega_2-1})$, where $\omega_2 \le \log_2(7)$ is the matrix multiplication constant for $\mathbb{F}_2$.

My question: Can we prove that for any $f : \{0,1\}^n \rightarrow \{0,1\}^m$, we always have $C_a(f) = O(n+m)$?

There is an easy construction based on sorting networks that shows that $C_a(f) = O(n(n+m))$ - this is off by a factor of $n$ from what I want. In fact, I'll show that $C(2^n{\times}f) = O(n(n+m)2^n)$:

Given $2^n$ input strings $v_0, ..., v_{2^n-1}$ each of length $n$, for each $i < 2^n$ we make a string $X_i$ of length $n+m+1$ by putting $m+1$ $0$s at the end of each $v_i$, and we make a string $Y_i$ of the same length by first encoding $i$ with $n$ binary bits, following this with a $1$, and filling the last $m$ bits with $f(i)$ ($i$ considered as a string of $n$ bits). Then we sort the combined list of $X_i$s and $Y_i$s using a sorting network, keeping track of the result of each comparison - this requires $O(n2^n)$ comparisons, and $O(n+m)$ gates per comparison. After sorting, each $X_i$ is either next to an identical $X_{i'}$ or to some $Y_j$ with $v_i = j$ and with last $m$ bits $f(j) = f(v_i)$, and we can use the $n+1$st bit of each string to tell whether we are looking at an $X_i$ or a $Y_j$. So now we propagate the values $f(v_i)$ to the left with $O(m2^n)$ gates (or if we prefer low-depth circuits, with $n$ layers of $O(m2^n)$ gates using power-of-2 shenanigans). Finally, we unsort, using our record of the comparisons we kept track of during the sorting process, to route each answer to the relevant output gate.

It's plausible that this construction could be improved by using a sorting method which is not based on comparisons, but then I don't see how to unsort at the end. Edit: To unsort at the end, we just need to modify the beginning of the strategy by appending $i$ to the end of each $X_i$, making all the strings have length $2n+m+1$, and then finish by sorting based on the last $n$ bits. I tried searching the literature, and eventually found this paper which says in the abstract that improving the circuit complexity of sorting to $o(n(n+m)2^n)$ is an open problem.


texts: How to gurantee that the extended value iteration(EVI) always chooses a policy with APERIODIC transition matrix

texts: The realted discussion is in section 3.1.3 of the paper Near-Optimal Regret Bound for Reinforcement Learning. I am confusing about the statement: "Indeed, extended value iteration always chooses a policy with aperiodic transition matrix.'' Why this can be ensured in the paper?


texts: estimating the number of comparisons of Shell Sort

texts:
I would like to estimate the number of comparisons in ShellSort.
I'm using $h_s = 2^s-1$, where $s=\left \lfloor{\log(n)}\right \rfloor, \left \lfloor{\log(n)}\right \rfloor -1, \dots, 1   $ ;

I know that it is good idea to part it  into two cases:
(1) $s=\left\lfloor{\log(n)}\right \rfloor \left \lfloor{\log(n)}\right \rfloor -1, ..., \left\lfloor{\log(\frac{n}{2})}\right \rfloor$

(2) $\left\lceil{\log(\frac{n}{2})}\right \rceil, \left\lceil{\log(\frac{n}{2})}\right \rceil  -1, ..., 1 $

Could somebody give me a clue ? I am not asking to solution, but only help.


texts: Incorrect Lower Bound of k-Means++ Algorithm

texts:
The $k$-means++ algorithm is composed of two parts:

Initialization part: the initial $k$ centers are chosen based on $D^2$ sampling.
Expectation maximization part: the standard $k$-means algorithm (or Lloyd's algorithm) is run with these initialized centers.

In the k-means++ paper, the authors show that the $k$-means algorithm can not perform better than $O(\log k)$-approximation in expectation (see Section 4 of the same paper). However, they only give this lower bound for the initialization part without considering the expectation-maximization part. Does that make their lower bound argument incorrect/incomplete? If so, the $k$-means++ algorithm might give better than $O(\log k)$-approximation and the proven lower bound is misleading.


texts: Could chromatic number be easy to calculate when colouring is hard for some graph class?

texts:
Similar question was asked before, but there was an error in it so it was left unanswered Graph class with easy chromatic number, but NP-hard coloring

Is there any infinite set of graphs $C$ such as:

There is a polynomial algorithm recognizing for every graph $G$ whether $G$ belongs to $C$
There is a polynomial time algorithm computing chromatic number $\chi(g)$ for every $g \in C$
Humankind does not know a polynomial time algorithm for computing proper colouring for $C$, or (which is better) there is a proof that such an algorithm (under reasonable assumptions) does not exist.


texts:
For a given graph $G$, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions $G$ into two disjoint graphs of approximately equal sizes. This is called the Vertex Separator Problem when the removed set is a vertex set, and the Edge Separator Problem when it is an edge set. Both problems are NP-complete for general unweighted graphs. What is the best known hardness of approximating vertex separator ? Is a PTAS ruled out ? What are the best known hardness results in the directed setting ?

Correction : The following links and answers did not help me because I did not state my question correctly. My question is related to the following theorem of Leighton-Rao :

Theorem : There exists a polynomial time algorithm that, given a graph $G(V,E)$ and a set $W \subseteq V$, finds a $\frac{2}{3}$ vertex separator $S \subseteq V$ of $W$ in $G$ of size $O(w.{\log}n)$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$.

Given a graph $G(V,E)$ and a set $W \subseteq V$, I want to find a $\delta$-vertex separator (where $\frac{1}{2} \leq \delta \leq 1$ is a constant) of size $w$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$. What is the best known hardness of this problem ? The above theorem gives an $O({\log}n)$ approximation for this problem.

Note that I am allowing constant factor blow-up in the size of the resulting components after removing the separator, but I want to minimize the size of the separator itself. The links mentioned in the comments point to minimum b-vertex separator, in which we insist that the size of the resulting components is at most $|V|/2$.


texts: Online Weighted Allocations to Simulate a Distribution

texts:
I have a seemingly simple task that I want to solve using an online algorithm but unfortunately I wasn't able to find relevant resources even though it seems so basic.
The inputs are $D=(d_1,\dots,d_m)$ a distribution, $P=(p_1,\dots,p_m)$ positive prices and $K=(k_1,\dots,k_m)$ an allocation of integers to be augmented. At every turn we get $q$ points to spend, choose an augmentation $J=(j_1,\dots,j_m)$ of integers such that $\langle J,P\rangle\approx q$ and augment $K=K+J$. I don't want to worry too much about utilizing exactly $q$ points and turn this into some Knapsack problem, new points will keep coming so small leftovers aren't so bad.  The goal is to make $\frac{K\odot P}{\langle K,P\rangle}$ resemble $D$, ($\odot$ denotes element-wise multiplication).
I'll give examples and try to make things clearer.

Approach 1: The most basic approach is the non-adaptive one, simply keep drawing $i\sim \frac{d_i}{p_i}$ and augmenting $k_i$ by $1$, until we run out of points. Remember the last draw (where we didn't have enough points left) to start with in the next turn, so that we don't bias against larger prices. (Can assume $q$ is larger than all prices)
The problem with this approach is inaccuracy: We want to use adaptiveness in order to get better convergence. For example if $m=2$ with $d_1=d_2=0.5$ and $p_1=p_2=1$ then instead of drawing $i$ at random, it would be smarter to choose $\arg\min_ik_i$ and balance between them.

Approach 2: The adaptive approach that seemed natural to me but failed, is to use the residual distribution. For every $i$ we compute how much weight is missing, $d_i-\frac{k_i p_i}{\langle K,P\rangle}$ (setting negative results to zero) and divide by the jump size $p_i$. Namely, we keep augmenting using draws $i\sim \max\left(\frac{d_i-\frac{k_i p_i}{\langle K,P\rangle}}{p_i},0\right)$, updating the weighting after every draw.
Unfortunately, this approach is problematic. For example, assume that $m=10$, $\forall i:\:d_i=0.1$ and $p_i=1$ except for $p_{10}=10$. Say that we want to distribute $q=20$ points, so logic indicates we want to distribute in expectation around $2$ points in each cell. However, what is probably going to happen is that we distribute $1$ point to every $i$ other than $10$, and then immediately turn to increase the only under-represented choice left, $k_{10}$ by $1$, causing it to be largely over-presented.
We can try to fix that using a loss function assigning values to allocations and using the post-step value when assigning weights, but I don't see a natural way to do that. We don't only care about distance between $\frac{K\odot P}{\langle K,P\rangle}$ and $D$, but also about how hard it would be to bridge the gap. If $\frac{K\odot P}{\langle K,P\rangle}\equiv D$ it would be natural to have the same behavior as the non-adaptive case, and they are expected to get closer over time but we don't expect to converge into the non-adaptive behavior.

I also want to comment that if all $p_i$'s are equal, then this question is similar to dividing seats after an election: The distribution $D$ is determined by the distribution of votes, $q$ is the number of seats to be distributed, and we start with $K=0$.
Also, another property that I care about but not sure how to formulate: Let's say that all $p_i$'s and all $d_i$'s are equal, and let's say that for some reason we were given $k_1=10,\,k_2=0,\,k_3=1$, and we want to distribute $1$ point. One legitimate approach would be to immediately go for $k_2$ because it is minimal, but I think that a more fair and continuous approach would be to also give $k_3$ a chance, though slightly smaller. For example, pick $k_2$ w.p. $4/7$ and $k_1$ w.p. $3/7$.
Any advice would be appreciated, thanks!


texts: Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

texts:
We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover.

Let $G$ be connected simple graph.

$k$-clique cover of graph $G$ is partition of the vertices of $G$
into $k$ disjoint cliques $D'_i$.

Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle
in time $O(\mathrm{polynomial}(n) n^{O(k)}$) or better?
Let $k$ be fixed, is it true that for all graphs with given $k$-clique
cover Hamiltonian cycle is polynomial in $n$?

The basic idea is that all paths in cliques are easy.

One possible approach is to merge the cliques to single vertex
and then enumerate walks allowing visiting vertex more than once.

For $k=2$ the answer is easily true.

For $k=3$ the merged graph is either $K_3$ or $P_3$
and we can try to extend walk to Hamiltonian cycle in $G$.

For $k=4$ the merged graph might be claw, so we need
more complicated algorithm.


texts: k-CNF ←→ k-DNF conversion to minimize errors

texts:
the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby diverse refs if there is sufficient interest.

consider the problem of monotone k-CNF ←→ k-DNF conversion by minimizing errors where $k$ is the maximum width of clauses (number of variables in the clause). let $f(x)$ be a k-CNF formula where $x$ is a bitvector (denoting the boolean values of all the variables). there exists a k-DNF "approximation" formula $g(x)$ that "approximates $f(x)$" by minimizing total errors under the following metric.

evaluate $f(x)$ and $g(x)$ on every $x$. if $g(x)=1$ while $f(x)=0$ then count one "false positive". if $g(x)=0$ while $f(x)=1$ then count one "false negative". the total errors are the sum of "false positives" and "false negatives". another way of looking at this "natural" error metric is that its the Hamming distance between the two bitvectors of size $2^n, n=|x|$ composed of all "corresponding values" of $f(x)$ and $g(x)$ (eg function value column for both functions evaluated on the same truth table).

there is a dual version k-DNF → k-CNF approximation in the opposite direction that has mirrored theory.

  how does one determine the optimal $g(x)$ given $f(x)$?
  which "types" of functions $f(x)$ are harder or easier to approximate in the
  sense of errors (high vs low errors, respectively)?

(note: suspect there may be some transition-point-like behavior associated with the problem.)


texts: Techniques to improve the efficiency of Dynamic Time Warping Algorithm

texts: I am analyzing a set of time series that are shifted along the x-axis (see image below for clarification). I intend to average the time series and for that I would like to overlap all the start points together. The Dynamic Time Warping algorithm is the best algorithm to do the same. However, conventional DTW algorithm seems to be taking a long time to perform the computations. I was wondering if there was a way to accelerate the process.


texts: Regular expressions of families of regular expressions

texts:
I was reading about the Star Height Problem and noticed that Eggan's family of regular expressions follows a simple pattern which can be described by a regular expression. My question is: are there any interesting results about regular expressions which describe families of regular expressions? Can this process be continued further, so you have a regex describing a family of regexes each of which in turn describes a family of regexes?
Just a thought.


texts: Graph decompositions for combining "local" functions of vertex labelings

texts:
Suppose we want to find
$$\sum_x \prod_{ij \in E} f(x_i,x_j)$$
or
$$\max_x \prod_{ij \in E} f(x_i,x_j)$$

Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a graph $G=\{V,E\}$ and $f$ is an arbitrary function. This quantity is easy to find for bounded tree width graphs and in general NP-hard for planar graphs. Number of proper colorings, maximum independent set and number of Eulerian subgraphs are special instances of the problem above. I'm interested in polynomial time approximation schemes for problems of this kind, especially for planar graphs. What graph decompositions would be useful?

Edit 11/1: As an example, I'm wondering about decompositions that might be analogous to cluster expansions of statistical physics (ie, Mayer expansion). When $f$ represents weak interactions, such expansions converge, which means that you could achieve given accuracy with $k$ terms of the expansion regardless of the size of the graph. Wouldn't this imply existence of PTAS for the quantity?

Update 02/11/2011

High temperature expansions rewrite partition function $Z$ as a sum of terms where higher order terms depend on higher order interactions. When "correlations decay", high order terms decay fast enough so that almost all of $Z$'s mass is contained in finite number of low-order terms.

For instance for Ising model consider the following expression of its partition function

$$Z=\sum_\mathbf{x\in \mathcal{X}} \exp J \sum_{ij \in E} x_i x_j = c \sum_{A\in C} (\tanh J)^{|A|} $$

Here $c$ a simple constant, $C$ is a set of Eulerian subgraphs of our graph, $|A|$ is number of edges in subgraph $A$.

We have rewritten partition function as a sum over subgraphs where each term in the sum is exponentially penalized by size of the subgraph. Now group terms with same exponent together and approximate $Z$ by taking first $k$ terms. When number of Eulerian subgraphs of size $p$ doesn't grow too fast, the error of our approximation decays exponentially with $k$.

Approximate counting is hard in general, but easy for "correlation decay" instances. For instance, in the case of Ising model, there's correlation decay when $f(k)$ grows slower than $(\tanh J)^k$ where $f(k)$ is the number of Eulerian subgraphs of size $k$. I believe in such case, truncating high temperature expansion gives a PTAS for $Z$

Another example is counting weighted independent sets -- it's tractable for any graph if the weight is low enough because you can make the problem exhibit correlation decay. The quantity is then approximated by counting independent sets in bounded size regions. I believe Dror Weitz' STOC'06 result implies that unweighted independent set counting is possible for any graph with maximum degree 4.

I've found two families of "local" decompositions -- Bethe cluster graphs and Kikuchi region graphs. Bethe decomposition essentially tells you to multiply counts in regions, and divide by counts in region overlaps. Kikuchi region graph method improves on this by taking into account that region overlaps can themselves overlap, using "inclusion-exclusion" type of correction.

Alternative approach is to decompose the problem into global tractable parts, like in, "Variational Inference over Combinatorial Spaces". However, local decompositions allow you to control approximation quality by selecting region size


texts: Relation between MDPs and non-deterministic finite automatons

texts: I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars?  If so, are markov decision processes thus solvable by nondeterministic finite automota?  Thank you, and my apologies in advance if this question is invalid/makes no sense.


texts:
Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$.

I have the following bilinear program:

max $\sum_{i=1}^n (x_i-a_i)y_i$

subject to

$b_i\leq x_i\leq c_i$   for each $i\in [n]$;
$0\leq y_i\leq 1$   for each $i\in [n]$;
$y_i-y_j\leq d_{ij}$ for $i,j\in [n], i\neq j$;
$\sum_{i\in [n]} x_i=1$

Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$.

This question is known to be in NP. But is it NP-hard?


texts:
For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits:
$$
f(n)=\max_{|k|\le n}\left|C(k)\right|.
$$

(Note that by taking input as $\{0,1\}^*$ rather than $\mathbb{Z}^+$ I'm distinguishing between the 1-bit number 1 and the 2-bit number 01.)

The counting bound gives $f(n) \ge \left\lceil\log\left(2^n+2^{n-1}+\cdots+2^0\right)\right\rceil = \left\lceil\log\left(2^{n+1}-1\right)\right\rceil = n+1$ for $n>0$ where, throughout this post, $\log$ denotes the binary logarithm.

It's easy to construct $C$ such that $f(n)=O(n)$, $f(n)=n+O(\log n)$, $f(n)=n+\log n+O(\log\log n),$ etc. by recursion (starting from, say, Elias gamma coding). Is there a prefix-free code with $f(n)\le n+(1-\varepsilon)\log n$ for some $\varepsilon>0$ and large $n$?


texts: Statement that inequality of P and NP obstructs finding a proof of their separation

texts:
In this set of video lectures, Prof. Mulmuley emphasizes several times that P vs. NP is a very deep philosophical question at the core of Mathematics and that the fact that the two classes are not equal stands as an obstruction to proving that they are not equal (I paraphrase here, according to my limited understanding).

Now, I have two difficulties with this idea. Firstly, it was presented as though it were common mainstream belief (akin to the belief that P != NP). I did not come across this idea before, being expressed explicitly in this manner (maybe this is lack of exposure from my side).

The second difficulty is a bit more technical. P != NP tells something about hardness of finding proofs for provable statements, it does not saying anything about existence vs. non-existence of such proofs. Said naively, if P != NP, then this fact should not obstruct the existence of an easy, verifiable proof of this fact (other facts may provide such an obstruction though).

Am I misunderstanding something?

Note: I was not really sure if this question belongs to tcs.SE but I couldn't find a more suitable choice.


texts: Complexity of the densest $k$-subgraph problem on planar graphs

texts:
In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is maximized. The subgraph is not required to be connected.

There are conflicting sources on the complexity of this problem on planar graphs. Wikipedia claims that this problem is $\mathsf{NP}$-complete on planar graphs. Keil and Brecht  prove that the connected variant of the problem is $\mathsf{NP}$-complete on planar graphs, but leave the complexity of the densest $k$-subgraph problem as stated above open. Zenklusen claims that the problem is still open. There are other sources that take both sides, but no source that I have seen gives a proof that planar densest $k$-subgraph is $\mathsf{NP}$-complete.

What is the complexity of the densest k-subgraph problem on planar graphs?

Thank you in advance.


texts:
It has been known since the early 70's that  ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$). As far as I know, however, it is still open whether one class is a subset of the other, or they are incomparable, meaning that ${\bf NP}-{\bf E}$ and ${\bf E}-{\bf NP}$ are both nonempty.

Question: Which are some (preferably natural) problems that are candidates for being in  ${\bf NP}-{\bf E}$ or ${\bf E}-{\bf NP}$, assuming the respective set is not empty? I am particularity interested in natural problems within ${\bf NP}$ that likely require exponential time with superlinear exponent, i.e., they are in ${\bf NP}-{\bf E}$.


texts:
I'd like to know more about real performances of data structures, in particular two families attract my interests:

hash tables
cache oblivious

My researches didn't find any "comprehensive" (let me use this adjective) book or article that describes the advantages and disadvantages of these two families.

When is a hash table more performant than a cache oblivious data structure? What are the real use cases for a hash table, when is a cache oblivious B-tree (or simply binary) preferable?

The questions I'm asking are related not only on theoretical results, but also on real results on real computers.

I've read the book "Handbook of Data Structures and Applications", but it contains only theoretical limits, and it is not sufficient to me: I need to evaluate which data structures to implement on a real system.

Thanks for any pointers!


texts: Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there is a trivial algorithm to achieve $2^{n-1}$-error, but if $k<2^{n-1}$, is it possible to have an efficient approximation algorithm, or this problem is also #P-hard?


texts: How does one know what is not in a certain class of pseudo-distributions?

texts:
We consider working in the function space $\mathbb{R}^{\{ -1,1\}^n}$ where the expectation inner-product makes the juntas form a $2^n$ dimensional orthonormal basis.

Now say one has found a degree $2$ pseudo-distribution $\mu$ which has a negative pseudo-expectation with a non-negative objective function i.e $\mathbb{E}_\mu [f] <0$. This means that the degree $2$ SOS relaxation of the optimization problem     $min_{x \in \{-1,1\}^n} f(x)$ will not be able to hit the correct minimum. (...alternatively one could say that this pair $(\mu,f)$ forms an integrality gap instance for this SOS relaxation at degree $2$...)

Now a hope to get out of this problem would be if one can show that for some degree $d >2$ this particular $\mu$ is no more in the feasible set of degree $d$ pseudo-distributions.  Lets say that one wants to show that at $d=4$ this problem gets cured. I think that would be tantamount to showing that all degree $4$ pseudo-distributions have a non-negative inner product with this $\mu$ (inner product as defined in the first line)

What is the method (even if exponential time!) to show such a thing?


texts: Relationship of the P=PSPACE problem to alternating complexity classes

texts: From a very naive point of view of someone who haven't studied complexity theory in depth, I am wondering whether the theorems that APSPACE=EXPTIME and AP=PSPACE have any derived results on separating P from PSPACE, i.e. P=PSPACE implying AP=APSPACE and thus violating the Time Hierarchy and Space Hierarchy theorems. I would like any references discussing these relationships and why does this separation not happen or why is deciding this separation hard by discussing the alternating complexity classes and their relationship to their deterministic and probabilistic variants or alternatively any attempts on deriving alternating variants of Time Hierarchy and Space Hierarchy theorems.


texts: What's wrong with this proof that NP=Co-NP implies NP=PSPACE

texts:
Below is a short informal proof that NP=co-NP implies NP=PSPACE. What's wrong with the proof?

Assuming NP=co-NP, an instance F of TQBF can be solved by a polynomial NDTM this way:

  Non-deterministically guess the values for all the variables corresponding to existential quantifiers in F.
  The resulting formula F1 (with the guessed values substituted in the formula) will only have universal quantifiers, which makes F1 a Co-NP problem instance.
  Since NP=co-NP, there's a short certificate to verify F1's truth.
  Guess this short certificate too.

That is, the NDTM non-deterministically guesses two things: The values for all the variables corresponding to existential quantifiers in F, and the short certifcate for the intermediate (co-NP) instance F1.


texts: Using ϵ -unification and Knuth-Bendix completion to automatically proof theorems about groups

texts:
This is a follow-up question. In my previous question, I presented Welder proof assistant and I stated that I want to automate proofs about basic field theory. The only answer to this post states that a combinatorial search is sufficient since the goals are easy. I'm looking for a more general technique.

I have read Equations and rewrite rules: a survey. In page 12, it reads:

  An abelian group theory unification algorithm is given by Lankford.

The idea is as follows. Given some context equations $\Delta$ from where we can deduce some other equations $\Delta \vDash \{x_i = y_i\}$, the unification process will give the neccesary substitutions to proof all the equalities in the right part using the formulas in $\Delta$.

Another interesting quote appears on page 28:

  This algorithm gave the first known solution to unification in group
  theory using for $\mathcal{B}$ the canonical set shown in the
  appendix.

In the appendix on page 33, I find a very interesting practical session. I have some questions on the power of the methods used and the actual results that I can expect after well-understanding this 30 pages heavy mathematical paper. I hope someone can give some orientation:

What is being simulated in the practical session? I describe what I think is happening. The canonical set $\mathcal{B}$ mentioned above corresponds to given axioms $R_1$, $R_2$ and $R_3$. Then some theorems about groups are deduced. I assume that this happens by application of the $\epsilon$-unification algorithm given at page 27 and the Knuth-Bendix completion. Am I right? Could you tell me what is exactly the role of each algorithm (page 27 and Knuth-Bendix) in the solution? If you think that I can use this scheme in my problem, what steps should I do, how should I integrate this algorithms?


texts: Feasibility of equations with max constraints

texts:
Relating to a question I posted here, I have formulated the following question:

Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$.

How to check the following system of equations is feasible? Assumption: $x_i, b_k$ are all in $[0,1]$

$\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$

for example:

$\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$

What's the complexity of this problem? Obviously it is in NP, but is it NP-hard? It would be a surprise if such an easy problem does not have a polynomial algorithm. Does linear programming help here?

Many thanks.


texts: Hartmanis-Stearns conjecture and the computable transcendental numbers

texts:
In the 1965 article "On the computational complexity of algorithms" by Hartmanis and Stearns, the authors conjecture that if a real-time Turing Machine computes the real number $r$ in, for example, base 10, then $r$ is either a rational number or a transcendental number.

Is there a computable transcendental number that is not computable by a real-time Turing machine in, for example, base 10?


texts: Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include minimum vertex cover, maximum independent set, subgraph isomorphism. Name some natural optimization problems that remain NP-hard on trees.