Systematic studies of sum of quadratic polynomials squared I'm wondering if there exists systematic studies of sums of quadratic forms squared, similar to the quadratic forms, which is practically reflected in eigenvalue decomposition (that has huge practical implication). Couple of examples related to the importance of the question.

Principal component analyses (PCA).
Given a set of points $x_i \in \mathbb{R^n}, i=1..k$ find the set of axes $u_1$, ... $u_m$, written as matrix $U \in \mathbb{R^n x R^m}$, and projections $\xi_1$, ..., $\xi_k, \xi_{\circ} \in \mathbb{R^m}$ that minimizes unexplained variance, i.e. solve the following quartic optimization problem
$$ \arg\min_{u_1,\dots, u_n,\\ \xi_1,\dots, \xi_k} \sum \limits_{i} \left( U^T \xi_i - x_i \right)^2$$
By the magic of symmetry it has the solution by singular value decomposition

Generalized PCA. Same as PCA, but now there is a precision matrix $A_i \in \mathbb{R^n x R^n} $ associated with each observable $x_i$. The problem becomes more complicated
$$ \arg\min_{u_1,\dots, u_n,\\ \xi_1,\dots, \xi_k} \sum \limits_{i} \left( A_i U^T \xi_i - x_i \right)^2$$
(when all $A_i$ are identity matrix this problem is equivalent to PCA, when $A_i = A_j, \forall i,j$, and diagonal it is weighted PCA ). This problem can also be solved in polynomial time via semi-definite programming (SDP) -- Since the solution has the form of sums of squares, by NZ Shor (1987) it is convex problem , and Parillo thesis (2000) gives a practical way to compute it via SDP $ \square $

In SDP approach the quartic polynomial is written as a sum of quadratic polynomials squared. Therefore, it is of major importance to know what kind of quartic polynomials can be written as a sum of quadratic forms squared (by the analogy to biquadratic function they can be called biquadratic forms). Most of the literature, I've encountered stop at the point where they find that the minimum of quartic polynomial $p= \sum_k^n (x_k^2-1) + (a^T x)^2, a \in \mathbb{Z^n}$ is encoding partition problem, and there are no arguments why $p$ cannot be represented as a sum of squares of quadratic polynomials, beyond that.
I'm wondering if anyone made systematic studies of polynomials representable by the sum of squares of quadratic polynomials.

