texts:
As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue.

The setting is as follows: Let $\epsilon>0$. we need to maintain a space-efficient data structure that supports the following operations:

$add(x)$ - add $x$ to the front of the queue. All elements are integers in the range $0,1,\ldots, R$.

$remove()$ - removes the oldest element from the queue. The function is not required to output the element (or anything else).

$sum()$ - returns an approximation for the sum of the elements in the queue. The estimation error must be smaller than $n\cdot R\cdot \epsilon$, where $n$ is the number the queue contains at the moment of the query.

All operations are required to run in constant time.

For example, consider $\epsilon = 0.1, R = 100$ and the sequence:

$add(50)$

$add(33)$

$add(72)$

$remove()$

$sum()$

Then the algorithm is required to answer a number within $105\pm 20$.

A trivial solution maintains a linked list with a sum variable, computing the exact sum. The space requirements of this algorithm is $O(n\cdot\log R)$.

Another simple solution is to keep a linked list of approximated values (represent each element using $O(\log\frac{1}{\epsilon})$ bits), which results in a $O(n\log\frac{1}{\epsilon})$ space algorithm.

Our solution uses some compression techniques to reduce the complexity to $O(\min\{\frac{1}{\epsilon} + \log n, n\log\left\lceil1+\frac{1}{n\epsilon}\right\rceil\})$ by keeping an approximate representation of "blocks" of elements.

  Is this result known? Are there known sub-linear (in the number of elements in the queue) algorithms for computing statistics (sum / norms / percentiles/ etc.) of a queue?

This problem can be viewed as a generalization of summing over sliding windows in streaming data (e.g., see [1] and [2]).


texts:
Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that
$Y_i$'s are pairwise independent gaussians with mean $0$ and variance $1$.


texts: How can unification be applied to interaction combinators?

texts:
The problem of unifying interaction combinators is probably undecidable since those are turing complete. As opposed to the lambda calculus, there is nothing like a simple type theory for interaction combinators nor a subproblem of them that is known to be decidable.

When is it possible to unify interaction combinators?


texts: Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

texts:
Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space.

Since we are unable to build nondeterministic or 'lucky' computers, does it make any difference to us if a problem is $NP$-complete or $PSPACE$-complete?


texts: Capacity of Uniquely Solvable Puzzle (USP)

texts:
In their seminal paper Group-theoretic algorithms for matrix multiplications, Cohn, Kleinberg, Szegedy and Umans introduce the concept of uniquely solvable puzzle (defined below) and USP capacity. They claim that Coppersmith and Winograd, in their own groundbreaking paper Matrix multiplication via arithmetic progressions, "implicitly" prove that the USP capacity is $3/2^{2/3}$. This claim is reiterated in several other places (including here on cstheory), yet nowhere is an explanation to be found. Below is my own understanding on what Coppersmith and Winograd do prove, and why it's not enough.

  Is it true that the USP capacity is $3/2^{2/3}$? If so, is there a reference for the proof?

Uniquely solvable puzzles

A uniquely solvable puzzle (USP) of length $n$ and width $k$ consists of a subset of $\{1,2,3\}^k$ of size $n$, which we also think of as three collections of $n$ "pieces" (corresponding to the places where the vectors are $1$, the places where they are $2$, and the places where they are $3$), satisfying the following property. Suppose we arrange all the $1$-pieces in $n$ lines. Then there must be a unique way to put the other pieces, one of each type in each line, so that they "fit".

Let $N(k)$ be the maximum length of a USP of width $k$. The USP capacity is
$$ \kappa = \sup_k N(k)^{1/k}. $$
In a USP, each of the pieces needs to be unique - that means that no two lines contain a symbol $c \in \{1,2,3\}$ in exactly the same places. This shows (after a short argument) that
$$ N(k) \leq \sum_{a+b+c=k} \min \left\{ \binom{k}{a}, \binom{k}{b}, \binom{k}{c} \right\} \leq \binom{k+2}{2} \binom{k}{k/3}, $$
and so $\kappa \leq 3/2^{2/3}$.

Example (a USP of length $4$ and width $4$):
$$\begin{align*}
1111 \\ 2131 \\ 1213 \\ 2233
\end{align*}$$
Non-example of length $3$ and width $3$, where the $2$- and $3$-pieces can be arranged in two different ways:
$$\begin{align*}
123 && 132 \\ 231 && 321 \\ 312 && 213
\end{align*}$$

Coppersmith-Winograd puzzles

A Coppersmith-Winograd puzzle (CWP) of length $n$ and width $k$ consists of a subset $S$ of $\{1,2,3\}^k$ of size $n$ in which the "pieces" are unique - for any two $a \neq b \in S$ and $c \in \{1,2,3\}$,
$$ \{ i \in [k] : a_i = c \} \neq \{ i \in [k] : b_i = c \}. $$
(They present it somewhat differently.)

Every USP is a CWP (as we commented above), hence the CWP capacity $\lambda$ satisfies $\lambda \geq \kappa$. Above we commented that $\lambda \leq 3/2^{2/3}$. Coppersmith and Winograd showed, using a sophisticated argument, that $\lambda = 3/2^{2/3}$. Their argument was simplified by Strassen (see Algebraic complexity theory). We sketch a simple proof below.

Given $k$, let $V$ consist of all vectors containing $k/3$ each of $1$s, $2$s, $3$s. For $c \in \{1,2,3\}$, let $E_c$ consist of all pairs $a,b \in V$ such that $\{ i \in [k] : a_i = c \} = \{ i \in [k] : b_i = c \}$, and put $E = E_1 \cup E_2 \cup E_3$. Every independent set in the graph $G = (V,E)$ is a CWP. It is well-known that every graph has an independent set of size $|V|^2/4|E|$ (proof: select each vertex with probability $|V|/2|E|$, and remove one vertex from each surviving edge). In our case,
$$ |V| = \binom{k}{k/3} \binom{2k/3}{k/3}, \quad |E| \leq 3|E_1| = \frac{3}{2}\binom{k}{k/3} \binom{2k/3}{k/3}^2. $$
Hence
$$ \frac{|V|^2}{4|E|} = \frac{1}{6} \binom{k}{k/3} \Longrightarrow \lambda \geq \frac{3}{2^{2/3}}. $$


texts: New theories and publications on computer science

texts: When someone develops a new theory on computer science, specifically in artificial intelligence domain, which is barely on schetch (so there are no measurements, nor simulations, nor finished code or ready application) with just a mathematical and conceptual description, in which scientific journals people use to publish these theories/concepts?


texts: maintaining a balanced spanning tree of a growing undirected graph

texts:
I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.

I have an undirected graph that starts as a single node, the "root".

At each step, I add to the graph either a new node and an edge connecting it to the graph, or just a new edge, connecting two old nodes. As I grow the graph, I maintain a spanning tree. Most of the time, this means that when I add a new node and edge, I set the new node to be the child of the old node that it connects to.

I have no control over the order in which the new nodes are added, so the above tree-building algorithm can obviously lead to imbalanced spanning trees.

Does anybody know of online heuristics that will keep the spanning tree "relatively balanced", while minimizing the amount of work done in re-treeing? I have full control over the tree structure. What I don't control is the graph connectivity, or the order in which new nodes are added.

Note that the standard Google responses to terms like "balanced" "spanning" and "tree" seem to be binary trees and B-trees, neither of which apply. My graph nodes can have any number of neighbors, so the tree nodes can have any number of children, not 2 like binary trees. B-trees maintain balance by changing their adjacency lists, and I cannot change the graph connectivity.


texts:
For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.

For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.

A $k$-uniform hypergraph ${\mathcal H}\subset [n]$ is called a shift-chain if for any hyperedges, $A, B \in {\mathcal H}$, we have $A\le B$ or $B\le A$. (So a shift-chain has at most $k(n-k)+1$ hyperedges.)

We say that a hypergraph  ${\mathcal H}$ is two-colorable (or that it has Property B) if we can color its vertices with two colors such that no hyperedge is monochromatic.

Is it true that shift-chains are two-colorable if $k$ is large enough?

Remarks. I first posted this problem on mathoverflow, but nobody commented on it.

The problem was investigated on the 1st Emlektabla Workshop for some partial results, see the booklet.

The question is motivated by decomposition of multiple coverings of the plane by translates of convex shapes, there are many open questions in this area. (For more, see my PhD thesis.)

For $k=2$ there is a trivial counterexample: (12),(13),(23).

A very magical counterexample was given for $k=3$ by Radoslav Fulek with a computer program:

(123),(124),(125),(135),(145),(245),(345),(346),(347),(357),

(367),(467),(567),(568),(569),(579),(589),(689),(789).

If we allow the hypergraph to be the union of two shift-chains (with the same order), then there is a counterexample for any $k$.

Update. I have recently managed to show that more restricted version of shift-chains are two-colorable in this preprint.

Permanent bounty! I'm happy to award a 500 bounty for a solution anytime!


texts: PiSigma: why does 'unfold' bind a variable?

texts:
I'm trying to understand the paper ΠΣ: Dependent Types without the Sugar by implementing an interpreter and type checker for the language. In doing so, I've seen that the unfold t as x -> u syntax for recursive definitions (syntax is defined in Section 2.1) binds a variable, but I don't see why that's needed. None of the examples in the paper actually use the variable binding -- they all use a shorthand form unfold t (meaning unfold t as x -> x).

I do see that the type checking rule for it (from section 5) uses the variable binding, but I don't understand the implications of this. As far as I can tell unfold t as x -> u is entirely equivalent to let x = unfold t in u.

Can someone provide an example of when the variable binding is helpful or necessary? Is there some term that type-checks with the long form of unfold but not with the short form and let?


texts: Removing all but a few cycles in a graph

texts:
Let problem $S$ be defined as

  Given undirected graph $G$ and a set
  of cycles $C_1,C_2, \ldots, C_n$ in G,
  find minimum number of vertices that
  need to be deleted to remove all
  cycles in the graph G except the
  specified set.

Surely Problem $S$ is NP-hard, since finding minimum number of vertices required to remove all cycles in G (feedback vertex set) is NP-hard

My question is:

  Is it possible to Reduce Problem S to
  the feedback vertex set problem in an undirected
  or directed graph reduction such that if there exist a solution for problem S of size at most k in G iff there exist a feedback vertex set of size at most k in G'

ksoltys gives a reduction (answer below) from Problem S to feedback vertex set when we are not allowed to pick vertices from the forbidden cycles $C_1,C_2, \ldots, C_n$ .Suppose we are allowed to pick vertices from these forbidden cycle. Is there a reduction such that if there exist a solution for problem S of size at most k in G iff there exist a feedback vertex set of size at most k in G'


texts: Expressing a set of 0-1 strings by Extended Formulation

