texts: Does a multilayer perceptron taught by simple backprop learn the shape of a character or the exact image of a character?

texts:
(Feel free to suggest a better title) (same with tags, none of relevant tags exist yet, and I only have 101)

Let's say I have a perceptron with an optimal number of layers and optimal number of neurons, which I have taught to recognize an alphabet which was printed in a certain font, with the same settings and resolution. Now if I feed it a symbol from that set, but say, printed in another (but similar) font, or with the same font, but rotated 5 degrees, or shifted 2 pixels to the left, or scaled a 5 percent, and so on, will this system recognize this modified symbol, or at least have an easier time learning to recognize this symbol? (than a system without any prior learning)

Basically, what is the point of back-propagating neural networks? Is it
1) a way to recognize shapes, and effectively filter noise in images of those shapes, in form of different rotations, scales and other disortions
or
2) just a relatively simple and fast way to recognize a limited number of bitmaps of those shapes, and not being able to recognize the shape in another bitmap if that particular bitmap was never taught to the network.


texts:
In languages oriented towards systems programming, digital logic and hardware design, it's common to treat boolean as a subtype of integer. In languages oriented towards mathematics and type theory, it's more usual to treat them as disjoint types.

Being from more of a systems programming background, it has always seemed to me appropriate to take the former approach. I would have thought it appropriate even from a mathematical viewpoint, since we already have a hierarchy of numeric types (natural numbers are a subtype of integer which is a subtype of rational etc.) so it would fit neatly at the start of that hierarchy; but then I'm not a real mathematician, so I may be missing something.

Apart from a little bit of extra error checking (catching the mistake if you pass a boolean to a function expecting an integer and you didn't mean to), is there any advantage to having them be disjoint types?


texts: Using lambda calculus to derive time complexity?

texts:
Are there any benefits to calculating the time complexity of an algorithm using lambda calculus?  Or is there another system designed for this purpose?

Any references would be appreciated.


texts: Suppose I have a simple polygon $S$ and an integer $k$.  What are some existing approaches for finding the smallest radius $r$ such that I can cover $S$ with $k$ circles of radius $r$?  How about if $r$ is fixed, and I want to minimize $k$?


texts: No Fair Merge via Nondeterminstic Data Flow Streams

texts:
While reading Wikipedia, I ran across a proof given on Unbounded Nondeterminism that I do not understand.

The proof is given as,
An example of the role of fair or unbounded nondeterminism in the merging of strings was given by William D. Clinger, in his 1981 thesis. He defined a "fair merge" of two strings to be a third string in which each character of each string must occur eventually. He then considered the set of all fair merges of two strings merge(S, T), assuming it to be a monotone function. Then he argued that merge(⊥,1ω)⊆ merge(0,1ω), where ⊥ is the empty stream. Now merge(⊥,1ω) = 1ω, so it must be that 1ω is an element of merge(0,1ω), a contradiction.

My misunderstanding is, "merge(⊥,1ω) = 1ω." Previously it said that "merge(S, T)" is "the set of all fair merges of two strings".

Why is "merge(⊥,1ω) = 1ω," instead of merge(⊥,1ω) = {1ω}. If so, isn't {1ω} ⊆  merge(0,1ω)? What am I missing?


texts:
In chapter 8 (page 288) of the "Handbook of Applied Cryptography," the authors describe an attack against RSA with small exponent. Let there be 3 parties with independent RSA public keys $(e_1,n_1)$, $(e_2,n_2)$, and $(e_3,n_3)$, with $e_1=e_2=e_3=3$. With very high probability, the moduli are coprime; otherwise, it would be possible to factor them.

Consider a forth party, who wishes to secretly send a single message $m$ to the 3 parties above. He computes $c_i = m^3 \pmod{n_i}$, and sends $c_i$'s on the channel. The adversary, who eavesdrops the ciphertexts, can simply apply the Chinese Remainder Theorem to recover $m$. (See the above chapter for exact computations.)

  My question is: Assume that there are only two recipients, instead of three. Given $c_1$ and $c_2$, is it possible to prove (under the RSA assumption) that the adversary cannot recover $m$ (except with negligible probability)?

More formally, let $G$ be an RSA public-key generator, and $A$ be a PPT adversary. Is it possible to prove, under the RSA assumption, that the success probability of $A$ is negligible in the experiment below?

$(e_1,n_1) \leftarrow G(1^k)$ and $(e_2,n_2) \leftarrow G(1^k)$
$m \leftarrow_R \{1,\ldots,\min\{n_1,n_2\}\}$
$c_1 \leftarrow m^{e_1} \pmod{n_1}$ and $c_2 \leftarrow m^{e_2} \pmod{n_2}$
$m' \leftarrow A(e_1,n_1,e_2,n_2,c_1,c_2)$
IF $m'=m$ OUTPUT "$A$ succeeded"; ELSE OUTPUT "$A$ failed".

PS: One can assume any technical condition to make the proof work; say $e_1=e_2$.


texts:
The input is set of (disjoint) intervals $I$. The output should be the following rooted binary tree. Each leaf node corresponds to an interval from $I$. Each interior node contains an interval which encloses intervals from both child nodes. The goal is to minimize the sum of lengths of intervals in interior nodes.

Example. Input $I=\{[1,5], [7,9], [20,25]\}$

leaf nodes: $l_1 = [1,5], l_2 = [7,9], l_3=[20,25]$

interior nodes $i_1 = (l_1, l_2, [1,9]), i_2= (i_1, l_3,[1,25])$

Is this problem NP-hard?


texts:
Is there a canonical name for the following data structure for list of lists?

Suppose we have got a list of length $Z$ of finite lists $[a_0,\dots,a_n], [b_0,\dots,b_m], [c_0,\dots,c_o], \dots$ of the same data type, but with variable length. Then we can represent them in the following way in one single data strucutre.

Let $P = [0,p_1,p_2,\dots,p_Z]$ be a list of integers, and let

$Q = [a_0,\dots,a_n,b_0,\dots,b_m,c_0,\dots,c_o,d_1,\dots ]$

be the concatenation of all list entries. We demand that for all indices $0 \leq z < Z$ we have that the $z$-th list is given by the entries of Q with indices $q$, $P[z] \leq q < P[z+1]$. Note that $P[Z]$ is the total number of elements listed.

An instance of this idea is the compressed sparse rows format for sparse matrices

http://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_.28CSR_or_CRS.29

I would like to know a proper for the general idea.


texts: Learnability of under some characteristics of the distribution

texts:
TLDR; is there any results showing that more concentrated (or easier) distributions are easier to learn?

In PAC-learning, the guarantee is given for any underlying distributions. But in reality, we don't need the guarantees for any distribution. For example for image classification, there is a limited underlying distribution. It makes sense to have stronger guarantees for easier distributions. Are there any such results?


texts: Finding exact value with a quotients of products of random values

texts:
Sorry for the haphazard title: really not sure what this should be called

Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime).

Now, suppose we have $n+1$ variables $R_1, \dots, R_n, R_{n+1}$, such as for each $R_i$:
$R_i = r_{i_1} r_{i_2} \dots r_{i_k}$ where $r_{i_j}$ are $k$ randomly drawn values from $S$ with replacement$^*$.

We consider the problem of expressing $R_{n+1}$ as a quotient of $R_i$ ($i < n+1$). That is, find $S_1$, $S_2$ such that:

$R_{n+1} = \frac{\prod_{i \in S_1}{R_i}}{\prod_{i \in S_2}{R_i}}$

(ideally, we are looking in $\mathbb{Z}_N$, but I doubt it makes a big difference, provided $N$ is large enough compared to the other parameters)

How "difficult" is this problem?
(Assuming the previous answer to be: "not so easy" or worse) What about even deciding on the existence of a solution?
Does this problem (or something it can be trivially reduced to) have a formal name? [guess this should be my first question, huh]
Bonus question (depending on the above): Can any hypothesis be made about the uniqueness of $S_1$/$S_2$ elements (by default, it does not sound like elements should be unique in either collection) or the maximum size of either collection...

My intuition is that there is no easy solution, but I cannot see a simple reduction to any NP-Hard problem that I can think of... (there's an obvious parallel set-theory problem, but I'm not sure I see an easier answer for it)

$^*$: or without replacement, if it makes a major difference to the questions/proofs...


texts: Are local canonical labellings of a graph ever a subsequence of the global canonical labelling?

texts:
So a canonical labelling of a graph G is a function CL(G) that maps each vertex to a numerical label. Sorry if my definitions are a bit obvious or clumsy, by the way. For every isomorphic graph G', CL(G) = CL(G').

Now, I'm actually dealing here with spanning trees of the graph, and spanning subtrees. The tree T that spans G is rooted at a particular vertex, and the labelling of this tree may not be canonical for the whole graph.

My question, then is this : if you label a subtree of a particular spanning tree, will its labels sometimes not be a subsequence of the labels of the tree? Even less formally : is the local order defined by (any) function CL likely to be inconsistent with the global order.

Of course, there could be graphs for which subtrees of certain depths are consistent for particular vertices. By consistent I mean subsequence as [0,2,1] is a subsequence of [0,2,1,3,4].


texts:
Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs.

In other words, there is an  $A\in$ P, such that $L\Delta A$ is vanishing, which means
$$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$$
It also means that on a uniform random input, the polytime algorithm for $A$ will give the correct answer for $L$ with probability approaching 1. Therefore, it makes sense to view $L$ almost easy.

Note that $L\Delta A$ does not have to be sparse. For example, if it has  $2^{n/2}$ $n$-bit strings, then it is still vanishing (at an exponential rate), since $2^{n/2}/2^n=2^{-n/2}$.

It is not hard to (artificially) construct NP-complete problems  that are  P-density-close, according to the above definition. For example, let $L$ be any NP-complete language, and define $L^2=\{xx\,|\, x\in L\}$. Then $L^2$ retains NP-completeness, but has at most $2^{n/2}$ $n$-bit yes-instances. Therefore, the trivial algorithm that answers "no" to every input, will correctly decide $L^2$ on almost all inputs; it will err only on a $\leq 1-2^{-n/2}$ fraction of $n$-bit inputs.

On the other hand, it would be very surprising if  all NP-complete problems are P-density-close. It would mean that, in a sense,  all NP-complete problems are almost easy. This motivates the question:

  Assuming P$\neq$NP, which are some  natural NP-complete problems that are not  P-density-close?


texts: Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

texts:
Crossposted at MathOverflow

