Complexity of the Fisher-Yates Shuffle Algorithm This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).

In each iteration i, a random integer is chosen between 1 and i. Simply writing the integer in memory is O(log i), and since there are n iterations, the total is

O(log 1) + O(log 2) + ... + O(log n) = O(n log n)

which isn't better the the naive algorithm. Am I missing something here?

Note: The naive algorithm is to assign each element a random number in the interval (0,1) , then sort the array with regard to the assigned numbers.

I suspect that here, like in most algorithms work, the cost of reading and writing $O(\log n)$ bit numbers is assumed to be a constant. It's a minor sin, as long as you don't get carried away and collapse P and PSPACE by accident.


BSP, but with curved surfaces (NURBS? kernelized support vectors?) Let's say that I wanted to use a BSP not just for partitioning points, but also to define surfaces, i.e. that I have $\mathbb{R}^2$ and I want to be able to continuously map at least some easily known/calculated continuous subset of it to the points on the surface at every branch. Let's furthermore say that I wanted those surfaces to be curved.

I could arbitrarily approximate curved partitioning surfaces by using a helluva lot of straight planes ala the classic BSP, but that seems silly.

Is there prior art in using NURBS or kernelized support vectors or whatever to define smooth curved surfaces in a binary space partitioning tree s.t. extraction of some of the boundaries' points from the representation (enough to illustrate the boundary) is easily (and preferably deterministically, avoiding monte carlo methods) accomplished? Or is this one of those trivial knowledge-synthesis problems and I'm better off just winging it? If not, could someone please point me in the right direction?

You can absolutely do it with kernelized support vectors.  I don't have a publication handy but I've implemented it myself before.  You'll probably want to use quadrics for the split planes, and unfortunately I only found a suboptimal way to do csg (Naylor's original bsp/csg algorithm from 1990); there may be a better way.  But it's very possible, and allows for a couple really interesting things:

ray segment/quadric bsp intersection tests can be done extremely effectively with the following procedure: first, early exit if the two points are not in the same node, then ray-march using the signed distance from the nearest quadric hyperplane, which is easy to compute by traversing the tree.  This becomes very efficient, especially for certain smoother shapes, because the trees tend to be very shallow.
you can fit the hyperplanes to a sampling of a signed distance function by using linear least squares.  Recursively split until all sample points are in the same node of the tree and the mean square error of the signed distance to the shape is below a certain tolerable level, at each stage using least squares to optimize the coefficients of the quadric split.

as implied in (1), determining whether one point is accessible from another reduces to determining whether they are in the same node of a very shallow tree, useful for 3d blob detection and such.

As far as the implementation, it really is simple, as you have hinted.  Just use a few more coefficients in the hyperplanar equation for each node, and the rest will flow.   But if you want to look at my implementation, it's somewhere buried in my github (vpostman).


Bounded depth probability distributions Two related questions about bounded depth computing:

1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem simpler we can assume that all p(i)s are 0,1, or 1/2. or even that all of them are 1/2.)

Now you make a bounded number of computation round. In each round you apply reversible classical gates on disjoint sets of bits. (Fix your favorite set of universal classical reversible gates.)

At the end you get a probability distribution on strings on n bits. Are there results on restriction of such distributions?

I am looking to something analogous to Hastad switching lemme, Boppana result that the total influence is small or LMN theorem.

2) The same question as 1) but with bounded depth quantum circuits.

There are some relatively recent papers by Emanuele Viola et al., which deal with the complexity of sampling distributions. They focus on restricted model of computations, like bounded depth decision trees or bounded depth circuits.

Unfortunately they don't discuss reversible gates. On the contrary there is often loss in the output length. Nevertheless these papers may be a good starting point.

Bounded-Depth Circuits Cannot Sample Good Codes

The complexity of Distributions


Menagerie of polygons UPDATE

Now community wiki.  My new version of the question is: let's make a big list of classes of polygons.  We may be able to produce the most comprehensive list on the web, or in the literature. If there is community interest, after Jan 1st I will organize the information from all the answers into a post on the community blog.

ORIGINAL QUESTION BELOW

  Could you recommend a source, either in print or online, for a menagerie of polygons?  An extensive/exhaustive list of classes of polygon?

The Wikikpedia article on polygons provides a partial classification, but I would like something more complete.  Also, I am not concerned about how to name a 90-sided figure.  Rather, I am trying to find a list of classes that contain infinitely many figures each (examples: star polygon, isothetic polygon).

For example: actual words for "looks like a spider," "would look like a football if it were smoothed out," and so on.

I've already checked The Geometry Junkyard and several pages of a Google search, but perhaps I didn't know what to look for.

Thanks very much.

I think(?) I [Joe O'Rourke] was the first to introduce monotone mountains, but perhaps I copied
that class from someone else.  It is a subclass of monotone polygons, with one of the
two chains that constitutes a monotone polygon a single segment.
I used it in the paper,
"Vertex pi-lights for monotone mountains,"
9th Canad. Conf. Comput. Geom., Aug. 1997, pp. 1-5.

Joe Mitchell subsequently used this class of polygons in his abstract,
"Triangulating Monotone Mountains,"
AMS 345/CSE 355 (PDF link).


The length of non perfect binary 1 error correcting codes I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other $n$ too. My motivation is completely theoretical and is related to graph theory.

Here is a table of the best known (linear and non-linear) binary codes for distance 3, for $n \leq 512\,$. Distance 3 is equivalent to being able to correct one error. The table only gives you the number of codewords, but the references given in the table will tell you how to construct the codes themselves.

The best known codes for $n$ not in this table can be found by taking the code for the next larger $n$ in the table, repeatedly choosing a coordinate, and retaining only those codewords which have $0$'s (or $1$'s) in that position. You can delete $\ell$ coordinates and retain a $2^{-\ell}$ fraction of the codewords.


What hierarchies and/or hierarchy theorems do you know? I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, from theology and sociology to biology and chemistry. Seeing that the amount of information is vast, I hope that I could ask for some help by this community. Of course, I don't want you to do a bibliographic search for me, but rather I am asking for two kinds of information:

Hierarchies and hierarchy theorems that are the result of your work or the work of your colleagues or other people you are familiar with and you think that are not that well known. This could be for example a hierarchy theorem for an obscure computation model that you're interested in or a hierarchy of specific classes, e.g. related with game theory.
Hierarchies and hierarchy theorems that you deem absolutely necessary to be included in a survey of this kind. This would probably be known to me already, but it would be useful to see what hierarchies you consider more important and why. This could be that of the kind "I deem $PH$ very important because without it we wouldn't be able to do this kind of research" or "Although not so well known, in logic-based TCS we constantly use this hierarchy and I deem it an important tool." . And yes I do believe that people from logic have a lot of hierarchies to mention, however keep in mind we are talking about hierarchies of problems.

I will keep an updated list here:

$DTIME$ Hierarchy
$NTIME$ Hierarchy
$SPACE$ Hierarchy
Arithmetical (also known as Kleene) Hierarchy
Hyperarithmetical Hierarchy
Analytical Hierarchy
Chomsky
Hierarchy
Grzegorczyk hierarchy
and the related: Wainer hierarchy
(fast-growing) , Hardy hierarchy
(slow-growing) and the Veblen
hierarchy
Ritchie's hierarchy
Axt's hierarchy (as defined in Axt63)
The Loop Hierarchy (defined in MR67)
$NC$ ($AC$,$ACC$) Hierarchy
The depth hierarchy, as defined in Sipser83
Polynomial Hierarchy ($PH$) and the less refined Meyer-Stockmeyer hierarchy (no dinstinction between quantifiers)
Exponential Hierarchy ($ELEMENTARY$)
$NP$-Intermediate hierarchy
(Ladner's theorem)
The not-so-sturdy $AM$ (Arthur-Merlin)
The $W$ (Nondeterministic Fixed-Parameter) hierarchy and the related Alternating W hierarchy ($AW$-hierarchy) and $W^{*}$-hierarchy (W with Parameter-Dependent Depth)
Counting Hierarchy
Fourier Hierarchy
Boolean Hierarchy (over $NP$) , also equal to the Query Hierarchy (over $NP$)
Hierarchies for property testing, as seen in GoldreichKNR09
The dot-depth hierarchy of star-free regular languages
$BP_{d}(P)$ : The classes solvable by polynomial size branching programs, with the additional condition that each bit of the input is tested at most d times, form a hierarchy for different values of $d$
The time hierarchy for Circuit Complexity
The polynomial hierarchy in communication complexity

Note: If you do not want to be mentioned exclusively, please say so. As a rule of thumb, I will mention both the community and also the specific person that brings new information to light.

The Fourier Hierarchy as defined in "Yaoyun Shi, Quantum and classical tradeoffs."

From the complexity zoo:

  $\mathsf{FH}_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with $k$ levels of Hadamard gates and all other gates preserving the computational basis.

  $\mathsf{FH}_0 = \mathsf{P}$
  $\mathsf{FH}_1 = \mathsf{BPP}$
  $\mathsf{FH}_2$ contains factoring because of Kitaev's phase estimation algorithm.

  It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, $\mathsf{FH}_k$ is strictly contained in $\mathsf{FH}_{k+1}$).


A graph parameter possibly related to treewidth I am interested in graphs on $n$ vertices which can be produced via the following process.

Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as unused.
Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more  unused vertices in $G$, and is not connected to any used vertices in $G$. Label $v$ as unused.
Label one of the vertices in $G'$ to which $v$ is connected as used.
Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.

Call such graphs "graphs of complexity $k$" (apologies for the vague terminology). For example, if $G$ is a graph of complexity 1, $G$ is a path.

I would like to know if this process has been studied before. In particular, for arbitrary $k$, is it NP-complete to determine whether a graph has complexity $k$?

This problem appears somewhat similar to the question of whether $G$ is a partial $k$-tree, i.e. has treewidth $k$. It is known that determining whether $G$ has treewidth $k$ is NP-complete. However, some graphs (stars, for example) may have much smaller treewidth than the measure of complexity discussed here.

4th October 2012: Question cross-posted to MathOverflow after there was no conclusive answer after a week (though thanks for the info about causal flows).