texts:
Extended Formulation of a polytope $P \subseteq \mathbb{R}$ is a system of linear constraints which satisfies the following condition:
$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$
A convex set of $n$-points $x_{1},...,x_{n}$ in $\mathbb{R}^{d}$ is defined as $\mbox{conv}(\{x_{1},...,x_{n}\})=\{y\in \mathbb{R}^{n}  |y=c_{1}x_{1}+c_{2}x_{2}+\cdots +c_{n}x_{n}, c_{1}+c_{2}+\cdots +c_{n}=1   \}$
Question:
Is the following statement true ?
Statement:
For every $P\subseteq  \{0,1\}^{n}$, If we construct a system of linear constraints $ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$ such that
$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$
,then the system of linear constraints $ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$ is a extended formulation of $\mbox{conv}  (P)$  ?
I am not sure about expressing a set of boolean strings by linear constraints.


texts:
Given a graph in which each vertex $A_i$ has float value $B(i)$ between 0 and 1 inclusive.
How can we find a cycle (if such exists) with vertices $[C_1, C_2, ..., C_k]$ which violates following condition: $\sum(B(C_i)]) \le k/2$ (integer division)?
Thank you.


texts: Are process calculi (pi calculus, CSP) "shared memory"?

texts:
In Andrews' foundations of multithreaded parallel and distributed programming, "shared memory/variable" and "message passing" seem to be opposite programming models, and CSP is message passing:

Part 2 Distributed Programming
The synchronization constructs we have examined so far are based on
reading and writing shared variables. Consequently, they are most
commonly used in concurrent programs that execute on hardware in which
processors share memory.
Distributed-memory architectures are now common. ...
Chapter 7 examines message passing, in which communication channels
provide a one-way path from a sending to a receiving process. Channels are
FIFO queues of pending messages. They are accessed by means of two
primitives: send and receive. To initiate a communication, a process sends a
message to a channel; another process acquires the message by receiving from
the channel. Sending a message can be asynchronous (nonblocking) or
synchronous (blocking); receiving a message is invariably blocking, as that makes
programming easier and more efficient. In Chapter 7, we first define
asynchronous message passing primitives and then present a number of examples that
show how to use them. We also describe the duality between monitors and
message passing: They are equivalent and each can directly be converted to the
other. Section 7.5 explains synchronous message passing. The last four sections
give case studies of the CSP programming notation, the Linda primitives, the
MPI library, and the Java network package.

Varela's programming distributed computing systems a foundational approach  use "shared memory" and "distributed memory" to describe opposite concurrency models, but strangely, pi calculus is called shared memory, because a channel is shared between multiple processes.

7.1.2 Shared or Distributed Memory
Memory or state in concurrency units—such as processes, actors, or join calculus
atoms—can be shared, where multiple concurrency units have the capability to read it
and update it, or distributed where only one concurrency unit owns it and can read it,
update it, or communicate its content to other units.
The π calculus has a shared memory model, where multiple processes can read
from a shared channel or write to a shared channel.

and it even goes on to give "Figure 7.1 A pictorial representation of shared memory in the π calculus."
As far as I know pi calculus and CSP both use channels that are shared between multiple processes. Wikipedia (https://en.wikipedia.org/wiki/Communicating_sequential_processes) says

CSP is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi, based on message passing via channels

(1). Does   "message passing" programming model of Andrews and   "distributed memory" concurrency models of Varela mean differently?
(2). Does "shared variables/memory"  programming model of Andrews and "shared memory"   concurrency models of Varela mean differently?
Does   Varela's "shared memory" as in pi calculus not mean the same sense as "shared memory" by threads of the same process, or by processes as in OS concepts and as in Andrew's book?
(3).  Is any model which uses a channel for communication between two or more processes, (e.g. any concurrency model in process calcluli?), both

a "shared memory" but not "distributed memory" concurrency model in Varela's sense, and
a "message passing" but not "shared variable/memory" programming model in Andrews' sense?

Thanks.
p.s. related questions:
https://cstheory.stackexchange.com/questions/47931/what-difference-are-between-the-topics-and-perspectives-of-these-two-distribute
https://cstheory.stackexchange.com/questions/47907/do-connection-and-message-coexist-in-csp-pi-calculus


texts: Are there any heuristics that works solely on graphs?

texts:
I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work solely on graphs where "traveling in a straight line" doesn't make sense at all?

Are there any heuristics that works solely on graphs (i.e. without requiring coordinates of the locations)?


texts: Expected probability of error in Vapnik's book

texts:
In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ times the expected number of support vectors.

Is the expected probability of error - the LHS of inequality 10.32 - non-increasing in the number $l$ of training samples?


texts: multi-party Communication complexity of "Set Partition problem"

texts:
In an application I'm considering, I need to know the communication complexity of the following problem:

Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each receives a subset of $S$, denoted by $A$, $B$, and $C$, respectively. They want to check whether $A$, $B$ and $C$ form a partition of $S$, i.e., they are disjoint and their union is $S$.

I'm particularly interested in the case of 3 parties but other cases would be interesting as well.  Note that for the case of 2 parties, the problem is equivalent to EQUALITY problem so it has $\Omega(n)$ lower bound for deterministic protocols but $O(\log n)$ upper bound for randomized protocols.

My question is whether this problem is known before. If you know any problems that might be related, I would be interested to know as well.


texts:
Impagliazzo gave a talk last week at Simons Institute on oracle separation. At minute 5:34 he asks whether a one-way permutation can be constructed given oracle access to a random function oracle. Then he explains why it is tricky using "history and pre-image" paradigm.

This paradigm wasn't clear to me although it seems a cornerstone. Could someone volunteer to explain it?


texts: Help on the following combinatorial problem?

texts:
I have $m$ bit vectors, each of which is composed by $m$ bits. Let's denote with $v_i[j]$ the $j$-th bit of the $i$-th vector, $i,j \in [1, m]$. Each bit vector $v_i$ is subject to the following 2 restrictions:

$v_i[j] = 0\ \forall j \geq i$.
$v_i[j] = 1\ \forall j < i - \frac{m}{log(m)}$.
Those bits that do not fall in the restrictions above can be either $0$ or $1$, but in such case the number of $0$'s can be at most $12$.

Now I have another bit vector $s$, of $m$ bits: initially all the $m$ bits of $s$ are set to $1$. By "applying $v_i$ to $s$" I mean performing a bitwise AND between $s$ and $v_i$, and then storing the result in $s$. I'm interested in the evolution of $s$ after repeated applications of the vectors $v_1, ..., v_m$ given in input.

Let's call those "repeated applications" a trajectory, and let's define such trajectory more formally. A trajectory is a sequence composed by at most $m$ vectors (selected from those $v_1, ..., v_m$ given in input) such that if $v_i$ is in the sequence, then all the $v_j$ after it must have $j < i$. So, for example, $<v_8, v_3>$ is a trajectory, while $<v_3, v_8, v_7>$ is not (because $8\geq3$).

Clearly, there are $2^m$ different trajectories. Let $S=\emptyset$. Suppose to take $s = 1^m$ and to let it undergo a trajectory $T_1$: for each step of the trajectory $T_1$, put the new value taken by $s$ in $S$. Then repeat the same process for another trajectory $T_2$ (always starting from $s=1^m$, and always putting every new value of $s$ in $S$). Then again, until you tried all the possible $2^m$ trajectories. At the end, the set $S$ will contain all the possible values that $s$ may ever assume given the vectors in input.

  Questions

  I have $v_i, ..., v_m$ in input. I want to know $|S|$, i.e. how many distinct values may $s$ ever assume. Of course, I want to compute $|S|$ efficiently, i.e. without trying all the possible trajectories one by one.
  Suppose to remove the 2nd restriction on the vectors in input. How doing so affects $|S|$?
  More importantly, what I most care about is how $|S|$ grows with $m$. Is $|S|$ at most polynomial in $m$? Is $|S|$ at most sub-exponential in $m$? Or do there exist bad instances on which $|S|$ is necessarily exponential in $m$?

The following figure is an example with $m=17$:

I'm collecting experimental data in order to try to figure out which is the relationship between $m$ and $|S|$. So far, experiments seems to suggest that $|S|$ grows faster than $m^3$ and slower than $m^4$. However, for the moment those data have not much significance: I was only able to make tests up to $m = 90$, so there may be a big hidden constant or some other factor that lets an exponential law look like a polynomial law for small $m$. I need help in figuring out the asymptotic behaviour of $|S|$ with respect to $m$.


texts: Complexity of recognizing vertex-transitive graphs

texts:
I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.

  Question 1. Let $G$ be a simple undirected graph of order $n$. What is the
  computational complexity (in terms of $n$) of determining if $G$ is
  vertex-transitive?

Recall that a graph $G$ is vertex-transitive if $\mathrm{Aut}(G)$ acts transitively on $V(G).$

I am not sure if the above definition allows for a polynomial time algorithm since it can be that the order of $\mathrm{Aut}(G)$ is exponential.

However vertex-transitive graphs have some other structural properties that might be exploited in order to be able to efficiently determine them so I am not sure what is the status of the above question.

Another interesting subclass of vertex-transitive graphs that has even more structure is the class of Cayley graphs. So it is natural to also pose the following related question

  Question 2. What is the computational complexity of determing if a graph $G$ is a
  Cayley graph?


texts:
We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm
$\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 + ε)\#A(x)$$
in time polynomial in $|x|$ and within $\frac1ε$ multiplicative factor, using an oracle for $NP$.

That is $\#P$ can be approximated in $BPP^{NP}$.

  What is the best derandomization result for this that is known?


texts: Counting reduction from #SAT to #HornSAT?

texts:
Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by counting reduction.

Suppose $f,g : \{0,1\}^* \to \mathbb N$ are two counting problems. For example, #SAT asks how many satisfiable assignments are there for a specific instance $\phi$, and $f,g$ are similar counting problems finding total number of witnesses. A weakly parsimonious counting reduction from $f$ to $g$ consists of a pair of polynomial time computable functions $\sigma : \{0,1\}^* \to \{0,1\}^*$ and $\tau : \{0,1\}^* \times \mathbb N \to \mathbb N$ such that $f(x) = \tau (x, g(\sigma(x)))$. In the case that $f(x) = g(\sigma(x))$, this is known as strongly parsimonious counting reduction.

I can see that if there is any such counting reduction from #SAT to #HornSAT, it must be weakly parsimonious reduction: a strong reduction would imply that the #SAT and #HornSAT instances will have zero or non-zero number of solutions together, and assuming that $\mathsf P \ne \mathsf{NP}$, this is impossible (as HornSAT $\in \mathsf P$ while SAT is $\mathsf{NP}$-complete).

So my question is: is there any weakly parsimonious counting reduction from #SAT to #HornSAT? If so, can anyone please give me some reference ?


texts: Lower bounds in PRAM model for evaluation of straight-line code

texts:
Miller, Ramachandran and Kaltofen showed that any straight line program can be executed in parallel time O(log n) using M(n) processors where M(n) is the number of processors for multiplying nxn matrices in O(log n) time.

