texts: Proving proof system properties within the proof system itself?

texts:
While reading about Frege proof systems in [1], I came across the completeness theorem and its proof, which involves a few lemmas introduced first. Here are the first two of those lemmas:
$$\begin{equation} \vdash \phi \supset \phi \tag{1} \end{equation}$$
$$\begin{equation} \Gamma, \phi \vdash \psi \space \text{if and only if} \space \Gamma \vdash \phi \supset \psi \tag{2} \end{equation}$$
The first one is easy to prove using the axioms and inference rule of Frege proof system. The proof of the second one uses induction. This confused me a bit and prompted the following questions:

Are proof systems "self-contained", in the sense that their properties can be proven within themselves? Or are properties such as soundness and completeness "external" to the system? The rationale being part of the motivation for proof systems to formalize proofs and thus serve as a foundation of sorts for other math.
Is there some "strange loop" going on when using something like induction (which is defined on the natural numbers) to prove such properties? Also, $\Gamma$ is a set, which is not really part of this proof system vocabulary. For example, if you use a sound but incomplete proof system $P$ to prove the soundness and completeness of another proof system $Q$, does that imply that $Q$ can't "express" $P$ somehow, since that would be paradoxical?

Sorry if my question is ill-posed. I'm a beginner to this topic, so I would appreciate any advice on formulating the question correctly as well.

[1] Buss, Samuel R. (ed.), Handbook of proof theory, Studies in Logic and the Foundations of Mathematics. 137. Amsterdam: Elsevier. 811 p. (1998). ZBL0898.03001.
[2] https://en.wikipedia.org/wiki/Semantic_theory_of_truth


texts: How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

texts:
Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to proceed.

As you can see on my example image I have added all diagonals connecting two concave vertices each. The green ones do not have any intersections with other diagonals and thus can be applied immediately for sectioning. The other diagonals lead to the following intersection graph:

The graph already shows a maximal matching as found by the Hopcroft-Carp algorithm in blue. (If you are interested in an easy step-by-step tutorial for applying it manually, I can recommend this YouTube video.)

For the next step (choosing the good diagonals) Eppstein writes:

  [...] ﬁnding the maximum
  number of disjoint good diagonals translates, in graph-theoretic terms, into ﬁnding a
  maximum independent set in a bipartite graph. By König’s theorem [49], in any n-
  vertex bipartite graph the maximum independent set has size n − M, where M is the
  cardinality of a maximum matching; an independent set of this size may be found from
  a maximum matching by partitioning the vertices according to the lengths of the shortest alternating paths from an unmatched vertex to the given vertex, and including the
  vertices at even levels of this partition.

If I understood it correcty, I do not know how to determine this length for each node in my graph, as there are nodes unable to reach an unmatched node via an alternating path. Here is what I would assume is meant:

Node | Alternating Path Length to unmatched Node
-----+------------------------------------------
  1  | ?
  2  | ?
  3  | ?
  4  | ?
  5  | 2 (5-e-7)
  6  | 1 (6-g)
  7  | 0 (7)
  a  | ?
  b  | ?
  c  | ?
  d  | ?
  e  | 1 (e-7)
  f  | 2 (f-6-g)
  g  | 0 (g)

According to this I would definitely choose 5, 7, f and g as good diagonals, wouldn't I? But there will be remaining intersections not resolvable by this information.

I asked this question in very short form and without an example on the linked MathOverflow page in a comment, but the question there already left primary school (*) and I'm not sure if I will get any reaction there.

(*) In Germany primary school has four grades and usually one switches to a secondary school at the age of 10.


texts: Practical example: how to formally verify "file name" implementation from a spec?

texts:
Say you have an OS-independent specification for file names. The file names are case sensitive, and let's say can't be more than 200 characters, and can't have : or / in the name.

Now say you want to implement this specification in C on different operating systems (different versions of linux and darwin, not windows for now).

Let's say for argument's sake, it turns out on some operating system (operating system "A"), that you also can't use | in the file name. Well, you didn't capture this in your spec initially.

The question is, how do you figure this out before running into this case? In circuits (from my understanding), you can use "model checking" to automatically explore all possible states of the system, to figure out edge cases your spec doesn't handle. That makes sense for relatively simple state machines like logic circuits. But what about this case with file names?

How would you generate file names, and try to save the file on that operating system, so it can discover these implementation errors, without having to generate every possible string up to 200 characters in length?

How do you verify that the implementation of the spec on operating system "A" is valid? The model checker would have to somehow randomly construct a file name using the | character, and then hit an error. Or maybe I am misunderstanding model checking, and what this really is is automatic testing.

What I'm wondering is, how do you account for these types of cases in advance using formal methods? What are the general techniques or topics to start looking into?


texts: Quasipolynomial and polynomial time hierarchy

texts:
Consider the following two scenarios:

$NP\subseteq RTIME[2^{(\log n)^c}]$ or $NP\subseteq DTIME[2^{(\log n)^c}]$, i.e., $NP$ can be solved in quasipolynomial randomized or deterministic time.
$NP$ has quasipolynomial size circuits.

Does the polynomial time hierarchy $PH$ collapse under any of the above conditions?

The first condition implies $EXP=NEXP$. Does the second imply the same or something weaker?

Could $P=BPP$ still hold in such situations?

Separately what implications follow from $EXP=NEXP$ and/or $EXP$ having quasipolynomial circuits?


texts: An identity about the Majority function?

texts:
Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and $\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x \oplus e_i)]$ be the total influence of a function under the standard definitions. Then does the following identity always hold?

$$  \langle f,Maj_n \rangle \leq c*\frac{\mathcal{I}(f)}{\mathcal{I}(Maj_n)} $$

where c is some universal constant. I believe it might be true but have not been able to prove it. I have tried some standard functions and they seem to work. I may be mistaken as I am very new to this area.  Could you please suggest a way to prove it ? or some references regarding this

Thanks in advance


texts: can you please tell me how can I show that there exists an algorithm that can determine for every regular language L, whether or not |L| ≥ 5


texts: Can graphons be useful outside of extremal graph theory?

texts: I was recently introduced to the notion of a Graphon ([Quick introduction], [Original definition]) and I have been fascinated by the idea behind them and the way they combine fields such as graph theory, measure theory, probability, and functional analysis. Skimming through the limited literature around them, I have been wondering whether these structures could be useful outside of extremal graph theory, (edit:) besides property testing?


texts: A language outside the Boolean closure of stochastic languages

texts:
Stochastic languages, that is, those accepted by probabilistic automata, are known to not be closed under intersection, union, concatenation, and morphism, even on unary languages.

I have two questions about the Boolean closure of the class of stochastic languages:

Is this class closed under morphisms or concatenation?
Can we show that  $\{a^{2^n} \mid n \in \mathbb{N}\}$ is not in it?

Many thanks!


texts: Factoring assuming smoothness of some numbers

texts:
I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers.

For example

When $p-1$ is smooth
When $|E(\mathbb{F}_p)|$ is smooth. (Elliptic curve factorization)
Smoothness of prime ideals in Number field sieves.

I want to know whether any other notions are known to be equivalent to factoring like smoothness of $p+1$ or $p^2+1$  ?


texts: What is the reverse of greedy algorithm for setcover?

texts:
A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, until there are no more uncovered elements.

However, one can go from the other end. Start with the full set, and iteratively remove the subset that is least cost-effective, and will not cause any elements to be uncovered, until there are no more such subsets.

In some sense, the second algorithm may be better because there wont be any redundant subsets in the solution. My question is, what is the name of this algorithm? Does it have the same runtime complexity and approximation ratio as the first one? I could not find any mention of this algorithm after a few hours of searching.

(Please include unweighted SETCOVER for comparison)

Edit: I see that the number of steps can in fact be as large as $(n-1)$ where $n$ is the number of subsets.


texts: Finding islands of vertices in a network of roads containing one-way streets

texts:
I am working on GIS project where we are making use of road maps that may contain one-way streets.

We are writing some debugging tools one of which I want to design to find "Islands".  This would list out all the sets of vertices such that for each pair of vertices A, B in a set you would be able to get from A to B and from B to A.

Here is an example:

A<----------------------> B
\                        /
 \                      /
  \                    /
   \                  /
    \                /
     \              /
      \            /
       \          /
        \        /
         \      /
         v     v
            C

In this case the islands are {c} and {a,b}.

I expect that this reduces to some well-known graph-theory algorithm, but I don't see it.

Does anyone have any pointers for me to do further research or some ideas about a solution?


texts: Stronger reductions in parameterized complexity

texts:
An FPT-reduction between parameterized problems $P$ and $Q$ is a pair of functions $f$ and $p$, such that every instance $x$ of $P$ with parameter $k$ is mapped to an instance $f(x,k)$ of $Q$ with parameter at most $p(k)$, with

$f(x,k) \in Q$ iff $x\in P$,
$f(x,k)$ is computed in fixed-parameter tractable time, i.e., in time  $g(k) \cdot |x|^{O(1)}$ for some function $g$.

Is there an established name for the stronger type of reduction where $f(x,k)$ does not depend on the parameter $k$, but only on the instance $x$, and $p$ is the identity function?

In other words, $f$ is a polynomial time reduction between the underlying classical problems that does not increase the parameter. Does the existence such a reduction from some $\mathsf{W}[t]$-complete problem to a problem $Q$ have any further consequences beyond the $\mathsf{W}[t]$-hardness of $Q$?


texts: Transitive closure of an affine relation

texts:
I am looking for work on computing the transitive closure
of an affine relation in the following sense:

Let $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$
be the relation defined by a system of linear inequalities over real variables
$x_1,\dots,x_n,x'_1,\dots,x'_n$,
i.e.

$R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff
$A x_1\dots x_n x'_1\dots x'_n \leq b$

where $A$ is an $m\times 2n$ matrix and $b$ an $m$-vector.

I am looking for a symbolic representation of $R^k$,
where