Though we've chatted about this in person before, I'll add this in the hope that this will allow someone else to provide a complete answer.
In your process of adding vertices, define a partial function $f:V(G) \rightharpoonup V(G)$ from each vertex $v$ which gets used, to the vertex which was added when $v$ got used. Then it turns out that $f$ is a (causal) flow function (p. 39), which is a restricted version of a path cover. Indeed, your description of these graphs of "complexity k" (given a set of vertices which are to be the initially unused vertices, and the final unused vertices) is precisely the star decomposition of a "geometry" with a causal flow (p. 46 of the above article).
Although these "causal flows" have been studied mainly in the context of (measurement-based) quantum computation — where they are motivated by certain structures of unitary circuits — there are graph-theoretic results about them which are totally divorced from quantum computation:

Uniqueness modulo endpoints: the graphs with " complexity $k$ " are precisely those for which there exist (possibly intersecting) sets $S,T \subseteq V(G)$, both of size $k$, such that $G$ has exactly one path cover of size $k$ whose paths start in $S$ and end in $T$.
Extremal graphs: A graph on $n$ vertices which has "complexity $k$" has at most $kn - \binom{k+1}{2}$ edges.

Using these results, and given a candidate pair of sets $S,T$, determining whether or not they "subtend" a unique path cover in this way can be determined in time $O(k^2 n)$; but finding whether or not such sets of endpoints exist that is the apparent difficulty, and the extremal result above (which is only a necessary condition) seems to represent the state of the art in efficient criteria to determine whether such sets exist.


$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$? Can this statement be confirmed or disproved:

  $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$

[Question changed to use Kaveh's brilliant formulation.]

Here the NDTM must "outrun" the DTM.

This seems similar to the PvNP question, but I'm not sure...

Thanks!

EDIT: This question seeks an inequality between the run time of polytime DTM deciders and their corresponding NP verifiers. If k=1, the proposition fails (e.g.: determining parity requires n steps on a TM and therefore a verifier cannot take any shortcuts). But if k>=2 ...?

I wonder if the statement can be disproved without leading to any major or unexpected complexity class separations... Is there a diagonalization argument that could work here.

It seems to me that you are not familiar with the basic complexity theory and therefore your question is probably not suitable for cstheory.

You probably mean to ask if the following statement is true:

  $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$.

Note that the $\mathsf{NTime}$ hierarchy theorem is tight. If the answer to your question was positive then it would separate $\mathsf{NTime}$ from $\mathsf{DTime}$ which is not known as explained in the answers to the question linked by Robin.


Generalization bound for parameters rather than loss functions I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and the estimated parameters for model classes such as that comprising of logistic regressions? As an example corresponding to linear regression, see below:

For the full proof of the aforementioned example see Thm. 2.2 on pgs 36 and 37 here: https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/lecture-notes/MIT18_S997S15_CourseNotes.pdf. I think this is a special case because they're able to make use of linearity and sub-gaussian assumptions. I was wondering if a similar bound could be obtained for Logistic Regression parameters, or alternatively, are there any other classification models for which similar results could be obtained?
I know learning theory gives us risk bounds. Are there certain settings wherein those risk bounds translate to bounds on the deviations in estimated and true parameters? Saw a similar (but more specific) question in math stackexchange without any answers: https://math.stackexchange.com/questions/3846492/generalization-error-in-logistic-regression. Is this simply impossible to ask for in the agnostic setting for general model classes? Can we hope to get such results for specific model classes, under specific assumptions (eg: the parameter space being compact)? Any related literature? Any insights would be appreciated.
P.S: I don't mean the number-of-iteration based bounds obtained in optimization settings, i.e. computation error, here I am referring to estimation error

See our recent paper:
"Non-parametric Binary regression in metric spaces with KL loss"
https://arxiv.org/abs/2010.09886
The setting is actually non-parametric and quite general. Our loss measures the expected log-likelihood -- which is more natural in the context of logistic regression than distance in parameter space. Notice that our loss is unbounded, as would be the $\ell_1$ or $\ell_2$ loss in parameter space.


Computational complexity of learning (classification) algorithms - fitting the parameters My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume anything about its distribution (it may be symmetric or very skewed). In statistics, we choose a predictive model and fit its parameters. What is the time complexity of fitting

naive Bayesian classifier
logistic regression
$k$-nearest neighbor classifier
SVM
$\ldots$

I understand that in some cases additional parameters or assumptions about the data (types of variables) are required. These parameters can be of course incorporated in your answer. Thank you very much!

"Training" a naive bayes classifier, assuming you're given the feature vectors, is $O(n)$, where $n = \sum_i nnz(x_i)$, where $nnz(x_i)$ is the number of nonzero features in data point $i$.

For logistic regression you have to solve an optimization problem, and this depends on the optimizer. With L-BFGS an iteration takes linear time on the size of the training set and I've never needed more than 100 iterations to converge to a reasonable value (but I'm not aware of any worst-case bounds).

For the $k$-nearest neighbor classifier there is no training, but classifying has a high cost, and depends on the search algorithm you're using. For linear search the complexity is (for fixed k) proportional to the size of the training set for each point you want to classify. With approximate algorithms this can be brought down considerably at the expense of accuracy.

For svms standard quadratic-programming solvers are $n^3$, but recent approaches are inverse in the size of the training set. More information in this quora answer.

If you really need fast learning the best approaches so far are those based on online learning, which can converge to classifiers that compete well against batch classifiers with only one pass over the training data. A very fast implementation is vowpal wabbit and a good algorithm is confidence-weighted learning.


Chomsky hierarchy for tree structures I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.

Is there a similar hierarchy for grammars/parsers which are specifically taylored for nested words or trees?  In particular, this hierarchy should include tree automata, perhaps streaming tree automata, the algorithms used to apply CSS rules...

As I am planning to implement parsers for one/some of the steps in the hierarchy, I am very interested also in the algorithmic complexity of parsers for those grammars.  I might use this as a basis for a CSS-like functionality in LaTeX.

For tree automata, you have the Mostowski hierarchy, which is about the complexity of acceptance condition: each level is of the form $(i,j)$ with $i\in\{0,1\}$ and $i\leq j$. Being at level $(i,j)$ means that there is a parity automaton using parities from $i$ to $j$ recognizing the language. For more on parity condition, see here: https://en.wikipedia.org/wiki/%CE%A9-automaton. This hierarchy exists in 3 versions: deterministic, nondeterministic, or alternating, depending on the model of automaton you are looking at (although the deterministic hierarchy does not cover all regular languages).

There is an other hierarchy called Wadge hierarchy, with a more topological flavour, but it is getting further from complexity of acceptors: http://en.wikipedia.org/wiki/Wadge_hierarchy


Complexity of counting paths in a graph Given a directed graph with n nodes such that each vertex has exactly two outgoing edges, and a natural number N encoded in binary, two vertices s and t,

I want to count the number of (not necessarily simple) paths from s to t within N steps.

Is this a #P-hard problem? Or generally, what's the complexity of this problem?

The output number of paths may be $\Omega(2^N/n)$ (choose $s$ arbitrarily and then choose $t$ as the vertex that is the endpoint of the largest number of the $2^N$ walks from $s$) which requires $\Omega(N)$ bits to write down explicitly; this is exponential in the input size. On the other hand, the matrix powering approach has complexity polynomial in the sum of the input and output sizes. So that seems to place it squarely in the class of counting problems that have exponential-sized output and may be solved deterministically in time polynomial in their output size, whatever the notation for that class is (it's some sort of counting analogue for EXP, and definitely not #EXP which is more analogous to NEXP).


Serial and parallel neural network The question is:  can exist a parallel or serial neural network or someone talked about this?
For explanation, in the network a single record in a data set enter in the input layer as a value between 0 and 1, but, could i interpretate the value parallely as an array of bits (so i need an input layer as large as the number of bits composing the value) or even serially? or this is a bad technic?

Imagine a number (es. 5) that is interpretated as an n-bits values (101) in a 3-way input layer instead of a degree (0,?) in a 1-way input layer.

I'm a novice in neural network and the question could be stupid. Sorry if it is.

Yes, of course you could do that.  Whether it is useful will depend on the task.  I'd suggest spending some quality time on tutorials/classes on neural networks, and then spend some time experimenting with different network architectures to see how the choice of feature vector affects the performance of the network.


Amplitude of Random Cubic Graphs Consider a connected random cubic graph $G=(V,E)$ of $n =|V|$ vertices, drawn from $G(n, 3$-reg$)$ (as defined here, i.e. $3n$ is even and any two graphs have the same probability).

Of course there are $n$ possible Breadth First Searches, one for each starting node $s \in V$. A Breadth First Search $B_G$ starting at node $s \in V$ assigns a level $d(s, v)$ to each node $v \in V$, where $d(s, v)$ is the distance between $s$ and $v$ in $G$.

Let us say that such a Breadth First Search $B_G$ also assigns a level
$$ L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$$
 to each edge $e=\{u,v\} \in E$.

Given a specific Breadth First Search $B_G$, let $\alpha(B_G,i)$ be the number of edges that have been assigned level $i$, and let $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$. In other words $\alpha(B_G)$ is the number of edges of the level containing more edges than any other level. Finally, let $\alpha(G)$ be the maximum $\alpha(B_G)$ for any of the $n$ Breadth First Searches of $G$.

Let us call $\alpha(G)$ the amplitude of $G$.

  Question

  How does the expected value of $\alpha(G)$ grow as $n$ tends to infinity? Recall that $G$ is random cubic. More precisely, what I really would like to know is whether the expected value of $\alpha(G)$ belongs to $o(n)$.

Since $n$ is even, the limit is considered so that I don't care of odd $n$'s.

The amplitude $\alpha(n) = \Theta(n)$  for expander graphs. A random 3-regular graph is asymptotically almost surely an expander graph (see Wikipedia), so the expectation of the amplitude will be $\Theta(n)$, since the probability that it's not an expander graph goes to $0$ as $n$ goes to $\infty$.

For an expander graph with parameter $\beta$, for any set of $s$ vertices with $s \leq n/2$, there are $\beta s$ neighbors of the set. Now, let the number of vertices on level $j$ be $\ell_j$, with $\ell_0=1$. We then have from the expansion property that as long as $j$ is not too large (i.e., we haven't included half the vertices yet)
$$
\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}
$$
Now, look for the level $\ell_j$ which contains vertex $\frac{n}{3}$. That is, so $\sum_{i=0}^{j-1} \ell_i < n/3$ and $\sum_{i=0}^{j} \ell_i \geq n/3$. If this level is large, i.e., $\ell_j \geq n/6$, we are done. Otherwise, the next level has size
$$
\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},
$$
and we are done.