My question is this: suppose that the number of processors is constrained to be at most polylogarithmic. What is the best lower bound known for parallel complexity of straight-line code evaluation?


texts: Random Sampling Threshold to Get a Connected Induced Subgraph

texts:
Working on network design this summer I have come across certain applications that have inspired me to ask the following question:

Given an undirected connected graph $G=(V,E)$ what is the minimum number of vertices, $k$, sampled uniformly and independently at random from $V$ (without replacement), such that the induced subgraph on those vertices is connected w.h.p.?

Notice, I am not looking for a way to sample a connected (induced) subgraph, I am looking for a probabilistic guarantee that I have sampled enough vertices to end up with a connected induced subgraph.

Does this sounds familiar to anyone? A quick search was not very promising so I decided to ask here if anyone has any references or even directions to point me at.

I am assuming the answer would be a function of some structural property(/ies) of the graph, like connectedness, minimum degree, expansion, etc..


texts: Fourier decomposition in terms of another basis

texts:
Given a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$, it is well know that the Fourier decomposition of $f$ can be written as $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) \prod_{i\in S} x_i$ where $\widehat{f}(S)$ are the Fourier coefficients. So the quantity $\prod_{i\in S} x_i$ can be viewed as the parity of $x\in \{-1,1\}^n$ when restricted to $S\subseteq [n]$.

Is there a way to write the Fourier decomposition in terms of the AND of its variables, i.e., is it possible to express every Boolean function $f$ in terms of
$f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) AND(x_{S})$?  Can this be generalized even further? In general, can any polynomial $p:\{-1,1\}^n\rightarrow \mathbb{R}$ be written in terms of an "AND" decomposition instead of a parity decomposition (in the Fourier sense).


texts:
There some internet pages:

http://en.wikipedia.org/wiki/Program_synthesis
http://research.microsoft.com/en-us/um/people/sumitg/pubs/synthesis.html
https://sites.google.com/site/asergrp/bibli/program-synthesis

But, honestly, i can't find entrance to that topic. There are a lot of advanced level talks but only a few "hello world" examples(or completely none).

So where can one start learning about program synthesis ?


texts: Fuzzy K-modes clustering how to find the cluster centers

texts:
I'm trying to understand [fuzzy k-modes][1] algorithm (look mainly at page 3) in order to implement it.
I'm stuck at the calculation of cluster centers they said as shown in the link
https://stackoverflow.com/questions/7788417/fuzzy-k-modes-clustering-how-to-find-the-cluster-centers
I need to know whether the following is true or false and please correct me
In order to get the center of a cluster we need to:

for each category in a variable calculate the sum of membership value for all the point, that the category belongs to, to this cluster
the highest obtained value to be set as the category of the center


texts: Martingale exit arguments for gradient Langevin dynamics

texts:
I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high probability to be concentrated in a ball around the global minimum (say $x^*$).

Between equations 33-36 there seems to be happening a tricky use of Azuma-Hoeffding inequality that I dont seem to understand. Schematically this is what is happening : for a sequence of iterates/r.vs $\{ X_i' \}$, the authors define another sequence of r.vs $\{ Y_i = \Vert X_i' - x^*\Vert^2 - iP \}$ for some constant $P>0$ . Then the authors show that $Y_{i+1} - Y_i \leq Q$ for some constant $Q>0$. Now for some $\lambda >0$, they seem to want to do Azuma-Hoeffding to upperbound,

$$ \mathbb{P} \left [ \sum_{k=1}^i (Y_{k} - Y_{k-1}) > \lambda \right ] \leq e^{-\frac{\lambda^2}{2Q}}$$

How is this possible? Even if we believe that the difference sequence sequence, $\{ Y_{i+1} - Y_i \}$ satisfies the conditions for Azuma-Hoeffding to be applied to it, shouldn't the RHS be $e^{-\frac{2\lambda^2}{iQ}}$. Where is this ``$i$" in the exponent?

For concreteness I should state that I am using conventions about the Azuma-Hoeffding inequality as given in Corollary 3.9 (page 57) here https://web.math.princeton.edu/~rvan/APC550.pdf

Secondly how do we know here that $Y_{i+1} - Y_i$ even satisfies the conditions for Azuma-Hoeffding to be applied? One sufficient condition is to show, (a) that this difference is bounded in absolute value and (b) that $\mathbb{E} \left [ Y_{k} - Y_{k-1} \vert {\cal F}_{k-1} \right ] =0$ where ${\cal F}_{k-1} = \sigma (\{ X_i \}_{i=0,\ldots,k-1})$

Towards (a) we only seem to know that this difference is upperbounded and towads (b) we observe that here $Y_k$ is a function of $X_{k}$ and which in turn, because of the nature of gradient Langevin dynamics, is a function of all the iterates and injected noise till the $(k-1)^{th}$ iterate. So both $Y_k$ and $Y_{k-1}$ are  ${\cal F}_{k-1}$ measurable and hence $\mathbb{E} \left [ Y_{k}  - Y_{k-1} \vert {\cal F}_{k-1} \right ] = Y_k - Y_{k-1}$ and thats not $0$. What am I missing?


texts: A Boolean function that is not constant on affine subspaces of large enough dimension

texts:
I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension of this subspace is $o(n)$.

It is not difficult to show that a symmetric function does not satisfy this property
by considering a subspace $A=\\{x \in \\{0,1\\}^n \mid x_1 \oplus x_2=1, x_3 \oplus x_4=1, \dots, x_{n-1} \oplus x_n=1\\}$. Any $x \in A$ has exactly $n/2$ $1$'s and hence $f$ is constant the subspace $A$ of dimension $n/2$.

Cross-post: https://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen


texts: The number of cliques in a graph: the Moon and Moser 1965 result

texts:
I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't have access to the particular journal. (In fact, the preview provides the first few sentences of the proof, but then leaves me without the rest!)

I was interested in this result related to a research direction I was pursuing, but the direction has changed slightly, so admittedly my interest is now purely academic curiosity.

My question is:

  Is there a link to the full text of the paper somewhere OR another paper that sketches the proof OR if a proof sketch is short enough to reproduce here, does anyone know it? Also, I'm interested in the class of graphs with an exponential number of cliques.

I added the BibTeX for reference:

@article {springerlink:10.1007/BF02760024,
   author = {Moon, J. and Moser, L.},
   affiliation = {University of Alberta Edmonton Canada},
   title = {On cliques in graphs},
   journal = {Israel Journal of Mathematics},
   publisher = {Hebrew University Magnes Press},
   issn = {0021-2172},
   keyword = {Computer Science},
   pages = {23-28},
   volume = {3},
   issue = {1},
   url = {http://dx.doi.org/10.1007/BF02760024},
   note = {10.1007/BF02760024},
   year = {1965}
}


texts: Find the Discrete Pair of {x,y} that Satisfy Inequality Constriants

texts:
This question has been asked at StackOverflow ( a variant of this has been asked at Math SE), but so far there is no great response. So I'm going to reask here-- with a bit of twist.

I have a few inequalities regarding $x,y$ ( both must be integer), that satisfies the following equations:

$$x>=0$$
$$y>=0$$
$$100 \leq x^2+y^2 \leq 200$$

Is there an algorithm (non-brute force!) that allows me to find every admissible pair of $x,y$?

The $100 \leq x^2+y^2 \leq 200$ is just an example; in general the constraint equation(s) can be of polynomial functions with any degree.


texts: Other popular lambda calculus encodings besides Church's?

texts: I know once could start from the popular Church encodings of booleans, ints, etc and arbitrarily obfuscate and complicate them to obtain new representations of the same concepts, but are there other popular encodings that aren't sourced this way?


texts: Relation between edit distances over different alphabets

texts:
Assume we have two strings $S_1$ and $S_2$ of lengths $cn$ and $cm$ bits resepctively for some $c\in\Bbb N$.

Assume that the Levenshtein distance (minimum number of single-character edits (i.e. insertions, deletions or substitutions)) between $S_1$ and $S_2$ over binary alphabet is $L(2)$.

For any $b$ such that $b>1$ and $b|c$ consider the strings $S_1$ and $S_2$ over alphabet $\{0,1,\dots,2^b-1\}$. Assume the Levenshtein distance between $S_1$ and $S_2$ over $b$-ary alphabet is $L(2^b)$.

Is there any relation between $L(2)$ and $L(2^b)$ in general?

Can we say anything for LCS (minimum number of insertions or deletions) distance as well?


texts:
There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases:

$f$ is a member of some class of functions $\mathcal{C}$
$f$ is $\varepsilon$-far from every function in class $\mathcal{C}$.

The range $R$ of the function is sometimes Boolean: $R = \{0,1\}$, but not always.

Here, $\varepsilon$-far is generally taken to mean Hamming distance: the fraction of points of $f$ that would need to be changed in order to place $f$ in class $\mathcal{C}$. This is a natural metric if $f$ has a Boolean range, but seems less natural if the range is say real-valued.

My question: does there exist a strand of the property-testing literature that tests for closeness to some class $\mathcal{C}$ with respect to other metrics?


texts: Consequences of existence of a strongly polynomial algorithm for linear programming?

texts:
One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and constraints and is independent of the size of the representation of the parameters (assuming unit cost arithmetic).  Would resolving this question have implications outside of better algorithms for linear programming?  For instance, would the existence/non-existence of such an algorithm have any consequences for geometry or complexity theory?

Edit: Maybe I should clarify what I mean by consequences.  I'm looking for mathematical consequences or conditional results, implications that are known to be true now.  For instance: "a polynomial algorithm for LP in the BSS model would separate/collapse algebraic complexity classes FOO and BAR", or "if there is no strongly polynomial algorithm then it resolves such-and-such conjecture about polytopes", or "a strongly polynomial algorithm for problem X which can be formulated as an LP would have interesting consequence blah".  The Hirsch conjecture would be a good example, except that it only applies if simplex is polynomial.


texts:
In Notions of Computation and Monads Moggi models the notion of a computation of type $A$, $TA$, using a monad $T$. Among other things this ensures the $T\eta$ rule:

$$\frac{x: A \vdash a:TB}{x:A \vdash let \,  y \Leftarrow a \, in\, [y] = a}$$

This rule prevents distinct computations having the same value. Is there a weakened notion of a monad that does not yield the $T\eta$ rule? Has this question already been studied? I'm particularly interested in the logic you get when you drop $T\eta$ from Moggi's rules for the simple metalanguage, but keep the other rules in place (table 4 in the pdf).


texts: Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network

texts:
Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?

As far as I know, the only way to sort with $O(\log n)$ comparison on each element is to construct an AKS sorting network for $n$ inputs, and run the input on the sorting network.

AKS is not easy to implement and has an impractical constant factor, so there are motivations to search for other algorithms.

An algorithm with $O(\log^2 n)$ comparisons per item which does not seem to imply a sorting network is presented here. (iirc, this was first presented by Rob Johnson at Stony Brook's algorithm seminar).


texts: Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$

texts: Given a $\Sigma^p_2$-complete oracle (i.e., $\Sigma_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function problem (https://en.wikipedia.org/wiki/Function_problem.) I'm trying to prove the lower bound of this problem. Is there any canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$ that I can reduce from?


texts: Can one do quantum computing without negative amplitudes?

texts:
The typical representation I see of $k$ qubits is a $2^k$ complex numbers $c_i$ for every possible combination of values of those bits, such that the sum of all the squared magnitudes of those numbers is 1. i.e.

$$\sum_i \vert c_i \vert^2 = \sum_i (a_i + i b_i)(a - ib_i) = \sum_i a_i^2 + b_i^2 = 1$$

(so with two bits, we have $\vert c_0 \vert^2 = P(00)$, $\vert c_1 \vert^2 = P(01)$,  $\vert c_2 \vert^2 = P(10)$, and $\vert c_3 \vert^2 = P(11)$)

Then gates are simply defined by complex matrices of size $2^k \times 2^k$ that preserve this requirement (formally the set of such matrices is the unitary matrices). To apply a gate we simply multiply these matrices by our current "vector of complex probabilites" and a new set of $c_i$'s. I.e., if $c \in \mathbb{C}^{2^k}$ and our unitary gate H is in $\mathbb{C}^{2^k \times 2^k}$  then we get our result $c^\prime \in \mathbb{C}^{2^k}$ via

$$c^\prime = H c $$

However, is using complex numbers necessary? What I mean is, we could instead define real $p_i = \vert c_i \vert$, and then to apply a gate we do

$$p^\prime = \vert H \sqrt{p} \vert^2 $$

(here by $\sqrt{p}$ and $|..|^2$ I mean I apply those operations to each element of the vector, and keep the vector the same size)

This answer seems to suggest we might be able to do this, and clearly this does preserve everything for one application of an operator if we pick $c_i = \sqrt{p_i} + 0i$, for example, but I don't know about a sequence of multiple gates that each output and work with rotated complex numbers with the same magnitude.

Personally I feel having a set of $0 \leq p_i \leq 1$ s.t. $\sum_i p_i = 1$ seems much more intuitive to me, so my question is simply: is a computer using these rules less powerful than a quantum computer? Or is it a separate complexity class?

As far as I can tell the main difference is gates with imaginary numbers: in this $p$ setting they result in an operation on the inputs in terms of real numbers but it may not be linear, and the order of applying the gates may now matter (try out the $\sqrt{NOT}$ gate for example), but I don't know if that actually matters in terms of what it can compute efficiently.

Edit: for example, the Hadamard gate

$$ H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

applied to $\begin{bmatrix} p_0 \\ p_1 \end{bmatrix}$ ($p_0$ is probability of $<0|$, $p_1$ is probability of $<1|$) would be

$$ p^\prime = \vert \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} \sqrt{p_0} \\ \sqrt{p_1} \end{bmatrix} \vert^2 = \vert \begin{bmatrix} \frac{\sqrt{p_0} + \sqrt{p_1}}{\sqrt{2}} \\ \frac{\sqrt{p_0} -\sqrt{p_1}}{\sqrt{2}} \end{bmatrix} \vert^2 = \begin{bmatrix} \vert \frac{\sqrt{p_0} + \sqrt{p_1}}{\sqrt{2}}\vert^2 \\ \vert \frac{\sqrt{p_0} -\sqrt{p_1}}{\sqrt{2}}\vert ^2 \end{bmatrix} =
\begin{bmatrix} \frac{p_0 + p_1}{2} + \sqrt{p_0}*\sqrt{p_1} \\ \frac{p_0 + p_1}{2} - \sqrt{p_0}*\sqrt{p_1}\end{bmatrix} $$


texts: Shortest string containing all fixed-length substrings

texts:
This is related to a math.SE question I asked, but I've realized I want a slightly different form and it's probably more of an algorithms question.

Fix an alphabet $\Sigma$.  Let $P(n)$ be all length-$n$ strings over $\Sigma$.  What is the shortest string $S$ such that every $s \in P(n)$ is a substring of $S$?

For example, let $\Sigma = \{a\}$ and $n=1$; then clearly $S=a$ is minimal.  If instead $\Sigma = {a,b}$ and $n=2$, $P(2) = {aa, ab, ba, bb}$ and $S = aabba$ is minimal.

Clearly we are solving "shortest common superstring" over $P(n)$, and it's known to be MaxSNP hard. I'm wondering if this special form, with $P(n)$ containing all substrings of $\Sigma$ might be easy?!


texts: Alternative proofs of Schwartz–Zippel lemma

texts:
I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz.

Are there any other proofs which use substantially different ideas?


texts: Guidelines to reduce general TSP to Triangle TSP

texts:
I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie:

$D(a, b) \leq D(a, c) + D(c, b)$

I am not sure how to attack this kind of problem, so any pointers / explanations regarding this would be helpful. Thank you.


texts: How do we contribute to the lexicon of computer science?

texts:
What's the best way to contribute to the lexicon of computer science? There is an obvious organic nature to the naming of things in most sciences. The name of the discoverer is inherited or bestowed, the taxonomy of the subject lends a name directly, the author of the authoritative text names it with their full expertise of the subject behind them... But what are the other routes? What if something is poorly named, conflicts with other names, just ambiguous, etc?

In CS we frequently have semantic debates in the pursuit of good names, cause we're constantly creating things. CS is one of the few fields where these arguments really make a difference. A good deal of any developers time is being thoughtful about the names of things, and it becomes a sort of learned skill. Are there established routes for either renaming something, or proposing new names for things that are ambiguously defined?

There are endless examples of the need, but I'd like to provide a specific example: Dynamic programming. The history of the name is well known and it's not well named.


texts: References to programming languages based on conditional logics

texts:
Conditional logics are logics which augment traditional logical implication with modal operators corresponding to other notions of condition (for example, the causal conditional $A\; \square\!\!\!\!\to B$ reads "$A$ causes "B", or probabilistic conditioning "$A|B$", which reads "$A$ given $B$").

Typically these logics are studied model-theoretically, but I've wondered about their applications to programming language design (for example, to type imperative actions).

I'd appreciate references to their proof theory (ie, sequent calculus/natural deduction), or to programming languages with types based on these kinds of modal operators.

Thanks!

EDIT: The Stanford Encyclopedia of Philosophy has a nice introduction to the subject.


texts: $CIS_G$ problem deterministic lower bound

texts:
In notes, http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf, it is mentioned towards end of section $4$ that http://dl.acm.org/citation.cfm?id=237817 shows that deterministic complexity of $CIS (\mathsf{Clique-IndependentSet})$ problem is $$D(CIS_G)\geq (2-o(1))n$$ with a specific graph $G$. I checked cited paper, it mentions no citation of $CIS_G$. However, it specifies a function for which $$D(f)\geq(2-o(1))n$$ holds in theorem $3$.

My question is how is this result connected to $CIS_G$? In other words how does lower bounds $D(f)$ on a function $f$ gives lower bounds on $CIS_G$ and/or vice versa?

What is best lower bound known for $D(CIS_G)$?


texts: Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length

texts:
If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then
$$\max_i  \sum_j (a_{ij} x_j + b_j)  \qquad (\ast)$$
is a convex piecewise linear function of $(x_1, \ldots, x_n) \in \mathbb{R}^n$. We can minimize it efficiently using linear programming.

I want to minimize an expression of the form
$$\sum_h \max_i  \sum_j (a_{hij} x_j + b_{hj}) \qquad (\dagger)$$
where $a_{hij}$ is an $\ell \times m \times n$ array of integers of bounded size and $b_{hj}$ is an an $\ell \times n$ array of integers of bounded size.

  Is there a method to do this, polynomially in $(\ell, m, n)$?

Note that $(\dagger)$ is equivalent to an expression of the form $(\ast)$, so it is convex and piecewise linear, but writing it that way involves the $\max$ of $m^{\ell}$ terms.


texts: Source Coding Theorem: what happen when we go below N*H(x) bits?

texts:
I was following the textbook by David Mackay: Information theory inference and learning algorithms.

I have question on Shannon's source coding theorem (p81):

  $N$ i.i.d. random variables each with entropy $H(x)$ can be compressed into more than $N \cdot H(x)$ bits with negligible risk of information loss, as $N \to\infty$; conversely if they are compressed into fewer than $N \cdot H(x)$ bits it is virtually certain that information will be lost.

My question is the bold part of the above: what happens when you go below $N \cdot H(x)$ bits?

There is an example in the textbook (p77), where he shows that, as $N$ increases, the average entropy per symbol approaches $H(X)$, for a risk tolerance $0 \lt \delta \lt 1$. (So it becomes flatter as indicated on the diagram.) Therefore,  $N \cdot H(x)$ is the number of bits you can compress no matter how much risk tolerance you are willing to take.

In the definition above, however, it is saying that information will be lost if you go below $N \cdot H(X)$. My question is, how much information will be lost?

I found something on the web regarding this question: http://www.kim-bostroem.de/Library/Notes/Shannon.pdf

It is saying that for each symbol, if you compress below $H(x)$ bits, then               for $N \to\infty$, we will lose all the information. Can someone please confirm this?


texts: Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times?

texts: The standard proof that BQPSPACE is in PSPACE relies on a Savitch game type analysis on path integrals. However, it assumes the time running length for BQPSPACE is at most exponentially long. This is true for PSPACE, but for closed quantum systems with a fixed number of degrees of freedom, it typically takes a doubly exponentially long time before Poincare recurrence due to the exponential nature of the state vector. So, does the proof still run through, or not?


texts: What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

texts:
In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$.

I wanted to know if there are more examples like this.


texts:
$\mathbf{Definition.}$ A random variable $X$ has pseudoentropy $k$ if it is computationally indistinguishable from a random variable $Y$ with $H(Y) = k$, where $H(Y)$ is the Shannon entropy of $Y$.

By this definition, can we say that any random variable has pseudoentropy equals to its Shannon entropy, just because it is computationally indistinguishable from itself? The caveat here is whether or not the definition of computational indistinguishability is still valid when there is only one random variable, not two.


texts: Inclusion probability of irregularly shaped polygon

texts:
I have two shapes, one is a circle, let's call it Circle A, and another irregularly shaped Polygon B. A will always have a greater area than B. Both of these polygons exist inside an area S.

My task is to compute the inclusion probability of Polygon B in a random sample, where inclusion is defined as Polygon B being entirely inside of Circle A (the circle).

My assumption is that the inclusion probability of Polygon B is the area of another Polygon C, which equates to the area in which Circle A can be placed so that it can enclose Polygon B divided by the total area of S.

If this assumption is correct, then computing Polygon C seems computationally intensive.

Is there an efficient method for finding Polygon C?


texts:
Let us consider a complete weighted graph, with $NM$ nodes.
Our objective is to find, among all possible combinations of $N$ disjoint $M$-cliques (each clique consisting of $M$ nodes), the configuration that maximizes/minimizes the sum of the $N$ $M$-cliques weights.
Here the weight of a $M$-clique is the sum of the edge weights between all the $M$ nodes composing the clique.

It sounds like a classical mathematical problem, but I have been spending hours without finding anything.
The special case where $M=2$ consists of a maximal weighted matching problem in a complete graph and can be solved using Edmonds Matching Algorithm, but I can't find anything for $M>2$.

Is there an efficient algorithm for this problem?


texts: Formal Semantics of Programming Languages

texts: I'm new to programming languages theory and I'm seeking for a good resource on a resource for formal semantics  of programming languages. Specifically looking  for structural operational semantics. I got some book recommendations. But I'm looking for a resource in a  more introductory level. Especially tutorials, web-site and free book recommendations are  welcomed.


texts: existence & characterization of "kolmogorov efficient" programs

texts:
$\newcommand{\Prog}{\operatorname{Prog}}\newcommand{\kol}{\operatorname{kol}}$
Disclaimer: I do not have a formal background in algorithmic complexity theory so apologies if I use non-standard notation.

Fix a language $L$. Let $C$ be the set of computable functions $\mathbb N\to\mathbb N$. Further, denote with

$$ \Prog(f) = \{p\in L\mid p\text{ describes }f\}$$

the set of (computable) descriptions of $f$ in the language $L$ and the length of a program by $|p|$.

Given a function $f\in C$ and a (computable) description $p_f\in\Prog(f)$, let's define the following:

Call $p_f$ "kolmogorov efficient" if and only if it is shorter than the description of any program of any other computable function $g\in C$, if $f$ and $g$ agree for sufficiently many inputs. That is $p_f$ is efficient if and only if

$$\forall g\in C\exists n_0\in\mathbb N\forall n\ge n_0 \Big[f\big|_{[0, n]} = g\big|_{[0,n]} \implies\forall q\in\Prog(g) : |p_f|\le |q|   \Big]$$

Note that since we are allowed to choose $g=f$, $p_f$ must be a shortest description of $f$. Further, we call $f\in C$ "simple" if and only if
$$\exists p_f \in \Prog(f): p_f \text{ is kolmogorov efficient} $$

My questions:

Does this notion exists already? Maybe under another name?
Are all computable functions simple?
If not, is there a way to figure out if a function is simple (sufficient/necessary criteria?)

Remark I came up with this definition whilst pondering how to formalize Occam's razor & inductive learning. Consider for example a classical intelligence test question:

  extent the sequence 1,2,4,8,16, ...

Of course, given a finite length sequence there are infinitely many ways to continue it (e.g. take any interpolating polynomial). However the "obvious" answer, $f(n) = 2^n$, stands out in regards to having low kolmogorov complexity. So given that we only observe a finite sequence, the simple function is supposedly the preferred solution.


texts: Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

texts:
I'm considering integer programming on an variation of Steiner Forest Problem:

  Given a graph $G=(V,E)$, a cost function: $c:E \rightarrow R^{+}$, a terminal set $T \subseteq V$, and a positive integer $k$, find a subgraph containing at most $k$ connected components that includes all the terminals with minimum total edge cost.

The key point of constructing the ingeger programming is to enforce the $k$ connected components constraint. The only way I came up with is using the generalized subtour elimination constraints over edge variables for each connected component. Is there any other ways to enforcing the $k$ connected components constraint? Any clue or suggestion would be appreciated.


texts: Is PARITY in QAC_0 (if that even makes sense)

texts:
As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in
fact const-dept circuits require EXP number of gates.

What about QUANTUM circuits?

a) Can PARITY be done with a quantum circuit that has constant depth and poly number of gates?

b) Does my question even make sense?


texts: Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

texts:
Since every $3$-SAT instance with $n$ variables can be expressed as a  degree-$3$ polynomial over $\mathbb{F}_2$ with $n$ unknowns,  the NP-hardness of $3$-SAT directly translates to NP-hardness of solving(finding roots) $3$-degree polynomials.

So my question is solving a single degree-$2$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, NP-hard?


texts: Derivation of cut rule in sequent calculus

texts:
I searched internet but could not find any good weblink which shows how the cut rule for sequent calculus can be derived.

I found this paper but it uses implication elimination rule which I cannot find as a standard rule anywhere (see page 2).

Thanks in advance.


texts: Complexity of unbalanced bipartite isomorphism

texts:
For $i=1,2$, let $G_i=(A_i\cup B_i,E_i)$ be an undirected bipartite
graph with bipartition $A_i$ and $B_i$, where $|A_1|=|A_2|=a$ and
$|B_1|=|B_2|=b$ with $a\le b$.

  Question. Is the problem of deciding isomorphism between
  such graphs solvable in $O(b^k 2^a)$ time, for some constant $k>0$?

Note that Babai's result yields a $2^{(\log(a+b))^c}$ time
algorithm for some constant $c>1$.
For the cases with $a=O(\log b)$, a solution to my question would
yield a polynomial time complexity.


texts:
1) What, if any, is the relationship between static typing and formal grammars?

2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was well typed? A nested stack automaton?

3) Is there a natural way to express static typing rules in formal grammar terms?