$R^k(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff
there exists $y_1,\dots,y_n$ such that
$R^{k-1}(x_1,\dots,x_n,y_1,\dots,y_n)$
and
$R(y_1,\dots,y_n,x'_1,\dots,x'_n)$.

As a very simple example, consider

$R(x,x')$ iff $x'\leq x+1$ and $x'\geq \frac{1}{2} x$

In this case, $R^k(x,x')$ iff $x'\leq x+k$ and $x'\geq \frac{1}{2^k} x$

There is an easy special case where all constraints are equalities:
then we can apply Gauss elimination to find the affine transformation
that maps the $x_i$ to the (dependent) $x'_j$ and compute its $k$th power.
But of course in general, $R$ will not be functional.

The problem also seems to be easier when $R$ describes an open polytope  a convex cone, but I can not assume this.

Edit: I'm looking for a parametric form independent of the concrete value of $k$ (as in the toy example). For a given value of $k$, a representation of $R^k$ can always be obtained from $R^{k-1}$ and $R$ by variable elimination.


texts: Example problems with polynomial and exponential solutions, and tiny footprint?

texts:
I'm planning on running an “experiment” when teaching my algorithms class this fall, with one very old, limited computer (main limiting factor is probably memory—possibly as low as 16KB) and one modern/standard one. The idea being to solve a problem with a polynomial one, running on the slow computer, and an exponential one on the fast one (and, of course, have the slow one win).

The problem is finding a suitable problem—one where the running times will be really different for instances of very limited size (and, preferably, where the data structures are quite simple; the primitive computer is … primitive). I originally thought about sorting algorithms (e.g., quadratic vs. linear), but that would require far too large instances (unless I went with bogosort, for example).

At the moment, the only (rather boring) example I've thought of is computing Fibonacci numbers the smart and the stupid way. It would be nice to have something a little less tired/overused, and preferably something (semi-)obviously useful. Any ideas/suggestions?


texts: Arithmetic circuits with restrictions on occurrence of pairs of variables

texts:
I am curious if the following model was studied or has some obvious lower bounds:

We want to compute a polynomial $P(x_1,x_2, \dots , x_n)$. Suppose we have a graph G on $n$ nodes that we are going to call restriction graph.
Now we will call a monomial $x_{i_1} \times x_{i_2} \times \dots \times x_{i_d}$ valid if no two variables form an edge in the restriction graph $G$:

$$x_{i_1} \times x_{i_2} \times \dots \times x_{i_d} \text{ is valid } \iff \forall a,b: \{x_{i_{a}},x_{i_b}\} \not\in E(G)$$

A polynomial is valid if all of its monomials are valid. We will call a circuit $G$-restricted if all the gates in $G$ compute valid polynomials. We will be only interested in $G$-restricted circuits for valid polynomials.

This model is a strict generalization of multilinear circuits: we can take $G$ to be a collection of loops. My questions are:

Was this model studied?
Are there any other classes of circuits that can be represented this way?
Are there any obvious lower bounds for $G$-restricted circuits for explicit polynomials (and explicit $G$)?


texts:
I'm looking for a graph $G$ on $n$ vertices with the following properties

G doesn't have too many edges, $O(nlog(n))$ or $O(n)$ would be perfect
For random k disjoint pairs of vertices $(s_i,t_i)$ there is a path that links $s_i$ to $t_i$ for each $i$ such that all of these paths are vertex-disjoint. This statement should be true with high probability p.

The goal is to find $G$ such that $k$ is maximal. I'm not very precise on $k$ and the number of edges as well as on p (but let's say large constant p is fine or even better something that goes to 0 with n) because I don't know what is possible.

EDIT: I rephrased the question in terms of average case instead of worst case since worst case won't give many vertex-independent paths as pointed out by Chandra Chekuri.

Thanks,
André.


texts: Speed-up of Boolean over Algebraic computation

texts:
I would like to know what is the maximum speed-up of algebraic computation when we work in the word RAM model.

This question is motivated by this theorem from Ryan's paper:

  Theorem 1.2 Let $(R, +, \times)$ be a semiring on $K$ elements. For all $\epsilon ∈ (0, 1)$, every $n×n$ matrix $A$ over $R$ can be preprocessed in $O(n^{2+ε\log_2 K})$ time such that every subsequent matrix-vector multiplication can be performed in $O(n^2/(ε \log n)^2  )$ steps on a pointer machine or a $(\log n)$-word RAM, assuming operations in $R$ take constant time.

For Matrix-vector multiplication over a field there is a lower bound by Winograd  of $\Omega(n^{2})$ additional gates for an arithmetic circuit, which has the matrix and vector as input. But the theorem above says that there is an algorithm in the word RAM model that, with some preprocessing time, can multiply faster by a factor of $\log^{2}n$.

Is there any other example of an algebraic computation where a speed-up of more than $\log^{2}n$ or even more than a polylogarithmic factor can be achieved?


texts: Let $H$ be $\{-1,+1\}$ Hadamard matrix of size $2$ and $J$ be the same size all $1$ matrix. Let $W$ be $\frac{H+J}{2}$. Is the discrepancy of $W^{\otimes k}$ atmost $\sqrt{k^{-1}}$?


texts: Concentration Bounds for Thompson sampling

texts: This paper gives concentration results around the mean of the regret for variants of UCB algorithm in multi-armed stochastic bandits. However, I could not find any similar results for Thompson sampling, where most of the results are only in expectation. Is there any paper which studies concentration of the regret in the case of Thompson sampling ?


texts: What automorphisms on a Markov Chain imply a uniform limiting distribution?

texts: Consider an irreducible aperiodic Markov chain $M$, modeled as a connected directed graph with weighted edges. The existence of certain (graph) automorphisms on this Markov chain imply various symmetries regarding the limiting distribution. What properties can be demanded of an automorphism or set of automorphisms on $M$, in order for the limiting distribution to be uniform?


texts: Learning Finite Automata Behavior by Experimentation

texts:
This conjecture is from an expert in Game Theory area, I post it here to draw more attentions of TCS experts. Discussions and comments are welcome.

http://gtcenter.org/WCS_Call_for_papers.pdf

An unknown deterministic finite automaton with a known number of states $n$ is put in a black box. The states of the automaton are colored in two colors, 0 and 1. Given an input bit the automaton outputs the color of its current states and moves to a new state as a function of the current state and the input bit. A decision maker trying to predict the behaviour of the automaton by feeding it input bits and observing the output repeatedly. An attempt is called successful if the input bit is equal to the output bit. How many attempts does the decision maker need until he can succeed in 99% of the attempts (in expectation)? Neyman (1997) showed that $O(n \log n)$ is sufficient and conjectured that $Ω(n\log n)$ is necessary.


texts: Beating naive dynamic programming: examples similar to integer partitions?

texts:
Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming algorithm to find $p(n)$ is to construct a square table $A$ where
$$A_{i,j} = \text{partitions of $i$ where each part is $\leq j$}$$
and recursively fill it using the rules
$$A_{i,j} = A_{i,j-1} \text{ if }j>i$$
and
$$A_{i,j} = A_{i,j-1} + A_{i-j,j}\text{ otherwise}$$
with the appropriate conventions for the corner cases. Then $p(n)=A_{n,n}$. This takes $O(n^2)$ operations on integers (let's say we're looking for $p(n)$ modulo some big number, so the size of the numbers is $O(1)$). We can optimize the memory down to $O(n)$ by noticing that we only need the previous column to find the next one.

However, the pentagonal number theorem due to Euler says that
$$p(n) = \sum_{k\in\mathbb{Z}:g_k\leq n}(-1)^{k+1}p(n-g_k)$$
where $g_k = k(3k-1)/2$ are the pentagonal numbers. This allows us to recursively build a one-dimensional list of the $p(i)$, using only $O(n\sqrt{n})$ operations, since the above sum contains $O(\sqrt{n})$ terms.

My question: I was wondering if there are other examples of natural problems for which there is such a surprising speed-up over the standard dynamic programming algorithm, or if this is more of an isolated case complexity-wise.


texts: reference for a special modular decomposition

texts:
For modular decomposition.

X is a module if all members of X have the same set of neighbors among vertices not in X.

I need a special modular decomposition.

X is my module if all members of X have the same set of neighbors among vertices not in X, and X is a clique.

I think this should have been studied already, I would like to avoid redefining it and use some non-standard name, can someone give me some reference?


texts: What are some good resources for strengthening my theoretical foundation for machine learning?

texts:
I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like them to be, so I'm wondering about resources for these two topics. I'm not new to either areas, but I would like to build a really solid theoretical foundation since I enjoy being rigorous and I also potentially want to do research in ML in the future.

Calculus: I took calc 1 and calc 2 in high school, but my AP class didn't really cover that much more beyond basic derivatives, integrals, and Taylor series. I took calc 3 recently but I feel that my intuition about multivariate calculus is still relatively weak.
Linear algebra: I took a rigorous proof-based book on linear algebra as a first course on linear algebra. While I enjoyed the class and did well in it, I don't know that much about the applications, and we didn't get to things like diagonalization. I've been reading Linear Algebra Done Right since it's been recommended to me by a friend and I've heard great things about it.

What are some resources (online or books) that I can use to review and strengthen my theoretical understanding on these two topics, especially calculus? Preferably I'd like something with a lot of exercises and not necessarily aimed at someone with no prior knowledge of it.


texts: Minimizing $L_2$ norm of a vector with two distinct entries

texts:
Let $d\in\mathbb N$ and denote $V=\bigcup_{a,b\in\mathbb R}\{a,b\}^d$, the set of all vectors with two distinct values.
Given a vector $x\in \mathbb R^d$, I want to compute some $v^*\in V$ such that $\left\lVert x-v^*\right\rVert_2\le \left\lVert x-v\right\rVert_2$ for any $v\in V$.

What would be the fastest algorithm to compute $v^*$?

It seems possible to show that the problem is equivalent to finding a threshold $T\in\mathbb R$ such that $v^*_i=\begin{cases}a & \mbox{if $x_i<T$}\\b & \mbox{otherwise}\end{cases}$, where $a$ is the mean of all entries smaller than $T$ and $b$ is the mean of all entries larger than or equal to $T$.
This suggests a $O(d^2)$ time algorithm. Can we find the optimal $T$ faster?

I am also interested in an extension of the problem where we look at $V_4=\bigcup_{a,b,c,z\in\mathbb R}\{a,b,c,z\}^d$ instead of $V$. How fast can we find $v^*$ in this setting?


texts: Graphs in which all shortest paths are unique

texts:
I'm looking for undirected, unweighted, connected graphs $G=(V,E)$, in which for every pair $u,v \in V$, there is a unique $u \rightarrow v$ path that realizes the distance $d(u,v)$.

Is this class of graphs well-known? What other properties does it have? For example, every tree is of this kind, as well as every graph without an even cycle. However, there are graphs containing even cycles that are of this kind.


texts: Software tool to generate the Ising model for random $k$-SAT problems

texts: Is there a software tool available to study the phase transition of the underlying Ising model for a given class of random $k$-SAT problems? I am basically asking whether the framework presented in this paper is already implemented in a public domain library.


texts: Ref request: grammar specification how-to

texts:
I am looking for a reference where I can learn a reasonably systematic approach to how to specify a formal grammar for a given syntax.

By a "formal grammar" I mean something like a BNF description.

(Implicit in this question is the assumption that one can draw a meaningful distinction between "a syntax" and "a grammar".  It is my understanding that this is the case, since many different (formal) grammars can represent the same syntax.  But please correct me if my understanding is wrong.)

The only model I can think of for the kind of reference I'm looking for is Friedl's book on regular expressions.  Its presentation is somewhat informal, but it devotes a fair bit of space to the problem of translating a verbal description of a pattern into a formal description in the form of a regular expression.  The key is that Friedl's book is focused on the practical problem of specifying regular expressions correctly.  I am interested in the practical problem of specifying a formal grammar correctly.

Thanks!


texts: Existence of zero-knowledge proof for location

texts:
N items have been placed at specific points on a map. A prize is awarded to the first person who turns in a list with the location of all N items. The location of each item must fall with a distance error of E.

Player 1 has J locations where $$J < N$$

Player 2 has K locations where $$K < N$$

And for this problem we assume $$(J + K) > N$$

Players 1 and 2 agree to pool their locations to win the prize, but not before they each determine that they have the location of all N items. i.e. $$ J \bigcup K = N $$

Each player wants proof that the other player has some number of locations which they themselves do not have.

Is it possible for a player to prove to the other that they have a location that the other player does not have without disclosing that location?

I call my best guess the triangle game (or sub-game if your prefer)
Here is one round of Player 1 trying to prove a location to player 2.

Player 1 picks a point on the map x1,y1
Player 2 picks a point on the map x2,y2 and a condition 'player 1's point will be in the triangle formed by x1,y1 x2,y2 and x3,y3'
Player 1 picks a point on the map x3,y3 for which at least one his points falls inside the triangle

The condition in step 2 may also be 'player 1's point will not be in the triangle formed by x1,y1 x2,y2 and x3,y3'.

Player 2 will try to pick a point and a condition such that he can confirm that Player 1's point is not one of his K points.

The players may have to play this triangle game many rounds in order to verify a point.

This problem is based on the DARPA Network Challenge

N items=10 red balloons
map=the continental United States
prize=$40,000
distance error of E < 1.0 mile


texts: The number of triangulations of a set of $n$ planar points: Why so difficult?

texts:
After hearing Emo Welzl speak on the subject this summer, I know the number of
of triangulations of a set of $n$ points in the plane is somewhere between
about $\Omega(8.48^n)$ and $O(30^n)$. Apologies if I am out-of-date; updates welcomed.

I mentioned this in class, and wanted to follow up with brief, sage remarks to give
students a sense for (a) why it has proved so difficult to nail down this quantity,
and (b) why so many care to nail it down.  I found I did not have adequate answers
to illuminate either issue; so much for my sageness!

I'd appreciate your take on these admittedly vague questions.  Thanks!


texts: Efficient enumeration of the reachable leaves of nodes in a polytree

texts:
A polytree is a directed acyclic graph which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart.

Given a polytree $T$ and a node $n \in T$, the set of reachable leaves $L(n)$ of $n$ is the set of nodes $n' \in T$ that have no child in $n'$ and such that $n'$ is reachable from $n$.

I would like intuitively to know an efficient algorithm to preprocess a polytree to be able to answer queries where I am given an arbitrary $n \in T$ and I must enumerate the contents of $L(n)$.

Specifically, a preprocessing algorithm takes as input the polytree $T$ and computes some data structure $D$ in some amount of time. An enumeration algorithm takes as input $T$, $D$, the query node $n \in T$, and the previous state $S_{i-1}$ of the enumeration (initially $S_0$ is empty), and outputs the $i$-th element $n' \in L(n)$ and a next state $S_i$ (with a special value used to signal termination of the enumeration). The enumeration, when called successively, must output exactly the elements of $L(n)$ in some arbitrary order, without outputting the same element multiple times.

What are the most efficient algorithms for this problem, in terms of preprocessing time and enumeration time? Specifically, I am looking for a linear-time preprocessing and for constant-delay enumeration, i.e., the preprocessing should take time $O(|T|)$ and, for any query node $n \in T$, each enumeration step should take $O(1)$ time. If this is known to be impossible, I am also interested in a lower bound.

[Note that we can just precompute the answer for all nodes with quadratic preprocessing time, or compute each answer on the fly with linear-time enumeration for each answer (to traverse the relevant part of $T$), hence my focus on linear-preprocessing and constant-delay.]

[Further note that, if $T$ is a directed tree, we can achieve what I request by precomputing in linear time, for each node, its first and last reachable leaf in pre-order traversal, and for each leaf, its next leaf in post-order traversal. Then we can do constant-delay enumeration by jumping to the first reachable leaf of the vertex, and go through the leaves in order until we reach the last reachable leaf of the vertex. But the extension to polytrees does not seem straightforward.]


texts: clustering (lat,lng) pairs, with clusters having the same number of elements

texts:
Imagine you have a list of (lat,lng) pairs. You have k employees. And you want each employee to visit roughly the same number of places, making the least distance possible.

I've tried to solve this with K-Means clustering, but found that it didn't produce clusters with the same number of elements.

Is this possible? Is there a known algorithm that could solve this?


texts: Minimum number of hours of speech needed to train a neural net to recognize speech

texts:
From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 hours for 90% accuracy
commercial quality speech recognition. Is there is a minimum amount of information needed to reproduce the complexity of the actual language.  I.e., if you had 5000 hours and compress it down with a neural net, there is some minimum size neural net needed to do a good job at speech recognition.   You can call that the "bit complexity of a natural language".  Does inverting the compression ratio tell you how many hours of speech, at a minimum, you would need to train a commercial quality speech recognition system?  For context, the classic paper Prediction and Entropy of Printed English seems relevant.

Also relevant is the work of Sanjeev Arora on theoretical machine learning.

This question comes out of the NIST OpenCLIR19 evaluation  and OpenSAT19.  OpenSAT is having an open meeting in August.  In both programs there is a focus on Low Resource Languages. OpenCLIR had 80 hours of Swahili and OpenSAT has Pashto. In OpenCLIR, no solver team was able to do speech recognition on Swahili training from 80 hours of speech. Hence the question.


texts: vertex in a degeneracy ordering of a undirected graph

texts:
There is a step in Bron–Kerbosch algorithm

for each vertex v in a degeneracy ordering of G:

what is "a degeneracy ordering of G"?  For example what is vertex in a degeneracy ordering  in

this graph


texts: Communication complexity of approximating the size of set intersection

texts:
Consider the set-intersection problem: Alice and Bob each get a subset of $\left\{ 1,\ldots, n\right\}$, and they would like to know whether their sets intersect. This is a canonical problem of communication complexity, and it is well-known that randomized protocols for this problem require $\Theta(n)$ bits of communication (see survey here). In the case where the sets are of size $k$ for $k \ll n$, it is known that randomized protocols require $\Theta(k)$ bits (see here).

Consider now the variant in which Alice and Bob want to know the size of the intersection of their sets. Clearly, computing the exact size reduces to the standard set-intersection problem, and this holds even if they only want to compute a multiplicative approximation of the size. However, what happens if they want to compute an additive approximation of the size of the intersection? Is there any lower bound or upper bound known about this problem?

I am particularly interested in this question in the setting of small sets, i.e., the case where the sets are of size $k \ll n$.


texts: What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?

texts:
It is unknown whether $P\subseteq CSL$ or $P\not\subseteq CSL$, where

$P$ is the set of all languages decidable in polynomial time on a deterministic Turing machine, and
$CSL$ is the class of context-sensitive languages, known to be equivalent to $NSPACE(O(n))$, the languages decided by linear-bounded automata.

For many open questions, there is a tendency towards one answer (a la "most experts believe that $P\neq NP$"). Is there something like this for this question?

In particular, would either answer have unexpected consequences? I can only see expected (but unproven) consequences:

If $P\subseteq CSL$, then $P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$ (space hierarchy theorem), hence $P\subsetneq PSpace$.
If $P\not\subseteq CSL$, then there is a language $l\in P\setminus NSPACE(O(n))$ and therefore $l\in P\setminus NL$, hence $NL\subsetneq P$.

(Acknowledgement: The second consequence of these two was pointed out by Yuval Filmus at https://cs.stackexchange.com/questions/69614/)


texts:
SAT Problems  have a  phase transition  that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP Complete problems in general, AFAIK.

Suppose I have a hard instance of an NP Hard problem, say HAM CYCLE and I reduce the problem down to SAT.  Can you say anything about the hardness of the SAT instance? Will it be easy or hard?

Intuitively, it seems the SAT Problem reduced to should be hard, but is there a proof?


texts: Ref Request: Asymptotics of frequency restricted sequences

texts: Given a sequence of $n$ symbols drawn from an alphabet of size $m$, I wish to count the number of sequences that have no more than $k$ occurrences of any symbol.  What is known about the asymptotic behavior of such sequences?  i.e., are there any reasonable upper bounds in terms of the three parameters $n$, $m$ and $k$?  There must be a name for this, but all I can find is the more specific Stockhausen sequence, which has other restrictions.


texts: Geometry on a space of polynomial functions

texts:
I am considering some geometric concepts in a space of functions.But I am not sure the concept I consider is already defined in some references.

Let $P_{1},...,P_{N}:\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}$ be functions with $ n $ variables

$dist (P,Q):=$ the number of input strings $x$ such that   $P(x)$ agrees with  $Q(x)$

Let $\mathcal{P}$ be a family of funcitons $\{P_{1},P_{2},...,P_{N}\}$

A subfamily $(m,\epsilon)-\mathcal{C}$ of $\mathcal{P}$  is called  $(m,\epsilon)$-colony , if $(m,\epsilon)-\mathcal{C}$ is a subfamily of $\mathcal{P}$ such that for $some$ partial assignment to $m$ variables $\rho (m):{[n] \choose m} \rightarrow \{0,1\}$ $\max\limits_{i,j}dist (P_{i}|_{\rho},P_{j}|_{\rho}) \leq \epsilon $

  My question : is there a reference or results on $any$ concepts relating with the above  $(m,\epsilon)$-colony ?


texts: Where is Yao's original proof that distinguishers imply next-bit-predictors?

texts:
In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that distinguishes $X$ from the uniform distribution with advantage $\varepsilon$. Then there is an efficient algorithm that correctly predicts the $i$th bit of $X$ with probability $1/2 + \varepsilon / n$ given the first $i - 1$ bits of $X$, for some $i \in [n]$.
The lemma is typically attributed to Yao, with a citation to the paper "Theory and Application of Trapdoor Functions" (FOCS 1982). For example, in the journal version of Blum and Micali's paper "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits" (SICOMP 1984), they give a perfectly clear statement of (one version of) this lemma and attribute it to Yao.
But looking through Yao's paper, I am struggling to find the proof or even the statement of the lemma. In Section 2.3, Yao does briefly discuss the distinction between unpredictability and indistinguishability from the uniform distribution, but I can't find the generic reduction between the two notions of pseudorandomness in his paper.
Does the lemma somehow follow from some of the analysis in Yao's paper? Is there a "full version" of his paper with more details? What is the history of this lemma and its proof?


texts:
Let $S\subset F_2^n$ be a subset of size $\epsilon\cdot 2^n$.
Say I choose a random subspace $V$ of dimension $k$ in $F_2^n$.
I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\cap S \neq \emptyset$, with probability $\geq 1-\delta$.
As the points of $V$ are pairwise independent, one can show that $k=\log(\frac{1}{\epsilon\cdot \delta})$ suffices (See appendix C of Goldreich's "A sample of samplers").

I'm wondering whether smaller $k$ can suffice.
An argument for why this might be true is that a subspace should be ``better'' than a general collection of pairwise independent points, as many subsets of points in $V$ are more than pair-wise independent.


texts: Stronger version(2) of Isolation Lemma for linear forms

texts:
Klivans and Spielman give isolation lemma for linear forms in their paper Randomness Efficient Identity Testing of Multivariate Polynomials. Lemma 4 in this paper says.

  "Let $C$ be any collection of distinct linear forms in variables $z_1\ldots z_l$
  with coefficients in range {$0,\ldots, K$}.
  If $z_1,\ldots,z_l$ are independently chosen uniformly at random from set $S = \{0\ldots Kl/\epsilon\}$,
  then with probability greater than 1-$\epsilon$,
  there is a unique form of minimal value at $z_1,\ldots,z_l$".

Is there a stronger version of this lemma? Namely, can we choose set $S$ to be of size sublinear in $K$? Assume that $l$ is small compared to $K$.

Let me introduce a different notion of "stronger". Suresh Chari, Pankaj Rohatgi and  Aravind Srinivasan give Generalized isolating lemma in their paper Randomness-Optimal Unique Element Isolation, With Applications to Perfect Matching and Related Problems. Lemma 2[Generalized isolating lemma] in this paper says

  Let ($S$, $\mathcal{F}$) be any set system  and let $Z$ be a give upper bound on the size of unknown family $\mathcal{F}$. There is a simple scheme which uses $O(\log Z + \log N)$ random weights to assign integer weights to the $x_i$'s in the range $[0,N^7)$ such that with probability atleast $\frac{1}{4}$, there is a unique minimum weight set in $\mathcal{F}$.
  Here $S=\{x_1,x_2,\ldots x_N\}$ and $\mathcal{F}\subset2^S$.

Do we have something similar for isolating linear forms? Namely, if we know that number of linear forms is bounded by $Z$, can we reduce random bits as compared to $O(N\log(KN))$ random bits used in Randomness Efficient Identity Testing of Multivariate Polynomials. We also want that weights should not be too large, again weights sublinear in $K$ should be interesting.


texts: Problem property name where an optimal solution in a graph can be used as a solution in any subgraph

texts: Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal solution for the problem on $G$, then $S \wedge G_i$ is a solution on $G_i$ all $G_i \subseteq G$. Is there a canonical name for this property for a graph optimization problem?


texts: Describe the condition of "non-adjacent 3-cycles" in terms of the cubic adjacency matrix

texts:
Oleg Borodin and André Raspaud
  "A sufficient condition for planar graphs to be 3-colorable"
  Journal of Combinatorial Theory B88, 2003, 17–27

state the following conjecture:

  Conjecture 1.2:
  Every planar graph without adjacent 3-cycles and 5-cycles is 3-colorable.

My question is whether it is possible to describe this condition of "non-adjacent 3-cycles" purely in terms of the cubic adjacency matrix?


texts: Does there exist a data structure for quick list manipulation and order queries?

texts:
We have a set, $L$, of lists of elements from the set $N = \{ 1, 2, 3, ..., n \}$.  Each element from $N$ appears in a single list in $L$.  I am looking for a data structure which can perform the following updates:

$concat(x, y)$ : concatenates the list containing $y$ onto the end of the list containing $x$
$split(x)$ : splits the list containing $x$ directly after $x$

It also needs to perform the following queries:

$follows(x, y)$ : returns $true$ if $x$ and $y$ are in the same list and $y$ comes after $x$ (but is not necessarily adjacent to $x$)
$first(x)$ : returns the first element of the list containing $x$
$next(x)$ : returns the the next element after $x$ in the list containing $x$

I have already come up with a data structure which performs these updates in $O(lg^2 (n))$ and queries in $O(lg (n))$ time.  I'm mostly interested in whether or not there is already a data structure which can do this (hopefully faster?).

Motivation: rooted directed forests can be represented with two of these list sets and they allow quick calculation of reachability in such forests.  I want to see what else they can be used for and if all of this is already known.


texts: Rust is famous for its ownership type-system, but requires the programmer to annotate ownership in function signatures. Is it possible to do full program inference of ownership, without any annotations? What would be the pros and cons of such a system?


texts: Are there works on function complexity classes not included in FNP?

texts: Is there a sort of polynomial hierarchy in the case of function problems?


texts: Open or Interactive Constraint Satisfaction

texts:
In the past, I implemented coordination models using SAT and regular constraint satisfaction as the core workhorse in their engines. Continuing in this line of work, I would like to make the models more interactive, and the best way I see of doing this is to open up the constraint solver so that it is no longer a black box.

Thus,
I'm interested in learning more about constraint satisfaction where the constraints have what I will call external variables, predicates and functions,
that is, the constraint language may have predicates such as $\mathbf{P}(x)$ which can only be satisfied by consulting some agent external to the solver, and then only when $x$ is ground. A scenario where this is useful is whenever $\mathbf{P}$ corresponds to some external decision process that cannot be incorporated into the constraint solver. Such constraint solvers could be called open (as constraints are not entirely known) or interactive (as interaction is required to proceed with constraint satisfaction).

I would like to know both:

theoretical research done in this direction
tools or libraries that implement constraint solvers that allow interaction with the external world during the constraint solving process.


texts: A canonical complete problem for EXP and NEXP in terms of formulae

texts:
3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE.

Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen examples in terms of bounded halting problem, games and succinct formulation of problems in various classes within P and PSPACE.


texts: Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$

texts:
Say I have an undirected, weighted graph $G=(V,E)$ and I know a hamiltonian cycle of minimum weight in that graph. Can I use that information to efficiently find a hamiltonian cycle in $G'=(V',E')$ where $V'=V-\{v\}$ for some vertex $v$ and $E'$ is $E$ with all edges touching $v$ removed?

It is safe to assume that there still exists a hamiltonian cycle in $G'$.


texts: Inferring the Kolmogorov complexity of a string from its substrings' complexity

texts:
I know that the Kolmogorov complexity of a substring $v$ of an incompressible string $x$ has $C(v)\geq |v|-O(\log{|x|})$ , but I'm wondering if it is also possible to infer the complexity of a string given its substrings' complexity:
Specifically, If $x$ is a string of length $n$ and every substring $v$ of $x$ having length $m$ has complexity $C(v)\geq k$, is it possible to infer any general lower bound for $C(x)$ in terms of $n$, $m$, and $k$? I'm thinking that $C(x)$ cannot be much smaller than $k$ or else the $C(v)$ would not have $k$ as a lower bound. On the other hand, since $n$ can be much larger than $m$ this might balance things out.


texts: What is the correct definition of $k$-tree?

texts:
As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, and I've seen many seemingly incorrect definitions. For example, at least one place defines $k$-trees as follows:

  A graph  is called a $k$-tree if and only if either $G$ is the complete graph with $k$ vertices, or $G$ has a vertex $v$ with degree $k − 1$ such that $G \setminus v$ is a $k$-tree. A partial $k$-tree is any subgraph of a $k$-tree.

According to this definition, one can create the following graph:

Start with an edge $(v_1, v_2)$, a $2$-tree.
For $i=1\ldots n$, create a vertex $v_i$ and make it adjacent to $v_{i-1}$ and $v_{i-2}$.

Doing this would create a strip of $n$ squares with diagonals. Similarly, we can start creating a band from the first square in a direction orthogonal to the strip above. Then, we would have the first row and first column of an $n \times n$ grid. Filling in the grid is easy by creating vertices and joining them to the vertices to its above and to its left.

The end result is a graph that contains an $n\times n$ grid, which, in effect, is known to be of treewidth $n$.

A correct definition of $k$-trees has to be the following:

  A graph is called a $k$-tree if and only if either $G$ is a complete graph with $k$ vertices, or $G$ has a vertex $v$ with degree $k-1$ such that the neighbor of $v$ forms a $k$-clique, and $G \ v$ is a $k$-tree.

Then, the grid-like graph described as above cannot be created.

Am I correct?


texts: Path replanning in path finding algorithms

texts:
I'm working on a path finding algorithm for my thesis and I've gotten to a problem I need to solve where agents can replan their path if they need/have to. For example, if an agent is traversing across a corridor and then a barrier is inserted in, the agent has to replan because his old path is invalid. Another case is if the barrier already exists and the agent has to take a longer route, but while traveling, the barrier is removed and a significantly shorter route becomes available so the agent may replan but can still continue on his old path.

I have some ideas on how to work on the first case, but I'm at a loss for where to start for the second case. Does anyone know how other path planning algorithms deal with replanning, or can point me to any resources that can help me find some direction in tackling this problem?


texts: How can we know that formal methods work?

texts:
An important goal of formal methods is to prove the correctness of systems, either by automated or human-directed means. However, it seems that even if you can give a correctness proof, you may NOT be able to guarantee that the system will not fail. For example:

The specification may not model the system correctly, or a production system may be too complicated to model, or the system may be flawed inherently due to contradictory requirements. What techniques are known to test whether a specification makes any sense at all?
The proof process may be flawed too! Who knows that those inference rules are correct and legitimate? Furthermore, proofs can be very large, and how do we know that they do not contain errors? This is the heart of the critique in de Millo, Lipton, and Perlis's "Social Processes and Proofs of Theorems and Programs".  How do modern formal methods researchers respond to this critique?
At runtime, there are many nondeterministic events and factors that can seriously affect the system. For example, cosmic rays can alter RAM in unpredictable ways, and more generally we have no guarantees that hardware will not suffer Byzantine faults, which Lamport has proved are very difficult to be robust against. So the correctness of the static system does not guarantee the  system won't fail! Are there any techniques known to account for the fallibility of real hardware?
At present, testing is the most important tool we have for establishing that software works. It seems like it should be a complementary tool with formal methods. However, I mostly see research which is either focused on formal methods or testing. What is known about combining the two?


texts: Communication Complexity with real numbers

texts:
I'm looking into communication complexity with real numbers. One problem if we want to define this is that one can encode many real numbers $0.a_1a_2a_3... , 0.b_1b_2b_3..., 0.c_1c_2c_3...$ using only one number $0.a_1b_1c_1a_2b_2c_2...$

To get around this problem, existing papers that deal with this issue (such as Abelson (1978), Luo and Tsitiklis, and Chen(1994)) assume that the messages that can be sent between Alice and Bob must be continuously differentiable functions of the inputs $x_1,...,x_n$.

Do we need differentiability? Is there any problem if the messages are assumed to be continuous (not necessarily differentiable) functions?  I know that there's no continuous bijective function $f: \mathbb{R}^n \to \mathbb{R}$ for $n > 1$, so it seems like just assuming continuity should be enough.

Thanks!


texts:
I have an algebraic problem related to vectors in the field GF(2).
Let $v_1, v_2, \ldots, v_m$ be  (0,1)-vectors of dimension $n$, and $m=n^{O(1)}$. Find a polynomial time algorithm that finds a (0,1)-vector $u$ of the same dimension such that $u$ is not the sum of any $(\log n)^{O(1)}$ vectors among $v_1,v_2, \ldots, v_m$. The addition of vectors is over the field GF(2), which has two elements 0 and 1 ($0+1=0+1=1$, and $0+0=1+1=0$).

It is easy to see the existence of such a vector u by a simple counting argument.  Can we find $u$ in a polynomial time?  It is trivial to find $u$ in exponential time.   I will send a $200 check award for the first correct solution.


texts: Complexity question from mathematical music theory

texts:
Fix an positive integer $N$.

A row means any linear ordering $R=(n_i)_{0\leq i <N}$ of the additive group ${\Bbb Z}/N{\Bbb Z}$.

Call $R$ a (generalized) all-interval row if the elements of the sequence $(n_i-n_{i-1})_{1\leq i <N}$ exhaust $({\Bbb Z}/N{\Bbb Z})\setminus \{0\}$. (This requires even $N$.)

I would like to know if the following decision problem is NP-complete:

Given $M<N$ and a sequence $S=(n_i)_{0\leq i <M}$ with $n_i\in {\Bbb Z}/N{\Bbb Z}$, does $S$ extend to an all interval row?


texts: Complexity of deciding whether a matrix is totally regular

texts:
A matrix is called totally regular if all its square submatrices have full rank. Such matrices were used to construct superconcentrators. What is the complexity of deciding whether a given matrix is totally regular over the rationals? Over finite fields?

More general, call a matrix totally $k$-regular if all its square submatrices of size at most $k$ have full rank. Given a matrix and a parameter $k$, what is the complexity of deciding whether the matrix is totally $k$-regular?


texts:
A direct product theorem, informally, says that computing $k$ instances of a function $f$ is harder than computing $f$ once.

Typical direct product theorems (e.g., Yao's XOR Lemma) look at average-case complexity, and argue (very roughly) that is $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed by circuits of size $s' < s$ with probability better than $p^k$.

I am looking for different types of direct product theorems (if they are known). Specifically:

(1) Say we fix the probability of error $p$ and are instead interested in te size of the circuit needed to compute $k$ copies of $f$? Is there a result that says that if $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed with probability better than $p$ using a circuit of size less than $O(k \cdot s)$?

(2) What is known with respect to worst-case complexity? E.g., if $f$ cannot be computed (with 0 error) by circuits of size $s$, what can we say about the complexity of computing $k$ copies of $f$ (with 0 error)?

Any references would be appreciated.


texts: covering an NxN grid using overlapping vs. non-overlapping windows residing k points in each

texts:
Let the problem, $P_{overlapping}$, be the following.
We have an $N_1 \times N_2$ grid. Each cell of the grid can have the
value either 0 or 1. Assume that we have $a \times b$ overlapping windows as
the subset of the $N_1 \times N_2$ grid where $a < N_1$ and $b < N_2$,
and we want to have at least $k$ of the cells in each window
have the value 1. We are interested in minimizing the number
of cells having the value 1 when $N_1 \times N_2$ grid is covered by
$a \times b$ overlapping windows having $k$ cells with the value 1 in each.

And, let the problem, $P_{non-overlapping}$, be the following.
We have an $N_1 \times N_2$ grid, and each cell of the grid can have the
value either 0 or 1 similar to the problem, $P_{overlapping}$.
But this time, assume that we have $a \times b$ non-overlapping windows as
the subset of the $N_1 \times N_2$ grid where $a < N_1$ and $b < N_2$,
and we want to have at least $k$ of the cells in each window
have the value 1. We are interested in minimizing the number
of cells having the value 1 when $N_1 \times N_2$ grid is covered by
$a \times b$ non-overlapping windows having $k$ cells with the value 1 in each.

For an $N \times N$ grid, $\left \lfloor \frac{N}{a} \right \rfloor \times
\left \lfloor \frac{N}{b} \right \rfloor \times
k$ is the lower bound for
$P_{non-overlapping}$.
In order to find optimal solutions for the problem $P_{overlapping}$, I used the following Integer Linear Programming formulation:

$
\begin{align}
\label{eqnew:01}
\mbox{Minimize: } &{\displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} x_{ij}}   &;&  x_{ij} \in \{0,1\}   \notag \\
\mbox{Subject To: } & {\displaystyle  \sum_{i=m}^{m+a-1} \ \sum_{j=n}^{n+b-1} x_{ij} \ge k}  &;&     \forall{m}, \ 1 \le m \le N_1-a+1 \notag \\
                    &          &,&   \forall{n}, \ 1 \le n \le N_2-b+1
\end{align}

$

And using GLPK linear programming solver, and solving the problem for some $N \times N$ grids with $a \times b (12 \times 9)$ overlapping windows for $k=2$,
I got some results for
optimum solutions for $P_{overlapping}$. Interestingly, when
I used  the lower bound for the problem $P_{non-overlapping}$,
$N \times N$ grid, $\left \lfloor \frac{N}{12} \right \rfloor \times
\left \lfloor \frac{N}{9} \right \rfloor \times
2$ for $k=2$; solutions for both problems are the same as seen in the following graph

comparison of the problems

And, finally, my question is the following.
Why are these two different problems have the same solutions
for $k=2$? How about for $k$ values other than 2?
Is this reasonable theoretically?

Many thanks for your time, fellas.

Baris


texts:
A set of numbers $S=\{x_1,...,x_n\}$ is said to be algebraically dependent if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a subset thereof).

  Given numbers $S=\{x_1,...,x_n\}$, is it decidable whether they are algebraically dependent?

Now, there is obviously an encoding issue here, since the numbers need to be transcendental, so describing them is problematic. Any solution would do, but specifically, I am interested in the case where all the numbers are of the form $e^{a_i}$, where the $a_i$'s are linearly independent over $\mathbb Q$.

The motivation for this question is understanding whether a (positive) solution to Schanuel's conjecture would automatically lead to a constructive solution.

UPDATE (based on the comments): the encoding of the numbers is an issue. I'll accept any answer which suggests either a reasonable encoding for a subset of the reals for which the problem is non-trivial, or a solution that uses a computational model that allows real numbers.


texts: How many subsets of size L do not contain the first k arbitrary pairs?

texts:
Let there be a large set $X$, and a bijective function $f$ which maps the integer range 1 to $|X| \choose 2$  onto the subsets of $X$ of size 2. Given integers $L$ and $k$, where $2 \leq L \leq |X|$ and $1 \leq k \leq {|X| \choose 2}$, what is the cardinality of the collection $P^L_k=\{Y : Y \subset X$ and $|Y|=L$ and $f(i) \not\subset Y \; \forall 1\leq i \leq k\}$.

Is there a more efficient way than generating all subsets of size $L$ and checking? Alternatively, do you see a good way to approximate the cardinality?


texts: Clarification of leftmost maximal periodicities

texts:
Main describes an algorithm for detecting all 'leftmost maximal' periodicities in a string in linear time, using the following definitions:

A periodicity of a string $x$ a nonempty substring of $x$ of the form $p^mq$ with $m\ge2$ and $q$ a proper prefix of $p$.
A leftmost periodicity of $x$ is a periodicity $x[i] \dots x[j]$ such that if $x[i] \dots x[j] = x[i'] \dots x[j']$ then $i \le j$.
A periodicity $x[i] \dots x[j]$ with period $k$ is maximal if:

$i = 1$ or $x[i - 1] \dots x[j]$ is not a periodicity with period $k$, and
$j = |x|$ or $x[i] \dots x[j + 1]$ is not a periodicity with period $k$

Main goes on to present a theorem (3.4): given an s-factorisation of a string $x=u_1 \dots u_k$ and let $r$ be a periodicity of $x$, with leftmost occurrence of $r$ at $x[i] \dots x[j]$, and with the $j^{th}$ position of $x$ within $u_h$, then the $i^{th}$ position of $x$ occurs before $u_h$.

This theorem forms the basis of the algorithm for computing 'leftmost maximal' periodicities of a given string $x$. The algorithm finds all maximal periodicities of $t_hu_h$ for $2 \le h \le k$ where $t_h$ is a substring of length $2|u_{h-1}| + |u_h|$ that immediately precedes $u_h$, such that each periodicity begins in $t_h$ and ends in $u_h$.

My question concerns the meaning of "leftmost maximal", particularly if this should be read "periodicities that are both leftmost and maximal", or "maximal periodicities that are leftmost". To clarify the distinction, consider the string $x=aaabcaabd$. Clearly the periodicity $aaa$ starting at $x[1]$ is leftmost maximal under both interpretations, but is the periodicity $aa$ starting at $x[6]$ also leftmost maximal? According the the first interpretation, it isn't, and $x$ only has one leftmost maximal periodicity. According to the second, it is, and $x$ has two leftmost maximal periodicities.

It seems to me that Main's algorithm gives 'leftmost maximal' periodicities of the first kind: the s-factorisation of $aaabcaabd$ is $a|aa|b|c|aab|d$, hence the second $aa$ periodicity starting at $x[6]$ will not be included as it is contained entirely in a single s-factor ($u_5 = aab$).

However, as best as I can tell, the result of Kolpakov and Kucherov, for computing all maximal periodicities of string in linear time, assumes the second definition. Kolpakov and Kucherov use Main's result as a key component of their algorithm.


texts: Costs of performing approx. nearest neighbor search in a skip quadtree

texts:
NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$?

Quadtrees are efficient spatial indices. I have a puzzle with the implementation of a nearest neighbour search in a compressed quadtree structure as described in [2]. (Without going into details, the search is going top-down along so-called equidistant squares, ending in the tail node of an equidistant path. In the attached image this might be any of the nodes in the southeast filled with points.)

For their algorithm to work, one must maintain for each node -- a square with at least two non-empty quadrants -- pointers for each lowest (closest in the hierarchy) ancestor node in each of the four directions (north, west, south, east). These are indicated by the green arrows for the nodes' westward ancestor (the arrow points at the ancestor square's centre).

The paper claims these pointers can be updated in O(1) during point insertions and deletions. However when looking at the insertion of the green point, it seems I need to update any arbitrary number of pointers, in this case six of them.

I am hoping for a trick to do this pointer update in constant time. Maybe there is a form of indirection that can be exploited?

EDIT:

The relevant section from the paper is 6.3, where it reads: "if the path has bends, then in addition to the $log(c/ε)$ lowest ancestors of $q$, we should also consider for each of the $2^d$ directions the lowest ancestor of $q$ that goes towards that direction [...] Finding these squares from $q$ can be done in $O(1)$ time per square if we associate additional $2^d$ pointers to each square in $Q_0$ pointing to its closest ancestors for each direction. These pointers can also be updated in $O(1)$ time during an insertion or deletion of a point."

[2]: Eppstein, D. and Goodrich, M.T. and Sun, J.Z., “The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data,” in Proceedings of the twenty-first annual symposium on Computational geometry, pp. 296—305, 2005.


texts: ${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

texts:
We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$.
We also know that ${\bf E} \subset {\bf EXP}$, where
${\bf E} = \cup_c DTIME[2^{cn}]$ and
${\bf EXP} = \cup_c DTIME[2^{n^c}]$.

It has been shown by Book in [1972] that ${\bf E} \not = {\bf NP}$ and in 1974 [1974] that ${\bf E} \not = {\bf PSPACE}$.

${\bf Question}$: Why is it believed that there could be an exponential time algorithm for any problem in ${\bf PSPACE}$?

Edit:  How is it still possible to argue that an NP-complete problem or a PSPACE-complete problem could possibly have a polynomial time algorithm or an exponential time algorithm when it is known that ${\bf P} \subset {\bf E} \subset {\bf EXP}$ and that ${\bf E} \not = {\bf NP}$ and ${\bf E} \not = {\bf PSPACE}$. The fact that ${\bf E} \not = {\bf NP}$ and ${\bf E} \not = {\bf PSPACE}$ should be able to disqualify one of these two possibilities. [The possibility that 1) A NP-Complete problem or a PSPACE-Complete problem having a Polynomial time algorithm. OR 2) A NP-Complete problem or a PSPACE-Complete problem having an Exponential time algorithm.]

