texts: The entropy of a convolution over the hypercube

texts:
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural to define the entropy of such a function as follows:
$$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x)^2 \log \left( f(x)^2 \right) .$$

Now, consider the convolution of $f$ with itself:
$$ [ f*f] (x) = \sum_{y \in \mathbb{Z}_2^n}f(y)f(x+y) .$$
(Note that since we are dealing with $\mathbb{Z}_2^n$, then $x+y=x-y$)

Is it possible to upper bound the entropy of $f*f$ (normalized in its $L_2$-norm, in order for it to be a distribution) by the entropy of $f$? Formally, is there any constant $C$ such that
$$ H \left( \frac{f*f}{\|f*f\|_2} \right) \le C \cdot H(f)$$


texts: How hard is it to find a "well-distributed" subset of models of a propositional formula?

texts:
We consider the propositional language $\mathcal{L}_{\mathit{PS}}$ defined over a finite alphabet $\mathit{PS}$ and the usual logical connectives. An interpretation is an assignment $\mathit{PS} \mapsto \{true, false\}$, and a model of a formula $\phi \in \mathcal{L}_{\mathit{PS}}$ is an interpretation $\omega$ which makes $\phi$ true in the usual way. The set of models of a formula $\phi$ is denoted $Mod(\phi)$. The Hamming distance $d_H(\omega, \omega')$ between two interpretations is the number differences between them, i.e., $d_H(\omega, \omega') = |\{x \in \mathit{PS} \mid \omega(x) \neq \omega'(x)\}|$.

I am interested in the computational complexity of the following decision problem. Given a formula $\phi$, an integer $k$ given in unary and a number $\alpha$, does there exist a set $\mathcal{I} \subseteq Mod(\phi)$ such that $|\mathcal{I}| \leq k$ and such that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d_H(\omega, \omega') \leq \alpha$? Intuitively, this problem asks whether there is a subset (of size at most $k$) of models of a given formula such that every model of the formula is "close" enough (wrt the distance threshold $\alpha$) to some model of the subset.

Actually, I am also wondering about the hardness of the above problem when the set $Mod(\phi)$ is given explicitly in input (at least, this one is in $\mathbf{NP}$, but is it $\mathbf{NP}$-hard?)

Update:

The following is the answer for the case where the set $Mod(\phi)$ is explicitely given in input.
The problem is $\mathsf{NP}$-hard by reduction from the vertex cover problem on cubic graph, which is known to be $\mathsf{NP}$-hard.
Let $G = (V, A)$ be a cubic graph with $V = \{v_1, \dots, v_n\}$ and $A = \{a_1, \dots, a_m\}$ and $k$ be a positive integer.
We associate with every edge $a_j \in A$ a propositional variable $f(a_j) = x_j$ and denote $\{x_1, \dots, x_m\} = \mathit{PS}$.
We associate with every vertex $v_i \in V$ an interpretation $g(v_i) = \omega_i$ defined for every $j \in \{1, \dots, m\}$ as $\omega_i(x_j) = 1$ if the edge $a_j \in A$ is incident to the vertex $v_i$, $0$ otherwise. Denote $\{\omega_1, \dots, \omega_n\} = \mathcal{S}$ ($\mathcal{S}$ stands for the set of models $Mod(\phi)$ of some formula $\phi$, but which is here defined explicitely). One can see that for every $\omega_i, \omega_j \in \mathcal{S}$, $d_H(\omega_i, \omega_j) = 4$ if $v_i$ and $v_j$ are adjacent in $G$, otherwise $d_H(\omega_i, \omega_j) = 6$. Therefore, $G$ admits a vertex cover $V'$ such that $|V'| \leq k$ if and only if the set $\mathcal{I} = \{g(v_i) \mid v_i \in V'\}$ satisfies $\forall \omega_j \in \mathcal{S}$, $\exists \omega_i \in \mathcal{I}$, $d_H(\omega_i, \omega_j) \leq 4$.

For the succinct case (i.e., where considering a formula $\phi$ instead of a list of interpretations), then the problem is still open. From the answers of Marzio De Biasi and D.W., it is $\mathsf{coNP}$-hard. Moreover, it is in $\mathsf{NP}^\mathsf{NP} = \Sigma_2^{\rm P}$. Indeed, one can use the following non-deterministic algorithm with $\mathsf{NP}$ oracle: (i) guess a set $\mathcal{I}$ of interpretations such that $|\mathcal{I}| \leq k$; (ii) check in polynomial time that $\forall \omega \in \mathcal{I}$, $\omega \in Mod(\phi)$, and check using one call to the $\mathsf{NP}$-oracle that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d_H(\omega, \omega') \leq \alpha$.

I still need to characterize the exact complexity of the problem. Intuitively, it seems that the problem is $\Sigma_2^{\rm P}$-hard (thus, it would be $\Sigma_2^{\rm P}$-complete in this case). Does anybody know an extension of the vertex cover problem to some $\Sigma_2^{\rm P}$-hard problem? Otherwise, a reduction from the validity problem of a QBF of the form $\exists X \forall Y \psi$ to our problem seems cumbersome.


texts: Correspondence between complexity classes and logic

texts:
I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, first order logic, ...).

The correlation included several results in one fields, that were obtained using techniques from the other field. It was conjectured that P != NP could be attacked as a problem in Logic (by projecting the problem from the domain of complexity classes to logics).

Is there a good summary of these techniques and results?


texts: When we use a proof of unsatisfiability to derive an interpolant, isn't using the interpolant to check satisfiability now redundant?

texts:
A few papers I've been reading have algorithms on using interpolants for the following clauses (bounded model checking):

$$ \begin{align*}
A &= I \wedge T_1 \\
B &= T_2 \wedge T_3 \wedge \ldots \wedge T_k \wedge (F_1 \vee F_2 \vee \ldots \vee F_k) \\
\end{align*} $$

This interpolant is then used to compute an over approximation of reachable states and then we can check for inconsistency with less computation.

BUT, the interpolant itself is derived from a proof of unsatisfiability. So before you get the interpolant, wouldn't you already know if the final states are reachable?


texts: Kleinberg-consistency of spectral clustering

texts:
Spectral clustering refers to a family of graph-based algorithms, which usually rely on a similarity function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity function, say $e^{-\rho(x,y)}$.

What I called Kleinberg-consistency is commonly referred to in the clustering literature as "Kleinberg's consistency axiom". A clustering algorithm takes a finite point set $S$ together with a metric $\rho$ as input, and returns a clustering $\mathcal{C}$ of $S$, which is just a nontrivial partition of $S$.

The clustering algorithm $A$ is consistent if it satisfies the following property: Run $A$ on point set $S$ with metric $\rho$, to obtain some clustering $\mathcal{C}$. Now take any $\rho'$ such that all $x,y\in S$ that fell into the same cluster $C\in\mathcal{C}$ satisfy $\rho'(x,y)\le\rho(x,y)$ while for all $x,y$ that fell into distinct clusters, we have $\rho'(x,y)\ge\rho(x,y)$. Consistency requires that if we run $A$ on $(S,\rho')$, we obtain the same clustering $\mathcal{C}$ as we did for $\rho$.

Question: Is there any specific natural spectral clustering algorithm that is known (not) to be Kleinberg-consistent?

NB: The question is explicitly not about the statistical consistency of spectral clustering, which has been addressed in the literature.


texts: What is the difference between arrows and exponential objects in a cartesian closed category?

texts: In a Cartesian Closed Category (CCC), there exist the so-called exponential objects, written $B^A$.  When a CCC is considered as a model of the simply-typed $\lambda$-calculus, an exponential object like $B^A$ characterizes the function space from type $A$ to type $B$.  An exponential object is introduced by an arrow called $curry : (A \times B \rightarrow C) \rightarrow (A \rightarrow C^B)$ and eliminated by an arrow called $apply : C^B \times B \rightarrow C$ (which unfortunately called $eval$ in most texts on category theory).  My questions here is: is there any difference between the exponential object $C^B$, and the arrow $B \rightarrow C$?


texts: Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

texts:
optimization problem

Input: cubic Hamiltonian graph

feasible solution: A simple path

measure to optimize: length of the simple path

Design a polynomial-time algorithm that outputs the longest path it can find.

To my knowledge, longest path problem does not have polynomial-time constant-factor approximation in cubic Hamiltonian graphs unless P=NP. This problem is interesting since the input is cubic graph and has a n-length Hamiltonian cycle.

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs, Journal of Algorithms 31, 249-268, 1999.


texts: Example of a function that you can write in Calculus of Constructions but not in System-F

texts: It's been suggested in an answer to this question that the Calculus of Constructions has more computational strength than System-F. What are examples of functions that you express in CoC that you cannot write in System-F?


texts:
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.
Equivalently, $P$ is integral if for any $c \in \mathbb{R}^n$, the program $\max\{cx : x \in P\}$ has an integer optimizer.
Now according to the theorems, to show that $P$ is integral, it merely suffices to show that for any $c \in \mathbb{Z}^n$, the program $\max\{cx : x \in P\}$ has an integer optimal value (whenever the optimum is finite).
Why should having an integer optimal value imply that there is an integer optimal solution? The proofs that I read for this use duality and give me no intuition.
Is there a better explanation of why this is true, or some kind of intuition?


texts: Approximation algorithms based on relaxing a feasible to infeasible solution?

texts:
A lot of approximation algorithms are based on relaxation. The way it usually works is this. You take the original problem and relax it some large class of efficiently solvable problem (e.g. relax an IP to an LP). Any solution to the original problem of cost $X$ gives a corresponding solution to the relaxation of cost $X$.

You then convert a solution to the relaxed problem of cost $Y$ to a solution to the original problem of cost $\alpha Y$ for some $\alpha > 1$. This implies that you have an $\alpha$ approximation.

But what if you could argue that the original feasible solution of cost $X$ guarantees the existence of a solution to the relaxation of cost $X/\beta$? Then you would get an $\alpha/\beta$ approximation algorithm.

Has this strategy ever been employed? Is there ever a case when you can show that a feasible solution to the original problem corresponds to a feasible solution to the relaxation of strictly lower cost ?


texts: Question about discarding the second register in the standard approach of hidden subgroup algorithm

texts:
My questions:

What does discarding the second register mean for the standard approach of hidden subgroup algorithm?
Why does discarding  let the first register end up in a mixed state?

My understanding so far:

I am trying to understand the effect of discarding the second register in the standard approach of hidden subgroup algorithm using this paper as resource. I will be using $S_5$ as my group of interest.

It is said in the paper that,

I assume $f$ maps $g$ to it's irrep. So, if we take the case of $S_5$, assuming an automorphism group of a $5$-node graph is hidden inside $S_5$, $|G| = |S_5| = 120$. Both $|g\rangle$ and $|f(g)\rangle$ are $120$ element column vectors.

So, when it is said that the second register is discarded what it actually means? Let's take the case of trapped ion qubits. When we say we discard the second register, does it mean that we will not do any unitary transformation or measurement on them anymore but they will always be there? In the Wikipedia page of Simon's problem the second register is measured.

I also don't understand why discarding (whatever it means) will let the first register end up in a mixed state. Shouldn't it be in a pure quantum state?


texts:
I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness assumptions, and I've heard of methods based on the hardness of factorization, discrete logarithm, NP-complete problems (such as the Knapsack problem) and problems on lattices.

Is there any good text addressing the different existing paradigms?

In particular, I would be interested on open problems and questions on less studied methods.

Answers for this question may include both references to a text giving an overview of the area but also to specific methods.


texts: Computing volume of high-dimensional convex polyhedra

texts:
I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-dimensional space with parameters bounded roughly as follows: $d \le 50$  and $n \le 1000$. Note, that there is no guarantee on the number of faces.

Jeff Erickson's page has a link to a program Vinci-1.0.5, which has a hard limit of 255 faces. This is a limitation of the implementation, the algorithm itself can probably handle more faces in reasonable time.

I couldn't find any implementations of the Markov chains based method for estimation, although I guess they will be even less efficient.

Is there any software, that can handle the range of parameters described above or some moderate relaxation of it? I would be very grateful for any other references as well.


texts: Minimum weight subforest of given cardinality

texts:
This question was motivated by a question asked on stackoverflow.

Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$).

Each vertex $i$ has a non-negative integer weight associated: $w_i$.

Additionally, you are given an integer $k$, such that $1 \le k \le n$.

The weight $W(S)$ of a set of nodes $S \subseteq \{1,2,\dots, n\}$ is the sum of weights of the nodes: $\sum_{s \in S} w_s$.

  Given input $T$, $w_i$ and $k$,

  The task is to find a minimum weight
  sub-forest* $S$, of $T$, such that $S$
  has exactly $k$ nodes (i.e. $|S| =
> k$).

  In other words, for any subforest $S'$ of $T$, such that $|S'| = k$, we must have $W(S) \leq W(S')$.

If the number of children of each node were bounded (for instance binary trees), then there is a polynomial time algorithm using dynamic programming.

I have a feeling that this is NP-Hard for general trees, but I haven't been able to find any references/proof. I even looked here, but could not find something which might help. I have feeling that this will remain NP-Hard even if you restrict $w_i \in \{0,1\}$ (and this might be easier to prove).

This seems like it should be a well studied problem.

  Does anyone know if this is an NP-Hard problem/there is a known P time algorithm?

*A sub-forest of $T$ is a subset $S$ of nodes of the tree $T$, such that if $x \in S$, then all the children of $x$ are in $S$ too. (i.e. it is a disjoint union of rooted sub-trees of $T$).

PS: Please pardon me if it turns out that I missed something obvious and the question is really off-topic.


texts: How to determine whether there is exactly one simple path between two nodes in a graph

texts:
Given an undirected sparse graph G and a list of queries (each query consisting of two nodes), how to determine if there exists exactly one simple path between them (for each query) ? I have a (trivial) solution based on a breadth-first search (for each query the complexity would be O(V+E)) but is there a more efficient way to answer the queries?

You don't have to find the actual simple path, just answer each query with a True/False answer.

This question was asked as part of the Latin American regional competition of the 2011 ACM International Collegiate Programming Contest.


texts: What is the best-known inapproximability result for MIN-3CNF-DELETION?

texts:
I am really curious what the best-known inapproximability result is for MIN-3CNF-DELETION. To clarify, this is the problem of minimizing the number of unsatisfied clauses in a CNF
SAT formula with at most 3 literals per clause. The objective function is the number of unsatisfied clauses. The strongest hardness result I have been able to find is that of MIN-HORN-DELETION, which is a restricted variant of MIN-3CNF-DELETION. As far as I know the best-known inapproximability result for MIN-HORN-DELETION is that which is given in The Approximability of Constraint Satisfaction Problems by Khanna et al (2000).

However, I have not yet been able to find explicit references to MIN-3CNF-DELETION. Is it even harder than MIN-HORN-DELETION? In which case, what is the best known inapproximability threshhold? Any feedback would be most welcome. Thanks!


texts: Quantified Boolean Formulas with logarithmic alternations

texts:
I'm studying a problem which is hard for the class of quantified boolean formulas with a logarithmic number of alternations of the quantifiers. A problem in this class would look like:

$\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F$

Where $a_{\log n} = n$, and $F$ is a boolean formula of the variables $x_1 \ldots x_n$.

This class clearly contains $PH$ and is contained in $AP = PSPACE$. Is there a name for this class? Is there anything more known about it?


texts: Does there exist a sentence of first-order logic that is satisfiable only in infinite models that do not have a finite algorithmic representation?

texts:
There exist sentences of first-order logic that are satisfiable and are satisfiable only by models of infinite size. However, all such sentences I can think of are satisfied by infinite models that can be generated by a non-terminating algorithm of a finite size.

For a example, there exists a sentence of first-order logic that is satisfied only by a model of an infinite size:

$$ \exists x \lnot \exists y S ( y, x ) \land $$
$$ \forall x \exists y S ( x, y ) \land $$
$$ \forall x \forall y \forall z ( ( S ( x, z ) \land S ( y, z) ) \to x = y ) $$

A model for this sentence can be generated (listed, enumerated) by a finite algorithm that never terminates - just list the elements of the infinite model in a sequence one after another and make $S$ hold only for successive pairs of such elements.

Does there exist a sentence of first-order logic that is satisfiable only in some infinite models for which there does not exist a finite algorithm that generates them?


texts: A fixed-depth characterization of $TC^0$? $NC^1$?

texts:
This is a question about circuit complexity. (Definitions are at the bottom.)

Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{poly(\log s)}$ of depth two, where the output gate is a symmetric function and the second level consists of $AND$ gates of $poly(\log s)$ fan-in. This is a fairly remarkable "depth collapse" of a circuit family: from a depth 100 circuit you can reduce the depth to 2, with only a quasi-polynomial blowup (and one fancy but still restricted gate at the top).

My question: is there any known way to express a $TC^0$ circuit family, similarly? More ambitiously, what about an $NC^1$ circuit family? Potential answers would have the form: "Every $TC^0$ circuit of size $s$ can be recognized by a depth-two family of size $f(s)$, where the output gate is a function of type $X$ and the second level of gates have type $Y$".

It doesn't have to be depth-two, any sort of fixed-depth result would be interesting. Proving that every $TC^0$ circuit can be represented in depth 3 by a circuit consisting of only symmetric function gates would be very interesting.

Some minor observations:

If $f(n)=2^n$ the answer is trivial for any Boolean function (we can express any function as an $OR$ of $2^n$ $AND$s). For concreteness, let's require $f(n) = 2^{n^{o(1)}}$.
The answer is also trivial if either $X$ or $Y$ is allowed to be an arbitrary function computable in $TC^0$... :)
I'm obviously interested in "simpler" functions, whatever this means. It's a bit slippery to define because there are symmetric function families which are uncomputable. (There are unary languages which are uncomputable.) If you like, you may simply replace $X$ and $Y$ with symmetric functions in the statement, however I'd be interested in any other neat choices of gates.

(Now for some brief recollections of notation:

$ACC^0$ is the class recognized by a family of unbounded fan-in constant-depth circuits with $AND$, $OR$, and $MOD_m$ gates for a constant $m > 1$ independent of the circuit size. A $MOD_m$ gate returns $1$ iff the sum of its inputs is divisible by $m$.

$TC^0$ is the class recognized by constant-depth circuits with $MAJORITY$ gates of unbounded fan-in.

$NC^1$ is the class recognized by logarithmic-depth circuits with $AND$, $OR$, $NOT$ gates of bounded fan-in.

It is known that $ACC^0 \subseteq TC^0 \subseteq NC^1$ when the circuit size is restricted to be polynomial in the number of inputs.)


texts: Quantum analogues of SPACE complexity classes

texts:
We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in complexity theory there was much success with these classes such as the space-hierarchy theorem and the creating on important classes like $\textbf{L}$ and $\textbf{PSPACE}$. Is there analogous definitions for quantum computation? Or is there some obvious reason why the quantum analogous would not be interesting?

It seems like it would be important to have a class like $\textbf{QL}$ --- a quantum version of $\textbf{L}$: require a logarithmic number of qubits (or maybe a quantum TM uses logarithmic space).


texts: Does p-isomorphism preserve phase transition?

texts:
Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other must also have phase transition, with respect to some (possibly different) order parameter?

Intuitively, I would expect that the answer is yes. The reason is that p-isomorphmism means that the two languages are "essentially the same," apart from a polynomial-time re-encoding. It would appear quite surprising if one of them has phase transition, while the other does not, despite their p-isomorphism. But how can the implication be proved formally?


texts: Size of complement of context-free language

texts:
Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$.

  What is known about $|\bar L_n|$?

Note that it is known that $|L_n|$ is either polynomial (if $L$ is bounded$~$), or grows exponentially.
I wonder if anything similar might be true about $|\bar L_n|$.
Warning, $L$ is allowed to be ambiguous!


texts: Universities for Quantum Computing / Information?

texts:
Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research?

The aim here is to collect a useful list for someone considering graduate study in these fields, not to discuss which is "best".  To make this list useful, please include a brief description of the part of the university where this area is pursued (in many places this is in an interdisciplinary institute that may not be familiar to everyone), and a URL.


texts: Internal as well as external partition of (regular) graphs

texts:
Let $G$ be a simple finite undirected graph. Let $\{V_1,V_2\}$ be a partition of its vertex set; that is, $V_1\cup V_2=V(G)$ and $V_1\cap V_2=\emptyset$. The partition $\{V_1,V_2\}$ is said to be an internal partition if every vertex has at least as many neighbours in its own part than in the other part. The partition $\{V_1,V_2\}$ is said to be an external partition if every vertex has at most as many neighbours in its own part than in the other part.
It is known that $G$ always has an external partition. The situation is more diverse for internal partitions (eg: see [1]). There are many unresolved problems and conjectures on internal partitions even when the input graph is even regular.
Is partitions that are both internal and external studied in the literature?
(that is, a partition $\{V_1,V_2\}$ such that every vertex has the same number of neighbors in its own part as in the other part).
If it matters, I am more interested in even regular graph (esp. 4-regular graphs) and in partition into equal-sized parts (i.e. $|V_1|=|V_2|$).
[1] Ban, Amir; Linial, Nati, Internal partitions of regular graphs, J. Graph Theory 83, No. 1, 5-18 (2016). ZBL1346.05223.


texts:
Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is Gallai-colored if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c_1,\ldots,c_k)$. We may then define the polytope $\mathcal{P}(G) \subseteq \mathbf{R}^V$ by:

  $0 \leq f(x)$ for every $x \in V$,

  $\sum_{x \in S} f(x) \leq c_i$ for every monochromatic set $S$ with color $i$.