To the best of my knowledge, there is no such study; furthermore, without some nontrivial advances in the technology of sum-of-squares (SOS) problems, it is not currently clear what the immediate benefit of such a study would be.  (I'll focus on the SOS connection since that, as far as I know, is the best way to solve these general quartic problems.) This statement should be taken in a positive light: I believe there is a lot of research depth surrounding these problems.  I'll substantiate my claim in a few ways, hopefully in ways people find useful..

Firstly, for the most basic problems of the type you discuss, the SVD connection gives a much better solver than the SOS black box; in particular, the latter constructs an SDP with $\binom{n+2}{2}$ terms, where $n$ is the total number of variables in the source optimization problem (for instance, the total number of elements in all unknown matrices; to see where I got these numbers, see lecture 10 from Pablo Parrilo's 2006 course:  http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/lecture-notes/lecture_10.pdf ).  This is an SDP you would never want to solve (running time depends on $n$ as $n^{6}$ using an interior point solver?), especially when compared with the ridiculous speed of an SVD solver (using consistent notation, SVD will be something like $\mathcal O(n^{1.5})$; you can de-fudge my computations by tracking the number of columns, rows, and target rank, but it's a disaster no matter how you rectify my negligence).  Along this vein, if you designed a specialized algorithm to solve SOS problems where the max degree within any polynomial is two: this would be amazing, and then the sort of survey you seek would have lots of value.

Secondly, since the basic formulation of these problems is out of the window, one may wonder if certain variants of these problems are well handled by SOS solvers.  As an important example, consider the NMF (non-negative matrix factorization) problem, where the matrix unknowns you are optimizing over (in your above formulation) must now have non-negative entries.  Unfortunately, if you take the standard SDP used to solve these problems (see for instance Pablo Parrilo's notes from above), there's no way to introduce those constraints.  (And since some formulations of the resulting problems are NP-hard, you would now be building an approximation scheme; i.e., this can get nasty.)  Furthermore, there is recent work that exploited the polynomial structure of this problem to build solvers with some guarantees: see http://arxiv.org/abs/1111.0952 by Arora, Ge, Kannan, and Moitra.  They build a few algorithms, however when they solve an "exact" NMF problem (where there is an exact factorization, i.e., one giving objective value 0), they do not use a SOS solver: they use a solver checking feasibility of "semi-algebraic sets", a much more difficult optimization problem which allows the kinds of constraints which NMF raises, but now with exponential running time.

Anyway, to summarize and give some further perspective; since SOS is afaik the only solver for the quartic problems you speak of (i.e., I don't think there is a specialized quartic solver), I've discussed how these solvers have better alternatives for the kinds of quartic problems people care about.  To effectively use SOS tools here, you would either have to build some amazing solver for the quartic case (inner polynomials of degree at most 2), or you would have to find some way to add constraints to these problems.  Otherwise, the connection to SOS problems, while fascinating, does not give you much.

You also mention that you are surprised that the literature you have found does not make this connection.  I think that is mostly due to the newness of practical SOS solvers (even though abstract consideration of SOS problems goes back very far), and what I said above.  In fact, when I first found SOS solvers, it was via Parrilo's notes and papers, and I similarly wondered, "why isn't he talking about PCA-type problems"?  Then I checked the above facts and frowned a lot.  I think it's also a bad sign that Parrilo himself has not, as far as I can tell/skim, discussed these problems outside the reference you mention in his thesis (meanwhile, he has papers on various extensions, and I have a lot of respect for his work in these field: he must have thought about these specific quartic problems many times.. okay I just checked and found a related negative result by him and some colleagues, which has some connections in its introduction: http://arxiv.org/abs/1111.1498 ).


k-outerplanar graphs are subgraphs of bounded diameter planar graphs? of bounded diameter bounded genus graphs? It is well known that bounded diameter planar graphs have bounded treewidth (e.g. see this). Does the converse hold? That is, is every planar bounded treewidth graph the (induced?) subgraph of a bounded diameter planar graph?

I am interested in a proof sketch/reference if this is true or a counterexample if this is false.

Note1: David's correct answer below is in the negative. In its light can we modify the question to read: Are k-outerplanar graphs subgraphs of simultaneously bounded diameter and bounded genus graphs?

Note2: David further indicates (correctly) that the nested triangles graph cannot be made bounded tree-width even at the expense of increasing the genus to a constant.

No: see the nested triangles graph. It has bounded treewidth (more strongly, bounded pathwidth and bandwidth) but cannot be augmented to have bounded diameter while preserving planarity.


What is the maximum number of stable marriages for an instance of the Stable Marriage Problem? Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem

I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the Gale-Shapley algorithm. However, if we are given only $n$ , the number of men/women, we ask the following question - Can we construct a preference list that gives the maximum number of stable marriages? What is the upper bound on such a number?

For an instance with $n$ men and $n$ women, the trivial upper bound is $n!$, and nothing better is known. For a lower bound, Knuth (1976) gives an infinite family of instances with $\Omega(2.28^n)$ stable matchings, and Thurber (2002) extends this family to all $n$.


What are some good introductory books on type theory? I'm recently studying Haskell and programming languages.  Could someone recommend some books on type theory?

Software Foundations by Benjamin C. Pierce would be a good place to start. It would be a make a good precursor to his Types and Programming Languages. There is also Simon Thompson's Type Theory and Functional Programming and Girard's Proofs and Types.


Eliminating clauses from a CNF formula based on their unsatisfying truth assignments being covered by some other clause We are given a Boolean formula in Conjunctive Normal Form (CNF) with $n$ variables and $m$ clauses, where we do not allow repetition of clauses in a given formula and we do not allow repetition of variables in a given clause. Then it is well known that we can have up to $3^n-1$ distinct clauses.

What I would like to know is the complexity of eliminating clauses where their unsatisfying assignments are already covered by some other clause. For example, given the following CNF formula $ \{ (a,b,c,d), (a,b,c,\bar{d}), (a,\bar{b},c,d), (a,b,c), (a,b,d), (b,c,d), (c,d) \}.$ After we eliminate the clauses where their unsatisfying truth assignments are already covered by some other clause we get following CNF formula $\{ (a,b,c), (a,b,d), (c,d) \}.$ How fast can this be done for an arbitrary formula? Could it be done in polynomial time in terms of the length of the input?

What you're describing is called subsumption; it is a standard CNF simplification technique for SAT solvers.  None of the operations involved is worse than quadratic to either the number of variables or number of clauses in the formula.


Number of solutions for a system of linear equations over a finite ring Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and
$b\in R^{m}$.

Questions:

What is the complexity of counting the number of solutions to the system of equations $Ax = b$? Can it be done in polynomial time?
More generally, let $R$ is a finite set and $(+,\cdot)$ be binary opeartions such that $(R,+)$ and $(R,\cdot)$ are (not necessarily commutative) semigroups. What is the complexity of counting the number of solutions to a system of linear equations $Ax=b$?

Note that it is well known that the answer to Question 1 is affirmative if the the ring $R$ is a finite field.

The answer to (1) is yes (regardless of the properties D.W. asked for in the comments), depending on how $R$ is given: First, note that since $R$ is finite, the abelian group $(R,+)$ is of the form $\mathbb{Z}_{p_1^{k_1}} \oplus \dotsb \oplus \mathbb{Z}_{p_\ell^{k_\ell}}$, where $\ell \leq \log_2|R|$. Now, if $R$ is only given to you by generators and relations, even finding this decomposition is as hard as factoring (but given a factoring oracle, it can then be done easily). But if $R$ is fixed for all time (not part of the input), then this can be done as a once-and-for-all off-line precomputation, or if $R$ is part of the input, this can be done in $O(|R|)$ steps (even when given generators and relations).

So depending on your assumptions, the preceding step is either hard or easy. But let's suppose it's done. Now we'll use two viewpoints on the elements of $R$ to reduce to linear algebra over abelian groups.

Viewpoint 1: We may consider elements of $R$ as "vectors" with $\ell$ integer coordinates, where we consider the $i$-th coordinate modulo $p_i^{k_i}$.

Viewpoint 2: This requires a little setup. Let $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$ denote the set of ring homomorphisms between these two rings. In particular, when $p_i \neq p_j$, this is zero; when $p_i = p_j$ if $k_i < k_j$ then this involves taking element of $\mathbb{Z}_{p_j^{k_j}}$ modulo $p_i^{k_i}$, and possibly multiplying it by an element of $\mathbb{Z}_{p_i^{k_i}}$ (which we may represent by an integer, treated modulo $p_i^{k_i}$); if $k_i > k_j$ it involves possibly multiplying by an element of $\mathbb{Z}_{p_j^{k_j}}$ (represented by an integer), and then applying the unique embedding of $\mathbb{Z}_{p_j^{k_j}}$ into $\mathbb{Z}_{p_i^{k_i}}$ (as the multiples of $p_i^{k_i-k_j}$, modulo $p_i^{k_i}$)

Now, consider the left multiplicative action of any $r \in R$ on $R$. Then we may associate to $r$ an $\ell \times \ell$ matrix, where the $(i,j)$ entry is an element of $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$, which can be represented by an integer, following the conventions above.

Now, replace each entry of $A$ by the associated $\ell \times \ell$ matrix as in viewpoint 2, replace each entry of $b$ by the associated vector as in viewpoint $1$, and replace each entry of $x$ with a vector of length $\ell$ (as in viewpoint 1).

Now the original problem has been reduced to linear algebra over abelian groups, which can be solved in polynomial time (see, e.g., Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002).


Which properties of planar graphs generalize to higher dimension / hypergraphs? A planar graph is a graph which can be embedded in the plane, without having crossing edges.

Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k.

There has been some work done on embedding hypergraphs in the plane (with the context of clustering or some other application), but often, the data just can't be embedded in the plane. The solution could be either to force it, with some loss, or embed it in higher dimension as I suggest here:

A natural extension of planarity (IMO, at least) is a "$k$-simple-embedding" (is there a known different name for it?) of $G$: an embedding $\mathcal{M}:X\to \mathbb{R}^k$, such that there exist surfaces which connect all of the vertices of each hyperedge, and these do not intersect except for the endpoints.

(Think of the analogue in 2D, where each surface is an edge you can draw however you like).

Here's an example of a valid 3-simple-embedding of a 3-uniform-hypergraph. (Each vertex is colored by the hyperedges it is contained in, and each face represents an hyperedge).

Another example of 3-simple graph is the complete 3-uniform-hypergraph on 5 vertices $G=(V,V\times V\times V)$. To see this simply take 4 points in $\mathbb{R}^3$ which don't lie on a 2D plane, create a triangular pyramid (their convex hull), and place the fifth point in the center of the pyramid, connecting it to the other vertices.

Similarly, it seems that the complete 3-uniform-hypergraph on 6 vertices doesn't have a 3-simple-embedding.

There are some very useful properties of planar graphs which allow improved algorithms for hard problems when the graph is planar. Unfortunately, the data is often not planar, although sometimes it is of low dimensionality. I think that understanding which properties of planar graphs generalize will help us figure out which algorithms can be adapted for higher dimension with the same tool.

An example of a property that could be useful comes from Fáry's Theorem which suggests every planar graph can be embedded in a way that all of its edges are straight line segments.

Does Fáry's Theorem hold in higher dimension?, i.e. if a graph has a $k$-simple-embedding, does it have an embedding in which all of the hyper edges are hyperplanes?

Are there any other properties that can be generalized? for example, can Euler's Formula for planar graphs be generalized somehow to higher dimension? (although at the moment I'm not sure what would be the meaning of it).

Oh oh. You want to be very very careful. Contact graphs of convex polytopes in 3d can realize any graph. Surprisingly, the clique can be realized by n polytopes that are n rotated and translated copies of the same polytope (the mind boggles). See this paper:

http://www.cs.uiuc.edu/~jeffe/pubs/crum.html

This already implies that you can encode pretty nasty graphs as intersection graphs of triangles in 3d. See section 4 of this paper:

http://sarielhp.org/p/09/set_cover_hard/

BTW, I am interested in a similar version of your problem by trying to understand how geometric intersection graph behaves...


Data structure that allows moving groups of elements into buckets I'm looking for a data structure that can do the following geometric operation:

Suppose there are a set of buckets $b_0, b_1..., b_n$ each of which contains some elements. Suppose I want to move all the elements in buckets $b_i$ where $i > k$ one bucket forward. So the elements in bucket $b_{k+1}$ would be moved to bucket $b_k$ and the elements in bucket $b_{k+2}$ would be moved to bucket $b_{k+1}$ and so on. The obvious way to move these elements is to go to each bucket and shift all the elements into the previous bucket. But is there a data structure that will allow me to move the buckets all at once?

I used buckets in the description because it's easier to formulate the question in terms of buckets. But the data structure doesn't necessarily have to be buckets. All I need is a data structure that can allow me to move "chunks" of elements in one go (for example shifting consecutive the buckets $x$ number of buckets forward all at once) and then allow me to query the structure as normal (for example, allow me to query $b_{k}$ now with all the elements shifted.

EDIT: I'm mainly interested in whether an already existing data structure that I'm not aware of does this.

I don't quite know if this is what you were looking for since it is not a single data structure that has a name - but what you are asking for is easily implementable using just a linked list and a binary search tree:

Keep a single linked list where all the elements of bucket $i$ come before the elements of bucket $i+1$. On every link you can have a boolean flag - is this the same bucket or next bucket. Now doing the shift corresponds to setting the flag to "same bucket" from "next bucket".

Of course you probably also want to maintain some way to see the first element of each bucket. A way to do this is to store the pointers to the first element of each bucket in a balanced binary search tree, such that the key of the pointer to bucket $i$ is $i$. The search tree should be able to: (a) given $i$, output the entry with the $i$'th lowest key and (b) delete entries from the search tree.

Merging bucket $i$ and $i+1$ now reduces to finding the entry in the search tree with the $i+1$'st lowest key, deleting this entry from the search tree, going to where it points in the list, and setting the flag of the arc pointing into this node in the list to "same bucket". Thus all operations take $O(\log n)$ time.

Note that after some "shift" operations are performed the key of the $i$'th bucket is no longer $i$, but it is the $i$'th lowest key stored in the search tree.


Choosing random permutations in "strict" polynomial time This question compares "strict" polynomial time, as opposed to "expected" polynomial time.

Let $S = \{1,2,…,n\}$, and let $O$ be an ordering on elements of $S$ (the number of orderings is $n!$).

A probabilistic algorithm can easily select a random ordering in "strict" polynomial time (in $1^n$), as follows:

Let O = {}, T = S
For i = 1 To n
    Let e be a random element from T
    Let T = T - {e}
    Let O = O ∪ {(i,e)}

The algorithm assumes that sampling a random element from $T$ can be performed in strict polynomial time. (More precisely, we assume that in strict polynomial time, we can uniformly sample from any set whose size is polynomial in $n$.)

Now let's consider the following problem:

  Choose $m$ distinct random permutations over $S$, where $m$ = poly($n$) < $n!$.

One naive way of doing this is to repeat the above algorithm, keep a record of permutations selected thus far. If the algorithm returns a "redundant" permutation, throw it away, and start over.

The above approach works in "expected" polynomial time, rather than "strict" polynomial time.

  Is there a strict polynomial time which does the job?

Edit: Here's a reference for those who want to know more on "strict vs. expected" issue:
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.

I believe the answer is that it is possible in polynomial time as follows:

Each permutation of $N$ can be expressed as a function $f(x)$ which maps an input index to the corresponding output index. Each such function can be expressed as a string $f(1) + f(2) + f(3) + ... + f(N)$, where $+$ is the concatentaion operator. Thus there is a natural lexicographic ordering on the permutations. The idea is to pick the permutations in lexicographic order.

The probability $p_{i,1}$ that permutation $P_i$ will be the first permutation (in lexicographic order) from a set of $M$ permutations of $N$ elements chosen uniformly at random will be $$p_{i,1} = \frac{\binom{N-i}{M-1}}{\binom{N}{M}}.$$

By making a random choice from this probability distribution we determine the first permutation in our set. Let's assume that this permutation is indexed by $x_1$. We now need to choose the permutation which is second lowest in lexicographic order. Clearly, this is the same problem as before, but now we need to choose according to the probability distribution $$p_{i,2} = \frac{\binom{N-x_1-i}{M-2}}{\binom{N-x_1}{M-1}}.$$

For an arbitrary ranking $k$ the probability distribution will be given by $$p_{i,k} = \frac{\binom{N-i-\sum_{j=1}^{k-1} x_j}{M-k}}{\binom{N-\sum_{j=1}^{k-1}x_j}{M-k+1}}.$$

This process is repeated until we have chosen all $M$ permutations. As there is no possibility of collision, the process terminates after exactly $M$ such choices, and hence is an exact polynomial time computation assuming the random choice can be made in time $\mbox{poly}(N)$.

UPDATE: Kaveh points out in the comments below that I have not shown how to find the $i$th permutation in time polynomial in $n$, so here is one way.

We can turn an permutation into an integer by taking $I_P = \sum_{k=0}^{n-1} \frac{n!}{(n-i)!} (y_k-1)$. Here $y_k$ is defined as follows: Let $S_0$ be the set of integers from 1 to $N$, and take $S_k = S_0 / \{f(x)\}_{x=1}^k$. Then $y_k$ is the lexicographic index of $f(k+1)$ in $S_k$. Note that $y_k$ is always an integer between 1 and $n-k$. Thus you obtain a unique integer between 0 and $n!-1$ for every permutation. To reverst this and find the $i$th permutation is trivial, since $y_0 = (I_P \mbox{ mod } n)+1$, $y_1 = ((I_P-y_0)/n \mbox{ mod } n)+1$ etc., and once all $y_k$ have been calculated, $f(x)$ can be calculated by taking $f(1) = y_0$, which allows you to calculate $S_1$, which in turn gives you $f(2)$, etc.

Thus you have a polynomial time algorithm for converting a permutation of $n$ items into a unique integer between $0$ and $n!-1$ and back.

This answer makes an assumption that it is possible to generate probabilities of the necessary form, which is not necessarily granted in the question. See the answer for Peter Shor for why this can be a problem.


Graph nodes preserving changes to the overall graph I remember reading about a kind of Graph data structure, where every change to the the graph could be preserved. I don't remember exactly neither the name, neither a good description (if it was the graph that remembered the changes, or each node who kept the changes of its childs).

It was on Wikipedia about 2-1.5 years ago, I was reading about version control. I would really appreciate if someone could help me find the name of this data sctructure.

Thanks Fraser, the paper is J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan, Making Data Structures Persistent, Journal of Computer and System Sciences, Vol. 38, No. 1, 1989.

I believe you are thinking of persistent data structures.
http://en.wikipedia.org/wiki/Persistent_data_structure


What is the name of this partition-indexed key-value data structure? Consider a data structure that holds N elements having M partitions each holding N/M elements where M divides N. Each element has a key that satisfies an equivalence relation so as to index into one of the partitions.

Assuming this data structure is implemented within an array insertions are performed by computing the beginning partition location corresponding to the key for the element in question and a linear search is performed until a sentinel empty-value is found (or the end of the partition). Searches are performed analogously.

What is the name of the data structure described above? Does it have any advantage over a hash-table?

Sounds like a hash table to me, with collision resolution by chaining.


Multiplicative version of 3-SUM What is known about the time complexity of the following problem, which we call 3-MUL?

Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$?

This problem is similar to the 3-SUM problem, which asks whether there are three elements $a,b,c\in S$ such that $a+b+c=0$ (or equivalently $a+b=c$). 3-SUM is conjectured to require roughly quadratic time in $n$. Is there a similar conjecture for 3-MUL? Specifically is 3-MUL known to be 3-SUM hard?

Note, the time complexity should apply in a "reasonable" model of computation. For instance, we could reduce from 3-SUM on a set $S$ to 3-MUL on set the $S'$, where  $S'=\{2^x\mid x\in S\}$. Then a solution to 3-MUL, $2^a\cdot 2^b=2^c$, exists if and only if $a+b=c$. However, this exponential blow-up of the numbers scales very badly with various models, like the RAM model for example.

Your reduction from $3$SUM to $3$MUL works with a minor standard modification.
Suppose your original integers were in {$1,\ldots,M$}. After the transformation $x\rightarrow 2^x$ the new integers are in {$2,\ldots,2^M$}. We will reduce the range.

Consider any triple of integers $a,b,c$ in the new set $S'$.
The number of prime divisors of any nonzero $ab-c$ is $<2M$. The number of such triples is $n^3$. Hence the number of primes $q$ which divide at least one of the $ab-c$ nonzero numbers is at most $2Mn^3$.

Let $P$ be the set of the first $2M\cdot n^4$ primes. The largest such prime is of size at most $O(Mn^4\log Mn)$. Pick a random prime $p\in P$. With high probability $p$ will not divide any of the nonzero $ab-c$, so we can represent each $a\in S'$ by its residue, mod $p$, and if $3$MUL finds some $ab=c$ in $S'$, with high probability it will be correct for the original $3$SUM instance. We have reduced the range of the numbers to {$0,\ldots, O(Mn^4\log Mn)$}.

(This is a standard size reduction. You might be able to do better by considering the fact that the $ab-c$ are always differences of two powers of $2$.)


What is best known space requrement for solving SATISFIABILITY problem in exp time I searched a lot for finding best space requirement algorithm for SATISFIABILITY problem but I didn't find any thing better than brute force that is in DSPACE(n). is there exists better bound? and what is best known bound.

If I understand your question correctly, as far as I understand this is computational-model dependent. An excellent lecture on the subject by Prof. Ryan O'Donnell can be found here: https://www.youtube.com/watch?v=_nCBH_lVjGU


Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language? I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ worst-case slowdown. Is there a definitive reference I can cite? In my case I am working on a purely-functional data structure and I use Standard ML, if these details matter.

And perhaps this question would be even more relevant when applied to data structures specified in, say, Java? Maybe there is some relevant discussions in algorithms/data structure textbooks that use Java? (I know Sedgewick has a Java version, but I have access to the C version only.)

Yes, gc is amortized constant time. Suppose you have an algorithm which runs for time $n$ with a peak working set of size $k$. Now, note that you can allocate at most $O(n)$ words during the execution of the program, and that the time cost of running a copying garbage collector is $O(k)$ (ie, the cost of a gc is proportional to the total amount of live data). So if you run the gc at most $O(n/k)$ times, then the total runtime cost is bounded by $O(n)$, which means that the amortized cost of the gc is constant. So if you have a Cheney-style collector, with each semispace being size $2k$, then it's easy to see that a full collection can't be invoked more than once every $n/k$ steps, since allocating $k$ words takes $O(k)$ time, and the working set never exceeds size $k$, which gives you the bound you want. This justifies ignoring gc issues.

However, one case where the presence or absence of gc is not ignorable is when writing lock-free data structures. Many modern lock-free data structures deliberately leak memory and rely on gc for correctness. This is because at a high level, the way they work is to copy some data, make a change to it, and try to atomically update it with a CAS instruction, and run this in a loop until the CAS succeeds. Adding deterministic deallocation to these algorithms makes them much more complex, and so people often don't bother (esp. since they are often targeted at Java-like environments).

EDIT: If you want non-amortized bounds, the Cheney collector won't do it -- it scans the whole live set each time it is invoked. The keyword to google for is "real-time garbage collection", and Djikstra et al. and Steele gave the first real time mark-and-sweep collectors, and Baker gave the first real time compacting gc.

@article{dijkstra1978fly,
  title={{On-the-fly garbage collection: An exercise in cooperation}},
  author={Dijkstra, E.W. and Lamport, L. and Martin, A.J. and Scholten, C.S. and Steffens, E.F.M.},
  journal={Communications of the ACM},
  volume={21},
  number={11},
  pages={966--975},
  issn={0001-0782},
  year={1978},
  publisher={ACM}
}

@article{steele1975multiprocessing,
  title={{Multiprocessing compactifying garbage collection}},
  author={Steele Jr, G.L.},
  journal={Communications of the ACM},
  volume={18},
  number={9},
  pages={495--508},
  issn={0001-0782},
  year={1975},
  publisher={ACM}
}

@article{baker1978list,
  title={{List processing in real time on a serial computer}},
  author={Baker Jr, H.G.},
  journal={Communications of the ACM},
  volume={21},
  number={4},
  pages={280--294},
  issn={0001-0782},
  year={1978},
  publisher={ACM}
}


Can we have more than one Deterministic Finite Automata diagrams for a set of strings? Much like many math equations can be simplified. I am wondering if Deterministic Finite Automata diagrams can equal each other while some may be more simplified than others. I am following the youtube video and I am wondering if the graph that I drew with pencil and paper would also be correct. Given the Prompt:

Construct a DFA that accepts any strings over {a,b} that does not contain the string aabb in it.

Can we have more than one Deterministic Finite Automata (DFA) diagrams for a set of strings?

Of course!

There's also an algorithm to minimize a deterministic finite automata into a minimal deterministic finite automata. The existence of such algorithm is a proof that for most, if not all, sets of strings, many DFAs can be defined.


Trees that structure partially ordered data Suppose we have a binary search tree $T$ built over keys from a totally ordered set, and we want to support the standard dictionary lookup $\mbox{Find}(x)$ which returns a pointer to the node containing key $x$, or reports that $x$ is not contained in $T$.

Normally, we start a query from the root of a binary search tree, but we don't have to.
From any node in the search tree, we can traverse the tree to find the location of any key in the search tree using only local information stored at each node. This takes $O(h)$ time, where $h$ is the height of the tree.

Now suppose we want to support that same $\mbox{Find()}$ query over keys drawn from a partial order.
A quadtree built over 2d points has these three interesting properties:

The data in the tree is partially ordered.
We can perform a $\mbox{Find()}$ query in $O(h)$ time using only local information at each node.
It is often used to answer more complex queries.

Question: are there other tree data structures that meet these three criteria?

Justification of the three criteria for the quadtree is included below:

1) Points in two dimensions are partially ordered. Sorting 2d points, or finding the successor of a point $(x,y)$ doesn't have meaning unless we first define a total order on the points, essentially projecting them down to one dimension. (Sort these points lexographically, find the successor of $(x,y)$ along this space-filling curve).

2) Each cell of a quadtree stores an axis-aligned rectangle, and the rectangle of a parent is the union of the rectangles of the children. We can navigate to the correct node in $O(h)$ time by comparing the point we are searching for with the rectangle stored at each node along our search path.

3) e.g. Approximate nearest neighbor or approximate range queries.