A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$. $\mathbf{1}$ is the $m$-dimensional vector with all its coordinates being 1. The nature of the problem I study guarantees that there exists at least a solution $\mathbf{x}\in[0,1]^n$ for this system, which means that the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is nonempty. I want to know what condition guarantees the existence of a 0-1 solution $\mathbf{x}\in\{0,1\}^n$ to this system.
I know that the unimodularity of $A$ is a sufficient condition, which has been useful for me. I also know the TDI condition in integer programming is sufficient, whereas I do not know how to make use of this condition. Both unimodularity and TDI guarantee that all vertices of polyhedron $P$ to be integral, thus I know there is at least a 0-1 solution (vertex), since the polyhedron is nonempty. However, all vertices being integral is more than I want, because I only care about whether there exists an integral vertex. I wonder whether there are more specialized results for this problem.
As pointed out by a helpful comment in MathOverflow, this problem is essentially equivalent to the EXACT SET COVER problem. I would now ask whether there is any condition or structure that guarantees the existence of an exact cover.


texts: Catching the complexity of determining some recursively defined property

texts:
I am currently working on some property defined in the following way. Let $S$ be a set of positive integers. We say that $S$ has the property $P$ iff one of the following two conditions holds.

This set $S$ is a singleton.
For every $x \in \{1,…,\lfloor \frac{|S|}{2} \rfloor\}$, there exists a partition of $S$ into two parts $S_1$ and $S_2$ such that their sizes are $x$ and $|S|-x$, respectively, and they both satisfy the property $P$.

In other words, $S$ has the property $P$ iff it can always be partitioned into two subsets of arbitrary sizes having the property $P$ themselves.
Now, I would like to consider the complexity of the associated decision problem.

P-PROPERTY
Instance: A set $S$ of positive integers.
Question: Does $S$ have the property $P$?

At first sight, such a problem belongs neither to NP nor to co-NP (does it?). Moreover, because of the recursivity, I do not see how this problem could belong to the polynomial hierarchy.
I never saw a problem recursively defined like this one, that is why I am getting some trouble dealing with it. So, is there a way to deal with the complexity of such a problem?
Thanks in advance (and sorry if the answer is obvious :o) )!


texts: What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

texts:
The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic ($p$-isomorphic) to each other. It has been an early attempt (published in 1977) to prove $P\neq NP$. It is still open, and if true, it indeed implies $P\neq NP$.

However, the proof of this  implication is essentially trivial: it is proved by referring to the fact that if $P=NP$, then there are finite $NP$-complete languages, which clearly contradicts to the Isomorphism Conjecture, since a finite language cannot be $p$-isomorphic to SAT.

While the above proof is technically correct, I find it somehow disturbing that to prove the implication one needs a finite  $NP$-complete language.

Question: Let us consider a weaker version of the conjecture, stating only that all infinite $NP$-complete languages are $p$-isomorphic. Would this still imply $P\neq NP$? Is anything known about this weaker version of the conjecture?


texts: Maximizing difference of a submodular and a modular function

texts:
I'm considering a network planning problem which is stated as follows:
From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that
\begin{equation}
f(\mathcal{A}) - \sum_{v_i \in \mathcal{A}} c_i
\end{equation}
is maximized where $f$ is a monotone submodular function and $c_i \ge 0$ is the cost of selecting $v_i$. The problem is an instance of nonomonotone submodular maximization for which a local search heuristic with approximation bound of $\frac{2}{5} - \frac{\epsilon}{n}$ is presented in

Uriel Feige, Vahab S. Mirrokni, Jan Vondrák: "Maximizing Non-Monotone Submodular Functions ", FOCS 2007.

I'm wondering if anyone is aware of a better approximation algorithm for my specific problem?


texts: Existence of $d$-regular expander graph that can be represented as a bipartite graph

texts:
It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander graph that is also a bipartite graph? Thus I have a sparse bipartite graph example that does not have a $o(n)$-vertex/edge separator.

Note that by definition this bipartite graph is not exactly a bipartite expander graph, which only requires that every small subset on the left side of the bipartite graph to have large neighbors on the right.


texts: Handbook of Logic in Computer Science - is it worth it?

texts: I just found the first volume of Handbook of Logic in Computer Science in a library, but unfortunately I won't be able to use it here. It seems like a great resource, but it's insanely expensive to buy - is it worth it? Do you know any good alternatives?


texts:
Reversible computing is a computational model that only allows
thermodynamically reversible operations.  According to Landauer's
principle, which states that erasing a bit of information releases $kT
\ln(2)$ joules of heat, this rules out transition functions that are not
one-to-one (e.g., the Boolean AND and OR operators).  It is well known
that quantum computation is inherently reversible because the allowed
operations in quantum computation are represented by unitary matrices.

This question is about cryptography.  Informally, the notion of "reversibility" seems anathema to the fundamental goals of cryptography, thus suggesting the question: "Does cryptography have an inherent thermodynamic cost?"

I believe that this is a different question than, "Can everything be done in quantum?"

In his lecture notes, Dr. Preskill states,  "There is a general strategy for simulating an irreversible computation on a reversible computer. Each irreversible gate can be simulated by a Toffoli gate by fixing inputs and ignoring outputs.  We accumulate and save all 'garbage' output bits that are needed to reverse the steps of the computation."

This suggests that these reversible quantum simulations of irreversible operations take an input as well as some "scratch" space. Then, the operation generates output along with some "dirty" scratch bits. The operations are all reversible with respect to the output plus garbage bits, but at some point, the garbage bits are "thrown away" and not considered further.

Since cryptography depends on the existence of trapdoor one-way
functions, an alternative statement of the question might be, "Are
there any trapdoor one-way functions that can be implemented using
only reversible logical operations, without additional scratch space?"  If so, is it also possible to COMPUTE an arbitrary trapdoor one-way function using only reversible operations (and no scratch space)?


texts: Reading some papers and articles about PageRank and HITS algorithm, I've figured out that there's a problem called topic drift problem. Googling it, (since I wanted to know more about it) I only found a few articles which has mentioned it but not in detail. I'd like to know is the problem caused by the fact that these algorithms ignore web page content and only conider inlinks (PageRank) and outlinks. But how does it happen? what are researches done by far to avoid this problem?


texts: Nontrivial separation consequences of P!=NP

texts: I am looking for nontrivial examples of complexity class separations that are known to follow from the P!=NP hypothesis. By a "nontrivial example" I mean that it is not just an automatic consequence of an easy containment relationship, such as P!=PSPACE, P!=PH etc. would be.


texts: Is the Complexity Zoo Inclusion Diagram exclusively about classes of decision problems?

texts:
The Complexity Zoo includes the class QNC$^0$, which does not seem to be a class of decision problems. When I chase the references of the link provided, they say

  “To extend this definition from quantum operators to decision problems in the classical sense, we have to choose a measurement protocol, and to what extent we want errors bounded. We will not explore those issues here.”

(https://arxiv.org/abs/quant-ph/9804034)

I guess any attempt at making a decision problem version will lead to QNC$^0$ = NC$^0$ since the output of the circuits will only depend on a constant number of bits of the input.

On the other hand, the zoology introduction states

  Some of the classes in the Zoo are not suitable for this Zoology project because they are not decision classes [...]

Hence the question: Is the Complexity Zoo Active Inclusion Diagram supposed to be about classes of decision problems only?


texts:
I've tried the following LP relaxation of maximum independent set

$$\max \sum_i x_i$$

$$\text{s.t.}\  x_i+x_j\le 1\  \forall (i,j)\in E$$
$$x_i\ge 0$$

I get $1/2$ for every variable for every cubic non-bipartite graph I tried.

Is true for all connected cubic non-bipartite graphs?
Is there LP relaxation which works better for such graphs?

Update 03/05:

Here's the result of clique-based LP relaxation suggested by Nathan

I've summarized experiments here  Interestingly, there seem to be quite a few non-bipartite graphs for which the simplest LP relaxation is integral.


texts: Does polynomially bounded number of witnesses and polynomial time decidability imply polynomial time enumeration?

texts:
Let us assume that $\text{P=NP}$.

Let $\#\Pi$ be a counting problem in $\#\mathrm{P}$ and let $\Pi$, the decision version that asks if the count is positive, be in $\mathrm{P}$.

In general, instances to a problem in $\#\mathrm{P}$ may have a count that is exponentially larger than the input size.  Suppose however that for any instance to $\#\Pi$, the count is bounded by some fixed polynomial of the input size.

Given these assumptions, can we enumerate all witnesses being counted by $\#\Pi$
in polynomial time when $\text{P=NP}$?


texts:
I was reading this paper on effect handlers and got hung up on the phrase 'free model'.

In context:

      [...] From an algebraic point of view, the $x_e$ provide a model for the theory of exceptions on $X + E$, interpreting each operation $raise_e$ by $x_e$. If we write $X + E$ for the free model and $\overline{X + E}$ for the new model on the same carrier set, we see from the above two equations that [...]

I want to reach for something being freely generated from something else, but I'm not sure what (e.g. right after the comment about $x_e$ providing some other model, where're the parts of the 'free model' coming from?).


texts: What methods exist for returning all points within an arbitrary closed shape?

texts:
I have been reading about range search algorithms, but most that I read apply only to a simple range (such as a standard rectangle in 2d).

In a similar fashion, what options exist for range search algorithms across arbitrary closed shapes?  For example, if I had a binary image of a person, and random points across the image, how do I determine which points lie on the portion of the person?


texts:
I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$
maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\Vert^2=1, \hat{x}\in \mathbb{R}^d$.
Without the absolute value inside the summand, the solution is easy, the optimal solution is achived by the unit vector along the vector $\sum_{p\in P}\Vert p\Vert p$. But with the absolute value in the picture, I failed to find a solution. Can this problem be solved by techniques of optimization literature?
Thanks
p.s.
This problem has some superficial similarities with Chebyshev approximation problem:
$minimize \max_i \vert a_i^Tx-b_i\vert$. The aforementioned problem involves $l_\infty$ norm, whereas the original problem deals with $l_1$ norm.


texts: Equality Constraints over Sets with Tree Automata

texts:
Tree Automata can be used to model sets of values of a Herbrand Universe, for example, to model possible values in a functional program.

Systems of subtype constraints over set expressions have decidable satisfiability, but this is EXPTIME complete, and NEXPTIME complete when projections are allowed in expressions. See here and here.

I'm wondering, has the set constraints problem over equality constraints, instead of subset constraints, been studied? Clearly it's not a harder problem than with subsets, but is it easier? Are there simpler solutions than tree Automata for solving such systems?