We say that $G$ is perfectly Gallai-colored if the polytope $\mathcal{P}(G)$ is integral for every tuple $c$ with integral values. In particular, for two colors it includes graphs for which the clique-packing / independent-packing problems are LP-solvable. Among those are the comparability and co-comparability graphs, as this should follow by the Greene-Kleitman theorem if I'm correct.

I have two questions in this respect:

(1) Are there existing references to this class in the literature?

(2) Is this class closed under the operation of substitution? If true this would imply that a completely decomposable colored graph is perfectly-Gallai colored. This would generalize the fact that a cograph is both comparability and co-comparability.


texts: What should I do to switch from math department to cs to research tcs topics?

texts:
This can be a very weird question, but I haven't seen the same situation with mine in this forum, so I'd like to put this. Let me introudce my situation first.

I'm now a math student of master program in a university in Korea, and I was majored in economics and math as an undergrduate. As a freshman, though my first major was economics, I took a class of mathematical logic, and it was great to me. From that time, I decided to have double major in math and economics. And taking math courses like linear Algebra, Algebra, Analysis, Complex Analysis, Logic, Set theory, Statistics, Homological Algebra, Topology and so on.

But as time went on, I felt that the motivation of standard math courses are somewhat different from mine. Yes, mathematics has a culture of broad range, but, even if the core courses are very useful and beautiful, I think it has a slightly different motivation from mathematical logic. "What can be a good course to take if I liked logic class?" I asked to myself, and I decided to take "Formal languages and automata theory" in cs. It was fantastic. And at that time, I learnt there existes the area of theory of computation or theoretical computer science. But in Korea, culture of cs is more oriented in the way of engineering area, so I felt that it would be more helpful to train myself in math dep. than cs, so I chose to go to master program of math.