Interval trees store partially ordered data (intervals) and can answer complex queries (e.g. find all the intervals overlapping given one/containing given one/etc). Looks like criteria (2) and (3) are met, but I'm not sure if I understand (1) correctly.


Can a non-competitive deterministic algorithm be k-competitive if randomized? Let's say there is a problem in which all possible deterministic online algorithms tha solve this problem are not-competitive.

Does this mean that a randomized online algorithm for the same problem will also be not-competitive, or is there a case that it can be k-competitive (k is a constant)?

Imagine having to predict 0 or 1 on every round, and we are counting the number of correct predictions.  Every deterministic strategy has an adversarial sequence that makes it always predict incorrectly. Hence, no competitive ratio is possible.

However, the randomized strategy of flipping a coin on every round will be $2$-competitive with the best constant prediction (in expectation).


Is Kolmogorov complexity a surjective function? Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,x) outputs whatever T outputs on input x (possibly both running forever).
Define the Kolmogorov complexity of x, K(x), as the length of the shortest program, p, such that U(p)=x.

  Is there an N such that for all n>N there is an x with K(x)=n?

Remark. If we define universal Turing-machines in a different way, the answer can be negative. For example, consider a U that on input (T,x) simulates T on x if the length of (T,x) is divisible by 100, and otherwise does nothing.
One can modify this example in several ways to obtain counterexamples for different definitions of universal Turing-machines.

Just an extended comment with no deep insights: perhaps you can cheat on the encoding of a Turing machine, and build an artificial encoding that leads to a surjective Kolmogorov complexity:

$0$ represents the Turing machine that outputs $0$ (1 state TM);
$0p$ represents the Turing machine that outputs $p+1$ (the number represented by the binary string $p$ plus one); it is simply an implicit "zipped" version of a decidable TM that outputs $p+1$;
$1p$ represents the $p+1$-th Turing machine in a standard enumeration (the enumeration can skip the TMs already included with $0$ and $0p$).

The corresponding universal TM on input $bx$ checks what is the value of $b$, if it is $0$ then it simply outputs $x+1$, otherwise it  simulates TM $M_{x+1}$ ($M_0$ when $x$ is the empty string); note that $M_{x+1}$ embeds the inputs.