While this proof looks at the number of vertices in a level rather than the number of edges (which the OP asked about), there are always at least as many edges added in step $i$ as vertices in level $i$, since each vertex must be reached by some edge.


Consequences of $BQP \subseteq P/poly$? While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{poly}$. What complexity-theoretic consequences would such an inclusion have?

Adleman's theorem is sometimes called "the progenitor of derandomization arguments." $\mathsf{BPP}$ is believed to be derandomizable, whereas there is no evidence that the "quantumness" of $\mathsf{BQP}$ could somehow be removed. Is this possible evidence that $\mathsf{BQP}$ is unlikely to be in $\mathsf{P}/\text{poly}$ ?

I'd say we have no good reason to think BQP is in P/poly.  We do have reasons to think that BQP is not in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP.  E.g., if BQP⊂P/poly then Factoring is in P/poly, which is enough to break lots of cryptography according to standard security definitions.

Also, as you correctly point out, there's no quantum analogue of Adleman's trick---indeed, there's no way to "pull the quantumness out of a quantum algorithm," analogous to how one can pull the randomness out of a randomized algorithm.  So I don't think anyone has a guess for what the P/poly advice for simulating a quantum computer should even consist of (any more than they have a guess, say, in the case of NP vs. P/poly).

A final note: my work with Alex Arkhipov (and the independent work of Bremner-Jozsa-Shepherd), can easily be adapted to show that if QUANTUM-SAMPLING is in P/poly (OK, in "BPP-SAMPLING/poly"), then P#P⊂BPPNP/poly, and hence the polynomial hierarchy collapses---in this case, I think, to the fourth level.  At present, though, we don't know how to adapt this sort of result from sampling problems to decision problems.


Does an infinitely long tape make any difference when proving theorems about Turing Machines? Standard accounts of Turing Machines in the literature assume an infinitely long tape in at least one direction (and indeed infinitely time long to perform its computations). Clearly in practice no computer could have an infinite amount of cell storage either from the commencement of computations (even if we disregard the infinite amount of available time) or by adding blank cells at the end of the tape as required (which we'll eventually need if we assume infinite amount of time).

So my question is this: do the properties about Turing Machines obtained by assuming an infinitely long tape still hold of practical computing devices, for instance the existence of uncomputable functions? If so what does the assumption of an infinite tape buy us in terms making it easier to prove such properties?

Yes it makes a huge difference!  A Turing machine with a finite tape is just a finite automaton, which we know are much less powerful.  For example, a TM with a finite tape cannot compute a context free grammar.  All of this is in theory, of course.


Expected Kolmogorov complexity under Kolmogorov complexity distribution If $K(w)$ is the Kolmogorov complexity of a string $w$, where programs are prefix-encoded so $\sum_{w} 2^{-K(w)} \leq 1$, what is

$$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} K(w)}{\sum_{|w|=n} 2^{-K(w)}}?$$

Also, what is

$$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} \frac{K(w)}{n}}{\sum_{|w|=n} 2^{-K(w)}}?$$

The distribution here is closely related to the "universal distribution".
The second limit would say whether $\Theta(|w|)$ is an approximation for $K(w)$.

If $\alpha$ is the answer to the 1st question then $\alpha=\infty$. Namely, for any  $c $  there is an $n $ such that all strings $w $ of length at least $n $ have $K (w) \ge c$. In particular the expectation of $K (w) $ with respect to any distribution on strings of length $n $ is  $\ge c $.

Similarly if $\beta$ is the answer to the 2nd question then $0\le\beta\le 1$, since
$$
(\exists c)(\forall w)(K(w)\le |w|+2\log |w| + c),
$$
but I don't know exactly what $\beta$ is.


Proof assistant usage in complexity theory research? Considering the topics covered at a conference like STOC, are any algorithm or complexity researchers actively using COQ or Isabelle? If so, how are they using it in their research? I assume most people wouldn't use such tools because the proofs would be too low level. Is anybody using these proof assistants in a way that is critical to their research, as opposed to a nice supplement?

I am interested because I might start learning one of those tools and it would be fun to learn about them in the context of proofs of reductions, correctness, or run time.

A general rule of thumb is that the more abstract/exotic the mathematics you want to mechanise, the easier it gets. Conversely, the more concrete/familiar the mathematics is, the harder it will be. So (for instance) rare animals like predicative point-free topology are vastly easier to mechanize than ordinary metric topology.

This might initially seem a bit surprising, but this is basically because concrete objects like real numbers participate in a wild variety of algebraic structures, and proofs involving them can make use of any property from any view of them. So to be able to the ordinary reasoning that mathematicians are accustomed to, you have to mechanize all these things. In contrast, highly abstract constructions have a (deliberately) small and restricted set of properties, so you have to mechanize much less before you can get to the good bits.

Proofs in complexity-theory and algorithms/data-structures tend (as a rule) to use sophisticated properties of simple gadgets like numbers, trees, or lists. Eg, combinatorial, probabilistic and number-theoretic arguments routinely show up all at the same time in theorems in complexity theory. Getting proof assistant library support to the point where this is nice to do is quite a lot of work!

One context where people are willing to put in the work is in cryptographic algorithms. There are very subtle algorithmic constraints in place for complex mathematical reasons, and because crypto code runs in an adversarial environment, even the slightest error can be disastrous. So for example, the Certicrypt project  has built a lot of verification infrastructure for the purpose of building machine-checked proofs of the correctness of cryptographic algorithms.


How do you argue a query is impossible in a query language like SPARQL or SQL? I've been investigating the ability of the SPARQL query language to represent certain basic tasks in graph theory and machine learning, and have come to believe that it is not possible to do some. For example, I suspect that it is not possible to test (s,t)-connectivity without using Property Paths (but simple with them).  Also, I suspect that it is not possible to list the k nearest neighbors of a list of vectors with a single query.

Is there a proof technique or general approach to show, or at least provide some evidence, that a search or decision problem cannot be represented as a single query in a query language like SPARQL or SQL?

From page 52 of Leonid Libkin's Elements of Finite Model Theory textbook:

  Since we know that graph connectivity is not Hanf-local and transitive closure is not Gaifman-local, we immediately obtain, without using games, that these queries are not FO-definable.

SQL and (original) SPARQL are based on fragments of first-order logic, without fixed-point or transitive-closure operations.  The basic idea is that first-order formulas can only express things that are "local" in some sense, with the reach of locality increasing with the length and complexity of the formula.  (The definitions of Gaifman and Hanf locality make this precise.)  Transitive closure and graph connectivity require either a more powerful way of talking about arbitrarily long paths (like property paths in (new) SPARQL, or a fixed point operator), or arbitrarily long formulas.  So one can't capture path expressions of arbitrary length without explicitly adding support for them to a first-order-based query language.

If you want to know more, have a look at the above textbook, or at the paper:

Leonid Libkin, Logics capturing local properties, ACM Transactions on Computational Logic 2, 135–153, 2001.  doi:10.1145/371282.371388

which has a brief overview of the history with further references.


What are the algorithms and the data structures for GUIs and input management? I'm studying how, given:

an input from the user ( like a click of the mouse or the input from a key )
a well defined data structure that represent the graphical layout inside a window ( a tree/graph like structure for now )

I could possibly create what is generally called as a "G/UI toolkit", which means that I should be able to create a responsive UI and a mapping between the input from the user and the functionality given to the UI itself.

I found absolutely no paper, no technical explanation, no articles, about both the data structure and the algorithms used to perform this kind of mapping, and I'm wondering if someone could help me with this.

I found some sparse reference to some tree-like data structure like kd-tree or quadtree that are used to subdivide the 2D space in the window and so when the signal will be fired, the coordinates generated by the signal, the click of a mouse, will be injected in the tree to find the corresponding widget to activate.
This approach feels really old and I don't think it will scale that well.

I also found some reference to what is called the third generation of rasterizers and UIs which seems to be based on linear algebra/vectors and sounds really nice because it's highly scalable and simple to reason about, the problem is I can't see any implementation or algorithms or data structures.

Someone can point me in the right direction ?

I'll first restate your question, and then try to answer it. As I understand it, the question you are trying to answer is, "if I have a scene graph/widget tree, and I get an event, how can I figure out how to dispatch that event to the appropriate subnodes of the tree?"

The answer is that the data structures you have outlined are not sufficient by themselves to do the job; you need a bit more information.

The primitive events the OS produces tell you the positions of the mouse, and the scene graph gives you a logical decomposition of the structure of the GUI. Therefore, you need some additional data structures to translate between the widget tree and what it looks like geometrically.

The simplest case is when every widget is an axis-aligned rectangle. What you do then is:

Every widget node stores its position and shape.
In addition to the widget tree, you keep  a separate doubly-linked list storing all of the clickable widgets in their z-order, so that the widget which is visually "on top" is at the head of the list.
You also keep track of the current mouse position (you have to do this anyway, because the OS only gives you relative position changes).

When an event occurs, what you do is:

When an event occurs you iterate through the z-order list, doing a simple hit test for the bounding box of each widget.
The first time the hit test succeeds, you know where the event occurred, and can do event dispatch.

With fancier graphics geometry (say with vector graphics), each widget will store a data structure representing the shape, and your hit test gets more complicated to match. The things to Google for:

"collision detection" or "hit detection".
"spatial indices" -- often these data structures are variants of quadtrees and the like. It really does work pretty well, even though the geometric data can be quite large, because user events are generally relatively infrequent.


Hardest optimization problems in NC When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy to understand algorithms. However, the decision version of LP is $\mathsf{P}$-complete. This suggests that it is one of the hardest problems we can solve in polynomial time.
Under the assumption that $\mathsf{NC} \neq \mathsf{P}$. What is the 'hardest' natural kind of optimization problems with decision problems in $\mathsf{NC}$?
If this is too vague, then we can restrict to restrictions. What is the minimal set of restrictions we need to place on linear programs (or more generally: convex programs) to allow the decision problem associated with the restricted programs to be solvable in $\mathsf{NC}$?

Motivation
To a large extent, this is idle curiosity. However, it was brought about by Cosma Shalizi's "In Soviet Union, Optimization Problem Solves You". In particular, if LP is too difficult to solve to have a centralized economy (i.e. optimizing in $\mathsf{P}$ is asking too much), then any decentralized system must be doing some sort of parallel processing faster than poly-time (for me: $\mathsf{NC}$).

Are you aware of the work on positive LPs/SDPs? There are a bunch of results in the area, mostly along the lines of "if the constraints of the LP/SDP are positive, then the problem can be solved in NC."