But now, in my university, there are more strong culture of concetrating on "classical" mathematical things, not computation or even combinatorics or logic. So, I realized that if I pursue this way, then I'll be just a "pure" mathematician. Considering interconnectedness of academia, it can be also a good way, but I don't like to do that. So I'd like to change a university to pursue tcs research.

However, I've just taken two courses in cs - Formal languages and automata theory, and c programming. And I have no research experiences in cs. I'd like to self study my own to have sufficient information of tcs area for a while, but it's just an individual thing. And I'm so confused because I don't know what courses to take from now on, and what resonable amount of knowldeges are needed to start reasearch in tcs(especially the knowledge in cs). Briefly, what should I do to switch from math department to cs to research tcs topics?

Recently, I have some interest in computational complexity theory and start to study "gems of theoretical computer science" and it's very interesting. But that's only plan that I have. I wish my plan would be more concrete. Any help? Please?


texts: algorithms for a large submatrix / general factor / quasi-biclique problem?

texts:
Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that all rows sum to $\ge p$, all columns sum to $\ge q$, and the number of columns is $\le k$.   Equivalently, given a bipartite graph $G = \langle U, W, E \rangle$, find a subgraph $G’ = \langle U’, W’, E’ \rangle$ where the minimum degree is $p$ for all $u \in U’$ and $q$ for all $w \in W’$, where $|W’| \leq k$, and where $|U’|$ is as large as possible, if any such subgraph exists.

Here's what I know so far:

A naïve algorithm that alternately deletes invalid rows and columns finds a solution in time $O(mn(m+n))$, if the row maximizing solution fortuitously has number of columns $\le k$. (A tighter bound accounting for sparsity could be given.) Its I/O behavior is not good though.
With constraining $k$, the problem is an instance of (an optimization version of) Lov\'{a}sz's GENERAL FACTOR PROBLEM.  GFP asks whether a graph has a subgraph such that each vertex has a degree that falls in a specified set. I can cast my problem as GFP by defining a bipartite graph $\langle \{U \cup y \}, \{W \cup x \}, E^{+} \rangle$ by adding a vertex $x$ with an edge to all vertices in $U$, and vertex $y$ with an edge to all vertices in $W$.  We require all vertices in $U$ to have degree in the set $\{0,p,p+1,…, n\}$, all vertices in $W$ to have degree in the set $\{0, q,q+1,…, m\}$, and vertex $y$ to have degree in the set $\{1,…, k\}$. We define vertex $x$ to have degree $j$, and do binary search on $j$ with a solver (that finds a solution, not just yes/no) for GENERAL FACTOR PROBLEM as a subroutine.  Unfortunately, GFP is NP-complete when there are gaps greater than 1 in the degree set (as the 0's for dropping nodes introduce). And while there's a lot of theoretical work on GFP, I haven't found any heuristic algorithms appropriate for large data sets.
There are several definitions of a quasi-biclique and heuristic algorithms for finding them in large graphs (e.g. social network or genomics data).  Unfortunately, the ones I have found either constrain degree on nodes in only one side of the bipartite graph, or use symmetric criteria that effectively allow only certain combinations of $p$ and $q$ to be used.  Abello, Resende, and Sudarsky give a semi-external algorithm for large graphs, but use a definition of quasi-biclique based on edge density that doesn't match my needs at all.

Any pointers to semi-external or external memory algorithms for my problem, or suggestions of other ways to think about it?


texts: One-sided errors in probablistic proof systems

texts:
In most probabilistic proof systems ( PCP theorem, for instance), the error-probabilities are usually defined on the side of the false-positives, i.e., a typical definition could look like :  if $x \in L$ then the verifier always accepts, but in other case the probability of rejection is at least 1/2.

Is there a problem in allowing the error to happen on the other side ? That means the verifier always rejects when it should, and makes no more than a constant error when it needs to accept. Another obvious possibility is allowing the error on both sides.
Will these definitions be equivalent to the one usually given? Or, they behave differently ? Or for that matter, is there a genuine problem in allowing the errors on the other side.?


texts: Streaming Algorithm Lower Bounds by Communication Complexity

texts:
I am learning the methods for proving lower bounds on streaming algorithms using communication complexity.

My question is about a basic technique to prove lower bounds on streaming models using the reduction by giving each player in the communication game a fragment of the tape of Turing Machine whose sequential scan is bounded.The number of sequential scans is the number of passes.

We consider streaming algorithm as a one tape TM.

Is there some inherent limitations of this reduction using fragments of the tape?

It seems that increasing of the number of passes deteriorates the efficiency of reductions and that we would not use this fragment methods to prove lower bounds on streaming models with many passes.

Are there other powerful methods which overcome the weakness of the fragment methods?


texts: Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?

texts:
Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition.

http://www.sciencedirect.com/science/article/pii/030439759190180A

Scott's algorithm on building parse trees doesn't take into account this enhancement.

http://www.sciencedirect.com/science/article/pii/S1571066108001497

Leo notes in his paper his algorithm builds an effective recognizer, but ultimately leaves out information that would be needed to construct the parse forest. Building the parse forest would require the transition items omitted by the enhancement and therefore undo the complexity gains.

So I would like to know if there is research or findings on creating a parse forest that retains the complexity gains from the Leo enhancement without pushing the complexity from the recognizer to the parse forest generation. Basically, is there a linear time algorithm on LR(k) grammars for building sparsely packed parse forests?


texts: Are there any logics to formalize understanding?

texts:
Are there any logics (modal-based or others) to formalize the following statement:

"agent A understands p". For example "agent A understands that Titanic sank
because it hit an iceberg"

Where "understands" could be considered as a modal operator like the epistemic modal operator "agent A knows p".

Thank you,


texts: Algorithm for converting very large NFA to DFA

texts:
I have really large Non-deterministic finite automaton and I need to convert it to the DFA.

By large I mean 40 000+ states.
So far I have done some experiments and programmed the default algorithm that searches through table (as described here), but even after optimization is quite slow and very memory consuming. I am aware of the fact, that the number of states can grow exponentially, but after minimization, the resulting DFA has about 9 000 states and that is bearable.

So my question is, is there some algorithm, that would be faster or more memory friendly?


texts:
TLDR;
What is the mathematics foundation for the namespace problem? Can I reduce namespace problem to set theory or other math concepts/objects (lambda calculus, category theory)?

I'm doing an essay on concepts like namespaces, packages and modules in programming languages. Among other topics, I'm studing how to avoid names collitions and in particular how programming languages solve the problem. For example:

Given any programming language, suppose that we have following user defined functions (or other language specific "object") named $a$ and $b$:

function a () {
  // do something
}

function b () {
  // do something
}

And a function called $c$ that uses above functions:

function c () {
  a();
  b();
}

If in the "context" above we defined another function called $a$, we would have a collision in function $c$ because it doesn't know what $a$-function implementation must use.

So to avoid name collisions a programming languages can implement namespace/package/module systems and let the programmer doing something like the following:

module alpha{
  function a () {
    // do something
  }
  function b () {
    // do something
  }
}

module beta{
  function a () {
    // do something
  }
}

And then doing:

function c () {
  alpha.a();
  alpha.b();
}

or

function c () {
  beta.a();
  alpha.b();
}

Thanks.


texts: Reference request: transforming a grammar to Greibach normal form preserves the number of parse trees

texts:
I believe that most "natural" ways of transforming a grammar to the GNF should preserve the number
of parse trees for each string. For example, Urbanek's construction from the paper
"On Greibach normal form construction" seems to do the job.

What I need is the statement that for every context-free grammar there exists a grammar
in GNF that every word has the same number of parse trees for both grammars (therefore
this grammars define the same language; but it should be noted that the equality of
the number of the parse trees is stronger condition).

Unfortunately, proving this rigorously looks really tedious and probably won't
add any conceptual value to the paper I currently participate
in writing. Moreover, this result can't possibly be original and therefore
it is much better to cite it rather than to reprove it again. However, all my
attempts to find a paper where this result is stated directly were futile.

Some requirements (all not strict, though):

For simplicity of quoting, I would prefer a paper where this result is stated
as a theorem, lemma, corollary or something "noticeable" like this, preferably
not as a remark in the middle of the proof (though the latter also would be okay
for the lack of the former).
Situations, where this result is not stated at all and just immediately
follows from some deeper theory (but the fact that it follows is not established in the paper)
are less preferable, of course, but still fine, as long as the main results of the theory are
easy to state.
In the same vein, if the result is proved for weighted grammars
(with the number of parse trees being replaced with weigt of the word),
it is completely fine.

While not probable, it still may happen that this result is incorrect. In this case, link to the disproof or a disproof as the answer would be nice.

UPD It seems that lemma 4 in this paper does the job. However, if
someone finds a link that does not mention multigrammar, I would still appreciate that.


texts: Complexity of QBF with Restrictions on Models

texts:
Do you know the complexity of the following decision problem?

Given a quantified boolean formula (QBF) $\phi$ with $2n$ free variables with $n\in\mathbb{N}$. Is there a satisfying assignment s.t. exactly $n$ free variables are true and $n$ free variables are false.

I am also interested in the easier case, where we consider propositional logic instead of QBF. What would the complexity be then?


texts: Distributing a binary relation into bins such that each element is in a small number of bins

texts:
We are given pairs of objects (say, numbers). Each object appears in at most $q$ pairs. Our goal is to distribute the pairs into equal-size  bins, such that each object occurs in as few as possible different bins.

More precisely, we are interested in a function $f$ with the property that for every binary relation with $m$ pairs with at most $q$ pairs per object, there is a distribution of the pairs to $p$ bins, such that each bin receives $m/p$ pairs ($p$ should divide $m$), and no object occurs in more than $f(m,q,p)$ bins.

This question came up in our research on parallel query evaluation. One would expect that $m$ is large compared to $p$. The "right" size of $q$ is less clear. An interesting size for $q$ could be, e.g., $\sqrt{\frac{m}{p}}$. A function that does not depend on $q$, but only works for a certain range of $q$ would also be useful (but not $q=O(1)$).

Actually, we are after bounds of the form $p^{1-\epsilon}$, with $\epsilon>0$ as large as possible...


texts:
Say we want to understand a game tree search algorithm in a theoretical context.  Thus, we want a parameterized family of problem instances, separate from actual games such as a chess, so that algorithms can be theoretically tested on small instances and then scaled up.

The simplest example would be a random tree (or random DAG) with random values at leaves chosen i.i.d. from some distribution.  Unfortunately, this model seems too simple to capture many interesting properties of game trees.  In particular, in a domain such as chess or go the values at leaves are both (1) highly correlated to nearby leaves and (2) highly correlated to simpler heuristics available at interior nodes.

A model that includes these correlations/heuristics would, for example, allow one to monitor the increasing strength of an agent as the depth of tree search increases.

Question: Are there papers which construct this kind of theoretical model of game trees with correlations between leaf values, or between leaf and heuristics at interior nodes?


texts: What's the difference between "adaptive sorting" and "sorting almost sorted data quickly"?

texts:
A SIGMOD 2014 paper from Microsoft Research states that the "importance of sorting almost sorted data quickly has just emerged over the last decade", and goes on to propose variants of Patience sort and Linear Merge, and measure their performance on synthetic "close to sorted" data.

It seems to me that this description matches the theme of "Adaptive Sorting", covering algorithms taking advantage of existing preorder in sequences to be sorted, which has been the topic of various publications (albeit in the community of theoretical computer science rather than databases) from as early as 1979:

 - 1979-CTCS Sorting Presorted Files - Mehlhorn
 - 1980-CACM Best Sorting Algorithm For Nearly Sorted Lists - Cook, Kim
 - 1985-TCom Measures Of Presortedness And Optimal Sorting Algorithms - Mannila
 - 1992-ACMCS ASurvey Of Adaptive Sorting Algorithms - Estivill-Castro, Wood
 - 1994-IC Sorting Shuffled Monotone Sequences- Levcopoulos, Petersson
 - 1995-DAM A Framework For Adaptive Sorting - Petersson, Moffat

Am I missing a key difference between those approaches or is it a mere occurrence of weak communication between the database and TCS communities?


texts: What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

texts:
A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based on the undecidability of the halting problem - see for example https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof

Who first proposed this proof and in what article or book has it been first published?


texts: If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$?  I am aware of results for subtree isomorphism where both $G$ and $H$ are trees and also where $G$ is planar or has bounded treewidth (and others) but not for this graph and tree case.


texts: Problems in dynamic algorithms in computational geometry

texts:
The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as:

Dynamic Range Searching
Dynamic Point Enclosure
Dynamic Set Intersection

And others.

What are some open problems in dynamic computational geometry currently that have good static algorithms but worse dynamic algorithms? I am especially interested in algorithms that use priority queues in the static solution.


texts: Impact of proof of NP=co-NP on RP vs co-RP Question?

texts:
It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world:

If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions?
If NP=PSPACE, does RP=co-RP=ZPP follow automatically or does it require additional conditions?

In both cases what additional constraints are required to prove RP=co-RP=ZPP if the conditions above are not sufficient?


texts: What is the error bound in the classical error threshold theorem?

texts:
For unreliable classical computation there is an error threshold theorem due to von Neumann analogous to the quantum error threshold theorem that shows that even if gates produce the wrong result at some rate, as long as this rate is below a certain threshold the total error probability can be reduced arbitrarily by adding some polynomial overhead.
For the quantum threshold there is a lot of active research trying to pin down bounds, but are there any corresponding results for classical computation error thresholds?
The best bound I know of on the polynomial overhead is from (Spielman 1996): a computation taking time $T$ on $N$ error-prone processors can be run using $N \log^{O(1)}(N)$ processors in time $T \log^{O(1)}(N)$ with failure probability at most $t \exp(-N^{1/4})$. But are there known values of the O(1) constants? And there is no explicit estimate of the threshold error rate.


texts: Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us?  [If not, can we make one? I know this is off topic, but it would be SO useful]


texts: Generating a random graph with constraints on spectrum

texts:
Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple graphs on $n$ vertices that have their spectrum lower-bounded by $l_{1:n}$ and upper-bounded by $u_{1:n}$. In other words, let $G$ be a graph on $n$ vertices, and $\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n$  the eigenvalues of $G$'s adjacency matrix; if $l_i \leq \lambda_i \leq u_i$ for all $i$ then $G \in \mathcal{G}(l_{1:n},u_{1:n})$.
Is there an efficient procedure to sample a graph uniformly at random from $\mathcal{G}(l_{1:n},u_{1:n})$? If not, what restrictions do we need to place on $l_{1:n}$, $u_{1:n}$, or elsewhere to have such a procedure? What if we just need the distribution over $\mathcal{G}(l_{1:n},u_{1:n})$ to be approximately uniform?
In the application I am considering, I really only care about the first few eigenvalues (biggest 2 or 3). If we constain only $l_i \leq \lambda_i \leq u_i$ for all $i \in \{1,2\}$ or $i \in \{1,2,3\}$ (instead of all $i$ as before) then is there a good sampling algorithm?
If no good sampling algorithm is known even in the restricted case then what do people usually do in practice?

Related question

Reverse Graph Spectra Problem?


texts: If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?

texts:
The homeomorphic embedding relation for trees as I understand it is a well-quasi-order (wqo) on trees when the label of a node determines the number of children of that node, and there are a finite number of such labels. A description of what (I hope) I'm referring to is in section 5.1 of this article.

I want to naively generalize this wqo to trees wherein the labels do not determine the number of children, for the purpose of runtime termination checking with states being said ill-behaved trees.

Assuming that I'm testing the homeomorphic embedding relation $\leq$ according to the rules (if something looks wrong here, then trust the linked the paper and correct me instead):

$l \leq r = \begin{array}\\
c(s_1 \ldots s_n) \leq c(t_1 \ldots t_n) & \text{if} & l = c(s_1 \ldots s_n) \text{ and } r = c(t_1 \ldots t_n) \text{ and } s_1 \leq t_1 \ldots s_1 \leq t_n \\
s \leq c(t_1 \ldots t_n) & \text{if} & l = x(s_1 \ldots s_n) \text{ and } r = c(t_1 \ldots t_n) \text{ and } \exists i.s\leq t_i \\
false && \text{otherwise}
\end{array}$

where $c$ is a label, $x$ is some other label, and $s_i$ and $t_i$ are subtrees (and the $c(\ldots)$ notation is a tree construction with $c$ as the root of a (sub)tree and $\ldots$ that (sub)tree's children).

Would I still have a wqo if I simply said the relation holds if I ever encounter (in the course of checking membership in the relation) a scenario where I'm checking $c(\ldots s_m) \leq c(\ldots t_n)$ and $m \neq n$?

My gut says that I still would have a wqo (the 'dives in' rule should force me to make the arity check and blow the whistle whenever the vanilla homeomorphic embedding would be too lenient on labels-with-inconsistent-children-counts, and catch the case of an infinite sequence of widening trees), but as with any procedural hack on a mathematical relation I feel a bit too dumb to be sure.


texts: Set of functions computable in polynomial time

texts:
I write paper and I want to distinguish between the class of decision problems which can be decided in polynomial time and the class functions which can be computed in polynomial time.
The first is just written as $\mathrm{P}$ or $\mathrm{PTIME}$, right? Can the latter be denoted as $m^{\mathcal{O}(1)}$ or is this a confusing definition?


texts: A first order logic extended with binding terms like the familiar set descriptors $\{x:\varphi\}$

texts:
First order logic comes equipped with two kinds of terms:

Variable: those terms of the form $x$ for some variable $x$, of which there are infinite.
Function application: those terms of the form $f(t_1,\dots,t_n)$ for some $n$-place function symbol $f$, of which there are infinite, and some $n$ terms $t_1, \dots, t_n$.

In practice, one more kind of term is commonly used informally in the context of set theory: set descriptors of the form $\{x:\varphi\}$, where $x$ is a variable, and $\varphi$ is a first order well-formed formula. This term cannot be rewritten as a function application, since $\varphi$ is not a term. This term creates a scope in which the variable $x$ is bound, similar to the way the quantified formulas of the form $\forall x\varphi$ and $\exists x\varphi$ work.

One way to introduce set descriptor terms into the logic, which then will no longer be a first order logic, so lets call it extended first order logic, is by introducing an infinite set of binding term constructors that is disjoint from the the first order logic vocabulary (consisting of logical symbols, variables, function symbols, and relation symbols), and a new way of forming terms: $Cx\varphi$, for every binding term constructor $C$, every variable $x$, and every extended first order well-formed formula $\varphi$ (the definition of function application and of a well-formed formula should be modified to accomodate this new kind of term). Let's call such terms binding terms.

We can now set aside one of the new-fangled binding term constructors, say $\sigma$, and interpret every binding term of the form $\sigma x\varphi$ as $\{x:\varphi\}$.

Set descriptors are probably the most familiar example of binding terms, but two others that I know of have been proposed in the past by mainstream mathematicians, likewise in the context of set theory: Hilbert's epsilon operator and Bourbaki's $\tau$ operator, which, though similar, are not the same operator, as they satisfy slightly different axioms.

Note that extending first order logic with binding terms necessitates a corresponding extension of the inference system, say Gentzen's Natural Deduction.

Has the combination of extended first order logic with a corresponding inference system been studied? Where can I read more about it?


texts: Data structure that allow efficient tag based lookups

texts:
I am looking for a highly efficient data structure for storage of data similar to the following.

Id    Tags   Order1 Order2
--------------------------
1     1,2     1      1
2     2,5     2      3
3     1,7     4      7
4     6       3      0

I need to be able to query this structure in such a way that it would give me a list of all ids containing an expression of tags - supporting AND and OR and NOT operations. Eg. ((1 or 2) and not 7)

I also need to be able to specify the ordering of the results (Order1 or Order2) and be able to specify maximum rows returned with an optional offset. Performance for the fetch of the first 30-100 results is key.

Finally, I need a cheap way to lookup "tag relations" for example I want to know which tags "relate" to tags (1 OR 2) and in what frequency. Meaning which tags appear in the same set as 1 OR 2 ... ordered by frequency.

Any idea of what data structure (or set of structures) would be highly efficient for this kind of work?

(I would like to use this as a proof of concept for redesigning the tagged pages of the SE family of sites)


texts: How hard is it to approximate distance of linear code

texts:
I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance.
I of course found that calculating the distance in exact is NP-Hard and that even Approximate it to any constant factor is hard (under randomized reductions).
However, this result is a bit old, and I didn't manage to find any newer hardness of approximation result.
I also didn't manage to find any polynomial approximation algorithms to this problem (for any factor) - all the works I found are either deal with specific code families or even don't relate to a promised gap approximation and bring only huristic/paractical result as a proof to the algorithm worthyness
Did my search miss something? Is there any current work that relates to this problem for a gap between constant and the trivial linear gap, and proves inapproximability /shows approximation for this gap?
Thanks!


texts: Advantages of ANN classifiers over the AdaBoost

texts: So what are the advantages of ANN classifiers over the AdaBoost or Boosting algorithm?


texts: Average performance of universal computation

texts:
This post is related to my previous question but takes a different angle

There are several related questions in here

Consider an input-less algorithm $A$ generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Consider $T$ the conditional expectation value of $A$'s execution time, the condition being "$A$ halts"

  Is T finite?

Consider $U$ an algorithm accepting input-less halting algorithms as input and producing their output as ouput. $U$ is essentially a universal Turing machine or perhaps a "universal algorithm" since we're assuming all algorithms run on the same "hardware". Consider $T(U)$ the conditional expectation value of the execution time of $U(A)$, the condition still being "$A$ halts"

  Is $T(U)$ finite for some $U$?

Obviously, the answer to the 2nd question is "yes" if the answer to the 1st question is "yes". If the answer to the 2nd question is "no", the following questions become trivial

Consider $T_{min} = \inf_{U} T(U)$

  Is there $U_{opt}$ s.t. $T(U_{opt}) = T_{min}$?

Consider infinite sequences $U_1, U_2...$ s.t. $\lim_{i \to \infty}T(U_i)=T_{min}$

  Is there an algorithm $V$ that takes a natural number $i$ for input and outputs $U_i$ as above?

Obviously, "yes" for the 3rd question implies "yes" for the 4th


texts: A course for learning algebraic complexity

texts:
I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.

Is there a set of lecture notes, books, papers and surveys for students who have read standard textbook about theory like Sipser's book or the Arora-Barak's complexity textbook.

The set of references will includes recent advanced results.


texts:
I'm trying to understand the sparsification lemma by Impagliazzo, Paturi and Zane (IPZ) (from this article) and in their proof they reduce the k-SAT problem to the k-set cover problem. But their definition of the problem seems to be different from the definition found in other articles where the problem is simply the normal set cover with the addition that each set is limited to contain a maximum of k elements from the universe, as can be seen in eg. this description from Führer and Yu (taken from this article):

The solution to this problem then consists of a collection of sets whose union covers the universe. But IPZ states the problem in this way:

and in that, the solution is defined as a set C that contains at least one element from each of the sets S in $\mathscr{S}$. It is not stated that the collection of sets necessarily covers the universe. Finding a C of size |$\mathscr{S}$| is therefore trivial and finding a minimal C corresponds to finding elements that overlap different sets from $\mathscr{S}$ in the best possible way.

After this lengthy intro my question is this: Am I somehow not reading the definition given by IPZ correctly and is it just an other way of stating the same problem? Or is this two different problems that unfortunately has been given the same title?


texts: Shortest s-t Path with a covering constraint

texts:
Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
  a source $s\in V$ and a sink $t\in V$;
  a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding subset $X(v)\subseteq X$.

  Objective: Find a minimum weight $s$-$t$-path for which the subsets
  on its path verties cover $X$.

Has this problem been studied before in combinatorial optimization?


texts:
Alice has a function $f: \{0,1\}^* \to \{0,1\}^*$ which can be computed in polynomial time. She claims that $x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing $f$ on the set $\{0,1\}^n$ to Bob. Bob is an algorithm from $\mathbf{P}^{\mathrm{SAT}}$ (or even $\mathbf{P}$). He wants to verify that $f$ is indeed a correct reduction of $\mathrm{SAT}$ to $\mathrm{CLIQUE}$ for all the inputs of length $n$.
If such Bob exists does it imply the collapse of the polynomial hierarchy?

In other words is $\{C \text{ - circuit }\mid \forall x \in \{0,1\}^n\colon x \in \mathrm{SAT} \iff C(x) \in\mathrm{CLIQUE}\}$
(here $n$ is the number of input gates of $C$).
$\Pi_2^P$-complete? $\mathbf{NP}$-hard? Clique and SAT are arbitrary $\mathbf{NP}$-complete languages I've picked.


texts:
I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes me as odd is that the definitions I have encountered so far seem to differ greatly. In particular, the differences that I have noted are

Difference between the uniform and logarithmic cost models: this can, for example, make a difference, when evaluating the time complexity of something like
for i = 1, 2, ..., n do c(i),
where c(i) is an instruction such that the number of bits involved depends on i.  When dealing with, say, sorting algorithms, all references I have ever come across adopt the uniform cost model, while in Cryptography, the time complexity of algorithms is always calculated in terms of bit operations.
Another difference is the definition of the size of an input: again, in sorting algorithms, the size of the input is simply the length of the vector that has to be sorted (as in graph searching algorithms, the number of nodes and edges). In Cryptography and Computational Number Theory, instead, the size of the input is always the number of bits involved. I don't know if this distinction is considered part of 1. , but it certainly makes a huge difference, since an algorithm that is linear using the first criterion, becomes exponential when adopting the second. Factorizing integers would be linear (actually, $O(\log{n} \sqrt{n})$) if we considered the input size of $n$ to be $n$.

One could justify these discrepancies with arguments such as "well, in Number Theory we are dealing with large integers, so adopting a more realistic model makes more sense". But this defies the whole purpose of evaluating asymptotic expressions for the complexity of algorithms! If, in certain contexts, we knew that all inputs were smaller then a fixed quantity, then everything would be $O(1)$. Also, how can it be possible to define, without ambiguity, complexity classes and other rigorous Computer Science concepts, when the definition of complexity varies from field to field?


texts: The complexity of finding a Borsuk-Ulam point

texts:
The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$.

Simmons and Su (2002) describe a method to approximate the point $x_0$ using Tucker's lemma. However, it is not clear what the run-time complexity of their method is.

Suppose we are given an oracle for the function $g$ and an approximation factor $\epsilon>0$. What is the run-time complexity (as a function of $n$) of:

Finding a point $x$ such $|g(x)|<\epsilon$?
Finding a point $x$ such that the $|x-x_0|<\epsilon$, when $x_0$ is a point satisfying $g(x_0)=0$?


texts: P and NP classes explanation through lambda-calculus

texts:
In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of computation are equivalent (and if we can introduce anything in terms Turing machine, we can introduce this in terms any model of computation), but I never seen explanation idea P and NP complexity classes through lambda-calculus.
Can anybody explain notions P and NP complexity classes without Turing machine and only with lambda calculus as model of computation.


texts: Graph classes for which the diameter can be computed in linear time

texts:
Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) and returns the length of the longest path found.

It is known that the APSP problem can be solved in optimal $O(n^2)$ time for several graph classes. For general graphs, there is an algebraic graph theoretic approach running in $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. However, computing the diameter is apparently not critically linked to APSP, as shown by Yuster.

  Are some non-trivial graph classes known for which the diameter can be computed even faster, say in linear time?

I am especially interested in chordal graphs, and any subclasses of chordal graphs such as block graphs. For example, I think the diameter of a chordal graph $G$ can be computed in $O(n+m)$ time, if $G$ is uniquely representable as a clique tree. Such a graph is also known as ur-chordal.


texts:
Given is a finite set $S$ of line segments in the plane.
I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$.
 Here splitting means that if $l$ intersects a line segment $xy$ in a point $z$ then $xy$ gets replaced by two new line segments $xz$ and $zy$.

The goal is to chose $l$ such that it minimizes the length of the longest line segment in $S'$.

I would be interested to know if this problem has been studied before.
What confuses me is that the problem does seem to be continuous and not discrete.


texts: Inappoximability status of Max One in Three SAT for satisfiable instances

texts: What is the inapproximability status of Max-One-in-Three SAT for satisfiable instances?


texts: Properties about verticies in Delaunay Triangulations

texts: I'm working on my thesis dealing with pathfinding over Delaunay triangulations. I have an algorithm that has running time in time proportional to the degree of a vertex. Are there any properties or upper bounds on the degree of vertices in a Delaunay (or Constrained Delaunay) triangulation?


texts: Is this a known combinatorial optimization/scheduling problem?

texts:
We are given $n$ stacks which hold "items" of different colour and a machine that can process multiple items of the same colour in one go. At each step, we can remove one item from the top of each stack and put it into our machine (so effectively the machine can process at most $n$ items in one step - for that to happen, all stacks must have items of the same colour on top). The goal is to process all items in minimal time.

Example input:

One possible solution is a greedy algorithm: at each step, just take as much items as possible and stuff them all into the machine. Unfortunately, the greedy algorithm is not optimal - it produces the following schedule for the example input:

The optimal schedule is the following:

I plan to go with some form of state space search, but maybe there is a more problem-specific and efficient approach? Links to relevant literature appreciated.


texts: What are the best possible time/error tradeoffs for approximate solution of linear programs?

texts:
For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity let's make no sparsity assumptions.

Suppose runtime $T$ is available to approximate the value of this game.

One technique for approximating this value is the multiplicative update method (known as no-regret learning in this context). This gives an error of $\tilde O(\sqrt{n/T})$, where $\tilde O$ hides log factors.

I don't know exactly what the error landscape for the best known interior point method looks like, but I'm guessing the error is something like $O(\exp(-T/n^3))$.

The multiplicative update methods give error that's an inverse polynomial in $T$. Interior point methods give error that's exponentially small in $T$. The error of the best of the two therefore slowly decreases for a while until interior point catches up, after which the error suddenly falls off a cliff. My instincts are against the best possible time/error tradeoffs behaving this way.

My question:

Is there an algorithm for approximate linear programming that smoothes out the corner of the time/error tradeoff curve? That is, an algorithm that does at least as well as the best of the two for any value of the available time parameter and has a relatively smooth time/error tradeoff. A more intelligent way to combine interior-point and multiplicative update techniques than taking the better of the two is one likely way to get such an algorithm.

References:

Multiplicative update in general:

http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Multiplicative update for zero-sum games:

http://dx.doi.org/10.1016/0167-6377(95)00032-0

Multiplicative update for covering/packing LPs:

http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.1987v1.pdf

The original interior point paper:

http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf

Interior-point from an applied math perspective:

Bertsekas's Nonlinear Programming, section 4.1.1.


texts: Combinatorial characterization of hypergraph Tseitin satisfiability

texts:
The Tseitin formulas are as follows: Given a connected graph and a function $\alpha: V \rightarrow \{0,1\}$. Associate each edge $e$ with a variable $x_e$. The Tseitin formula $G(\alpha)$ is defined to be
$$
\bigwedge_{v \in V} \big(\sum_{(u,v) \in E(G)} x_{(u,v)} = \alpha(v) \mod 2 \big)
$$

It's easy to see that the Tseitin formula $G(\alpha)$ is satisfiable iff $\sum_{v \in V} \alpha(v) = 0 \mod 2$.

This gives a nice characterization of the satisfiability of a system of random mod2 equations ($k$-XORs) $Ax = b \mod 2$ where each variable occurs in exactly 2 equations in the system which is connected (we cannot partition the rows of $A$ into two sets $A_1$ and $A_2$ so that $A_1 \cap A_2 = \emptyset$). Push the negation of any variable in a constraint into $b$ so that all variables occur positively in $A$. $Ax = b$ is then satisfiable iff $$\sum_{i = 1}^{|b|} b_i= 0 \mod 2.$$
This is because $Ax = b$ is equivalent to the Tseitin formulas where for each constraint $a_ix = b_i$ we create a vertex $v_i$ where $\alpha(v_i) = b_i$ and each variable $x_i$ corresponds to an edge between the two constraints in which $x_i$ appears.

My question is, if we relax the requirement that each variable occurs in 2 equations (to say at most $k$ equations), is there a similar nice combinatorial characterization of the satisfiability of the system of equations? This corresponds to a hypergraph version of the Tseitin formulas. It's easy to see that in this case if $\sum_{i=1}^{|b|} = 1\mod 2$ is odd then the system is unsatisfiable, but the other direction does not hold. Is there a nice sufficient condition for the satisfiability of such a system?


texts: What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution?

texts:
I know that in general, multivariate polynomial satisfiability is equivalent to 3-SAT; however, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a polynomial time solution.

I guess the more general question would be, are there any classes of multivariate polynomials for which the satisfiability problem is efficiently solvable?


texts: What are the relationships between Functional Reactive Programming, Automatic Differentiation, Self-Adjusting Computation and Partial Evaluation?

texts:
Self-adjusting computation seems to be related to all of the other topics, but I would like to get a clearer sense of how they all relate. For example, do any of them subsume or obsolete any of the others?

One might also throw Incremental Computing into the mix, of which Self-adjusting computation is presumably a special case.


texts: Algorithm for detecting closed region on a plane

texts:
First off, I just want to say that I am not well versed in computational geometry, so if this question has some obvious answer, I apologize.  I tried googling it but I could not find anything.

My question: Given an input of a plane with 1 or more line segments, is there an efficient algorithm for determining if there exists a closed region on this plane?  For example, see the following picture:

benjamindicken.com/closed_region.png

On this plane, there exists one closed region.  I would like the algorithm to return true if a closed region exists, and false if one does not.

At the moment, I only need this algorithm to determine if a closed region exists or not, but I could foresee needing this to return the number of closed regions as well.

Thanks for your help.


texts: How to become a Theoretical Computer Scientist

texts:
I am a computer science graduate from India. I have worked in a reputed software company for 10 months only to discover that my area of interest is something else. So I resigned from there and I am presently preparing for GATE 2014 which is due in a few days. Now I have the following doubts in my mind :
 1. Is it sufficient and necessary to get into a reputed college in India through GATE ?
 2. Are there any alternatives to pursue a career in Theoretical CS ?
 3. How about foreign universities for this career path ?

Please provide me some career guidelines. Thanks in advance.


texts:
Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT?

Can the estimates provide sharp lower bound to MAXCUT?


texts: Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

texts:
There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma.

Can we develop a Switching Lemma result to prove a size lower-bound for $\mathsf{TC^0}$ circuits (similar to the lower-bound proofs for $\mathsf{AC^0}$)?

Or is there any inherent obstacle to using this approach for proving $\mathsf{TC^0}$ lower-bounds?

Do barrier results like Natural Proofs say anything regarding using Switching Lemma like techniques to prove $\mathsf{TC^0}$ lower-bounds?


texts: Finding witness in minkowski sum of integers

texts:
Let $A$ and $B$ be subsets of $\{0,\ldots,n\}$. We are interested in finding the Minkowski sum $A+B=\{a+b~|~a\in A,b\in B\}$.

$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ is a characteristic function of $X$ if $$\chi_X(x) = \begin{cases} 1 \text{ if } x\in X\\ 0 \text{ otherwise}\end{cases}$$

Let $f$ be the discrete convolution of $\chi_A$ and $\chi_B$, then $x\in A+B$ if and only if $f(x)> 0$. Hence $A+B$ can be computed in $O(n\log n)$ time by discrete convolution via FFT.

Sometimes it is important to find out the actual pair $a\in A$ and $b\in B$ that sums to $x$. $a\in A$ is called a witness of $x$, if there exist $b\in B$ such that $a+b=x$. A function $w:A+B\to A$ is called a witness function if $w(x)$ is a witness of $x$.

  Is it possible to compute a witness function in $O(n\log n)$ time?


texts: Quantum Money where not even the Bank can counterfeit

texts:
The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties:

The bank can produce bank notes in the form of quantum states.
Anyone can verify that one of these quantum states is a valid bank note without destroying the quantum state.
No one except the bank can produce more bank notes, even if they already have some.

All assuming that the actors only have polynomial time quantum computers.

My question is if you can take this step further and make it so that even the bank is unable to forge bills.

What do I mean by this? The quantum money protocol I am looking for would have an integer parameter $k$, and the bank could only create $k$ valid bank notes.

(This might seem impossible since the bank could just run the protocol again to get $k$ more bank notes. A way to prevent this would be to require it to produce a random classical string $s$ of bits that it releases publicly, such that it can not run the protocol again and produce the same $s$ with non-negligible probability.)


texts: On the shortest vector problem (is it $NP$-complete?)

texts:
Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.

Has this been derandomized?


texts: Directed Acyclic Graph partition into minimum subgraphs with a constraint

texts:
I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 constraints:-

A sub-graph should have nodes of similar color
A sub-graph cannot directly or indirectly depend on it's own output

Example:- In the attached picture, the sub-graph with yellow nodes is invalid since input from the red node breaks rule#2 : 4th node from top has an input which depends on output of 2nd node - via the red node (outside the subgraph) Hence the algorithm should partition it after #2 or #3 so that 2 and 4 are on different nodes

Am sure this is a pretty common problem in Graph theory and must have a name and a standard algorithm for it. Thanks in advance for any pointers to it!


texts: Pruning a graph by removing vertices not part of any minimal Steiner tree

texts:
Given a sizable graph $G = (V, E)$, with $|V| \approx 1400$ vertices and $|E| \approx 1600$ edges, I have an optimization problem to find a connected subgraph of $G$ of size $k$ such that a given function $f$ over the subgraph is optimal. Furthermore, I have a set of undesirable vertices $U \subset V$ which do not affect the value of $f$, and desirable vertices $D = V - U$.

As a preprocessing step, I'm trying to prune $G$ by removing all undesirable vertices that will never be part of an optimal solution. A undesirable vertex has no affect on the value of $f$, but still might be included in an optimal solution if it is part of a minimal Steiner tree with desirable terminals $T \subset D$. Any vertex which is not part of any minimal Steiner tree of any subset $T \subset D$ is safe to remove.

Now, since I'm very inexperienced in this field and am having trouble finding the right literature, I'm asking for any advice or references for solving the problem of finding such vertices that are provably not part of an optimal solution.


texts: Examples where insight from geometry was useful for solving something completely non-geometric

texts:
One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think of a triplet of numbers as a point in 3-d and hence computation about triplets of numbers as computation about points in 3-d, which can then be solved using our intuition about space. This seems to suggest that it should be possible at times to solve a completely non-geometric problem using techniques from geometry. Does anyone know of such examples?

Of course, the terms 'geometric' and 'non-geometric' are slightly vague here. One can argue that any geometric problem is actually non-geometric if you replace all points with their co-ordinates. But intuitively, the definition is clear. Let's just say that we call something geometric if we would consider sending a paper about it to SoCG.


texts:
I would like to ask how could someone modify FloodSet algorithm to work in a general network,
where process failures happen..Is it possible for it to work if a "crucial" [1] failure happens?

[1]: As crucial i mean a failure in a process that "cuts" the network in two separate pieces


texts:
While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive integers given as part of the input. A specified subset of the variables $x_{ij}$ is set to zero, and the rest can take positive integral values:

Minimize
$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$
Subject to:
$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$
$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

I would like to know if this integer program is solvable in polynomial time; my original problem is solved if it is, and I have to try some other way if it isn't. So my question is:

How do I figure out if a certain integer linear program can be solved in polynomial time? Which integer linear programs are known to be easy? In particular, can the above program be solved in polynomial time? Could you point me to some references on this?


texts:
This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$.

Are there any similar results for Boolean circuits or do we know why such a thing is not possible?


texts: What do people mean by capabilities and capacities?

texts:
Someone made a casual remark to me about the terminology of capabilities and capacities, in the context of threads, processors and runtime systems, particularly their theoretical modelling.

For example, in Haskell, an OS thread that is started to schedule work for a single logical processor (hardware thread) is called a capability. Where does this terminology come from? I'm not sure what it really means.

The person who made the casual remark thought that there is also the related concept of capacities, but neither of us are sure.

Anyone know about this? Or have any references for me?


texts:
A Boolean function $\phi$ on variables $X$ is evasive if every decision tree for $\phi$ has height $|X|$. In other words, for any strategy that picks variables of $X$ and asks for their value, an adversary can answer the queries such that the strategy needs to ask about the value of all variables of $X$ to know the value to which $\phi$ evaluates.

A monotone DNF is a disjunction of conjunction of variables, representing a monotone Boolean function on the set $X$ of variables that it uses.

Which monotone DNFs are evasive? Is there a characterization of them? What is the complexity, given a monotone DNF, of determining whether it is evasive?

Examples of evasive monotone DNFs include single-clause DNFs, e.g., $x \land y \land z$, where we must query the value of every variable (and the adversary can answer $1$) until the last one which determines the value of the formula. For another example, take $(x \land y) \lor (y \land z)$: if I ask about $x$ or $z$ then the opponent answers $0$ and I'm left with evaluating the other clause, if I ask about $y$ the opponent answers $1$ and I must evaluate $x \lor z$ which requires me to query both variables.

However, not all monotone DNFs are evasive. For instance, for $(s \land t) \lor (t \land u) \lor (u \land v)$, I can query variable $t$. If it is false, then I know that clauses $s\land t$ and $t \land u$ are false, so I can evaluate the function just knowing $u$ and $v$ (I don't need to query $s$). If it is true, then I have to evaluate $s \lor u \lor (u \land v)$, and as the second clause subsumes the third, I just need to know $s$ and $u$ (I don't need to query $v$).

Playing a bit with the problem in the case of graph DNFs (with two variables per clause), it looks like for a path $(x_0 \land x_1) \lor \cdots \lor (x_{n-1} \land x_{n})$ with $n>0$ the function is not evasive iff $n$ is a multiple of 3, and this seems to generalize to trees if there is some kind of tree structure on nodes that are 3 steps apart. For general graphs, I have no idea. I have looked for related work about evasiveness and decision tree complexity for monotone CNFs and DNFs but I didn't find anything relevant.

On graph DNFs, the problem can be seen as a kind of game on the graph of the formula. You pick a vertex $v$ (= variable) on the graph, and the opponent can choose between:

removing $v$ and all its incident edges (= $v$ evaluates to $0$, all clauses involving it are removed), or
removing the open ball of radius 2 centered on $v$, i.e., $v$, its adjacent edges, the neighbors of $v$, and their adjacent edges (= $v$ evaluates to $1$, all clauses involving $v$ become singleton clauses involving $v$'s neighbors, you will need to ask about each of these neighbors because each has a singleton clause involving it, but these singleton clauses subsume all other clauses involving the neighbors so you get to remove them).

The question is about characterizing and recognizing the graphs $G$ for which you have a strategy that guarantees that you win, where "winning" means "reaching a graph with an isolated vertex" (= a variable that you do not need to ask about).


texts:
The paper Quantum Complexity of Testing Group Commutativity considers the problem of identifying if a given group is commutative.  The group is given via a certain oracle and the complexity of the problem is measured by the number of quantum queries to this oracle.  The paper gives an algorithm for this problem as well as an analysis of this algorithm that yields an upper bound of $O(k^{2/3} \log k)$.

I think the analysis of their algorithm can be improved to give an upper bound of $O(k^{2/3} \log^{2/3} k)$.

Their quantum algorithm uses a quantum random walk on the following graph.  The vertices are $\ell$-tuples containing distinct elements from a universe of size $k$.  Two vertices are adjacent if

the Hamming distance between them is 1 or
the Hamming distance between them is 2 and, after swapping the elements (in one of the vertices) in the two locations in which they differ, the Hamming distance between them is 0 (i.e., they are the same vertex).

For an example of the second type of edge, consider $k = \ell = 3$.  Then the vertices $(1, 2, 3)$ and $(1, 3, 2)$ would be connected by such an edge.

For given natural numbers $k$, and $\ell$, let $G(k, \ell)$ denote this graph with parameters $k$ and $\ell$.  The analysis in the paper shows that the absolute spectral gap of $G(k, \ell)$ is $\Omega(\frac{1}{\ell \log \ell})$.  I think the analysis of this absolute spectral gap can be improved to $\Omega(\frac{1}{\ell})$.

  Conjecture
  The absolute spectral gap of $G(k, \ell)$ with $k \ge 3$, $\ell \ge 2$, and $k > \ell + 1$ is $\Omega(\frac{1}{\ell})$.

This conjecture implies that the complexity of their algorithm is $O(k^{2/3} \log^{2/3} k)$.

I addition to just "feeling" that this conjecture should be true, I have "checked it" for 19 (small) pairs of $k$ and $\ell$ with $k \le 8$ and $\ell \le 6$ in the sense that I computed the spectra for those small graphs, conjectured a pattern for the relevant eigenvalues based on those spectra, and then (easily) showed that the above conjecture is true.

Does anyone know how to prove this conjecture?


texts: Can a random oracle change which TFNP problems are strongly hard-on-average?

texts:
I've been thinking about the following question at

various times
since I saw this question on Cryptography.

Question

Let $R$ be a TFNP relation.  Can a random oracle help P/poly

to break $R$ with non-negligible probability?  More formally,
$
\newcommand{\Pr}{\operatorname{Pr}}
\newcommand{\E}{\operatorname{\mathbb{E}}}
\newcommand{\O}{\mathcal{O}}
\newcommand{\Good}{\mathsf{Good}}
$

Does

  for all P/poly algorithms $A$,
  $\Pr_x [R(x, A(x))]$ is negligible

necessarily imply that

  for almost all oracles $\O$,
  for all P/poly oracle-algorithms $A$,
  $\Pr_x [R(x, A^\O(x))]$ is negligible

?

Alternative formulation

The relevant set of oracles is $G_{\delta\sigma}$ (thus measurable), so by taking contrapositive and applying Kolmogorov's zero-one law,
the following formulation is equivalent to the original one.

Does

  for almost all oracles $\O$,
  there exists a P/poly oracle-algorithm $A$ such that
  $\Pr_x [R(x,A^\O(x))]$ is not negligible

necessarily imply that

  there exists a P/poly algorithm $A$ such that
  $\Pr_x [R(x,A(x))]$ is not negligible

?

The uniform case

Here's a proof for the uniform version:

There are only countably-many PPT oracle-algorithms,
so by countable additivity of the null [ideal][8],
there is a PPT algorithm $A$ such that
for a non-null set of oracles $\O$,

$\Pr_x [R(x,A^\O(x))]$ is non-negligible.
Let $B$ be such an oracle-algorithm.

Similarly, let $c$ be a positive integer such that
for a non-null set of oracles $\O$,

$\Pr_x[R(x,B^\O(x))]$
is infinitely-often at least $n^{-c}$,
where $n$ is the length of the input.

By the contrapositive of Borel-Cantelli,
$\sum_{n=0}^{\infty} \Pr_{\O} \left[
n^{-c} \leq \Pr_{x\in\{0,1\}^n}[R(x,B^\O(x))]
\right]$ is infinite.

By the comparison test, infinitely often
$\Pr_{\O} \left[
n^{-c} \leq \Pr_{x\in \{0,1\}^n}[R(x,B^\O(x))
\right] \geq n^{-2}$.

Let $S$ be the PPT algorithm which [simulates the oracle][12] and
runs $B$ with that simulated-oracle.

Fix $n$ and
let $\Good$ be the set of oracles $\O$ such that
$n^{-c} \leq \Pr_{x\in\{0,1\}^n} [R(x,B^\O(x))]$.

If $\Good$ is not null then
$$\begin{matrix}
\Pr_{\O} [\O\in \Good] \cdot n^{-c}
\\ = \\
\Pr_{\O} [\O\in \Good] \cdot \E_{\O}[n^{-c}]
\\ \leq \\
\Pr_{\O} [\O\in \Good] \cdot \E_{\O} \left[
\Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))] \mid \O \in \Good
\right]
\\ = \\
\E_{\O}\left[
\Pr_{x\in \{0,1\}^n} [\O \in \Good \text{ and } R(x,B^\O(x))]
\right]
\\ \leq \\
\E_{\O}\left[
\Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))]
\right]
\\ = \\
\Pr_{\O, x\in\{0,1\}^n} [R(x,B^\O(x))]
\\ = \\
\Pr_{x\in \{0,1\}^n, \O} [R(x,B^\O(x))]
\\ = \\
\E_{x\in \{0,1\}^n} \left[ \Pr_{\O}[R(x,B^\O(x))] \right]
\\ = \\
\E_{x\in \{0,1\}^n} \left[ \Pr[R(x,S(x))] \right]
\\ = \\
\Pr_{x\in \{0,1\}^n} [R(x,S(x))]
\end{matrix}$$
.

