texts: Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?

texts:
Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm?

Are known any (classical) approximation algorithms for an $\sf{NP\text{-}complete}$ problem that uses Factoring as oracle?


texts: Hardness of Minimizing Submodular Functions with Cardinality Constraints

texts:
I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ).

In this introduction, it says

" A submodular set function can be minimized in strongly polynomial time. Remark: • minimizing a submodular function f, subject to a cardinality constraint, such as |A| = b, or |A| ≥ b, or |A| ≤ b are NP-hard when f is a cut function ".

In the remark, it says the problem is NP-hard if 1) there is a cardinality constraint and 2) f is a cut function.

What if only one of the 2 constraints holds, i.e. f is not a cut function but there is a cardinality constraint? Is this problem of minimizing f(A) still an NP-hard problem?


texts: Integer factorization using polynomial whose roots are prime factors

texts:
Let $n$ be a square-free positive integer, let $n=p_{1}p_{2}\ldots p_{k}$
be the prime factorization of $n$ into $k$ distinct primes $p_{i}$.
For such $n$, define $F_{n}(x)\triangleq\prod_{i=1}^{k}(x-p_{i})$.
That is, $F_{n}(x)\in\mathbb{Z}[x]$ is the monic polynomial whose
roots are distinct prime factors of $n$. If we know $F_{n}(x)$,
we can obviously factorize $n$ in polynomial time. Now suppose that
we are given some partial information on $F_{n}(x)$ instead of complete
$F_{n}(x)$. We would like to know

  What kind of partial information on $F_{n}(x)$ would allow factorization
  of $n$ in polynomial time?

For example, it was demonstrated in SUMS OF DIVISORS, PERFECT NUMBERS
AND FACTORING that knowing just the sum of absolute values of coefficients
of $F_{n}(x)$ is enough to factorize $n$. What other partial information
on $F_{n}(x)$ allows factorization of $n$ in polynomial time?

After seeing comments, I am adding for kind of "partial information" we should be looking for.  As pointed out by @joro, knowing $F_n(1)$ or $F_n(-1)$ allows factorization of $n$. First question is that, does knowing value of $F_n(x)$ at any non-zero integer allow factorization of $n$? Second question is that, does knowing only constant many coefficients of $F_n(x)$ allow factorization of $n$?


texts: What requirements should a denotational semantics for a programming language satisfy to be correct?

texts:
We have a programming language and its denotational semantic,
like Tony Hoare's CSP with its syntax and denotational semantic
e.g. stable failure and UTP.

We want to extend the language (its syntax and semantics) by
adding new operators to the language.
After given an informal definition for each new operator,
we want to provide a denotational semantic for the extended language.

We have been told that

the denotational semantic must be a domain,
the denotational semantic must distinguish what your language want to distinguish intuitively,
the denotational semantic must be consistent with its operational semantic or algebraic semantic.

What requirements should our denotational semantics for the extended language satisfy to be correct?
Are there any criteria to distinguish between correct and incorrect denotational semantic for a programming language?


texts: Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?

texts:
Suppose I have some set of points in d-dimensional space, each with some mass. Our problem size will be the number of points in this set. After some roughly (within polylog factors) linear initialisation using roughly linear storage, I would like to know the total mass of all the points that fall within various queried subspaces in polylogarithmic time.

If our queries are all axis-parallel boxes, ie sets of points defined by a cartesian product of intervals on each axis, we can apply some standard, easily-googleable range searching methods and achieve this without too much difficulty.

If our queries are all simplices, there are currently no known methods which satisfy both these criteria, either we use polynomial space and initialisation to achieve a polylog query time, or we use roughly linear space and have sublinear, but not logarithmic, query times.

What if our queries are all boxes, but each is rotated in some way? We can define such a box in a few ways, but for the sake of concreteness suppose I will give you a sequence of sets of hyperplanes, each with exactly one parallel partner, intersecting all others orthogonally, defining some boxey subspace between them. Is there a way of solving this slightly simpler problem with roughly linear initialisation and storage but polylogarithmic queries? Alternatively, if I were to give you a method of doing this, would you be able to use it to solve the simplex case of this problem in a similarly easy way?


texts: Non-boolean monotone planar circuit value problem

texts:
It is known that monotone planar boolean circuits have a NC circuit value problem (in fact, much more is known).

What about non-boolean monotone planar circuits?

Precisely, take $Q=\{0,...,n-1\}$ and any family of monotone functions $f_i:Q^2\rightarrow Q$ and consider planar circuits where gates are chosen among the $f_i$. What is known for such circuits?


texts: Sampling a uniformly random satisfying assignment

texts:
Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists).

Clearly this problem is NP-hard. My question is whether or not this problem is also "NP-easy":

Question: Does there exist an algorithm that solves the above problem in time polynomial in $n$ and the circuit size of $\phi$ given access to a SAT oracle?

Alternatively, is there a polynomial-time algorithm assuming NP=P?

Clearly having access to a #SAT oracle suffices, so the complexity lies somewhere between NP and #P.

I feel like this should have been studied before, but I can't find an answer on Google.

I know how to solve the problem approximately (i.e. generate a satisfying assignment that is statistically close to uniform) using a variant of the Valiant-Vazirani Theorem and/or approximate counting, but getting exactly uniform seems to be a different problem.


texts: Oracle relative to which MA does not have a complete problem?

texts:
Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called Arthur-Merlin games. The game is played by powerful but untrustworthy wizard Merlin (the prover), and the king Arthur (the verifier), who might flip coins but otherwise his power is polynomially limited. The players exchange messages in turn, and the goal for Merlin is to convince mistrustful Arthur to accept the input string.

$\mathsf{MA}$ is the set of problems that can be decided by one round Arthur-Merlin games with Merlin plays first. First Merlin sends Arthur the "proof", and then Arthur chooses random coins and  tries to verify the "proof" sent by Merlin.

My question is:

  Is there an oracle relative to which $\mathsf{MA}$ does not have a complete problem?

It is very likely this problem has been solved already since analogous results exist for $\mathsf{BPP}$ and $\mathsf{ZPP}$. But I couldn't find any reference for it.

Note that an oracle relative to which $\mathsf{BPP}$ does not have a complete problem can be found in

Juris Hartmanis and  Lane Hemachandra, Complexity Classes without Machines: On Complete Languages for UP, Theor. Comput. Sci. 58: 129-142 (1988).

Analogous result for $\mathsf{ZPP}$ can be found in

Daniel P. Bovet, Pierluigi Crescenzi and Riccardo Silvestri, A Uniform Approach to Define Complexity Classes, Theoretical Computer Science 104(2): 263-283 (1992).

But I couldn't find a reference for $\mathsf{RP}$ either. This leads to my "side" question:

  Is there an oracle relative to which $\mathsf{RP}$ does not have a complete problem?

I would really appreciate if you can point me to the right papers.


texts:
It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a
"Bernoulli" random variable $Y\in\{-1,1\}$ with $|\mathbb{E}[Y]| = \Theta(|\mu|)$. (Basically, just take $Y=\operatorname{sign}(X)$.)
Is it possible to do the converse (even allowing extra randomness, independent of the sample)? That is:

Given one realization of some random variable $Y\in\{-1,1\}$ with (unknown) $\mathbb{E}[Y] = \mu$, output $X\sim \mathcal{N}(\nu,1)$ s.t. $|\nu| = \Theta(|\mu|)$.

I conjecture that to be impossible (I have some mild contrived evidence), but I don't really see how one would go about proving that.


texts: Name of graph partition that balances edges between sets with edges remaining within sets

texts:
Is there a common name for this problem:

Let G=(V, E) be an undirected graph.  Partition V into sets $S_1$, $S_2$, ..., $S_k$, such that (the number of edges between sets) + (the number of "non"-edges within sets) is minimized.

To be clear: define "extra edges" to be the set of edges with endpoints in different sets; define "missing edges" to be the set of edges in the complement of G with endpoints in the same set.  The goal is to find a partition that minimizes the sum of "extra edges" and "missing edges".

(The sets need not be of similar size.)


texts: Are provable quantum speed-ups possible for classes larger than NP?

texts:
In the oracle query model quantum computers can provably achieve a quadratic speed-up over any classical randomized computer [Grover, BBBV].

Are similar speed-ups provably possible for higher levels of the polynomial hiearchy or even PSPACE or EXP? (i.e. for classes that require single-exponentially many queries classically.)

Note, that I'm not asking for superpolynomial speed-ups. Quadratic is fine. Can I get quadratic speed-up e.g. for finding a satisfying assignment to some quantified formular $\forall x \exists y\; \varphi(x,y)$?

Note that for larger classes "scaling Grover up an exponential" to NEXP gives $2^{2^n}$ vs. $2^{2^{n-1}}$ queries.


texts: Facility location problem with a cost function

texts:
I'm struggling with a facility location problem.

In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from them and create districts, such that no city in a district is farther from the center than a predefined distance parameter. This is a set covering problem that can be formulated as a binary integer program which I can solve with MATLAB's bintprog(). The solution vector gives me the list of cities that are selected as centers, after which I can establish districts by assigning each city to the closest center, and that's OK.

But I would also like to solve a specialized version of the problem, and this is where it gets ugly and I get stuck:

Let's assume we also know the population of each city and want to minimize the amount  of people who have to commute to the district center, and also the distance they have to do. So we would like to prefer solutions where the cost

$$
C =\sum_{v \in V}P_v \times d_{vc}
$$

is minimal ($v \in V$ are the cities in the district, $P_v$ is the population of $v$, and $d_{vc}$ is the distance to the center).

My problem is that I cannot think of a way to incorporate these constraints into the binary integer program, because computing these costs require the districts to be already established, which right now only happens after bintprog() has returned.

I suspect this problem might not even be formulated as a linear program at all, but I'm yet to find another way to solve it, so any help would be much appreciated. Thanks.


texts:
The following result is supposedly known. However, the proofs I am able to find all prove a weaker result with an extra log factor. Where can I find the proof of the tight bound?

  Theorem. Let $\mathcal{H}$ be a class of functions $h : \mathcal{X} \to \{-1,+1\}$ with VC dimension $d<\infty$. Let $\mathcal{D}$ be a distribution on $\mathcal{X} \times \{-1,1\}$ and let $(X_1,Y_1), \cdots, (X_n,Y_n)$ be independent samples from $\mathcal{D}$. Let $\varepsilon,\delta>0$.

  If $n \geq O\left(\frac{d+\log(1/\delta)}{\varepsilon^2}\right)$, then $$\mathbb{P}\left[\forall h \in \mathcal{H} ~~\left|\frac{1}{n} \sum_{i=1}^n h(X_i) \cdot Y_i - \underset{(X_*,Y_*) \leftarrow \mathcal{D}}{\mathbb{E}}[h(X_*) \cdot Y_*]\right|\le\varepsilon\right] \ge 1-\delta.$$