texts: Ranking the Difficulty of NP Hard Problems in Practice

texts:
This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard problems, this is about ranking the difficulty of the same instances.

There is a lot of bibliography on the effect known as Phase Transition. In particular for the case of random 3-SAT formulae in Conjunctive Normal Form (CNF), it is known that there is a value R of the ratio of clauses to variables such that for all r < R the formula can be satisfied with high probability and for r > R the formula is unsatisfiable with high probability. The Phase Transition effect happens near R and it has the remarkable effect that solving the satisfiability problem for those formulas is extremely hard in practice.

Since for proving NP hardness of a given problem it is needed to show that there is a polynomial time Turing-reduction to it of an NP-complete problem and that problems that are NP-complete can be transformed in polynomial time among them, then the following question naturally arises:

Is it possible to rank the difficulty of NP hard problems in practice using the Phase Transition of 3-SAT CNF as an indicator? The intuition is that one problem P1 can be expected to be harder than P2 if its 3-SAT encoding is nearer R (which is known to be near 4.2). Note that this idea does not necessarily bound each particular instance to a particular difficulty, it just ranks them.

There are a number of counter arguments, among them:

The Phase Transition of 3-SAT CNF formula applies to random formulae. However, a particular instance in a different problem has some structure that might be exploited by solvers for that problem ---this was already pointed out by Peter Shor in the aforementioned question.
It might be the case that the particular encoding used for transforming the particular instances in our problem to 3-SAT plays a crucial role in the ratio of clauses to variables leading to misleading values, hence misclassifications ---this concern is raised by Kaveh in the comments to this question.
Serge (according to my understanding from his comment to this question) raises the issue that one might artificially complicate the original NP hard problem so that it results in a 3CNF formula that alters the ratio of clauses to variables while preserving the satisfiability.

As for 1, all problems might share the same class of regularity so that ranking problems (instead of characterizing the difficulty) might apply; as for 2, there are encodings in particular problems which are known to be non-redundant w.r.t the Unit Propagation rule so that those should be preferred and maybe they avoid those misclassifications. An example is Sideris et al., 2010 for the case of Propositional Planning. As for 3, Cheeseman et al., 1991 already considered the issue of whether mappings between problems preserve or not the phase transition effect and their preliminary experiments seem to support their conjecture, provided that one reduces the original NP problem and even that "can be further reduced by applying resolution to the clauses".

Do this all make sense to you? are you aware of any bibliographical references about this? Any guidance would be largely acknowledged!


texts:
Is there a notion of computability on sets other than the natural numbers?  For the sake of argument, let's say on sets $S$ that biject with $\mathbb{N}$.
It's tempting to say "yes, they are those functions of the form $g \circ f \circ g^{-1}$ where $g$ is any bijection $\mathbb{N} \to S$ and $f$ is any computable function $\mathbb{N} \to \mathbb{N}$".  I'm cautious of this definition for two reasons.

It privileges $\mathbb{N}$ over other countable sets.  Why is $\mathbb{N}$ special when it comes to defining computability?  I'd like a "coordinate free" definition of computability without reference to any privileged set in the same way I might like a "coordinate free" definition of a linear algebra concept without reference to any privileged basis.

It raises questions about the choice of $g$.  I suspect it may be possible to find contradictions by particularly pathological choices of $S$ and $g$.  For example if I choose $S = \mathbb{N}$ and $g$ some non-computable bijection is it really the case that $g \circ f \circ g^{-1}$ is computable for all computable $f$?
It's tempting to require in the definition that $g$ be computable but unfortunately that's begging the question.

Is there some general way of describing computability on countable sets other than $\mathbb{N}$?


texts: What is the complexity of pallet loading for identical non-rectangular objects?

texts:
In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap.  This problem is a special case of the cutting stock problem and is known to be NP-complete.  It is NP-complete even for the special case in which the objects are identical squares [Fowler, Paterson, Tanimoto 1981].

Is pallet loading also NP-complete when the objects are non-rectangular? In particular, I am interested the case in which the objects are octagons.


texts: What is the complexity of chordalization?

texts:
A graph $G=(V,E)$ is a chordal graph, if it does not contain an induced
cycle of length at least four. We say a graph $H$ is a chordalization of graph
$G$, if $H$ contains $G$ as a subgraph, and $H$ is chordal.

$Q_1$: Find minimum number of edges whose addition to a given graph makes the graph a chordal graph.

According to this, $Q_1$ is NP-hard.

$Q_2$: Find a chordalization that does not introduce new $K_4$?

What is the complexity of $Q_2$? Is $Q_2$ harder than $Q_1$?

{
Remark: After Florent comment, I changed $Q_1$ from the following:

$Q_1$ in first version of my post: What is the complexity of giving an arbitrary chordalization of input graph?
}


texts: Separation oracle for hitting all small cut on a graph?

texts:
We are given as input an undirected graph $G=(V,E)$, weights $w_e \ge 0$ for all $e\in E$ and an positive integer $k$. We aim to select a set of edges with the minimum weight, such that the cut set of every small cut are hitted. A cut is defined as a subset of $V$. A small cut is defined as a cut whose cut set contains at most $k$ edges. The cut set of a cut $S\subseteq V$, denoted by $\delta(S)$, is the set of edges having exactly one endpoint in $S$.

Using $x_e$ to denote whether edge $e$ is chosen($x_e=1$) or not($x_e=0$), this problem can be formulated as an integer programming:

$$\begin{array}{rcl}
&\min \sum_{e\in E} x_e w_e\\ \\
&\sum_{e\in \delta(S)} x_e \ge 1 & \forall S\subseteq V \text{ s.t. } \delta(S)\le k \\
&x_e\in \{0,1\} \quad & \forall e\in E
\end{array}$$

Considering its similarity to set cover porblem, I try designing approximation algorithms by rounding the optimal solution for the linear programming relaxation of above IP. However, there is, exponentially many constraints. In order to slove the LP relaxation by ellipsoid method, a separation oracle is needed. I try to design a separation oracle by the max-flow min-cut theorem but failed.

Is it possible to design a separation oracle for the LP relaxation by the max-flow min-cut theorem or any other way? Or any suggestions on designing approximation algorithms for this problem?


texts: Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

texts:
I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that

$G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$.
$G$ has no left recursion; that is, we can't derive a sentential form like $A\alpha$ from a non-terminal $A$.
$G$ has no left factors; that is, there are no two rules of the form $A\to a\alpha$ and $A\to a\beta$ in $G$, where $\alpha,\beta$ are strings of terminals and/or non-terminals.

I am wondering whether these conditions are sufficient for the grammar to be in $LL(1)$.
If not, is there a grammar satisfying these conditions and yet is not in $LL(1)$?
If the answer is yes, this would imply that we can eliminate left recursion and left factors from any unambiguous grammars to obtain equivalent $LL(1)$ grammars.

The textbook Compilers: Principles, Techniques and Tools by Aho, Lam, Sethi and Jeffrey says that this is not the case.
But, the example grammar they give (Example 4.33, pp. 225, Second Edition) is ambiguous, even though it has no left factors or left recursion.


texts: Total time complexity of convex hull problem

texts:
The convex hull problem is to compute the facets of the convex hull of finitely many given points in $\mathbb{R}^d.$ By cone polarity it is equivalent to computing the vertices and rays of a polyhedron which is given in terms of finitely many linear equations and inequalities.

One way to measure the complexity of an enumeration algorithm is the total time used to compute all solutions. An output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. The number of solutions may be exponential in the size of the input, therefore a problem is tractable and said to be output polynomial when it can be solved in polynomial time in the size of the input and output.

The precise complexity status of the convex hull problem is unsettled: it is not known whether or not there exists an algorithm whose complexity is bounded by a polynomial in the combined size of the input and the output[1].

Unlike the well known convex hull algorithms, there is "the ultimate convex hull algorithm" which is an optimal output-sensitive algorithm by Kirkpatrick and Seidel in 1986 and a simpler algorithm was developed by Chan in 1996 [2].

Are there any known related results about the complexity of the convex hull problem? Even it is not output-sensitive. What caused the difficulty of this problem?

[1] Assarf, Benjamin, et al. "Computing convex hulls and counting integer points with polymake." Mathematical Programming Computation (2016): 1-38.

[2] https://en.wikipedia.org/wiki/Convex_hull_algorithms


texts: Fractional chromatic number of Johnson graphs

texts:
Johnson graphs have a dual like construction to Kneser graphs in the sense that in Kneser we encode non-intersecting k-sets by joining vertices that represent the sets while in Johnson graphs we encode intersecting k-1-sets.

I have a few questions on Johnson graphs:

What is the fractional chromatic number $\chi_f(J(n,2))$ of Johnson graph $J(n,2)$ which is the complement of Kneser graph $K(n,2)$?

In general what is $\chi_f(J(n,k))$?

It is known that we have a graph homomorphism $G\rightarrow K(n,m)$ if and only if $\chi_f(G)=\frac{m}{n}$ for any graph $G$. Is there a similar relation for Johnson graphs(atleast for $J(n,2)$)?

In general do we have $G\leftrightarrow H\iff\chi_f(G)=\chi_f(H)$? (where $\leftrightarrow$ implies homomorphisms bothways?)


texts: Relation between hardness of recognition of a graph class and forbidden subgraph characterization

texts:
I'm considering graph classes that can be characterized by forbidden subgraphs.

If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm (one can just use brute force). But an infinite family of forbidden subgraphs does not imply hardness: there are some classes with infinite list of forbidden subgraphs such that the recognition can also be tested in polynomial time. Chordal and Perfect graphs are examples but, in those cases, there is a "nice" structure on the forbidden family.

Is there any know relation between the hardness of the recognition of a class and the "bad behavior" of the forbidden family? Such a relation should exist? This "bad behavior" has been formalized somewhere?


texts: an axiomatic framework for clustering by jon kleinberg may have a problem?

texts:
In the paper An Impossibility Theorem for Clustering, Jon Kleinberg introduced an axiomatic framework for clustering and showed that his set of axioms are inconsistent. One of the axioms is the Richness Axiom: any partition of the input can be produced by some distance function.

My question is:

  Isn't the richness axiom unnatural?

The axiom implies that both trivial partitions: the one which puts all elements in the same cluster, and the one in which each cluster is a singleton, are both considered as valid clusterings. However, this is counter-intuitive in real life situations. In many (i guess most) real life situations we wouldn't have both these clusterings considered as valid simultaneously. so i guess the richness axiom could be modified. do we truly need  all partitions to be considered as valid clusterings?