texts: What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes

texts:
I'm trying to wrap my head around what the real differences between the Actor Model of concurrency and Communicating Sequential Processes (CSP) model of concurrency.

So far the best that I have been able to come up with is that the Actor Model allows the number and layout of nodes to change while CSP has a fixed structure of nodes.


texts: Constraint satisfaction problem on a graph

texts:
Consider the set $S = \{1, \dots, n\}$ and $n$ subsets $S_i \subseteq S$ of size $d$ each (think of $S_i$ as neighborhoods of vertex $i$ in some $d$-regular graph, although the graph structure is not important here). Each vertex can have label $0$ or $1$. Each set $S_i$ comes with 2 constraints: there can be at most $k_i$ zeroes in $S_i$ and at most $l_i$ ones in $S_i$ (assume that $k_i + l_i \geq d$, otherwise constraints are clearly inconsistent). The problem - is it possible to check in time $\mathrm{poly}(n)$ (with fixed $d$) whether this constraint problem is satisfiable by at least one labelling of vertices?

It smells like something NP-hard, but I don't see an obvious reduction e.g. from $d-SAT$ since it's not clear you can implement negation by only this type of constraints.


texts: Reference Request: Computational Learning Theory

texts:
Pretty soon I will be finishing up Understanding Machine Learning by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble finding a book that could come after this. Ultimately, my goal is to read papers in JMLR's COLT.

Is there a book similar to Understanding Machine Learning that would progress my knowledge further and would go well after reading UML?
Is there any other materials (not a book) that could allow me to learn more or prepare me for reading a journal like the one mentioned above?

(also taking courses in this is not really an option so this will be for self-study)

This question was also asked here on AI SE from suggestion of comments.


texts: Quantum complexity of maximum inner product search

texts:
Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$.  Typically $k \ll m, n$ (many small dot products).  In the approximate version, we ask for entries within a factor $\alpha < 1$ of the true largest.

Unfortunately, Ahle et al. show that an approximate solution to MIPS in subquadratic time $O(k^{O(1)} (mn)^{1-\epsilon})$ for $\epsilon > 0$ would contradict the strong exponential time hypothesis.  Terminology note: Ahle et al. calls it inner product similarity join (IPS) instead of MIPS.

Ahle et al. consider only classical complexity.  However, it is easy to beat the subquadratic limit using a quantum computer: applying Grover to the $m \times n$ search space gives $\tilde{O}(k \sqrt{m n})$ for $l = 1$.

Question: Is $\tilde{O}(k \sqrt{m n})$ the right quantum complexity for $l = 1$?  What about for larger $l \ll m, n$?


texts: Major advance for measurement based quantum computing?

texts:
http://arxiv.org/abs/1211.3405

The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm

If this recent paper is true, it seems like a major advance for measurement based quantum computing.  The claim is based on numerical evidence, rather than a formal proof.  Is this as important/revolutionary as I think it is?

This makes me wonder: Is there a known relation between the speed of gate-based quantum computing and the speed of measurement-based quantum computing?


texts: Finding $n$ many different primes efficiently

texts:
I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ and then next in $n+1$ to $2n$ and so on. If we find primes like in this way then overall running time will be $O(n \log n)$.

Question : Is there any way to find $n$ many different primes in better than $O(n\log n)$ running time?


texts: How is the inner ring chosen in the Schönhage–Strassen algorithm?

texts:
I've been trying to implement the Schönhage–Strassen integer multiplication algorithm, but hit a stumbling block in the recursive step.

I have a value $x$ with $n$ bits and I want to compute $x^2 \pmod {2^n+1}$. I originally thought the idea was to pick a $k$ such that $4^k \geq 2n$, split $x$ into $2^k$ pieces each with $2^{k-1}$ bits, apply SSA's convolution while working modulo $2^{2^k}+1$, a ring with $2^k$ bits of capacity per value, then put the pieces back together. However, the convolution's output has slightly more than $2n$ bits (i.e. $>2^k$ bits per output value, which is more than the capacity of the ring, due to each output value being a sum of several products) so this doesn't work. I had to add on an extra factor of 2 of padding.

That extra factor of 2 in the padding ruins the complexity. It makes my recursive step too expensive. Instead of an $F(n) = n \lg n + \sqrt{n} F(2 \sqrt{n}) = \Theta(n \; \lg n \; \lg \lg n)$ algorithm, I end up with an $F(n) = n \lg n + \sqrt{n} F(4 \sqrt{n}) = \Theta(n \lg^2 n)$ algorithm.

I read a few references linked from wikipedia, but they all seem to gloss over the details of how this issue is solved. For example, I could avoid the extra padding overhead by working modulo $2^{p 2^k} + 1$ for a $p$ that's not a power of 2... but then things just break later, when I have only non-power-of-2 factors remaining and can't apply Cooley-Tukey without doubling the number of pieces. Also, $p$ may not have a multiplicative inverse modulo $2^p+1$. So there's still forced factors of 2 being introduced.

How do I pick the ring to use during the recursive step, without blowing the asymptotic complexity?

Or, in pseudo code form:

multiply_in_ring(a, b, n):
  ...
  // vvv                          vvv //
  // vvv HOW DOES THIS PART WORK? vvv //
  // vvv                          vvv //
  let inner_ring = convolution_ring_for_values_of_size(n);
  // ^^^                          ^^^ //
  // ^^^ HOW DOES THIS PART WORK? ^^^ //
  // ^^^                          ^^^ //

  let input_bits_per_piece = ceil(n / inner_ring.order);
  let piecesA = a.splitIntoNPiecesOfSize(inner_ring.order, input_bits_per_piece);
  let piecesB = b.splitIntoNPiecesOfSize(inner_ring.order, input_bits_per_piece);

  let piecesC = inner_ring.negacyclic_convolution(piecesA, piecesB);
  ...