The (well-known) connection to agnostic learning is as follows. $\mathcal{H}$ is a class of "hypotheses" and $\mathcal{D}$ is some unknown ground truth distribution on attributes $X \in \mathcal{X}$ and labels $Y \in \{-1,+1\}$. You see $n$ samples from $\mathcal{D}$ and want to be sure that any hypothesis that labels the sample well (i.e. $\frac{1}{n} \sum_{i=1}^n h(X_i) \cdot Y_i$ is large) also labels the ground truth well (i.e. $\underset{(X_*,Y_*) \leftarrow \mathcal{D}}{\mathbb{E}}[h(X_*) \cdot Y_*]$ is also large). The above theorem says that if $n \geq O\left(\frac{\mathsf{VCdim}(\mathcal{H})+\log(1/\delta)}{\varepsilon^2}\right)$ then with probability $\ge 1-\delta$, for all hypotheses the error on the sample and the error on the distribution are within $\varepsilon$.

The proofs that I can find relating VC dimension to uniform convergence all include an extra log factor. That is, they prove a bound of $n \geq O\left(\frac{\mathsf{VCdim}(\mathcal{H}) \cdot \log(\mathsf{VCdim}(\mathcal{H})/\varepsilon)+\log(1/\delta)}{\varepsilon^2}\right)$. This is achieved by applying the Perles-Sauer-Shelah lemma and a clever union bound. For the simple case where $\mathsf{VCdim}(\mathcal{H})=\log|\mathcal{H}|$, this just follows from Hoeffding's inequality and a union bound.

Unfortunately, I haven't been able to find a proof of the tight and general result, despite looking for several hours. Surely someone can point me to the right source!


texts: What is the difference between LTL connectives X and O?

texts:
I have seen two different sets of connectives for LTL (see the picture):

I have learned LTL by the connectives of the first column ($X, F, G,$ ...). The table (from Wikipedia) says that the connectives in the second column have the same meaning as the connectives of the first column and are just different symbols. But recently I read a paper and saw this equivalence: $\bigcirc\varphi\equiv\bot\mathcal{U}\varphi$.

I know that $X\varphi\equiv\bot U\varphi$ does not hold in LTL (because $\bot$ does not hold in any state, so $\bot U\varphi$ can be true only if $\varphi$ is true in the current state and no other state in the future. But this is different from $X\varphi$ which says $\varphi$ is true in the next state). But that table says $X$ and $\bigcirc$, and $U$ and $\mathcal{U}$ have the same meaning.

I am confused, any help would be appreciated.


texts: Great algorithms, machine learning and no linear algebra

texts:
I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of the currently most interesting/greatest algorithmic results in machine learning. The potentially tricky constraint is that the students will not have any particular previous knowledge of linear algebra or the other main topics in machine learning.

This is really to excite them about the topic and to let them know that ML is a potentially exciting research area for algorithms experts.