texts: Where do sublinear time algorithms fit in the picture of complexity theory?

texts:
I know that there are complexity classes that are "below" P like L or NL and stuff like that. But I was curious to know where sub linear time algorithms fitted in this picture and maybe how they were related to the P vs NP problem or if they had their own version of something similar. I am aware that this question might lead to a list of open problem in sublinear time algorithms or something similar, which is a fine answer to my question. I am also curious to know what we know about this theory and what we don't know or what are open problems to tackle.

[I tried adding the tag sublinear time algorithms but I am not sure if it exists. Feel free to add a tag that might help]


texts:
I study pure greedy algorithms in different bases.  I am interested in the following question:  Is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that
$$
    \|f-G_m(f,D)\| > Cm^{-1/2} |f|_H
$$
for every constant $C$?  In other words, is there a Riesz basis that yields a convergence rate bigger than $-1/2$?

I know that there are such dictionaries whose convergence rate is larger than $-1/2$ (even $-0.27$) but I cannot construct such a Riesz basis.

Note: A Pure Greedy Algorithm is defined inductively by
\begin{align*}
  G_0(f) & = 0 \\
  G_m(f) & = G_{m-1}(f)+G(f-G_{m-1}(f))
\end{align*}
where $G(f)=\langle f,g\rangle g$  and $g=g(f)$ is an element from $D$ that maximizes $\left|\langle f,g\rangle\right|$.

Here are some ideas that might be helpful.  It is known that if
$$
    \sup_{g\in D} \sum_{g'\in D,~ g'\ne g} \left|\langle g,g'\rangle\right| < 1/3,
$$
then the convergence rate is less than $-1/2$.  That is why I took Riesz basis for which that supremum is equal to 1:
$$
    D=(f_j), ~\text{where}~ f_j=e_j+\frac{1}{2}e_{j+1}.
$$
Now I want to find $f$. But I can not :(

Some useful information can be found in this paper by DeVore and Temlyakov and this paper by Temlyakov.


texts: Papers on relation between computational complexity and algebraic geometry/topology?

texts:
I was wondering what papers I should read to understand this question

  A unexpected connection to other areas of mathematics such as algebraic geometry or higher cohomology. Perhaps even an area of mathematics not yet developed. Perhaps someone will develop a whole new direction for mathematics in order to handle the P versus NP question.
  -From Fortnow 2002

Another phrasing of the question would be "What papers should I read to create a connection from computational complexity to algebraic geometry / topology?"

I have looked at Geometric Complexity Theory already . Also papers in Topological Quantum Computation which I have read enough papers that I am already familiar with the field. Am I missing anything?


texts:
The following quote describes an algorithm invented by Feynman to compute the logarithm of a fractional number (presumably a dyadic one).

  Consider the problem of finding the logarithm of a fractional number between 1.0 and 2.0 (the algorithm can be generalized without too much difficulty). Feynman observed that any such number can be uniquely represented as a product of numbers of the form (1 + 2^{-k}), where k is an integer. Testing each of these factors in a binary number representation is simply a matter of a shift and a subtraction.

Unfortunately, there are many numbers that cannot be represented as advertised above, for example 7/4, 11/8.
There must be something wrong with the quote.

What was the algorithm proposed by Feynman ?


texts: How to format author information in research papers?

texts: Is there any standard style for adding author information in research papers? I see different papers use different styles. Some have affiliation and contact address only. Some have affiliation, email, contact address in full. Some include designation also. So what is the best style one should follow? I am preparing a paper for a Springer Conference.


texts: are there fixed context sensitive grammars which are PSPACE complete?

texts:
wikipedia entry  says without reference that

"There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."

This is stronger than saying that CSG is PSPACE-complete.
But is this proved? where are the references?


texts:
Are there results/techniques pertaining to the analysis of squares of random matrices ?

More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with equal probability. Now if we want to analyze for any $u,v \in \{-1,1\}^n$, we can make a case for concentration of the value of $u^TAv$ using chernoff bound arguements. However suppose now we want to analyze the value of $u^TA^2v$. This time due to a lot of dependencies among the variables a chernoff type arguement becomes difficult or at least I cannot see it straightaway. Could someone point me to an analysis for this scenario ?


texts: Precise definition for cryptographic protocol?

texts:
Is there some precise definition of cryptographic protocol?
I'm asking because I have tried a few good books and they don't seem to define it (Douglas Stinson, Wenbo Mao, Trappe/Washington). The lecture notes by Goldwasser and Bellare come close, but don't really define protocols (and leave key distribution out of the protocols chapter, for example).

I've seen people include key management in protocols and others keeping it out; the same for secret sharing and some other topics.

So, does that mean there no widely-accepted definition for cryptographic protocols?

Edit: I'm not sure I was clear enough when I originally posted the question -- I wanted to know what usually is considered a "protocol" in cryptography and what is not (and not how I'd go about defining some particular protocol)


texts: Algorithm to find s-t min paths in a weighted graph

texts:
Given a directed graph with $n$ vertices with non-negative edge weights, I would like to find first $n^2$, $s$-$t$ minpaths with minimum sum of non-negative weights. By using Dijkstras shortest path algorithm I found out the first minpath. In order to get next minpath I have replaced edges in first minpath with infinity. By following this procedure I am missing out many minpaths whose sum of weights are much smaller than what I am getting by following above procedure.

Can some one suggest me a good procedure to list first $n^2$ minpaths.

Thank you.


texts: Using martingale arguments to prove convergence of iterative algorithms

texts:
Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?

The examples I know of can only go so far as to show that there exists a ball of finite radius around the global minimum s.t the stochastic process is exponentially (in some parameter which scales with the radius of the ball) is suppressed to be outside this ball.

Unless we can get lucky that this ball is of radius $\epsilon$ such ``escape time" arguments are weaker than convergence. Are there examples where this style of argument actually goes all the way?


texts:
My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively enumerable functions classic (among others). Specifically,is an interactive proof system characterisation known for recursive and recursively enumerable functions?