Since $\Pr_{\O} [\O\in \Good] \geq n^{-2}$ infinitely often,
$\Pr_x[R(x,S(x))]$ is not negligible.

Therefore the uniform version holds.  The proof critically uses the fact that
there

are only countably many PPT oracle-algorithms.  This idea does not work in the

non-uniform case, since as
there are continuum-many P/poly oracle-algorithms.


texts: Maximum common subgraph of two planar graphs of bounded degree k

texts:
Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar graphs is NP-complete w.r.t to the number of vertices per David Eppstein[1].

However, the MCS of partial k-Trees of Bounded degree, (including outerplanar graphs, etc.), can be evaluated in polynomial time [2].

Is there a result for something in-between? Practical answers are also welcome.

[1] Largest common subgraph of two maximal planar graphs

[2] http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_10#page-1


texts:
Are there any papers that deal with something like the following scenario?

Given a large corpus of text, find all n-tuples of documents that are semantically identical.

This is not a categorization problem as if it were to be treated as one, there would be an indeterminate (until its finished) number of categories, with the vast majority of categories only having one document in them.

In fact, I don't think it is a part of any of these major areas on NLP.

Additionally, I believe that all purely statistical approaches are doomed to fail here as the training set cannot cover every post.

So, are there any papers on this topic?