[1972]: R. Book. On languages accepted in polynomial time. SIAM ournal on Computing, 1(4):281-287, 1972.
[1974]: R. Book. Comparing complexity classes. Journal of Computer and System Sciences, 3(9):213-229, 1974.


texts: Certainty of mutual confirmation over faulty channels?

texts:
This is a very theoretical question, although I am sure the problem pops up in lots of IT and automation applications. Still, I prefer to formulate it in an action-movie scenario (a bit of the Prisoner's Dilemma style).

"You" and "I" are two groups of partisans hiding in two different places in the forest. The enemy are holding some of our guys in a heavily guarded prison. We want to attack the prison and free our comrades, but this can only succeed if both our groups participate. If just one group goes ahead, it will get massacred for nothing.

So we need to be sure we're both going for it. But the only means of communication we have are signal flares, and firing one does not guarantee it will be seen (due to distance, fog, whatever).

I leave aside the issue of the enemy seeing our flares, or firing their own to confuse us - it's just my flares and yours, and my eyes and yours.

Suppose I fire a flare meaning "I'm ready, are you?".  You see my flare and you reply with another, meaning "Yes I'm ready too, let's go for it!". But I will only start if I see your flare, so you cannot start unless you are sure I have seen it. So now I need to fire another flare to confirm I have seen your reply...... and apparently this chain will never end. No matter how long we keep firing our flares, the last (and decisive) one will be unconfirmed.

Any ideas? For starters, does this problem already have a name that's recognizable in information theory?

TIA!


texts: Parameterized complexity of inclusion of regular languages

texts:
I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed alphabet $\Sigma$, with the operations union, Kleene-star and concatenation.)