texts: Upper bounds on higher order eigenvalues of regular graphs

texts:
Suppose $G$ is an undirected $d$-regular $n$-vertex graph for some constant $d$. Let $\lambda_k$ be the $k$-th largest eigenvalue of the normalized laplacian $L$ of $G$ (defined as $I - \frac{1}{d} A$ where $A$ is the adjacency matrix of $G$).

If the degree is constant, we can have good expanders of course but I want to say that the lower eigenvalues cannot be too close to $1$ if the degree is constant. I was wondering if there is a quantitative statement of this sort.

Are there any bounds known about how close $\lambda_k$ can be to $1$, as a function of $k$? In particular, is something of the following form known:

  ``For all $ k \ll n$,  we have $\lambda_k  \; \leq \; \left( 1 - O\left( \frac{1}{k^{0.99}}\right) \right)$'' ?

(where the constant in the order notation can hide factors of $d$).


texts: Length Extension Attack with a fixed length message

texts:
It's well known that using a hash function as message authentication is vulnerable to length extension attacks.

ie. H(key+message) is a bad idea. H(message+key), H(key+message+key) have their issues as well.

However, what if valid messages are a known length? Does length extension still apply?


texts: FPRAS on #P complete problems and self reducibility

texts:
I am quoting a phrase of Martin Dyer in his paper Approximate Counting by Dynamic Programming:

Since 0-1 knapsack is self-reducible, existence of an fpras for the problem now follows indirectly from a general result of Sinclair and Jerrum[19]

In that paper of Sinclair and Jerrum it is stated that:

It follows that, for self-reducible structures, polynomial time
randomised algorithms for counting to within factors of the form (1 +$n^{-\beta}$) are
available either for all $\beta \in R$ or for no $\beta \in R$.

Question 1: Does statement 2 mean that counting self reducible structures might have an FPRAS?

Question 2: What is the indirect method Dyer is talking about? Is it some folklore method considered well known?


texts: If $\sf{E} = \sf{NE}$. Then $\sf{NP}-{P}$ contains no sparse sets

texts:
I am reading "The Complexity Companion" by Hemaspaandra & Ogihara, I have a question about lemma 1.21.
In its proof, they suppose $L$ is some sparse language  in $\sf{NP}$ ($||L^{=n}||<p(n)$ for some polynomial) and then construct the language
\begin{align*}
L' = &\{0 \# n \# k , \text{ there are more than $k$ words of length $n$ in $L$}  \} \cup \\
&\{ 1\#n\#c \#i \#j \text{ there are $c$ words $z_1,\dots,z_c$ in $L$ of length $n$ such that the $j$-th bit of $z_i$ is 1 } \}
\end{align*}
Since $L$ is in $\sf{NP}$, then $L'$ is $\sf{NE}$. Then, one can construct a $\sf{P}$ algorithm for $L$ by checking in $L'$ each of the words $0 \# n \# 0, \dots , 0 \# n \# p(n)$ in order to obtain $c=||L^{=n}||$, and then checking if $1\#n\#c \#i \#j \in L'$ for $i \in \{1,\dots,c\} , j \in \{1,\dots,n\}$, this is a polynomial number of checks in $L'$, so (a priori) one would get that $L \in E$. But they claim that even though $L'$ is $NE$, its individual running time in this case is actually $O(\log n)$ which of course solves this problem.
Why is this? Is it because of the size of the input is made smaller when coded in binary?


texts: Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem?

texts:
In the unweighted generalized assignment problem (UGAP) we have $n$ items and $k$ knapsacks. For each item $i$ and knapsack $j$, there is a weight $w_{ij}$. Also, every knapsack has a capacity $W$. The question of UGAP is to pack the items into the knapsacks such that the weights of the items in any knapsack do not exceed $W$ and the number of all items packed is maximum.

UGAP is NP-hard. The greedy algorithm ALG that maximizes the number of items packed in each knapsack is $1-(1-1/k)^k$-approximation. I am trying to find a tight example for ALG that achieves this bound of $1-(1-1/k)^k$. I can find an example with fixed $n$ and $k$, e.g., $n=4$ and $k=2$ but I would like a generic example of arbitrary $n$ and $k$ such that ALG attains the bound of $1-(1-1/k)^k$.

This paper gives a tight example for the maximum coverage problem, which I think (if I am not mistaken) can be used to construct a tight example for the weighted generalized assignment problem. What about the UGAP?


texts: NP-Hardness of a special case of orthogonal packing problem

texts:
Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used for the container $C$.
The $D$-dimensional orthogonal packing problem (OPP-$D$) is to decide if $V$ fits into the container $C$ without overlapping. Formally speaking, the problem is to find out whether $\forall d \in \{1,...,D\}$ there exists a function $f_d:V\rightarrow \mathbb{Q}^{+}$, such that $\forall v \in V, f_d(v)+w_d(v) \leq w_d(C)$ and $\forall v_1,v_2 \in V$, $(v_1 \neq v_2)$, $[f_d(v_1),f_d(v_1)+w_d(v_1)) \cap [f_d(v_2),f_d(v_2)+w_d(v_2)) = \emptyset$.

The problem is NP-complete (see Fekete SP, Schepers J. "On higher-dimensional packing I: Modeling". Technical Report 97–288, University at zu Köln, 1997). The problem is NP-complete even for $D=2$. I am wondering, whether the orthogonal packing problem for a bounded number of types (i.e. sizes in each dimension) of items is still NP-complete or not. Till now I found a result in some paper about NP-completeness of packing squares into a square (see JOSEPH Y-T. LEUNG, TOMMY W . TAM, AND C. S. WONG, "Packing squares into a square", Journal of Parallel and Distributed Computing, Volume 10 Issue 3, Nov. 1990) which is already a restriction but I still don't know what happens when the number of types of items is bounded.

Thank you for your answer,


texts: Efficiently checking if removing a vertex yields a connected partition

texts:
Having seen the answer here, I have been looking at the algorithm suggested by Chlebikova (1996). The algorithm needs an implementation of the blockbalance algorithm which requires that one repeatedly checks if removing a vertex from on set and adding it to the other still yields a connected partition. The question is how to do this efficiently.
For completeness, here is the algorithm: Given a block (2-connected graph) $G=(V,E)$ and a vertex weight function $w$:

Order $V$ in such a way that $w(v_1) \geq w(v_2) \geq w(v_3) \geq \dots$.
Initialize $V_1 = \{v_1\}$ and $V_2 = V\setminus V_1$.
If $w(V_1) \geq w(V)/2$ then go to 3. else go to 2.
Let
$$V_0 = \left\{u \in V_2 \mid \left(V_1 \cup \{u\}, V_2 \setminus \{u\}\right) \text{ is a connected partition of }G\right\}.$$
Choose $u = \text{arg min}_{v\in V_0} w(v)$.
If $w(u) < w(V) - 2w(V_1)$ then set
$V_1 := V_1 \cup \{u\}$ and $V_2 := V_2 \setminus \{u\}$ and go to 1. else go to 3.
Return $(V_1, V_2)$.

The $V_1 \cup \{u\}$ condition in step 2. is easy to deal with as one can keep track of vertices that have neighbors in the other set. I am less sure how to efficiently check that $V_2 \setminus \{u\}$ is connected. Obviously, one can take any vertex in $V_2 \setminus \{u\}$, travers the subgraph $V_2 \setminus \{u\}$ while marking vertices and check in the end that all vertices are marked. However, this is $\mathcal O(\left|V_2 \setminus \{u\}\right|)$ and has to be done for each $u$.
Update
We cannot remove $u\in V_2$ in 2. if $u$ is an articulation point (cut vertex) of $V_2$ as then $V_2$ is no longer connected. Therefore, an implementation may look as follows:

Find $v_1 = \text{arg max}_{u \in V} w(u)$.
Initialize $V_1 = \{v_1\}$ and $V_2 = V\setminus V_1$.
Create the sets
$$\begin{align*}
     I &= \left\{u \in V_2 \mid u \text{ has an edge to any vertex } v \in V_1\right\} \\
     A &= \left\{u \in V_2 \mid u \text{ is an articulation point of }V_2\right\}.
  \end{align*}$$
If $w(V_1) \geq w(V)/2$ then go to 4. else go to 2.
Let $V_0 = I \setminus A$.
Choose $u = \text{arg min}_{v\in V_0} w(v)$.
If $w(u) < w(V) - 2w(V_1)$ then go to 3. else go to 4.
Set $V_1 := V_1 \cup \{u\}$ and $V_2 := V_2 \setminus \{u\}$.
Update $I$ and $A$ and go to 1.
Return $(V_1, V_2)$.

I figure the above is correct? We can find the articulation points in $\mathcal O(\lvert V_2\rvert)$ using the method suggested by Hopcroft and Tarjan (1973) and we do not need to do anything for every vertex $u\in I$. Perhaps we can update $A$ quicker then this? Maybe there is a smarter way to implement the algorithm?
References
Chlebíková, J. (1996). Approximating the maximally balanced connected partition problem in graphs. Information Processing Letters, 60(5), 225-230.
Hopcroft, J., & Tarjan, R. (1973). Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6), 372-378.


texts: Problems equivalent to the existence of secure cryptosystems?

texts:
What are some necessary and sufficient conditions for the existence of following?

Symmetric encryption (defined here as satisfying $\text{IND-CPA}$ and $\text{INT_CTXT}$)
Asymmetric encryption
Digital signatures
Key exchange

Ignore quantum computing for the moment.


texts: Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

texts:
My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's QF_LIA optimizer have fallen flat, which leads me to wonder if perhaps there is an alternative formulation of the problem, and a solver that might have better performance characteristics. Any advice is appreciated.

I have:

A set $V$ of Boolean variables: $V = \{v_i\}$. For a "large" instance, $|V| \approx 6,000$.
A set $P \subseteq V \times V$. For the same "large" instance, $|P| \approx 140,000$.
A set of constraints $C \subseteq V \times V$: if $(x,y) \in C$, then $x \wedge y \neq 1$. For the same "large" instance, $|C| \approx 4,000$.
A weight function $w_1 : V \mapsto \mathbb{N}$ (i.e., a total function on $V$).
A weight function $w_2 : P \mapsto \mathbb{N}$, which is mostly unrelated to $w_1$, except that $\forall v_i,v_j. w_2(v_i,v_j) \leq min(w_1(v_i),w_1(v_j))$. $w_2$ can be thought of as either:

A total function on $P$
A partial function on $V \times V$
A total function on $V \times V$, where $w_2(x,y) = 0$ if $(x,y) \notin P$.

I want: an assignment $Asg : V \mapsto \mathbb{B}$ such that:

Satisfies all constraints: $\forall (v_i,v_j) \in C$, $Asg(v_i) \wedge Asg(v_j) \neq 1$.
Maximizes $\sum_{v_i \in V} Asg(v_i)*w_1(v_i) + \sum_{(v_i,v_j) \in P} Asg(v_i)*Asg(v_j)*w_2(v_i,v_j)$

I.e., maximizes $w_1$ on $V$ and $w_2$ on $P$ simultaneously.


texts: Is this variation of TQBF still PSPACE-complete?

texts:
Deciding if a quantified boolean formula such as

$\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$

always evaluates to true is a classical PSPACE-complete problem. This can be viewed as a game between two players, with alternating moves. The first player decides the truth value of the odd-numbered variables and the second player decides the truth value of the even-numbered variables. The first player tries to make $\varphi$ false and the second player tries to make it true. Deciding who has a winning strategy is PSPACE-complete.

I am considering a similar problem with two players, one trying to make a boolean formula $\varphi$ true and the other trying to make it false. The difference is that on a move, a player can choose a variable and a truth value for it (for example, as the very first move, player one might decide to set $x_8$ to true and then in the next move, player two might decide to set $x_3$ to false). This means that the players can decide which of the variables (of those that have not yet been assigned a truth value) they want to assign a truth value, instead of having to play the game in the order $x_1 , \ldots , x_n$.

The problem is given a boolean formula $\varphi$  on $n$ variables to decide if player one (trying to make it false) or player two (trying to make it true) has a winning strategy. This problem is clearly still in PSPACE, since the game tree has linear depth.

Does it remain PSPACE complete?


texts: Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?

texts: I'm looking for a problem which belongs to $\mathsf{\Sigma^P_2}$ in general graphs but is in $\mathsf{P}$ in bounded tree width graphs, In fact I think this problems are harder than using normal dynamic programming in bounded-treewidth graphs to solve them.


texts: I'm searching for papers dealing with the problem of finding not just the shortest tour in the graph (TSP) but finding N shortest tours. Somewhat surprisingly, I didn't find any mention of it, anywhere. I might be searching under a wrong name.


texts:
There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. What I'm wondering is whether there is a reasonable direct reduction between these problems. Say, a reduction that I could explain to a friend fairly briefly without needing to describe an intermediate language like SAT.

As an example of what I'm looking for, here's a direct reduction in the reverse direction: Given G with $n$ and some $k$ (the number of colors), make a graph G' with $kn$ vertices (one per color per vertex). The vertices $v'$, $u'$ corresponding to vertices $v, u$ and colors $c, d$ respectively are adjacent if and only if $v \neq u$ and ($c \neq d$ or $vu \not \in G$). An $n$-clique in $G'$ has only one vertex per vertex in $G$, and the corresponding colors are a proper $k$-coloring of $G$. Similarly, any proper $k$-coloring of $G$ has a corresponding clique in $G'$.

Edit: To add some brief motivation, Karp's original 21 problems are proved NP-Complete by a tree of reductions where CLIQUE and Chromatic Number form the roots of major subtrees. There are some natural reductions between problems in the the CLIQUE subtree and the Chromatic Number subtree, but many of them are just as hard to find as the one I'm asking about. I'm trying to drill down on whether the structure of this tree shows some underlying structure in the other problems or if it is entirely a consequence of which reductions were found first, since there is less motivation to search for reductions between two problems when they are known to be in the same complexity class. Certainly the order had some influence, and parts of the tree can be rearranged, but can it be rearranged arbitrarily?

Edit 2: I continue to search for a direct reduction, but here is a sketch of the closest I've gotten (it should be a valid reduction, but has CIRCUIT SAT as a clear intermediary; it's somewhat subjective whether this is any better than composing two reductions as alluded to in the first paragraph).

Given $G, k$, we know that $\overline{G}$ can be $n-k+1$-colored with $k$ vertices all colored True iff $G$ has a $k$-clique. We name the original vertices of $G$ $v_1, \ldots, v_n$ and then add to $\overline G$ additional vertices: $C_{ij}$ with $1 \le i \le n$, $0 \le j \le k$. The key invariant will be that $C_{ij}$ can be colored True if and only if among vertices $\{v_1,\ldots, v_i\}$ there are at least $j$ vertices colored True. So, each $C_{i0}$ can be True. Then, $C_{ij}$ for $j > 0$ gets the color $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ where all non-true colors are treated as false. There is a $k$-clique in $G$ iff $C_{nk}$ can be colored True, so if we force that coloring, the new graph is colorable iff there was a $k$-clique in the original graph.

The AND and OR gadgets to enforce the relationships are much like the reduction from CIRCUIT SAT to 3-COLOR, but here we include a $K_{n-k+1}$ in our graph, pick vertices T, F, and Ground, and then connect all others to everything but the $v_i$s; this assure that the $C_{ij}$s and the other gadgets receive only 3 colors.

Anyway, the $\overline G$ part of this reduction feels direct, but the use of AND/OR gates is much less direct. The question remains, is there a more elegant reduction?

Edit 3: There have been a few comments about why this reduction would be hard to find. CLIQUE and k-Color are indeed quite different problems. Even without a reduction, though, an answer that details why the reduction is hard in the one direction but possible in the other would be very helpful and contribute a lot to the problem.


texts: Proving membership in W-hierarchy when problem is not parameterized by its solution size

