texts: How well can an arbitrary (unknown) quantum state be imperfectly cloned?

texts:
How well can an arbitrary unknown (quantum) state $\rvert \psi \rangle = \alpha\rvert 0 \rangle + \beta \rvert 1 \rangle$, be imperfectly/approximately cloned?

Given an unknown state ${\rvert \psi \rangle}$, say one can clone ${\rvert \phi \rangle}$ , such that
$${\langle \phi }{\rvert \psi \rangle}= \delta$$

If $\rvert \phi \rangle$  and  $\rvert \psi \rangle$ are identical and same, $\delta = 1$, however we know, due the no cloning theorem, that $\delta<1$.

My question is what is the 'highest' value of $\delta$ one can achieve using polynomial time 'resources', i.e. how well can an UNKNOWN quantum state be imperfectly cloned?

(Let's agree we $\rvert \psi \rangle$, both $\alpha, \beta$ are non-zero, i.e. not basis states)


texts: What is known about computing distinct count range queries?

texts:
Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$.
Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries.

In the Range Query problem we get an integer array $A[1,\ldots,n]\in U^n$ and wish to compute queries that takes as input parameters $1\le i\le j\le n$ and return $f(A[i,\ldots,j])$.

Consider the function $f$ that returns the number of distinct elements in the queried range.

The goal is to preprocess the input array $A$ and create a small summary that allows efficient computation of these distinct queries.

  What is the best known algorithm for the problem? (given a memory bound $m$, what is the minimal query time that is required).

.

  If we allow approximation of the number of distinct elements, can we get faster queries?

EDIT: I have found a related problem discussed in stackoverflow. The answer there shows a $O(n\log n\log u)$ bits algorithm that answers queries in $O(\log n)$ time.

Is this optimal?

Can we get better time/space bounds if we allow approximation?


texts: On reducing the hardness of CNF-SAT to k-Clique

texts:
CNF-SAT refers to the following problem:

  Given a boolean formula $\phi$ in conjunctive normal form, does there
  exist an assignment to the variables that satisfies $\phi$.

There are several parameters that one can associate with $\phi$:

$n$ will denote the number of variables in $\phi$.
$m$ will denote the number of clauses in $\phi$.
$N$ will denote the number of variable occurrences in $\phi$.

  Claim: For every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly
  $2^{\frac{N}{k}}$ vertices and $2^{\frac{2 N}{k}}$ edges.

  Proof Idea: Any clause in $\phi$ can be split into two clauses by adding an
  additional variable.  The positive literal gets added to one of the
  new clauses and the negative literal gets added to the other new clause.

  We make at most $k$ splits to the clauses of $\phi$ to get a new
  formula $\phi'$ such that:

  $\phi'$ has at most $N+2k$ variable occurrences.
  $\phi'$ can be expressed as $\bigwedge_{i\in[k]} \phi_{i}'$ where each $\phi_{i}'$ is a CNF formula with at most $\frac{N}{k} + 2$
  variable occurrences.
  $\phi$ is satisfiable if and only if $\phi'$ is satisfiable.

  We can look at each $\phi_{i}'$ independently and build up a list of
  all the satisfying assignments.  There are at most $2^{\frac{N}{k}+2}$
  satisfying assignments for each $\phi_{i}'$.

  The satisfying assignments for the $\phi_i'$'s will represent the
  vertices of the graph $G$.  In total, $G$ will have at most $k \cdot 2^{\frac{N}{k}+2}$ vertices.

  Vertices $v$ and $u$ are adjacent in $G$ if the following are true:

  $v$ and $u$ represent assignments for $\phi_i'$ and $\phi_j'$ respectively where $i \neq j$.
  For the variables that are in both $\phi_i'$ and $\phi_j'$, the assignments for $v$ and $u$ agree on their respective bit values.

  Now, if a $k$-Clique exists in $G$, then we get an assignment for each
  $\phi_i'$ where no two assignments disagree on bit values for the same
  variables.  As a result, these assignments can be joined to form a
  satisfying assignment for $\phi'$.

  Conversely, if a satisfying assignment exists for $\phi'$, then we can
  remove variables from this assignment to get a satsfying assignment
  for each of the $\phi_i'$'s where no two assignments have any bit
  mismatches making them form a $k$-Clique in $G$.  $\square$

Using fast matrix multiplication, we can solve $k$-Clique in $O(n^{.792 k})$ time.  Therefore, we can solve CNF-SAT in $2^{.792 N}$ time.  In fact, there is a trivial algorithm for solving CNF-SAT in $2^{.5 N}$ time.

However, it is not known if we can solve CNF-SAT in $poly(N) \cdot 2^{(1-\epsilon) \cdot n}$ time.

Question: Does there exist a constant $c$ such that for every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly $2^{\frac{c \cdot n}{k}}$ vertices and $2^{\frac{2 \cdot c \cdot n}{k}}$ edges.

Relevant Links:

Exponential Time Hypothesis: https://en.wikipedia.org/wiki/Exponential_time_hypothesis
Algorithms for $k$-Clique: http://theory.stanford.edu/~virgi/combclique-ipl-g.pdf
Sparsification Lemma: https://cseweb.ucsd.edu/~russell/ipz.pdf


texts:
I want a challenging Where's Waldo type game, where the goal is to find some pattern.
But I would want something where you can make your own puzzles, for example by randomly pulling your hand over a board.

Let me give an example.
Suppose that the board is a triangulated large triangle and every vertex is either red, blue or yellow, with the constraints as in Sperner's lemma.
(It shouldn't be too hard to fabricate such a board.)
Then after randomly assigning colors, it is challenging to find a rainbow triangle, since it is PPAD-complete.

The problem with this example is that the board needs to be huge to make it non-trivial, not to mention that for a random large board there would be many rainbow triangles, so in most cases it would be easy to find one.
I think one could reduce the board size by changing the solution from a rainbow triangle to something more complicated, like a given pattern of a dozen points.
It is important that I want the solution to be immediately verifiable, thus of constant size, so games like find a 4-coloring of this planar graph are ruled out.

  So is there some nice TFNP result that would give such a puzzle?


texts: What is an accessible introduction to Percolation Theory?

texts: What is the best place to start for someone in Computer Science with a graduate level background in linear algebra, probability theory, and graph theory?


texts: Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

texts:
It would be nice to show that $P=L$ implies $NP=NL$.  Or, $NP=NL$ implies $UP=UL$.  Or maybe, $⊕P = ⊕L$ implies $PP = PL$.

Are there any known connections between the problems: P vs L, UP vs UL, NP vs NL, ZPL vs ZPP, RL vs RP, BPP vs BPL, PP vs PL, or ⊕P vs ⊕L?

I just started to learn about probabilistic space complexity classes so for all I know there are known results or maybe this hasn't even been investigated thoroughly.

An incomplete list of results (correct me if any of them are wrong):

(1) $L \subseteq UL \subseteq NL$

(2) $L \subseteq ZPL \subseteq RL \subseteq BPL \subseteq PL$

(3) $RL \subseteq NL \subseteq PL \cap ⊕L$

(4) $PL \cup ⊕L \subseteq NC^2 \subseteq P$

One connection: if any of these problems have a positive answer, then we get $NC^2 = P$, $PSPACE = EXPTIME$, and $AL \neq AP$ where it is well known that $AL = P$ and $AP = PSPACE$.

For example, suppose that we have $PP=PL$.  Then, we get $PL = NC^2 = P = PP$.  And, $NC^2 = P$ implies $PSPACE = EXPTIME$.  Further, we can't have $AL = AP$.  Otherwise, we would get $P = PSPACE = EXPTIME$ which violates the time hierarchy theorem.

Any corrections, ideas, thoughts, results, or references are appreciated.  Thank you for reading!  :)


texts: NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

texts:
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with entries in $\{0,1\}$ that maximizes the number of vectors $v_i$ having positive dot product with $x$.

For example, for the collection of vectors given by the rows of the matrix
$$ \begin{bmatrix} -1 & -1 & -1 & -1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & +1 & -1 \\ -1 & +1 & +1 & -1 \\ -1 & -1 & -1 & -1 \end{bmatrix} $$
the optimal choice of $x$ is $[1,\ 1,\ 1,\ 0]^T$, which has positive dot products with the middle three rows.

Is this problem known to be NP-hard? If so, are any polynomial-time approximation algorithms available?

(Cross-post from mathoverflow here: https://mathoverflow.net/questions/288136/np-hardness-of-finding-0-1-vector-to-maximize-rows-of-1-1-matrix)


texts: Ensuring integral maximizer from integral linear program

texts:
An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is totally unimodular.
Suppose that we have an integral LP, how can we then efficiently find an integral maximizer? After all, the optimum may be achieved by (exponentially) many different maximizers rather than just the integral ones.

Cross-posted from CS.SE where no answers have been posted after two weeks.


texts: Are there generalizations for Chow's theorem?

texts:
The Chow's theorem as it stands holds only for a single linear threshold gate. That these gates are uniquely determined by their first $n+1$ Fourier coefficients.

Are there other circuits for which such a Chow's theorem is known to hold? Like for depth $2$ LTFs? Or are there reasons to believe that such extensions can't be true?


texts: Theorem prover fails to find simple set theory proof?

texts:
I am trying to use an automated theorem prover (SNARK) to prove a theorem in first-order logic.
Tarski claims in his "a work on mereology" that
the goal is provable from assertions 1-3 but he does not give a proof
(I have found an easy proof by contradiction).

However SNARK is currently unable to find a proof,
even with the axioms of (NBG) set theory in [1].
Any suggestions will be greatly appreciated.

Assertions:

The relation ‘part of’ is transitive:
$$\forall x,y,z. PartOf(x,y) \land PartOf(y,z) \to PartOf(x,z)$$
The sum of a class is defined as follows: x is the sum of a class alpha if alpha is contained in the ‘parts’ of x, and if when y is any part of x there is always a z belonging to alpha having parts in common with the parts of y:
$$\forall x,y,a,t. \exists z,p. SumOf(x,a) \to
(Member(t,a) \to PartOf(t,x)) \land
(PartOf(y,z) \to Member(z,a) \land PartOf(p,z) \land PartOf(p,y))$$
This was originally given in Peano-Russell notation as:
$$S=_{Df} \hat{x} \hat{\alpha} \{\alpha\subset\vec{P^‘}
x:.(y):yPx.\supset .(\exists z).z\in \alpha .\vec{P^‘}  y\cap \vec {P^‘} z\neq \Lambda \}$$
Every class which is not null has a sum:
$$\forall a. \exists m,s. Member(m,a) \to SumOf(s,a)$$

Proof Goal: The relation ‘part of’ is reflexive:
$$\forall x. PartOf(x,x)$$

[1] Automated Development of Fundamental Mathematical Theories, by Art Quaife, Kluwer Acadamic Publishers (1992)


texts:
Tries allow for efficient storage of lists of elements.  The prefixes are shared so it is space efficient.

I am looking for a similar way to efficiently store trees.  I would like to be able to check for membership and to add elements, knowing if a given tree is a subtree of some stored trees or if there exists a stored tree being a subtree of the given tree is also desirable.

I would typically store about 500 unbalanced binary trees of height less than 50.

EDIT

My application is some kind of model checker using some sort of memoization. Imagine I have a state $s$ and the following formulae: $f = \phi$ and $g = (\phi \vee \psi)$ with $\phi$ being a complex subformula, and imagine I first want to know if $f$ holds in $s$.  I check if $\phi$ holds and after a lengthy process I obtain that it is the case. Now, I want to know if $g$ holds in $s$. I would like to remember the fact that $f$ holds and to notice that $g \Rightarrow f$ so that I can derive $g$ in $s$ almost instantly.
Conversely, if I have proved that $g$ does not hold in $t$, then I want to tell that $f$ does not hold in $t$ almost instantly.

We can build a partial order on formulae, and have $g \geq f$ iff $g \Rightarrow f$.  For each state $s$, we store two sets of formulae; $L(s)$ stores the maximal formulae that hold and $l(s)$ stores the minimal formulae that do not hold. Now given a state $s$ and a formula $g$, I can see if $\exists f \in L(s), f \Rightarrow g$, or if $\exists f \in l(s), g \Rightarrow f$ in which case I am done and I know directly whether $g$ holds in $s$.

Currently, $L$ and $l$ are implemented as lists and this is clearly not optimal because I need to iterate through all stored formulae individually. If my formulae were sequences, and if the partial order was "is a prefix of" then a trie could prove much faster. Unfortunately my formulae have a tree like structure based on $\neg, \wedge$, a modal operator, and atomic propositions.

As @Raphael and @Jack points out, I could sequentialise the trees, but I fear it would not solve the problem because the partial order I am interested in would not correspond to "is a prefix of".


texts: How to improve this pseudorandom generator?

texts:
Let $f$ be a Boolean function and $\varepsilon > 0$.

There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$  with the following property.
Let $T$ be a set and $p(n)$ a polynomial.
If
$|\Pr_{r \in \{0,1 \}^n}[r \in T] -
\Pr_{r \in \{0,1 \}^{n^{\varepsilon}}}[G_f(x) \in T]| > \frac{1}{p(n)}$
for all large $n$,
then there exists a polynomial-size oracle circuit family $\{C_n\}_{n \in \mathbb{N}}$ with oracle $T$ that computes $f$ and queries $T$ non-adaptively.

Roughly speaking, if $T$ exposes generator $G_f$ then there exists a polynomial-size circuit with oracle $T$ that computes $f$.
For simplicity I will consider only oracles $T$ such that $\Pr_{r \in \{0,1 \}^{n^{\varepsilon}}}[G_f(x) \in T] =0$.  For oracles $L$ and $T$ having this property we say that $L$ expose $G_f$ not worse than $T$ if $T \subseteq L$.
I want the following generalization of this result. If $T$ exposes generator $G_f$ then there exists a polynomial-size circuit $C$ such that $C^L$ computes $f$ for every oracle $L$ that is not worse than $T$.
Unfortunately, this generator $G$ (based on Nisan-Wigderson generator) does not have this property.
Is it possible to improve $G$ for achieving my goal?
Motivation. In the cited paper ``Power from random strings'' authors consider oracles containing strings with high Kolmogorov complexity, for example oracle $R =\{x | C(x) \ge \frac{x}{2} \}$ where $C$ is some variation of Kolmogorov complexity.
It is natural to consider a spoiled oracle instead of $R$ that answer `yes' if we ask about string $x$ s.t. $C(x) \ge \frac{x}{2} + B$, answer ``no'' if we ask about string $x$ s.t. $C(x) \le \frac{x}{2} - B$ and can answer everything if $\frac{x}{2} - B < C(x) < \frac{x}{2} + B$. Here $B$ is bound for example constant.
If there exists a wishful generator which properties decribed above then some results from ``Power from random strings'' can be generalized for such family of oracles.


texts: Other types of uniformity for circuits (incl. by small modifications)

texts:
I've seen poly-time and logspace uniformity for circuit families, typically defined as the existence of a poly-time/logspace Turing machine "generator" that outputs the correctly sized circuit $C_n$ on input $n$. These restrictions upper bound the power of circuit families by requiring that they are computationally generated.

I was wondering what happens when you change the generator model. Here are two (vague) questions:

  Are there other useful types of uniformity for circuit families?
  Are there interesting "generators" besides time/space bounded TMs? For example, consider families that progress from $C_i$ to $C_{i+1}$ by "small" modifications of the circuit. Can these be broad and have interesting complexity properties?

The idea in #2 is far too inclusive, since it allows things like simple recursive definitions. I am more interested in severe restrictions on the range of possible families by limiting the types of modifications.


texts:
The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $\phi$ on variables $X_1, \ldots, X_n, Y_1, \ldots, Y_m$ of the form $\bigvee_{1 \leq j \leq k} X_{n_j} \land Y_{m_j}$. This problem is known to be #P-complete [Provan, J. S., Ball, M. O. (1983). The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4), 777-788.].

Is it known whether #PP2DNF is hard to approximate or not?


texts:
I have an undirected graph on matris by vertex adjacency relations like that;

/*    a  b  c  d
 * a -1  0  1  1
 * b  0 -1  1  1
 * c  1  1 -1  1
 * d  1  1  1 -1
 *
 */

I want to draw this graph on cordinate system. What's the algorithm that gives each vertex position (x,y) by any method(force-directed, spring vs) with no intersection between edges or minimum intersection?
Thanks.


texts: Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum

texts:
This question arose from a discussion between a friend and I.

$A$ is a sequence of length $T$ where for any $a_i$ in $A$,  $a_i \in  \left\{{1, 2, 3}\right\}$

$B$ is a sequence of length $U$ where for any $b_i$ in $B$,  $b_i \in  \left\{{1, 2, 3}\right\}$

And the following conditions:

1) They possess equal sum,

$N = \sum_{\forall a \in A} a = \sum_{\forall b \in B} b$

2)  They don't possess sub-sequences starting at the head of equal sum,

$\sum_{i=1}^c a_i \neq \sum_{i=1}^d b_i$

for any $c < T$ and $d < U$,

where $a_i \in A$ and $b_i \in B$

Question: For given $N$, find an algorithm that calculates in polynomial time the number of possible pairs $(A, B)$ that satisfy these conditions.

It's very easy to write an algorithm that satisfies condition 1) using dynamic programming, but I simply cannot figure out how to make it satisfy 2) as well.

Good luck!


texts: Is the theory of asymptotic bounds finitely axiomatizable?

texts:
Let $F$ be the set of functions over real numbers.
Consider the structure $M = \langle F, <, \leq, =, \geq, > \rangle$ where the $<, \leq, =, \geq, >$ are defined as asymptotic notions $o$, $O$, $\Theta$, $\Omega$, $\omega$. For example, for $f,g\in F$, $f\leq g$ iff $f \in O(g)$.
Consider the first-order theory of this structure $T = Th(M)$.
Questions:

Is $T$ finitely axiomatizable?
Does $T$ have quantifier elimination property?
Is $T$ a decidable theory?

Is there a references discussing logical and model theoretic properties of this theory (statements similar to those above)?


texts: Is conversion of PRAM to parameter number of processors trivial

texts:
In section 2 of chapter 4 of Kumar the idea of scaling down is discussed.
It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "shifting" it from the  number of processors to time.

Two things are on my mind with respect to this question.

I'm sure it is interesting to come up with efficient schemes for such conversion for dedicated hardware solutions (say , given the architecture of CUDA , one can implement efficient algorithms based on the size of the different cache levels etc.)
Is it interesting from the theory point of view? Can I say something about it without relating to a particular hardware solution? (Say , general schemes for work efficient preserving conversions)
I'm starting to see some possible connections to parameterized complexity. Is there any known work on the area? So far , Iv'e seen two popular papers and that

Any leads?


texts: Optimal evaluation of polynomials / rational functions

texts:
A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the poynomial:

$$P(x) = \sum_{k=0}^n \binom{n}{k} x^k$$

with $n$ known. One technique would be to precompute the coefficients and evaluate the polynomial using the Horner form. However that will take time linear in $n$, whereas we might observe that

$$P(x) = (x+1)^n$$

which can be evaluated in $\mathcal{O}(\log n)$ multiplications.

In general, identifying patterns inside a polynomial that lend themselves to simplification can speed up evaluation. This is not always obvious

For instance $75938+99169x+45123x^2-805x^3-10745x^4-5523x^5-1309x^6-127x^7$ can also be written as $(x+5)^7-(2x+3)^7$.

Things become even more complicated once multiple variables are introduced, or when we generalize to rational functions.

Clearly there exists an algorithm to find the most efficient computation of a given expression in terms of arithmetic operations and variable assignments: iterate through all possible computations in order of their number of operations, decide if they are equivalent to the target equation and if so stop.

This of course is cost prohibitive. Is there a known efficient algorithm to solve this problem, or at least to approximate it?


texts:
Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer.
This is just a shift if $c$ is a power of two, but what about other numbers?
Can we do it with a constant depth circuit for every $c$?
What about $c=3$?

ps. I know that computing $x\bmod c$ is hard, but this seems unrelated.


texts: KKT-like conditions for values close to optimal solution

texts:
The KKT conditions are necessary and sufficient conditions for problems where we maximize over a convex function subject to linear inequality and equality constraints. That is $x^*$ is an optimal point iff it satisfies the KKT conditions.

My question is, are there similar necessary and/or sufficient conditions for points $x$ near $x^*$?


texts: Permutations of maximum period: applications to Rubik's cube

texts:
Dear Mods: this may be a non-research question, but I am asking it because from my knowledge, the question appears nontrivial.

This video claims that a Rubik's cube can be "solved" from any starting position with the repeated application of two fixed moves. The method is easily seen as wrong because the specific moves he suggests actually leave the bottom right $2\times 2 \times 3$ block unaffected. My question is more general: does there exist a finite set of moves which if applied repeatedly from any starting position, yield a solved Rubik's cube?

Moves can be thought of as permutations on the set configurations of a Rubik's cube. A solved Rubik's cube is a specific configuration of interest. If these moves get you from any configuration to a solved configuration, then (by symmetry) these moves must get you from any configuration to any other configuration. This means these moves constitute a permutation of maximum period. Does such a permutation even exist? What is known about the existence of such a permutation?


texts: Converting a Hardware description language to a functional programming language

texts: I am looking for some guidelines on converting a Hardware description language such as VHDL or Verilog to a Typed Language. The reason I want to do this is to formally verify a hardware whose behavioral description is written in HDL.


texts:
In 1995, Russell Impagliazzo proposed five complexity worlds:

1- Algorithmica: $P=NP$ with all the amazing consequences.

2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) but are efficiently solvable in the average-case.

3- Pessiland: There exist average-case $NP$-complete problems but one-way functions do not exist. This implies that we can not generate hard instances of $NP$-complete problem with known solution.

4- Minicrypt: One-way functions exist but public-key cryptographic systems are impossible

5- Cryptomania: Public-key cryptographic systems exist and secure communication is possible.

  Which world is favored by the recent advances in computational complexity? What is the best evidence for the choice?

Russell Impagliazzo, A Personal View of Average-Case Complexity
, 1995

Impagliazzo's Five Worlds,
The Computational Complexity
     blog


texts: Hardness of geometric area minimization problem

texts:
This question is a generalized variant of: Hardness of perimeter minimization?

Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.

  What is the complexity of finding $x, y, z$ such that $xy+xz+yz$ has minimum value? Is there any subexponential algorithm that solves this problem? Does the problem become easier when integers are encoded in unary?

Edit Motivation: I'm interested in the following generalized problem:

Input: intgers $C$ and $K$

Problem: Find integers $x$, $y$, and $z$ such that $xyz\ge C$ and $xy+xz+yz\le K$


texts: Hard problems on subclasses of planar cubic bipartite graphs

texts:
Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem and perfect P3 matching problem. I'm looking for a reference on interesting subclasses of planar cubic bipartite graphs. An interesting subclass contains infinite number of graphs and excludes infinite number of graphs.

More importantly, Which hard problems do remain hard on nontrivial subclasses of planar cubic bipartite graphs?


texts: Is graph connectivity definable in existential MSO with vertices and edges?

texts:
Can $\exists$MSO$_2$ express graph connectivity?

Monadic SO (MSO) is the fragment of second-order logic in which the second-order quantifiers range over relations of arity 1 only.
$\exists$MSO is the fragment of MSO in which only non-negated existential second-order quantification is allowed.

MSO over graphs (sometimes denoted MSO$_1$) has as its universe vertices only.
In contrast, the variant MSO$_2$ has as its universe vertices as well as edges.

It is well-known that MSO$_2$ is more expressive than MSO$_1$; for instance, the former can express the existence of a Hamiltonian cycle (see Libkin's Elements of Finite Model Theory, Exercise 7.4), while the latter cannot (Libkin's proof of Corollary 7.24 is a neat pumping argument due to Makowsky).

It is also standard that $\exists$MSO$_1$ cannot express graph connectivity.  One proof is via Hanf locality due to Fagin, Stockmeyer, and Vardi (Information and Computation 1995).  This paper states: "we consider it possible that connectivity is not in monadic NP, even in the presence of arbitrary built-in relations of arbitrary degree"; the edge relation has arity 2 so they are conjecturing that the answer to my question is negative (monadic NP is the same as $\exists$MSO).
(Removed last clause as per comment of Emil Jeřábek.)

More recently, Courcelle and Engelfriet's textbook on MSO mentions that it is possible to express "$X$ is a set of edges forming a directed path from $s$ to $t$" in MSO$_2$.  However, their formula uses universal quantification.  It is not immediately obvious whether this is necessary, at least for the concept of connectivity of an undirected graph.


texts: Combinators for the Primitive Recursive Functions

texts: It is well-known that the S and K combinators are Turing Complete. Are there combinators that suffice to yield (only) the primitive recursive functions?


texts:
Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length.  Does there exist an arrangement of these triangles in two dimensions (with any arbitrary translation or rotation) such that:

Every pair of triangles share a finite number points on their perimeter (can't have collinear, touching sides) and do not intersect
If two triangles are adjacent in $G$, they share a vertex (a stronger restriction than just sharing any point on the perimeter)

Here are two valid non-isomorphic arrangements for $K_3$:

$K_n$ has no arrangement for $n>5$.

$\forall n \geq 3$, $C_n$ has an arrangement as a "necklace" of triangles.  One such arrangement for $C_4$ is shown:

What is the complexity of this problem?  What algorithm could you use to recognize arrangeable graphs (or at least a sketch of how it would work)?  Would this algorithm be able to provide a solution rather than just assert its existence?

One observation is that if $G$ is arrangeable, all of its subgraphs are as well.


texts: Difference lists in functional programming

texts:
The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), which is something I've recently been interested in. This led me to find the difference list implementation for Haskell. I have two questions (forgive/correct me if I should make them two different questions on the StackExchange).

The simple question is, is anyone aware of academic consideration of difference lists in functional programming and/or implementations besides the one in the Haskell library? jbapple's answer didn't give a citation for difference lists (difference lists in logic programming exist in the lore and in a couple of sources which I have Around Here Somewhere (TM)). Before finding the Haskell implementation I wasn't aware that the idea had leaped from logic to functional programming. Granted, the Haskell difference lists are something of a natural use of higher-order functions and work quite differently from the ones in logic programming, but the interface is certainly similar.

The more interesting (and far fuzzier-headed) thing I wanted to ask about is whether the claimed asymptotic upper bound for the aforementioned Haskell difference list library seems correct/plausible. My confusion may be because I am missing something about obvious about complexity reasoning with laziness, but the claimed bounds only make sense to me if substitution over a large data structure (or closure formation, or variable lookup, or something) always takes constant time. Or is the "catch" simply that there's no bound on the running time for "head" and "tail" precisely because those operations may have to plow through an arbitrary pile of deferred computations/substitutions?


texts:
Consider the space of all imperative programs.

From the view of mathematical analysis, what kind of space is it?
Is it an algebraic structure?

Please also give references.

Editing of the question is welcome.


texts: Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

texts:
A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground.

  In the BGS 1975 proof that there exists a language $B$ such that $P^B \neq NP^B$. To best available knowledge, what complexity class is $B$ in?
  Fill in the blank ("$?$") if possible, or analyze as best possible: if there existed a $B'$ in class "$?$" such that $P^{B'} \neq NP^{B'}$, then $P \neq NP$.


texts: Busy Beaver Equivalent for the Untyped Lambda Calculus

texts:
In the same way that the Busy Beaver function is defined for Turing Machines, we could define a similar function for the untyped lambda calculus:

Over all terms in the ULC composed of n abstractions, variables and applications, which has the longest normal form?

This could be defined in a couple ways: we could consider only strongly normalizing ULC terms, or we could look for the longest normal form over all replacements.

Clearly, this function is not computable for arbitrarily large n, for the same reason as for the standard Busy Beaver function. However, I am interested in whether anything is known about this function for small values of n. What values is it known for? What bounds exists for higher n? For what n is the value known to be independent of ZFC?


texts: Computing size of permutation group from generators

texts: You're given $k$ permutations $a_1,\dots,a_k$. Consider closure of this set under the composition operation. What are most efficient and simple algorithms to calculate the size of this closure?


texts: Given a partition and an element, find the subset that includes this element

texts:
I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am mostly interested in some general background on this problem. I'm stuck because I do not know of a canonical "name" for this problem.
Does this problem have a name, or is there a closely related problem that might generate some useful hits?


texts: Status of Raghavendra's algorithm for solving linear systems in finite fields

texts:
In 2012, Lipton wrote a blog entry about a new algorithm for solving linear systems over finite fields by Prasad Raghavendra.

The link to Raghavendra's draft paper on the topic is now dead, and I can't find anything on the subject on Raghavendra's website.

Is the result correct? Is a write-up available anywhere?

Thanks!


texts: Is there an algorithm that finds the forbidden minors?

texts:
The Robertson–Seymour theorem says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors.

  Is there an algorithm that for an input $\mathcal G$ outputs the forbidden minors or is this undecidable?

Obviously, the answer might depend on how $\mathcal G$ is described in the input.
For example, if $\mathcal G$ is given by an $M_\mathcal G$ that can decide membership, we cannot even decide whether $M_\mathcal G$ ever rejects anything.
If $\mathcal G$ is given by finitely many forbidden minors - well, that's what we're looking for.
I would be curious to know the answer if $M_\mathcal G$ is guaranteed to stop on any $G$ in some fixed amount of time in $|G|$.
I'm also interested in any related results, where $\mathcal G$ is proved to be minor-closed with some other certificate (like in case of $TFNP$ or WRONG PROOF).

Update: The first version of my question turned out to be quite easy, based on the ideas of Marzio and Kimpel, consider the following construction.
$M_\mathcal G$  accepts a graph on $n$ vertices if and only if $M$ does not halt in $n$ steps. This is minor closed and the running time depends only on $|G|$.


texts: Properties expressible in 2-CNF or 2-SAT

texts:
How does one show that a certain property cannot be expressed in 2-CNF (2-SAT)?  Are there any games, such as pebble games?  It seems that the classical black pebble game and the black-white pebble game are unsuitable for this (they are PSPACE complete, according to Hertel and Pitassi, SIAM J of Computing, 2010).

Or any techniques other than games?

Edit:  I was thinking of properties that involve counting (or cardinality) of an unknown predicate (SO predicate, as finite model theorists would say).  For example, as in Clique or unweighted Matching.
(a) Clique: Is there a clique $C$ in the given graph $G$ such that $|C| \ge$ some given number $K$? $~$ (b) Matching: Is there a matching $M$ in $G$ such that $|M| \ge K$?

Can 2-SAT count?  Does it have a counting mechanism?  Seems doubtful.


texts: Im working on image clustering (finding duplicates). I have a metric for images, it uses histogram features (mean, dispersion, skewnewss) for each color channel. So there are 9 dimensions. It is quite easy to calculate distance between two images (L1), but I don't know how to cluster them. Is there any clustering algorithms that use only the metric, other than bruteforce? Wikipedia article tells about projected clustering, how can it be implemented?


texts:
UniqueSAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. Unique SAT is CoNP-hard and $US$-complete.

  What is the density of UniqueSAT?

I know only weak evidence to support that it can not be sparse: All known CoNP-complete sets are dense and UniqueSAT is CoNP-hard.

Here, density $D$ of a set $S$ refers to the number of strings of length less than $n$ in the language. A set $S$ is exponentially dense if its density is $D=\Omega(2^{n^\epsilon})$ for some $\epsilon \gt 0$ and for infinitely many $n$ and sparse if $D$= $O(poly(n))$.

Motivation: I would like to link the existence of Karp reduction from SAT to UniqueSAT to the existence of "large gap" between the density of the two problems. Mahaney's Theorem gives evidence that Karp reduction can not exist between two $NP$ sets with densities separated by "large gap".


texts: Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?

texts:
Many theorems and "paradoxes" - Cantor's diagonalization, undecidability of hatling, undeciability of Kolmogorov complexity, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. - all have essentially the same proof by diagonalization (note that this is more specific than that they can all be proved by diagonalization; rather, it feels that all of these theorems really use the same diagonalization; for more details see, e.g. Yanofsky, or for a much more brief and less formalized account  my answer to this question).

In a comment on the above-mentioned question, Sasho Nikolov pointed out that most of those were special cases of Lawvere's Fixed Point Theorem. If they were all special cases, then this would be a good way to capture the above idea: there really would be one result with one proof (Lawvere's) from which all of the above followed as direct corollaries.

Now, for Gödel Incompleteness and undecidability of the halting problem and their friends, it is well-known that they follow from Lawvere's Fixed Point Theorem (see, e.g., here, here or Yanofsky). But I don't immediately see how to do that for the undecidability of Kolmogorov complexity, despite the fact that the underlying proof is somehow "the same." So:

  Is the undecidability of Kolmogorov complexity a quick corollary - requiring no additional diagonalization - of Lawvere's Fixed Point Theorem?


texts: Is it possible to check equality of equi-recursive types, or recursive λ-terms?

texts:
Can we determine if two λ-terms are equal?

Given two lambda terms, let's say they are equal if their (possibly infinite) Bohm trees are. Under this definition, for example, (Y λr.λt.(t r)) and (Y λr.λt.(t (λt. (t r)))) are equal, despite not having a normal form, because both terms have the same infinite Bohm trees. I believe this problem, in general, is undecidable. Is there any efficient, preferably simple algorithm capable of determining if two λ-terms are equal for some large class of common terms? The main problem, I believe, is finding the right series of reductions that make two terms identical without getting stuck in an infinite loop.

Can we determine if two equi-recursive types are equal?

Suppose we extend CoC with equi-recursive types. Naturally, type checking the application of a f : ∀ (x : A) -> B to a x : A' requires you to check if A == A'. In plain CoC, this can be done by merely reducing both sides to normal form and checking if they are equal. In the presence of equi-recursive types, though, that isn't possible. Is there any algorithm capable of checking if two types are equal in such language?

Note: I'm not sure if those questions are equivalent and I felt that asking another question would be spammy, so I've asked both in this same thread.


texts: The evaluation problem for AC$^0_d$ formulas is in FO

texts:
Let $d \in \mathbb{N}$ be arbitrary. Let $\mathsf{AC^0_d}$-Eval be the following promise problem:
Input: A depth $d$ formula $\varphi(x)$ and a binary string $a$.
Output: $\varphi(a)$
I am looking for a reference to cite for $\mathsf{AC^0_d}$-Eval
$\in \mathsf{FO}$.

Notes

$\mathsf{FO} = \mathsf{LH} = \mathsf{AltTime}(O(1), O(\lg n)) = \mathsf{DLogTimeUniform\ AC^0}$.

$\mathsf{AltTime}(a(n), t(n))$ is the class of alternating Tuition machines with at most $a(n)$ alternations and $t(n)$ time. Some authors use other notations like ATime, AAltTime,  ATimeAlt, etc. to refer to the class of alternating Turning machines with bounds on alternations and time. For details of the definition of alternating Turing machines with small amount of resources refer to Ruzzo, "On uniform circuit complexity", 1981.


texts: How is this graphical representation of SAT/CSP instances called?

texts:
Given a CNF formula (SAT problem), we can construct the constraint/dependency graph, which contains a vertex for each variable and a hyperedge for each clause. Same goes for CSPs, where we have a hyperedge for each constraint.

But given a CNF formula, we could also define a (slightly larger) graph that has literals as vertices and clauses as hyperedges, where each edge is incident to each literal it contains. This can analogously be done for a CSP.

How is the latter graph called?


texts: What is a really good problem to get your hands dirty in computational-geometry?

texts:
Computational geometry is an area I find pretty interesting, and I'd like to devote about a month or two to a project that will introduce me to this and help me learn key concepts.

What is a good way to approach this and what are the key concepts I should be sure I'm introduced too?


texts: In my work arose the problem of classification CFL under rational functions images. In other terms, what class of languages form languages $T(L)$ , for fixed context free language $L$ and  deterministic finite state transducer $T$. I've obtained some easy results like Dyck language with two braces corresponds to CFL and Dyck language with one brace is a strict subset of CFL, now there are a few problems that are still interested to me, but I can't believe that nobody have discovered it yet. Are there any papers on this subject? Googling classification of CFL or Rational Functions (Deterministic FST) + CFL gives bad result.


texts: What one bit of computable information would you most like to know?

texts:
If you could ask one computational yes/no question, what would it be?

To be precise, you get to specify a Turing machine (in a convenient language) and an oracle will tell you whether or not it halts. You only get one query (let's say filesize < 1TB); it's answered immediately; and you know for a fact that the answer you get is correct.

For example, you could ask "Does there exist a proof that $\mathsf{NP}\ne\mathsf{P}$?" by specifying a Turing machine that enumerates all proofs and halts when it finds such a proof. But is that the best question to ask?


texts: If we have a $2^{n^a}$ algorithm to $K$-$SAT$ where $a<1$ for all $K>2$ then $ETH$ fails and literature gives consequences. What are the consequences if $a=o(1)$?


texts: What are the best known reductions from SAT to CNF-SAT?

texts:
Problems

  Let SAT denote the following problem:

  Given a boolean formula, does there exist a satisfying assignment?

  Let CNF-SAT denote the following problem:

  Given a boolean formula in conjunctive normal form, does there exist a
  satisfying assignment?

Note: CNF-SAT is more restrictive because it requires that the boolean formulas be in conjunctive normal form.

Parameters

Let's consider some parameters that we associate with a boolean formula.  Let $n$ denote the number of variables and $m$ denotes the number of literal occurrences (or we could say the total size of the formula).

Question

  Consider a polynomial time reduction that reduces a SAT instance $\phi$ with $n$ variables and $m$ literal occurrences to a CNF-SAT instance $\phi^{\prime}$ with $v(n,m)$ variables and $l(n,m)$ literal occurrences for some functions $v(n,m)$ and $l(n,m)$.

  What are the best known bounds on $v(n,m)$ and $l(n,m)$?

As pointed out by qsp in the comments below, Tseytin transformation is a reduction where $v(n,m) = O(m)$ and $l(n,m) = O(m)$.  However, does there exist a reduction where $v(n,m) = O(n \sqrt{m})$ and $l(n,m) = O(m^2)$?  What about a reduction with $v(n,m) = O(n^2)$ and $l(n,m) = O(m^2)$?

Revised Question

  Does there exist a polynomial time reduction with functions $f(n)$ and $g(m)$ such that:

  $l(n,m) = \mathrm{poly}(m)$
  $v(n,m) = f(n) \cdot g(m)$
  $g(m) = o(m)$

Any relevant references are greatly appreciated!  Thank you.


texts: Good resources to learn loopy belief propagation

texts: What are some of the good references to understand loopy belief propagation and the need for it? I am looking for both theory and applications (for instance in coding/information and learning theory).


texts: Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"

texts:
I've been toying recently with the idea that the set of all "real-world" paradoxes...such as the Liar's Paradox, Russell's Paradox, the Unexpected Hanging Paradox, the Berry paradox, etc. ...correlates precisely with the set of techniques that can be used to prove that the halting problem is undecidable.  (I believe the same holds for Godel's first incompleteness theorem, but that might be off-topic.)

A post on another thread (relating to the halting problem), coupled with my interest in recent days in this notion, led me to post this.  I am curious as to whether or not the answer to either of the following two meta-mathematical questions is 'yes':

1)  Is there a technique that can be used to prove the halting problem that has nothing to do with any paradox?

2)  Is there any paradox that cannot be used to prove the halting problem?

For the record, I recently came up with a (slightly garbled, but probably correct) proof that HP is undecidable based on the Unexpected Hanging paradox.  I believe that the answer to both of the above questions is 'no,' but I'm not sure how to establish this.

If anyone can offer a counterexample to my claim (on either question), I'd love to hear it.  I realize that I've left the term paradox undefined.  Ideally, I'd like to think that a reasonable definition of paradox might be crafted in terms of the halting problem.

(Also, I've always been curious as to whether or not there's a way to express paradoxes mathematically...that's another part of the motivation for asking this.  I've always wondered if there is any way to figure out precisely how many "basically distinct" paradoxes there are, and if there's a way to prove how many there are.)

Thanks,

Philip

EDIT:  I'm trying to clarify, because some posters think that my question is off-topic.  What I am referring to is the notion that a paradox, such as the liar's paradox, the Berry paradox, unexpected hanging paradox, etc., could be used intuitively as a guide for proving the Halting problem.  As an example, Turing used logic similar to Godel's in proving that the halting problem is undecidable; in that sense, I think one could argue that this halting problem proof is "based on" the liar's paradox.  The question, again, is:  is there any paradox that cannot be used to prove THP, or any proof that doesn't use a paradox?

If you believe that this is somehow less on-topic to TCS than, say, the Baker-Gill-Solovay result, please let me know why you think so.

EDIT #2:  I am now trying to more clearly define what I mean by a "paradox."  By a paradox, I mean a natural language situation, idea, or sentence that is intuitively and inherently contradictory.  In a Wikipedia article, they refer to this type of paradox as an "antimony."

I'm not referring to paradoxes that do not lead to an inherently absurd seeming result; i.e., I have no interest in the Obama paradox, or even less blatant paradoxes such as the chicken-and-the-egg paradox.  I am also not interested in paradoxes that seem philosophical but not logical, e.g., Zeno's paradox.

It's difficult to really nail down what I mean by "paradox," so here's a partial list of paradoxes that are relevant:

liar's

Russell's/barber

Berry

Quine

Curry's

Most, but not all of the paradoxes listed in this Wikipedia article under the heading of "Logic" other than vagueness are relevant.  Another question I am wondering about is Newcomb's paradox, or the psychic paradox.

Thanks to anyone who has any ideas on this.  In particular, one way to answer the question that I would appreciate is:  Can you come up with a reasonable way to define/capture the notion of paradox that I'm referring to?

I apologize if this question, as originally asked, was vague or unclear.


texts: Jointly Establishing a Shared Random String for NIZK proofs of knowledge

texts:
If OWFs exist, then a Shared Random String for

NIZK proofs (of membership) can be established by:

verifier commits a random string of the same length using statistically hiding commitment

prover sends random string of the same length

verifier opens the commitments

the xor of the commited bits and the prover's string is used as the shared random string

The problem with using this for NIZK proofs of knowledge is that the

above protocol is not (at least not obviously) simulable for the prover.

  Is there a known concrete obstacle to being able to establish

  a Shared Random String for NIZK proofs of knowledge?

  (For example, showing that such a protocol can't be black-box zero knowledge?)

If no, is there a plausible computaional assumption that is known to suffice for doing so?


texts: Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$

texts:
As pointed out explicitly by Emil Jeřábek here:

  Even with Turing reductions, $\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$ would still be a breakthrough (and completely unexpected) result.

So the expectation is that $\exists\mathbb{R}$ (existential theory of reals) is significantly easier than $\mathbf{PSPACE}$.

It is nice to have some expectation, but are there conditional separations of $\exists\mathbb{R}$, $\exists\mathbb{R}\cup\mathbb{co}\exists\mathbb{R}$ or $\mathbf{P}^{\exists\mathbb{R}}$ from $\mathbf{PSPACE}$ that can actually be achieved to justify those expectations?

Let us conditionally assume that the counting hierarchy would count as significantly easier than $\mathbf{PSPACE}$. Here Scott Aaronson vaguely remembers:

  indeed it’s in the counting hierarchy I think

Is his vague recollection correct? Is there at least some paper which could explain where those vague recollections came from, even if it doesn't directly prove this?

Here is another argument why $\exists\mathbb{R}$ should be significantly easier than $\mathbf{PSPACE}$:

  I think this is highly unlikely. $\mathbf{PSPACE}$ is closed under complement,and I don't think $\exists\mathbb{R}$ is expected to be (though I don't know of any strong consequence of this)

If we conditionally assume that $\exists\mathbb{R}$ is not closed under complement, how significant could we separate it from $\mathbf{PSPACE}$ then? Can we at least separate $\exists\mathbb{R}\cup\mathbb{co}\exists\mathbb{R}$ from $\mathbf{PSPACE}$?


texts: NP-hardness for one-dimensional facility location problem with entrance fee for each customer

texts:
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note that these facilities can be located anywhere on the real line. Each facility $j\in [m]$ is associated with an entrance fee $f_j$, such as the ticket money for a swimming pool. Given a location profile $(y_1, \dots, y_m)\in \mathcal{R}^m$ for the facilities($(y_1, \dots, y_m)$ is not necessarily ordered), the cost for customer $i$ at facility $j$ is $c_{ij} = |x_i- y_j|+f_j$, which can be understood as the aggregate money of the travelling cost and the entrance fee when you taxi to a swimming pool and purchase a ticket to swim inside. And the customer will always choose the facility so as to minimize her cost.
Our goal is to find a location profile $(y_1, \dots, y_m)$ for the given $m$ facilities such that the total minimum cost
$$\sum_{i\in [n]}\min_{j\in [m]}c_{ij}$$
is minimized.
An easy but critical obserbation is that there is an optimal solution where each facility is located in the median agent of the continuous region of agents it serves. If we have identical entrance fees, we only need to find the optimal $m$ continuous partitions, which can be solved by dynamic programming in $O(mn^2)$. For the general case, similar DP algortihm runs in $O(2^mn^2)$. The algorithm, however, is exponential in $m$ and only makes sense after we've proved the problem is NP-hard. Another observation which may be helpful is that for if we have known the optimal $m$ continuous partitions, we just assign the facility of the $k$-th smallest entrance fee to the partition of the $k$-th most customers.
So is this problem NP-hard?  Or is there an algorithm running in polynomial time?
Update
Below is the detailed DP algorithms for the special case where all entrance fees are identical and the general case:

For the spcial case, denote by $M(i,j,k)$ the minimum total cost when customer $i$ is in the $k$-th partition and customer $j$ the right boundary of this partition. Depending on whether or not customer $i-1$ is still in the $k$-partition, we derive the following transition function:
$$M(i,j,k)=  \min\{M(i-1,j,k), M(i-1,i-1,k-1)+c(i,j)\}$$
where $c(i,j)$ is the minimum total cost of partition $[i,j]$, i.e., total cost for these customers when exact one facility is located in the median of $[i,j]$.
Obvious, this DP runs in $O(mn^2)$.

For the general case, the key difference is that we have to decide which facility is located in the rightmost partition since now facilities are heterogeneous. Similarly we denote by $M(i,j,F)$ the minimum total cost when customer $i$ is in the rightmost partiton, customer $j$ is the right boundary of this partition and $F$ is the set of facilities to be located. Similarly again, we can derive the following transition function:
$$M(i,j,F)=  \min\{M(i-1,j,F), \\ \min_{s\in F}\{M(i-1,i-1,F\setminus\{s\})+c^{\prime}(i,j,f_s)\}\}$$
where $c^{\prime}(i,j,f_s)$ is the total cost of $[i,j]$ when a facility with entrance fee $f_s$ is locate in the median of $[i,j]$.
This DP runs in $O(2^mn^2)$


texts: Lower bounds on simple hash table operations?

texts:
There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash table with (possibly amortized) worst-case O(1) lookups, insertions, and deletions?

Thanks!


texts: Design a sampling process to select an element with probability proportional to its appear probability in a simulation

texts:
We are given a black box $A$ that can do a simulation. Each time running box A gives a sample $S \in 2^X$ where $X$ is a finite ground set.

Let $\Pr[x]$ be the probability that $x \in X$ appears in the sample $S$.

We try to design a sampling process $B$ which can produce an element in $X$ randomly.

Let $\Pr_1[x]$ be the probability that $x$ is produced by $B$.

We need that $\Pr_1[y]=\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$ for each $y \in X$.  An approximately correct algorithm would be OK too, i.e., $\Pr_1[y] \approx\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$.

How to design such a sampling process $B$ by using the black box $A$?

First try:

1 run A once and obtain a sample $S$.

2 select an element from $S$ uniformly at random.

3 return $x$.

Intuition: First, the probability that $x \in S$ is $\Pr[x]$. In the second step, each element in $S$ is selected with probability $1/|S|$. The expected value of $|S|$ is actually $\sum_{x \in X} \Pr[x]$. At the first glance, the probability that $y$ is returned seems to be  $\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$. However, that $x \in S$ and $|S|$ are not independent.

Counter Example:
Suppose $X=\{1,2\}$ and the distribution associated with $A$ is $\Pr[\{1\}]=0.5$ and $\Pr[\{1,2\}]=0.5$. Then $\Pr_1[1]=0.5+0.5*0.5=0.75$. However, $\Pr[1]/(\Pr[1]+\Pr[2])=1/(1+0.5)=2/3$.

Any help is appreciated.


texts: What's the difference between online and incremental optimization?

texts:
Recently I've read some stuff about incremental optimization problems, but I can't see what's the difference between those and online optimization problems. My impression is that I can define every online problem as an incremental counterpart (the reverse is clearly true).

Here go the (not very formal) definitions. In an incremental problem, one is given a sequence of instances of an optimization problem. The (i+1)-th instance is an "extension" of the i-th one. The (i+1)-th solution must be calculated without knowledge of the "future" instances, and has to keep the decisions made at the i-th solution. The classical example is with the k-median problem: after opening k facilities, one wants to have k' > k facilities but does not want to demolish the old ones.

In an online problem, (the usual definition is that) one is given a sequence of "requests". Here, one also has to answer a request without knowledge of the future requests. One wants to optimize the cost/gain of answering the sequence as a whole.

I believe that for any online problem I can define an "offline" optimization problem that fits the incremental definition (and what I usually see is the reverse). If the definitions are equivalent, what is the point of using a different name for the same concept?


texts: Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?

texts: It is well-known that in a $2$-player zero sum game if one player plays a regret minimizing mixed strategy, and the other player best-responds at each round to that mixed strategy, we are guaranteed convergence to an approximate Nash Equilibrium in poly-time. See e.g. (https://theory.stanford.edu/~tim/f13/l/l17.pdf). My question is suppose that one player is playing a no-regret strategy, and the other play best-responds to a sample from the mixed strategy of her opponent, rather than to the mixed strategy. Is it still true that the empirical average of both strategies will converge to Nash in poly-time?


texts: Locating a set of 5 geometrically constrained points within a cloud of points

texts:
What is the most efficient way to find a set of 5 geometrically constrained, non-collinear points within a 3D point cloud of, for example, 100 points?

All points are expressed with respect to a single world coordinate system.


texts: Computational complexity of clustering algorithms

texts:
My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space.

Suppose further that the pairwise dissimilarity matrix $\Delta$ of $n\times n$ dimensions is already computed and that we have already spent $O(m\cdot n^2)$ steps. What is then the time complexity just of

hierarchical clustering (HC) using Ward's linkage
HC using complete linkage
HC using average linkage
HC using single linkage
$k$-medoid approach
$k$-means approach

Is there any benefit if the dissimilarity matrix $\Delta$ is not already computed? As I understand it is necessary for HC and $k$-medoid approach but not for $k$--means?

Thank you for your help!


texts: Proof of $LP$ is in $coNP$ without showing it is in $P$?

texts:
Is there a proof that linear programming is in $coNP$ without showing it is in $P$?
If so what is the strategy?


texts: Are there any practical applications of a faster algorithm to compute Huffman codes?

texts:
Which practical problem would benefit from a technique to compute optimal prefix free codes faster (say, faster than O(sigma log sigma) on sigma input symbols)?

When compressing a source of n symbols over al alphabet of size sigma, computing the Huffman code takes time within O(sigma log sigma), while compression and decompression takes time within O(n), typically much larger than sigma log sigma. So, is it useless to improve on this O(sigma log sigma) or are there applications where the running time of computing the optimal code does matter?

Background:

A new algorithm:

In 2016, I describe (at the peer reviewed scientific conference CPM) a new (adaptive) algorithm for computing optimal prefix free codes (http://arxiv.org/abs/1602.00023 Optimal Prefix Free Codes With Partial Sorting), inspired by van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with a relatively minor extension of Karp et al.'s Deferred Data Structure to partially sort a multiset accordingly to the queries performed on it (known since 1988). This algorithm is (optimally) taking advantage of some easy instances, such as when the frequencies cluster in a few groups of frequencies all within a factor of two of each other.

Experimental Results:

For the extended version, I implemented this algorithm in python (https://gitlab.com/FineGrainedAnalysis/PrefixFreeCodes) and tested it on word frequencies in English texts (from the Gutenberg project): I will update the arxiv version shortly with a description. The experiments suggest that the improvement cannot be by more than a constant factor.

Negative comments:

On the other hand, I am also told that the concept that "the problem of computing optimal prefix free codes faster is important because the Huffman code is used in main data compression standards" is "completely invalid", as none of implementations of standards contains routines for constructing Huffman codes, because Huffman codes are pre-constructed and are kept in the form of look-up tables.

Partial answers:

Various people (e.g. van Leeuwen in 1976, Moffat and Turpin in 1988, Belal and Elmasry in 2016, etc.) in the past have worked on improving the computing time of optimal prefix free codes, so I am in good company in thinking the problem interesting, and I assumed that it meant that it had practical applications.
In 2000, Moura et al.~\cite{2000-TOIS-FastAndFlexibleWordSearchingOnCompressedText-MouraNavarroZivianiBaezaYates} studied the compression of natural texts via a Huffman code, taking words as input symbols, and showing that it lost a bit of compressibility but gained a lot in indexability.
In 1997 Takaoka showed that using the Huffman code tree to schedule the merging of sorted arrays yielded a faster version of merge sort (by detecting sorted runs, and merging in priority the shortest ones).

I am unhappy with any of those answers, as those are all quite academic/theoretic: I am wondering about real practical applications.


texts: Effective algorithm of searching the "nearest" doubly stochastic matrix

texts:
Given a data matrix $D$, is there any effective algorithm to solve the optimization problem

$\min_Q || D - Q ||_F$

such that

$Qe=e$,
$e^TQ=e^T$, and
$Q_{i,j} \geq 0 $  $\forall i,j$,

where $||\cdot||_F$ is the Frobenius norm of matrix.

p.s. I also posted this question on the Mathematicss exchange.


texts: Nondeterminstic Linear Time vs Other Complexity Classes

texts: Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?


texts: When do coherence spaces have pullbacks and pushouts?

texts:
$\newcommand{\symp}{\Bumpeq}$

A coherence relation $\symp_X$ on a set $X$ is a reflexive and symmetric relation. A coherence space is a pair $(X, \symp_X)$, and a morphism $f : X \to Y$ between coherence spaces is a relation $f \subseteq X \times Y$ such that for all $(x,y) \in f$ and $(x',y') \in f$,

if $x \symp_X x'$ then $y \symp_Y y'$, and
if $x \symp_X x'$ and $y = y'$ then $x = x'$.

The category of coherence spaces is both Cartesian and monoidal closed. I would like to know when pullbacks or pushouts exist for this category, and when some monoidal analogue of pullbacks or pushout exists (and how to define it, in case this notion makes sense).


texts: An interesting construction of a Tits building?

texts:
The notion of Tits building was introduced by Jacques Tits to study certain questions in group theory. The wikipedia entry gives a way to construct a Tits building from a vector space, but I would be interested in a simpler construction defined as follows.

Let $\mathbb{V}$ be a vector space over a field $\mathbb{F}$. Construct a simplicial complex $SCI(\mathbb{V})$ with ground set $\mathbb{V}$, where the simplices are the linearly independent subsets of $\mathbb{V}$ - note that this essentially defines a representable matroid.

Consider two basis $B^1 = \{u^1_1,\ldots,u^1_n\}$ and $B^2 = \{u^2_1,\ldots,u^2_n\}$ of $\mathbb{V}$, such that the basis-change matrix $M_{B^1,B^2}$ is lower-triangular. We can then define an apartment $O_{B^1,B^2}$ which is the subcomplex of $SCI(\mathbb{V})$ formed by the subsets $\{u^{i_1}_1,\ldots,u^{i_p}_p\}$ for $1 \leq p \leq n, i_j \in \{1,2\}$.

Question: does this construction satisfy the four axioms of a Tits building (given in the above link)? If so, what are the possible applications to matroid theory?


texts: Do Genetic Algorithms Expect a Independent Search Space

texts:
Genetic Algorithms seem like multiple simulated annealing instances, augmented with a crossover genetic operator. The crossover operator selects predefined genes from two different parent solutions to create a new child solution for the next generation.

This seems to suggest that the search space is independent (a single gene will benefit a solution regardless of the other genes). Additionally, it seems like the user needs to choose axes along which the search space is separable.

However, genetic algorithms are often used in practice.  Are my concerns a nonissue? Are most real world search spaces independent?

P.S. I would a define a two argument fitness function $F(x,y)$ as independent if

$$F(x,y) = G(x)+H(y)+\epsilon J(x,y)$$

for some small $\epsilon$. For example, $F(x,y) = -x^2-y^2+0.1xy$ would be an independent function. Intuitively, the arguments of an independent function interfere with each other minimally.


texts: A reduction proof of SK-security for the Needham-Schroeder-Lowe protocol

texts:
The Needham-Schroeder-Lowe protocol works as follows between the initiator I and responder R:

$I \longrightarrow R : \text{Enc}_{pk_R}(r_I, I)$

$R \longrightarrow I : \text{Enc}_{pk_I}(r_I, r_R, R)$

$I \longrightarrow R : \text{Enc}_{pk_R}(r_R)$

(I assume throughout that the encryption scheme is CCA-secure.)

Upon receiving their messages, both parties decrypt using the corresponding private key and finally output $r_I$ as their session key.

I understand others have proven that this protocol is SK-secure protocol, based on the CK01 model for SK-security.  (As a reminder, the protocol is secure in this model if no adversary can distinguish, with probability strictly greater than $1/2$, between the output $r_I$ of the protocol and a random bit.)  Security was proven using formal methods.  My question: is there a proof of this using an explicit reduction?


texts: Comparing SAT to MCSP reduction class separations and faster SAT class separations?

texts:
Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $NQuasiP\neq ZPP$.
Now if $SAT$ reduces $MCSP$ by $LOGSPACE$ $m$-reductions we infer a stronger separation of $PSPACE\neq ZPP$ by https://drops.dagstuhl.de/opus/volltexte/2015/5074/.

I am wondering if $SAT$ is in $TISP(QuasiPTIME, QuasiLOGSPACE)$ will provide $PSPACE\not\subseteq P/poly$ and $PSPACE\neq ZPP$?

I think at least $SAT$ in $TISP(PTIME, LOGSPACE)$ will provide $PSPACE\not\subseteq P/poly$ and $PSPACE\neq ZPP$.

Does faster $SAT$ provide implications to $SAT$ to $MCSP$ reductions or vice versa?


texts: Complexity of type-checking in relation to complexity of normalization

texts:
In order to verify that a terminating program terminates, one thing that can be done is to actually run the program. That may take a lot of time. If the program is typed in a total type-system, we can instead just type-check the program. That will take some time too, sometimes "a lot" too.

I'm looking for results that formalize the relation of the complexity of type-checking to the complexity of normalization for a various type-systems, i.e. possible speedup ratios. Is that relation always well defined? I'm not sure.

But we can give some lower bounds by demonstrating families of typed terms.

I'm interested mostly in any of the well known type systems such as System F, predicative variants of system F, including 'Rank 1' variant and Calculus of constructions.  'Intersection types' are particularly interesting case since they characterize the family of normalizing lambda terms.


texts: Are generalized map involutions captured by GNN?

texts:
In coming across a post related to this question's topic,  posting in Theoretical Computer Science might be the right place. In combinatorial maps (1,2,3), are generalized map involutions captured by Graph Neural Networks?
Generalized maps (gmap) can be defined by the data structure: M = (D, $\sigma$, $\alpha$) where $\alpha$ is a permutation that gives the other dart connected on the same edge , i.e., the neighboring dart/s (see 2).
Involutions can be properties of nodes. This is ideal for local structure aggregation in GNNs and GCNs. However, in conversation with others, there are suggestions that the GNN handles involutions information (such as the face a triangle forms in planar graphs). Is that right?


texts: Complexity of finding the square root of a perfect square

texts: What is the complexity of precisely finding the square root of a perfect square?


texts: Random self-avoiding lattice cycle within a given bounding box

texts:
In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all possible simple cycles.

One way to do this would be to use a Markov chain whose states are sets of squares whose boundaries are simple cycles and whose transitions consist of choosing a random square to flip and keeping the flip when the modified set of squares still has a simple cycle as its boundary. One can get from any simple cycle to any other one in this way (using standard results about existence of shellings) so this eventually converges to a uniform distribution, but how quickly?

Alternatively, is there a better Markov chain, or a direct method for selecting simple cycles?

ETA: See this blog post for code to calculate the number of cycles I'm looking for, and pointers to OEIS for some of these numbers. As we know, counting is almost the same thing as random generation, and I infer from the lack of any obvious pattern in the factorizations of these numbers and the lack of a formula in the OEIS entry that there unlikely to be a known simple direct method. But that still leaves the questions of how quickly this chain converges and whether there's a better chain wide open.


texts: Comparing two graphs when starting from a single edge

texts:
Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes.

$G_1$ and $G_2$ are isomorphic (including matching of the edge weights). However, I would like to check whether they look the same when 'building' them from one edge. i.e. we pick one (not necessarily the same) edge in both graphs and would like to know if they look the same starting from that edge. For the example above, we could choose the edge (1,2) in both graphs and see that they are not the same. If we would choose (1,2) and (5,6), they would be the same.
Are you aware of any algorithm to check this kind of similarity? Or is there even a NetworkX function? For tree graphs I could just use NetworkX's is_isomorphic function. However, my intuition is that this similarity measure should be easier (i.e. faster) to check than isomorphism.
Thanks a lot


texts: Number of Vertex Covers: when it is polynomial and when it is superpolynomial

texts:
The number $C$ of vertex covers of a graph $G = (V, E)$ can be either polynomial in $|V|$ or superpolynomial in $|V|$. $C$ being superpolynomial in $|V|$ doesn't necessarily mean that $C$ is hard to determine. For instance, consider the graph $G = (V, E)$ where $|V| = 2n$ and $E$ is defined as $E = \{ \{ i,j \} | i \mod 2 = 1 \land j = i + 1 \}$: such graph has a number of vertex covers $C=3^{|E|} = 3^{\frac{|V|}{2}}$ which is both superpolynomial in $|V|$ and very easy to determine. On the other hand, knowing in advance that $C$ is polynomial in $|V|$ allows us to use brute force keeping the running time polynomial in $|V|$. So it seems that determing $C$ is hard only if it is superpolynomial in $|V|$, but not always (as the above example demonstrates).

  Questions

  Is it possible to determine in advance if $C$ is polynomial in $|V|$ or superpolynomial in $|V|$? Is there any known result linking some parameter of the graph with the number of its vertex covers? An example of such result would be: "Every graph with $\frac{|E|}{|V|} \geq 4$ has not more than $n^{\frac{|E|}{|V|}}$ vertex covers". Another example would be: "Every graph with $\frac{|E|}{|V|} < 2$ has not less than $1.18^{\sqrt{|E|}}$ vertex covers". How $C$ varies with $G$? Clearly, the more edges $G$ has, the less vertex covers it has: did anyone formalized this trivial fact, showing precisely how $C$ decreases as $|E|$ increases? Which other parameters affect $C$, and how? I mean, from a pure empirical point of view, it's almost evident that a graph with $\frac{|E|}{|V|} \geq 5$ has not so many vertex covers, where "not so many" means "certainly polynomial in $|V|$".
  When $C$ is superpolynomial in $|V|$ brute force is useless. However, I wonder if, as in the above example, it is always true that $C$ being superpolynomial intrinsically implies the presence of "multiplying blocks" (I don't know how to state this more formally), which in turns would mean that the set of all vertex covers is easy to represent (in other words, it is compactly representable). Is there any known result in this spirit?


texts: Featherweight Generic Java formalization in Coq

texts:
I've been searching for some nice formalization of FGJ (Featherweight Generic Java) in Coq. I am going to develop an extension of FGJ in Coq, so I hope there is an appropriate Coq implementation which I can base my work on.

I have found this one. I haven't yet read corresponding paper carefully, but it looks like a whole «framework» for building up FGJ extensions. The Coq files seem to be quite difficult to dive in (probably after reading the paper they'll become clearer).

Is anybody aware of another Coq formalizations of FGJ?


texts: How to design a secret sharing scheme for matrix-like positioned participants

texts: How to design a secret sharing scheme where when participants are positioned as a matrix, the minimum group people who can reconstruct the secret are the ones that are in same row or in same column?


texts: Optimal parallel algorithm for finding roots of a function

texts: In some problem I need to find the zeroes (multiple real solutions) of some functions in 1D and 2D. I wonder which is the best parallel algorithm for this, which can provide the highest accuracy and its optimal from the computational point of view.


texts: What is the status of Determinantal Complexity of Permanent

texts:
Recently Landsberg and Ressayre announced an exponential lower bound for permanent's determinantal complexity assuming certain symmetry conditions.

What is the status of the problem of Permanent's determinantal complexity after this proof? What more needs to be done to close the loop? Will the natural proof barrier affect whatever needs to be done? In short what progress does this proof intend to give on this important problem?


texts: Path finding algorithm to maximise points of interest along the route

texts:
I am trying to write an algorithm to find a path (not the shortest one) between a given start and end point.

An user will enter the start location, the end location and the available time to travel. For each edge of my graph I know the cost in time to traverse that edge and the gain in points of interest along that edge. I want to find the path witch maximises the gain in points of interest and falls within the given time.

Until now I only found references to A Star routing algorithm or optimisations to it witch only compute the shortest path.

Could you please give me some hints on what algorithm should I use or some references to solutions of similar problems? This algorithm is an important part of my Dissertation.

Thank you,
Radu-Stefan


texts: Understanding the Proof of Strong Normalization of the Calculus of Constructions

texts:
I have difficulties in understanding the proof of strong normalization for the calculus of constructions. I try to follow the proof in the paper of Herman Geuvers "A short and flexible proof of Strong Normalization for the Calculus of Constructions".

I can follow the main line of reasoning well. Geuvers constructs for each type $T$ an interpretation $[\![T]\!]_\xi$ based on some evaluation of type variables $\xi(\alpha)$. And then he constructs some term interpretation $(\!|M|\!)_\rho$ based on some evaluation of term variables $\rho(x)$ and proves that for valid evaluations the assertion $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ for all $\Gamma\vdash M:T$ holds.

My problem: For easy types (like system F types) the type interpretation $[\![T]\!]_\xi$ is really a set of terms, so the assertion $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ makes sense. But for more complex types the interpretation $[\![T]\!]_\xi$ is not a set of terms but a set of functions of some appropriate function space. I think, I almost understand the construction of the function spaces, however it cannot assign any meaning to $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ for the more complex types $T$.

Can anybody explain or give links to some more understandable presentations of the proof?

Edit: Let me try to make the question clearer. A context $\Gamma$ has declarations for type variables $\alpha:A$ and object variables. A type valuation is valid, if for all $(\alpha:A) \in \Gamma$ with $\Gamma\vdash A:\square$ then $\xi(\alpha) \in \nu(A)$ is valid. But $\nu(A)$ can be an element of $(SAT)^*$ and not only $SAT$. Therefore no valid term evaluation can be defined for $\rho(\alpha)$. $\rho(\alpha)$ must be a term and not some function of a function space.

Edit 2: Example which does not work

Let's make the following valid derivation:
$$
\begin{array}{llll}
[] &\vdash  & *:\square &\text{axiom}
\\
[\alpha:*] &\vdash& \alpha:* &\text{variable introduction}
\\
[\alpha:*] &\vdash& *:\square &\text{weaken}
\\
[] &\vdash & (\Pi \alpha:*.*):\square   &\text{product formation}
\\
[\beta:\Pi \alpha:*.*] &\vdash& \beta:(\Pi \alpha:*.*) &\text{variable introduction}
\end{array}
$$

In the last context a valid type evaluation must satisfy $\xi(\beta) \in \nu(\Pi \alpha:*.*) = \{f| f:\text{SAT} \to \text{SAT}\}$. For this type evaluation there is no valid term evaluation.


texts: What machine learning algorithm solves this problem?

texts: I want to solve this classification problem. Basically what I have is a sequence of feature vectors $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N$, and each feature vector is sequential in time. I want to predict the class label $y$ based on the observation of these $N$ feature vectors. The outcome label $y$ can be from a set of two possible classes $y \in \{A,B\}$. So my question is: What machine learning algorithm is best suited for this kind of problem? I know sequential learning like Hidden Markov Model, but they are more suitable for the case where each observation $\mathbf{x}_i$ corresponds to a hidden state $y_i$, versus here in my case only the final class label is needed. There is no hidden states along the time in my problem. So the goal is to predict the class label $y$ based on a sequence of feature vectors $\{\mathbf{x}_i\}_{i=1}^{N}$. Any suggestions?


texts: Intractability of NP-complete problems as a principle of physics?

texts:
I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical verification, I'm not aware of similar evidence for the P vs NP question.

Additionally, I'm not aware of any direct physical world consequences of the existence of undecidable problems (or existence of uncomputable functions). Protein folding is NP-complete problem but it appears to be taking place very efficiently in biological systems. Scott Aaronson proposed using the NP Hardness Assumption as a principle of physics. He states the assumption informally as "NP-complete problems are intractable in the physical world".

  Assuming NP Hardness Assumption, Why is it hard to design a scientific experiment that decides whether our universe respects the NP Hardness Assumption or not?

Also, Is there any known numerical evidence from experimental mathematics for or against $P\ne NP$?

EDIT: Here is a nice presentation by Scott Aaronson titled Computational Intractability As A Law of Physics


texts: Do such instances always admit a 3D matching?

texts:
I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching.
We are given 3 sets $A,B,C$ containing $m$ elements each, and $n$ tuples $\{T_i\}_{i\in [n]}$ where $T_i \in A\times B\times C$. We further know:
(i) Each element of $A\cup B \cup C$ occurs exactly in two tuples. Simple counting shows $n = 2m$.
(ii) The elements of $A\cup B \cup C$ can be partitioned into $m$ singleton elements, and $m$ pairs $(x,y)$ where $\{x,y\} \subset T_i$ for some $i\in [n]$.
I want to know if such an instance admits a 3D matching. Is there a simple counter-example?


texts: Super-polynomial time approximation algorithms for optimization problems

texts:
This is motivated by my previous question, Super-polynomial time approximation algorithms for MAX-3SAT.
For many optimization problems, for each one we have inapproximability lower bound $\alpha$ assuming some widely believed complexity theoretic conjecture. In other words, there is no polynomial time algorithm for such optimization problems with approximation ratio better than some $\alpha$ (different ratio $\alpha$ for each problem).

Are there optimization problems for which we can achieve approximation ratio better than $\alpha $ if we allow super-polynomial time algorithms? Can we achieve better approximation ratios using quasi-polynomial time algorithms ( $n^{O(\log n)}$) or even using sub-exponential time algorithms($2^{o(n)}$)?

I would appreciate a survey of such results.


texts: Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

texts:
If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds.

  What are the best statements we have proved that come close to converse to these statements?

My motivation is this $P=BPP$ and $NP\subseteq P/poly$ are consistent with what we know. However $MCSP\subseteq NP\implies$ $NP\subseteq P/poly$ gives no strong pseudorandom generators in $P/poly$ from Circuit Minimization Problem by Kabanets and Cai.

  So is it possible one way functions and pseudorandom number generators are not necessary for derandomization?

It might be that any argument that shows $P=BPP$ implies strong pseudorandom number generator exists should also show $NP\not\subseteq P/poly$ in that case $P=BPP$ and $NP\subseteq P/poly$ should not be consistent with what we know. However I cannot uncover a statement on this.

In an extreme it can very well be that $P=NP$ in which case we have derandomization and no one way functions and pseudorandom number generators. It is not at all clear why these should be considered essential for derandomization.

  Are there alternate proofs of $E$ needing exponential circuits for infinite input lengths leading to $P=BPP$ without going through these objects?


texts: Random grid point in a d-dimensional ball

texts:
I would like to know if there is any standard algorithm to generate
a random grid point inside a d-dimensional ball with a given radius r.

Thanks

Bin Fu


texts: Certified compiler and optimizations in Coq/Agda

texts:
I am interested in verified compilers formalized in Martin-Löf type theory, i.e. Coq/Agda. At the moment I’ve written a small toy example. Therewith I can prove that my optimizations are correct. For example that additions with zero can be eliminated, i.e. expressions like "x + 0".

Are there optimizations that are difficult to perform with a regular compiler, that would serve as a good example? Is it possible to prove certain properties of a program that allow optimizations that are not possible to perform with a regular compiler? (i.e. without the inference that is possible with a theorem prover)

I would be interested in ideas or examples and also references on the topic.

A related question:
Compiler correctness proofs

edit:
As Tsuyoshi nicely put it in the comments:
I am looking for optimization techniques which are difficult to implement if a compiler is written in (say) C but easier to implement if a compiler is written in (say) Coq. As Agda compiles to C (via haskell) it is possible to do everything that is possible in Agda also in C. Probably the only benefit of theorem provers like Coq/Agda is that the compiler and the optimizations can be verified.

edit2:
As suggested by Vijay D I write what I've read so far.
I mainly focused on Xavier Leroy and the CompCert project at INRIA (there is a 80 pages paper that is a good read, I think).
A second interest was in the work of Anton Setzer on interactive programs. I though that perhaps his work could be used to prove properties about IO programs and bisimulation of IO programs.
Thanks for mentioning Sewell. I've heard his talk "Tales from the jungle" at ICFP and read perhaps 2-3 of his papers. But I haven't specifically looked at his work and that of his coauthors.
I did not yet find out where to start or look for papers on optimizing compilers; e.g., which optimizations would be interesting to look at in the setting of a verified compiler.


texts: The concept of binary description by Ray Solomonoff

texts:
In this article, http://world.std.com/~rjs/rayfeb60.pdf in page 7 of the PDF, Solomonoff gives an a-priori probability for a string which is $pr(S)=2^{-|S|}$.

My question - why are shorter strings considered more probable? Is there some kind of hidden assumption that justifies this?

e.g. that the machine which produces these strings have a constant probability to stop at a any given point (an inherent preference to shorter strings).


texts: What would a very simple quantum program look like?

texts:
In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first programs I ever wrote was something like

for i = 1 to 10
  print i
next i

Can anybody give an example of code of comparable simplicity that would utilize quantum photonic chips (or similar hardware), in pseudocode or high level language? I am having difficulty making the conceptual jump from traditional programming to entanglement, etc.


texts: Extension of a sampling Lemma of Indyk for $k$-median cost

texts:
A famous sampling lemma of Indyk (Theorem 31 here) states that if the $k$-median cost of a finite point set(in a metric space) is large with respect to the optimum, then this is true for the case of a unifrm ramdom set of points as well.
More formally, Let $(X,d)$ be a metric space, $P\subset X$ finite and $Q$ be a non-empty sample, drawn uniformly and independently at random from $P$. Let $a,b\in P$ two points such that $\sum_{p\in P}d(p,a) > (1+\epsilon)\sum_{p\in P}d(p,b)$. Then it holds that,
$\sum_{q\in Q}d(q,a)\leq \sum_{q\in Q}d(q,b)$ with probability at most $\exp(-\epsilon^2\vert Q\vert/64)$
See Lemma 3.3,here for a similar result. The proof crucially depends on the behaviour of the following carefully defined random variable
$X=\sum_{q\in Q}\frac{d(q,a)-d(q,b) + d(a,b)}{2d(a,b)}$
Since $d$ is a metric, it is not hard to see that $X$ is sum of random variables between 0 and 1.
Recently Feldman et. al extends certain clustering cost to more relaxed metric spaces. $(X,d)$ is a $\rho$-metric space if $d(x,y)\leq \rho(d(x,z) + d(z,y))$. $(X,d)$ is $(\rho,\phi,\epsilon)$-metric space if it is a $\rho$-metric and $d(x,z)-d(y,z)\leq \phi d(x,y)+\epsilon d(x,z)$.They proved that the KMEANS++ algorithm works for $\rho$-metric as well.
My question is that : Can the above sampling lemma be extended for such relaxed metric spaces?
Some initial thoughts,
From Feldman et.al, we know that any $\rho$-metric is also a $(\rho,\rho,\rho-1)$-metric. Some initial calculation shows that the following random variable (defined for each $q\in Q$)
$X_q = \frac{\rho d(q,a)-d(q,b)+\rho d(a,b)}{2(\rho d(a,b)+(\rho-1)d(q,a))}$
assumes value in the range $[0,1]$. Note that this coincides with our original random variable when $\rho=1$. But now the issue is that the denominator also depens on the random point $q$. So it seems difficult to compute the expectation of $\sum_{q\in Q}X_q$.


texts:
A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called $(n,k)$-universal if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, all $2^k$ vectors appear in $\mathcal{U}$'s vectors when restricted to $S$.

A $(n,k)$-universal set is said to be $(T,\alpha)$-balanced if for every vector $v$ of length k and every subset $S\subset [n], |S|=k$, the number of vectors in $\mathcal{U}$ which has $v$ in indices $S$ is at least $\frac{T}{\alpha}$ and at most $T\cdot \alpha$. The original definition of the universal set only ensures that there exists at least one such vector $u\in \mathcal{U}$.

Related works for similar structures are:

Nearly optimal build of $(n,k)$-universal set (NSS).
Nearly optimal build of $\delta$-balanced perfect hashing family by Alon and Gunter.
Simple Constructions of Almost k-wise Independent Random Variables (AGHP).

My question is: is it possible to deterministically build a small $(T,\alpha)$-balanced  universal set?

(By small, I mean $O(2^{k+\text{polylog}(k,\alpha)}\cdot \text{poly}(n))$).

It doesn't seem hard to show (using the probabilistic method) that such set exist, but I'm interested in explicit build.


texts:
I read about Potential Method when I was trying to understand some calculations.

I just can't understand how do you perform the calculation it self. How can you even define $O(n)-O(n)$ as it is used in the Wikipedia page? I just don't understand where is the calculation done.

Is there any good and simple example of this kind of analysis?

Shay


texts: Known sparse integer programming problems

texts:
I am studying the properties of sparse integer programming problems, Would like to know if there are any interesting known problems of that type ?

I would define sparse problems as problems that have their output mostly populated by zero values.

Thank you


texts: Justification of log f in DTIME hierarchy theorem

texts:
If we look at DTIME hierarchy theorem, we've got a log due to the overhead in simulation of a deterministic Turing Machine by a universal machine :

$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$

We haven't this kind of overhead for NTIME of DSPACE. A basic justification comes from the details of the proof by considering the difference between simulators.

My question is the following: without considering the detail of the proof of DTIME hierarchy theorem, is there a justification of this log or it could be just a consequence of the proof and it would be reasonable to imagine that if $f = o(g)$ then

$DTIME(f) \subsetneq DTIME(g)$

In my opinion, considering that the simulation explanation is a good justification should be itself justified by proving that if we had a better result, then we could create a better simulation.


texts: Does the approximatibility of individual gates together with unitarity imply BPP=BQP

texts: Suppose you can prove upper bounds on errors from approximating an individual quantum gate by randomly hashing the qubits of a circuit to a polylog number of qubits. (So, you prove a bound on how much of the entanglement information is lost by approximation on average for each individual gate and changing which qubits are hashed and not is a unitary transformation without subsequent loss of information.) Does unitarity provide a barrier to the accumulation of errors over many quantum gates such that errors in probability amplitudes at most add up (since unitary transformations preserve inner products), implying that $\mathrm{BPP}=\mathrm{BQP}$?


texts:
This is a question from the lecture about Toda's theorem:

http://www.cs.princeton.edu/courses/archive/spring01/cs522/lecnotes/lec8.ps

The lecture uses theorem 1 and theorem 2 but not include proof. My question is how to proof?

Theorem 2:

$L \in \oplus P$ iff $L$ can be computed by a DC uniform circuit $\{D_n\}$ that

use $AND$, $OR$, $NOT$, $XOR$ gates.

has size $2^{n^{O(1)}}$ and constant depth

$XOR$ gates can have unbounded (exponential) fanin, but $AND$, $OR$ gates have fanin at most $n^{O(1)}$

$NOT$ gates can appear anywhere in the circuit.

This question may not be a research level question, but I really want to know the answer. If someone can give me a detailed reference, I will appreciate that.


texts: Complexity of cycle cancellation with integral capacities and irrational costs

texts:
Cycle cancellation is a standard textbook algorithm for computing minimum-cost circulations: As long as the residual graph of the current circulation contains a negative cycle, push as much flow along that cycle as possible.  I'm trying to understand the worst-case behavior of the generic algorithm.  For purposes of analysis, I want to assume that at each iteration, the negative cycle to augment is chosen adversarially.

If all capacities and costs are integers, each iteration decreases the cost of the current circulation by at least 1.  Thus, the algorithm halts after augmenting at most $-\$(f^*)$ cycles, where $\$(f^*)$ is the cost of the final circulation.  Moreover, standard bad examples for Ford-Fulkerson and the standard reduction from maximum flow to minimum-cost circulation imply that $-\$(f^*)$ iterations are necessary in the worst case.

If we allow irrational capacities, then standard bad examples of Ford-Fulkerson and the standard reduction from maximum flow to minimum-cost circulation imply that the algorithm may never terminate, and worse, may not even converge to an approximate minimum-cost circulation in the limit.

What is known about the case of integer capacities and irrational costs?  I have found nothing in the literature about this case.

Cycle cancelling must terminate after a finite number of iterations in this case, because there are only a finite number of feasible integer circulations, but that argument only implies the upper bound $O(U^E)$, where U is the maximum edge capacity.  Zadeh's classical bad examples for network simplex (and I suspect similar bad examples for Ford's generic shortest-path algorithm) imply an $\Omega(2^V)$ lower bound, even if the most negative cycle is canceled at each iteration.  Are any tighter bounds known?

In particular: What is known about the case of unit capacities and irrational costs?


texts:
Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.

I wonder whether such kind of provable security exists for secret-key cryptosystems, such as AES. If not, what is the evidence that breaking such cryptosystems is hard? (other than resistance to trial-and-error attacks)

Remark: I'm familiar with AES operations (AddRoundKey, SubBytes, ShiftRows, and MixColumns). It seems that the hardness of AES stems from the MixColumns operation, which in turn must inherit its difficulty from some hard problem over Galois Fields (and thus, algebra). In fact, I can restate my question as: "Which hard algebraic problem guarantees the security of AES?"


texts: Constructing a digraph from its spectrum

texts:
This is related to the following question which has already been explored:
Reverse Graph Spectra Problem?

So it seems as if given a sequence of real numbers, it is not always possible to generate a 0-1 symmetric matrix (with zeros on the diagonal) whose spectrum is the given sequence. This is because not only is it true that not all sequences can occur as eigenvalues of such matrices, but also because there exist non-isomorphic graphs with the spectrum. This leads to the question of characterizing n-sequences for which such a reverse reconstruction exists and whether such a reverse reconstruction is possible in more specific cases.

Consider the case of simple digraphs and their line digraphs. In this case, the adjacency matrices are again 0-1 matrices with zeroes on the diagonal, but not the matrix need not be symmetric. The following paper shows a clean relationship between the spectrum of a digraph and that of its line digraph:
http://www.academia.edu/1462821/Algebraic_properties_of_line_digraphs

What I noticed in the introduction was that:

"As it is expected, it is not possible, to reconstruct the adjacency matrix of a digraph from the spectrum or the characteristic polynomial only. However we shall prove that this is possible for the case of line digraphs."

The paper claims to do this using a relation between the Jordan normal forms of the adjacency matrices of the digraph and its line digraph, which I am firstly unable to see clearly.

Secondly, given any graph, I could convert it into a digraph in the natural way by having two arcs for each of its edges. Then given the spectrum of a graph, we could construct the spectrum of its line digraph, from which I could reconstruct the line digraph, from which I could in turn reconstruct the digraph (this correspondence between a digraph and its line digraph is well-understood in the case of digraphs with no sources or sinks- from the result of Harary and Norman) from which we could construct the underlying graph.

What am I missing here?


texts: Testing Isomorphism of projective planes

texts:
Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI would colapse isomorphism testing for projective planes to polynomial time.

  Is Miller's algorithm still the best known upper-bound? What other natural hard problems can be solved in $n^{O(\log \log n)}$ time?

Here, hard means the problem has no known polynomial-time algorithm.