EDIT: This is a final year undergraduate course (as we don't have graduate courses in the UK in the main).  They will have done at least one basic algorithms course beforehand and presumably done well in it to have chosen the advanced follow up course. The current syllabus of the advanced course has topics such as perfect hashing, Bloom filters, van Emde Boas trees, linear prog., approx. algorithms for NP-hard problems etc.  I don't intend to spend more than one lecture exclusively on ML but if something is really relevant to both an algorithms course and an ML one then of course it could also be included.


texts: Oracular separations between poly- and log-depth quantum circuits

texts:
The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory.

  Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of any quantum algorithm be compressed to $\mathrm{polylog}(n)$ depth, provided we're
  willing to do polynomial-time classical postprocessing? (This is known
  to be true for Shor's algorithm.) If so, building a general-purpose
  quantum computer would be much easier than is generally believed!
  Incidentally, it's not hard to give an oracle separation between $\mathsf{BQP}$
  and $\mathsf{BPP}^{\mathsf{BQNC}}$, but the question is whether there's any concrete function "instantiating" such an oracle.

It has been conjectured by Jozsa that the answer to the question is yes in the ''measurement-based model of quantum computation": where local measurements, adaptive local gates and efficient classical post-processing are allowed. See also this related post.

Question. I would like to know about the currently-known oracular separations between this classes (or, at least, the oracle separation to which  Aaronson is referring to).


texts: Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?

texts:
Question

I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete.

Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$.

Where $\bar{x}=(x_1,x_2,\dots x_n)$ and $\bar{y}=(y_1,y_2,\dots y_n)$ are tuples of non-negative integers.

How long does it take to "decide" whether a given $(\bar{w},r)$  is in the "language" $L$? This is obviously in NP but is it NP-Complete remains to be concluded. Is this language NP-Complete?

Motivations

This problem comes out of my own explorations. I have been exploring solutions on hyperspheres and this is a natural generalization of a hypersphere.
Note that $(<2,2,2,2,2,2>, 296675)\in L$ because by Lagrange we know that there exists some $(x_1,x_2,x_3,x_4,x_5,x_6)$ which satisfies
$x_1^2+x_2^2+x_3^2+x_4^2+x_5^2+x_6^2=296675$. An $n>3$ dimensional hypersphere with radius $\sqrt{r}$, where $r$ is a whole number centered at the origin can always be satisfied by some integer coordinates (Lagrange's sum of 4 squares theorem). This makes the "decision" problem easy. There IS some solution though it might be hard to find.

But what about
$x_1^2+x_2^3+x_3^4+x_4^5+x_5^6+x_6^7=296675$?

"Is there a solution to the equation above?" is the same as "Is $(<2,3,4,5,6,7>,296675) \in L$?" in my notation above.

This may be a computationally tricky problem to solve. I know of no guarantee that there must be some $(x_1,x_2,x_3,x_4,x_5,x_6)$ which satisfies the equation. On the otherhand, given an "instance" $(x_1,x_2,x_3,x_4,x_5,x_6)=(1,2,3,4,5,6)$ this problem is easy to verify. "Hard to solve but easy to verify" is a hallmark of NP problems.


texts: Inefficient pseudorandom distribution using a few random bits

texts:
In these slides, it is mentioned that for a class of functions $\mathcal{C}$, a pseudorandom generator is a distribution $D$ such that

$D$ fools $\mathcal{C}$.
$D$ is efficiently samplable.
$D$ is sampled using a few random bits.

Then if you want to achieve $(1)$ and $(2)$, let $D = U$, where $U$ is the uniform distribution. This is clear to me. It's mentioned further that for $(1)$ and $(3)$: $\forall \mathcal{C}$ $\exists$ inefficiently samplable $D$ using $O(\log \log |\mathcal{C}|)$ random bits. Could someone explain how to construct such an inefficient $D$?


texts:
I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations of DFA, NFA, Mealy machines, Moore machines, context-free grammars, and even simple quantum systems. I have not found a good source for representing a Turing Machine as a coalgebra.

Any sources/thoughts?

Thanks!


texts: Would an NP-complete public key cryptosystem imply NP=co-NP?

texts:
Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP?  My specialty is definitely not theoretical computer science, so this is somewhat of a mystery to me.

Any useful cryptosystem has to be in NP or co-NP.  Using digital signatures as an example, you obviously need signature verification to be in P.  Similarly, key generation needs to be in P, or good luck generating keys.

To say that a signature system is an NP-complete problem would really mean that the decision problem of determining whether the signature for an arbitrary message is less than some integer is NP-hard.  That definition would imply that deriving whether the private key is less than some integer is also NP-hard.  For both these problems, the certificate is the full answer, which shows membership in NP (and NP-complete).

But then the complement to these two problems, determining whether their full answer is not less than some number, is a simple reduction to the "less than" version.  Does this mean that the existence of such an NP-complete signature system implies NP = co-NP?

My argument above is highly informal.  For example, checking whether an alleged private key in fact matches a given public key may not be straightforward and possibly not in P.  (It is definitely in BPP, though: try signing random messages.)  Also, many public-key signature systems may have multiple valid signatures (DSA, ECDSA) or multiple matching private keys (RSA).  These things throw wrenches into the works.


texts: Regular languages under change of encoding

texts:
Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$.
Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other encoding (say unary, or, decimal) also form a regular language ?

Formally, is it the case that the language $L' = \{w | w \in 1^*, \exists w' \in L \text{ such that the unary encoding of } w' \text{ is } w \}$ also regular?

What happens when the base is shifted to a lower number? For example can we also say anything about the following language:
$L'' = \{w | w \in \{0,1,2\}^*, \exists w' \in L \text{ such that the ternary encoding of } w' \text{ is } w \}$


texts:
Let C={Cn} be a family of uniform boolean circuits, whose size and depth are bounded by functions s(n) and d(n).

What is the upper bound on the running time of a Turing machine M that evaluates C? How tight is this upper bound?


texts: Boolean functions with high query complexity for PAC learning

texts:
The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier weights are concentrated on some modes can be PAC learnt in polynomial time. Also it trivially follows that in $2^n$ queries one can learn any Boolean function on the $n-$Hamming cube.

My question is two fold,

For what concept classes do we know of high ($2^n$?) query lowerbound for PAC learning? If the proof is short then it would be very helpful if you could kindly type it in or give a reference.
For Boolean functions whose Fourier spectrum seems very evenly spread out over the modes it seems that it should be hard to learn them in a few queries. Is this intuition right and if yes then what is the most quantitative theorem we know of which captures this?

I am interchangeably using the words "query complexity" and "running time of the learning algorithm". I hope this is okay. If not then it would be helpful if you could point out the subtlety that I am missing.


texts: Delegating all of the work to the prover in $\mathcal{MA}$ protocols

texts:
An $\mathcal{MA}$ communication complexity protocol is communication complexity protocol that starts with an omniscient prover that sends a proof (that depends on the the specific input of the players, but not on their random bits) to both players. The players then communicate with each other, in order to verify the proof (for more details, see: On Arthur Merlin Games in Communication Complexity, by Hartmut Klauck).

The are quite a few lower bounds (e.g., On the power of quantum proof, by Ran Raz and Amir Shplika) of the following form: Suppose we have a communication complexity problem $\mathcal{P}$ with a tight bound of $\Theta(T(n))$ on its communication complexity (for some function $T$). There exists a lower bound that shows that every $\mathcal{MA}$ communication complexity protocol that communicates $c$ bits and uses a proof of size $p$, must satisfy $c \cdot p = \Omega(T(n))$. So one can think of it as a tradeoff between the work that prover has to do, and the work that the verifiers have to do.

Moreover, it seems that for every communication complexity problem that I know of (with a tight bound of $\Theta(T(n))$ on its communication complexity), there exists a protocol wherein the prover sends a proof of size $\tilde O(T(n))$, and the verifiers only uses $\tilde O(1)$ bits of communication (cf. the two papers I mentioned above). Thus, in a sense, all of the work has been delegated to the prover (achieving the extreme case of the aforementioned lower bounds).

Is there a result that shows that a verifier-"heavy" protocol implies the existence of a prover-"heavy" protocol? Is there a counter example? What about other models (such as $\mathcal{MA}$ decision trees/query complexity) wherein our understanding of the behaviour of $\mathcal{MA}$ protocols is deeper?


texts: Proof of convergence of alternative minimization/maximization

texts:
Given a problem

\begin{equation}
\max_{x\in X} \min_{y \in Y}  f(x,y)
\end{equation}

where $f$ is strongly convex in $Y$ and strongly concave in $X$

How to show that the following iterative processes will finally converge and how is the speed?

\begin{equation}
x_k=\arg\max_{x \in X} f(x,y_{k-1})
\end{equation}

\begin{equation}
y_k=\arg\min_{y \in Y} f(x_{k-1},y)
\end{equation}

UPDATE 1: The problem is being rewritten in order to distinguish from another question which looks similar.

UPDATE 2: The function $f$ is now strongly convex in $Y$ and strongly concave in $X$


texts: Is topological conventional computation possible?

texts:
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\mathrm{Id}_{X})\circ(\mathrm{Id}_{X}\times f)\circ(f\times \mathrm{Id}_{X})=(\mathrm{Id}_{X}\times f)\circ (f\times \mathrm{Id}_{X})\circ(\mathrm{Id}_{X}\times f).$$

The positive braid monoid $B_{n}^{+}$ is the monoid presented with generators
$\sigma_{1},\dots,\sigma_{n-1}$ and relations
$\sigma_{i}\sigma_{i+1}\sigma_{i}=\sigma_{i+1}\sigma_{i}\sigma_{i+1}$ and
$\sigma_{i}\sigma_{j}=\sigma_{j}\sigma_{i}$ whenever $|i-j|>1$. A positive braid $b\in B_{n}^{+}$ is said to be simple if it cannot be written in the form $b=b_{0}\sigma_{i}^{2}b_{1}$ for some $i\in\{1,\dots,n-1\}$.

If $f$ satisfies the Yang-Baxter equation, then define a monoid action
$\pi_{f,n}:X^{n}\times B_{n}\rightarrow X^{n}$ by letting
$$\pi_{f,n}((x_{1},\dots,x_{n}),\sigma_{i})=(x_{1},\dots,x_{i-1},f(x_{i},x_{i+1}),x_{i+2},\dots,x_{n}).$$

Does there exist

a function $f:X^{2}\rightarrow X^{2}$ with satisfying the Yang-Baxter equation where $X$ is finite,
some natural number $c$, and
for $m,n$ are natural numbers, functions
$i_{n,m}:\{0,1\}^{n}\rightarrow X^{m},j_{m,n}:X^{m}\rightarrow\{0,1\}^{n}$ such that the maps $(n,m,r)\mapsto i_{n,m}(r),(m,n,x)\mapsto j_{m,n}(x)$ are computable in polynomial time such that

if $C$ is a circuit of width $w$ and depth $d$ that computes a function $F_{C}:\{0,1\}^{m}\rightarrow\{0,1\}^{n}$, then there is some $v\leq w\cdot c$ and positive braid $b\in B_{v}$ where
$$F_{C}(x_{1},\dots,x_{m})=j_{v,n}(\pi_{f,n}(i_{m,v}(x_{1},\dots,x_{m}),b)))$$ for all inputs $(x_{1},...,x_{m})\in\{0,1\}^{m}$ such that
$b=b_{1}\dots b_{s}$ for some simple braids $b_{1},\dots,b_{s}$ and some $s\leq d\cdot c$?


texts:
Irreversible computations can be intuitive. For example, it is easy to understand roles of AND, OR, NOT gates and design a system without any intermediate, compilable layer. The gates can be directly used as they conform to human's thinking.

I have read a paper where it was stated that it is obviously correct way to code irreversibly, and compile to reversible form (can't find the paper now).

I am wondering if there exists a reversible model, that is as easy to understand as AND, OR, NOT model. The model should be therefore "direct" use of reversibility. So no compilation. But also: no models of form: $f(a) \rightarrow (a,f(a))$ (ie. models created by taking irreversible function $f$ and making it reversible by keeping copy of its input).


texts: Optimal preprocessing for certain types of queries

texts:
Suppose we have a semigroup $(S,\circ)$ with elements $S=\lbrace s_1,s_2,\dots,s_n\rbrace$. Our goal is to compute products $s_i\circ s_{i+1}\circ \cdots\circ s_j$.

In their paper "Optimal Preprocessing for answering on-line product queries" Alon and Schieber prove that we can answer each such query in at most $O(\alpha(n))$ steps (where $\alpha$ is the inverse Ackermann function) by using only linear amount of preprocessing.

If it is desired that each query $s_i\circ s_{i+1}\circ \cdots\circ s_j$ can be answered in $O(\log(j-i))$ steps, can one still do this with only linear preprocessing?

(This question is inspired by this recent question by Brendan McKay at Mathoverflow.)


texts: Are there any good examples of branching efficiency / prediction in quantum algorihms? Specifically suppose I have a set of CNOT gates one after the other that have the control line on the same line as the output of the CNOT gate?


texts: Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

texts:
I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).

I am particularly interested in algorithms (specially their application to machine learning, and whenever possible, proving theoretical guarantees for them, wether these guarantees are in complexity or learnability).

I'd be interested in knowing if there are any "heuristic" algorithms out there in the area of sub modularity and machine learning, with unknown guarantees. From my current knowledge of the topic, the most common heuristic seems to be the "greedy" heuristic, and it seems to be quite well understood. Hence, I was wondering if there was any open problems in the area of designing new algorithms (or improving current ones) or algorithms that already exists, that don't have any guarantees. Is there anything open questions related with theoretical guarantees that is open in sub modularity?

Or of if there aren't any such open question, are there any open question in the intersection of sub modularity and machine learning?


texts:
Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as cited by Fortnow.

  What is the intuition that VNP and NP are similar/ analogous in some way? Is there analysis/ results since its introduction that point toward or away from this analogy? Has/ can the study of VNP lead to some insights on NP?


texts: Finding triangles in a graph: other approaches besides property testing?

texts:
We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the tradeoff between the number of triangles in the graph and the communication load necessary. I am looking for references to work done on this question in the centralized model.

The problem is that nearly everything I found on this topic that had a theoretical flavor to it was within the framework of property testing. To illustrate the difference - consider the case of a graph with $n$ vertices, that is comprised of $n-2$ triangles all sharing the edge $\left(1,2\right)$. From the point of view of property testing, this graph is very close to be triangle-free (removing that critical edge does the job), whereas it has a linear number of triangles, which is a lot by our standards.

Any references at all will be appreciated.

Edit: I'm mainly interested in algorithms that can determine whether the graph contains triangles quickly. For triangle (or other subgraph) listing algorithms, the running time is naturally bounded from below by the number of triangles in the graph, as the algorithm needs to list them all, making such instances harder in a sense. From the point of view of a decision problem ("triangle-free or not"), having many triangles actually makes the problem easier, since you can easily find one.


texts: Height of randomly built binary search tree by insert and delete?

texts:
In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and delete.

In a  discussion (Oct 12. Can it be said old?) in stack ex here https://cs.stackexchange.com/questions/6342/proof-that-a-randomly-built-binary-search-tree-has-logarithmic-height as well the explanation of CLRS method has been discussed.

Is there some work in last one year or so?
Much appreciate if a reference could be found of some recent publication noting the above i.e. there is no progress as yet!

Thanks


texts: Linear programming, a non standard handling of absolute value

texts:
This is really a basic (undergrad) question in LP but still i would like to
clarify it for myself to be sure. I have a minimization problem from the sort $\min \sum_i |x_i|$ s.t $Ax \le b$.
I've seen that the standard way to convert it to LP is to represent $x_i$ as the difference
of two non negative variables. We question is, can i also handle it like so :
add a new variable t : $|x_i|=t_i$ and get
$$\min \sum_i t_i \\
Ax \le b \\
-t_i \le x_i \le t_i $$
Thanks.


texts: Algorithm whose running time depends on P vs. NP

texts: Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?


texts: Constructing subfields of a finite field

texts:
Suppose we have a finite field $\mathbb{F}_{p^n} = \frac{\mathbb{F}_{p}[x]}{<f(x)>}$. I want a deterministic polynomial algorithm to compute all subfields of this field. I think we can do something using linear algebra.

Can someone suggest a reference of this problem? I am unable to find it in standard texts.


texts: The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

texts:
Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which sampling a vector $w$ is done by setting each coordinate of $w$ independently, and a particular coordinate is set to $1$ with probability $\epsilon$ and to $0$ with probability $1-\epsilon$.

Let $C \subseteq V$ be a linear subspace, and let $e \in V \setminus C$ be a vector not in $C$. Consider the following pair of events concerning a vector $x$ drawn from $\mu_\epsilon$:

$E_1$ is the event that $x$ is in $C$
$E_2$ is the event that $x$ is in the coset $C + e$

Some experimentation (picking some choices for $C$ at random and also some popular linear codes) suggests that, when $\epsilon < 1/2$, the probability of $E_1$ occurring is at least the probability that $E_2$ occurs, for any $C$. Does anyone have any solid intuition or a proof for why this might be true? Or know of an example where it is false?


texts: Applications of Hamiltonian Cycle Problem

texts:
The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively.

I am looking for applications of the HamCycle and TSP.
What are some interesting real world problems where the HamCycle and TSP come up?


texts: Known upper bounds on the communication complexity of Karchmer-Wigderson games

texts:
In 1988 Karchmer and Wigderson established a nice characterization of the circuit
depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number of bits that Alice and Bob need to communicate in order to find
an index $i$ such that $a_i \neq b_i$, where Alice knows $a \in f^{-1}(0)$ and Bob knows $b \in f^{-1}(1)$.

What is known about upper bounds proved for such games? I've only
managed to find the following three results:

1) $2\log n$  upper bound for Parity function (binary search).