Some important references in this line of work are Luby-Nisan 93 and Jain-Yao 11. Another excellent resource is this slide of Rahul Jain's talk at the "Recent Progress in Quantum Algorithms" conference at IQC. The entire talk is available on youtube.


Two way deterministic multihead counter automata or logspace TM with counter Is that known something about languages recognized by two-way deterministic multihead counter automaton or logspace TM with counter (equivalent model)? This class called Aux2DC in my advisor's paper. Or about such nondeterministic class? I've obtained that class of languages recognized by such nondeterministic maschines includes NL and it seems to be included in LOGCFL. Are there any papers on this subject? Is that result trivial?

A two-way deterministic (nondeterministic) multi-head finite automaton can be simulated by a logspace DTM (NTM), and vice versa.

So, for including class $ \mathsf{NL} $, you do not need a counter!

The value of the counter belonging to a two-way nondeterministic multi-head finite automaton with one-counter can be bounded by a polynomial, otherwise, the computation enters an infinite loop. Since both such a counter and the input heads can be simulated in logspace, $ \mathsf{LOGCFL} $ upper bound can be replaced with $ \mathsf{NL} $.

Note that any language recognized by a two-way deterministic (nondeterministic) one-head finite automaton with one-counter is in $ \mathsf{L} $ ($ \mathsf{NL} $).

There are many papers on these topics, e.g. this paper. You can find more after some googling. (Check also Lemma 1 of this paper.)


Best approximations of Minimum Dominating Sets in chordal graphs I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime here ?
The problem was shown to be $W[1]$-hard for the natural parametrization by Liu and Song in 2009.

The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the Set Cover problem which is NP-hard to approximate within a factor of $(1-\alpha)\cdot N$ where $N$ is the input size [1].
First, we use the standard reduction from Set Cover to Red Blue Dominating Set: Build a bipartite graph with a red and a blue side. The red side corresponds to the sets of the Set Cover instance and the blue side corresponds to the elements of the universe and an edge connects a set $S$ and an element $e$ if $S$ contains $e$. Now selecting a set of red vertices to dominate all blue vertices is the same as selecting the sets of the Set Cover instance to cover the universe. Hence, the reduction is approximation-preserving.
The bipartite graph is of course not chordal and we have a coloring of the vertices but we can now make the red side a clique and forget the vertex colors. We will never select a formerly blue vertex since the red vertices have larger neighborhoods. The resulting graph is a split graph and thus also a chordal graph.
Dana Moshkovitz: The Projection Games Conjecture and the NP-Hardness of $\ln n$-Approximating Set-Cover. Theory Comput. 11: 221-235 (2015)


Primal vs dual decomposition methods I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I understand, that dual decomposition methods often lead to more efficient algorithms.

After reading about decomposition methods on various sources (e.g. see these notes by Stephen Boyd), I don't get the intuition of why this would be the case.

Perhaps an important difference is that, as S. Boyd notes in his slides, in primal decomposition methods:

  the master problem manipulates the primal (complicating) variables

while in the dual decomposition methods, this would not be the case. However, when S. Boyd describes the procedures for primal vs dual methods, the decomposition looks essentially the same:

repeat
   solve the subproblems (presumably on the slaves)
   update complicating variable (presumably on the master)

So my questions are:

Is it true that dual decomposition methods tend to be more efficient in practice than primal methods?  If so, why?
Why does S. Boyd say that in primal decomposition methods, "the master problem manipulates the complicating variables" ? How is this different from the way these variables are handled in a dual decomposition?

Update: Additional background:

Statistical machine learning problems, such as MAP-MRF estimation, arise often in bioinformatics, computer vision and NLP, and are usually formulated as quadratic pseudoboolean problems (i.e. mathematical programming problems with binary and quadratic cost functions) (e.g. (3)).

There seems to be a growing trend in the literature to solve these problems via dual decomposition (as pointed out by the two articles I linked to above: (1), (2)). Moreover, some of these authors have pointed out that there are connections between an important class of inference algorithms, such as belief propagation and other general message passing methods, to dual decomposition (4).

I don't think one can make a blanket statement on whether primal decomposition methods or dual decomposition methods are more efficient. The efficiency is dictated by the structure of the problem; primal decomposition and dual decomposition are ways of exploiting this structure to develop efficient algorithms.

The key aspect in making a choice between these methods is the kind of parametrization the master brings about on the slaves. Fo e.g., sometimes it is convenient (in terms of theory or practice) to have the parametrization in the objective function of the slave problems instead of having it in the constraints. If the parametrization happens to appear in the constraints (and it has suitable structure), one can try to dualize the slave problem to get in the objective.

In the slides you have linked, the effort seems to be in exploiting the structure for parallelization of the solution of subproblems. For parallelization one would require subproblems that are independent of each other. If there is a natural separability in the constraints, dual variables can be used to parametrize the problem and thereby create such subproblems.

Edit: I repeat once again that structure is important in determining the choice of the method. I am still not completely clear on the structure afforded by the problems you have in mind. Based on the information given, this is my best attempt at answering your question.