For all strings $x$, $1 \leq K(x) \leq |x|+1$; and for all $n \geq 1$ there are $2^{n}$ strings of length $n$ but there are only $2^{n-1}-1$ programs of length $< n$ that can be represented using the $1p$ encoding; and only $2^{n}-1$ programs of length $n$ that can be represented using the $1p$ encoding; so at least a string $x'$  of length $n$ cannot be represented with a program $1p$ of length $\leq n$; but it can surely be represented with the program $0x'$ of length $n+1$ (we don't worry if there is also a program $1p$ of the same length $n+1$ that generates it).

We can conclude that for all $n > 1$, there exists a string $x', |x'|=n$ such that $K(x') = n+1$ (so this particular K is surjective).


Making an adjacency matrix positive semidefinite I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can find on which nodes to set self-loops and how many of those.

Your question is too imprecise.  What does it mean to "transform a matrix"?  Are you asking whether there is an algorithm that takes as input a symmetric matrix and finds the minimal total weight that can be added to diagonal entries so as to make the new matrix positive semi-definite?

If this is your question, the answer is yes, since it is an SDP.  If you restrict to adding integer values to diagonal elements ("self loops"), then I do not know the complexity of finding the minimum number of self loops needed.

You might want to look into Gershgorin's circle theorem if you are trying to do this by hand.


Is there a name for this Assignment definition The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks.

Now consider the following generalization: Instead of specifying a  cost of a single agent-task pair, assume that you can specify a cost of an arbitrary set of agent-task pairs. The problem is then defined by a set of constraints, where each constraint is a cost c and a set S of task-agent pairs. Meaning of a such constraint is that a cost c occurs when all pairs in S are "satisfied", and the overall cost is the sum of costs of all satisfied constraints.

Note that this problem can be encoded as Weighted Partial MAX-SAT, where hard clauses encode one-to-one assignment between agents and tasks, and each constraint is a (weighted) soft clause.

However, I am interested if this can be reduced to something simpler or if this is a known problem, but so far wasn't able to find an answer.

Thanks for your help.

Seems to me that the submodular welfare problem falls under your description. Have a look at http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf chapter 4; here we assume that the utility function of subsets is submodular.
In general, your problem is just the combinatorial auction problem which is hard to approximate without any assumptions on the valuation function.


Feasibility of equations with max constraints Relating to a question I posted here, I have formulated the following question:

Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$.

How to check the following system of equations is feasible? Assumption: $x_i, b_k$ are all in $[0,1]$

$\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$

for example:

$\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$

What's the complexity of this problem? Obviously it is in NP, but is it NP-hard? It would be a surprise if such an easy problem does not have a polynomial algorithm. Does linear programming help here?

Many thanks.

Let $y_i=\min\{b_k| i\in J_k\}$. Observe for any feasible solution, $x_i\leq y_i$.

Claim: The system of $\max$ equations is feasible iff $x_i=y_i$ for $1\leq i\leq n$ is a solution.

Proof.
If $x_i=y_i$ is a solution, then the system of $\max$ equations is feasible

Consider any solution, and $x_i < y_i$ for some $i$. We can increase $x_i$ to $y_i$ without violate any equation. Assume it violates the $k$th equation, namely $\max\{x_j|j,i\in J_k\}=b_k$, then it implies $y_i = \max\{x_j|j,i\in J_k\} > b_k$, but that's a contradiction because
$$
b_k \geq \min\{b_j| i\in J_j\} = y_i = \max\{x_j|j,i\in J_k\} > b_k
$$.

The algorithm is just compute $y_i$s and check if it satisfies all the equations. This takes linear time.


If P = BQP, does this imply that PSPACE (= IP) = AM? Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking...

I wondered what if Quantum Computers could be efficiently simulated by Classical Computers. Could this be SIMPLY related to the Divide between IP and AM? What I mean is that IP is characterized by Polynomial number of rounds of  classical interaction, while AM has 2 rounds of classical interaction. Could simulating a Quantum Computing reduced the amount of interaction for IP from polynomial to a constant value?

Great question!  Short answer: no implication like
$$
\mathsf{P} = \mathsf{BQP}   \Rightarrow  \mathsf{IP} = \mathsf{AM}
$$
is known; but that doesn't mean it's not worth trying to prove...

I would say, though, that finding such an implication seems unlikely.  I think the message of much quantum complexity theory is that, while quantum computers are not an all-purpose panacea for solving hard problems, they can be much more powerful than classical computers in certain specific circumstances.

For example, in query complexity, quantum algorithms can efficiently solve certain problems classical ones provably cannot, when the input is promised to obey some nice global structure.  E.g., Shor's algorithm is based on an algorithm to quickly find the unknown period of a function promised to be periodic.  On the other hand, quantum query algorithms are not too much stronger than classical ones for solving problems in which there is no special structure assumed on the input.  (See Buhrman and de Wolf's survey on query complexity for this last point.)

Similarly, I think the results $\mathsf{QIP}(3) = \mathsf{QIP} = \mathsf{IP}$ tell us, not that interaction is unexpectedly weak (even if $\mathsf{P} = \mathsf{BQP}$), but that quantum computation is unexpectedly strong, specifically in the context of interaction with computationally-unbounded provers.


Minimizing residual finite state automata Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular language, and the language recognized by each state in the RFSA is a residual, just like in a DFA. However, whereas a minimum DFAs states form a bijection with all residuals, the canonical RFSAs states are in bijection with the prime residuals; there can be exponentially fewer of these, so RFSAs can be much more compact than DFAs for representing regular languages.
However, I can't tell if there is an efficient algorithm for minimizing RFSAs or if there is a hardness result. What is the complexity of minimizing RFSAs?
From browsing [BBCF10], it doesn't seem like this is common knowledge. On the one hand, I expect this to be difficult because a lot of simple questions about RFSAs like "is this NFA an RFSA?" are very hard, PSPACE-complete in this case. On the other hand, [BHKL09] shows that canonical RFSAs are efficiently learnable in Angluin's minimally-adequate teacher model [A87], and efficiently learning a minimum RFSA and minimizing RFSAs seems like it should be of equal difficulty. However, as far as I can tell [BHKL09]'s algorithm does not imply a minimization algorithm, since the size of counter-examples is not bounded and it is not clear how to efficiently test RFSAs for equality to simulate the counter-example oracle. Testing two NFAs for equality is PSPACE-complete, for example.
References
[A87] Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and Computation, 75: 87-106
[BBCF10] Berstel, J., Boasson, L., Carton, O., & Fagnot, I. (2010). Minimization of automata. arXiv:1010.5318.
[BHKL09] Bollig, B., Habermehl, P., Kern, C., & Leucker, M. (2009). Angluin-Style Learning of NFA. In IJCAI, 9: 1004-1009.
[DLT02] Denis, F., Lemay, A., & Terlutte, A. (2002). Residual finite state automata. Fundamenta Informaticae, 51(4): 339-368.

Let the "DFA $\to$ NFA" problem denote the following: Given a DFA $A$ and an integer $k$, is there an NFA with at most $k$ states equivalent to $A$? Similarly, let "DFA $\to$ RFSA" denote the problem obtained from the above if we replace "NFA" with "residual finite state automaton".

Jiang and Ravikumar showed that the "DFA $\to$ NFA" problem is PSPACE-complete by a reduction from the "DFA union universality" problem. The latter problem has given a list of DFAs $A_1,A_2,\ldots,A_n$, and asks if $\bigcup_{i=1}^nL(A_i) = \Sigma^*$.

Their reduction goes by defining a language $L$ from these DFAs and a suitable integer $k$, such that a DFA accepting $L$ can be constructed in time polynomial in the size of the DFAs $A_i$. Then they show that every NFA (thus a fortiori every RFSA) accepting $L$ needs at least $k$ states in case $\bigcup_{i=1}^nL(A_i)$ is universal and at least $k+1$ states otherwise. Then they construct a $k$-state NFA $N$, which accepts $L$ iff $\bigcup_{i=1}^nL(A_i) = \Sigma^*$.

This proof was reconsidered later by Gruber and Holzer (Developments in Language Theory '06). They use the same reduction to show a slightly different result, which concerns the computational complexity of lower bound techniques for NFAs: An (extended) fooling set for a regular language $R$ is a set $S$ of word pairs $(x_i,y_i)$, such that for each $i$ holds $x_iy_i\in L$ but for all $i\neq j$ holds: $x_iy_j \notin R$ or $x_jy_i\notin R$.

For the above reduction, they show that there is an extended fooling set $S$ of size $k$ in case $\bigcup_{i=1}^nL(A_i)$ is universal. By inspecting the proof by Gruber and Holzer, one readily notes that each "left word" $x_i$ in the set $S$ is such that the NFA $N$ mentioned above can go from the initial state to only a single state $q_i$ on reading $x_i$. That is, the language accepted from state $q$ equals $x_i^{-1}L$, and thus $N$ is a residual finite state automaton.

If the above reasoning contains no mistakes, this yields a reduction from the DFA union universality problem to the "DFA $\to$ RFSA" problem, and thus it is PSPACE-hard. Membership in PSPACE follows along the same lines as for the DFA $\to$ NFA problem, so the "DFA $\to$ RFSA" problem is PSPACE-complete. Being more general but still in PSPACE, the "NFA $\to$ RFSA" problem is PSPACE-complete as well.

For those who want to reconstruct the above argument (please don't take it for granted, my writeup was a bit hasty), I recommend reading the proof of Theorem 15 in the ECCC report cited below. Especially, Figure 5 on page 18 depicts the automaton $N$ which I claim to be a RFSA.

T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on
Computing, 22(6):1117–1141, December 1993.

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity Is Hard. In Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of Lecture Notes in Computer Science, pages 363--374. Springer, June 2006.

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Technical Report ECCC TR06-027, Electronic Colloquium on Computational Complexity, 2006.


Rational function for Parity function Let $x_1,x_2,\dots x_n$ be literals.

Let $P(x_1,x_2,\dots,x_n)$ be the parity function.

What is the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $f(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$)?

What is the smallest degree of $r(x_1,x_2,\dots,x_n)\in \mathbb R(x_1,x_2,\dots,x_n)$ (sum of degrees of numerator and denominator) that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $R(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$)?

Note that $f(x_1,x_2,\dots,x_n)$ and the numerator and denominator of $r(x_1,x_2,\dots,x_n)$ can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.

It will be somewhat easier to replace $\{0,1\}$ with $\{\pm 1\}$, so that the parity function is just $x_1\cdots x_n$. Since this is an affine transformation, it doesn't affect degrees. I'm also assuming that the denominator of a rational function must be non-zero for all $\pm 1$ inputs. Since we only care about $\pm 1$ inputs, we work below over the ideal generated by $\{x_i^2 - 1\}$.

We prove by induction on $n$ that if $P/Q$ represents parity of length $n$ then $PQ = \alpha \prod_{i=1}^n x_i + \cdots$ for some positive $\alpha$, where the dots represent lower degree terms. This implies that $\deg P + \deg Q \geq n$. The claim is clearly true for $n = 0$. Now consider
$$\frac{P}{Q} = \frac{x_nP_1+P_2}{x_nQ_1+Q_2}, $$
where $P_1,P_2,Q_1,Q_2$ are over $x_1,\ldots,x_{n-1}$. Substituting $x_n=\pm1$ and applying the induction hypothesis, we deduce that for some $\alpha,\beta > 0$,
$$
\begin{align*}
(P_1+P_2)(Q_1+Q_2) &= \alpha \prod_{i=1}^{n-1} x_i + \cdots, \\
(P_1-P_2)(Q_1-Q_2) &= -\beta \prod_{i=1}^{n-1} x_i + \cdots. \\
\end{align*}
$$
Subtracting both equations, we get
$$ P_1 Q_2 + P_2 Q_1 = \frac{\alpha+\beta}{2} \prod_{i=1}^{n-1} x_i + \cdots. $$
Therefore
$$ PQ = (x_nP_1+P_2)(x_nQ_1+Q_2) = x_n(P_1Q_2+P_2Q_1) + \cdots = \frac{\alpha+\beta}{2} \prod_{i=1}^n x_i + \cdots. $$


Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components? I'm considering integer programming on an variation of Steiner Forest Problem:

  Given a graph $G=(V,E)$, a cost function: $c:E \rightarrow R^{+}$, a terminal set $T \subseteq V$, and a positive integer $k$, find a subgraph containing at most $k$ connected components that includes all the terminals with minimum total edge cost.

The key point of constructing the ingeger programming is to enforce the $k$ connected components constraint. The only way I came up with is using the generalized subtour elimination constraints over edge variables for each connected component. Is there any other ways to enforcing the $k$ connected components constraint? Any clue or suggestion would be appreciated.

Base on Komus's constraint, we add another constraint which ensures a Steiner Tree on $G^{'}=(V, E^{'})$, where $E'=\{(i,j): i,j \in V\}$:
$$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall \text{ }u-v\text{ }cut \text{ }(U,V)$$where $cut(U,V)$ denotes the cut set of $(U,V)$.

Together with Komus's constraint, our model is obtained as follows:

  $$min \sum_{e \in E}c_e x_e$$
  subject to
  $$\sum_{e \in cut(U,V)}x_e \ge 1, \forall u,v \in T, \forall \text{ }u-v\text{ }cut \text{ }(U,V)$$
  $$\sum_{e \notin E} x_e \le k-1$$

Base on Cao's comment, one more step is needed to prune the solution of our model: if $\sum_{e \notin E}x_e < k-1$, then we delete the largest $\Delta$ edges in the solution, where $\Delta=k-1-\sum_{e \notin E}x_e$. Then we get an optimal solution.


How many different Huffman encoding for a given number of symbols In Huffman coding, if we have two symbols to be encoded, we will get the result either 01 or 10. If we have three symbols, we will get 12 different encoding. I am wondering if I give a arbitrary number of symbol, is there a formula to calculate how many different encoding we will have by Huffman coding?

The answer is $C_{n-1} n!$ . That is, the $(n-1)$st Catalan number times $n$ factorial.

There are $C_{n-1}$ ways of making a complete binary tree with $n$ leaves, and there are $n!$ ways of assigning these leaves to the symbols to get a Huffman code.

This sequence goes 2, 12, 120, 1680, 30240, and is listed in the Online Encyclopedia of Integer Sequences as Quadruple Factorial Numbers, with a simpler formula than I give above.

The above argument shows that the quadruple factorial numbers give the number of ways of assigning $n$ symbols to codewords in a complete binary prefix code. It's not hard to show that you can assign probabilities to the symbols to make this encoding optimal (so it satisfies the definition of a Huffman code). It's not clear that a given Huffman coding algorithm will generate all of these, however.


A more intuitive proof of the Zone theorem ? The Zone theorem says that if we stab an arrangement of n lines with another line, the total complexity of its zone, the set of all 0-, 1-, and 2-faces adjacent to it,  is O(n). The actual constant is something like 6n at least as stated in various textbooks, and the proof is by induction with a reasonably careful charging argument.

I was asked this question in class, and don't have an answer:

  Is there an alternate, more intuitive
  proof of the Zone theorem ?

Now I realize that many people find induction quite intuitive and would be offended by my implication, and am willing to amend the above to merely "alternate" for them. But is there any such proof ? Or even a proof from the book ?

This is not cleaner, but it is a good preparation for more advanced stuff, and it is a good example of abstraction...

One can use Davenport-Schinzel sequences argument. Consider the region above your zone line. Every line becomes a ray, and in fact two rays, as we consider the left side and right side as being different. Scan the boundary of this zone from left to right, writing down which rays you encounter. This is a sequence defined over 2n symbols, and the pattern abab is illegal. As such, the length of the sequence is at most 2(2n)-1 = 4n-1. Applying it to the zone below the line, implies a bound of the form 8n.

Now, proving that a sequence of symbols without ...a..b..a..b... as a subsequence of n symbols has length 2n-1 is easy. indeed, consider two consecutive appearances of the same character that are closest to each other in this sequence. Clearly, in between these two characters, each character that appears must be unique. Consider such a character, and observe that if it appears anywhere else in the string, then we will get the forbidden subsequence. As such, this character appears exactly once in the string. Remove it, and remove an extra character if needed if you created two consecutive identical characters. Namely, removing a character from the string shorten it by 2, as such, the maximum length of the string is 2n-1.


If the untyped language is terminating, can we still derive a contradiction from `Type : Type`? Question

If a pure type system has a terminating proof language, can we have Type : Type at the logic level without causing paradoxes (i.e., without causing ∀ (x : *) -> x to be inhabited)?

Example

Suppose we take a pure type theory such as the Calculus of Constructions, restrict functions to be affine (at most 1 variable uses) and add constructs for stratified duplications - see here for details. That language - which we could call EACC (Elementary Affine Calculus of Constructions) has a normalizing untyped fragment. That is, the reduction of any term - even ill-typed ones - is guaranteed to terminate due to the reduction rules (and, in particular, the restriction that duplicated terms can not change their levels).

The 'logic' of the contradiction with Type:Type is that you can create a term of any type including 'empty' type by 'cheating' by never returning. This is essentially the only way to cheat because of subject reduction and the subformula properties.

Subject reduction states that evaluation of terms preserves their type.
If you have subject reduction and strong normalization (through whatever means), then you can infer that if you have a term of type T, you have a term of type T in a normal form - without any redexes (cuts) in it.

You have to go over all your type rules and verify that all of them have subformula property except the cut rule (which normalization eliminates).
I.e you have to verify that if one of the non-cut rules were to produce a term of type T then you'll have one of its premises produce the term of type T (perhaps somewhere deeper in the derivation tree).
AFAIK every good type system requires sub-formula property (I'd like to learn of examples that contradict it).

Since type derivations are supposed to be finite trees, and you have no axiom (0 premises) rule to introduce a term of an empty type, you can prove by induction that no tree can build a term of an empty type.

To reiterate, the role of normalization is that cut rule does not have sub-formula property, so we have to eliminate it first while preserving the type of the term.

This is the general sketch of Gentzen's proofs of consistency of logics.


PTAS Algorithm for K-Clustering when Distance Computation is Costly Can anyone throw any light on any PTAS algorithm that I can apply for K-Clustering algorithm when the distance computation between the clustering points is costly.

In details, I have a set of N points and I have a customized distance metric between them. I want to compute a set of k clusters such that the cluster centers are far apart while among the clusters the points are very close. This customized distance metric is costly to calculate and hence I would like them to be calculated as less as it can possibly be.

I can give more clarification if required.

[EDIT] So the distance metric I have defined is $D(x,y) = 1 - \rho(x,y)$ where $\rho(x,y)$ is the Pearson Correlation Coefficient between points $x$ and $y$ ( $x$ and $y$ are data sets in themselves). Obviously to compute all such Pearson Correlations Coefficient when the number of data-points is 1000 (each set $x$ has another 1000 or so values within themselves) or so can be very expensive computationally.

Have you seen this paper by Piotr Indyk ? It's old, but it's a good one. It solves a number of problems including k-median while making only sublinear number of calls to the distance oracle. It's not exactly the model you're looking for, but it does try to reduce the number of distance invocations.


Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$? In the "last paragraph" of the "first page" of the following paper:

Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical Computer Science, 1995.

I encountered a somewhat counter-intuitive claim:

$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$

I think the identity above is deduced from the following:

$(\Sigma^P_2)^{NP} = \Sigma^P_3$

and

$(\Pi^P_2)^{NP} = \Pi^P_3$

The former is more simply written as $(NP^{NP})^{NP} = NP^{NP^{NP}}$, which is quite odd!

Edit: In light of Kristoffer's comment below, I'd like to add the following inspiring remark from Goldreich's complexity book (pp. 118-119):

  It should be clear that the class $C_1^{C_2}$ can be defined for two complexity classes $C_1$ and $C_2$, provided that $C_1$ is associated with a class of standard machines that generalizes naturally to a class of oracle machines. Actually, the class $C_1^{C_2}$ is not defined based on the class $C_1$ but rather by analogy to it. Specifically, suppose that $C_1$ is the class of sets that are recognizable (or rather accepted) by machines of a certain type (e.g., deterministic or non-deterministic) with certain resource bounds (e.g., time and/or space bounds). Then, we consider analogous oracle machines (i.e., of the same type and with the same resource bounds), and say that $S \in C_1^{C_2}$ if there exists an adequate oracle machine $M_1$ (i.e., of this type and resource bounds) and a set $S_2 \in C_2$ such that $M_1^{S_2}$ accepts the set $S$.

${\Sigma_2^P}^{NP}$ is the set of language decided by an alternating turing machine in existential, and then universal state, with an oracle in NP. Both the universal and the existantial part can querye NP.

Hence, in this case you decided to write this as $(NP^{NP})^{A}$ then the way you should think of it is as  $(NP^{NP^A\cup A})$ (by $\cup$ I mean an oracle either to $A$ or to an $NP^A$ language).

Hence ${\Sigma_2^P}^{NP}$ is equal to $(NP^{(NP^{NP})})^{NP}$ which is certainly equal to $(NP^{NP^{NP}})$ since every query you could make to the $NP$ oracle, you could make it to the $NP^{NP}$ oracle.


Computability and continuity Say $L_1$ and $L_2$ are computable languages.  Let $f$ be a function $L_1 \rightarrow L_2$.  Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(l)$ is a computable language."  Does $C$ imply that $f$ is necessarily a computable function?
$C$ is similar to the topological concept of continuity; a function $g$ between topological spaces is continuous if, for each open set $S$ in the codomain of $g$, $g^{-1}(S)$ is an open set in the domain.  Here "open sets" have been replaced with "computable languages."  (Computable languages can't actually be considered open sets here, because they aren't closed under infinite union.)
The converse, "$f$ is computable implies $C$," is easily proved.  If $f$ is computable, and $l$ is a computable language that's a subset of $L_2$, then let $l' = f^{-1}(l)$.  You can computably tell whether something is in $l'$ by first mapping it through $f$ and asking if the result is in $l$.  So $l'$ must be a computable language, proving $C$.

Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable (c.e.) subset $S \subseteq \mathbb{N}$ contains either finitely many elements of $L$ or all but finitely many elements of $L$.
Let $f : \mathbb{N} \to \mathbb{N}$ be an enumeration of $L$ without repetitions. The map $f$ is not computable, or else $M$ would be a computable subset of $\mathbb{N}$, which a maximal set is not.
We claim that $f$ is a counter-example to your question. Consider any c.e. subset $S \subseteq \mathbb{N}$:

If $S \cap L$ is finite then $f^{-1}(S) = f^{-1}(S \cap L)$ is finite (as $f$ is injective) and therefore a computable set.
If $S \cap L$ contains all but finitely many elements of $L$ then $f^{-1}(S) = f^{-1}(S \cap L)$ contains all but finitely many elements of $\mathbb{N}$, therefore it is a computable set.

In your question you hint at the analogy between computability and continuity. Indeed there is one, but we need to be a bit more sensitive about computability.
Let $$\mathcal{E}  = \{S \subseteq \mathbb{N} \mid \text{$S$ is c.e.}\}$$ be the set of all c.e. subsets of $\mathbb{N}$, and let $W : \mathbb{N} \to \mathcal{E}$ be a standard enumeration of c.e. sets. We can think of $\mathcal{E}$ as the "computably open" subsets of $\mathbb{N}$. Indeed, they're closed under finite intersections and unions of computable families.
Say that a map $F : \mathcal{E} \to \mathcal{E}$ is computable if there exists a computable $r : \mathbb{N} \to \mathbb{N}$ such that $F(W_n) = W_{r(n)}$ for all $n \in \mathbb{N}$. (This is just the standard notion of computability for numbered sets.)
Your question can be rectified into a theorem like this (I just inserted the emphasized "computable"):
Theorem: A map $f : \mathbb{N} \to \mathbb{N}$ is computable if, and only if, its inverse image map $f^{-1} : \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ restricts to a computable map $f^{-1} : \mathcal{E} \to \mathcal{E}$.
I will leave the (easy) proof as an exercise. The above can easily be generalized from number-theoretic maps to languages.


Is this a weaker or stronger form of the halting problem Halting problem: There is no decider for $L =\{\langle M,w\rangle ~|~ M$ halts on $w \}$
This problem: For any $H$ which can decide some infinite subsets of $L$, then I can always, constructively find $\langle M,w\rangle$ such that $H(\langle M,w\rangle)$ is incorrect.
Here the infinite subset part is supposed to be like heuristics. Primitively checking for infinite loops and things. If someone comes up with a program which can mostly determine halting, I should always be able to come up with an adversarial case in which it fails.
Halting implies these adversarial cases exist, but can I find them at all? Can I find them efficiently?

The standard proof that the halting problem $L$ is undecidable also gives an efficient algorithm for constructing an instance on which a given Turing machine $H$ fails to solve the halting problem.
For any Turing machine $H$, let $M_H$ be a Turing machine implementing the following algorithm: "On input $\langle P \rangle$ where $P$ is a Turing machine, run $H(\langle P, P \rangle)$. If it outputs $1$, run forever, otherwise halt."
By design, $H(\langle M_H, M_H \rangle)$ fails. Either it runs forever, or else it halts and gives the wrong answer to the question of whether $\langle M_H, M_H \rangle \in L$. Given $\langle H \rangle$, one can efficiently construct $\langle M_H, M_H \rangle$.


Does a universal index exist? Given a data table containing a very large number $N$ of rows, with each row containing a large number $k$ of fields, with each field containing a large but fixed number of bits, there are a number of methods for constructing an "index" structure so that the following operations can be performed on the table and index in $O(k\log N)$ time (relative to $N$ and $k$):

Insert a new element into the table.
Remove a specified element from the table.
Given a set of values of the fields, obtain the first record that is in the table with field values greater than the given field values, when the table is sorted into the lexicographic order with field 1 first, field 2 second, etc.

We wish to generalize this construction so that when operation 3 is done, any of the $k!$ orderings of the $k$ fields can be specified to determine the ordering of the records in the table.

Clearly, this can be done by constructing k! indexes, one for each ordering of the fields.  Then the operations take $O(k!k\log N)$ time.

We want an algorithm whose operations are much faster (relative to $k$), preferably $O(k\log k \log N)$ time.

Does such an algorithm/data structure exist?  It seems likely that if it existed, someone would have published and implemented it by now, but I've found no signs that one exists.  Conversely, perhaps it can be proven that no such algorithm exists.  But I've found no signs that such a proof exists.

One can show a lower bound for the data structure you are asking for under the Strong Exponential Time hypothesis. In particular, if all the entries have one bit, then one can use the data structure to do subset queries: i.e the data structure stores a family ${\cal F}$ of $N$ sets, each of size at most $k$. Then, the user may make "subset" queries - give a set $S$ and ask whether there is an $X \in {\cal F}$ such that $S \subseteq X$.

Such a query can be supported if we have a "universal index" - if we look for the lexicographically first entry coming after $S$, where we sort first by the columns where $S$ is $1$ and then along the ones where $S$ is $0$ then any element appearing after $S$ according to this order must be a superset of $S$.

Now, subset queries are equivalent to "dot product = 0" queries from this awesome answer by Ryan Williams - go read it. I will just summarize the effects of this answer on the universal index problem; assuming the Strong Exponential Time Hypothesis one can't support queries with running time $O(poly(k)N^{0.99})$, even if the family ${\cal F}$ is given in advance and we only have queries of type $3$ (i.e the data structure is static), and we have $poly(N,k)$ pre-processing time.


Can you make a different learner? My questions are:

[Solved by Dave] Given a learner N, can you design a learner M that behaves differently from N? No.

and

[Solved by Dave] Given a learner N, can you design a learner M that is more powerful than N? No.

and

[Solved by Dave] Given a learner N that always halts, can you design a learner M and a set of natural numbers L, such that (a) for every text T that contains exactly L, M converges on T and (b) there exists a text T' that contains exactly L, such that N diverges on T'? No.

and especially

[Open] Given a learner N that is prudent and always halts, can you effectively design a learner M such that there exists a set of natural numbers L such that

for every text T that contains exactly L, M converges on T and
there exists a text S that contains exactly L, such that N diverges on S?

Note that the difference between the fourth and the third questions is that N is required to be prudent. But M is not required. So N can't simulate M and follow exactly what M does -- M may conjecture a set it does not always converge on.
Also note that a yes answer to the open problem (discussed below) will imply a no answer to the fourth question. I'm saying this because, if you follow Dave's line of thought, you are solving the open problem, which is a stronger statement than (a negative answer to) my question.
And a yes answer to the fourth problem implies a no answer to the open question.
Now come the definitions.
A learner is a Turing machine that, when the input is a (finite) sequence of natural numbers, outputs a program that enumerates a subset of natural numbers.
A text is an infinite sequence of natural numbers.
A learner is said to converge on a text if, when feeding successively longer initial segments of the text, there exists a point after which the learner outputs the same enumeration procedure that enumerates exactly the elements in the text.
A learner diverges on a text if it does not converge on it.
Learner A is said to behave differently from learner B if there exists a text on which A converges but B diverges or A diverges but B converges.
Learner A is said to be more powerful than learner B if A converges on (strictly) more texts than B.
A learner M is prudent iff, if on some initial segment of some text it conjectures a set S, it converges on all texts for S.
Discussion
The background of these problems is the open question whether there exists a program that when given a learner outputs a prudent learner that converges on a superset of texts. Mark Fulk proved that the prudent learner exists (in Theorem 15 of the article "Prudence and other conditions on formal language learning"), but his proof is non-constructive because it has a seemingly undecidable case distinction. The open problem is to give a constructive proof of this theorem.

Answer to questions 1 and 2: No. This is also the answer to 3 if $M$ is required to always halt (isn't this implied by the definition of a learner, or do you mean the program produced by $M$ must always halt?). Here's a proof for 1 (2 and 3 work pretty much the same way)

Suppose there's an algorithm $A$ which takes the description of a learner $N$ and outputs a learner $M$ which behaves differently. Let $N$ be a learner which runs $A$ on its own description, then runs the output $A(N) = M$ on the input text to produce a program that enumerates some set. By definition of $A$, $N$ and $M$ behave differently, but by construction they behave identically, contradicting the existence of $A$.

This same argument can be pretty easily modified to show that 2 is impossible. It can also be used to show that 3 is impossible if $M$ must always halt.

Not a real answer for question 4, but you might find this helpful: A prudent learner cannot converge on both every text for a finite set and on every text for the set of all natural numbers. Let $N$ be a learner that converges on every text for a finite set. Now, consider the following text for the set of all natural numbers. It contains all numbers in order, separated by differing numbers of 1s. After $i$, it contains enough 1s that $N$ will return a program which enumerates the set $1,\ldots,i$. $N$ will do this because it converges on every finite set. Because it will return a program enumerating a finite set after every prefix of this text, it does not converge on this text.

So if you let $M_1$ be the learner which converges on all finite sets and $M_2$ be the learner which converges on all texts for the set of all natural numbers, at least one of $M_1,M_2$ satisfies the criteria in question 4. You can extend this to a countably infinite set of learners in which at least all but one learner satisfies the criteria in question 4 by producing a machine $M_i$ for each natural number $i$ which converges on all finite sets which don't contain powers of the $i$th prime and also converges on the set of all powers of the $i$th prime. By similar logic as above, $N$ can't converge on all sets that any two of these converge on.

You can use this set of learners to find an $M$ satisfying 4 with arbitrarily high probability.


FSM transducer sequential composition decidability this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word $x$. define a sequence/ composition of such mappings $x_n = F(\ldots F(x_1))$ where $F^n(x)$ is $n$ sequential mappings of $x$. the sequence terminates if/ "at the point" that $F(x_n)$ is unaccepted (by the FSM transducer).

now consider/ define a property of such sequences "descending". a FSM sequence $x_i$ is "descending" iff $|x_i| \geq |x_{i + 1}|$ where $|x|$ denotes word length, and for all $i,j$, $x_i \neq x_j$. (by defn all such sequences must be finite/ terminating.)

  question: given an input regular language $L$ and a FSM transducer $F$. is it decidable if all sequences $x_n = F^n(x) = F(\ldots F(x))$ for all $x \in L$ are descending?

a complete answer would be ideal but prefer partial answer(s) to none at all. looking for nontrivial analysis, reduction(s) to known problems, refs to related literature etc.

motivation/ background: a long story, but inspired/ related to investigation of a highly studied open number theory problem. the basic idea is to look for/ formulate a generalized loop invariant function applicable to automated theorem proving.

The problem seems undecidable: consider a transducer $F$ that parses and "executes" a single step of a Turing machine $M$ with the head $H$ on symbol $a$, in state $S$ and with tape content $x[a]by$ where $a,b \in \Sigma; x,y \in \Sigma^*$:

$$\# x \, a \, H\, S \, b \, y \, \# \, w $$

where $w \in \{0,1\}^+$ and it outputs

$$\# x \, H \, S' \, a'\, b \, y \, \# \, w' $$

if the head moves left, i.e. $\sigma(a,S)\to (a',S',L)$ or it outputs

$$\# x \, a' \, b \, H \, S' \, y \, \# \, w' $$

if the head moves right, i.e. $\sigma(a,S)\to (a',S',R)$.

$w'$ is simply $w +1$ (binary addition with the LSB on the left) and its "role" is to make $x_{i+1} \neq x_j \forall j \leq i$ as required.

If $M$ halts (when $S'$ is a final state), then $F$ adds an extra $\#$ at the end (i.e. it makes the output ascending) and rejects to stop the sequence; otherwise it accepts and the length is unaltered.

If there is not enough space for a right move of the head then $F$ rejects to stop the sequence.

If there is not enough space for writing $w+1$ (carry overflow on the right), it simply replaces the last digit with $\#$ (to make $x_{i+1} \neq x_i$) and rejects to stop the sequence.

Note that:

$F$ needs only a limited look-ahead buffer (4 symbols) to make the rewrite and also to perform the $w+1$ operation;
the internal states of $F$ embeds the internal states of $M$ so it can simulate the transition function $\sigma$;

Now, consider $M$ on an empty tape; we can use an (infinite) regular language:

$L = \{ \# \, H \, S_0\, \, 0^+ \# \, 0^+ \}$

$M$ halts if and only if $F^n(x)$ is not descending for all $n$, for all $x \in L$

Indeed the only length increase occurs when $F$ runs on $\# \, H \, S_0\, 0^s \, \# \, 0^t$ and $s,t$ are such that $M$ halts in less than  $2^t$ steps using at most $s$ space.


Do people look at loop nestness in boolean circuits? While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought of as dags, but in real hardware cycles are common. Now, modulo some technicalities regarding what a loop is and what constitutes a nested loop, the claim was basically that in order to implement in hardware an automaton one needs two nested loops, and in order to implement a processor one needs three nested loops. (I might be off-by-one with these counts.)

Two things bother me:

There was nothing like a formal proof.
I didn't see this anywhere else.

Did anyone investigate precise statements of this kind?

Searching for the name of the professor I found a small webpage and book (Chapter 4) that discuss this taxonomy.

Sort of background: In case you wonder why are cycles useful at all in real hardware, here is a simple example. Connect two inverters in a cycle. (An inverter is a gate that computes the boolean function NOT.) This circuit has two stable equilibriums (and an unstable one). Absent any outside intervention, the circuit will simply stay in one of the two states. However, it is possible to force the circuit into one particular state by applying an external signal. The situation can be seen like this: While the cycle is connected to the outside signal "we read the input," and otherwise we simply "remember the last value we saw." So one loop helps us remember stuff.

You should have a look at PhD thesis (later published as a monograph) of Tomás Feder: Stable Networks and Product Graphs, where he studied the complexity of finding stable configurations of networks, which are exactly circuits with "loops" like  you mentioned.


Examples of the use of biased estimators Biased estimators are useful in statistics because they can optimize mean-squared error more than what an unbiased estimator can manage. I was wondering if in theoryCS if there are any very notable examples of the effective use of biased estimators. I realize this list could get long, and if it does I can modify this question to a big-list CW question, but for now I'm just curious.

In machine learning, the sample error of an ERM learner is a biased estimator of the true generalization error. Here the bias is not by choice but by necessity: we simply don't know of a way to construct an unbiased estimator of the generalization error, and I'm pretty sure it's impossible from general no-free-lunch principles.


What is the proof that the existence of one-way-functions implies $P \neq NP$? I am not an expert in this field, but I have read that the existence of one-way functions implies $P \neq NP$. Since there seem to be so many different definitions of one-way-functions and I have not seen a proof  I wanted to ask if someone knows where to read this, or knows the proof.
Please if you give a proof, also give a precise definition of which version of "one-way-function" you use. The proof can of course be detailed, the detailed, the better! :)
Thanks!

$P \ne NP$ if and only if worst-case one-way functions exist.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.


What are the known pseudo-polynomial PSPACE-complete problems? please can you provide either a reference, or give particular examples of PSPACE-complete problems which are solvable in pseudo-polynomial time?

Additonal Notes:

Definition of pseudo-polynomial time: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

In reply to some comments mentioned earlier. I have asked earlier if there were any problems which were PSPACE-complete which had an FPTAS. The surprizing answer was YES!

Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

This is therefore a follow-up question.

(Note that the EXP conjecture apply to the complexity class NP, yet there exists NP-complete problems which are solvable in psuedo-polynomial time!)

Addendum...
Sasho Nikolov asked about FPT and Pspace. I know that there are FPT problems which are Pspace , Exp, Exp Space complete etc... Unfortunately I do not have references... Will correct when I remember

Thanks!!!

Zelah

Consider Subset Sum. A standard reduction from 3-SAT produces an instance with values $x_0,\ldots,x_{2n+1}$, where if there is a subset with the target sum, that set contains exactly one of $x_{2i},x_{2i+1}$ for each $i$. Furthermore, choosing $x_{2i}$ corresponds to setting the $i$th variable in the 3-SAT instance to true, and choosing $x_{2i+1}$ corresponds to setting it false. You can use this same reduction to reduce from quantified 3-SAT to result in a PSPACE-complete quantified version of subset sum, $\exists y_0 \forall y_1 \cdots \sum_{i}y_i = k$, where $y_i$ is equal to either $x_{2i}$ or $x_{2i+1}$.

You can use the same pseudo-polynomial time algorithm for subset sum on this quantified version with some minor modifications. We simply fill in a table of all sums $k$ such that $Q_iy_iQ_{i+1}y_{i+1}\cdots Q_ny_n\sum_{j=i}^{n}y_j = k$ (where each $Q_j$ is either $\exists$ or $\forall$). This table has only polynomial size if all the values are polynomially bounded, and it's not hard to see how to fill it in for $i-1$ given the values for $i$ - simply add $x_{2(i-1)}$ and $x_{2i-1}$ to all the values for $i$, and take either the union or intersection of these sets (for $\exists$ and $\forall$ quantifiers, respectively).


How should I perform research as an Undergraduate Are there distinct fields or types of problems which have contributions that are realistic to achieve for an undergraduate?

Yes, ask your professor to give you a problem that you may solve as an undergraduate. You can also look for publications that say that the problems are appropriate for undergraduates.

I think that a research project that you could do that would be interesting would be to create a language that would compile to the EVM (I suggest scratch https://scratch.mit.edu/).

Another would be to explore user interface design for voice systems like making an Alexa App or one that you create yourself to solve some problem that you face.

A good example can be found at http://www.ics.uci.edu/~theory/269/020125.pdf


Space-approximation Trade-off In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(2k-1)$-approximate distance between any pair of  vertices in the graph.

At a fundamental level, this construction achieves a space-approximation trade-off --- one can reduce the space requirements at the cost of a lower "quality" of the solution.

  What other graph problems exhibit such a trade-off between space and approximation?

I am interested in the case of both static and dynamic, weighted and unweighted, undirected and directed graphs.

Thanks.

this research appears to be active in a more applied sense than the theoretical one you mention (ie oracles etc) with "data streaming" algorithms which attempt to work with very large data through "sliding windows", with many graph algorithms considered, but it is indeed relatively new/recent, fitting in with "big data" research directions.

Tradeoff Algorithms in Streaming Models, Andrea Ribichini, p7:

  We have devised several algorithms for fundamental graph problems in the
  W-Stream model, including connected components, minimum spanning tree,
  biconnected components and single-source shortest paths. To the best of
  our knowledge, our algorithms are the first to allow effective space/passes
  tradeoffs for such problems in a data streaming setting.

this ref includes other refs/surveys which might be helpful.

  Despite the heavy restrictions imposed by the [classical streaming] model, major success has
  been achieved for several data sketching and statistics problems, for which
  a constant number of passes and polylogarithmic working memory have
  been proven enough to find approximate solutions (see [4, 16, 17] and the
  extensive bibliographies in [7, 29]).

also:

Trading off space for passes in graph streaming problems
Camil Demetrescu,
Irene Finocchi,
Andrea Ribichini


Formal semantics of tactics Tactics are supposed to represent inference rules in a system, and it might seem unnecessary at first to formalize the semantics of tactics; nevertheless, modern theorem provers can have pretty complicated tactics which have complex semantics.

My question is, thus, has there been any work on the formalization of tactics in interactive theorem proving, either for Coq-style or LCF/HOL-style theorem provers?

Obviously there is an operational semantics of Ltac by Jedynak et al.


The connection between compressed sensing and sparse representation If I understand correctly, Compressed Sensing as an application of Sparse Representation is defined as:

  To find linear compression schemes for huge input signals that are
  known to have a sparse representation, so that the input signal can be
  recovered efficiently from the compression (the "sketch").(ref: this
  question)

So based on my understanding, compressed sensing is like a precoding before analog to digital data conversion.
And my take on sparse representation is:
A signal can be represented as a linear combination of basis functions where the set of basis functions is called dictionary and data samples are much more than their features. Mathematically, in the system of linear equations $Y=DX$ where $Y \in \mathbb{R}^{n \times N} (n \ll N)$ we seek a dictionary that results in sparse representation of $Y$.

So as far as I've understood, the output of sparse representation is used in compressed sensing. In my thesis on dictionary learning, after an introduction about compressed sensing, I'd like to talk a bit about the connection between compressed sensing and sparse representation before getting into the details of sparse representation. What I fail to do  is to explain the connection between the two even though I am aware of the concepts.
I'd like to have a good understanding of the connection between compressed sensing and sparse representation. Any explanation would be greatly appreciated!

Consider a real world 'signal' - a discrete set of numbers representing something real (e.g. an image, an audio recording, etc.). These numbers form a vector in some vector space. Any such vector can be transformed into many different bases. The vector will be more 'sparse' in some of those bases than others. In fact, there's even a set of bases where the signal is 100% sparse - i.e. a basis set which includes that particular vector as one of it's components. The representation of the vector in a basis in which it is very sparse is a 'sparse representation' of that vector. Unless there is some deliberate connection between the two, the common sense assumption is that in any randomly chosen basis, a given vector will most likely have a very not sparse representation. However, it turns out that in the real world, useful signals are often time very sparse in certain domains. This information can be used.

Compressed sensing seeks to reconstruct a signal with more information than given directly by the measurements (e.g. in imaging, a higher resolution than the number of pixels actually measured, etc.). This is mathematically impossible... unless you have some additional information about the signal aside from the measurements, such as knowing it will likely be sparse in some known domain (e.g. images tend to have a sparse representation in the Fourier domain). So, you measure the signal in some domain (not the sparse one), then you fill in the missing values with guesses to form a a bigger dataset, transform to the sparse domain, and measure the sparsity there. You then adjust your guesses and check again, and so on until you find a set of guess values that minimize sparsity in the alternate domain. You  now have a more complete vector.

So the connection is: compressed sensing uses the fact that the signal has a sparse representation in some known basis


What is known about this binary representation polytope? Consider the following set.

$S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$

$S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer between 0 and $2^n-1$ and $y$ is its binary representation. I'm interested in the convex hull of $S_n$; you can call it $P_n$.

Has $P_n$ been studied before? Does it admit a compact extended formulation?

I think $S_n$ can be written in terms of inequalities in the obvious way. Let
$$
Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}.
$$

I claim that $Q_n = S_n$. First, obviously all $(x, y) \in S_n$ are also in $Q_n$, so $S_n \subseteq Q_n$. Second, fix a point $(x^*, y^*) \in Q_n$. Consider the probability distribution over $\{0, 1\}^n$ induced by picking $y_i = 1$ with probability  $y^*_i$, independently for each $i$. If $y$ is sampled from that distribution, then, by linearity of expectation,
$$
\mathbb{E}\ x = \mathbb{E} \sum_{i = 0}^{n-1}{2^i y_i} = \sum_{i = 0}^{n-1}{2^i y^*_i} = x^*.
$$
Therefore $(x^*, y^*)$ is in the convex hull of $S_n$, which proves $Q_n \subseteq S_n$.

BTW, this didn't really use anything special about $S_n$. Whenever you have the convex hull of the set $\{(x, y): y \in S, x = Ay\}$, and the convex hull of $S$ has a concise extended formulation, the same thing will work. The main point is that $x$ is a linear function of $y$. Here we used the fact that the cube $[0, 1]^n$ has a very easy formulation in terms of inequalities.


Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist? Does there exist an algorithm, about which a non-constructive $\omega$-consistent theory $A$ can prove that it has time complexity $O(f(n))$ where $n$ is some univariate function of the input, but there is no $\omega$-consistent constructive theory which proves this bound, and there is a constructive $\omega$-consistent theory $B$, which proves that the algorithm terminates? If it is, is there such a case for a polynomial-time algorithm?

No (assuming $f$ is computable).  By $ω$-consistency, the $O(f(n))$ bound is correct, so some $c f(n)$ bound is correct, and we can add $c f(n)$ bound (which is $Π^0_1$) as an axiom to a constructive theory.


Sum of products with bounded coefficients The following lemma is not hard to prove.

Lemma : Let $c_1 \neq c_2 \neq \dots \neq c_r \in [n]$ and $k \in [n]$. If $m_1, m_2, \dots, m_r$ are integers (some of them might be negative) such that $m_1c_1 + m_2c_2 + \dots + m_rc_r = k$, then $\exists$ integers $m'_1, m'_2, \dots,m'_r$ satisfying $m'_1c_1 + m'_2c_2 + \dots + m'_rc_r = k$ such that $|m'_1|+|m'_2|+\dots+|m'_r| \leq poly(n)$. Here $poly(n)$ means $n^c$ for some positive constant $c$.

I am guessing that the above lemma is well known. I am looking for a reference of the above lemma and the best possible bound for $poly(n)$.

An $O(n^2 \log r)$ bound can be obtained by Bézout's lemma:

  Lemma. For every integers $0 < c_i \leq n$, $\gcd(c_1,\ldots,c_r) = \sum_i m_i c_i$ for some integers $m_i$ with $|m_i| \leq n \log r$.

This lemma is obtained by recursively applying Bézout's lemma on two variables and the identity $\gcd(x_1,x_2,x_3) = \gcd(\gcd(x_1,x_2),x_3)$.

Without loss of generality assume that $\gcd(c_1,\ldots,c_r) = 1$ by dividing $\gcd(c_1,\ldots,c_r)$ on both sides of $\sum_i m_i c_i = k$. By Bézout's lemma there exists integers $m_i$ with $|m_i| \leq n \log r$ such that

$$k \cdot \sum_i m_i c_i = \sum_i (k \cdot m_i) c_i = k \cdot 1 \text,$$

by observing $k = O(n)$ we have the desired $m'_i = k \cdot m_i$ with $|m'_i| = O(n^2 \log r)$.

If you are searching for literature, the keyword is inhomogeneous linear Diophantine  equations, that is the equation $\sum_i m_i c_i = k$ when $k = 0$. For the homogeneous one, one can obtain a linear bound on $|m_i'|$, see e.g. this or this paper. As for the inhomogeneous one, I have not yet found such a result; however this paper seems relevant.


The Overfull conjecture in graph theory and $coNP$ I am not good at complexity, but got a possible
relation between a plausible conjecture in graph
theory and $coNP$.

Graph $G$ is Class 1 if it can be edge colored
with $\Delta(G)$ colors, otherwise it is Class 2 and
can be edge colored with $\Delta(G) + 1$ colors.

The Overfull conjecture (OC)
asserts

  A graph G with $\Delta (G) \geq n/3$ is class 2 if and only if it has an overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$.

Assume OC and $\Delta (G) \geq n/3$.

This means that we have short certificate if $G$ is Class 1
or Class 2.

For Class 1 the certificate is $\Delta(G)$ edge coloring finding it is in $NP$.

For Class 2 the certificate is overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$ and finding it is in $NP$.

This means there are no $coNP$-hard problems in this case.

There is a reduction from SAT to edge coloring
$3$-regular graphs. Encoding unsatisfiable CNF
to edge coloring is UNSAT and UNSAT is in $coNP$.

  Question:  Does the overfull conjecture and reduction
  from SAT to edge coloring $G$ with $\Delta (G) \geq n/3$
  imply $NP=coNP$?

According to a paper
edge coloring is NP-complete (possibly minor abuse of terminology) for
$r$-regular graphs for any fixed $r \ge 3$ and it gives reduction
of $G$ to $r$-regular $G'$.

Positive answer might help for counterexample to the
overfull conjecture.

$\Delta(G)$ is the maximum degree and $n$ is the number of
vertices.

EDIT Special cases of OC are proven.

According to Overfull Conjecture for Graphs with High Minimum Degree,
Michael Plantholt:

  we show that any (not necessarily regular) graph $G$ of even order $n$ that has sufficiently high minimum degree $\delta(G) \ge (\sqrt{7}/3) n$  has chromatic index equal to its maximum degree providing that $G$ does not contain an
  "overfull" subgraph, that is, a subgraph which trivially forces the chromatic
  index to be more than the maximum degree. This result thus verifies the
  Overfull Conjecture for graphs of even order and sufficiently high minimum
  degree.

EDIT 2
This paper p.2
might be related since it claims unless $NP=ZPP$, one can't
approximate $\chi'(L^k(G))$ where $L^k(G)$ is the $k-th$ power of
the line graph of $G$. (might be wrong on this since $\chi'$ is either
$\Delta$ or $\Delta+1$).

For the possible reduction you are mentioning, if you find such a reduction from SAT to this particular edge-coloring problem, and additionnally you assume OC, then it would indeed mean  NP $=$ co-NP. However, it would be very surprising:   it would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable.
This seems quite unlikely to reach with a simple construction.


Inference in typed lambda calculus theories I'd like to do automated inference, say solving word problems or reducing to normal form, in an equational theory of the typed lambda calculus (with product and unit types). Equivalently, in category-theoretic language: I'd like to do inference in a cartesian closed category presented by a finite set of generators and relations. I would be interested in any references on this topic.

I understand that inference in this setting is generally undecidable. However, I wonder whether there is any literature that either gives useful conditions under which exact inference is possible or proposes heuristic algorithms for approximate inference.

At least the problem of whether 2 terms are equal modulo the theory of Cartesian Closed Categories (or $\beta\eta$ conversion) is decidable, because (in part) of the normalization property.

Another, more categorical way to see this is by extracting a conversion algorithm through normalization by evaluation which gives decision procedures for equality in categories which can naturally be embedded in the presheaf or sheaf category over sets.

See e.g. Altenkirch, Dybjer, Hoffmann & Scott, Normalization by Evaluation for Typed Lambda Calculus with Coproducts

for the version with products and coproducts (the version for just CCCs without coproducts can be found in the references).

An account which gives examples of implementations can be found here.

Solving more complex questions than conversion, or solving conversion questions in the presence of datatypes like the natural numbers becomes undecidable rather quickly. I'm not aware of much work on algorithms for such systems, which I would be interested in as well. One could try simply encoding the equational theory into a first-order logic prover like Vampire, but I don't know how well that would work. It would be an interesting experiment!