2) Chin proved $2.88\log n$ upper bound for $MOD_3$, $3.47\log n$ for
$MOD_5$, $4.93\log n$ for $MOD_{11}$ (http://unclaw.com/chin/scholarship/countingfunctions.pdf).

3) Brodal and Husfeldt proved an $O(\log n)$ upper bound for all symmetric functions (http://www.brics.dk/RS/96/1/BRICS-RS-96-1.pdf).

Are these the only known (non-straightforward) protocols?


texts: Complexity Theory in Finance and journals?

texts: What journals are there that try to combine these two areas ? I came across the Algorithmic Finance Journal, are there others ? Looking at papers, mixed to overly -ve views about the quality and direction.


texts:
Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$.  We throw the balls into the bins randomly, i.e., each ball lands into a random bin.

Can we argue that with constant probability, if you take the heaviest ball that lands into each non-empty bin, you get a set of balls whose total weight is $c T$ for some constant $c \in [0,1]$? I prefer $c$  as close to $1$ as possible but I want to make sure that the probability that happens is at least a constant.


texts:
Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices.

Furthermore, consider a variant of the Minkowski sum (somehow its weighted version). For $n$ nonnegative numbers $\vec{w}=(w_1, \cdots, w_n)$, we write
$\sum_{\vec{w}}P_i=\{\sum_{i=1}^n w_i \vec{x}_i\mid \vec{x}_i\in P_i\}$.

The question is, given two weight vectors $\vec{w}$ and $\vec{v}$, decide whether
$\sum_{\vec{w}}P_i = \sum_{\vec{v}}P_i$, where $=$ is interpreted as set equivalence.

It appears that a straightforward approach fails because $\sum_{\vec{w}}P_i$ as a polytope, might contain exponentially many vertices (?, order of $m^n$), so I only can show that the problem is in coNP. But is the problem in P, or it is coNP-hard as well?


texts:
Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes.
It cannot write on the tapes, but it can move on them in both ways, even move off from the input.
So for example, it can simulate counter machines, which implies that it can recognize any recursive language if $k\ge 3$.
If $k=1$, then it can be simulated by a two-way DFA, thus can recognize only regular languages. But what happens for $k=2$?

  Can two-tape read-only Turing machines recognize any recursive language?

Note that two-counter machines exhibit an intermediate behaviour, but this doesn't seem to answer my question.
Nor does the answer to this question, though the proof might not be much different.


texts:
I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them.

By this, I want to find the minimal number of single transitions of a node into a different group that are necessary to go from partition A to partition B.

For example the distance from {0 1} {2 3} {4} into {0} {1} {2 3 4} would be two

After searching I came across this paper, but a) I am not sure if they are taking into account the ordering of the groups (something I don't care about) in their distance b) I am not sure how it works and c) There are no references.

Any help appreciated


texts: How to solve this generalization of binary search?

texts:
Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.

Consider, for some unknown threshold $1\le T\le n$, a threshold function
$$g(x)= \begin{cases}
0&\text{x<T}\\
1&\text{otherwise}.
\end{cases}$$

Our goal is to find $T$ while minimizing the worst case cost, where computing $g(x)$ for any $x\in\{1,\ldots n\}$ has a cost of $f(x)$.
We assume that $f$ is known.

There are two straightforward approaches for this: a linear scan and a binary search.

It's not hard to see that each of them is good for different scenarios -- a linear scan works fine for $f(x)=2^{x}$ while a binary search is optimal for $f(x)=1$.

Since $f(n/2)$ may be much larger than $f(T)$, another approach is to use doubling and then binary search. The cost of this is bounded by $O(f(2T)\log T)$. This can be modified to
$$O(\epsilon^{-1} f(T)\log T +  f(T(1+\epsilon))\log (T\epsilon))$$
by doing the doubling using a $(1+\epsilon)$ factor.

  If this problem is known, What is the name of this problem?

  What is the optimal strategy here?

Obviously, it is possible to exhaustively compute the correct strategy. Can we compute it (or an approximation of it) faster? Is it possible to give an analytical formula for it?

I am aware that the problem is somewhat vague. Mainly, I am wondering if it is possible to analytically find an optimal solution (using the $f(i)$ values) and if not, if it is possible to compute a reasonable strategy given $f$ as an input.
You may also assume additional reasonable properties on $f$.


texts: About the origin of the names "immune" and "simple"

texts:
I have been wondering for a while about the origin of the names "immune"
and "simple". I also posed the same question to Andrea Sorbi, who in turn
involved a few more colleagues in the discussion.

About "simple" we have a few conjectures. Martin Davis suggests that the name
derives from an analogy with simple groups. Simple groups have no
non-trivial normal subgroups; complements of simple sets have no
infinite r.e. subsets.

Other people (Stephan, Nerode) seem to think that "simple" just refers to
the fact that they are simpler than creative sets, the latter being
considered a useful property of a human mind.

This is Nerode's
account:

"Post originally hoped to get computably enumerable sets with degrees of
unsolvability different from one of his creative sets  by  controlling
the lattice of re subsets of their complements. Simple sets are those
infinite re sets with infinite complements for which the lattice of re
subsets of the complement is as small as possible. So "simple" was
chosen to connote "fewest re subsets of complement", in stark contrast
with "creative set" which connotes "effectively uncountable number of re
subsets of the complement", which informally represents the perpetual
incompleteness of mathematics."

About "immune" we have no clue, however. Apparently, the word was introduced
by Dekker, in an article with Myhill in the fifties. Again this is Nerode's
affectionate opinion:

"As to why "immune", Dekker also introduced "isolated" and "regressive".
Stanley Tennenbaum always said that this was because Jim Dekker lived an
isolated life. He was an engaging homebody. I think that I and Myhill
and Stanley Tennenbaum were his main friends, scientifically and
personally. We all met at U Chicago in about 1952 just after Myhill
proved that all creative sets were recursively isomorphic, still one of
my favorite theorems."

If anybody has better information, I would be extremely grateful if he could
share this bit of knowledge.


texts: Graphs whose maximal clique intersection graph has bounded chromatic number

texts:
In general,
The chromatic number of the clique intersection graph a graph can again be arbitrarily high.
For example, take $n$ maximal cliques of size $n$ such that every pair of maximal cliques has a vertex in common.

So, for which non-trivial graphs the clique intersection graphs has bounded chromatic number even if the graph can have arbitrarily high chromatic number?

Any reference to surveys in this area is welcome.
I welcome any reference relating the graphs with bounded degree and to the chromatic number of its clique intersection graph.
Let the independent neighborhood of a vertex $v$ in a graph is the maximum independent set with every vertex having a common neighbor as $v$.
Let for a graph family $F$, we have a constant $C(F)$, such that for any graph in the family $F$, the size of independent neighborhood of a vertex $v$ in the graph is bounded by $C(F)$. Are there any studies which relate the chromatic number of the clique intersection graph family of $F$ with the above notion.

Edit:

In the clique intersection graph $C(G)$ of a graph $G$, the nodes are maximal cliques of $G$ and there is an edge whenever they share a vertex.

Note: This is different from the definition of clique-separator graph for chordal graphs (Which is a tree).


texts: How much smaller can universal Turing machines get if they only need to be universal for a subclass?

texts:
Say that a Turing machine $U$ is universal for a class $\mathcal{C}$ of languages if for any language $L \in \mathcal{C}$, there is a word $w_L$ with:
$$(\forall w)\quad w \in L \Leftrightarrow U(w_L, w) \text{ accepts}\enspace.$$

What is an upper bound for the size of $U$ for the classes of regular languages, CFLs, or CSLs?  What is the complexity of the function taking a grammar for a language $L$ in input and outputting $w_L$ for this upper bound?  Does it change anything if the negation of "$U$ accepts" is taken to be "$U$ rejects" or "$U$ does not halt"?


texts: Necessary and sufficient number of comparisons by every element to fully sort a set of n elements?

texts:
Given $n$ distinct elements.

Is there a sorting algorithm which ensures that every element is compared atmost $\lg n$ time?

Or is there a higher lower bound?


texts: Hadwiger number under matching contraction

texts:
Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a function of $h(G)$, say: $$h(G/M) \geq \Omega(\log h(G))$$ (or something like that), or a counter example to show that there is no such bound. Does anybody have any pointer on this?

I think the right bound is: $$h(G/M) = \Omega(h(G))$$
but I am unable to prove (or disprove) it. This is based on two observations: contracting a matching of $K_h$ resulting in $K_{h/2}$ and the similar situation holds for treewidth parameter: contracting a matching of a treewidth $k$ graph resulting in a graph of treewidth at least $k/2$ (though treewidth is loosely connected to Hadwiger number).

From Wikipedia: Hadwiger number $h(G)$ is the largest number $k$ for which the complete graph $K_k$ is a minor of $G$.


texts:
I'm interested in open questions from the book Approximation Algorithms for NP-Hard Problemss dedicated to k-clustering. They are:

  Is Euclidean max cut solvable in polynomial time? If not, how well can
  it be approximated?

  Does the problem minimizing the sum of distances from points to their
  cluster centers has good approximation algorithm ?


texts:
As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution.

Suppose we have a boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ and we are given a distribution over the inputs. I would like to ask whether I can apply Yao's principle when there is already some distribution given over inputs? If yes, then how?

I was reading the paper by Scott Aaronson and could not understand why he simply stated that by Yao's principle we can assume that algorithm is deterministic while there was already a distribution given over the inputs.


texts: What is a practical non-von Neumann architecture?

texts: Are there any practical applications for non-von Neumann programming models? What are the most widely adopted non-von Neumann programming languages?


texts: Phase transition in counting feasible solutions to knapsack problems?

texts:
Imagine that you have a normalized knapsack constraint with $n$ items and weights
$w_1,...,w_n$ satisfying $\sum_{i=1}^n w_i = 1$. I'm trying to understand the behavior of the function

$$Z(c) = \#| S \subset \{1,...,n\} : \sum_{i \in S} w_i \leq c|.$$

Clearly if $c = 0$, then $Z(c) = 0$, and if $c = 1$ then $Z(c) = 2^n$. Are there any results on phase transition behavior for $Z(c)$ when the $w_i$ are drawn randomly?

I'm aware there are results, for example, for counting the number of solutions to constraint satisfiability problems, but I haven't seen similar results for a counting the feasible solutions to a knpasack constraint.


texts: Kolmogorov complexity applications in computational complexity

texts:
Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$) It is easy to see that most of strings are random (there are not so many short programs).

Kolmogorov complexity theory and algorithmic information theory are quite developed nowadays. And there are several amusing examples of using Kolmogorov complexity in proofs of different theorems that do not contain anything about Kolmogorov complexity in their statements (constructive LLL, Loomis-Whitney inequality and so on).