Input: Two regular expressions $E_1$ and $E_2$
Question: Is it true that $L(E_1)\subseteq L(E_2)$?

REGULAR LANGUAGE INCLUSION is known to be PSPACE-complete [1].

The classic way to solve it (in PSPACE) is to construct the NFAs $A_1$ and $A_2$ associated to $E_1$ and $E_2$, to build a DFA $D_2$ from $A_2$, complement it into a DFA $D_2^C$, and finally, build the intersection automaton $A_P$ from $A_1$ and $D_2^C$ corresponding to the intersection of $L(E_1)$ and $L(E_2)^C$. Now $L(E_1)\subseteq L(E_2)$ if and only if there no an accepting path in $A_P$.

If I am not mistaken, the whole process can be done in polynomial time when $E_2$ is a fixed language, since the only exponential blow-up comes from transforming $A_2$ into $D_2$. Even better, the problem is FPT when parameterized by $|E_2|$, the length of $E_2$.

This motivates my question:

  Question: When $E_1$ is a fixed expression, what is the complexity of REGULAR LANGUAGE INCLUSION? Does it remain PSPACE-complete?

[1] L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: preliminary report. Proceedings of the fifth annual ACM Symposium on Theory of Computing, STOC '73, pp. 1-9.

Remark: Being a non-expert in the field, I find [1] (and related papers of that time) quite unreadable, and couldn't find another proof of the PSPACE-completeness - any pointer to a modern proof, such as in a book, is very welcome! Also, the authors seem to allow squaring in their regular expressions, which is nowadays rather non-standard, I believe.)