texts:
I'm curious about the following general problem:
Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of a solution but something about the input), and we know that its solution size can be as big as $|x|$ in general.
One example is the Independent Set Problem parameterized by the max-degree of a vertex, where we ask whether there exists an independent set of size at least $s$ (which is NOT the parameter) given a graph of $n$ vertices with max-degree $d$ (which is the parameter).
(Compare this with the Clique problem with bounded degree, which is in FPT -- here, the size of a solution (clique) is also bounded because of the bounded degree, so it's different.)
(1) First of all, is this even a fair parameterized problem, when the size of a solution is only polynomially bounded by the size of an input (because $s$ can be as large as $n$)?
The reason for this first question is mainly because I can't imagine how this problem can be reduced to the weft-t weighted circuit satisfiability problem to show that it belongs to W[t] (for t >= 1), in particular, if it does belong. Specifically, a solution (= a large independent set) would have to contain $s$ vertices, but we can only set $f(d)$ input nodes to true in a hypothetical WCSAT instance we create (since $d$ is the only parameter being considered).
This makes me think that perhaps the problem I wrote above is ill-defined in the first place (or, maybe it trivially implies that it can't belong to W[t] for any fix t, but this is what I am confused about). As a follow-up if the above problem is well-defined and it actually belongs to W[t] for some constant t, I'd love to know how one can show that.
Update: After my initial post, I realized that this is (probably) para-NP-hard since the independent set problem is already NP-hard when $d = 3$, and so is the vertex coloring problem. What I meant to ask was (not specifically about the independent set problem I wrote) whether this is in general true: When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then does it imply that the parameterized problem is W[t]-hard for all t, at least?
(2) My next question is (if this question makes sense):
When we try to show that a problem that is not parameterized by the size of a solution AND its solution size (under the said parameterization) is still only polynomial in input size, what are some known techniques for doing this? Are there any known problems (assuming that my question in the previous paragraph was "NO, it's not always implied")?
I'd love to see relevant examples and papers, if anyone can recommend.
I've searched a few references, but I couldn't quite find an answer to my questions.


texts: Prove that this linear relaxation has half-integral extreme points

texts:
Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope:
(1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$
(2) For each $e \in E$, $0 \leq x_e \leq 1.$
Here $\delta(S)$ is the set of edges with exactly one endpoint in $S$.
It is known that the above polyhedron has integral extreme points when G is a bipartite graph. It is also known that, in a general graph, any extreme point of the polyhedron is half-integral - that is, it's coordinates are either integers or multiples of 1/2.
I am trying to prove the half-integrality on general graphs by using a transformation to a new bipartite graph $\tilde G$, obtained from $G$ by placing a new vertex 'in the middle' of each edge. Note that this makes $\tilde G$ a bipartite graph.
However, I'm struggling with the details. Given an extreme point of the polytope for $G$, I need to somehow create a feasible point for $\tilde G$. Then I can apply the integrality and transform it back somehow.
Can anyone help me out with how to proceed?


texts: Is feedback vertex set problem is solvable in polynomial time for some special graph

texts:
Feedback vertex set (FVS) problem is NP-complete for both undirected and directed graphs, and it is NP-complete even for bipartite graphs and tournaments.

Is there any special family of graphs other than trees for which FVS is solvable in polynomial time? I kindly request you to throw some light on it.


texts: what is the LP gap of this particular non metric facility location problem in planar graphs?

texts:
Suppose I have a facility location problem with all service costs 0 (or infinity (in particular service costs are not metric)) such that the edges $ij$ for which facility $i$ can service client $j$ with cost 0 (together with the facilities and clients)  forms a planar graph.
What is the maximum integrality gap of such an LP?
This is exactly set cover with the additional constraint that the set element incidence graph (  that is a graph with nodes  $v_S$ for every set $S$ and nodes $v_e$ for every element $e$ and the edges $v_S v_e$ for elements $e$ and sets $S$ for which $e \in S$)
is planar.
What is the LP gap if the graph is not planar but say fixed genus/minor free etc?
Also, does this problem have a name like planar/bounded genus set cover or something?


texts: If $A$ and $B$ are NP-complete problems, is there a bijective function $f$ (computable in polynomial time) such that $w\in A$ iff $f(w)\in B$?


texts: What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?

texts:
If we have some string $x$ and a permutation $g$ which preserves the bits of $x$, we can store the value of $x$ on each of its $g$-orbits as well as $g$ instead of storing $x$ and we can reconstruct $x$ using this information in the obvious way.

Let $M_x$ be the set of Turing machines which print $x$ on their tape given any input, let $enc(M)$ be some reasonable encoding of Turing machines, and let $\langle g \rangle$ be the subgroup generated by $g$. Given $x \in \{0, 1\}^n$, we define

$K(x) = min_{M \in M_x} |enc(M)|$,

$Aut(x) = \{ g \in S_n \mid \forall i \in [n], x_i = x_{i^g} \}$,

$orb(g) = |\{ i^{\langle g \rangle} \mid i \in [n] \}|$,

and, for $g \in Aut(x)$, $b_{g,i}(x) = $ the value of $x$ on the $i$th orbit of $g$, ordering the orbits by the ordering already present on their lowest elements.

We extend $enc$ to $g \in S_n$ such that $enc(g)$ is the smallest encoding of a Turing machine which outputs $g$ in cycle notation on any input.

Finally, we define $GC(x) = min_{g \in Aut(G)} | b_{g, 1} ... b_{g, orb(g)} enc(g) |$.

I'm curious about the relationship between $K$ and $GC$. In particular, I suspect there exists some family of strings $x_{i \in \mathbb{N}}$ such that $K(x_i) \in o(GC(x_i))$ as functions of $i$, but I have no clue how to prove that or really why I suspect it, other than the fact that permutations just seem much less able to be clever than general Turing machines. The other natural thing to suspect would be that somehow these two things are measuring roughly the same thing and somehow this symmetry method is "complete" for the Kolmogorov sort of compression.


texts: Deciding satisfiability and non-validity

texts:
For propositional logic, a decision procedure for satisfiability can be turned
into a decision procedure for non-validity by giving it the negated
version of a formula.

Does this hold for all logics for which satisfiability is decidable?

More precisely:

Let $F$ be a set of well-formed formulas in some logic $L$. $F$ is closed under
negation, i.e. $f \in F \implies \neg f \in F$. Let $F'$ be a subset of $F$ such that
satisfiability of $F'$ is decidable. Let $F'' = \{ \neg f | f \in F' \}$. Is there a logic
$L$ for which satisfiability is decidable for $F'$ but not for $F''$?


texts: Are Turing machines still useful as model of computation?

texts:
Often when I hear "Turing machine," my mind's eye pictures a quaint infinite ticker-tape with a small little machine writing and erasing $0$'s and $1$'s.

But when I'm forced to think about a Turing machine as a tuple of states, blank symbols, alphabet symbols, transition functions, etc., my mind often glosses over.

I live in the 21st century; thinking about computation is so second-nature to me now that I struggle with keeping my mind on such a pleasantly old-fashioned infinite ticker tape.  I know pretty well how the computer on which I'm writing this operates, clearly not at the details of the machine code but at a level of abstraction that I feel comfortable with.  I also never liked how the alphabet has, basically, three symbols $(0,1,blank)$.  Why do we even need the $blank$?

Turing's work in the 30's was baller of course, and there are some well-deserved accolades when the new "smallest universal Turing machine" or "largest Busy-Beaver" are announced.  People also have a game of writing esoteric programming languages based on small Turing machines.

  But is there a good reason to use the ticker-tape Turing machine for a model of computation, now, in the 21st century?  Are there reasons for the formalism still being "worth it?"  Or can we just say a Universal Turing Machine as in a smart-phone?

Of course Hamilton's etchings on Broom Bridge marked a turning point in the history of mathematics, but I've read that quaternions per se were oversold by the end of the 19th century.


texts: Which convex polytopes have volumes of polynomial bit-length?

texts:
A convex polytope is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The volume computation problem for convex polytopes asks, given such a polytope $P$, what is its volume $V(P)$, expressed as a rational number. The size of the input $||P||$ is accounted by writing out the inequalities, with rational numbers written as a pair of numerator and denominator (as binary numbers), and the size of the output $||V(P)||$ is defined in the same way.

It was shown by Lawrence in this paper that there are convex polytopes $P$ for which $||V(P)||$ is exponential in $||P||$, implying, e.g., that the volume computation problem is not in FP$^{\#\mathrm{P}}$. My question is: are there known classes of convex polytopes for which $||V(P)||$ is polynomial in $P$? I know that this is the case, e.g., of simplices; are there other cases?


texts: What is the tradeoff between population size and the number of generations in genetic algorithms

texts:
Genetic algorithms evolve in fewer generations with a larger population, but also take longer to compute a generation. Are there some guide lines for balancing those two factors, in order to arrive at a viable solution as soon as possible?

Also, is this the best place for the question?


texts:
I am interested in examples of constructions in the complexity theory which are better than a random constructions.

The only one example of such construction which I know is in the field of error-correcting codes. Algebraic-geometry codes are better in some range of parameters than a random codes.

One can easily to construct such artificial examples.
I am interested in the examples like algebraic geometry codes, where it is easy make a random construction and it is not obvious how to do better.


texts: VC generalization bound extended to other types of target functions

texts: In Y. S. Abu-Mostafa's book "Learning from Data", he mentions on page 55 after deriving the VC generalization bound for a binary target function that "it can be extended to other types of target functions". I have looked online for quite a bit but it's really not clear to me how that should work. I'm particularly interested in continuous target functions, where hypothesis $h \in \mathcal{H}$ maps input space $\mathcal{X}$ to $\mathbb{R}^N$, rather than classifications. But I don't see how shattering could be adapted for these target functions.


texts: Communication complexity protocols depending on inputs

texts:
Classical communication complexity requires one protocol (binary tree with edges labeled by bits Alice and Bob send) to solve the problem for every pair of inputs. What if we allow Alice and Bob to choose protocols separately depending on the input they have?

Consider the following communication model. Alice and Bob are trying to compute $f (x,y) $, $x $ is given to Alice, $y $ is given to Bob. At the begining of communication Alice chooses protocol $P_A =P_A (x) $, Bob chooses protocol  $P_B=P_B (y) $. They follow their protocols as in the classical case. They compute $f (x,y) $ if at the end they both come to leaves labeled with $f (x,y) $.

As $P_A $ is not necessary equal to $P_B $ at some round they may decide (according to their protocols) to either both send a bit or both wait for a bit - in these cases we say that the communication is invalid but Alice and Bob do not know about it: if they both send a bit they don't receive anything (as in half-duplex channels), if they both wait for a bit they receive "some" bit (uninitialized variable, potentially adversarial).

What is the relation to classical communication complexity? Trivially this model is at least as powerful as a classical one: Alice and Bob can use the same protocol for all inputs. Is it strictly more powerful? Is there any studies of this model? (I think I've seen something similar but I don't remember when and where.)


texts:
I'm currently trying to implement this paper:

Bouckaert, Remco R., A probabilistic line breaking algorithm, Gedeon, Tamás D. (ed.) et al., AI 2003: Advances in Artificial Intelligence. 16th Australian conference on AI, Perth, Australia, December 3--5, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20646-9/pbk). Lecture Notes in Computer Science 2903. Lecture Notes in Artificial Intelligence, 390-401 (2003). ZBL1205.68488.

Based on a bayesian network, the paper stays unclear about how to ultimately use its content ("straightforward inference").  But after a lot of researches (I have no background in that field), I think I can apply Viterbi algorithm to get the expected result. I will give here a description of my problem but as I might have misunderstood some things, the non biased description of the algorithm is available Section 3.1 of the paper.

We try to find a set of breakpoint $S$.

The test case is "aaa bb cc ddddd" with text width 6 which should result in:

aaa
bb cc
ddddd

which is a set of breakpoints $S = \{0,1,3,(4?)\}$. Just for information, for the test, I use o-=14 and o+=3 to get more manageable results (ref. paper).

We try to find the boolean value of $i \in S$ for each word (character in the paper). We start with the beginning of the paragraph with nlw0=0 (nwli is the width of a line from previous breakpoint) and $0 \in S$.

First take next token c1 = "aaa" with width cw1 = 3.

So, trying to use the Viterbi algorithm, I explore both possibilities of $i \in S$ and $i \not\in S$. It leaves us with two paths, set of breakpoints with nlwi = 3 (Pa is described page 7):

{0,1} with Pa(0, -6)≅0.8713
and {0} with Pa = 1

No choices here to make so it's seems okay. But I'm not sure if I even use Pa the right way...

Then I tried a few things which all ended wrong. It more or less looked like this:

Take next token cw2, try all possibilities and keep only the best ones for 2 ∈ S and 2 ∉ S.

It gives use 4 different sets:

{0,2} with Pa(3, -3) 4.45 product previous Pa. Total≅ 4.45
{0,1,2} with Pa(3, -3)≅ 4.45 product previous Pa. Total≅ 3.877
{0} Pa=1. Total=1
{0,1} Pa=1. Total≅ 0.8713

The best two sets we keep are {0,2} and {0} which already discards the expected result. Anyway I usually end up with no breakups at all...

So I'm probably missing something important. There are a few things I don't get in the paper either:

What is node bi used for?
and why is Pa described as the "acceptability of breaking-up up to ci instead of ci-1?


texts:
I know that for an AVL tree of N nodes, the depth of the tree is bounded by
$$ \log_2(N + 1) -1 \leq height \leq c \log_2(N + 2) + b$$
where $c,b$ are taken from the golden ratio linked to the worst case of the tree, i.e. $c = 1/ \log_2(\varphi)$ and $b = c/2 \log_2(5) - 3$.
I am interested in reducing this bound (up to some probability) granted that the elements inserted in the trees are generated randomly, with entropy $H$. In my application, I have exactly $2^k$ elements of size $2^l$ to be inserted, where $k\ll l$.
I know that asymptotically a randomly generated tree will have depth very close to the theoretical lower bound, and I could find some experimental results reducing this upper bound - I can refer to Data Structures and Algorithms by Drozdek or The Art of Computer Programming by Knuth (which itself refers to the work of C. C. Foster) - but I am looking for a more concrete answer with error probability rather than only asymptotic arguments or experimental results. Would you happen to have any material support discussing this approach, of random or pseudo-random insertions in a sorted tree?
Note: For those interested, Knuth suggests an average of  $1.01 \log(N) + 0.1$ comparisons for the $N$th insertion in an AVL tree with random elements, except for small $N$. From my own experiments, it seems that a close upper bound would be $1.2 \log(N) + 0.1$, though I could not test it over $2^{24}$ due to insufficient memory.


texts: Difficulty of Getting into Top Graduate Program in TCS

texts:
I'm currently a sophomore interested in TCS. Recently I've been somewhat bothered by the difficulty of getting into PhD programs in the future since the selection is indeed very competitive.

I looked through the webpages of some top CS school and found that their current grad students mostly also come from top undergrad schools and many graduated summa cum laude, i.e. with highest honors(top GPA, I guess?).

I've also been advised by a PhD student that by the time of application, I'd better figure out a specific area in theory(algorithms, complexity, crypto, etc) to write in my PS. Being interested in a wide range of topics would put me at disadvantage.

Though I'm at a top 5 university, I started learning CS only after getting into college. I fell in love with theory right away but I felt really left behind by many around me. I have a relatively good GPA, but not stellar enough. I've also been doing research in a few diffenrent topics but haven't published a paper yet. And currently I'm still widely interested in graph theory, complexity, cryptography and even quantum computing.

I know I still have two years to go. But sometimes I felt really pushed by the scenario in academia nowadays. I believe that many students are in the same boat as I am.

I wonder roughly what is the difficulty of getting into top graduate programs in theoretical cs(MIT,Berkeley,Stanford,CMU,Princeton etc.)nowadays? Does GPA really play no role once you have reached a "bar"(like 3.7/4), as many said?
Do I have to decide on a specific area just after 3 years of undergrad studies?

And any other advice related to my situation(research, application, anything) would be appreciated.


texts: Lower bounds for linear satisfiability problem

texts:
In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses infinitesimals and Tarski's transfer principle.

Could someone explain the intuition behind the route taken to prove this bound ? What is the difficulty in coming up with a direct proof like this: "Given a decision tree which takes real numbers, here's how we can construct an adversarial input" ?