Are there any nice applications of Kolmogorov complexity and algorithmic information theory in computational complexity and related fields? I feel that there should be results that use Kolmogorov complexity as a straightforward replacement of simple counting arguments. This is, of course, not that interesting.


texts: Searching for partial match - 1 item to be searched in $n$ preprocessed items

texts:
My problem is generalization of the simple problem:

Search for item $x$ in a set $S$.

This is trivial to do it fast if the elements are comparable. Sort the $S$, and do the binary search.

My problem is that I'm interested in partial match. That is, my items are ordered sets of $n = 15$ numbers, and I consider them equal if they have $m = 10$ numbers (at same position) same. For smaller numbers (like 5 out of 6), I can use $n = 6$ sorted sets that have all $m = 5$ number subsets of preprocessed items and then just do 6 binary searches. But for large numbers $n$ and $m$ where $n - m > 2$ number of sets (the binomial coefficient) explodes.

Is there efficient way to search for a partial match?

The only thing that I could think of is to index each number of the set. For example, when preprocessing size 3 sets:

{1,2,3},//set0
{2,3,4}//set1

Create entries

1->(set0,pos0)(position is important), 2->(set0,pos1),(set1,pos0) ... (4->set1,pos2)

and then when I get a new number, I just go for the each number in it and check the sets in which it appears. If there is a set that has many hits (say 10 or more), they are declared the same.

Of course I could use an array trick (i.e. array[1234] contains the pointer to the list of sets that contain 1234). This works for small ranges. For large ranges, I could hash the number and do modulo.

Of course this could go very very wrong for some distributions of preprocessed data.

So is there a better way?


texts:
Background: I'm a CS grad student. I've taken a course on computational complexity.

Question:

Can you suggest an introductory book on quantum computation, especially regarding the details of Question 2.
Argue whether it's hard to separate $QIP[i]$ from $QIP[i + 1]$ for $i < 3$. I know $QIP$ collapses to $QIP[3]$. The simple argument is that this question is hard because we still can't separate P from $PSPACE$. Note $P \subseteq BQP = QIP[0]$ and $PSPACE = IP = QIP = QIP[3]$. However on the other hand, I would think separating $QIP[i]$ from $QIP[i + 1]$ is easy, because the difference is obvious. The only thing left to do is to define a language that exploits the difference.

Remark. To me question 1 is more important than question 2. :p


texts: Category theory and parsers --- references wanted

texts:
Since I'm interested in parsers (mainly in parser expression grammars), I'm wondering if there's some work that gives a categorical treatment of parsing. Any reference on applications of category theory to parsing is highly appreciated.

Best,


texts: Lower bounds on alternative models of multiparty communication complexity

texts:
I'm a newcomer to communication complexity, and so far I've read the chapter in Arora-Barak and some papers giving lower bounds in various applications.

A priori the definition of multiparty communication complexity is strange. Forgetting the fruitful applications of the "number on the forehead" model, I would imagine people first thought to have each player see only their own input and not all but their own inputs. The computation of the protocol would happen in parallel, and communication could be player-to-player or broadcast.

I have reason to believe that lower bounds in such a model will aid me in proving lower bounds in a problem I'm currently looking at. Does this model have a name? What is known about it?


texts: Complexity of Max Bisection on cubic planar graphs?

texts:
Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximum. Max Bisection is $NP$-complete on cubic graphs and also on planar graphs.

  What is the complexity of Max Bisection on cubic planar graphs? Is it $NP$-complete?

Cross posted on mathOverflow


texts: Finding optimal parallelization from general weighted undirected graph

texts:
I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:

Each node represents an image. Overlapping images are connected by an edge. Edge weight represents overlap area size (blending larger overlap sooner leads to better overall quality).

The algorithm generally removes edges. It can do it sequentially or in parallel. However, when blending occurs, the nodes merge and the graph structure changes. So parallelization is possible only on connected components that are themselves not overlapping!

Such non-overlapping components are D-B and F-E-G. We can run the blending algorithm on these components safely in parallel. The result is the following graph (merged nodes are displayed in green):

Now there is no further parallelization possible because any two connected components are overlapping (they have an edge directly between them).

The parallel version of the algorithm would look like this:

1. Find connected components (no two are connected directly) and create task for each.
2. Run the tasks in parallel.
3. Update graph.
4. Until single node remains, continue with 1.

The tricky part is the first step: How to find best set of connected components?

One way would be a greedy algorithm that simply finds the largest number of components at a given iteration.
The greedy algorithm will maximize parallelization in the beginning but at the cost of many iterations later.

The optimal solution may be bringing good amount of connected components in each iteration to maximize parallelization and minimize number of iterations at the same time (so there are two variables in the optimization).

I can't think of any optimization algorithm other than backtracking, i.e. search space of all possible evolutions and choose the one with maximum parallelization.

Edge weights can be ignored, but improved version of the algorithm may take it into account as larger areas takes more time to blend (e.g. area of size 200 will take roughly twice the time to blend than two areas of size 100). Taking weights into account may lead to better strategy on selecting components (faster overall running time of the algorithm).

Do you have any clues for such optimization algorithm, that finds the best strategy of selecting parts of graph so that there is maximum parallelization and minimum number of iterations?


texts: Reduction SAT to a problem on a planar graph with as few vertices as possible

texts:
Let $\phi$ be CNF formula with $n$ variables and $m$ clauses.

I am looking for a reduction is $\phi$ satisfiable to a problem
on a planar graph $G$ with as few vertices as possible.

The majority of reductions I have seen use "crossing gadget",
which replaces edge crossing by a planar graph.

So far the best reference is $|V(G)|=m^2$.

The motivation is that the treewidth of planar graphs
is at most $4.9 \sqrt{|V(G)|}$ and this gives subexponential
complexity for problems exponential in the treewidth like
Independent Set.


texts:
Of course, some complexity results may collapse for unary languages but I wonder
if there is somewhere a survey summarizing the known results in this case: a kind of
complexity zoo for unary languages. Would you know of such a reference ?


texts: Is there a mathematical analysis/proof available for correctness of solutions to inter process communication problems?

texts:
I've been going over some material related to IPC recently from Tanenbaum's "Modern Operating Systems" and revisited semaphore after many years. There is a lot of code and pseudo code based explanations and solutions to classic IPC problems like dining philosophers etc and scenario based deadlock situations.

However, I didn't come across any reference to proving the correctness of those solutions. I had a look at Dijkstra's original paper (following a link on Wikipedia reference section). I did a quick run through and found the explanations to be more code and pseudo code based that mathematically rigorous. The google results at best give simulation cases, which are again code based.

My question is as the title says: Are there any mathematically rigorous analyses and proofs about the correctness of the solutions to the IPC problems available, freely (without membership to access information)?


texts:
A graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.

The Graceful Tree conjecture (all trees are graceful) is a well known open problem.

Finding a graceful labeling seems not so easy; some time ago I made a few tests with a Constraint Programming language and the solver got stuck even for relatively small highly symmetric trees.

A natural variant of the problem is the following:

  Graceful Tree Labeling Completion problem: Given a partially labeled tree $T$, is it possible to assign the remaining labels and obtain a graceful labeling?

I'm wondering if there have been attempts to study its complexity?

The conjecture is false for general graphs, furthermore any graph $G$ can be embedded as an induced subgraph of a graceful graph; so the following generalization to graphs could include enough "gears" to allow an NP-complete reduction.

  Graceful Graph Labeling Completion problem: Given a partially labeled graph $G$, is it possible to assign the remaining labels and obtain a graceful labeling?

I searched for both, but didn't find anything.


texts:
The AND&OR gate is a gate which is given two inputs and returns their AND and their OR. Are circuits made only out of the AND&OR gate, without fanout, capable of doing arbitrary computations? More precisely, is polynomial time computation logspace reducible to AND&OR circuits?

My motivation for this problem is rather strange. As described here, this question is important for computation inside the computer game Dwarf Fortress.


texts: Distributions over circuits and N-to-N vs N-to-1 circuits

texts:
This is really a two part question, and they aren't necessarily related.  First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small circuits will "look like" a distribution over all functions, at least to someone with limited computational power.  So, are there specific models studied of random circuits, and proofs that they do indeed look pseudo-random?  The dialogue in Gowers' blog some time ago indicates some of the difficulty in choosing such a distribution, as at one point one of the speakers inadvertently creates a distribution (over formulas rather than circuits) which fails even some fairly simple tests as pointed out in the comments (see http://gowers.wordpress.com/2009/09/22/a-conversation-about-complexity-lower-bounds/ ).  For example, I know that there are results like Mark Braverman's about polylog independence, but are there results showing that a given circuit distribution produces an output with such polylog independence w.h.p?

Second question: is the state of the art any better on circuit lower bounds if we consider N-to-N functions rather than N-to-1 functions?  That is, are there explicit functions with N input bits and N output bits for which a superlinear bound is proven, where the results are better than what one can prove for functions with 1 output bit?  Would lower bounds on N-to-N functions be "almost as interesting" as those on N-to-1, or is this much less interesting?


texts: Are there NP-complete problems with polynomial expected time solutions?

texts:
Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)?

If not, are there problems for which the existence of such an algorithm has been established?

Or does the existence of such an algorithm imply the existence of a deterministic polynomial time algorithm?


texts: What are good references on understanding online learning?

texts:
Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I failed to bookmark them.

As you might imagine, it's a rather challenging topic to search for on the internet.


texts: What is the significance of abstract linear algebra in machine learning/computer vision research?

texts:
I am a computer science research student working in application of Machine Learning to solve Computer Vision problems.

Since, lot of linear algebra(eigen-values, SVD etc.) comes up when reading Machine Learning/Vision literature, I decided to take a linear algebra course this semester.

Much to my surprise, the course didn't look at all like Gilbert Strang's Applied Linear algebra(on OCW) I had started taking earlier. The course textbook is Linear Algebra by Hoffman and Kunze. We started with concepts of Abstract algebra like groups, fields, rings, isomorphism, quotient groups etc. And then moved on to study "theoretical" linear algebra over finite fields, where we cover proofs for important theorms/lemmas in the following topics:

  Vector spaces, linear span, linear independence, existence of basis.
  Linear transformations. Solutions of linear equations, row reduced
  echelon form, complete echelon form,rank. Minimal polynomial of a
  linear transformation. Jordan canonical form. Determinants.
  Characteristic polynomial, eigenvalues and eigenvectors. Inner product
  space. Gram Schmidt orthoganalization. Unitary and Hermitian
  transformations. Diagonalization of Hermitian transformations.