texts: Some algorithmic questions on permutations

texts:
I'm interested in the possibility of fast algorithms for the following two problems on permutations.

1)

Given a permutation $\pi$ and an integer $k$, compute a pair $(\mathcal{C},\mathcal{A})$ where $\mathcal{C}$ is a maximum $k$-chain and $\mathcal{A}$ is a corresponding $l$-antichain certifying the optimality of $\mathcal{C}$.

If you only care about $\mathcal{C}$, this can be done in $O(k n \log n)$ by an involved algorithm ('Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms' by S. Felsner and L. Wernisch). It seems possible to obtain a simpler algorithm that would also provide a certificate.

2)

Given a permutation $\pi$, compute the pair of Young tableaux $(P,Q)$ associated to $\pi$ by the Robinson-Schensted bijection. Is it possible to do it in subquadratic time?

Note: if we only care about the first $k$ rows of each tableau this can be done in $O(k n \log n)$ time in the RAM model; by Greene theorem, the cumulated size of the first $k$ rows gives the cost of an optimum solution for 1), without providing an explicit solution. Thus question 1) seems to require a different approach.


texts: Is there a simple game with asymmetric complexity?

texts:
Consider full information two-player combinatorial games that end after a polynomial number of moves, and in an alternating way, the players picks from a finite number of allowed moves.
The usual question is, how difficult it is to tell from a given position the winner.
Another would be, how difficult it is to pick a winning move from a winning position.
(Here I call a move winning, if the position remains winning after playing it.)
To differentiate, I will call the former POSITION-COMPLEXITY and the latter MOVE-COMPLEXITY.