texts: Computing sum of sparse polynomials squared in O(n log n) time?

texts:
Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient algorithm for computing the polynomial:

$$\sum_i p_i(x)^2$$

Since this polynomial has degree at most $2n$, both input and output size is $O(n)$. In the case $m=1$ we can compute the result using FFT in time $O(n \log n)$. Can this be done for any $m<n$? If it makes any difference, I'm interested in the special case where coefficients are 0 and 1, and the computation should be done over the integers.

Update. I realized that a fast solution for the above would imply advances in fast matrix multiplication. In particular, if $p_k(x)=\sum_{i=1}^n a_{ik} x^i + \sum_{j=1}^n b_{kj} x^{nj}$ then we can read off $a_{ik} b_{kj}$ as the coefficient of $x^{i+nj}$ in $p_k(x)^2$. Thus, computing $p_k(x)^2$ corresponds to computing an outer product of two vectors, and computing the sum $\sum_k p_k(x)^2$ corresponds to computing a matrix product. If there is a solution using time $f(n,m)$ to computing $\sum_k p_k(x)^2$ then we can multiply two $n$-by-$n$ matrices in time $f(n^2,n)$, which means that $f(n,m)=O(n\log n)$ for $m\leq n$ would require a major breakthrough. But $f(n,m)=n^{\omega/2}$, where $\omega$ is the current exponent of matrix multiplication, might be possible. Ideas, anyone?