I wanted to understand if there is any significance/application of understanding these proofs in machine learning/computer vision research or should I be better off focusing on the applied Linear Algebra?


texts: Algorithmic game theory - nonstandard equilibrium concepts?

texts:
I'm beginning my studies of algorithmic game theory, and it seems that the equilibrium concept usually taken is that of a fixed point in a graph. However, have people looked at alternative equilibrium concepts, such as limit cycles? I can imagine that a "tight" limit cycle - that is, a cycle in the graph of very small length - could be considered something that's "close" to the standard definition of equilibrium.

I've tried digging around Google Scholar, but to little avail.


texts: Maximize the expected number of "losers" - Is it NP-hard?

texts:
I am trying to find a reduction for a problem that seems NP-hard:

Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$.
You want to choose two pairs out of the three pairs and compare the
two elements of each pair. There is a true underlying ordering of
the elements, which we don't know. Our objective is to pick the comparisons
that will maximize, in expectation, the number of elements that
will "lose" at least one comparison.

For example, lets assume that we choose $(a,b)$ and $(b,c)$.
There are four possibilities:

(1) $a>b$ and $c>b$ with probability $\frac{2}{6}$ ($2$ out of the $3!$ possible permutations respect $a>b$ and $c>b$)

(2) $a>b$ and $c<b$ with probability $\frac{1}{6}$

(3) $a<b$ and $c>b$ with probability $\frac{1}{6}$

(4) $a<b$ and $c<b$ with probability $\frac{2}{6}$

In the case of (1), only $b$ loses at least one comparison, in (2), $b$ and $c$ lose at least one comparison, and so on.
The expected number of elements losing at least one comparison is:

$\frac{2}{6} * 1 + \frac{1}{6} * 2 + \frac{1}{6} * 2 + \frac{2}{6} * 2 = 1\frac{2}{3}$

Note that the outcome of each comparison is based on the true ordering, which we don't know..

In this toy example, any two pairs give the same expected number of "losers".
In its general form, the problem states that we have $n$ elements, and we can ask
for $b$ comparisons (the problem becomes interesting when $b>\frac{n}{2}$). Making
it even more general, we can have the outcome of previous comparisons as input and try to maximize the "losers" out of those elements that still haven't lost any comparison. I am interested in the second, more general, case but I feel that even without the previous comparisons' outcome, the problem is still NP-hard.

The most helpful result I have found until now, is that counting linear extensions of a partially ordered set is #P-complete [1].

I would greatly appreciate any ideas about a reduction, or any obvious reduction that I can not see.

Thank you!

[1] Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order 8 (3): 225–242, paper


texts: Multidimensional arithmetic progression variant

texts:
For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e.
$Q(\vec{d} = \{\langle \pm d_1, \ldots, \pm d_n\rangle\}$.

Consider the following problem:

  Given a set of points in $\mathbb{N}^n$ and number $k$,
  does the set contains an $n$-dimentional arithmetic progression of length $k$?

More formally,

  Input:
  given a finite set $X \subseteq \mathbb{N}^n$ and a positive integer $k \in \mathbb{N}^+$.

  Question:
  are there $\vec{o}\in \mathbb{N}^n$ and $ \vec{d} \in (\mathbb{N}^+)^n$ such that
  $\vec{o}+ Q(i\vec{d})\subseteq X$ for all integers $0 \leq i \leq k$?

Informally we are looking at the containment of
the vertices of scaled $n$-dimensional axis-aligned cubes centered at $\vec{o}$.

Does this problem have a name?
What is its complexity?
Can we solved it using dynamic programming?


texts: In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

texts:
Decision Problem
Input: An $m$ by $n$ Boolean matrix $M$.
Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left corner entry == lower-right corner entry == 1?  That is, all four corners of the square block are 1's.
Cubic Time Solution
We know that this problem can be solved in $O(m \cdot n \cdot min\{m,n\})$ time.  The approach involves scanning through the matrix row by row.  For each row, for each pair of 1's in that row, we check whether those 1's form an edge of a square block whose four corners are 1's.
Our Question
What is the time complexity of this problem?  Is there a quadratic time solution?  In particular, can we solve this decision problem in $O(m \cdot n)$ time?
Extra Background

If you're just looking for a rectangular block whose four corners are ones, this can be solved in $O(m \cdot n)$ time.  Many variations to this problem can be solved in $O(m \cdot n)$ time as well.  I co-authored a paper on this subject.

The paper "Finding squares and rectangles in sets of points" investigates a related problem from computational geometry where you're given a set of points in a 2D plane and you want to know if there are four points that form an axis-parallel square.

Written together with Eevvoor.


texts: Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

texts:
For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct integers $p_1, \ldots, p_n$, the sequence $\mathbf{p}$ is a subsequence of $s$, i.e., there exist $1 \leq i_1 < i_2 < \cdots < i_n \leq |s|$ such that $s_{i_j} = p_j$ for all $1 \leq j \leq n$.

What is the complexity of the following problem? Is it in PTIME, or coNP-hard? Note that it is in coNP as you can guess a missing sequence (thanks @MarzioDeBiasi).

Input: an integer $n$, a sequence $s$ of integers in $\{1, \ldots, n\}$
Output: is $s$ $n$-complete?

The notion of $n$-complete sequence is known in combinatorics because people have investigated what is the length of the shortest $n$-complete sequences as a function of $n$ (see, e.g., this mathoverflow thread for a summary). However, I was unable to find references to the complexity of recognizing them. Note that in particular we can easily build $n$-complete sequences of length polynomial in $n$, namely, of length $n^2$, as $(1, \ldots, n)$ repeated $n$ times (any permutation $\mathbf{p}$ can be realized by choosing $p_i$ in the $i$-th block). Hence we cannot afford in general to enumerate all permutations.


texts: Fast deletion / contraction in combinatorial embedding

texts:
I wonder if there is a sublinear algorithm to make deletion or contraction of an edge in a combinatorial embedding of, lets say, planar graph?

Since in combinatorial embedding we have to maintain vertices of G and G* at the same time, taking in account that contraction in the primal is deletion in the dual, it's sufficient only to make deletions, updating primal permutation according to dual and vice-versa. But obvious way to do it is just recompute them, which takes linear time. Can we do any better?

Second question: is there any technique that helps to get rid of multiple edges between same vertices? (the only solution I see to the second problem is to postpone deletion of multiple edges until we will get graph with, for example, m=6n, where m - number of edges, n - number of vertices, this will make time amortized O(1)) Maybe there is some techniques, which can make this time not amortized? (I am also interested in just o(n) solutions, not necessarily O(1))

Thank you very much!


texts: Graph partition with weighted vertices and edges

texts:
I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from standard min, max cut problems. I have searched for a suitable algorithm for several days but with no success. Maybe someone can give a suggestion or at least come up with a standard name for such problem?

The problem is as follows:

Input: Undirected graph $V$ with vertex weights $u_i$ and edge weights $w_{ij}$.

Output: Graph partition in two components $S_1$ and $S_2$ to minimize the following:
$$\max((\sum_{i\in S_1}u_i-\sum_{i,j\in S_1}w_{ij}), (\sum_{i\in V-S_1}u_i-\sum_{i,j\in V-S_1}w_{ij})) $$
Basically, if we define $weight$ of a component as the sum of weights of its vertices minus the sum of weights of its edges, then I would like to find a pair of components such that a maximal weight out of the two components is minimal over all possible pairs. The edges between two components are removed.

Here is an example of possible graph partition (there may be several). The numbers mean the weights:

Thanks in advance for suggestions!


texts: What is the simplest universal unidimensional interaction net system?

texts: The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? What is the simplest of those systems which is Turing-complete?


texts: Will quantum computing pave the way for native, true RNGs?

texts: Obviously, regular computers can't generate random numbers on their own, since they're inherently systematic machines. Would quantum computing be able to run a true RNG without a seed based off user input (or any other external variables)?


texts: On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits

texts:
As I understand from the survey "Progress on Polynomial Identity Testing - II"
a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown.

However, there exists paper of Ankit Gupta "Algebraic Geometric Techniques for Depth-4 PIT
& Sylvester-Gallai Conjectures for Varieties" that gives a polynomial-time algorithm for this case modulo the following conjecture from this paper.

Conjecture Let $F_1, F_2, \ldots,  F_k$ be finites sets of irreducible polynomials in $\mathbb{C}[x_0, \ldots, x_n]$ of degree at most $r$ such that
$ \cap F_i = \varnothing$ and for every $Q_1, \ldots , Q_{k-1}$  from distinct sets there are  polynomial $P_1, \ldots, P_c$ in the remaining set such that $V(Q_1, \ldots, Q_{k-1}) \subseteq \cup_i V(P_i)$. Then $\text{trdeg}_{\mathbb{C}}(\cup_i F_i) = \lambda(k,r,c)$ for some function $\lambda$.

This conjecture impies the existense of polynomial-time for PIT for $\Sigma \Pi \Sigma \Pi (k, r)$.
As I understand for $k=2$ this conjecture holds. Note first that
$V(Q_1)\subseteq \cup_i V(P_i)$ implies $V(Q_1)\subseteq  V(P_j)$ for some $j$. Indeed, by  Nullstellensatz   $(P_1 \cdot P_2 \ldots \cdot P_c)^m = Q_1 \cdot H$ for some $m$ and $H$. Since $Q_1$ is irreducible this means that some $P_j$ is divided by $Q_1$.

So, now we have two sets of irreducible polynomials $F_1$ and $F_2$ such that $F_1 \cap F_2 = \varnothing$ and for every $P$ from one of this set there exists $Q$ from another set such that $V(P) \subseteq V(Q)$. Of course this means that both sets are trivial.

So, there exists a polynomial-time algortihm for solving PIT for $\Sigma \Pi \Sigma \Pi(2,r)$-circuits.

Am I wrong?


texts:
Given a directed graph $(V,E)$ with $E\subseteq V\times V$, a source vertex $v_0\in V$ from which all other vertices are reachable, and a set $I$ of unique identifiers for the edges in $E$ (i.e., there is a bijection $I \rightarrow E$), we can construct a set $M\subseteq V \times \mathcal{P}(I)$ containing exactly those $(v,S)$ such that there is a path from $v_0$ to $v$ using exactly the edges represented by $S$ (in any order and repetition).
For example, the graph $(\{A,B\},\{(A,B),(B,A)\})$ with $v_0=A$ and $I(a)=(A,B), I(b)=(B,A)$ would be represented as $\{(A,\emptyset),(B,\{a\}),(A,\{a,b\}),(B,\{a,b\})\}$.

I wonder under which conditions the inverse construction is possible: assuming $M$ is "consistent" (there is at least one graph satisfying it), what conditions are needed for $M$ to represent a unique graph? Certainly $M$ has to satisfy some kind of "closure" property, like: for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $|S|=|P|+1$.
Then a (hopefully deterministic) algorithm would construct $G$ by picking elements from $M$ in order of increasing cardinality.

Edit: of course the closure property should be that for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $S= P\uplus\{x\}$.
But this is not strong enough if self-loops are allowed: $\{(A,\emptyset),(B,\{a\}),(B,\{a,b\})\}$ represents two non-isomorphic graphs (one with $b=(B,A)$, the other with $b=(B,B)$).

Edit: I just noticed that there are counter-examples even without self-loops: $M=\{(A,\emptyset),(B,\{a\}),(C,\{a,b\}),(C,\{a,b,c\})\}$ may imply $c=(C,B)$ or $c=(C,A)$ (or $c=(C,C)$).

Has somebody worked on this kind of problem?


texts: Comparing the Kolmogorov complexity of theories - Part 2

texts:
Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently large constant. The size of $L$ depends on the theory.

Consider the following hierarchy of theories: Let the base theory be Robinson arithmetic ($Q$). Augment $Q$ with increasingly stronger axioms of polynomial bounded induction. Let $Q^*$ be the theory of theorems provable with $Q$ and any of these bounded induction axioms.

Let $L(T)$ be the least natural number such that $T\not\vdash \exists x(K(x)\geq L(T))$. In Comparing the Kolmogorov complexity of theories I asked if there was a constant upper bound for $L(Q^*)$ and all of its sub-theories. The answer was yes. In fact, it was shown that $L(T)$ is monotonic for sub-theories of $Q^*$.

One would assume this means $L(Q) \leq L(T) \leq L(Q^*)$ where $T$ is a sub-theory of $Q^*$. $L(Q^*) - L(Q)$ is a finite number and there are an infinite number of sub-theories. Does this mean an infinite number of sub-theories of $Q^*$ have the same complexity ($L(T)$)?

Another way to ask this question: Is there some point where stronger sub-theories can no longer prove the existence of numbers with larger Kolmogorov complexity than weaker sub-theories can prove. For example, can bounded induction beyond $L(Q^*)$ prove anything about the Kolmogorov complexity of numbers that can't be proven with weaker sub-theories?


texts: Minimax agnostic risk for Lipschitz functions

texts:
For $L>0$, let $F_L$ be the class of all $L$-Lipschitz functions on $[0,1]$. Let $D$ be a joint distribution on $[0,1]\times\mathbb{R}$, from which we sample $n$ iid copies $(X_i,Y_i)$. Given any $f:[0,1]\to\mathbb{R}$,
$
%its empirical risk is
$
$$
% R_n(f) = \frac1n\sum_{i=1}^n (f(X_i)-Y_i)^2$$
its true risk (w.r.t. $D$) is
$$ R(f) = \mathbb{E}_D[(f(X)-Y)^2].$$
Define the minimax agnostic excess risk by
$$ \Delta_n = \inf_{\hat f}\sup_D \mathbb{E}_D[ R(\hat f)-\inf_{f\in F_L}R(f)],$$
where the sup is over all distributions $D$ and the inf is over all estimators taking an $n$-point sample $(X_i,Y_i)$ to a function $\hat f:[0,1]\to\mathbb{R}$.

What is known about the behavior of $\Delta_n$? I was only able to find mimimax rates for additive -- rather than agnostic -- noise models.


texts:
Is there a natural (and hopefully well-known) maximization problem that is known to be in FPT?
For instance, Vertex Cover is in FPT, but it's a minimization problem.
I'm looking for natural maximization problems that are in FPT.

Edit (clarification): "I assume you mean a maximization problem that is in FPT when parameterized by the solution size." This is exactly what I meant to ask, as the first comment (by Jan Johannsen) points out.


texts:
My question relates to bi-partite expander graphs, defined as bi-partite graphs on $n$ left vertices, $m$ right vertices, constant left-degree $k$, such that

For any linear-sized subset $S$ of the left vertices of size $|S| = O(\gamma n)$ (where $\gamma$ is some constant), the set of right neighbors is close to full-expansion, i.e. $k (1-\epsilon) |S|$.

My question is:

  What is known about the degrees of the right vertices?
  Is there a phenomenon, where some vertices have a very high degree,
  while others have a very small degree?

Below, is a proof that assuming that for every such expander all right vertices have degrees at most sublinear in $n$ implies some contradiction to a
theorem by Capalbo, Reingold, Vadhan and Wigderson.
This theorem states that for any $n,m,\epsilon$ there exists some $k = \mathrm{polylog}(n/m)$, $\gamma=g(n,m,\epsilon)$ for which there exists such a bi-partite expander.

Let $G$ be such a bi-partite expander.
Let $q$ be some right vertex, and let $S_q$ be the set of left vertices adjacent to $q$.  Suppose on the negative that each $|S_q|$ is of some bounded small size, and so it must abide by the expansion property.
So the number of neighbors of $S_q$ is at least $|S_q|k(1-\epsilon)$.
Yet, we know that since all vertices of $S_q$ share $q$ then the number of neighbors is upper-bounded by $|S_q|(k-1)+1$, and so
$ |S_q|k(1-\epsilon)< |S_q|(k-1) + 1$.
Hence, $$|S_q| < \frac{1}{1-\epsilon k} \text.$$

On the other hand, the number of edges is $nk$ and so there exists a right vertex of degree at least $\frac{nk}{m}$, and so there exists some $q$ for which
$|S_q| > \frac{nk}{m}$, and we have $\frac{nk}{m}< \frac{1}{1-\epsilon k}$.
This implies the following quadratic equation in variable $k$:
$$ \frac{n \epsilon}{m}k^2 - \frac{n}{m}k + 1 >0 $$
which, for sufficiently small $\epsilon$ and $n>m$ forces $k>\frac{1}{\epsilon}$ (or $k<0$).

Yet, by the theorem $k< (\frac{n}{m})^t$ for some constant $t$
so $\frac{1}{\epsilon}< (\frac{n}{m})^t$.
But one can easily choose $n,m,\epsilon$ which do not hold the above, by contradiction.


texts: What is entropy of a variable described by Knightian uncertainty?

texts: Given a discrete variable whose value is characterized by Knightian uncertainty, that is, belief and plausibility, as in Dempster-Shafer theory, what is its entropy?


texts: Complexity of Finding Largest Set of Intersecting Convex Polytopes

texts: I have a set of $n$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am struggling to find a reduction and I can't find any relevant literature on the subject. Can anyone help me with a reduction or point me towards something I can read about? Thanks!


texts:
I would like to know if the following NP-complete problem has a name and has been studied:

  Input: Given a CNF formula $\varphi$ on $n$ variables, a truth assignment $\sigma:[n] \to \{T,F\}$ and an integer $k$;
  Question: Can we transform $\sigma$  into a satisfying assignment for $\varphi$, swapping the truth values of at most $k$ pairs of variables.

It is very similar to the problem k-FLIP SAT (see my previous question for details); but here the number of truth values used cannot change.

In particular, I would like to know if there are some results about its parameterized complexity in the general case and under some restrictions (e.g. q-CNF formulas, max occurrences of a variable).

I did a few searches on google, but didn't find anything (but probably I'm not using the correct terms).