It is easy to see that if the MOVE-COMPLEXITY is in $P$ or $PSPACE$, then so is the POSITION-COMPLEXITY - we can calculate the optimal moves and check who wins at the end.
(I have not really thought through what happens if the MOVE-COMPLEXITY is in $NP$, probably the POSITION-COMPLEXITY is in something like $P^{NP}$.)
However, there are dummy examples when the MOVE-COMPLEXITY is trivial and the POSITION-COMPLEXITY is arbitrary hard - like the (not very interesting) game of checking what is the output of an algorithm, with the players making the next steps, being allowed only one move.
I have digressed a bit, my main question is the following.

  Is there a natural game, where the MOVE-COMPLEXITY of the two players is different?

For example, the game where the first player picks the values of the variables of a CNF (that might not have a solution), while the second player is trying to solve a SOKO-BAN puzzle (that might not have a solution), is such an example.


texts:
This questions is cross-posted from MathOverflow

A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use different definitions. Here I propose my own definition (though I probably consider it my own out of ignorance rather than originality). This definition seems very natural but immediately raises several questions which I find difficult to answer. Here I ask the two questions that seem the most fundumental. Here it goes:

Fix $V$ a complex inner product vector space of finite dimension $n$. Consider $A$ the *-algebra End($V$). Take $\Gamma = \mathbb{Z}^d$ a lattice. Define the *-algebra $A_\Gamma$ (quantum cellular automaton observables) in the following manner. Assign to each element $x$ of $\Gamma$ a copy $A_x$ of $A$. To each finite subset $S$ of $\Gamma$ we can correspond the *-algebra $A_S$ defined by

$A_S$ := Tensor product of $A_x$ over $x \in S$

For two finite subsets $S$, $R$ of $\Gamma$ with $S$ contained in $R$ we have the morphism

$i_{S,R}$: $A_S \rightarrow A_R$

obtained by tensoring with $1 \in A_y$ for all $y \in R\backslash S$. We define $A_\Gamma$ to be the direct limit of $A_S$ w.r.t. $S$.

Denote $T_\Gamma$ the group of translations of $\Gamma (Z^d)$. $T_\Gamma$ acts on $A_\Gamma$ in the obvious manner.

A quantum cellular automaton is defined to be a *-endomorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. An invertible quantum cellular automaton is defined to be a *-automorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. The 1st question is:

  Are all quantum cellular automata invertible?

Any unit vector $v \in V$ defines a state

$\phi_v$: $A_\Gamma \rightarrow C$

in the following manner. Suppose $S$ is a finite subset of $\Gamma$ and for any $x \in S$, $a_x$ is an element of $A_x$. Then we have $a_S$ an element of $A_S$ (and hence of $A_\Gamma$) defined by

$a_S$ := tensor product of $a_x$ over $x \in S$

We then define

$\phi_v(a_S)$ := product of $(v, a_x v)$ over $x \in S$

It is easy to see this extends uniquely to a linear map $\phi_v$: $A_\Gamma \rightarrow C$ and that the map is a state.

Fix $v$ in $V$. We construct the Hilbert space $H_v$ in the following manner. Choose $v_1$ ... $v_n$ an orthonormal basis of $V$ s.t. $v_1 = v$. Consider maps

$\alpha: \Gamma \rightarrow \{1 ... n\}$

s.t. $\alpha(x) = 1$ for all $x$ except a finite set. Define $J$ to be the set of such $\alpha$. To each $\alpha \in J$ we assign the basis vector $\Psi_\alpha$ of $H_v$, thought of as

$\Psi_\alpha$ := tensor product of $v_\alpha(x)$ over $x \in \Gamma$

Thus $H_v$ is defined to be $l^2(J)$. It is easy to see that $H_v$ thus defined depends only on $v$ and not on $v_2$ ... $v_n$ i.e. that for any two choices of $v_2$ ... $v_n$, there is a canonical isomorphism between the corresponding Hilbert spaces.

There is a natural *-homomorphism

$\rho$: $A_\Gamma \rightarrow B(H_v)$

where $B(H_v)$ is the *-algebra of bounded operators on $H_v$. Thus, any unit vector $\Psi \in H_v$ defines a state

$\phi_\Psi$: $A_\Gamma \rightarrow C$

by

$\phi_\Psi(a) = (\Psi, \rho(a) \Psi)$

Now, fix an invertible quantum cellular automaton $f$: $A_\Gamma \rightarrow A_\Gamma$. Suppose $v$ in $V$ is s.t. $\phi_v$ is $f$-invariant. Then $f$ is called $v$-representable if there exists