From the examples you have added, the problems appear to be what can be called "nearly separable". In essence, these problems appear to be variants of the problem $\min \{\sum_{i=1}^n f_i(x_i) : (x_1,...,x_n) \in K\}$, where $K$ is a constraint that has a separable structure. For example, the constraint $(x_1,...,x_n) \in K$ may be $\sum_ix_i =b$, where $b$ is a vector of appropriate size. By separable structure I mean that the optimal values of variables $x_1,...,x_n$ can be chosen independently of each other. If one looks at the problem as a whole, the objective functions are decoupled in individual variables, but because of the coupling in $K$ these variables cannot be independently optimized. However because this coupling in $K$ is mild, one can still salvage separability. Dual decomposition lets you separate the variables when they are coupled in the constraints. If the variables were coupled in the objective, one may have to employ primal decomposition (as in Boyd's slides). One may of course try to reformulate problems to bring them in some or the other form that one is comfortable using.

To demonstrate separation by dual decomposition, define the Lagrangian $L(x,\lambda) =\sum_i f_i(x_i) + \lambda^T(\sum_i x_i)$. If $(x,\lambda)$ is a saddle point of $L$, then $x$ solves the original problem. A dual decomposition method would for each value of $\lambda$, minimize $L(x,\lambda)$ over $x$, altering $\lambda$ until a saddle point is found. The minimization in $x$ is easier, in particular separable and parallelizable.


Function that is guaranteed to be one-way if one-way functions exist? There is an old trick for writing down an algorithm that, if P = NP, solves SAT in polynomial time.  Essentially, one lists all polynomial time machines and multi-tasks over them.

Is there an analogous trick for one-way functions (or even one-way trapdoor functions)?  That is, can we write down a function that, if one-way functions exist, is necessarily a one-way function?

There seems to be no easy way to mimic the P = NP trick.  In that case, we can quickly recognize a solution when we get one.  But if I multi-task over all polynomial time functions, there's no obvious way to recognize a one-way function when I arrive at one.

If the answer to the above question is no, is there some kind of argument why we can't do it?  Maybe writing down such a function would somehow prove that one-way functions exist?

Yes, such a function was found by Levin himself, published somewhat recently:

The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003.


Ways for a mathematician to stay informed of current research in complexity theory Complexity theory is a strong secondary interest of mine but it's not my primary research interest, so there is no hope for me to attend all the conferences, read all the blogs, and ensure that the "in" crowd cc: me on every bit of hot news.  I try to do some of this but I am wondering what methods will give me the most bang for the buck (or rather time, since time is more of a limiting factor than money in this context).  Some methods I have attempted include:

Look over STOC/FOCS proceedings.  This often means I don't hear about breakthroughs until they're (somewhat) old news, but that's O.K. from my point of view as long as I am likely to catch the news eventually.  Are there other proceedings I should be tracking?
Subscribe to the Los Alamos ArXiv.  How many complexity theorists use this?  Are there other preprint servers I should look at?
Read blogs.  I tried this for a while but have more or less given up because there are too many blogs out there and it seems to be a very inefficient method of staying current.

Anything I've missed?  Again my focus is on finding time-efficient methods rather than on doing every conceivable thing to keep abreast.

Edit: Thanks for all the responses; I would accept more than one answer if the software allowed it.  My somewhat arbitrary choice is based on the fact that I now recall having heard of the ECCC and the CCC before, but I was completely unaware of the Blog Aggregator.

In addition to ArXiv, you could subscribe to the Electronic Colloquium on Computational Complexity. It gets a lot of traffic from current research, and the email updates you receive are normally a succinct format of paper title/author(s)/abstract, so you won't have to invest much time to see what's just happened.


Using Indicator Functions as Transfer Functions for Neural Networks Does there exist any theory (other than Cybenko's proof of the Universal Approximation Theorem with sigmoids) advocating the use of indicator functions as transfer functions for machine learning with neural networks?

After having read matus's beautiful answer in this thread explaining (among other things) Cybenko's proof, I wonder: if it weakens the approximation to use sigmoid transfer functions instead of indicator functions, what are the theoretical reasons for not using indicator functions?

As suggested here, perhaps it's because indicator functions have negative implications for generalization.

However, indicator functions are computationally far cheaper to implement than sigmoid functions, and also more closely resemble biological neural networks (ie the brain). Therefore, does there exist any other theory advocating the use of indicator functions as transfer functions for machine learning with neural networks?

Sigmoid functions have clear probabilistic interpretation, so one can derive optimal learning algorithms for them within the bayesian approach. Moreover, they are differentiable, so the gradient descent can be directly applicable.
However, in general, neural networks are "universal approximators" in almost the same sense as, for example, polynomials. They can capture a limited set of regularities. Different activation functions (like different basis functions in functional approximation) will capture different regularities and will have different biases in approximating other regularities.
Thus, what activation functions are better depends on what underlying regularities are presented in data. Indicator functions can surely be better for some tasks. However, no generally applicable (task-independent) theory advocating the use of indicator functions is possible.


Is there any result on approximating an arbitrary tree metric by an HST metric? Is there any known result on approximating an arbitrary tree metric by an HST metric (or an Ultrametric)? What is the distortion? Thanks.

The distortion of embedding any $n$-point metric in  ultrametric is at most $n-1$, and on the other hand, the distortion of embedding the path metric $P_n$ in ultrametric is at least $n-1$.

Similarly, if you are interested in probabilistic embedding, then by Fakcharoenphol, Rao, and Talwar result mentioned above, any $n$-point metric space probabilistically embeds in ultrametric with distortion $O(\log n)$.
On the other hand, the distortion of probabilistically embedding $P_n$ in ultrametric is $\Omega(\log n)$.


Why is linearizability a safety property and why are safety properties closed sets? In Chapter 13 "Atomic Objects" of the book "Distributed Algorithms" by Nancy Lynch, linearizability (also known as atomicity) is proved to be a safety property. That is to say, its corresponding trace property is nonempty, prefix-closed, and limit-closed, as defined in Section 8.5.3. Informally, a safety property is often interpreted as saying that some particular "bad" thing never happens.

Based on this, my first problem is as follows:

  What are the advantages of linearizability as a safety property? Are there some results based on this fact in the literature?

In the study of the classification of safety property and liveness property, it is well-known that safety property can be characterized as the closed set in an appropriate topology. In the paper "The Safety-Progress Classification" @1993 by Amir Pnueli et al., a metric topology is adopted. More specifically, a property $\Phi$ is a set of (finite or infinite) words over the alphabet $\Sigma$. The property $A(\Phi)$ consists of all infinite words $\sigma$ such that all prefixes of $\sigma$ belong to $\Phi$. For example, if $\Phi = a^{+}b^{\ast}$, then $A(\Phi) = a^{\omega} + a^{+}b^{\omega}$. An infinitary property $\Pi$ is defined to be a safety property if $\Pi = A(\Phi)$ for some finitary property $\Phi$. The metric $d(\sigma, \sigma')$ between infinite words $\sigma$ and $\sigma'$ is defined to be 0 if they are identical, and $d(\sigma, \sigma') = 2^{-j}$ otherwise, where $j$ is the length of the longest common prefix on which they agree. With this metric, the safety property can be characterized as closed sets topologically.

Here comes my second problem:

  How to characterize linearizablity as closed sets topologically? In particular, what is the underlying set and what is the topology?

What are the advantages of linearizability as a safety property? Are there some results based on this fact in the literature?

Suppose that you've implemented a shared memory machine $M$ that only satisfies eventual linearization, defined as follows: in every run $\alpha$ of $M$, there exists some point in time $T_\alpha$, such that linearization holds from time $T_\alpha$ on. Note that there is no upper bound on $T$. (*)
 (This is an artificial liveness counterpart of the standard safety property definition of linearizability.)

Such a shared memory implementation wouldn't be very useful to the programmer: Note that if only eventual linearizability holds, there are no guarantees whatsoever on the consistency of read/write operations in any "early" prefix of a run (before the unknown time $T$). Or, in other words, whatever has happened until now, you can still extend the current prefix of a run to one that satisfies eventual linearizability.

(*) If there was such an upper bound, then eventual linearizability would become a safety property.

  How to characterize linearizablity as closed sets topologically? In particular, what is the underlying set and what is the topology?

We can define a metric topology on the set $ASYNC$, which is the set of all possible runs of a distributed algorithms. Note that each run $\alpha \in ASYNC$ corresponds to an infinite sequence of state transitions.
For $\alpha, \beta \in ASYNC$, $\alpha \ne \beta$, we define $$d(\alpha,\beta) := 2^{-N}$$where $N$ is the earliest index where the state transitions in $\alpha$ and $\beta$ differ; otherwise, if $\alpha = \beta$, we define $d(\alpha,\beta) = 0$.

We first argue that $d$ is a metric on $ASYNC$.
By definition, $d$ is nonnegative and $\forall \alpha,\beta \in ASYNC$ we have
$d(\alpha,\beta)=d(\beta,\alpha)$.
For $\alpha,\beta,\gamma \in ASYNC$, the triangle-inequality $d(\alpha,\beta)
\le d(\alpha,\gamma) + d(\gamma,\beta)$ trivially holds if $\gamma=\alpha$ or
$\gamma=\beta$.
Now consider the case that $d(\alpha,\gamma) \ge d(\gamma,\beta) > 0$, i.e.,
$d(\alpha,\gamma)=2^{-n_1}$ and $d(\gamma,\beta)=2^{-n_2}$, for some indices
$n_1\le n_2$.
Since $\gamma$ shares a common prefix of length $n_2-1$ with $\beta$ but only a
prefix of length $n_1-1$ with $\alpha$, it follows that $\alpha$ and
$\beta$ differ at index $n_1$, and thus $d(\alpha,\beta) = d(\alpha,\gamma)$ and
the triangle-inequality follows.
The case where $0<d(\alpha,\gamma) < d(\gamma,\beta)$ follows analogously.

The metric $d$ induces a topology (e.g., page 119 of [1]) where the $\epsilon$-balls  $B_\varepsilon(\alpha) = \{
\beta \in ASYNC \mid d(\alpha,\beta) < \varepsilon \}$ are the basic open sets.
We will now argue why safety properties correspond to
closed sets:
If an execution $\alpha$ does not satisfy a safety property
  $S\subseteq ASYNC$, i.e.\ $\alpha \notin S$, then there is an index
  $N$ where
  all runs $\beta$ that share a prefix longer than $N$ with $\alpha$ are
  not in $S$. This closely matches intuition, since once a
    safety property is violated in a prefix of an execution, it makes no
    difference how this prefix is extended!
Formally speaking, suppose that $\alpha \notin S$.
There exists an $N\geq 0$ such that, if some
$\beta \in ASYNC$ has $d(\alpha,\beta) < {2^{-N}}\text{,}$ i.e., $\alpha$ and
$\beta$ share a prefix of length $\ge N$, then $\beta \notin S$.  Thus, the
set of runs $S$ is closed, since its complement is open.

[1] James Munkres. Topology.


Degree reduction step in Dinur's proof of the PCP theorem In the degree reduction step of Dinur's proof, the input graph $G$ is transformed into a graph $G'$ by replacing each vertex $v \in V(G)$ by a set of vertices, $cloud(v)$, such that $|cloud(v)| = degree_G(v)$, and imposing a degree d expander graph on $cloud(v)$ for all $v \in V(G)$. This makes $G'$ a d+1 regular graph, and the construction ensures that the gap reduces only by a constant factor. I was wondering what would happen if we impose a cycle on each cloud instead? I tried bounding the drop in the gap, but was not able to do so. So, does the proof break down at this step?

It is essential to the construction to have an expander between the copies of a vertex (the "cloud" of the vertex).
Otherwise, you won't be able to argue that the adversary assigning values to the vertices is better off assigning those vertices the same value.

In particular, if instead of an expander you have a cycle, the prover can assign one half-cycle one value, and the other half-cycle another value. This way with good probability the verifier won't catch the inconsistency between the vertices, but you can't appeal to the soundness of the original graph to prove soundness for the new graph (it's like allowing the prover in the original graph to use two different assignments for the vertex).


Almost always almost right I am looking for a complexity class that relates to APX as BPP relates to P. I have already asked the same question here, but perhaps TCS would be a more fruitful location for answers.

The reason for the question is that in practical problems one often needs to find approximate answers (thus APX) with sufficiently high confidence (thus BPP), which would make the class of problems with bounded probabilistic approximation algorithms potentially a useful model of what's computable in practice.

A possible candidate of such class would be $APX^{BPP}$: problems that admit approximated solutions with bounded probabilistic subroutines; however, I'm not confident that such class would be the appropriate setting for the class probabilistically computable approximations.

Both BPP and APX have been extensively studied. Is that the case for $APX^{BPP}$, or whichever class would be the best to capture the above problems?

For any given objective function, let BotL (best-of-the-list) be the algorithm that evaluates the objective function on a set of inputs and returns an input from that list that had maximal output (from among those inputs), with ties broken arbitrarily. $\:$ Since APX only includes problems

who's objective function can be computed in deterministic polynomial time, BotL can be implemented deterministically in polynomial time. $\:$ Furthermore, the value returned by BotL

is at least as good as any of inputs in the least that BotL was evaluated on. $\:$ In particular,

if any of the inputs in that list is good-enough then BotL's output will be good-enough.

Therefore running BotL on the outputs of a sufficiently large number of independent executions of a base algorithm can amplify the success probability from 1/poly to 1-(1/(2^poly)).

As consequence of the preceding paragraph, the precise

confidence level essentially does not affect the resulting class.

(This situation is highly analogous to RP.)

I was not able to find anything about that on the complexity zoo, although there

might have been talks on it given at the workshop referred to in this paper.


Nonregular Languages in Sublogarithmic Space Are there any known languages that require $o(\log n)$ space but are also not regular?  I'm looking for a problem "just below" undirected connectivity.

Yes. I think the main reference is Turing Machines with Sublogarithmic Space by Szepietowski (1994). (Link to books.google)


Partitioning a connected polygon into connected pieces of equal area Armaselu and Daescu (TCS, 2015) present algorithms that, given a convex polygon $P$ and an integer $m$ (which  must be a power of $2$), return a partition of $P$ into $m$ convex polygons with the same area and same perimeter.
If we only want the area to be equal (and do not care about perimeter), then the problem becomes easy for any $m$: move a "knife" (a straight line) over $P$ from left to right, and make a cut whenever the area covered by the knife is $1/m$. Since $P$ is convex, the resulting pieces are convex too.
But what if $P$ is not convex? Then, cutting $P$ by a knife might generate pieces that are not convex and even not connected.
What is an algorithm for partitioning a polygon (that is connected but not necessarily convex) into $m$ connected polygons?
My guess is that the problem should be much easier for hole-free polygons. But even for this case, I could not find an algorithm.

To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the length of the cut. See: Elias Koutsoupias, Christos Papadimitriou, and Martha Sideri (1992), "On the optimal bisection of a polygon", ORSA J. Comput. 4 (4): 435–438, doi:10.1287/ijoc.4.4.435.


Higher-rank polymorphism over unboxed types I have a language in which types are unboxed by default, with type inference based on Hindley–Milner. I’d like to add higher-rank polymorphism, mainly for working with existential types.

I think I understand how to check these types, but I’m not sure what to do when compiling. Currently, I compile polymorphic definitions by generating specialisations, much like C++ templates, so that they can work with unboxed values. E.g., given a definition of f<T>, if the program invokes only f<Int32> and f<Char>, then only those specialisations appear in the compiled program. (I’m assuming whole-program compilation for now.)

But when passing a polymorphic function as an argument, I don’t see how I can generate the right specialisation statically, because the function could be selected at runtime. Do I have no choice but to use a boxed representation? Or is there a way around the issue?

My first thought was to somehow encode rank-n polymorphism as rank 1, but I don’t believe it’s possible in general because a formula in constructive logic doesn’t necessarily have a prenex normal form.

I've thought a bit about this. The main issue is that in general, we
don't know how big a value of polymorphic type is. If you don't have
this information, you have have to get it somehow. Monomorphisation
gets this information for you by specializing away the
polymorphism. Boxing gets this information for you by putting
everything into a representation of known size.

A third alternative is to keep track of this information in the
kinds. Basically, what you can do is to introduce a different kind for
each data size, and then polymorphic functions can be defined over all
types of a particular size. I'll sketch such a system below.

$$
\newcommand{\bnfalt}{\;\;|\;\;}
\newcommand{\rule}[2]{{\mathord{\array{#1}} \over {\mathord{#2}}}}
\newcommand{\judge}[3]{{#1} \vdash {#2} : {#3}}
$$
$$
\begin{array}{llcl}
\mbox{Kinds} & \kappa & ::= n \\
\mbox{Type constructors} & A & ::= & \forall a:\kappa.\; A \bnfalt \alpha \bnfalt A \times B \bnfalt A + B \bnfalt A \to B \\
                         &   & |   & \mathsf{ref}\;A \bnfalt \mathsf{Pad}(k) \bnfalt \mu \alpha:\kappa.\; A\\
\end{array}
$$

Here, the high level idea is that the kind of a type tells you how
many words it takes to lay out an object in memory. For any given
size, it's easy to be polymorphic over all types of that particular
size. Since every type -- even polymorphic ones -- still has a known
size, compilation isn't any harder than it is for C.

The kinding rules turn this English into math, and should look something like this:
$$
  \rule{ \alpha:n \in \Gamma}
       { \judge{\Gamma}{\alpha}{n} }
  \qquad
  \rule{ \judge{\Gamma, \alpha:n}{A}{m} }
       { \judge{\Gamma}{\forall \alpha:n.\; A}{m} }
$$
$$
  \rule{ \judge{\Gamma}{A}{n} &
         \judge{\Gamma}{B}{m} }
       { \judge{\Gamma}{A \times B}{n + m} }
  \qquad
  \rule{ \judge{\Gamma}{A}{n} &
         \judge{\Gamma}{B}{n} }
       { \judge{\Gamma}{A + B}{n + 1} }
$$
$$
  \rule{ \judge{\Gamma}{A}{m} &
         \judge{\Gamma}{B}{n} }
       { \judge{\Gamma}{A \to B}{1} }
  \qquad
  \rule{ \judge{\Gamma}{A}{n} }
       { \judge{\Gamma}{\mathsf{ref}\;A}{1} }
$$
$$
  \rule{  }
       { \judge{\Gamma}{\mathsf{Pad}(k)}{k} }
  \qquad
  \rule{ \judge{\Gamma, \alpha:n}{A}{n} }
       { \judge{\Gamma}{\mu \alpha:n.\; A}{n}
       }
$$

So the forall quantifier requires you to give the kind you are ranging
over. Likewise, pairing $A \times B$ is an unboxed pair type, which
just lays out an $A$ next to a $B$ in memory (like a C struct
type). Disjoint unions take two values of the same size, and then add
a word for a discriminator tag. Functions are closures, represented as
usual by a pointer to a record of the environment and the
code.

References are interesting -- pointers are always one word, but they
can point to values of any size. This lets programmers implement
polymorphism to arbitrary objects by boxing, but doesn't require
them to do so. Finally, once explicit sizes are in play, it's often
useful to introduce a padding type, which uses space but doesn't do
anything. (So if you want to take the disjoint union of an int and a
pair of ints, you'll need to add padding the first int, so that the
object layout is uniform.)

Recursive types have the standard formation rule, but note that
recursive occurences have to be the same size, which means you usually
have to stick them in a pointer to make the kinding work out. Eg, the
list datatype could be represented as

$$
   \mu \alpha:1.\; \mathsf{ref}\;(\mathsf{Pad}(2) + \mathsf{int} \times \alpha)
$$

So this points to an empty list value, or a pair of an int and a pointer
to another linked list.

Type checking for systems like this is also not very hard; the
algorithm in my ICFP paper with Joshua Dunfield, Complete and Easy
Bidirectional Typechecking for Higher Rank
Polymorphism applies to this case
with almost no changes.


NP-complete decision problems on deterministic automata Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or things like that.

The only problem that comes to my mind is the DFA-INTERSECTION-NONEMPTINESS for unary automata. Given $k$ deterministic automata, this problem is to decide if they accept some common word. In this generality the problem is PSPACE-complete, but for unary automata it is NP-complete.

But beside from that, no other decision problem from the realm of finite automata theory come to my mind. So do you know any?

The decision version of the DFA identification problem  (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:

Input: Integer $k$ and sets $P, N \subseteq \Sigma^*$

Question: Is there a DFA $A$ with at most $k$ states such that $P \subseteq L(A)$ and $N \cap L(A) = \emptyset$. In other words $A$ accepts all words in $P$ and rejects all words in $N$.

See: E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978


Algorithm to determine function equality on the simply typed lambda calculus? We know that beta-equality of simply typed lambda-terms is decidable. Given M,N:σ→τ, is it decidable whether for all X:σ, MX $≃_β$ NX?

As I said in my comment, the answer in general is no.

The important point to understand (I say this for Viclib, who seems to be learning about these things) is that having a programming language/set of machines in which all programs/computations terminate by no means implies that function equality (i.e., whether two programs/machines compute the same function) is decidable.  An easy example: take the set of polynomially-clocked Turing machines.  By definition, all such machines terminate on all inputs.  Now, given any Turing machine whatsoever $M$, there is a Turing machine $M_0$ that, given in input the string $x$, simulates $|x|$ steps of the computation of $M$ on a fixed input (say, the empty string) and accepts if $M$ terminates in at most $|x|$ steps, or rejects otherwise.  If $N$ is a Turing machine that always immediately rejects, $M_0$ and $N$ are both (obviously) polynomially-clocked, and yet if we could decide whether $M_0$ and $N$ compute the same function (or, in this case, decide the same language), we would be able to decide whether $M$ (which, remember, is an arbitrary Turing machine) terminates on the empty string.

In the case of the simply typed $\lambda$-calculus (STLC), a similar argument works, except that gauging the expressive power of the STLC is not as trivial as in the above case. When I wrote my comment, I had in mind a couple of papers by Hillebrand, Kanellakis and Mairson from the early 90s, which show that, by using more complex types than the usual type of Church integers, one may encode in the STLC sufficiently complex computations for the above argument to work. Actually, I see now that the needed material is already in Mairson's simplified proof of Statman's theorem:

Harry G. Mairson, A simple proof of a theorem of Statman. Theoretical Computer Science, 103(2):387-394, 1992. (Available online here).

In that paper, Mairson shows that, given any Turing machine $M$, there is a simple type $\sigma$ and a $\lambda$-term $\delta_M:\sigma\rightarrow\sigma$ encoding the transition function of $M$. (This is not obvious a priori, if one has in mind the extremely poor expressive power of the STLC on Church integers. Indeed, Mairson's encoding is not immediate).  From this, it is not hard to construct a term

$t_M:\mathtt{nat}[\sigma]\rightarrow\mathtt{bool}$

(where $\mathtt{nat}[\sigma]$ is the instantiation on $\sigma$ of the type of Church integers) such that $t_M\,\underline{n}$ reduces to $\underline{1}$ if $M$ terminates in at most $n$ steps when fed the empty string, or reduces to $\underline{0}$ otherwise. As above, if we were able to decide that the function represented by $t_M$ is the constant $\underline{0}$ function, we would have decided the termination of $M$ on the empty string.


Does Max Planar 3-SAT admit a PTAS? Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each positive literal $x_i$ and for each negative literal $\overline{x_i}$. A literal is adjacent to a clause if and only if this clause contains the literal. $\phi$ is a planar instance If $G_\phi$ is planar.

Max planar 3-SAT is defined as the restriction of Max 3-SAT to planar instances.

This problem is known to be NP-hard. Is this problem also APX-Hard or there exists a known PTAS for this problem ?

Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach.
This has been observed, for instance, in Theorem 17 in

  Pierluigi Crescenzi and LucaTrevisan:
  "Max NP-completeness made easy"
  Theoretical Computer Science 28, (1999), Pages 65-79


Learning a discrete distribution in $\ell_r$ norm Let $P=(p_1,\ldots,p_d)$ be a distribution on $[d]$. Given $n$ iid draws from $P$, we construct some empirical estimate
$\hat P_n=(\hat p_{n,1},\ldots,\hat p_{n,d})$. Let us define the $r$-risk
by
$$ J_n^r = \sum_{i=1}^d |p_i-\hat p_{n,i}|^r.
$$

It is known (see, e.g., Lemma 2.4 here)
that when $\hat P_n$ is the maximum likelihood (i.e., empirical frequency) estimator
and $r\ge2$,
we have
$\mathbb{E}[J_n^r]\le1/n$. In particular, the expected $r$-risk decays at a dimension-free rate.

It is also known that for $r=1$, the risk decays at a minimax rate of $\Theta(\sqrt{d/n})$.

Question: what is known for $1<r<2$?

Clément Canonne and I worked this out at some point.

Let $X_j$ be the number of realizations of $j \in [d]$. So $\mathbb{E} X_j = np_j$.
\begin{align*}
  \mathbb{E} J_n^r &= \mathbb{E} \|\hat{P}_n - P \|_r^r \\
    &= \frac{1}{n^r} \sum_{j=1}^d \mathbb{E} |X_j - \mathbb{E}X_j|^r  \\
    &\leq \frac{1}{n^r} \sum_{j=1}^d 3\mathbb{E} X_j  & (*)  \\
    &= \frac{3}{n^{r-1}} .
\end{align*}
We get $(*)$ by a slightly tedious argument you can find in Theorem 5.1 of [1] or I can add here later. It just uses the extreme cases of $r=1$ or $r=2$.

In particular this gives a dimension-free bound. However, one can get a dimension-dependent upper bound simply by using the standard $p$-norm inequalities and the upper bound on the $2$-norm that you state. The dimension-dependent bounds will be better when the dimension is small relative to the number of observations, I believe when $d \leq O(n^{1/q})$ but will have to double-check (where $q = 1 - 1/r$).

[1]:  "$\ell_p$ Testing and Learning of Discrete Distributions" (Bo Waggoner, ITCS 2015), https://arxiv.org/abs/1412.2314


Variants of Densest Subgraph Problems Given a graph $G$, and a vertex-induced subgraph $H$ of $G$, there are two superficially-similar definitions ways to define the density of $H$:

(1) Average degree of vertices in $H$

(2) What I will refer to as the "edge density" of $H$, defined as $\frac{ E(H) }{ \binom{V(H)}{2}}$.

I'm interested in understanding the complexity of finding dense subgraphs, subject to constraints on the number of nodes, using the second definition of density. Unfortunately, most of the relevant work I can find, most notably on variants of the $k$-densest subgraph problem, uses the first definition. I'm looking for pointers to work on the second definition. First, I will elaborate on the similarities and differences between the two definitions before asking two specific questions.

If one is interested in finding the  densest subgraph with a given number of nodes $k$, it doesn't matter which definition you use. The two definitions coincide when comparing subgraphs with the same number of nodes. The result is the NP-hard $k$-densest subgraph problem, which is well studied, but who's complexity of approximation remains poorly understood. However,when looking for the "densest at-most-k subgraph"  or "densest at-least-k" subgraph, the two definitions of density appear importantly different.

Densest at-most-k subgraph: Using the average-degree definition, this problem is NP-hard, and its approximability is essentially equivalent to that of the classic "k-densest subgraph" problem [Anderson and Chellapilla '09]. Using the edge density definition, however, this problem is trivial: any two nodes connected by an edge are an optimal choice of $H$.

Densest at-least-k subgraph: Using the average-degree definition, this problem has been studied before, and admits a constant factor approximation [Anderson and Chellapilla '09]. However, using the edge density definition, I can't seem to find any related work.

This get more dicey when one considers both upper and lower bounds on $k$, the number of nodes in the sought induced subgraph.

My questions:

(a) Can anyone point me to work on approximation algorithms for densest at-least-k subgraph using the edge-density definition of density?

(b) What is the proper name of what I'm calling "edge density"? Why does this definition appear more esoteric, as far as the approximation algorithms community is concerned, than the average degree definition? (Or is it?)

This is meant more as a comment than as a solution, but is a bit too long to fit in the comment box. There is a bit of handwaving and ignoring of small factors, but I can formalize the work below further if requested.

Here's a heuristic reason why (a) might be difficult to approximate within a small factor.

Consider the random-in-random PLANTED DENSE SUBGRAPH problem, which one to reliably distinguish between the Erdos-Renyi graph $G(n,p)$ and the graph $G(n,p)$ with a planted $G(n',p')$ for certain values of $n,n',p,p'$. It is a difficult problem -- conjectured hard by some -- to do this in polynomial time for $p = \frac{1}{n^{1/2}}$, $n' = n^{1/2}$, $p' = \frac{1}{n^{1/4 + \epsilon}}$. That is, it's hard to distinguish a "pure" $G(n,1/\sqrt{n})$ graph (where each induced subgraph of size $\sqrt{n}$ has average degree near $1$) from instances where some subset of $\sqrt{n}$ vertices has so many edges planted between them that the average degree is roughly $n^{1/4 - \epsilon}$.

In such instances, there's quite a large gap in the maximum edge densities in subgraphs of size at least $\sqrt{n}$. In particular, while the planted portion of the planted-instance graph has edge density roughly $\frac{1}{n^{1/4+\epsilon}}$, just about any size $\sqrt{n}$ (or higher) subgraph of the non-planted $G(n,1/\sqrt{n})$ graph will have edge density about $1/\sqrt{n}$, a gap of roughly $n^{1/4 - \epsilon}$.

Any approximation algorithm with a stronger guarantee than $n^{1/4 - \epsilon}$ can thus be used to solve a conjectured-hard class of instances of Planted-DkS.


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

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

Your question is vague in several ways.

By a "non-negative vector," do you mean a quantum pure state, all of whose amplitudes are nonnegative real numbers?  (Or rather, a state that's equivalent to such a state under multiplication by a complex scalar, which of course is physically unobservable?)

By a "quantum oracle," do you mean a unitary transformation that outputs ACCEPT when fed a non-negative state, and REJECT when fed any other state?  With probability close to 1?

If so, then it's immediate that no such oracle exists.  Indeed, the probability that the oracle accepts is a continuous (quadratic) function of the amplitudes, but the amplitudes can be arbitrarily close to 0 while still being either positive or negative.

So at the least, you'd need some lower bound on the absolute values of the amplitudes -- together, perhaps, with the assumption that the amplitudes are all real (or if complex, that their angles with each other are either 0 or else sufficiently large).  If you impose these conditions, then the "non-negativity oracle" does exist for quantum states of dimension 2: there it's called the "Hadamard gate," or the "Deutsch-Jozsa algorithm"!  On the other hand, because of quantum-mechanical linearity, one can prove that the non-negativity oracle won't exist for states of dimension 3 or greater -- or will exist but only with very large probability of error (approaching 1).


Extending EAL with recursion makes it incompatible with the abstract algorithm? A few years ago, I've asked if Elementary Affine Logic can be used as the core type system of a practical programming language. The accepted answer argues that, yes, although such language would be awkward to use because you can not iterate over terms that were themselves produced as the result of an iteration. EAL calculus is compatible with Lamping's abstract algorithm because, due to its stratification condition, substitution doesn't alter the level of the substituted term. As such, by using the label approach to mark fan nodes with their levels, and only duplicating terms of higher levels, we'll never have an unsound reduction. If we, though, add recursion in the form of recursive let-bindings, then this argument shouldn't be affected at all. Take the infinite list of ones, for example:

ones = λcons. λnil. (cons 1 ones)

This term doesn't duplicate λ-bound variables and, as such, doesn't require boxes at all. It can be seen as no different than writing a very huge list at the level 0. From the interaction net perspective, its only fan-node is pointing downwards, i.e., it is not pointing upwards towards the variable slot of a λ-node, so it obviously can't interact with a fan-node with the same label coming from a different duplication process. Am I wrong in concluding that, thus, extending the EAL calculus with mutually recursive let shouldn't make it incompatible with the label approach of optimal reduction?

The term that you gave does have one duplication, i.e.: ones is used in the body and returned in form of a free variable. The following example illustrates the same effect but is smaller:

loop = λ_. loop

To make the graph structure clear, let's make sure that each identifier is used exactly twice (_ represents connected erasing node):

C[loop, loop_rec] = λ[_, loop_rec]

EAL gives you termination proof if you can stratify all the terms. I don't see how you can stratify this one.
If the level of loop_rec is $n$ then the level of whole λ is also $n$. And after the contraction the level of both loop and loop_rec should be $n-1$ which gives you contradiction.

On the other hand you are right that this copy can't escape the definition (assuming 1 and cons are closed), so it is equal to an actual infinite list. Yet I don't see how to generalize this into an argument about arbitrary recursive let statements.


How to play the following game? (placing balls into bins) Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$.

The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\quad{} \Sigma_{i=1}^\ell y_i = \ell\cdot n.$$

Next, there are $\ell$ bins such that bin $i$ contains $x_i$ blue balls.
Given a random permutation $\sigma:[\ell]\to[\ell]$, $y_{i}$ is the number of red balls in bin $\sigma(i)$.

From every non-empty bin, a random ball is chosen uniformly, and we win the game if all sampled balls are red.

  How can we select $x,y$ to maximize our winning odds?

If we pick $x_1,\ldots,x_\ell=n/\ell$ and $y_1,\ldots,y_\ell=n$, we have that in each bin a red ball will be sampled with probability $1-1/(\ell+1)$ and the chance of getting only red balls would be $(1-1/(\ell+1))^{\ell}\approx 1/e$.

As GMB answered, it's possible to improve this by setting $x_1=\ldots=x_{\ell-1}=0$ and $x_\ell=y_1=\ldots=y_\ell=n$, and getting a success probablity of 1/2.

Is this optimal?

Formulated as a math expression:

  What is $\max_{x,y\mid \Sigma_{i=1}^\ell x_i = n, \Sigma_{i=1}^\ell y_i = \ell\cdot n} \quad{} \mathbb E_\sigma\; \left[\prod_{i=1}^\ell \frac{y_{\sigma^{-1}(i)}}{y_{\sigma^{-1}(i)}+x_i}\right]$?

I think $x_1 = \dots = x_{\ell-1} = 0, x_{\ell} = y_1 = \dots = y_{\ell} = n$ is better.  You are guaranteed to choose red in all bins except for bin $\ell$, and bin $\ell$ has $n$ red balls and $n$ blue balls, so your overall odds of success are $1/2 > 1/e$.


In which posets is the set of compact elements downwards closed? In a poset $(D, \sqsubseteq)$, a compact element is an element $d \in D$ such that for every directed set $A$ which happens to have a supremum $\bigsqcup A \in D$ with $d \sqsubseteq \bigsqcup A$, it is $d \sqsubseteq a$ for some $a \in A$ (e.g., Definition I-4.1 of [Gierz et al 2003]).

My (elementary) question. Suppose $d$ is compact and $c \sqsubseteq d$. What are typical extra impositions on the poset, that ensure that $c$ must also be compact?

The only natural condition I can think of is Berry's "I condition" ([1], Sect. 12.3):

(I) each compact element dominates finitely many elements.

The above condition is the defining property of Berry's dI-domains, which are distributive (that's what the "d" stands for) algebraic domains satisfying condition I.  This is a widely known and well studied class of domains, which served as the basis for what is known as "stable" semantics (an attempt to capture the sequential behavior of the $\lambda$-calculus).  Girard's coherence spaces [2] give a particularly simple and useful example of dI-domains.  A coherence space may be seen as the set of cliques of a reflexive graph, ordered by inclusion.  The compact elements are the finite cliques, which obviously satisfy your requirement.

I don't know if generalizations of the I condition have been studied.  A counterexample to your property is given by the ordinal $\omega+2$ ($\omega+1$ is compact but $\omega$ is not), so certainly generalizing "finite" to "well-founded+no infinite antichains" does not work.

[1]  Roberto Amadio and Pierre-Louis Curien.  Domains and Lambda-Calculi.  Cambridge Tracts in Theoretical Computer Science, 1998.

[2] Jean-Yves Girard, Yves Lafont and Paul Taylor.  Proofs and Types.   Cambridge Tracts in Theoretical Computer Science, 1989.


Minimum degree of the "tree graph" Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a single edge. That is there is an edge $(T_1, T_2)$ if there exists two edges $x, y \in G$ such that $T_1 - x = T_2 - y$.

My question is this: are there some non-trivial lower or upper bounds on the degree of the vertex with minimum degree in $T(G)$?

Note: I edited the question (last line) a bit to make it less ambiguous
.

If $G$ has $n$ vertices and $m$ edges, then for any spanning tree $T$ of $G$, each of the $m-n+1$ edges that are not in $T$ may be swapped with any of the edges on the path in $T$ between the endpoints of the non-tree edge. Assuming $G$ is not a multigraph, this gives at least $2(m-n+1)$ different swaps; that is, every $T$ has degree at least $2(m-n+1)$.

This bound is tight: if $G$ has a vertex $v$ adjacent to all others, and $T$ is the spanning tree consisting of all the edges incident to $v$, then the path in $T$ between the endpoints $T$ of every non-tree edge has length exactly two, so each non-tree edge participates in exactly two swaps and $T$ has degree exactly $2(m-n+1)$.

On the other hand if $G$ has girth (shortest cycle length) $g$, then the path in any tree $T$ between the endpoints of any non-tree edge, together with that edge, forms a cycle which must have length at least $g$, so the minimum degree in the tree graph must be at least $(g-1)(m-n+1)$. This bound is tight for some graphs such as the cycle graphs, and complete bipartite graphs, and Moore graphs, since these graphs contain spanning trees for which all non-tree edges induce cycles of length equal to the girth.

However, finding the minimum degree of the tree graph for an arbitrary given graph (equivalently, finding a spanning tree minimizing the sum of lengths of the cycles induced by non-tree edges) is NP-complete: see Deo, Prabhu, and Krishnamoorthy, "Algorithms for Generating Fundamental Cycles in a Graph", ACM TOMS 1982. So finding bounds such as these that are tight for all graphs appears unlikely.


Planning jobs as partition problem I think this should be a famous problem but I could not find its name.

I have $n$ jobs with size $s_i$ that are offered at time $t_i$ and $k$ machines.
How can I assign jobs to machines to minimize the maximum finish time.

I know that when the offering times $t_i$s are equal, this is a partition problem as it balances the jobs over machines. Also I know that there are approximation algorithms for that.

Is there any greedy algorithm (with approximation bound) for this generalized version?

I found the solution of the solution of this algorithm in this book: Handbook of Scheduling: Algorithms, Models, and Performance Analysis .

In Theorem 3.4, they show an optimal algorithm for the preemptive case.
The largest processing time first algorithm has worst case bound of $\frac{4}{3} − \frac{1}{3k} $ if $t_i=0, \forall i$ for non-preemptive case

I will apply this largest processing time first to the general case and see how it works in practice.


Reference Request: Computational Learning Theory Pretty soon I will be finishing up Understanding Machine Learning by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble finding a book that could come after this. Ultimately, my goal is to read papers in JMLR's COLT.

Is there a book similar to Understanding Machine Learning that would progress my knowledge further and would go well after reading UML?
Is there any other materials (not a book) that could allow me to learn more or prepare me for reading a journal like the one mentioned above?

(also taking courses in this is not really an option so this will be for self-study)

This question was also asked here on AI SE from suggestion of comments.

Another good introductory book is "Foundations of Machine Learning" by Mohri et al.: https://www.amazon.com/Foundations-Machine-Learning-Mehryar-Mohri/dp/0262039400/.  It has a large overlap with the Shai and Shai book, but also quite a bit of content that they don't cover.

There are also good books and surveys on more advanced or specialized topics:

Szepesvári and Lattimore have a nice book on bandits:
https://tor-lattimore.com/downloads/book/book.pdf
Cesa-Bianchi and Lugosi have a difficult but rewarding book on
learning and games: https://www.amazon.com/Prediction-Learning-Games-Nicolo-Cesa-Bianchi/dp/0521841089/
Schapire and Freund have a wonderful book on boosting: https://mitpress.mit.edu/books/boosting

There are more, but I hope this is a good start.


Minimum non-zero variable in the optimal solution of linear programming Suppose we have a linear programming about the vertex packing of a hypergraph G=(V,E), with size $n = \sum_{e \in E}|e|$. We introduce a variable $x_v$ for each vertex $v \in V$.

$$\max \sum_{v} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$s.t. \sum_{v: v \in e} x_v \le 1, \ \forall e \in E$$
$$\ x_v \ge 0, \ \forall v \in V$$

Is it always possible to find an optimal solution such that the minimum non-zero variable has value at least $c \cdot 1/n$ for some constant $c$? (If representing the contraints as $\mathbf{Ax} \le \mathbf{1}$, there are $n$ entries as $1$ in $\mathbf{A}$ with remaining entries as $0$.)

No, it is not always possible.  The illustration below shows an example in which the smallest non-zero value must be $1/2^{\Omega(n)}$.

The example is shown in the top of the illustration.  Round nodes are vertices; square nodes are hyperedges, each with connections to its (two or three) vertices.  Each vertex $v$ is labeled with its weight $x_v$ in the optimal LP solution, which is essentially unique.

In general, the hypergraph consists of the first three vertices (labeled $1/2$) and their three edges to their left, followed by $N$ copies of the gadget shown in the middle (vertically).  The "inputs" to the gadget are the three vertices labeled $1/x$.  The "outputs" are the three vertices labeled $1/2x$; these are also the inputs for the next copy of the gadget (if any).  Above $N=3$, but in general $N$ is arbitrarily large.  The sum of the hyperedge sizes is $n = \Theta(N)$, and the given solution has a non-zero weight of value $\Theta(1/2^N) = 1/2^{\Theta(n)}$.  This solution is obtained greedily by assigning weights maximally, from left to right.

To answer the question in the post, we will show that the given solution is the unique optimal solution.  The bottom part of the illustration above is for the proof (given below).

Lemma 1. The given LP solution is the unique optimum.

Proof sketch.
Let $x$ be the LP solution given in the figure.  By inspection $x$ is feasible.  First we'll argue that $x$ is optimal, by giving a dual solution that achieves the same LP objective.
The dual LP is "covering vertices by edges":
$$\min \sum_e y_e ~:~ y_e \ge 0;~~(\forall v)~\sum_{e \ni v} y_e \ge 1.$$

We use the dual solution illustrated in the bottom part of the figure above, in green.  We give each edge weight equal to the green label at the bottom of its column.  This solution is obtained greedily, by assigning weights minimally from right to left.  By inspection, at least for the example, the dual solution is feasible and has the same cost as the primal solution $x$. In general, by calculation, the cost achieved by the given primal solution $x$ is
$$3[1/2 + N + 1/2^{N+2}],$$
while the cost achieved by the given dual solution is the same:
$$3[(1/2 - 1/2^{N+2}) + 1/2^{N+1} + N].$$
Therefore the primal and dual solutions are optimal.

To finish we argue that the optimal primal solution is unique.  Let $x^*$ be any optimal primal solution.
By complimentary slackness and the fact that all values are non-zero in the optimal dual solution, $x^*$ must make all primal constraints tight.

Let $x^*_1, x^*_2, x^*_3$ be the variables of the first three vertices, given weight $1/2$ by $x$.  That the first three constraints are tight implies $x^*_1 + x^*_2 = 1$ and $x^*_1 + x^*_3 = 1$ and $x^*_2 + x^*_3 = 1$, which implies that $x^*_1 = x^*_2 = x^*_3 = 1/2$, the same as in $x$.

Given that, the same reasoning implies that $x^*$ gives each of the next three vertices weight $1/4$, also the same as in $x$. Given that, likewise, $x^*$ must give each of the next three vertices weight $3/4$, the same as in $x$.  Continuing this reasoning inductively, $x$ and $x^*$ must be identical.  $~~~\Box$


Does the MIP* = RE proof work for limited provers? MIP* = RE shows that two arbitrarily strong entangled provers can convince a verifier of instances of the halting problem.  Now assume that we have two entangled provers that are only capable of solving problems in some language $L$ (say a language complete for NEEXP, NEEEXP, etc.).

Question: What constraints on $L$ allow provers to convince a verifier of solutions to $L$?

The nonquantum analogy is that not only is IP = PSPACE, but IP' = PSPACE where IP' provers are only able to solve PSPACE level problems.  In particular, L = PSPACE works for the MIP* question.  Moreover, provers that are limited to any level of the polynomial hierarchy $\Sigma_k \textrm{P}$ can establish $\Sigma_k \textrm{P} \subset \textrm{PSPACE}$. (Unfortunately, looks like this doesn't work lower in the polynomial hierarchy.)

(I'm blurring over some definitional subtlety here about function problems vs. decision problems; in the above one probably needs the provers to be able to solve $\textrm{FP}^L$ rather than just L.)

I believe our result shows that if the prover is capable of solving NTIME[poly(T)] problems, and has the ability to manipulate polylog(T) qubits, then they can convince the verifier of YES instances of NTIME[T] problems.

In other words, roughly speaking NTIME[2^poly(Q)] = MIP*[Q] where MIP*[Q] denotes the provers being limited to Q qubits of entanglement.


Is set packing easier when the sets are squares? I am interested in the following problem:

There are n collections of M axis-parallel squares (not necessarily disjoint).
Pick a single square from each collection,
     such that the n selected squares are pairwise interior-disjoint.

One way to approach the problem is to discretize the squares such that each square becomes a set of small squares. This makes the problem an instance of the following set packing problem:

There are n collections of sets (not necessarily disjoint).
Pick a single set from each collection,
     such that the n selected sets are pairwise disjoint.

The set packing problem is equivalent to the independent set problem, and both are known to be NP-complete.

My question is: does the fact that the sets in this case are discretizations of axis-parallel squares make the problem any easier?

Particularly, is it possible to solve the problem, or at least approximate it to a constant factor, in time polynomial in $n$ (the number of collections), assuming $M$ is constant?

I think your problem is NP-complete already for M=3, as there is a quite straight-forward reduction to it from 3SAT. Just for each variable xi, make a pair of squares, truei and falsei. For a clause Cj, make a pair of squares for each of its literals, e.g., Aj1, Bj1, Aj2, Bj2, Aj3, Bj3. Let Aj1 intersect the respective square of the variable (e.g., truei) (but disjoint from any other similar clause-squares intersecting it), while the Bj1, Bj2 and Bj3 are put somewhere in a disjoint way. Finally, for each clause we have a collection of three squares, which is also Bj1, Bj2 and Bj3.