texts: Have you ever realized you can't solve the homework you assigned?

texts:
This question is targeted at people who assign problems: teachers, student assistants, tutors, etc.

This has happened to me a handful of times in my 12-year career as a professor: I hurriedly assigned some problem from the text thinking "this looks good."  Then later realized I couldn't solve it.  Few things are more embarrassing.

Here's a recent example: "Give a linear-time algorithm that determines if digraph $G$ has an odd-length cycle."  I assigned this thinking it was trivial, only to later realize my approach wasn't going to work.

My question: what do you think is the "professional" thing to do:

Obsess on the problem until you solve it, then say nothing to your students.
Cancel the problem without explanation and move on with your life.
Ask for help on cstheory.SE (and suffer the response, "is this a homework problem?")

Note: I'm looking for practical and level-headed suggestions that I perhaps haven't thought of.  I realize my question has a strong subjective element since handling this situation involves one's own tastes to a large extent, so I understand if readers would prefer to see it not discussed.


texts: Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation essential for attaining a circuit of polynomial size with logarithmic or linear depth to calculate determinant (and any possible best circuit for permanent)? Are there fully exponential (not just superpolynomial or sub exponential) lower bounds for these problems using circuits without cancellation?


texts: Equivalence of categories of directed complete posets

texts:
I asked this question there: https://math.stackexchange.com/questions/700975/equivalence-of-categories-of-directed-complete-posets.
Since I had no answer, I try here.

In the book ``Domains and Lambda-Calculi'' by Amadio and Curien, there is the following exercise: Define an equivalence between the category of partial morphisms generated by $(\mathcal{M}_S, \textbf{Dcpo})$ and the category $\textbf{sCpo}$.

The category $\textbf{Dcpo}$ has as objects directed complete posets i.e. partially ordered sets such that any directed subset has a least upper bound and as morphisms continuous functions for the Scott topology (Scott opens of a dcpo $D$ are subsets $O$ of $D$ such that (1) $x \in O \textit{ and } x \leq y \Rightarrow y \in O$ and (2) $\Delta$ directed and $\bigvee \Delta \in O \Rightarrow O \cap \Delta \not= \emptyset$).

The category $\textbf{sCpo}$ is a subcategory of $\textbf{Dcpo}$: objects are dcpo's with a least element $\bot$ and morphisms are continuous functions $f$ such that $f(\bot) = \bot$.

For any dcpo $C$, we denote by $C_\bot$ the object of $\textbf{sCpo}$ obtained from $C$ by adding a new element $\bot$, which is the least element of $C_\bot$.

The "admissible family of monos" $\mathcal{M}_S$ associates with every object $A$ of $\textbf{Dcpo}$ the class of monomorphisms $\mathcal{M}_S(A)$ such that if $m \in \mathcal{M}_S(A)$, then (1) $m$ is a monomorphism $D \rightarrow A$ for some $D$ and (2) $\textit{im}(m)$ is a Scott open of $A$.