texts: Why does this algorithm not have an exponential complexity?

texts:
In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf

The authors present a PTAS algorithm that can compute a safe, close to optimal trajectory from a point A (having a certain speed vector) to a point B (having a certain speed vector). They do this by transforming the problem to finding the shortest path in a directed graph. All vertices in the resulting directed graph have an outgoing degree of 3.

I don't understand how we can find the shortest path in this directed path from one point to another (by using BFS) without the complexity being exponential, since doing a BFS from the starting point until we encounter the end point would take $O(3^x)$ with $x$ being the layer of the BFS.
Instead the complexity that is noted on page 5 of the article is this :

  $O( n( \frac{lv\gamma³}{\epsilon⁶})^d)$

$n$ being the number of bounding halfplanes on obstacles, $l$ being the length of the side of a cube in which all points are placed, $v$ is maximum velocity and $\gamma$ is maximum acceleration divided by maximum velocity. $\epsilon$ as always is the approximation value and $d$ the number of dimensions in which our problem is placed. For simplicity let $d$ be $1$.

Clearly we can see this complexity is not exponential, my question is why? Even in one dimension, we still obtain a graph in 2 dimensions (1 for position and one for velocity) and the BFS will still take exponential running time. Am I missing something?

Thanks


texts: Is there a theory to answer "the simplest program to solve a problem"?