$U$: $H_v \rightarrow H_v$

a unitary operator s.t. for any $\Psi \in H_v$ we have

$\phi_U \Psi = f^*(\phi_\Psi)$

It is clear that if such $U$ exists it is unique.

The 2nd question is:

  Is any invertible quantum cellular automaton $v$-representable for any $v$ with $\phi_v$ $f$-invariant?


texts: Why does Fourier analysis of Boolean functions "work"?

texts:
Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including property testing, pseudorandomness, communication complexity, and quantum computing.

While I got comfortable using Fourier analysis of Boolean functions as a very useful tool when I'm tackling a problem, and even though I have a pretty good hunch for which cases using Fourier analysis would probably yield some nice results; I have to admit that I'm not really sure what it is that makes this change of basis so useful.

Does anyone has an intuition as to why Fourier analysis is so fruitful in the study of TCS? Why so many seemingly hard problems get solved by writing the Fourier expansion and performing some manipulations?

Note: my main intuition thus far, meagre as it may be, is that we have a pretty good understanding of how polynomials behave, and that the Fourier transform is a natural way of looking at a function as a multilinear polynomial. But why specifically this base? what is so unique in the base of parities?


texts: View of Multiplicative Weights in contexts of combinatorial optimization, low-regret/online optimization, and entropy-regularized gradient descent?

texts:
Also called exponentiated gradient.

I understand these are three places where multiplicative weights shows up (i.e. $w_{t+1} = w_{t}e^{- \text{loss}(w_{t})}$ or variations. And I understand a bit about these interpretations. But what ties them all together? In particular, multiplicative weights has been around a long time and appeared in combinatorial optimization contexts that I understand much less well than the low-regret interpretation. I kind of understand the connection between convex optimization and low-regret learning, but I don't understand why entropy appears as the proximal gradient regularization term. Is there an information-theoretic interpretation of all this? And does it clarify anything?

In other words, there's a web of connections here, I know a lot of people are paying attention to this, and I understand bits and pieces, but what's the best lens to get at the big picture?

Related papers on regret (pdf), mirror descent, and
multiplicative weights application from S.A. Plotkin, D.B. Shmoys, and E. Tardos (1991).


texts: Computing distances with approximation less than 2 in general graphs?

texts:
Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use subquadratic space and sublinear query time.

I am aware of Zwick's result that uses matrix multiplication, but I am curious if any combinatorial algorithms are known for this problem?


texts: Hard gaps in maximum constraint satisfaction problems?

texts:
An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $r\lt 1$).

  Is there any known dichotomy theorem that classifies all Max CSP based on whether they have hard gaps or not?

Edit Dec 16, 2010: MAX CSP with hard gap means that the problem has optimal inapproximability factor. For instance, 3SAT has hard gap at location one since it is polynomial time approximable to a factor $7/8$ but it is $NP$-hard to obtain approximation factor $7/8+ \epsilon$ even when all clauses are satisfiable.


texts: A variant of the Maximum Weight Clique problem

texts:
I am trying to solve a problem that I could reduce to the following:
Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{i\in Q}w_i-\sum_{e=\{i,j\},i,j\in Q}w_e$ is maximized. Interestingly, the graph in my case turns out to be Perfect. It is well known that the problem is polynomial time solvable for perfect graphs if we have $w_e=0$ for all $e\in E$. I am not sure about the status of the above problem. Is it NP-hard even for perfect graphs? May be this problem has been studied before but I am not able to find any reference. Any pointers will be appreciated. Thanks in advance.

The problem can be written as a quadratic program that maximizes $x^{T}Wx$ over $x\in TH(\overline{G})$, where $W$ is the $|V|\times |V|$ matrix having $W(i,i)=w_i, i\in V, W(i,j)=-w_e,\text{ for } e=\{i,j\}$ and $0$ otherwise. $TH(\overline{G})=STAB(\overline{G})$ when $G$ is perfect. The quadratic programming problem is polynomial time solvable only when the matrix $W$ is positive definite, https://en.wikipedia.org/wiki/Quadratic_programming. This only shows that for special inputs the problem is in $P$.


texts:
Is there any way to get $n$ primes efficiently? That is, is there any polynomial algorithm for doing this? ($n$ is the cardinality.)

Re-phrasing the question:

1) Suppose that at the input level, we insert $n$. This is the number of primes we want to obtain. (any set) (So, for example, getting five number of prime. The example output would be 2,3,5,7,11)

2) Is there any algorithm that does this efficiently? What would be its complexity (based on $n$)?


texts: When can be used the "uncompute garbage" trick in quantum computing?

texts:
As far as I have understood, "uncomputation" in quantum computing is a way to restore the working memory to its initial state, while keeping the result of the computation in another register. This trick is usually explained as follows:

  Assume you have a classical function $f : \{0,1\}^n \rightarrow \{0,1\}$. Then there exists a unitary $U_f$ that maps state $|x\rangle|0\rangle |0\rangle$ to $|x\rangle |g(x)\rangle |f(x)\rangle$, where $|g(x)\rangle$ is the state of the working space at the end of the computation. Moreover, $|x\rangle |g(x)\rangle |f(x)\rangle$ is a pure state (not a superposition). You can now add an extra register $|0\rangle$ in which the result $f(x)$ of the computation is CNOT at the end, i.e. we get $|x\rangle |g(x)\rangle |f(x)\rangle |f(x)\rangle$. Finally, apply $U_f^{-1}$ to the first three registers of this state so as to obtain $|x\rangle |0\rangle |0\rangle |f(x)\rangle$. The working memory has been cleaned.

I'm fine with this procedure. However, it seems to me that it works because $|x\rangle |g(x)\rangle |f(x)\rangle$ is a pure state. It would also be ok
for a superposition of pure states that all have the same register $|f(x)\rangle$ at the end (before we CNOT). But it doestn't work in the other cases. Consider for instance this circuit:

After the first Hadamard has been applied, $x_1$ contains the result of the computation (it is the same as $|f(x)\rangle$ previously, but now it is
a superposition). It is CNOT with the extra register $x_2$ and then another Hadamard is applied. The final state is $(|00\rangle+|01\rangle+|10\rangle-|11\rangle)/2$.
Obviously, the first qubit has not been restored to its initial state.

My first question is: am I right when I say that the uncomputation trick only works when the register that is copied is not in superposition? My second
question is about the following algorithm taken from this paper from Scott Aaronson:

$\mathcal{Q}_*$ is a quantum circuit that takes some witness $|z\rangle$ as input, and outputs $0$ or $1$. It can be thought as a circuit for QMA,
for which the real input $x$ has been fixed and we want to know if there exists a witness that is accepted with high probability (the idea of this
paper is to only try with pure states witnesses $|z\rangle$). In this context, I don't understand why the "uncompute garbage" step restores the memory.
I think that the register containing the output $b$ is CNOT in an extra register (which will be measured later), but since it's usually a
superposition of $|0\rangle$ and $|1\rangle$ I don't understand why the uncomputation would work.


texts: Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

texts:
I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075).

The authors give a characterization of strong approximation resistance which I don't completely understand.

Given a measure $\Lambda$ in $R^{k + {k \choose 2}}$, (the coordinates of a point in this space are written $x_1, x_2, ..., x_k, x_{(1,2)}, ... x_{(i,j)}, ... , x_{(k-1, k)}$) and some subset $S \subset [k]$,  they define $\Lambda_S$ as the measure projected onto the coordinates of $S$.

I can think of two such interpretations for $\Lambda_S$. First fix $k=4$ so that $\Lambda$ is in $R^{10}$. Our coordinates are $1, 2, 3, 4, (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$. Fix $S = \{1, 2, 3\}$.

Interpretation 1: Under one interpretation, the measure $\Lambda_S$ should be projected using the coordinates $1$ and $2$ and $3$ only.

Interpretation 2: Under the other interpretation we should also include the "pair" coordinates so we should project using $1$, $2$, $3$, $(1,2)$, $(1,3)$, $(2,3)$.

I'm thinking that the second interpretation is the correct one. This is because the definition is reformulated in terms of matrices in definition 2.11 on page 19. In this formulation, we have a measure $\zeta$ on a subspace of matrices in $R^{(k+1)\times(k+1)}$ analogous to the measure $\Lambda$, but given $S$, projection measure $\zeta_S$ is defined by taking the submatrix formed by restricting to rows and columns whose indices are in $S$. But in this formulation, the entry $i,j$ of the matrix corresponds to the coordinate $x_{(i,j)}$.

Am I correct? Or is there some way to reconcile the first interpretation with the matrix analogue?


texts: Do nested convex bodies have increasing "Volume/Surface Area" ratios?

texts:
Suppose we have two convex bodies $A$ and $B$, where $A \subseteq B$.  Is it always true that $\mathrm{Vol}(A)/\mathrm{SurfaceArea}(A) \leq \mathrm{Vol}(B)/\mathrm{SurfaceArea}(B)$?

It's true in all the examples I've tried, but I'm not sure how to prove the general case, or whether the general case is even true.


texts: What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties?

texts:
In this paper, Hajnal states the following lemma:

  Let $\mathscr{G}_{n, m}$ be the set of all bipartite graphs with $n$ vertices in the left part and $m$ vertices in the right part. Suppose $\mathscr{P} \subseteq \mathscr{G}_{n, m}$ is nontrivial, monotone, and invariant with respect to bipartite graph isomorphisms. Order the set of minimal graphs with property $\mathscr{P}$ lexicographically according to the sorted list of degrees of left vertices, and let $G$ be the first minimal graph with property $\mathscr{P}$ according to this order. Then the zero-error randomized query complexity of $\mathscr{P}$ is $\Omega(\frac{\Delta_L(G)}{\delta_L(G)} n)$, where $\Delta_L(G)$ is the maximum degree of any vertex in the left side of $G$ and $\delta_L(G)$ is the average degree of the vertices in the left side of $G$.

(In fact, Hajnal actually uses a slight extension of the above lemma.) The same lemma is also used by Gröger in this other paper and by Chakrabarti and Khot in this other paper. But I can't figure out the proof of Hajnal's lemma. Hajnal attributes the lemma to Yao and cites this paper. But Yao's paper doesn't actually claim that lemma in that form.

Yao's paper does prove a closely related lemma. (Lemma 5 in Yao's paper, or equivalently Lemma 6 in this journal version of Yao's paper.) By adapting the proof of the lemma in Yao's paper, I see how to prove Hajnal's lemma under the extra assumption that $\delta_L(G) \geq \Omega(1)$. I'm having trouble with the case that $\delta_L(G)$ is subconstant.

(I'll now assume that the reader is familiar with Yao's proof.) My understanding is that to prove Hajnal's lemma, the idea is to modify Yao's proof by essentially just replacing $\lambda(n)$ with $\delta_L(G)$ and $\mu(n)$ with $\Delta_L(G)$ everywhere. At a high level, with these modifications, Yao's reasoning still makes sense, and shows that to "discover enough missing edges", the query algorithm will need to make at least about $\frac{\Delta_L(G) - 4\delta_L(G)}{\lceil 4 \delta_L(G) \rceil} \cdot \frac{n}{2}$ queries.

The issue is that when $\delta_L(G)$ is subconstant, because of the ceiling operation, that lower bound is only $O(\Delta_L(G) n)$, which is much smaller than the bound $\frac{\Delta_L(G)}{\delta_L(G)} n$ that appears in Hajnal's lemma. (Concretely, the issue is that each set $T_i'$ needs to have an integer number of vertices in it.)