The category of partial morphisms generated by $(\mathcal{M}_S, \textbf{Dcpo})$, denoted below by $\textbf{pC}$, has as objects dcpo's and as morphisms from $D$ to $D'$ equivalence classes $[m, f]$ of representatives of partial morphisms $(m, f)$, where a representative $(m, f)$ for a partial morphism from $A$ to $B$ is a pair of morphisms in $\textbf{Dcpo}$ with $m : D \rightarrow A \in \mathcal{M}_S(A)$ and $f \in \textbf{Dcpo}(D, B)$ and $(m : D \rightarrow A, f: D \rightarrow B)$ is equivalent to $(m': D' \rightarrow A, f': D' \rightarrow B)$ iff there is an isomorphism $i : D \rightarrow D'$ such that $m' \circ i = m$ and $f' \circ i = f$.

I had the idea to define the following functor $F: \textbf{pC} \rightarrow \textbf{sCpo}$: for any object $D$, $F(D) = D_\bot$; for any $[m, f] \in \textbf{pC}(D, D')$, $F([m, f])$ is the morphism $g: D_\bot \rightarrow D'_\bot$ defined by: $g(y) = f(x)$ with $m(x) =y $ if $y \in \textit{im}(m)$; $g(y) = \bot$ if $y \notin \textit{im}(m)$. But it seems that it does not work. Indeed, consider the following dcpo's: $D = (\{ a, b \}, \leq)$ with $a$ and $b$ not comparable; $D' = (\{ a', b' \}, \leq')$ with $a' <' b'$. I denote by $m$ the monomorphism $D \rightarrow D'$ defined by $m(a) = a'$ and $m(b) = b'$. Notice that $[m, m] \not= [id_{D'}, id_{D'}]$, since all the morphisms from $D'$ to $D$ are constant. But $F([m, m]) = id_{D'_\bot} = F([id_{D'}, id_{D'}])$, hence $F$ is not faithful.

So I am not able to solve the exercise.

(Assume that $\mathcal{M}_T$ associates with every object $A$ of $\textbf{Dcpo}$ the class of monomorphisms $\mathcal{M}_T(A)$ such that if $m \in \mathcal{M}_T(A)$, then (1) $m$ is a monomorphism $D \rightarrow A$ for some $D$, (2) $\textit{im}(m)$ is a Scott open of $A$ and (3) $m(x) \leq m(y) \Rightarrow x \leq y$. Consider the category $\textbf{pC'}$ of partial morphisms generated by $(\mathcal{M}_T, \textbf{Dcpo})$. Then it seems that the functor $F' : \textbf{pC'} \rightarrow \textbf{sCpo}$ defined as $F$ (for any object $D$, $F'(D) = D_\bot$; for any $[m, f] \in \textbf{pC'}(D, D')$, $F'([m, f])$ is the morphism $g: D_\bot \rightarrow D'_\bot$ defined by: $g(y) = f(x)$ with $m(x) =y $ if $y \in \textit{im}(m)$; $g(y) = \bot$ if $y \notin \textit{im}(m)$) is an equivalence of categories.)


texts:
Lately I have been studying cache-oblivious data structures and algorithms. I was reading about the cache-oblivious B-tree from the Handbook of Data Structures and Applications, with hopes of actually implementing it and doing some benchmarking.

Section 38.3.1 of the book talks about the density based approach. The vEB-layout and the density thresholds seem fine, but I am missing something (perhaps even trivial) from the updates. The text explains:

  To insert a new element into the structure we ﬁrst locate the position in $T$ of the new node $w$. If the insertion of $w$ violates the height bound $H$, we rebalance $T$ as follows: First we ﬁnd the lowest ancestor v of w satisfying $γ_i$ ≤ ρ(v) ≤ $τ_i$, where $i$ is the level of $v$.

Looking at the figure, let's consider a scenario: suppose we want to insert an item with value 15. We check to see that it cannot be inserted since the height bound $H$ would be violated. Hence we must find the lowest ancestor $v$ of $w$ satisfying the mentioned bounds. If we now work towards the top of tree trying to find a suitable ancestor, we find it immediately (the item with value 13). It clearly satisfies the bounds, since its ρ is 1.

It would make a lot more sense to me if the ancestor at which we should stop is the one with value 8. Right now I see two cases: either I don't know the exact definition of lowest ancestor or the lowest ancestor $v$ should satisfy not $γ_i$ ≤ ρ(v) ≤ $τ_i$ but $γ_i$ < ρ(v) < $τ_i$.

I also took a look at Cache-oblivious B-trees by Bender, Demaine and Farach-Colton. This paper also defines the bound as $γ_i$ ≤ ρ(v) ≤ $τ_i$.


texts:
Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at least $k$ connected components.

We can similarly define the minimum vertex $k$-cut problem: find $V' \subseteq V$ with minimum $|V'|$ such that the subgraph induced by $V \setminus V'$ has at least $k$ connected components.

There is a slight difference between the edge and the vertex version: for the edge version, a feasible solution $E'$ exists iff $|V| \geq k$, but for the vertex version, a feasible solution $V'$ exists iff $G$ has an independent set of size $k$. Therefore, if $k$ is part of input, for the vertex version, even finding a feasible solution is NP-hard. For the edge version, it is NP-hard to find the minimum solution, but we can get a good (<2)-approximation.

My main question is when $k \geq 3$ is a fixed constant (of course when $k = 2$ both vertex and edge versions can be easily solved). For the edge version, the following paper by Goldschmidt and Hochbaum shows that the minimum $E'$ can be found in time $O(n^{k^2})$.

https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021960.pdf

What is the complexity of computing the minimum vertex $k$-cut when $k$ is a fixed constant? Currently I do not know the answer for $k = 3$.


texts:
It is known that Linear Programming (LP) is P-complete.
I am interested in approximation algorithms for LP.

There are numerous inapproximability results for NP optimization problems,
e.g. it is NP-hard to achieve approximation ratio better than 7/8 for MAX-3SAT.

  Are there similar P-hardness results for approximation optimization problems in P?
  In particular, is it known if LP is P-hard to approximate?


texts: Is there a logic without induction that captures much of P?

texts:
The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ordered structures.  The fixed-point operator can be either least fixed-point (as considered by Immerman and by Vardi), or inflationary fixed-point.  (Stephan Kreutzer, Expressive equivalence of least and inflationary fixed-point logic, Annals of Pure and Applied Logic 130 61–78, 2004).

Yuri Gurevich conjectured that there is no logic capturing PTIME (Logic and the Challenge of Computer Science, in Current Trends in Theoretical Computer Science, ed. Egon Boerger, 1–57, Computer Science Press, 1988), while Martin Grohe has stated he is less sure (The Quest for a Logic Capturing PTIME, FOCS 2008).

The fixed-point operator is meant to capture the power of recursion.  Fixed-points are powerful, but it isn't obvious to me that they are necessary.

  Is there an operator X that is not based on fixed-points, such that FOL+X captures a (large) fragment of PTIME?

Edit: As far as I understand, linear logic can only express statements about structures that have quite restrictive form.  I would ideally like to see a reference to, or a sketch of, a logic that can express properties of arbitrary sets of relational structures, while still avoiding fixed points.  If I am wrong about the expressive power of linear logic then a pointer or hint would be welcome.


texts: How to design an online algorithm for secretary problem with multiple players?

texts:
We have $k$ bins of capacity $c_i$ each. These bins appear in an online fashion, say on day $i$, bin $i$ appears. There are $l$ balls. Ball $j$ has weight $w_{ij}$ with bin $i$.

Each ball knows that there will be $k$ bins. On day $i$, bin $i$ appears and ball $j$ gets to know the bin and its capacity $c_i$. Also, ball $j$ gets to know $w_{i1},w_{i2},\ldots,w_{il}$; the weights of all balls with bin $i$ (including her weight of course). Ball $j$ must decide either to put herself into bin $i$ or not, once and forever (i.e., once decided, the game is over for ball $j$).

Each ball wants to be satisfied, that is, puts herself into a bin that has enough capacity. Ball $j$ does not know if some other balls have chosen bin $i$ or not. Also, Ball $j$ knows only the current information, does not know the weights of the balls with bins that will appear in the future.

Is there a way to find an online algorithm that maximizes the number of satisfied balls? I think this is somehow related to secretary problem but I am not sure how to prove this claim.


texts: A matrix rank problem over finite fields: Is that a known problem?

texts:
The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated.

Let $A \odot B$ denote elementwise multiplication of matrices $A$ and $B$.
Let $M|\mathbf w$, where $M$ is a matrix and $\mathbf w$ is a subset of the column indices, denote the matrix formed by selecting columns $\mathbf w$ from $M$.

Problem:

  Input: A binary matrix $B=\left[b_{ij} \right]_{m \times n}$, $b_{ij} \in \{0, 1\}$ and a collection $\{ \mathbf{w}_i \subset \{1,\cdots, n\} | i=1,\cdots,k \}$ of column indices.

  Output: Find a matrix $A=\left[ a_{ij} \right]_{m \times n}$, $a_{ij} \in \mathrm{GF}(p^q)$ such that for each $\mathbf{w}_i$, $i=1,\cdots, k$, rank of $(A \odot B)|\mathbf{w}_i$ is $|\mathbf{w}_i|$ or print IMPOSSIBLE if no such matrix exists.

Informally, the problem is that given an $m\times n$ matrix in which some of the elements are fixed to 0, assign values from a finite field to other elements such that the rank of some specific subsets of the columns is maximized.

Observations:

You can assume that $w=\max_i |\mathbf w_i|$ is a constant.
You can assume that $p^q$ is much larger than $3knw$.
If $\mathbf w_i$'s are disjoint, one can simply solve the problem by solving the problem for each $\mathbf w_i$ separately.
If $\mathbf w_i \subset \mathbf w_j$ for some $i \neq j$, $\mathbf w_i$ can be removed from the collection and the problem does not change.
From #3 and #4, the only difficult case of the problem is when $\mathbf w_i$'s intersect, but do not overlap completely (i.e. one is the subset of another).

Edit:

As "mobius dumpling" noted in his answer, with random assignment from the finite field to the matrix $A$, $(A\odot B)|\mathbf w_i$ has full rank with a constant probability $s$ for each $i=1,...,k$. The problem is that the probability that all $(A\odot B)|\mathbf w_i$ have full rank is $s^k$, which is not a constant. Should I use a more complicated method (such as inclusion/exclusion method) to compute the total probability?
A necessary condition for the problem is: for all $i$: for each $j\in \mathbf w_i$, there is a distinct row $k$ such that $b_{kj}=1$. This can be checked in polynomial time.
Having a full rank matrix $A \odot B$ as the result is neither a necessary nor a sufficient condition. The necessary part is apparent since in many cases, the answer is not a full rank matrix. For the case $m < n$, it is not also sufficient.