texts:
To answer "what problems can be solved by computing", we developed the theory of computability. For the problems that are computable, is there a theory to answer the question "is the program I get the simplest one"?

I do not think computational complexity answer the question. I think it considers how long we need (though measured abstractly).

I am not sure whether algorithmic information theory answer the question. It seems that the theory talks about size, where the equivalence of minimal size and simplest is not obvious to me (well, at least they feel different to me).

I think the theory should at least define "simple" or "simpler than" relation.

I am now convinced that I should look into Kolmogorov Complexity. However, I would like to explain what was in my mind when I was asking the question.

When I improve a program, I try to reduce unnecessary connections between different parts of the program (maybe re-dividing parts so that there can be less or weaker connections). Since the connections are reduced, the program feels "simpler". Hence the choice of the word "simple" when I am phrasing the question. It is very likely the size of the program also decreases, but that is a good side effect, not the main goal. Obviousely, the improving process cannot go forever. There is a point that I should stop. If, only by considering the "structure" (sorry for another undefined concept) or "relation", can I convince myself that nothing more can be done?

Here contains better description of my notion of complexity.

Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623


texts: Full Completeness vs Full Abstraction of a program translation

texts:
Compiler verification efforts often come down to proving the compiler fully abstract: that it preserves and reflects (contextual) equivalences.

Instead of providing full abstraction proofs, some recent (categorical based) compiler verification work by Hasegawa [1,2] and Egger et. al. [3] prove the full completeness of various CPS translations.

Question:
What is the difference between full completeness and full abstraction?

To me, completeness just looks like equivalence reflection for a translation and fullness appears to be a consequence of equivalence preservation.

Note: Both Curien [7] and Abramsky [8] explore the relationship between definability, full abstraction, and to some extent full completeness. I suspect these resources may have the answer to my question, but after a surface read I have yet to confirm that.

Some Background:
The term "full completeness" was coined by Abramsky and Jagadeesan [4] to characterize the correctness of a game-semantic model of Multiplicative Linear Logic.

Blute [5] provides the following definition:

  Let $\mathcal{F}$ be a free category. We say that a categorical model
  $\mathcal{M}$ is fully complete for $\mathcal{F}$ or that we have
  full completeness of $\mathcal{F}$ with respect to $\mathcal{M}$ if, with respect to some interpretation of the generators, the unique free
  functor $[\![ - ]\!] : \mathcal{F} \rightarrow \mathcal{M}$ is full.

As far as I can tell, Hasegawa in [6] is the first to adapt full completeness to describe a program translation instead of a categorical semantic model. In this case, the Girard translation from simply typed lambda calculus to the linear lambda calculus.
Later, in [1], he defines full completeness of the CPS translation $(\cdot)^\circ$ as:

  If $\Gamma^{\circ};\emptyset \vdash N : (\sigma^\circ \rightarrow o) \multimap o$ is derivable in the linear lambda calculus, then there
  exists $\Gamma \vdash M : \sigma$ in the computational lambda calculus
  such that $\Gamma^{\circ};\emptyset \vdash M^\circ = N : (\sigma^\circ
 \rightarrow o) \multimap o$ holds in the linear lambda calculus.

(where $o$ is a base type in the linear lambda calculus (target language), but not in the computational lambda calculus (source language).)

To me, Hasegawa's definition seems like a fullness and should really be combined with completeness to get full completeness.

Egger et. al. [3] define full completeness of a CPS translation $(\cdot)^v$ as a combination of (1) completeness and (2) fullness:

  (1): If $\Theta \vdash M,N : \tau$ and $\Theta^v | - \vdash M^v =_{\beta\eta} N^v : !\tau^v$ then $\Theta \vdash M =_{\lambda_c} N : \tau$

  (2): If $\Theta^v | - \vdash t : !\tau^v$ then there exists a term
  $\Theta \vdash M : \tau$ such that $\Theta^v | - \vdash M^v =_{\beta\eta} t : !\tau^v$

(where $=_{\lambda_c}$ is Moggi's computational equational theory)

[1] "Linearly Used Effects: Monadic and CPS Transformations into Linear Lambda Calculus", Hasegawa 2002

[2] "Semantics of Linear Continuation-Passing in Call-by-Name", Hasegawa 2004

[3] "Linear-use CPS Translations in the Enriched Effect Calculus", Egger et. al. 2012

[4] "Games and Full Completeness for Multiplicative Linear Logic", Abramsky and Jagadeesan 1992

[5] "Category Theory for Linear Logicians", Blute 2003

[6] "Girard Translation and Logical Predicates", Hasegawa 2000

[7] "Definability and full abstraction", Curien 2007

[8] "Axioms for Definability and Full Completeness", Abramsky 1999


texts:
Given a matrix of size $n\times n$ with numbers, where every row is sorted, one can compute the $k$th smallest element in $O(n \log^2 n)$ time by simulating (implicitly) quick-select on this matrix (removing one log factor can be done by avoiding the binary search in each row). In fact, $O(n )$ time algorithm is possible if the columns are also sorted, see below for details by simulating some variant of QuickSelect on this matrix.

My question: Is there a reference that describes and analyzes how to simulate QuickSelect on an implicit set (like a row sorted matrix)?

This is not hard, but I would prefer not to write it down if somebody already did it. Thanks in advance...

More details

Fredrickson and Johnson showed how to get $O(n)$ time algorithm if both rows and columns are sorted http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no. It is in fact not too hard to come up with an $O(n)$ randomized time algorithm by massively sampling in each iteration, estimating the interval where the element must lie, and then recursively continuing on the elements lying in this interval (this selection algorithm due to Rivest and Floyd is described in pages 47-51 in the randomized algorithms book by Motwani and Raghavan).