I only know that IP = PSPACE and that MIP = NEXPTIME. By `know'  means I understand the definitions of objects on both sides of the equality and possibly understand the equality.

My second question is whether there is a graphical summary of different types of interactive proof systems and the complexity classes they characterise.

Specifically, I would like a reference to a figure similar to Immerman's picture of description complexity characterisations.


texts:
I am working on a text processer which gives out similarities between a set of strings. After weighted LCS, Levenshtein distance and double metaphone matching, I get buckets of strings such as

Bucket for string $i \rightarrow [s, k, m]$
Bucket for string $j \rightarrow [i, s, k]$

This effectively implies that $i,j,s,k,m$ belong to the same cluster.

One of the ways I could do this is to build a connectivity graph and cluster all the connected components.

The other way is to iteratively check for the matches.

Could somebody help me do it better.


texts: Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

texts:
I want to have an overview of all the meaningful equivalence relations defined on $X^{\ast}$, in particular when the languages in question are regular. They typically arise in connection with the minimization of automata. Further I want to know all the relations among them. Below I write what I know, I encourage everyone to add useful facts to this list, give other equivalence relations and how they relate to the given ones!?

Common equivalence relations on $X^{\ast}$ are
\begin{align*}
 u \equiv_L v & :\Leftrightarrow
  \forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L \\
 u \equiv_R v & :\Leftrightarrow
  \forall w \in X^{\ast} : wu \in L \leftrightarrow wv \in L \\
 u \equiv_S v & :\Leftrightarrow
  \forall w_1, w_2 \in X^{\ast} : w_1uw_2 \in L \leftrightarrow w_1vw_2 \in L
\end{align*}
If we have some deterministic and complete automaton $\mathcal A = (X,Q,\delta,q_0,F)$ with $L = L(\mathcal A)$, then every $u \in X^{\ast}$
corresponds to a function $\varphi_u : Q \to Q$. Then we can define
$$
 u \equiv_A v :\Leftrightarrow \delta(q_0, u) = \delta(q_0,v) \Leftrightarrow \varphi_u(q_0) = \varphi_v(q_0).
$$
Also for states $q, q' \in Q$ we could define
$$
 q \equiv q' :\Leftrightarrow \forall u \in X^{\ast} : \delta(q, u) = \delta(q',u) \Leftrightarrow \varphi_u(q) = \varphi_v(q')
$$
and by incorporating the final states (and thereby fitting it more to the conrete language $L$) we could define
$$
 q \equiv^L q' :\Leftrightarrow \forall u \in X^{\ast} : \delta(q, u) \in F \leftrightarrow \delta(q', u) \in F.
$$
And if we have some recognizing monoid $M$ with homomorphism $\varphi : X^{\ast} \to M$ we could define
$$
 u \equiv_h v :\Leftrightarrow h(u) = h(v).
$$
We have (the automaton is arbitrary)
\begin{align*}
 u \equiv_L v & \Leftrightarrow \delta(q_0, u) \equiv^L \delta(q_0,v) \\
 u \equiv_R v & \Leftrightarrow \forall q \in Q : \delta(q, u) \in F \leftrightarrow \delta(q, v) \in F \\
 u \equiv_S v & \Leftrightarrow \forall q \in Q : \delta(q, u) \equiv^L \delta(q,v) \\
 u \equiv_h v & \Rightarrow u \equiv_S v \\
 u \equiv_S v & \Rightarrow u \equiv_L v \land u \equiv_R v \\
 u \equiv_A v & \Rightarrow u \equiv_L v \\
 \varphi_u = \varphi_v & \Rightarrow u \equiv_S v \\
 u \equiv_S v & \Leftrightarrow \forall q \in Q : \varphi_u(q) \in F \leftrightarrow \varphi_v(q) \in F
\end{align*}
And we have that the syntactic monoid is precisely the transformation monoid of the minimal automaton (which could be constructed with $\equiv_L$). Also the above notions could be described in terms of language quotients $u^{-1}L := \{ w : uw \in L \}, Lu^{-1} := \{ w : wu \in L \}$ (and the minimal automaton could also be constructed with the quotients $u^{-1}L$) or the sets $L_q(\mathcal A) := (X,Q,\delta,q,F)$ (i.e. the language accepted if $\mathcal A$ is started at $q$).


texts:
I'm looking for an algorithm to merge two binary search trees of arbitrary size and range.  The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into an arbitrary external node in the other tree.  However, the worst case running time for this type of algorithm seems to be on the order of O(n+m) where n and m are the size of each tree respectively.

However, I've been told that this could be done in O(h), where h is the height of the tree with the larger height.  And I'm completely lost on how this is possible.  I've tried experimenting with rotating one the trees first, but rotating a tree into a spine is already O(h).


texts: Complexity of the recovery of an adjacency matrix from its square

texts:
I am interested in the following problem:  Given an $n\times n$ matrix, is there an undirected graph on $n$ vertices whose adjacency matrix squared is that matrix?

Is the computational complexity of this problem known?

Remarks:

Of course this can also be phrased as a search problem, where you are given the matrix $A^2$ for $A$ an adjacency matrix of an undirected graph and the problem is to find any adjacency matrix (of an undirected graph) $B$ such that $B^2 = A^2$.
Motwani and Sudan (Computing roots of graphs is hard, 1994) and
Kutz (The complexity of Boolean matrix root computation, 2004) show similar but distinct problems from this one are NP-hard - they consider only the square of adjacency matrices under Boolean matrix multiplication.


texts: Social choice theory, preference aggregation data sets

texts: I do computational research on preference aggregation. I am quite interested in Kemeny Optimal Aggregation. However I do not find much useful data for preference aggregation in context of social science where I can test my concepts and algorithms. I am not merely interested in meta-search stuffs. I am looking for some pure committee decision, voting type of social data. Any help will be highly appreciated.


texts: Lower bound method for ordered binary decision diagrams

texts:
This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?:

If you want to prove some exponential lower bounds for some function represented by an ordered binary decision diagram (OBDD) you have to prove this lower bound for every variable ordering (a variable ordering is a permutation on the input variables). Intuitively it is often easy to prove that for a special variable ordering the OBDD size is exponential in the number of input variables. It doesn't need to be one special variable ordering but some variable ordering with some property $P$.

According to my answer to the question mentioned above you can show that there are several variable orderings with polynomial size OBDD if there exists at least one. This contains the statement that you can get several variable orderings from another variable ordering with some blow up in the OBDD size.

I think you can improve this blow up and so the number of variable orderings you can get depending on the function. If you can prove that you can transform every variable ordering to one ordering with property $P$ with a "low" blow up and show that every OBDD with a variable ordering with property $P$ for this function has exponential size you have this lower bound for every variable ordering.

Is this kind of lower bound technique known? Does it seem to be useful if it is not known?


texts: Information complexity of query algorithms?

texts:
Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems.

Is there an analogue of information complexity for query complexity? There are many parallels between query complexity and communication complexity; oftentimes (but not always!) a lower bound in one model gets translated to a lower bound in the other model. Sometimes this translation is quite nontrivial.

Is there a notion of information complexity that is useful for lower bounding the query complexity of problems?

A first pass seems to indicate that information complexity is not very useful; for example, the query complexity of computing the OR of $N$ bits is $\Omega(N)$ for randomized algorithms and $\Omega(\sqrt{N})$ for quantum algorithms, whereas the most straightforward adaption of the notion of information complexity indicates that the information learned by any query algorithm is at most $O(\log N)$ (because the algorithm stops when it sees the first $1$ in the input).


texts: How to analyze a randomized recursive algorithm?

texts:
Consider the following algorithm, where $c$ is a fixed constant.

void partition(A[1..m], B[1..n])
{
   if m=1 or n=1
      return

   k = random(min(c,m,n));
   partition A into k sublists Asub[1..k] at k-1 distinct random indices
   partition B into k sublists Bsub[1..k] at k-1 distinct random indices

   for i = 1 to k
     for j = 1 to k
        partition(Asub[i], Bsub[j])

   Do something that takes O(n+m) time.
}

What is the expected running time of this algorithm?  The running time appears to be $O(mn)$, but I can't find the proof for this.

If we instead partitioned the input lists into $k$ different parts of equal length, we would have the recurrence $T(n,m) = k^2\,T(n/k,m/k) + O(n+m)$ with base case $T(1,n) = T(m,1) = O(1)$; it is not hard to prove that $T(n,m) = O(mn)$.  But the algorithm partitions the input into a  random number of parts with random sizes.  (As usual, "random" is shorthand for "uniformly at random".)  How does one analyze such an algorithm?


texts: Scaling Algorithms for the Minimum Spanning Tree Problem?

texts:
In his paper "Scaling Algorithms for Network Problems", Harold Gabow details several algorithms for graph problems that work using scaling, iteratively refining a candidate answer by beginning with a low-precision approximation to the original problem and repeatedly increasing the precision.  One of the problems that he considers is the single-source shortest paths problem with nonnegative weights, giving an algorithm that works through iterated applications of Dijkstra's algorithm in a modified graph.

I have seen this technique used in other places (min-cost max-flow, sorting, etc.), but one combinatorial problem that I have not seen solved via scaling is the minimum spanning tree problem.  Given the relation between Dijkstra's algorithm and Prim's algorithm, combined with the paper's discussion of a scaling implementation of Dijkstra's algorithm, it seems like there may be an efficient algorithm of this sort.

Has this problem been studied in any depth?  If so, are there any resources or papers I should take a look at?  If not, does anyone have any suggestions for how an efficient algorithm of this sort could be attempted?

Thanks!


texts: Reynolds: "the basic laws of variable binding"

texts:
I recently came across this passage in an article by John Reynolds (emphasis added):

  ...from designers innocent of the principles of programming language design, we have been given a nearly endless succession of “input formats” that seem to be designed to encourage error. (Flawed macro facilities that violate the basic laws of variable binding are particularly prominent examples.)

I was happy to come across the phrase in italics because for some time now I've been aware of having precisely this deficiency, but not knowing what to call it, and therefore failing repeatedly at finding a way to remedy it.

Can someone point me to where I can learn about these "basic laws of variable binding"?


texts: What's complexity of this set problem which looks like "Linear Programming"?

texts:
I came up with a problem below, which looks like a linear programming problem:

  Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of :
  $$
\forall i=1, 2, 3,...,n\space\space \left | S_{i} \right |=k;\\
\left | S_{j_{11}}\bigcup S_{j_{12}} \right |\leqslant k_{1};\\
\left | S_{j_{21}}\bigcup S_{j_{22}} \right |\leqslant k_{2};\\
...\\
\left | S_{j_{m1}}\bigcup S_{j_{m2}} \right |\leqslant k_{m}.\\
$$
  $j_{11},j_{21},...,j_{m1},j_{12},j_{22},...,j_{m2}$ are integers between $1$ and $n$. $k,k_{1},k_{2},...,k_{m}$ are constant positive integers.
  The questions is:
  For a positive integer $q$,Do such $S_{1}, S_{2},..., S_{n}$ exsit, such that $\left| \bigcup_{i}^{n}S_{i} \right |=q$?

I came up with this problem in order to judge complexity of another graph problem. But I failed to find any relative research. So has complexity of this kind of problem been studied? Is this problem NP-Complete or just P? How to judge this problem? Thanks.
By the way, what if $k=2,k_{1}=k_{2}=...=k_{m}=3$?


texts: Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)

texts:
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.

First, I will define a few relevant terms. These terms come up when we study the process of Gaussian elimination graph theoretically. Say, we have got a matrix $M$. With this matrix, we associate a directed graph $G_M = (V,E)$ where we have $V = \{v_1, v_2, \ldots, v_n\}$ where $v_i$ corresponds to row i and variable i and $(v_i,v_j) \in E$ iff $M_{ij} \neq 0$ and $i \neq j$.

The elimination process may create some new non-zero elements  in locations in $M$ which contained zeroes to begin with; the edges corresponding to these elements are called fill-in. In graph-theoretic terms, removing a vertex $v$ calls for addition of the following set $S_v$ of edges. $S_v = \{(u,w) | (u,v) \in E, (v,w) \in E, (u,w) \not\in E\}$

In order to make the elimination process efficient, we can target minimizing fill-in. By a result of Yannakakis, we know that fill-in minimization is a NP-Complete problem.

It is easy to see that the value of fill-in depends on the ordering of vertices which leads to definition of a related parameter. An elimination ordering is a bijection $\mathbf{\alpha \colon \{1,2,\ldots, n\} \to V}$ and $\mathbf{G_{\alpha} = (V,E, \alpha)}$ is an ordered graph. Basically, this represents the order in which the vertices will be picked for deletion in the corresponding directed graph representation. Corresponding to different orderings, we get different values of fill-ins. The ordering which minimizes the fill-in size is called the minimum elimination ordering. And again we (of course) have that computing the minimum elimination ordering is NP-Complete.

My question

  What is the best known approximation algorithm for minimizing fill-in?

Also, I would like to know what is the best known "approximation algorithm to minimize elimination ordering". By approximating the minimum elimination ordering, I mean a poly-time algorithm that outputs an elimination ordering which best approximates the minimum fill-in value.

Thanks for your time
Best Regards
-Akash


texts: Direct Diffie-Hellman by Shor's algorithm

texts:
Shor's algorithm appears to be capable of finding discrete logarithm even if the modulus is composite. Does the algorithm implicitly compute the Carmichael Lambda which goes in the exponent or somehow it does not need this information and if not can the algorithm be utilized to break Diffie-Hellman directly without computing the discrete logarithm?
Only one question now and very focused.


texts:
Let $L$ be a programming language, and $\cong$ a notion of equality of $L$-programs (in general $\cong$ will be undecidable).  Let $syntax(n)$ be the number  of $L$-programs of size $n$ (for some reasonable notion of program  size), and $semantics(n)$ denotes the number of $\cong$-equivalence  classes of $L$-programs of size $n$. Now define
$$  density(n) = semantics(n)\ /\ syntax(n)$$
So $density(n)$ tells us how many really distinct programs we can
write of size $n$. What is known about the limit:
$$   \lim_{n \rightarrow \infty} density(n)?$$
I conjecture that $\lim_{n \rightarrow \infty} density(n) = 0$ for
reasonable choices of $L$ and $\cong$, since the larger programs are
allowed to be, the more room for redundancies like $M+N \cong N+M$.
Question. What is related work this direction?


texts: Turing degree of Solomonoff semi-measure

texts:
We define the Solomonoff semi-measure $m$ on finite strings $x$ by

$$m(x) = \sum_{p: U(p) = x} 2^{-l(p)},$$

where $U$ is a universal prefix Turing machine, $U(p) = x$ means $U$ outputs $x$ on input $p$, and $l(p)$ is the length of $p$.
What is the Turing degree of (computing the first $n$ digits of) $m(x)$?


texts: $\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?

texts:
I’ve been reading up on the connection between first order logic and small circuit complexity classes, and specifically Barrington, Immerman, and Straubing’s paper “On Uniformity Within $\mathit{NC}^1$”, where they prove $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$ = $\mathit{FO}[+,\times]$. However, it seems to me that $\mathit{FO}[+,\times]$ is much more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$. For example, the following sentence:
$$
\forall x \,(Qx \lor \exists a \exists b \,(a\times b = x \land a\ne1 \land b\ne1))
$$
can be implemented as a circuit as an $\mathrm{AND}$ gate that is only connected to prime-numbered inputs (including input 1), and so defines the language $\{1, 11, 110, 1100, 11001, 110010\}$. However, $\mathit{DLOGTIME}$ only has time linear in the size of the gate indices to determine whether a connection exists between two gates. It seems to me that to recognize the connectivity language in linear time, one would have to be able to tell whether or not the input gate index was prime, and $\mathrm{PRIMES}$, although in $P$, is not computable in linear time. How can this language be $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$ then?


texts: Beigel-Tarui transformation of ACC cricuits

texts:
I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book.
http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf
One of the key lemmas is a transformation from $ACC^{0}$ circuits to multilinear polynomials over the integers with polylogarithmic degree and quasipolynomial coefficients, or equivalently, the circuit class $SYM^{+}$, which is the class of depth two circuits with quasipolynomially many AND gates at its bottom level with polylogarithmic fan-in, and a symmetric gate at the top level.

In the appendix to the textbook, this transformation has three steps, assuming that the gate set consists of OR, mod $2$, mod $3$, and the constant $1$. The first step is to reduce the fan-in of the OR gates to polylogarithmic order.

Using the Valiant–Vazirani Isolation Lemma, the authors obtain that given an OR gate over $2^{k}$ inputs of the form $OR (x_{1},...,x_{2^{k}})$, , if we pick $h$ to be a pairwise independent hash function, from $[2^{k}]$ to $\{  0,1 \}$, then for any nonzero $x \in \{0,1\}^{2^{k}}$,with probability at least $1/(10k)$ it will hold that $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2$.

  Isn't the probability of $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2$ at least $1/2$ ? It seems that $1/10k$ is a weak lower bound.

The second step is moving to arithmetic gates and pushing multiplications down. In this step, we will transform Boolean circuits with a given binary input string to an arithmetic circuit with an integer input.

Here they note that $OR(x_{1},...,x_{k})$ is replaced with $1-x_{1}x_{2}\cdots x_{k}$, and $MOD_{p}(x_{1},...,x_{k})$ is replaced with $(\Sigma_{i=1,...,k}  x_{i})^{p-1}$ using Fermat's Little Theorem.

  Why does this replacement give an equivalent $SYM^{+}$ circuit ?


texts: What are contravariant tensors of type m choose 0

texts:
I am not sure if the following question falls within the scope of this site; if it does not, I will request the moderators to take appropriate action

I have been going through Jin-Yi Cai's expository paper on Holographic algorithms.

I had a question. Immediately after introducing Grassman-Plucker Identities for Pfaffians and the definitions for matchgates, recognizers and generators, Cai introduces signature tensor for matchgates.

My question arises from the following statement.

He states that a generator $\Gamma$ with $m$ output nodes is assigned a contravariant tensor $\mathbf{G} \in V_0^m$ of type $\binom {m} {0}$.

I looked up contravariant tensors on wikipedia but did not find any reference to the type of contravariant tensors which Cai talks about. Maybe I am not searching properly, but I was unable to find a proper reference which defines what I am looking for.

I would be glad if anyone could help me with this.

Thanks
-Akash


texts:
In High School Computing I was taught the Structured Program Theorem - that you could implement any mathematical operation using:

Sequence
Selection
Iteration

After completing a Computer Science degree - we can express what is required for any computable function more formally with M-recursive functions:

The constant $0$ function
The successor function
Selecting parameters
Function composition
Primitive Recursion
The $\mu$-operator (look for the smallest $x$ such that...)

This being the minimal set of axioms. Translating this to code we get:

The constant 0
Incrementation _ + 1
Variable access x
Program/statement concatenation _; _
Countdown loops for ( x to 0 ) do _ end
While loops while ( x != 0 ) do _ end

But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?

(Noting of course that

Lambda Calculus is a subset of Term rewriting,
that Mathematica chose Term-writing over Lambda Calculus as its foundation,
and recent work in Univalent Foundations. )

My question is: Can all mathematical operations be encoded with a Turing Complete language?


texts: Deciding if a wildcard string is completely matched by another wildcard string in a set

texts:
Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the same length. These are standard UNIX wildcards; 10??1 matches 10011, 10111, etc -- a ? matches a 1 or a 0 in that position. If $v$ and $w$ are wildcard strings, then we write $v \leq w$ if every string matched by $v$ is also matched by $w$.

The problems: given a set $S$ of wildcard strings, and a query $v$ (also a wildcard string), does there exist a $w \in S$ such that $v \leq w$? And if not, can we add $v$ to $S$ efficiently?

Here's the obvious $O(\frac{k}{m}n)$ solution (where $k$ is the size of the strings, $m$ is the word size of RAM (usually 32 or 64)): go through each element of the list and test the condition (which can be done in 2 or 3 operations using bit-twiddling). Also test if $v \geq w$ holds for any item $w$ while we're scanning. If $v$ fails our test, then add $v$ to the set, and remove the $w$'s we marked.

But that's not fast enough. It'd be really cool if there was a $O(\log n)$ solution, or, in a perfect world, complexity similar to a radix tree ($O(k)$). It's also OK for the queries to be approximately correct: that is, if $v \leq w$, then return yes or no; but if the condition doesn't hold definitely return no.

Although this doesn't help the worst case complexity, you can assume that all elements in $S$ are bounded by a wildcard string; that is, there exists some $v$ such that for all $w \in S$, $v \geq w$.

Ideas I've tried

Wildcard strings form a join-semilattice. We could have an n-ary tree that holds wildcard strings; the leaves would be wildcard strings, and the branches would represent the join of all of the children. If the query and the join are incomparable, then we don't have to waste time trying to compare with all of the children of that branch. Furthermore, if we make an update, and the update happens to be greater than a join, we can simply delete the whole branch. Unfortunately, this is still $O(n)$ in the worst case, and we don't always find the "best" joins to make when scanning through the tree to add elements.
One could form a radix trie of $S$. We know that $S$ is bounded by some wildcard string; assume that it is ?0?0. Then all of the branches of the trie only have to be on the 1st and 3rd bits of the strings. If the current bit we are branching on of the query is a 1, we have to check the ? and the 1 branches; if it is 0, we check the ? and the 0 branches; if it is ?, we only check the ? branch. Because we have to potentially take multiple branches, this doesn't seem very good (it is hard to update the trie for the same reason). Since matching is a very very quick operation, it hurts in comparison to the naive strategy to do a lot of traversing in a tree (following a bunch of pointers is much more expensive than doing some ORs and ANDs).

Related work

In the networking community, this problem manifests as "packet classification", here is a good survey of the algorithms and data structures known. Unfortunately, the assumption is almost always made that the wildcard strings only match prefixes, and the query is a tuple of such strings. Of course, we can always convert a general wildcard string to meet these criteria: 1?00?1?? is (1, ?, 0, 0, ?, 1, ?, ?). This would not be efficient, though. The other assumption made is that these tuples are associated with a "color", and querying should return the color (not just that it matched). This makes the problem much harder, because we have to order the tuples (or else it is ambiguous which of (0, ?) and (?, 1) matches (0, 1)).
In the algorithms community I've found a lot of results related to finding substrings that match with "don't cares". This is a considerably harder problem, and I can't really make use of any of the techniques.

In conclusion

Thanks for any help!


texts: Example demonstrating the power of non-deterministic circuits

texts:
A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$.
Analogous to $P/poly$ (the class of languages decidable by polynomial size circuits), $NP/poly$ can be defined as the class of languages decidable by polynomial size non-deterministic circuits. It is widely believed that non-deterministic circuits are more powerful than deterministic circuits, in particular $NP \subset P/poly$ imply that the polynomial hierarchy collapses.

  Is there an explicit (and unconditional) example in the literature
  showing that non-deterministic circuits are more powerful than
  deterministic circuits?

  In particular, do you know of a function family $\{f_n\}_{n > 0}$
  computable by non-deterministic circuits of size $cn$, but not
  computable by deterministic circuits of size $(c+\epsilon)n$?


texts: Consequence of Decision Tree Complexity of $k$-SUM Problem

texts:
Ezra and Sharir showed the $O(n^2\log^2 n)$ linear decision tree complexity for $k$-SUM problem [1], which improves the $O(n^3\log^3 n)$ complexity result of Cardinal et al [2].

It is known that $k$-SUM and Table-$k$-SUM problems are related and can be reduced to each other in linear time[3] and both problems can be solved in polynomial time $O(m^k).$

$\textbf{$k$-SUM Conjecture}$ [4]:
There does not exist a $k ≥ 2$, an $ε > 0$, and a randomized algorithm that succeeds (with high probability) in solving $k$-SUM in time $O(n^{ \left \lceil{k/2}\right \rceil−ε})$.

What's the consequence of the above new decision tree complexity results? What can this lead to a new bound for the time complexity of $k$-SUM problem?

[1] Ezra, Esther, and Micha Sharir. "The Decision Tree Complexity for $ k $-SUM is at most Nearly Quadratic." arXiv preprint arXiv:1607.04336 (2016).

[2] Cardinal, Jean, John Iacono, and Aurélien Ooms. "Solving $ k $-SUM using few linear queries." arXiv preprint arXiv:1512.06678 (2015).

[3] Woeginger, Gerhard J. "Space and time complexity of exact algorithms: Some open problems." International Workshop on Parameterized and Exact Computation. Springer Berlin Heidelberg, 2004.

[4] Abboud, Amir, and Kevin Lewi. "Exact weight subgraphs and the k-sum conjecture." International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013.


texts: Why does most cryptography depend on large prime number pairs, as opposed to other problems?

texts:
Most current cryptography methods depend on the difficulty of factoring numbers that are the product of two large prime numbers. As I understand it, that is difficult only as long as the method used to generate the large primes cannot be used as a shortcut to factoring the resulting composite number (and that factoring large numbers itself is difficult).

It looks like mathematicians find better shortcuts from time to time, and encryption systems have to be upgraded periodically as a result. (There's also the possibility that quantum computing will eventually make factorization a much easier problem, but that's not going to catch anyone by surprise if the technology catches up with the theory.)

Some other problems are proven to be difficult. Two examples that come to mind are variations on the knapsack problem, and the traveling salesman problem.

I know that Merkle–Hellman has been broken, that Nasako–Murakami remains secure, and that knapsack problems may be resistant to quantum computing. (Thanks, Wikipedia.) I found nothing about using the traveling salesman problem for cryptography.

So, why do pairs of large primes seem to rule cryptography?

Is it simply because the it is currently easy to generate pairs of large primes that are easy to multiply but difficult to factor?
Is it because factoring pairs of large primes is proven to be difficult to a predictable degree that is good enough?
Are pairs of large primes useful in a way other than difficulty, such as the property of working for both encryption and cryptographic signing?
Is the problem of generating problem sets for each of the other problem types that are difficult enough for the cryptographic purpose itself too difficult to be practical?
Are the properties of other problem types insufficiently studied to be trusted?
Other.


texts: Fastest approximate triangle counting algorithms in dense graphs

texts:
One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the number of triangles) for $1\pm \epsilon$ approximate triangle counting. It works by repeatedly sampling triplets of vertices and using those sample to estimate the number of triangles.
Is there anything asymptotically faster than these two algorithms? I am aware of the sublinear-time algorithms for triangle counting. However, those that I am aware of are parameterized by the number of edges and not the number of vertices. I am only interested in results parameterized by the number of vertices.


texts: PAC-learning bound with epsilon-cover of hypothesis class

texts:
In this video at 43:00, a version of the PAC bound for generalization error $\epsilon$, which I hadn't seen before, is quoted:

$$\epsilon^2 < \frac{\log{|H_\epsilon|} + \log{1/\delta}}{2m}$$

where $m$ is the number of samples, $\delta$ is the confidence parameter, and $H_\epsilon$ is the cardinality of an "$\epsilon$-cover of the hypothesis class", where he defines an $\epsilon$-cover as a set of subsets of the hypothesis class, such that the probability that two hypothesis in the same subset disagree is less than $\epsilon$.

Apart from the fact that this isn't a formal statement, I couldn't prove this myself. Has anyone heard of this version of PAC, and if so, could they point me to resources explaining it, or give some explanation here?


texts: Reference Request : Accessible reference for Randomised algorithms and Hashing for non-Computer Scientists?

texts:
My goal is to understand well a paper like ApproxMC. It discusses the use of Hash functions for Propositional Model Counting. In my understanding what they call hash functions are just random XOR's added to propositional formulas. On the other hand any tutorial level discussion on hashing is completely dedicated to putting  data in bins for easy access which seems completely divorced from their discussion.
I would like to have a reference on randomised algorithms,  which is able to explain universal hashing from scratch and is able to build up to the level of rigorous statistical understanding of universal hashing families.
Other similar problems in my understanding is LSH (Locality Sensitive Hashing).


texts:
When interpreting keys as natural numbers we can use the following formula.

\begin{equation}
h(k) = \lfloor m (kA\bmod{1}) \rfloor
\end{equation}

What I am having trouble understanding is how we choose the value of A where:

\begin{equation}
0 < A < 1
\end{equation}

According to Knuth an optimal value is:

\begin{equation}
A \thickapprox (\sqrt{5} - 1) / 2 = 0.6180339887...
\end{equation}

So my question is how did Knuth come to this and how could I calculate an optimum value for my specific data?


texts: Lower bounds for inversion counting in comparison model?

texts:
For counting the number of inversions in an array, there are many $O(n \log n)$ algorithms, e.g. the one that modifies Merge Sort. There is an easy $\Omega(n)$ lower bound simply because you have to look at all the elements.

I saw some faster algorithms in the RAM model, such as this $O(n \sqrt{\log n})$ algorithm for a permutation on $n$ elements: http://people.csail.mit.edu/mip/papers/invs/paper.pdf.

Is anything else known in the comparison model for inversion counting? I'm mainly curious if there are better lower bounds.


texts:
I cannot find references concerning the complexity of the variant of the knapsack problem (decision version) where one of the two conditions must be a product instead of a sum (0 not allowed).

A related question is this one: Combining subset sum and subset product problems .

It is well known that we can say that knapsack is the special case of subset sum (where each weight is equal to each profit and the bounds are the same) to satisfy the equality of subset sum with 2 inequalities. However, this is not possible here since there are 2 equalities to satisfy in the "subset sum product" problem and we have only 2 inequalities in the "knapsack sum product".


texts:
Is there a priority queue data structure that supports the following operations?

Insert(x, p): Add a new record x with priority p
StableExtractMin(): Return and delete the record with minimum priority, breaking ties by insertion order.

Thus, after Insert(a, 1), Insert(b, 2), Insert(c, 1), Insert(d,2), a sequence of StableExtractMin's would return a, then c, then b, then d.

Obviously one could use any priority queue data structure by storing the pair $(p, time)$ as the actual priority, but I'm interested in data structures that do not explicitly store the insertion times (or insertion order), by analogy to stable sorting.

Equivalently(?): Is there a stable version of heapsort that does not require $\Omega(n)$ extra space?


texts: Bootstrapping results that really bootstrap

texts:
There is a type of results in TCS usually called bootstrapping results. In general, it is of the form

  If proposition $A$ holds, then proposition $A'$ holds.

where $A$ and $A'$ are propositions that look similar, and $A$ is seemingly "weaker" then $A'$, which is the reason we name this type of results.
Let me give a few concrete examples:

  Theorem. [Chen and Tell, STOC'19] Fix any problem $\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$
  . Assume that for every $c>1$ there exist infinitely many $d\in \mathbb{N}$ such that $\mathcal{TC}^0$ circuits of depth $d$ need more than $n^{1+c^{-d}}$ wires to solve the problem $\Pi$. Then for any $d_0,k \in \mathbb{N}$, $\Pi$ cannot be solved by $\mathcal{TC}^0$ circuits of depth $d_0$ and $n^k$ wires, and therefore $\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$.

  Theorem. [Gupta et al., FOCS'13] Suppose that computing the permanent requires depth-$3$ arithmetic circuits of size more than $n^{\Omega(\sqrt{n})}$, over fields of characteristic $0$. Then computing the permanent requires arithmetic circuits of superpolynomial size, and therefore Valiant's Conjecture holds.

Well, a more famous but not-so-appropriate example comes from fine-grained complexity:

  Theorem. [Backurs and Indyk, STOC'15] If we can compute EDIT DISTANCE in $O(n^{2-\epsilon})$ time (on the RAM model), then we will get a SAT solver faster than any one that currently exists.

Update. (July 10, 2019) The edit distance example may be a little confusing. Refer to Ryan’s answer for a “standard” example.

As you may have imagined, (to my  best knowledge) all results of this type are proved by taking the contrapositive (I have taken the contrapositive in the edit distance one). So in some sense these are all algorithmic results.

Usually there are two ways to understand a bootstrapping result. 1. We only need to prove $A$ and then apply the result, if we want to prove $A'$; 2. Proving $A$ may be difficult because a priori we think proving $A'$ difficult.

The problem is that, one (or more exactly, I) may be hardly optimistic and take the first understanding, if there does not exist any positive use of bootstrap results after all!
So my question is

  Do we know any bootstrapping result in which $A$ is proven?


texts:
This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about algorithms from the book. Hence a separate query!

Reductions of all kinds are most welcome.

I'll start off with the really simple reduction from vertex cover to multicut on stars. The reduction almost suggests itself once the source problem is identified (before which I would find it hard to believe that the problem would be hard on stars). This reduction involves constructing a star with $n$ leaves, and associating a pair of terminals with every edge in the graph, and it is "easy to see" that it works. I will update this with a link to a reference, once I find one.

Those who are missing the context of the book may want to look at the question about Algorithms from the book.

Update: I realize that I was not entirely clear as to what qualifies as a reduction from the book. I find this issue a little bit tricky, so I confess to half-deliberately dodging the issue by slipping in a reference to the other thread :)

So let me describe what I had in mind, and I suppose it goes without saying - YMMV in this regard. I intend a direct analogy to the original intent of Proofs from the Book. I have seen reductions that are awfully clever, and leave me gaping at how that sequence of thoughts might have occurred to anyone. While such reductions leave me with a definite sense of awe, those are not the examples that I am looking to collect in this context.

What I am looking for are reductions that are described without too much difficulty, and are perhaps mildly surprising, for the reason that they are easy to grasp but aren't easy to come up with. If you estimate that the reduction in question will require a lecture to cover, then likely it doesn't fit the bill, although I am sure there might be exceptions where the high-level idea is elegant and the devil's in the details (for the record, I'm not sure I can think of any).

The example I gave was deliberately simple, and hopefully somewhat - if not perfectly - illustrative of these characteristics. The first time I heard about multi-cut was in a classroom, and our instructor began by saying that not only is it NP-hard in general, it is NP-hard even when restricted to trees... {dramatic pause} of height one. I recall not being able to prove it immediately, although it seems obvious in retrospect.

I suppose obvious in retrospect closely describes what I am looking for. I am not sure if this has anything to do with the complexity of the description - perhaps there are situations where something apparently murky might classify as elegant - feel free to bring up your examples (exceptions?), but I would really appreciate a justification. Given that after some point this is a matter of taste, you should certainly feel free to find what I see as insanely complex, perfectly beautiful. I am looking forward to seeing a variety of examples!


texts:
This question was asked to Jeannette Wing after her PCAST presentation on computer science.

  “From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge question for the theoretical computer science community since I think it begs the question “What is information?”)

Beyond "What is information?" one should also figure out what "volume" means in this context? Perhaps maximum density of information is a better measure.


texts: Partition of $\{(i, j)\ |\ i \neq j \leq n\}$

texts:
Consider the set of  $n^2 - n$ pairs $\{(i, j)\ |\ i \neq j \leq n\}$.

Call a partition $(P_1,\ldots,P_r)$ of this set valid if for each $P_t$, the sets $\{i\ |\ \exists k: (i,k) \in P_t\}$ and $\{j\ |\ \exists k: (k,j) \in P_t\}$ are disjoint.

I would like a lower bound on the size (i.e. number of sets) of any valid partition. This feels like a natural problem but I was unable to find a reference.

Note that there are valid partitions containing sets of size $n^2/4$, e.g. those containing $\{(i, j)\ |\ i \leq n/2 \mbox{ and } j > n/2\}$.


texts: TSP variant in which edge costs depend on the already visited vertices

texts:
Does a TSP variant exist in which edge costs depend on the vertices already visited?
For instance, if you already visited vertices A, B, and then C, in that order, then now the cost to traverse CD = 5, whereas if you visited B, A, and then C, then the cost to traverse CD would be 8 or something like that.

It doesn't have to depend on the whole visit order so far, it can only depend on the last vertex visited. In a more general sense, if one knows of any TSP variant in which edge costs vary based on some choice made before traversing the edge, please state them here. They might be helpful.

I found the following post, in which the edge costs can depend on the "state" of the visiting entity, which is not unlike my own question :  Path finding on graph with state dependent edge costs
Unfortunately, it doesn't have any answer yet.


texts: Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance

texts:
We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some sparse graph with non-negative edge weights.

Now (first question) consider using one of these graph Laplacian matrices $A$ as the covariance or (second question) inverse covariance matrix of a zero-mean multivariate normal distribution $\mathcal{N}(\boldsymbol{0}, A)$, or $\mathcal{N}(\boldsymbol{0}, A^{-1})$.  For each of these cases, I have two questions:

A. How efficiently can we draw a sample from this distribution?  (Typically to draw a sample, we compute the Cholesky decomposition $A = LL^T$, draw a standard normal $y \sim \mathcal{N}(\boldsymbol{0}, I)$, then compute a sample as $x = L^{-1} y$).

B. How efficiently can we compute the determinant of $A$?

Note that both of these could be solved easily given a Cholesky decomposition, but I don't immediately see how to extract $L$ more efficiently than just by using a standard sparse Cholesky algorithm, which wouldn't use the techniques presented in the above-referenced works, and which would have cubic complexity for sparse-but-high-treewidth graphs.


texts:
Recently the long-standing k-server problem has been solved by Nikhil Bansal, Niv Buchbinder, Aleksander Mądry and Seffi Naor (to appear in FOCS 2011). I'm interested in knowing other open problems in online algorithms. Of course it's impossible to list all of them so I'm primarily looking for the more "important/famous/notorious" ones.

e.g. the k-server problem would be a good one, so is the adwords problem (which has received considerable attention recently).

Some background:

k-server: http://en.wikipedia.org/wiki/K-server_problem

adwords: http://www.stanford.edu/~saberi/adwords.pdf


texts: Polynomial cases of 0 1 quadratic programm with linear constraints

texts:
A pseudo boolean function f:{0,1}^n-> R is defined as f(x)= x^tQx +cx where
Q is a symmetric matrix with null elements in the diagonal. Finding the minimum of this function is solvable in polynomial time if all entries are non - positive.
My question is: Remains the problem of finding the minimum polynomial, if we add linear constraints which themselves decribe a flow. More exactly: Each variable in the constraints occurs in exactly two different equalities and one time its coefficient is 1 and one time its coefficient is -1.

Many thanks for response beforehand!


texts: What is the minimum size of a circuit that computes PARITY?

texts:
It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp.
(We define size as the number of AND and OR gates.)
The proof is by gate-elimination and it seems to fail if we allow arbitrary fan-in.
What is known for this case?

Specifically, does anyone know an example when larger fan-in helps, i.e., we need less than $3(n-1)$ gates?

Update Oct 18. Marzio has shown that for $n=3$ even $5$ gates suffice using the CNF form of PARITY. This implies a bound of $\lfloor \frac 52 n \rfloor-2$ for general $n$. Can YOU do better?


texts: Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

texts: Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?


texts: A reference for a "more algebraic" approach to pushdown automata and CFLs?

texts:
In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly mathematical theory of context-free languages". Nevertheless, this is not made explicit, as context-free languages and pushdown automata are beyond the scope of the book.

I am aware of some connections of free groups (and especially of what Sakarovitch calls involutive monoids) to the theory of pushdown automata and context-free languages -- e.g., the Dyck language, the Shamir's theorem, etc. However, I have had a hard time finding a source in which the "truly mathematical theory of context-free languages", mentioned by Sakarovitch, is actually built up.

The closest thing I have found is the Berstel's book on transductions and context-free languages. However, at first sight it seems to me that pushdown automata are treated only marginally in this book, while the theory of rational subsets of a free group is not applied at all. Perhaps the material I am looking for has been intended for Eilenberg's Volume C, but I am not sure about that neither.

So I would like to ask for a pointer to a book, survey, or perhaps a set of papers, from which I could learn something about the Sakarovitch's "truly mathematical theory of context-free languages" and its relations to free groups and their rational subsets. Or perhaps I am looking for something that does not actually exist?


texts: Relation between $AC^0$ and regular languages

texts:
Let $\mathsf{REG}$ be the class of all regular languages.

It is known $\mathsf{AC}^0 \not\subset \mathsf{REG}$ and $\mathsf{REG} \not\subset \mathsf{AC}^0$. But is there any characterization for languages in $\mathsf{AC}^0 \cap \mathsf{REG}$?


texts: Why do functional programming languages require garbage collection?

texts:
What's stopping ghc from translating Haskell into a concatenative programming language such as combinatory logic and then simply using stack allocation for everything? According to Wikipedia, the translation from lambda calculus to combinatory logic is trivial, and also, concatenative programming languages can rely solely on a stack for memory allocation. Is it feasible to do this translation and thus eliminate garbage collection for languages such as Haskell and ocaml? Are there downsides to doing this?

EDIT: moved here https://stackoverflow.com/questions/39440412/why-do-functional-programming-languages-require-garbage-collection


texts: Set cover approximation ratio as a function of m (number of sets)

texts:
Feige's well known result (and more recent results) show that set cover cannot be approximated within a factor of $(1 - o(1)) \ln n$, where $n$ is the number of variables. What if we want an approximation ratio in terms of $\log m$?

Apparently, there is a folklore result that the approximation ratio must be of the form $\Omega(\log m)$. (The reason for this is that one can assume that the set cover instances which witness the hardness result of Feige, satisfy $m = \text{poly}(n)$). Does anyone know an actual reference for this result? All the sources I read merely state that this is "well-known."

Is there anything more specific known about the approximation ratio here? For instance, is it known what is the optimal constant coefficient of $\log m$ in the approximation ratio?

Any sources/references would be greatly appreciated


texts: How much faster is solving Clique in properly colored graph?

texts:
Given a graph $G$ and a proper vertex coloring $C$ with the minimum
numbers of colors, how much faster can a maximum clique be found than
when just $G$ is given?

Additional information doesn't make the problem harder, and it is
still NP-hard since there are graph classes where coloring
is in P and clique is NP-hard.

There might be some relation to hypergraphs.

We have the trivial bound $\omega(G) \le \chi(G)$, so an algorithm
which finds a clique of size $\chi(G)$ will stop.


texts: Nested automatization of type inference of forall elimination

texts:
Following a previous question about how to automatize the type inference in a forall elimination of an application, now suppose we want to do the same but for a nested forall, say $(\Lambda X_1.\Lambda X_2.\dots.\Lambda X_n.\lambda x:U.t)$ is a function of type $\forall \vec{X}.U\to T$ and we want to apply it to an argument of type $V$. Then we need to find types $W_1,\dots,W_n$ such that $U[\vec{X}/\vec{W}]=V$.

This is clearly another unification problem. Can we solve this problem as easily as the problem with one variable? What is the algorithm for doing this?


texts:
We work in homotopy type theory. Denote the propositional truncation of a type $A$ by $\|A\|$ and the function type between types $A$ and $B$ by $A \to B$.
Can you construct a term of the following type:
$$
\prod_{A:U_0}\prod_{B:U_0}
(\|A\| \to A) \times (\|B\| \to B) \to (\|A + B\| \to A + B)
\quad?
$$


texts: Arithmetic complexity of matrix powering with non-commutative entries

texts:
Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables with $x_i$ being non-commutative.

What is the complexity class and circuit and formula complexity of computing $\mathsf{Tr}(M^d)$ when $d=O(m)$ and $n=O(m^2)$?

Can this class be algebraic class $\mathsf{VNP}$?


texts: Type-and-effect systems, stochasticism and effect squelching: how about quicksort?

texts:
There's a feature of Haskell's type system which bugs me: you can't implement a randomized sorting algorithm without the use of randomness spilling out into all of its callers.  That seems undesirable.

I know in vague terms that there' something called type-and-effect systems, and I guess those are the ones you would use to describe a randomized QuickSort.

It is the case that QuickSort consumes entropy and doesn't emit any, unlike the Fisher-Yates(-Knuth) shuffle which has randomness both in its input and its output.  I think it should somehow be possible to specify two effects, e.g. takes-entropy and yields-entropy such that QuickSort can be validly type+effect-checked as having one effect and the FYK-shuffle as having both.

A lower bound on their effects can probably be inferred easily when they call rand() or its equivalent.  If you annotate quicksort, being a sorting algorithm, as yielding an  output which is sorted and which contains the same elements as the input but in a different order, can you also infer that the randomness won't leak out---that is, an upper bound of anything-except-yield-entropy on the effect---of QuickSort?

Is this approach viable?  Is it useful?  When it comes to stochastic effects, I think what most callers would care about is whether the outputs of their callees are random, i.e. it's the yields-entropy effect which is the most likely to introduce bugs in your programs, and thus the interesting one to limit, which is why you would want the narrower type for QuickSort.

Are my thoughts here remotely correct?  Do they make sense?  I'm not versed in effect systems, but I think this idea might work.  How does it connect to the established literature?  Am I on to something?  If so, why hasn't this been done yet? ;-)


texts:
Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes)： Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 neighbor in the spanning tree (leaves).

That is I want to be able to construct a spanning tree where there are no nodes that are connected to only 2 other nodes in the spanning tree. They should all be connected to either 1 node (a leaf) or all their edges in the underlying cubic graph should also be present in the spanning tree (ie attached to 3 nodes in the spanning tree)?

Does anyone know the answer to this? And if it is possible, how to construct such a spanning tree? Many thanks.


texts:
Unique Games results provide very interesting barriers to results through semidefinite programming. Lovasz theta ($\vartheta(G)$) function is an incarnation of SDP.

Is UG conjecture true $\iff \vartheta(G)$ is best approximation number for independence number $\alpha(G)$ of classes of graphs whose $\alpha(G)$ computation do not have efficient procedure if $P\neq NP$?

(I am adding $P\neq NP$ to avoid cases where other techniques such as Haemer's Bound gives better approximation).