How can the proof be patched?


texts:
I don't know if this is the right place to ask but can someone explain in brief what T-Coloring algorithm is and provide a pseudo-code?

I've tried googling it but still cant understand what is it and how to use T-Coloring


texts: "Send Once"-One way Multiparty Communication Complexity

texts:
There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting.

I want to consider more restricted protocol that is "send once" protocol.

For example, Alice, Bob, and Cate are players and their communication must follow the following way:

Alice is only able to send Bob.
Bob   is only able to send Cate .

Each plyer sent bits just one time.

Are there lower bounds results and methods that k-party NIH or NOF communication complexity for set-disjointness and other functions ?


texts: Lower bounds for learning in the membership query and counterexample model

texts:
Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a minimal DFA of $n$ states is learnable in polynomial time (where the proposed functions are DFAs) with $O(mn^2)$ membership-queries and at most $n−1$ theory-queries ($m$ is the size of the largest counter-example provided by the tutor). Unfortunately, she does not discuss lower bounds.
We can generalize the model slightly by assuming a magical tutor that can check equality between arbitrary functions and provide counterexamples if different. Then we can ask how hard it is to learn classes bigger than regular languages. I am interested in this generalization and the original restriction to regular languages.
Are there any known lower bounds on the number of queries in the membership and counterexample model?
I am interested in lower bounds on the number of membership queries, theory queries, or trade-offs between the two. I am interested in lower-bounds for any class of functions, even for more complicated classes than regular languages.
If there are no lower-bounds: Are there known bariers to proving query lower bounds in this model?

Related questions
Are there improvements on Dana Angluin's algorithm for learning regular sets


texts:
I was wondering if anyone knew on whether it is possible to construct a quantum oracle that was able to detect whether a given state vector was "non-negative"?  Essentially I have a classical problem where the solution would be a non-negative vector but I am unsure about how to bring this into a quantum mechanical form since we're dealing over the complex field.

If anyone has any papers that they have come across that would be along these lines, would be greatly appreciated!


texts: Computation of reals: floating point vs TTE vs domain theory vs etc

texts:
Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised exact computation of reals. Clearly, the problem of floating point precision has not dwindled in relevance, so why haven't these theories become more mainstream and why aren't there more conspicuous implementations of them?

For example, are there domains of applications where we don't care much about floating point errors? Are there significant complexity concerns?


texts:
My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this:

The idea is to start from x and reach o via the normal rules.  Additionally, you can "hop" from any integer $a$ to any other integer $b$, but you must pay $|a-b|$ dollars for the privilege.  The goal is to solve the maze for the least cost.  In the example above, we could go from x to o via x-14-18-27-28-o at cost 5, but it's cheaper to go x-13-11-9-8-29-28-o for only 4.

So here is my question: what is the best solution (in terms of asymptotic running time) you can think of for solving this?  You may make any reasonable assumptions about the input format.

Note: I am using the "puzzles" tag here because I have an $O(n^2)$ answer in mind, but I'm not sure it's optimal and would like to see if someone else can improve my solution.  (Here $n$ is the number of integers in the maze.)


texts: Vector representation of probabilistic automaton

texts:
Suppose we have $N$ states

$q_i$, $0\leq i<N$

Suppose we have $N\times N$ probability matrix

$p_{ij}$, $0\leq i<N$, $0\leq j<N$,

And suppose a machine, which is being in state $q_i$ then goes to state $q_j$ with probability $p_{ij}$.

Question #1: is this what is called "probabilistic automaton"?

Next.

We can introduce another interpretation: represent each state of a machine as a column of values

$w_i$, $0\leq i<N$

each representing a "weight" of previously defined state $q_i$.

If machine is completely in state $q_0$ then we have

$w_i=1, i=0$

$w_i=0, i\neq0$

and so on.

In this interpretation each state change is just changing of the weights of a state column

$w_i \rightarrow p_{ij} w_i$

assumming summation by.

Question #2: it this a precise interpretation of previous PA? If each first interpretation corresponds with second and vice versa?


texts: Polynomial approximation algorithm for set cover with assumption

texts:
We want to cover $n$ elements with some sets from $S_1, …, S_m$ (classical set cover).

We furthermore suppose that any element belongs to at least $k$ sets and want to find a set cover with cardinal at most $\mathcal{O}\left(\frac{m \cdot log(n)}{k}\right)$.

For $k=1$, the classical greedy algorithm works, but after that I'm stuck.


texts: Problems that are hard to prove in $\mathcal{P}$

texts:
What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after?

I want to know a list of problems that are difficult to prove in the class of "easy" problems?

Maybe like matching, linear programming. Any list or references would be appreciated.


texts:
What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest path between two elements in the Tamari lattice? Since Wikipedia lists the problem of finding the length of such a path as not known to be in polynomial time, presumably the best known algorithm is $O(c^n)$.

As a rough attempt at an upper bound, the Tamari lattice has $C_n$ nodes (Catalan's number), and by its definition each has degree $n-1$ (for the rotations of each of its internal nodes), while the diameter of the graph is at most $2n-2$, so an algorithm of Johnson 1982 for shortest paths yields an $O(C_nn\log\log n)$, or $4^{n-o(n)}$ upper bound.

(I would also be interested to know about polynomial time algorithms that find approximate solutions, for example with length $\le c\ell$ where $\ell$ is the shortest path.)


texts: Short $\exists$SO sentences over strings that define an NP-complete problem

texts:
[Q1] I'm wondering if there are some "official" SHORT existential second order sentences with ONE binary relation, over strings (over a small alphabet) that define an NP-complete set.

(Something similar to 3-colorability that over graphs can be expressed with a short sentence)

All examples that come to my mind are rather LONG/complex even for simple NP-complete problems; for example we can define the instances of the STRING TO STRING CORRECTION PROBLEM $L$ using alphabet $\{ e, 0, 1, \# \}$

$L \subseteq \{ e^k (0|1)^n \# (0|1)^m \}$

$w \in L$ if the first string $S_1$ (binary sequence before $\#$) matches the second string $S_2$ (binary sequence after $\#$) up to at most $k$ edit/delete operations.

For example: $ee001100\#000000$ (with two edits we can transfor $001100 \to 000000$)

In order to define it we can use a SO sentence that begins with $\exists M$ but we need to use a lot of first order constraints and "details":

$\#$ occurs once
$M$ is a function (represents the copy or delete/insert operations)
$x$ belongs to $S_1$: $S_1(x) \equiv \exists y > x \;.\; U_{\#}(y)$
$x$ belongs to $S_2$: $S_2(x) \equiv \exists y < x \;.\; U_{\#}(y)$
$Diff(x,y)$ iff chars at $x,y$ are different
$M$ maps chars from $S_1$ to chars of $S_2$ or from a $e$ to a char of $S_1,S_2$
order is preserved: if $x_1, x_2 \in S_1 \land  y_1,y_2 \in S_2 \land M(x_1,y_1) \land M(x_2, y_2)$ then $x_1 < x_2 \land y_1 < y_2$
all chars are copied/edited/deleted: $\forall x \in S_i \exists y . M(x,y) \lor M(y,x)$
edited chars handling: if $S_1(x) \land S_2(y) \land M(x,y) \land Diff(x,y)$ then $\exists z . U_{e}(z) \land ( M(z,x) \lor M(z,y)$
deleted chars handling: if $S_i(x) \land \forall  y . \neg ( M(x,y) \lor M(y,x) )$ then $\exists z . U_{e}(z) \land M(z,x)$

  [Q2.1] Can we get an even shorter sentences that define an NP-complete language if we allow ONE (existential) ternary relation or [Q2.2] more (existential) binary relations?.


texts: Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

texts:
In the wikipedia article on Time Complexity it is written that:

  The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, at most, three literals per clause and with n variables, cannot be solved in time $2^{o(n)}$. More precisely, the hypothesis is that there is some absolute constant $c>0$ such that 3SAT cannot be decided in time $2^{cn}$ by any deterministic Turing machine.

We have $2^{o(n)} = \bigcap_{c > 0} O(2^{cn})$.

Proof: For the inclusion $2^{o(n)} \subseteq \bigcap_{c > 0} O(2^{cn})$.
Let $f \in o(n)$, then we know that for each $c > 0$ we can find an $N_c$ such that for $n > N_c$ we have $f(n) < cn$, or $2^{f(n)} < 2^{cn}$ which gives this inclusion. For the inclusion $\bigcap_{c > 0} O(2^{cn}) \subseteq 2^{o(f)}$. Let be some function $g : \mathbb N \to \mathbb N \in \bigcap_{c > 0} O(2^{cn})$, i.e., for each $c > 0$ we have some $N_c$ such that for $n > N_c$ we have $g(n) < 2^{cn}$. Taking logarithms this gives $\log g(n) < cn$. So we have $\log g(n) \in o(n)$.

But ETH is about algorithms, so if we can find for each $c > 0$ some algorithm running in time $O(2^{cn})$, this does not imply that we have a single algorithm running in the intersection of those times, i.e., in $2^{o(n)}$ by the above. So there is still the possiblity that we cannot solve a problem in $2^{o(n)}$, but we can solve it by giving for each $c > 0$ some algorithm $A_c$ that solves it in $O(2^{cn})$. So claiming that something is not solvable in $2^{o(n)}$ is actually a stronger claim than saying we have a $c > 0$ such that the problem cannot be solved in $O(2^{cn})$.

But is there any example of such a problem, i.e. a problem such that for each $c > 0$ we have an algorithm (deterministic TM) running in time $O(2^{cn})$, but we cannot give an algorithm running in time $2^{o(n)}$?


texts:
It is well known that certain classes of NP-problems have dichotomy theorems, which guarantee that every task in the class is either NP-complete or is in P. The best known such result is
Schaefer's dichotomy
theorem, along with a number of generalizations.

My understanding is that proving these dichotomy theorems is not really easy. I wonder, if there is any relatively short explanation for why certain classes have dichotomy theorems, while others do not? What is the essential problem structure that makes these theorems possible? Or perhaps there is no such clearly understood structure, rather it is a mystery in each case why the class does or does not have a dichotomy theorem?