A continuous center point of a convex spherical polygon In discrete geometry, the center point $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a center point always exists.)

My problem is similar but in a continuous setting.
I have a convex spherical polygon $P$ on the unit sphere. In this context an "area-center" point $c$ is such that any half sphere that contains $c$ also contains a part of $P$ whose area is at least a constant fraction of the area of $P$.

The definition can be similarly phrased with convex polygons on the plane and half-planes instead of half-spheres. It can also be generalised to higher dimension.

My questions are:

Does this definition has a well-known name? ("area-center point"?)
Do we know algorithm to compute such an area-center point? (exact or approximate)

(My motivation for finding such a point is for doing logarithmic search on the unit sphere.)

I ask this question here because searching the web only leads me to centroids or discrete center point, or the Tverberg generalization, but nothing related to the specific definition given above. (I have already asked question 30 minutes ago on math SE, but realised it is probably more relevant to comp. geom. hence its posting here)

Thank you !

For your second question...

For any distribution, if you take a sample $R$ of size $O(1/epsilon^2 )$ of it, and compute its center point, it is going to be a $\geq (1/3-\epsilon)$-center point, with probability $\geq 1-\epsilon^{O(1)}$ by the $\epsilon$-net theorem (well, more precisely the $\epsilon$-sample theorem). You can apply this to a polygon - you just need to sample points uniformly inside the polygon. This works in any constant dimension.

Similar ideas were used in the paper "Approximating Center Points with Iterated Radon Point". Or so I believe... ;)

Computing the exact center point for a general polygon is nasty as far as I know. There was a paper in the 90s by Dan Halperin on maintaining the area bisector of a polygon, and it was painful, if my memory serves me right.


What is the state of the art in online voting? Is there a cryptographic protocol which, at least in theory (and under standard cryptographic assumptions) enables people to securely vote from their homes? I could see how the various problems might be addressed (such as: preventing people from voting twice, producing proof that the vote was registered while revealing no information about who the vote was for) except for one: preventing coercion (that is making sure that the voter isn't being bribed or otherwise forced to vote a certain way). This seems to be impossible, in principle, without the voter being physically present at a voting center with overseers watching, but maybe I'm not sufficiently thinking outside the box?..

This question is probably too broad to be answerable here, because the answer depends on what kinds of security requirements you have, what the threat model is, and what assumptions we're willing to make -- there are many different versions of those.  In other words, the "secure voting" problem is not one problem, but a broad class of problems.  I suggest doing a literature search, reading some of the classic papers, then see if you have a more specific question.  You could start with papers published at EVT and WOTE use them to seed your literature search.

If you're specifically interested in coercion, I suggest looking at Juels, Catalano, and Jakobson (WPES 2005) and Civitas (IEEE S&P 2008).  Those are two important early papers.  Also, by doing a search on papers that cite them, you'll be able to turn up a lot of more recent work on coercion.

All of these schemes have something in common; they do require some kind of trusted channel to the voter or some situation where the voter does register in person in a supervised environment.  They might not require supervision during the time of voting; that can be pushed to a setup phase.

Also, the solutions may depend on whether you are willing to assume that voters have a personal device (e.g., smartphone) and whether voters are willing to trust it.  Obviously the problem gets easier if you answer that in the affirmative.


What do we know about checking real-stability of multivariate complex polynomials? Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root have a positive imaginary part.

[..clearly if $n=1$ then the polynomial being real-stable is the same as the polynomial being real-rooted..]

Q1 Do we know of any method to check for real stability of a polynomial?

Q2 Even if not a general solution but can one at least be able to check this property on some specific polynomial via some commands on SAGE or Mathematica ?

Q3 Is any hardness result known about this when thought of as a decision question?

If necessary feel free to assume that the polynomial is homogeneous.  May be if thinking about the associated projective variety helps...
May be you can just choose some specific value of $n$ or the degree of the polynomial if you think that the questions are answerable easier for those values. (like $n=1$ and degree $\leq 5$ are the trivial cases)
A generic example of a real-stable polynomial is $p(z,t_1,..,t_n) = det(zI + \sum_{i=1}^{n} t_i B_i)$ where $B_i$ are positive-semi-definite matrices. Now we know that real-stability of a polynomial is preserved under operations like acting by differential operators like $(1+ a \frac{\partial }{\partial x})$ (where $x$ is one of the domain variables of the polynomial and $a \in \mathbb{R}$) or setting any of the variables to a real-number or taking a product of two real-stable polynomials.  Now one obvious way to try to decide if a polynomial is real-stable or not is to see if it can be obtained via doing any combination of these real-stability preserving operations on some other polynomial which is known to be real-stable.

But I am wondering if any direct method (algorithm) exists..

Here is at least some upper bound: treat the polynomial $\mathbb{C}^n \to \mathbb{C}$ as $\mathbb{R}^{2n} \to \mathbb{R}^2$, and then ask in the first order theory of the reals if $p(x)=0$ implies that the imaginary part of each coordinate of $x$ is nonpositive. This can be solved in $\mathsf{PSPACE}$ (e.g. http://en.wikipedia.org/wiki/Existential_theory_of_the_reals).

Of course, the existential theory of the reals is $\mathsf{NP}$-hard, so taking this route in general won't get you below $\mathsf{NP}$...


Decision problems vs functions Complexity theory seems to be built around decision problems rather than functions.

Who introduced this first and what is the reason for this choice?

For example, Edmonds' "Paths, trees and flowers" paper is generally credited as the source of the notion of $\mathsf{PTime}$ representing the set of "tractable" problems and this is the path that we have taken.

Another reason is that this is often without loss of generality, since frequently (though not always - see below) complexity of functions and decision problems are equivalent. Every decision problem can be viewed as a function whose only values are 0 and 1. Conversely, given a function $f$, there are several associated decision problems which usually have the same complexity as $f$, for example:

$\{(x,i) : $ the $i$-th bit of $f(x)$ is 1$\}$.
$\{(x,k) : f(x) \leq k\}$ (or $\geq$)

Here is an example where the complexity of function classes and their associated language classes seem to differ: $\mathsf{P}^{\mathsf{NP}[\log ]} = \mathsf{P}^{\mathsf{NP}}_{tt}$ [Wagner 1987 "Log Query Classes", Hemaspaandra's 1987 thesis, Buss & Hay 1991],  but if $\mathsf{FP}^{\mathsf{NP}[\log ]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$ then $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{P} = \mathsf{UP}$ [Selman 1994].

(Here the oracle $^{\mathsf{NP}[\log]}$ means the machine gets to make $O(\log n)$ queries to any problem in $\mathsf{NP}$ (say, SAT). The notation $\mathsf{P}^{\mathsf{NP}}_{tt}$ means $\mathsf{P}$ with an $\mathsf{NP}$ oracle, but in which the oracle queries are non-adaptive: on input $x$, the if $y_i$ is the $i$-th string queried to the oracle, then $y_i$ does not depend on the answers to any previous oracle calls. Equivalently, on input $x$ the machine builds a list $y_1, \dotsc, y_m$ without querying the oracle, queries the oracle about all of the $y_i$ and gets the answers, then proceeds to compute without querying the oracle again.)


Dark Integers: General Purpose Computations on Internet Routers Greg Egan in his fiction "Dark Integers" (story about two universes with two different mathematics communicating by means of proving theorems around of inconsistence in arithmetic) claims that it is possible to build general purpose computer solely on existing internet routers using only its basic functionality of packet switching (and checksum correction, to be precise).

Is this possible, in principle?

Update.

To make the question more precise:

What is an absolutely minimal set(s) of properties the router network must have that it will be possible to build general purpose computer on top of it?

This can be helpful:

Parasitic computing is an example of a potential technology that could be viewed simultaneously as a threat or healthy addition to the online universe. On the Internet, reliable communication is guaranteed by a standard set of protocols, used by all computers. These protocols can be exploited to compute with the communication infrastructure, transforming the Internet into a distributed computer in which servers unwittingly perform computation on behalf of a remote node. In this model, one machine forces target computers to solve a piece of a complex computational problem merely by engaging them in standard communication.

In the parasitic computing site you can detailed information on how you can solve a 3-SAT problem using the checksum of TCP packets.

Other useful links:

Seminar report on parasitic computing by K.K.Maharana
Nature's article on parasitic computing (Aug 2001)


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

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

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

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

A slightly different way of arguing for the upper bound of $\log n$ is as follows:

Observe that by mirroring across the line $x = y$, we can ignore all points in the upper triangle of the grid (at the cost of increasing the partition size by a factor of 2).
Now consider the lower triangle. If we draw the vertical line $x = n/2$, and "reflect it" off the diagonal $x = y$, we get a square with endpoints $(n/2, 0)$ and $(n, n/2-1)$. all of these points can be placed in a single set.
This leaves two similar  copies of the lower triangle with half its size. Any construction for these two triangles can be "paired up" since sets in these partitions don't conflict.

This yields the recurrence
$$ S(n) = 1 + S(n/2) $$
and hence $S(n) = \Theta(\log n)$


Pairwise independent gaussians Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that
$Y_i$'s are pairwise independent gaussians with mean $0$ and variance $1$.

The posting on MathOverflow tells how to go from a small number of independent Uniform[0,1] random variables to a larger number of pairwise-independent Uniform[0,1] random variables. You can of course go back and forth between Uniform[0,1] and Gaussian by inverting the CDF. But that requires numerical analysis as the CDF is not closed-form.

However, there is a simpler way to from Gaussian to uniform. Given two independent Gaussians $X_1, X_2$, the angle $\arctan(X_1/X_2)$  is uniform in the range $[0,2 \pi]$.

Similarly, the Box-Muller method transforms two independent Uniform[0,1] variables into two independent Gaussian random variables.

Using these two transformations, you consume two Gaussians to produce a uniform or two uniforms to produce a Gaussian. So there is only a factor of $O(1)$ in the sampling efficiency. Furthermore, no inversion of the Normal cdf is required.


What graphs on $\mathbb{N}$ can be encoded as regular languages? Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers into a formal language $V$:

$0 \mapsto x$, $1 \mapsto sx$, $2 \mapsto ssx$, $3 \mapsto sssx$, etc

So $V = \{x, sx, ssx, sssx, ... \}$ is a regular language generated by the regex $s^*x$.
Now, Suppose $G = (\mathbb{N},E \subset \mathbb{N} \times \mathbb{N})$ is a directed graph.  An edge $e = (n, m) \in E$.  I now define an encoding $\beta : E \rightarrow W$ of edges into a new language $W$ using the following encoding
$(n,m) \mapsto \alpha(n),\alpha(m)$ (i.e. concatenate the encoding of each number's encoding with a separating comma).  For example, $W((3,1)) = $"sssx,sx"

Question:  For what graphs $G$ of this type is $W$ a regular language?

Obviously if $E$ has a product structure such as $E = \{ (n, m) \ | \ n \in R_1, \ m \in R_2\}$ where each $R_i \subset \mathbb{N}$ corresponds to a regular language, then $W$ would be regular.  But what about more "natural" relations on $\mathbb{N}$?  In particular, here are two particular examples I am especially interested in:

Ex 1:  $E_1 = \{ (n, n+1) \ | \ n \in \mathbb{N} \}$.  Is $\beta(E_1)$ a regular language?

Ex 2:  $E_m' = \{ (n, n \times m) \ | \ n \in \mathbb{N} \}$ (i.e. an edge from each natural number to its product with a fixed natural number $m$).  Is $\beta(E_m')$ a regular language?

Any help is much appreciated :)

$\beta(E_1)$ is the language $s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma.
If we assume that the language is regular, the pumping lemma tells us that there must exist some $p, q$ such that for all $n \ge p$, $s^{n+q}x,s^{n+1}x$ is also in the language. This is false, meaning that the language is not regular.
A similar argument also demonstrates that $\beta(E_2)$ is not regular, and more generally demonstrates that for a graph to be regular, for any $(n, m)$ in the graph with $n$ greater than some finite cutoff $p$, there must be infinitely many $n'$ such that $(n', m)$ is in the graph.
Since both $E_1$ and $E_2$ fail this condition, they are not regular.


What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)? The "Half Or Triple Plus One" process goes as follows:

  start with $x=n$ for some value of $n$
  if ($x$ is odd)

  $x = 3x+1$

  else

  $x = \frac{x}{2}$
  if ($x$ > 1) goto (2)

Define $f(n) = $

total stopping time of $n$, i.e. The number of steps required for the procedure to halt.

The Collatz conjecture suggests that the process stops for every value of $n$, hence if the conjecture holds, $f$ is well defined.

The question is:

  What is the asymptotic time complexity of calculating $f(n)$?

By request, two facts that are known and seem somewhat related to your question.

As a lower bound: infinitely many integers $n$ take time $\Omega(\log n)$. Applegate and Lagarias.
As a sort of an upper bound: $\Omega(N^c)$ positive integers bounded by $N$ reach $1$ in finite time, where $c \approx 0.84$. Krasikov and Lagarias.

Hopefully you have read Lagarias's survey before asking the question.


Best lower bound for proof complexity of graph non-automorphism problem Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in NP-intermediate. I'm looking for references that study the certificate complexity of graph non-automorphism (GNA= {G| G is rigid or asymmetric graph}).

What is the best known lower bound on the length of certificates that proves a graph is rigid ($G \in GNA$)? Also, Is there a plausible conjecture that prohibits sub-exponential certificates for Co-NP-complete problems (analogues to ETH)?

If GNA is in CoNP, and by certificate you mean any string y such that x is in GNA iff xy is accepted by a deterministic turing machine in polynomial time, then a non-trivial lower bound on the certificate size would imply P!=NP. If P=NP, then CoNP=NP=P and there is a deterministic turing machine that accepts GNA without the need of a certificate, or with a certificate whose size is equal to zero.


Resumption-based IO systems? I've been playing around with resumptions lately, mostly from Abramsky's classic paper Retracing Some Paths in Process Algebra. They are quite slick (basically solutions to the domain equation $R = I \to (O \times R)$), and very reminiscent of Kahn networks.

Of course, this observation is not original to me --- they form a traced monoidal category, and this fact was used by Abramsky and Jagadeesan to give semantics to linear logic. At any rate, note that if you feed a resumption $r$ an input of type $I$, you get an output of type $O$ and an updated resumption $r'$, which is what lets you model the fact that a dataflow node can change as it sees inputs come in.

As a result, it seems like they could give a nice API for building I/O transducers in a higher-order language like ML or Haskell, but I can't seem to find any papers describing such a thing. But they've been around for decades, and Gordon Plotkin invented them, so it's not like they've languished in obscurity. So I was wondering if anyone had seen them put to such use.

This looks a lot like the I/O API described by Felleisen et al in A Functional I/O System (or Fun for Freshman Kids).  Basically, you write (in the simpler, non-distributed setting), a series of event handlers, each of which accepts the current state, and returns an updated state. Finally, there's a to-draw handler, which produces the "output" for each state.

If we recast this API slightly, we can package up the handlers and the current state together, and each time a handler returns both a new state and a new set of handlers.  We might call this package of state and operations an "object". :)  If we then make the result a pair of this object, and the "output", then we have exactly the type of resumptions.

Interestingly, in the paper, Felleisen et al do exactly this when moving to the distributed setting -- every operation returns a pair of new state and "output" in the form of messages to be sent to the other participants in the system.


Smallest vertex cover which is also an independent set The vertex cover and independent set as a subset of nodes are always considered in a dual relationship. Have they been looked at together? What I mean is: start from a minimum vertex cover, and if it is not an independent set, add or remove vertices to make it one. So for instance, if there is an edge whose both endpoints are included in the vertex cover, remove one of them and add other nodes to maintain the covering property, but also achieve independence.

Does this kind of a subset of nodes have a name, and has it been studied? At least for acyclic graphs, it seems like there should be a "minimum deviation" way to convert a minimum vertex cover to a vertex cover which is also an independent set.

Thanks!

This is the "Independent Vertex Cover" problem. It is solvable in polynomial time. To see this, note that for every edge, exactly one endpoint of the edge must be in a vertex cover. We can reduce the problem to 2-SAT, as follows:  make a variable $x_i$ for each vertex $i$, and for each edge $(i,j)$, include clauses of length two of the form $x_i \oplus x_j = 1$.

See also https://stackoverflow.com/questions/10769971/algorithm-for-independent-vertex-cover


Circuit lower bounds and kolmogorov complexity Consider the following reasoning:

Let $K(x)$ denote the Kolmogorov complexity of the string $x$.
Chaitin's incompleteness theorem says that

  for any consistent and sufficiently strong formal system $S$, there
  exists a constant $T$ (depending only on the formal system and its language) such
  that for any strings $x$,
  $S$ cannot prove that $K(x) \geq T$.

Let $f_n$ be a Boolean function on $n$ variables s.t. the Kolmogorov complexity of its spectrum is at most $k$.
Let $S(f_n)$ be the circuit complexity of $f_n$, i.e. the size of the minimal circuit computing $f_n$.

A (rough) upper bound on for $S(f_n)$ is
$$S(f_n)\leq c\cdot BB(k) \cdot n$$
for a constant $c$ and $BB(k)$ is a busy beaver function (the maximum possible steps a halting Turing machine with a description of size $k$ can perform).
(For every $1$ in the spectrum, construct the minterm of the corresponding
truth assignment, and take OR of all these minterms together.)

Suppose now for an infinite family of Boolean functions
$L = \{f_n\}_{n}$, we have a formal proof that
$L$ requires superlinear size circuits, i.e.

$$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$$
where $g(n)\in \omega(1)$.

If we take $n$ to be sufficiently large, we will have
$$g(n) > c\cdot BB(T)$$

In particular this would be a proof that the Kolmogorov complexity of the spectrum
of $f_n$ is at least $T$, which is impossible.

This leads to two questions:

1) There should be something wrong in the above reasoning.
Mainly because it would make superlinear circuit lower bounds formally not provable.

2) Do you know of similar approaches to show barriers for lower bounds, that is, showing that certain types of (circuit) lower bounds are formally unprovable?

There is nothing wrong with your argument, but there is no contradiction. You prove that from some large enough $N$ the Kolmogorov complexity of the spectrum of $f_n$ is always at least $T$. But this statement is trivially true! Although we cannot prove that the Kolmogorov complexity of one string is large, if we have a sequence, then from some point it must contain only strings of large complexity. So what is this $N$ that you got? It must satisfy $N>g^{-1}(c \cdot BB(T))$, what is a number that we cannot compute (because of $BB$), so there is no problem at all.


What are the criteria for inviting conference papers (e.g. SODA) for special issue? This is mostly for some immigration related document that I am trying to write and want to reference an online link which mentions that only a select few papers are invited for special issue for SODA conference. Also would be good to know about the selection criteria and the panel which selects it.

You may want to refer to the editorials introducing recent special issues:

SODA 2016: https://dl.acm.org/citation.cfm?id=3230647

SODA 2017: https://dl.acm.org/citation.cfm?id=3319426

They both start with essentially the same paragraph:

  We are delighted to present a Special Issue of ACM Transactions on Algorithms, containing full
  versions of seven papers that were presented at the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) in Barcelona, Spain, on January 16–19, 2017. These papers, selected
  on the basis of their high rating by the conference program committee, have been thoroughly
  reviewed according to the journal’s highest standards.

(Emphasis mine.)

For something more detailed about the selection process, you probably want to follow Josh's suggestion from the comments: contact the PC chair directly, and ask for a brief explanation, ideally printed on official letterhead. My experience is that the process of selecting the special issue papers is not standardized, but usually involves identifying the papers that received the highest scores, and/or collecting suggestions from PC members, and then possibly having some voting procedure.


Updates on a cache-oblivious B-tree Lately I have been studying cache-oblivious data structures and algorithms. I was reading about the cache-oblivious B-tree from the Handbook of Data Structures and Applications, with hopes of actually implementing it and doing some benchmarking.

Section 38.3.1 of the book talks about the density based approach. The vEB-layout and the density thresholds seem fine, but I am missing something (perhaps even trivial) from the updates. The text explains:

  To insert a new element into the structure we ﬁrst locate the position in $T$ of the new node $w$. If the insertion of $w$ violates the height bound $H$, we rebalance $T$ as follows: First we ﬁnd the lowest ancestor v of w satisfying $γ_i$ ≤ ρ(v) ≤ $τ_i$, where $i$ is the level of $v$.

Looking at the figure, let's consider a scenario: suppose we want to insert an item with value 15. We check to see that it cannot be inserted since the height bound $H$ would be violated. Hence we must find the lowest ancestor $v$ of $w$ satisfying the mentioned bounds. If we now work towards the top of tree trying to find a suitable ancestor, we find it immediately (the item with value 13). It clearly satisfies the bounds, since its ρ is 1.

It would make a lot more sense to me if the ancestor at which we should stop is the one with value 8. Right now I see two cases: either I don't know the exact definition of lowest ancestor or the lowest ancestor $v$ should satisfy not $γ_i$ ≤ ρ(v) ≤ $τ_i$ but $γ_i$ < ρ(v) < $τ_i$.

I also took a look at Cache-oblivious B-trees by Bender, Demaine and Farach-Colton. This paper also defines the bound as $γ_i$ ≤ ρ(v) ≤ $τ_i$.

Perhaps one must consider the parent of the node to be inserted as having weight 2. Then the "find the lowest in-density ancestor" is equivalent to "find the least amount of rebuilding needed to maintain the invariants".

edit:

In the physical world, density is defined as mass divided by volume. This corresponds to the density notion in these cache-oblivious B-trees if we view each "item" as having mass 1 and each location in $\mathcal{T'}$ (the static binary tree) as having volume 1.

Before inserting an item, we want to make sure that once it is in the tree it is in a subtree that is within its prescribed density bounds. We therefore imagine that it is already there in the tree, but taking up no space yet. The reason why we might imagine that it presently takes up no space is that, well, there might not be any space for it to take up right now, as in your example.

To make sure that the tree the new item will be in is within bounds, we need to find its closest ancestor that we actually can rebalance (without increasing the height) and insert the item into while still remaining within the density boundaries. To do so, we find the nearest ancestor that will be within the density boundaries, which means using its current "volume" and its soon-to-be-correct "mass". To get the latter, we must include an extra unit of mass for the item we are about to insert.


NP-Completeness of Finding Minimum Automaton, in Gold's paper I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "System Identification Via State Characterization", and I am confused now.
I also checked Is finding the minimum regular expression an NP-complete problem? but I am still confused.

Let us call Problem 1: Finding a minimum regular expression for a
given regular expression which has same language L.

Let us call Problem 2a: Finding automaton which can explain some data D.

Let us call Problem 2b: Finding an automaton with minimum states for
Problem 2a.

In "Complexity of Automaton.." paper, it states that
"However, it is the objective of this paper to show that the construction of a minimum state
automaton which agrees with given data is, in general, computationally difficult."

Then later, in Theorem 2:
"Minimum Automaton Identification Question Qmin(D, n). Given: data D,
 positive integer n. Question: Is there a finite automaton with n states which
 agrees with D ?

Now, I can easily create an automaton which fits the data. Lets call it G. I can also minimize G to get G*, and count the number of states.
As I wrote the whole question, I realized that if the answer to the following statement is "NO", then I do need further help. If the answer is "YES", elaboration is appreciated, but a simple yes will clear lots of confusion.
Given arbitrary automaton G for language L, if we use some Polynomial algorithm
to minimize it to G* (and P =/= NP), can there exist another smaller automaton S < G
(in number of states) such that language of S is exactly L?

If answer is "NO", please proceed. If the answer is "YES", feel free to elaborate. Any help is appreciated.
First question:

Gold assumes that a blackbox can be "identified in the limit". However I find that an a regular expression: ab(ab*)* to not apply here, since we don't know the number of states in the FSM we are trying to identify. Hence, this makes me believe Problem 1 is different than Problems 2a and 2b. Correct?

Second question:

Given the data, I can easily create an automaton, then minimize it. Based on what I've seen (and yet don't understand), the minimal automaton G* is not necessarily the "minimum automaton which can explain the data". There is confusion about what "explain the data" mean. If I minimize G to get G* some known polynomial algorithm, wouldn't that be "Exact" fit for the data? meaning all the data is accepted by G* and G*'s language is only all the data?

Third question:

Depending on how second question is answered, if there could be another smaller automaton which is difficult to obtain, then that should imply that polynomial minimization algorithms may produce different "minimal" automaton, based either on the algorithm, which I find absurd, or based on the "initial constructed automaton".

I think question 3 is absurd, which is forcing me to believe that Gold meant something specific  with "agrees with given data".
Any help is appreciated.

After more and more digging, here is what I found:
First reference: Introduction to Automata Theory, Languages, and Computation 3rd Edition.
Specifically, theorem 4.26 indicates that the provided algorithm constructs a minimum state machine M for a A such that M has as few states as any DFA equivalent to A.
This was my original understanding, so the answer is "NO" to the pre-question.
Second reference: Grammatical Inference: Learning Automata and Grammar
First question:
This book was excellent source for my understanding. It turns out, Gold's construction does not necessarily "EXACTLY" fit the data. The data may be a subset of of the inferred automaton, and this is a key reason as to why eventually, identification in the limit can happen, so ab(ab*)* can be learnt, eventually, but we can never tell we learned it until we wait for ever (I see this as a halting problem sort of issue)
Second question:
The confusion occurred from the meaning of "consistent". The construction used in the paper has "holes" where an "experiment" is not known to accept or reject a string at that "point in time". It is difficult to summarize a whole chapter here, but what ends up happening is "consistent" does not mean "EXACT". Eventually, identification in the limit produces "EXACT" fit for "historical" and "future" experiments.
The reason why identification is NP-Hard is due to the holes in the algorithm. At some point a value is assumed to fill the holes, but based on the value, some inconsistency may arise, and a parsing tree is returned instead (which has large number of states). The other option is to use backtracking to implement nondeterminism and try different values (or run this in parallel...) to find the reduced automaton.
Since the algorithm is non deterministic and can find the correct consistent minimum automaton, finding the minimum automaton from data, in the limit, is NP hard.
Some Final Remarks
If we have a "complete" finite log, we can find the minimum automaton in P.
Then one may ask, what if we generate lots of experiments before we attempt to find an automaton, and assume that the log is complete?
The answer is:
If the log was indeed complete, then an algorithm in P can find the minimum state. Otherwise, the algorithm did not find the minimum state.
I believe this makes the question: "Is the Log Complete?" to be the problem here, because if we can answer that with a YES, then identification of automata from finite data would be possible (not in the limit...), which is not possible.
One way to circumvent this is to add domain knowledge, such as having an upper bound on the number of possible states.


$DTIME_1(o(n^2))\setminus$ REGULAR Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time.
Help!

Related paper: On the structure of one-tape nondeterministic turing machine time hierarchy by Kobayashi.

Related question: Why do we use single tape Turing machines for time complexity? by Kaveh.

For example, I think you can decide if $\lfloor\log_2|w|\rfloor$ is even in time $O(n\log n)$: you first overwrite the input string with all 1s, and then do $\log n$ passes over the string where you turn every other 1 into a 0 (while skipping 0s that are already there). You keep track of the number of passes modulo 2.


Why does the Fibonacci sequence produce a worst-case Huffman encoding? I noticed this in my Algorithms class, but just now got around to asking.

This paper may shed some light on the issues: http://www.springerlink.com/content/w32x70520k8jj617/


Is $PH \subseteq PP$? We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$.

Do we know whether $PH \subseteq PP$? If not, why is it that $P$ with a $PP$ oracle is stronger than $PP$? Is it possible that $PH \nsubseteq PP$ and $PP \nsubseteq PH$?

This question is very simple, but I haven't found any resources addressing it.

I asked this related but much less specific question on math overflow before learning more about the topic.

Here is a somewhat related (but different) question: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

Update: Take a look at Noam Nisan's question here: More on PH in PP?

Huck, as Lance and Robin pointed out, we do have oracles relative to which PH is not in PP.  But that doesn't answer your question, which was what the situation is in the "real" (unrelativized) world!

The short answer is that (as with so much else in complexity theory) we don't know.

But the longer answer is that there are very good reasons to conjecture that indeed PH ⊆ PP.

First, Toda's Theorem implies PH ⊆ BP.PP, where BP.PP is the complexity class that "is to PP as BPP is to P" (in other words, PP where you can use a randomization to decide which MAJORITY computation you want to perform).  Second, under plausible derandomization hypotheses (similar to the ones that are known to imply P=BPP, by Nisan-Wigderson, Impagliazzo-Wigderson, etc.), we would have PP = BP.PP.

Addendum, to address your other questions:

(1) I'd say that we don't have a compelling intuition either way on the question of whether PP = PPP.  We know, from the results of Beigel-Reingold-Spielman and Fortnow-Reingold, that PP is closed under nonadaptive (truth-table) reductions.  In other words, a P machine that can make parallel queries to a PP oracle is no more powerful than PP itself.  But the fact that these results completely break down for adaptive (non-parallel) queries to the PP oracle suggests that maybe the latter are really more powerful.

(2) Likewise, NPPP and coNPPP might be still more powerful than PPP.  And PPPP might be more powerful still, and so on.  The sequence P, PP, PPP, PPPP, PPP^PP, etc. is called the counting hierarchy, and just as people conjecture that PH is infinite, so too one can conjecture (though maybe with less confidence!) that CH is infinite.  This is closely related to the belief that, in constant-depth threshold circuits (i.e., neural networks), adding more layers of threshold gates gives you more computational power.


Minimal information needed for determine some function From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of information" is sufficient to describe a continuous function completely.
Is there a similar notion for computable functions (or Turing machines)? i.e.:
Let $T : \{0,1\}^* \rightarrow \{0,1\}$ be a Turing machine and let $\{0,1\}^{n_0}$ be the set of all binary string of lengh $n_0$. Describing $T$ on $\{0,1\}^{n_0}$ trivially requires $2^{n_0}$ values. Can we impose conditions on $T$, which will reduce $2^{n_0}$ (like continuity in the continuous domain)? Can we hope for non-trivial such conditions?

A natural condition is to bound the number of states of $T$ --- say, at most $n$. The set
$\mathcal{C}_n$
of all TM's on at most $n$ states is finite --- in fact, of cardinality $2^{O(n)}$. It is well-known that finite classes have a finite teaching dimension,
http://www.cs.columbia.edu/~djhsu/coms6998-f17/student-work/scribe-notes/teaching_dimension.pdf
of size $d_n=O(|\mathcal{C}_n|)$ --- meaning that for each $M\in\mathcal{C}_n$, some set of at most $d_n$ labeled strings uniquely identifies $M$. Taking the union of these "teaching sets" over all $M\in\mathcal{C}_n$ gives you a finite set $S\subset\Sigma^*$, which belongs to $\Sigma^{\le n_0}$ for some $n_0$. Now you required that all of the examples be of the same length, but other than that, this satisfies your criteria.

The bottom line is that for fixed $n$, the resulting $n_0$ will be a constant.


Do we care about confluence because of unique normal forms? Confluence implies uniqueness of normal forms, which is great. It is also much simpler to reason about, allowing more reusable proofs (indeed I don't imagine a way to prove UN directly for the $\lambda$-calculus).

It is however strictly stronger than UN, saying something about computations without any NF: they can be joined.

That's a nice result, but does anyone really care? What are really the practical goals of proving your calculus is confluent?

I don't know what you mean by "practical", but confluence is very useful from the semantic point of view.  Hopefully other people will be able to give you other answers from other points of view (for instance from the standpoint of abstract term rewriting, which is not my specialty).

For instance, in $\lambda$-calculi and related languages, usually the meaning of expressions is given by (something like) the smallest congruence such that $(\lambda x.M)N=M\{N/x\}$ (this is usually called $\beta$-equivalence). Reduction arises (historically, as well as technically) as an orientation of the above equality, so that one may redefine $\beta$-equivalence as $(\leftarrow\cup\to)^\ast$ (the reflexive-transitive closure of reduction and expansion), and study $\beta$-equivalence by means of reduction (there are "practical" advantages to this: for instance, $M\simeq_\beta N$ is often undecidable, whereas $M\to N$ is always decidable, and sometimes you may be able to replace $\simeq_\beta$ with $\to$ in some definition or statement of some property).

Now, confluence is equivalent to the transitivity of the following relation:

$$M\sim N\quad\text{iff}\quad \exists P.\,M\to^\ast P,\,N\to^\ast P,$$

that is, $M\sim N$ precisely when $M$ and $N$ have a common reduct. Therefore, if you have confluence, $\sim$ is an equivalence relation, and in fact it coincides with $\beta$-equivalence. The relation $\sim$ is technically much more convenient than $(\leftarrow\cup\rightarrow)^\ast$ (it involves only reduction, not arbitrary chains of reductions/expansions). So, if a calculus is confluent, it is usually a quite useful fact to know, although of course it is often only used to prove uniqueness of normal forms (which by the way, as you observe, I wouldn't know how to prove otherwise).

Also note that confluence is a sort of "practically necessary" condition for $\beta$-equivalence to be meaningful: many calculi of interest in practice are Turing complete, in which case the lack of confluence usually implies that everything is $\beta$-equivalent (one is likely to be able to concoct a term which non-deterministically reduces to every possible term).  So, in presence of confluence, $\simeq_\beta$ is a meaningful notion which may be taken as the basis, for instance, of denotational semantics; in absence of confluence, something else must be found (like some kind of behavioral equivalance, as in process calculi, which is much more complex).

Edit: as suggested by Guido, I add a further note on the additional interest of confluence with respect to uniqueness of normal forms (UN), which I had not thought of when writing my answer.

Confluence implies the following property: $N\simeq_\beta N'$ with $N$ and $N'$ normal implies $N=N'$ (syntactic equality). In other words, distinct normal forms cannot be $\beta$-equivalent. (This immediately follows from the characterization of $\simeq_\beta$ as $\sim$ given above). This property is interesting because it implies the consistency of $\simeq_\beta$ seen as an equational theory, as soon as there is more than one normal form (as is the case, for instance, in the $\lambda$-calculus).

On the other hand, UN is not enough to obtain the above property, as shown by the following rewriting system:

$$N\leftarrow M\to\Omega\leftarrow M'\to N',$$

in which all five terms are distinct and $\Omega$ is a term that reduces to itself.  We have $N\simeq_\beta N'$ and yet $N$ and $N'$ are distinct normal forms.


Complexity of Tensor Rank over an Infinite Field A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank one tensors that sum to $T$. A vector and matrix are tensors of degree 1 and 2 respectively.

The elements in $T$ come from a field $\mathbb{F}$. If $\mathbb{F}$ is finite, then Håstad proved that deciding if the rank of a degree 3 tensor is at most $r$ is NP-complete, but when $\mathbb{F}$ is an infinite field like the rationals $\mathbb{Q}$, he gives (or cites) no upper bound.

  Question: What is the best known upper bound for the complexity of deciding if the rank of a degree 3 tensor $T$ over $\mathbb{Q}$ is at most $r$?

There is a recent preprint about this: http://galton.uchicago.edu/~lekheng/work/np.pdf . It shows that most rank-related issues with tensors are NP hard over $\mathbb{R}$ and $\mathbb{C}$. (It also mentions that deciding the rank over $\mathbb{Q}$ is NP hard.)


Efficient way to generate random planar cubic bipartite graphs 3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to generate random planar cubic bipartite graphs?

I only know of algorithms that can efficiently generate random graphs with only subsets of the set of properties {cubic,planar,bipartite}, and it seems that generating those and then naively testing for the remainder of the properties would be terribly inefficient if one wants graphs with >100 vertices.

Would you be satisfied with generating planar cubic bipartite maps (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in:

Gilles Schaeffer, Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees, The Electronic Journal of Combinatorics 4(1), 1997.

Schaeffer describes how to efficiently generate (rooted) Eulerian planar maps uniformly at random using a bijection with a certain family of trees. In turn, Eulerian maps have a simple bijection with bi(partite-)cubic maps: see the second bullet point on slide 5 of this talk by Éric Fusy.

(Generating a uniformly random rooted planar bicubic map and then throwing away the rooting + embedding would give you a non-uniform distribution on planar bicubic graphs, but depending on what you have in mind that might be okay?)


Good Survey paper for k-means/k-median/k-center/facility-location I have stated 4 problems in the Question title.
All these problems are closely related and are studied in various variations. For example:

Space: Euclidean/metric/discrete/continuous/non-metric/2-D_plane...

Parameters: when $k$ or $d$ is fixed or some sort of bi-critera relaxation ...

Settings: Streaming/Online/parallel/Fault-tolerant/query/...

Constrained models: capacitated/outlier/fairness-constraints/...

Special models: $\beta$-separation/ORSS-separability/BBG-condition/...

Techniques: coreset-based/primal-dual/local-search/distance-sampling/tree-decomposition/...

...many more

There are several hardness results, approximation algorithm and parameterized algorithms known for the problem and its variants; and many are not known yet and are open.
Sometimes it happens that the research papers mention imprecise/incomplete/incorrect results, that have been previously discovered. This causes a lot of confusion. Moreover, it is difficult to go through every paper and check their results. I am looking for a (survey) paper that might give a brief idea of what all has been done in the field over the years and what are the open questions remaining in the field. It would be a great help if somebody could share such a paper.

Recently, I came across the following survey: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems
The authors only discuss the major results and mention some interesting open problems at the end.


P with integer factorization oracle I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$:

If $A$ is an oracle that solves integer factorization, what is the power of $P^A$?

I think it makes RSA-based public-key cryptography insecure ... but apart from this, are there other remarkable results?

Obviously any decision problem that can be reduced to factoring can be solved with a factoring oracle. But since we're given the ability to make multiple queries, I tried to think of a non-trivial problem for which one would want to make multiple queries.

The problem of computing the Euler totient function seems like such a problem.  I don't know  how to solve the decision version of this problem by a Karp-reduction to the decision version of factoring.  But with Turing reductions, it's easy to reduce this to factoring.


Second Smallest $s$-$t$-Cut in a Network Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem:

  Input: A network $N$ and a number $k$, all in binary.
  Output: A $k$th smallest $s$-$t$ cut.

A $k$th smallest $s$-$t$ cut $(S,T)$ is any $s$-$t$ cut, such that there are exactly $k-1$ $s$-$t$ cuts whose capacities

are pairwise different and
truly smaller than the capacity of $(S,T)$.

I would like to know how it can be computed and whether this can be done efficiently as for the case $k=1$.

The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See:

H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ best cuts in a network. Oper. Res. Lett. 1(5):186–189, 1982, doi:10.1016/0167-6377(82)90037-2.

H. W. Hamacher, J.-C. Picard, and M. Queyranne. On finding the $K$ best cuts in a network. Oper. Res. Lett. 2(6):303–305, 1984, doi:10.1016/0167-6377(84)90083-X.

H. W. Hamacher and M. Queyranne. $K$ best solutions to combinatorial optimization problems. Ann. Oper. Res. 4(1–4):123–143, 1985, doi:10.1007/BF02022039.


In what class are randomized algorithms that err with exactly 25% chance? Suppose I consider the following variant of BPP, which let us call E(xact)BPP:
A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/4 probability and every word not in the language with exactly 1/4 probability. Obviously EBPP is contained in BPP but are they equal? Has this been studied? What about the similarly definable ERP?

Motivation. My main motivation is that I wanted to know what the complexity theoretic analogue of the ``correct in expected value'' randomized algorithm of Faenza et al. (see http://arxiv.org/abs/1105.4127) would be. First I wanted to understand what decision problems such an algorithm can solve (with worst case polynomial running time). Let us denote this class by E(xpected)V(alue)PP. It is easy to see that USAT $\in$ EVPP. Also easy to see that EBPP $\subset$ EVPP. So this was my motivation. Any feedback about EVPP is also welcome.

In fact, their algorithm always outputs a nonnegative number. If we denote the decisions problems recognizable by such an algorithm by EVP(ositive)PP, then we still have USAT $\in$ EVPPP. While EBPP might not be a subset of EVPPP, we have ERP $\subset$ EVPPP. Maybe using these we can define a (nonnegative) rank for decision problems.

On a side note, it's not clear that EBPP is a robust class. For example, if instead of allowing the algorithm to flip an unbiased coin, if it were given an unbiased 3-sided coin, or a 6-sided die, it's not clear that you get the same class. BPP remains the same if you change these details.

Anyway, your primary question is whether EBPP is equal to BPP or not. It seems to me that EBPP is closer to P than it is to BPP. Consider the query complexity or oracle version of these classes where they have access to a large input string and have to make queries to learn bits of this string. If you have a P algorithm that computes a function $f$ with $Q$ queries, then there exists an exact representing polynomial of degree $Q$ for $f$ over $\mathbb{R}$. (This is the usual polynomial method argument.) On the other hand, if you have a BPP algorithm, then you get a degree $Q$ polynomial over $\mathbb{R}$ that approximates $f$ in the sense that its value is close to the value of $f$ at every input.

Given an EBPP algorithm for a function $f$, we can construct a polynomial that outputs 1/4 when the answer is NO and 3/4 when the answer is YES. By subtracting 1/2 and multiplying by 2, you can get an exact representing polynomial, just like in the case of P. This suggests to me that EBPP is closer to P.

This observation can also be used to show an oracle separation between EBPP and BPP. Consider the promise-Majority problem where you're promised that the input has either more than 2N/3 1s or less than N/3 1s and you have to decide which is the case. This is clearly in BPP. Using the polynomial argument described above it can be shown that this function requires $\Omega(N)$ queries for an EBPP machine.  But note that you can also prove an oracle separation the other way, between P and EBPP. So maybe oracle results don't say much for this problem? Or maybe what they say is that it will be hard to show equality in either direction.


Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$ 1) What classes contain $\textbf{PSPACE}$, are contained in $\textbf{EXP}$ and (presumably) are not equal to $\textbf{PSPACE}$ nor to $\textbf{EXP}$?

A possible class satisfying this requirement: the class of languages that can be recognized in exponential time and subexponential memory.

2) Which of these classes are provably strictly larger than $\textbf{P}$?

Depends what you mean by "class".

I don't know of any natural class that satisfies that, but certainly one can do the following:

Consider the set of languages that are decidable in time $2^n$ (exactly, not just any exponential). This is strictly contained in EXP by the time-hierarchy theorem.
Take the union of this set and PSPACE, and you have a class that strictly contains P (again, time hierarchy), contains PSPACE, and is contained in EXP (and presumably, if PSPACE$\neq$ EXP, then there is also strict containemnt here).


Computing topological sort while keeping edges "short" Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.

Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort with minimum maximum edge length (MEL), where MEL in a valid topological sort order $v_1, v_2 \ldots v_n$ is defined as $\max_{(v_i, v_j) \in E} \ |j - i|$.

Your problem is known under the name MINIMUM DIRECTED BANDWIDTH.
It is NP-complete:

  M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth:
  "Complexity Results for Bandwidth Minimization"
  SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495

It is problem [GT41] in the NP-completeness book by Garey and Johnson.

The special case where every vertex in $G=(V,E)$ has indegree $\Theta(|V|)$ has a polynomial time approximation algorithm with worst case guarentee 2:
https://www.nada.kth.se/~viggo/wwwcompendium/node54.html


Algorithmic lens in the social sciences Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In particular CS has made an impact on biology through computational biology, on physics through quantum information processing, and AI and complexity theory seem to regularly interact with neuroscience. The natural sciences seem relatively comfortable with TCS.

Thus, my question is in regard to the impact of TCS on the social sciences.

  What novel and important insights into the social sciences has TCS provided?

I am vaguely aware of the impact of algorithmic thinking on economics (through game theory). In fact algorithmic game theory is now a part of the 'standard domain' of TCS, so lets exclude AGT answers unless they specifically altered existing theories in the social sciences.

Another example I recall is from linguistics in the learnability vs. innateness of grammar (i.e. poverty of the stimulus) debate. Gold's theorem about the unlearnability of context free grammars provided a strong argument for innate-ness and helped convince some skeptics (I am not sure if this is still valid, since SCFG seem to be learnable). I am more interested in examples of this type, where TCS thinking helped change or shape existing theories in the social sciences.

References to books/surveys are appreciated.

This example is from social choice theory, and elections in particular. We know that Arrow's theorem (and the Gibbard-Satterthwaite theorem in general) rule out the possibility of elections that are fair, non-manipulatable and without other bizarre consequences. But a seminal paper by Bartholdi, Tovey and Trick showed that finding the desired 'hack' to break a voting scheme was NP-hard, and there's been a large body of work by many researchers on the complexity of problems in the realm of election design. There's a nice survey by Faliszewski, Hemaspaandra, and Hemaspaandra on this topic.


Characterize a point cloud Background: I have multiple point clouds (sets of objects) $\{S_i\}_{i\in\mathbb{N}}$ of variable size and "purity" (meaning that some sets contain very similar objects, some show a high diversity; some sets are large, some are small). Each object is characterized by a $n$-dimensional continuous feature vector $v_j \in \mathbb{R}^n$, each set can therefore be seen as a matrix $M_i \in \mathbb{R}^{|S_i| \times n}$.

I want to classify these point clouds using a binary classifier into "pure" and "diverse".

Idea: I was thinking about covariance. This way every point cloud is represented by its $n \times n$ covariance matrix.

Question: What other features can I use to characterize the individual point clouds? How else can I transform these matrices of different shape to representations of fixed length representations that can be passed on to a classifier?

You can use essentially any centroid-based clustering algorithm to define a notion of "coherence" or "purity" of a cluster. Let's say you've chosen some particular metric $||\cdot||$ on $\mathbb{R}^n$ (I'm using norm notation but any metric will do). Using your notation, $S_i$ is the $i$th "cluster". For each $S_i$, find the* point $c_i\in\mathbb{R}^n$ that minimizes
$$ F(c):=\sum_{x\in S_i}||x-c||\qquad(*)$$
over all $c\in\mathbb{R}^n$. Let $F(c_i)$ be the purity score of $S_i$; it might actually be better to consider the normalized version $F(c_i)/|S_i|$. Smaller values means more homogeneity or "purity".

*How to do this computationally? Try (sub)gradient descent. If the minimum is not unique then break ties arbitrarily.


Why study type theory? After reading the literature on type theory (especially the constructive kind - CTT) I'm left wondering "why" should one study type theory, specifically within the confines of "computing" in general?

I understand how type systems (loosely speaking) were created to avoid various paradoxes and the correspondence between philosophy, logic, lambda-calculus and the how it comes together for CTT to serve as a foundation of mathematics. Fair enough.

Now, functional programming (FP) languages like Haskell, Scala that can be used in large projects are based on an inconsistent logic - making any kind of (automated) formal reasoning about them nearly impossible - but that seems to be the very need/power of TT! E.g., theorem proving and proof assistants and the notion of programs as proofs. But none of this carries over to FP languages.

So my question is trying to understand the bigger role i.e., interplay of TT and computing taken together. Most FP languages have just "good enough" type systems (e.g., Haskell > Java). The problem of "type inference" is in some way similar to "logical inference" and doesn't seem all that complicated for simple types. I'm guessing things become undecidable after a particular threshold. Fair enough. I understand its need till this level. But is that it? It seems one can understand type systems/inference without really diving into the details of TT per se.

Since FP languages don't really borrow much from TT other than "type systems/inference", why bother studying the theory in depth especially within computation theory? It seems that after studying a good deal of TT, for fun, I'm still left wondering "what did I gain" - both as a theoretician and a software practitioner? What "is" the aha understanding that one gains at a deeper level - since very little of TT's power/awesomeness actually gets carried over to commercially viable FP languages (and not Agda, Epigram etc.,)?

(PS: Here's a similar question on Math.SE- but that's from a mathematical POV and I get that from that perspective. I'm struggling to see TT's importance when concerned about computing and software engineering in general)

Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic.

A general purpose programming language has general recursion. This allows it to populate every type, but we would not conclude from this fact that programming is a useless exercise, would we?

In the theory of programming languages types are used as a safety feature ("A well typed program does not go wrong" sad a famous man), as an organizational device, and a tool for program analysis. None of these purposes requires that there be an empty type.

Type inference is only one aspect in which type theory relates to programming languages. Some other uses of types in programming languages are:

Specification: before the programmer starts writing code he writes down the type of the program he is after. He specifies (although usually not fully) what he wants. This is also useful for communication between programmers.
Modularization: when several pieces of software need to be assembled together we have to make sure they fit. One way of doing this is to speficy the interfaces through which the pieces connect. This can be done with types.

Dependent types appear in programming languages, but in limited form (because general dependent types cannot be handled automatically by the compiler). For instance, an ML-style module is a dependent sum, while a polymorphic type can be seen as a dependent product.

You ask what is gained by studying type theory? Clarity of mind where there was only Visual Basic before. Ability to write 30000 lines of code without making it look like the Flyng Spaghetti Monster. Inner peace and feeling of superiority over the unfortunate users of Lisp.


Is P equal to the intersection of all superpolynomial time classes? Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$.

It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf {DTIME}}(f(n))$ for every superpolynomial time bound $f(n)$. I wonder, wether the converse of this statement is also true? That is, if we know $L\in {\mathsf {DTIME}}(f(n))$ for every superpolynomial time bound $f(n)$, does it imply $L\in {\mathsf P}$? In other words, is it true that
$${\mathsf P} = \cap_f {\mathsf {DTIME}}(f(n))$$
where the intersection is taken over every superpolynomial $f(n)$.

Yes.

In fact, by the McCreight-Meyer Union Theorem (Theorem 5.5 of McCreight and Meyer, 1969, free version here) a result of that I believe is due to Manuel Blum, there is a single function $f$ such that $\mathsf{P} = \mathsf{DTIME}(f(n))$. This function is necessarily superpolynomial, but "just barely."

The theorem applies more generally to any Blum complexity measure $\Phi$ and any union class $\bigcup_{f \in S} \mathsf{BLUM}_{\Phi}(f(n))$ where $S$ is a c.e., self bounded set of total computable functions. (A set of functions $S$ is c.e. if there is a single partial computable function $F(i,\vec{x})$ such that $S = \{f_i(\vec{x}) | i \in \mathbb{N}\}$ where $f_i(\vec{x}) := F(i,\vec{x})$. Self-bounded means that for every finite subset $S_0 \subset S$, there is a function in $S$ that dominates all $g \in S_0$ almost everywhere. "$\mathsf{BLUM}_{\Phi}$" is a notation I haven't seen before, but I like it :) - I'm using it for the $\Phi$-bounded analog of a time-bounded complexity class.)


Efficiently modeling Turing machines in Peano Arithmetic The (undecidable) Peano Arithmetic (PA) is powerful enough to model Turing machines.
Consider a standard first order axiomatization of Peano Arithmetic and a standard Hilbert-style proof system $\mathcal F$.

Is it true that every first order informal proposition $P$ about computation and Turing machines has a corresponding formal formula $\varphi$ in Peano Arithmetic which is equal in size up to a polynomial blow-up: $|\varphi| = O(|P|^k)$ for some fixed $k$ which is independent of $P$?

Furthermore if $P$ has an informal short proof (polynomial in $|P|$), is it true that the corresponding $\varphi$ in PA has a polynomial length proof with respect to $|\varphi|$

As a trivial example consider the following Turing machine (in pseudocode):
M:
n=100
while n > 0 do n = n - 1

and the informal proposition: $P \equiv \text{ M doesn't halt in less than 90 steps}$
$P$ can be converted to a formula $\varphi$ in PA; and this $\varphi$ must "embed" a symbolic representation of M and some kind of operational semantic. But can the conversion be done efficiently (polynomial time and space)?
Furthermore there is a trivial "informal" short proof of $P$, but does the corresponding formal proof in PA ($\mathcal F \vdash \varphi$) have a polynomial length size with respect to $|\varphi|$?
Edit: as noted by Kaveh the "informal" term above is confusing.
I could restate the two questions above in this way: if $P$ is a true mathematical statement that is expressible both in ZFC (as $\varphi'$) and PA (as $\varphi$). Is it always true that $| \varphi | \in O(|\varphi'|^k)$ for some fixed $k$ independent of $P$? What about the size of the corresponding proofs in the two axiomatizations (assuming that $\varphi'$ is provable in ZFC and $\varphi$ is provable in PA)?
But this lead to another question:

Is it true that every "human written proof" that is expressible in ZFC has indeed an "efficient" representation in ZFC? i.e. a (rather informal) proof of $\#p$ pages in my favourite paper cannot become a $O(2^{\#p})$ long formal proof in ZFC ? :-)

I am not sure I understand the question, specially the informal part. If by it you mean essentially how we generally argue for correctness of things, I woke interpret it as day proofs in ZFC or something like that.

In any case we can express provability of a statement in a computably axiomatizable system in PA (and in fact in weaker systems). Now you are asking if this can be expressed as efficiently in PA as in the stronger system. The answer is yes, just express that the Turing machine that search for a string is a ZFC proof of the formula halts. The size of the description of such a machine is polynomial in the size of the ZFC formula.

The answer to the second question is no. Just consider a computable function that grows so fast that PA cannot prove its totality but ZFC van prove its totality.

The key idea really is that the language of ZFC itself is very easy to capture. We can express that string $\pi$ is a ZFC-proof of $\varphi$ in much simpler systems that ZFC (e.g. Cook's $V^0$ which captures computation in $AC^0%).

If we can express that, then we can express anything ZFC can express. That is there is polynomial-time computable function $t$ that maps any well-formed formula in the language of ZFC to a formula in the language of PA such that the formula is provable in ZFC iff there is a string that PA proves it is a ZFC proof of the the translation with: just encode the ZFC proof, PA can verify syntactically that it is a valid ZFC proof, and if there is such a string that PA proves is a ZFC proof of the formula, then it is actually a ZFC proof of the formula.

It is key here that I didn't quantify for the existence of the ZFC proof in the PA translation. The reason is that PA might not be able to prove the existence generally. E.g. let $f$ be computable function whose totality is provable in ZFC but not in PA. Then the formula $\forall x \exists y f(x)=y$ is probable in ZFC but not in PA (with any resonable encoding). The reason is that if we can prove it then we prove the totality.

This is generally related to what is called interpretability and interpretation in logic. Essentially we have L1 and L2 and they have their own semantics, and we ask if everything in L1 can be faithfully expressed in L2. Think of the formulas as capturing the subsets of the standard models of those languages. E.g. for ZFC this would be the standard model $\mathbb{V}$ while for PA this would be standard natural numbers $\mathbb{N}$. Before thinking about expressing things, you need to think about how subsets of these two structure map to each other. What does it mean to map a set in ZFC to a set in PA. We can restrict our interest to subsets of $\omega$ in ZFC. Then the question becomes. We can restrict ourselves to arithmetic subsets of $\omega$. Then these subsets are expressible in PA clearly. For any such set we have a PA formula.

For size we really need to talk about families of formulas. If the family is uniform, that is it is obtained by sectioning another arithmetic formula, then the size relation is still polynomial: let the formulas in ZFC be $\varphi_n(x) := \varphi(n,x)$. To obtain the translation in PA, translate $\varphi$ and then plugin $n$: $[[\varphi_n(x)]] := [[\varphi(x,y)]]_{y/n}$. The only part that changes is $n$, the rest remain the same.

For provability the story is not about standard models but also non-standard models that satisfy the axioms. Is it the case that every function over natural numbers that is total in every model of ZFC is total in every model of PA? The answer is no.


Series-parallel DAG characterization According to this Wikipage series-parallel graphs are characterized like this:

2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to $K_4$.

I couldn't find a similar characterization for series-parallel directed acyclic graphs (DAGs), however I think that the prohibited subgraph in this case can be a little simpler ($K_4$ minus one edge plus specific orientation):

Is it correct? Is it proven anywhere?

The two-connected series-parallel DAGs are also called 2-terminal series-parallel graphs. The graph in the figure is also known as Wheatstone graph and is known as the example graph for demonstrating Braess' paradox in algorithmic game theory.
It was shown [1, Theorem 5.3] that a DAG is 2-terminal series-parallel if and only if it does not contain a subgraph that is homeomorphic to the Wheatstone graph.
1 Pietro Cenciarelli, Daniele Gorla, Ivano Salvo: Inefficiencies in network models: A graph-theoretic perspective. Information Processing Letters 131 (2018) 44–50.


Approximability of the genus problem What is currently known about the approximability of the genus problem? A preliminary search tells me that a constant factor approximation is trivial for sufficiently dense graphs, and an $n^\epsilon$-approximation algorithm has been ruled out. Is this information up-to-date, or are there better bounds known?

The best published results all appear in a 1997 paper by Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky.

For any fixed $\varepsilon>0$, computing the genus of a graph with additive error $O(n^\varepsilon)$ is NP-hard.
There is a trivial linear-time algorithm to embed any $n$-vertex graph of (unknown) genus $g$ on an orientable surface of genus $\max\{4g, g+4n\}$: Assign an arbitrary cyclic order to the edges leaving each vertex (keeping loops and parallel edges together).  In other words, when the genus is large, every embedding is a good approximation of the best embedding.
There is a polynomial-time $O(\sqrt{n})$-approximation algorithm for bounded-degree graphs.

It is an open question whether there is an efficient constant-factor approximation algorithm.


TCS conferences for undergraduate students? I have noticed that ICFP has a student volunteer program and research program that accepts undergraduate students and POPL have the Programming Language Mentoring Workshop, so I was wondering if there are any other conferences with similar programs within TCS?

Also, would it be very likely that an undergraduate student would get any funding for these programs, as I am assuming the organisers would prefer postgraduate students? I would be very interested in attending the PLMW at POPL but as it's in India next year, it would be hard to self fund...

Edit: Thanks for the suggestions, I have checked some of them out, but I should have probably added that I am in the UK, so some of them would be quite far, but I know of a couple of similar undergraduate conferences to the ones mentioned by vzn so I will consider that route too...

The POPL-colocated PLMW, which you mentioned, certainly provides travel support for undergraduate as well as graduate students.  I personally know undergrads who've been supported. If you're interested in PL research (of any kind, not just POPL-like research) I encourage you to apply.

The ACM student research contest (of which the ICFP SRC is a part) includes categories for both undergraduates and graduates. For SRC at SIGPLAN affiliated conferences like ICFP or PLDI, you can apply to the SIGPLAN PAC program for travel support.


Repeated Quine program A Quine is a computer program which produces a copy of its own source code as its only output. Is there any Quine program that could print itself out n times, with n specified some way in the program?

Fun question! As a base I will use this Haskell quine I found on Wikipedia:

main=putStr(p++show(p))where p="main=putStr(p++show(p))where p="

You can make it print out two copies of itself by replacing the occurrences of p++show(p) with p++show(p)++p++show(p). If you see why, the pattern to achieve variable repetition should be clear.

I will be using the following function that calculates the nth iterate of f on x:

iterateN n f x = (iterate f x) !! n

I'll assume it's available as a library function. You can easily embed its definition directly in the quine, but that would clutter the presentation without good reason. Now the rest is simple:

main=putStr(iterateN 42(++(p++show(p)))[])
  where p="main=putStr(iterateN 42(++(p++show(p)))[])where p="

The line break was inserted to aid readability; remove it if you want exact self-replication.


Is this tree minimization problem NP-complete? I'm totally new to complexity theory, hence don't know much about how reductions work. So, I'm not sure how hard the following problem is. Please let me know what kind of problems I should look at to attempt for a reduction to my problem (if it is NP-hard or complete). Even reduction from that problem to my problem (yielding this is NP-hard) would be a good result to have.

The problem is the following. Suppose, we have the set of all possible 'single rooted' trees with $n$ nodes, denoted by ${\cal T}$. The set of nodes is denoted by $N$. Each node has some intrinsic values $\gamma_i$ (these are given beforehand). The function $\mu : 2^N \to \mathbb{R}$ maps the children of each node to real numbers, and this function is also given beforehand. Another function $f: {\cal T} \to \mathbb{R}$ maps the subtree of a given node to reals. Now the problem is,

$$ \min_{T \in {\cal T}} \sum_{i \in N} f(T_i) \mu (C_{p(i)}) (\gamma_{p(i)} - \gamma_i).  $$

Where $T_i$ is the subtree rooted at $i$, $p(i)$ is the unique parent of $i$, $C_{p(i)}$ is the children set of $p(i)$. Given a tree $T$, both $f$ and $\mu$ are computable in linear time. The problem basically is to find the right connection of nodes over a tree.

Thanks in advance.

%%% Editing after getting the answer from Yuval %%%

Maybe I was unclear. For single rooted trees with $n$ nodes, one can have $(n-1)!$ possible trees (this can be enumerated using the incidence matrix of the tree and considering the placements of 1 in the upper triangular part), and in each of those trees, there are $n!$ ways to place the nodes (remember $\gamma_i$s are node identity specific). And so, in each of the $n! \times (n-1)!$ possible configurations, you'll get a value for the sum. The problem is to find the minimum over such a huge space. My question is: do there exist efficient algorithms to compute this min? Or, is the problem hard, i.e., no efficient algorithm exists?

Your problem is ill-defined. Since the functions $f\colon \mathcal{T} \rightarrow \mathbb{Q}$ and $\mu\colon 2^N \rightarrow \mathbb{Q}$ (rather than real-valued) have a very long description, you can go over all possible trees $T \in \mathcal{T}$ in polynomial time.

To make the question more meaningful you might want the algorithm to have oracle access to $f$ and $\mu$, and then instead of NP-completeness you might want to prove a lower bound on the number of evaluations of $f$ and $\mu$.

Another possibility is that $f$ and $\mu$ have some structure and so can be specified succinctly. If this is the case, then you need to refine the problem reflecting that feature.

A similar problem occurs in submodular optimization. Suppose we want to maximize a monotone submodular function over a matroid constraint. There are several randomized polynomial time algorithms giving a $1-1/e$ approximation. There is a lower bound by Vondrák showing that in the (so-called) value oracle model, any better approximation requires evaluating the function at exponentially many places (this lower bound is information-theoretic rather than complexity-theoretic). Feige proved that a special case of the problem, maximum coverage, is NP-hard to approximate better than this ratio. Finally, Vondrák and Dobzinski show how to lift the value oracle result to a complexity result in the succinct representation model, assuming RP$\neq$NP (rather than P$\neq$NP as in Feige's result); the technique (whose main ingredient is list-decoding) also gives results that Feige's can't.


How should one simulate self-avoiding random walks? There is a trivial method for simulating a random walk through a graph by exponentiating a stochastic adjacency matrix, but the problem becomes harder if you ask that the random walk be self-avoiding.  In other words, the process must traverse the graph using paths, like an infection or something.

If the edge probabilities are large, there is a simple Monte Carlo algorithm :  In each trial, you simply delete each edge $e$ with probability $1-p_e$, compute the new graph's connected components, and increment a counting matrix by matrices of 1s for each contacted component.  You divide by the number of trials at the end.

Does anyone know any algorithm for doing this computation when the probabilities are quite small?

If the graph isn't too highly connected, you can find some minimum cut sets, and do inclusion-exclusion counting on them, but such an approach is doubly exponential in the size of the cut sets.  There are various optimizations for specific cases of high connectivity too, like treating all the clique subgraphs separately via the obvious computation.  Any more general ideas?

I'm not sure if I'm interpreting your question correctly, but it sounds to me that you're asking not about simulating self-avoiding random walks, but about enumerating self-avoiding random walks.  I say this because you talk about exponentiating an adjacency matrix, which will give you a (weighted) enumeration of random walks.

I'm not sure if there is much literature on enumerating self-avoiding walks in general graphs; I believe that most attention has been focused on self-avoiding walks in lattices in Euclidean space, and that's what my comments below are based on.  I suspect that many of the ideas will carry over to general graphs.

The classic tool for reducing the labor involved in exactly enumerating self-avoiding walks is the lace expansion.  You should be able to locate the relevant literature easily with that keyword.  For highly connected graphs, though, my guess is that the lace-expansion idea won't help too much (but then maybe nothing will help much in that case).

If you're satisfied with approximate enumeration then there are a few options.  See EJJ van Rensburg's 2009 paper on "Approximate enumeration of self-avoiding walks" for a survey.  See also "Self-testing algorithms for self-avoiding walks" by Randall and Sinclair (2000).


Complexity of problem that can be solved by exponentially many SATs I have two decision problems (function problems, actually) that are closely linked.  The first one consists in finding a variable assignment to $x$ Boolean variables so that a specification $A$ is met.

The whole problem can be reduced to FSAT and vice versa, making it FNP-Complete.

Now there's a second problem related to the first, which is to determine all variable assignments to the $x$ variables, for which $A$ is met.

What is the computational complexity of this problem?

It can be solved by applying SAT $2^x$ (i.e., an exponential number of) times; so that is not a valid reduction.

This is like finding all satisfying assignments to a SAT problem.  Strangely I did not find much on this in Papadimitriou's book.

The problem you defined is not in FNP as by definition the length of the answer should be polynomial in the length of its input.

Even if we are guaranteed that the length of "y" (output of the function) is polynomial in length of formula (i.e., there are at most polynomially many answer), this problem is not FNP except P= CoNP.

Proof:

$$\hspace{-1cm}  F(\phi)= y \Leftrightarrow  \forall A: $$
$$\hspace{5cm}                 {\huge(} A\models \phi \Rightarrow M(A,y) \land $$
$$\hspace{5cm}       A\not\models \phi \Rightarrow \lnot M(A,y){\huge )} $$

Where $M(A,y)$ is a polynomial time computable function returning true iff assignment $A$ is in the set of assignments $y$.

Definition of FNP requires us to have a polynomial time function $P$ given $\phi$ and $y$,  returns true iff $F(\phi)=y$. That is, deciding if the following formula is tautology or not should be verifiable in P:

$$\Phi (A)= {\huge(} \left(A\models \phi \Rightarrow M(A,y)\right) \land     \left(A\not\models \phi \Rightarrow \lnot M(A,y)\right){\huge )} $$


Sorting using a black box Assume that we want to sort a list $S$ of $n$ real numbers.
Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly.
How much advantage can we gain using this black box?

For example, can we sort the numbers with only $O(\sqrt n)$ calls to the black box?
The best algorithm that I have found uses $n$ calls to the black box.
But I haven't been able to improve it further.
Here is my algorithm which is similar to merge-sort:

First partition the list $S$ into $\sqrt n$ lists $s_1, s_2, ..., s_{\sqrt n}$ with approximately $\sqrt n$ size.
Then use $\sqrt n$ calls to the black box to sort these lists.
Finally, merge the sorted lists using the black box as follows:

Put the smallest elements of the lists in a new list $L$,
then call the black box to sort it.
The number in $L[1]$ (first and smallest element of $L$) will be
the smallest number in $S$.
We can put it in the first place of the output list.
Assuming the element has been chosen from $s_j$,
we replace $L[1]$ with the second smallest element of sort list $s_j$,
and again run the black box on it to compute the second smallest member of $S$.
We continue till all the elements are sorted. The total number of black box calls for this part will be $n - \sqrt n$. Therefore overall the total number of calls will be $n$.

On the other hand, it looks like we should be able to obtain a lower-bound using the lower-bound on the number comparisons needed for sorting as follows:
We can implement the black box using $\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$ comparisons.
If we can solve the problem with $o(\sqrt n)$ calls to the black box and merging in linear-time we can sort $n$ real numbers with $o(n \lg n)$ comparisons which is impossible.

I guess we could prove that $\Omega(n)$ is a lower-bound for the number of calls to the black box, since lots of comparisons using in the black box would be shared and therefore are recounted in our argument.

UPDATE: As the the other posts suggest, an $\sqrt n \lg n$ is also achievable.

I think your question was addressed in Beigel and Gill's paper
"Sorting n objects using k-sorter" from 1990 and the abstract of the paper says it all:

  A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between $\frac{n \log n}{k \log k}$ and $\frac{4n \log n}{k \log k}$, up to first-order terms in n and k.


What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity? If we have some string $x$ and a permutation $g$ which preserves the bits of $x$, we can store the value of $x$ on each of its $g$-orbits as well as $g$ instead of storing $x$ and we can reconstruct $x$ using this information in the obvious way.

Let $M_x$ be the set of Turing machines which print $x$ on their tape given any input, let $enc(M)$ be some reasonable encoding of Turing machines, and let $\langle g \rangle$ be the subgroup generated by $g$. Given $x \in \{0, 1\}^n$, we define

$K(x) = min_{M \in M_x} |enc(M)|$,

$Aut(x) = \{ g \in S_n \mid \forall i \in [n], x_i = x_{i^g} \}$,

$orb(g) = |\{ i^{\langle g \rangle} \mid i \in [n] \}|$,

and, for $g \in Aut(x)$, $b_{g,i}(x) = $ the value of $x$ on the $i$th orbit of $g$, ordering the orbits by the ordering already present on their lowest elements.

We extend $enc$ to $g \in S_n$ such that $enc(g)$ is the smallest encoding of a Turing machine which outputs $g$ in cycle notation on any input.

Finally, we define $GC(x) = min_{g \in Aut(G)} | b_{g, 1} ... b_{g, orb(g)} enc(g) |$.

I'm curious about the relationship between $K$ and $GC$. In particular, I suspect there exists some family of strings $x_{i \in \mathbb{N}}$ such that $K(x_i) \in o(GC(x_i))$ as functions of $i$, but I have no clue how to prove that or really why I suspect it, other than the fact that permutations just seem much less able to be clever than general Turing machines. The other natural thing to suspect would be that somehow these two things are measuring roughly the same thing and somehow this symmetry method is "complete" for the Kolmogorov sort of compression.

They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ (also in ascending order). Then the "GC" description is just $01enc(g)$, whose length is $2 + K(g)$. But $K(g) \leq K(x) + O(1)$, since the above description of $g_x$ gives a uniform construction of $g_x$ from $x$. So we have $GC(x) \leq 2 + K(g) \leq K(x) + O(1)$.


Application of Yao's Minmax Principle for Adaptive Randomized Algorithms Reference Request: I am interested in references where Yao's Minimax Principle is applied for adaptive randomized algorithms if any. More generally, I am interested in minimax lower bound results for adaptive randomized algorithms.

You may find this video useful:
https://www.youtube.com/watch?v=0vrqCDcxbxs&t=22s
Also, this video here (time 00:43) states some books that can help:
https://www.youtube.com/watch?v=mQQ36cDnmR8&t=158s


Cook reduction for search problems, by universal property? A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be reasonable if for all $(x,y)\in R$ the word $x$ is at least as long as $y$.

Let $R$ and $S$ be reasonable search problems. Consider the following two properties.

There is a Cook-reduction from $R$ to $S$ (That is, there is a polynomial-time oracle Turing machine $M$ such that for all $f$ solving $S$, the function $M^f$ solves $R$. This is Definition 3.1 of Goldreich's "P, NP, and NP-Completeness: The Basics of Computational Complexity".)
For all functions $f$ such that $S\in\mathsf{FP}^f$, we have $R\in\mathsf{FP}^f$. (Here $\mathsf{FP}^f$ is the set of search problems solved by $M^f$ for some polynomial-time oracle Turing machine $M$.)

Clearly (1.) implies (2.). Also, if $S$ solves itself (i.e. $S$ is a function) then (2.) implies (1.) because we can take the oracle in (2.) to be $S$ itself to obtain an appropriate $M$. Does (2.) imply (1.) in general? I'd guess the answer is no, but I can't think of a counterexample.

(2.) implies (1.) by a standard compactness argument.

First note that it suffices to exhibit a Cook-reduction $M$ from $R$ to $S'$ for any relation $S'$ such that $S(x,y)\iff S'(x,y)$ for all but finitely many values of $x$. This is because we can then give a Cook-reduction from $R$ to $S$ by simulating $S'$ using $S$.

Suppose for contradiction that there is no such Cook-reduction. Let $M_1,M_2,\dots$ be a enumeration of polynomial-time oracle Turing machines. Pick a sequence $S_1\supseteq S_2\supseteq \dots$ as follows. Let $S_1=S$. Suppose we have constructed $S_k$ such that $S_k(x,y)\iff S(x,y)$ for all but finitely many $x$. We know that $M_k$ is not a Cook-reduction from $R$ to $S_k$: there is some $f$ solving $S_k$ and some $x$ such that $R(x,M_k^f(x))$ does not hold. Set $S_{k+1}$ to be the relation that agrees with $f$ on all the oracle queries used by evaluating $M_k^f$ on $x$, and otherwise agrees with $S_k$.

Pick a function $f$ solving $S_k$ for all $k$. Clearing $S\in\mathsf{FP}^f$, but by construction $R\notin\mathsf{FP}^f$.


Extended version of the paper "Consistent Hashing and Random Trees" with proofs I've been reading the following paper:

David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web", 1997. pdf

In the paper the authors mention that
the proofs will be available in the "full paper".
But I cannot find any extended version of the paper with proofs.
Can someone direct me to a version with the proofs?

Answering my own question.

I found that the authors never published an extended version with proofs.

The closest thing to an extended paper is,

  Rina Panigrahy. Relieving hot spots on the worldwide web. 1997. 1

which was the Master's thesis of Rina Panigrahy (under Prof. Karger & Prof. Smith), who's also a co-author of the paper under discussion.  It is a good, detailed reference to the original paper with all the proofs I needed.


(0,1)-vector XOR problem this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. have seen similar problems in the literature but not this one in particular.

will write it in terms of bit-vectors because thats easiest for me.

  let there be a set of bit-vectors of size $n$, $v_1, v_2, v_3, ... , v_n$. consider the bitwise XOR operation. given a target vector $v_0$. find a subset of vectors such that the bitwise XOR of the set equals the target vector. what is an efficient (or ideally, optimal) algorithm to find a subset?

the brute force algorithm enumerates the powerset of size $2^n$ and lists the 1st subset found. (slightly?) more efficient would look at 1-positions in the target and exclude subsets that do not have at least 1 vector with a 1 in a 1-position of the target.

the subset may or may not exist. it may or may not be unique.

closely related questions: (1) find the smallest subset, (2) output T/F depending on whether such a subset exists.

have a suspicion one of these problems is NP complete.

looking for references, insight etc. it would be interesting to know if there are "hard" vs "easy" inputs etc

as I wrote on the other question this seems closely related to the subset sum problem (see eg garey & johnson ref) which is known to be NP complete but this seems to have "slightly" less complexity because its simpler to compute a vector bitwise XOR than a binary sum (the sum can have more binary digits).

the problem also seems closely connected to bin fu's recent question [2]

[1] https://cstheory.stackexchange.com/questions/10341/building-0-1-vectors-out-of-xors

[2] Algorithmic Vector Problem

Let $v_0, v_1, \ldots, v_n \in \mathbb{Z}_2^m$. The problem is to determine whether the following system has a solution:

$$
\begin{pmatrix}
v_1 & \cdots & v_n
\end{pmatrix}
\begin{pmatrix}
x_1 \\
\vdots \\
x_n
\end{pmatrix}
=
v_0 \, (\text{mod } 2)
$$

This problem is known to be $\oplus L$-complete by [Damm90, BDHM92], thus inside $\text{NC}^2 \subseteq \text{P}$.

[Damm90] Carsten Damm: Problems Complete for $\oplus L$. Inf. Process. Lett. 36(5): 247-250 (1990)
[BDHM92] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)


Problem conditions to use Laplacian solvers I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense.
Suppose that we want to solve Ax=b, where matrix A is not a Laplacian matrix. Under what condition on A and b, we can solve Ax=b using Laplacian solvers?
P.S. Introducing a good reference will be helpful too.

It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition of the proof (which was originally by Gremban) can be found in Appendix A of the paper by Kelner, Orecchia, Sidford and Zhu (arXiv:1301.6628).
A recent result by Kyng and Zhang (arXiv:1705.02944) suggests that current Laplacian solvers are probably restricted to this class.


What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)? I am planning to join a CS Ph.D. program in 6 months. My topics of research will be in the area of Reinforcement Learning and Game Theory. Even though I have a good grasp of these two topics’ applications and empirical side, I struggle with the theory a lot when reading papers. For example, It is taking me a lot of time to understand the regret analysis of advanced Bandits. I have taken most of the essential math courses during my undergrad, including Differential + Integral + Multivariate calculus, Linnear Algebra, Probability, Stat, etc. But I feel most of those courses did not go deep enough. So I want to revisit some of my undergrad math and would also like to learn additional topics. Given my area of Ph.D., I would like to know the essential math topics I should study in the next six months to have a good grasp on the theoretical side and do well in graduate-level courses consistent with such a Ph.D.

Know linear algebra well, say, at the level of Peter Lax' book (start with the first 9 chapters). Also, some basic real analysis and probability theory should be a good place to start.


Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent? Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent.  Since finding a perfect matching in a non-bipartite graph is in NP, there exists some reduction from non-bipartite graphs to the permanent, but it may involve a nasty polynomial blowup by using Cook's reduction to SAT and then Valiant's theorem to reduce to the permanent.

An efficient and natural reduction $f$ from a non-bipartite graph $G$ to a matrix $A = f(G)$ where $\operatorname{perm}(A) = \Phi(G)$ would be useful for an actual implementation to count perfect matchings by using existing, heavily-optimized libraries that compute the permanent.

Updated: I added a bounty for an answer including an efficiently-computable function to take an arbitrary graph $G$ to a bipartite graph $H$ with the same number of perfect matchings and no more than $O(n^2)$ vertices.

I would say that a "simple" reduction to bipartite matching is highly unlikely. Firstly, it would give an algorithm for finding a perfect matching in a general graph using the Hungarian method. Hence, the reduction should contain all the complexity of the Edmond's blossom algorithm.
Secondly, it will give a compact LP for perfect matching polytope and hence the reduction should not be symmetric (which are ruled out by a result of Yannakakis) and inherently very complicated.


Number of connected components of a random nearest neighbor graph? Let us sample some big number N points randomly uniformly on $[0,1]^d$.
Consider  1-nearest neighbor graph based on such data cloud. (Let us look on it as UNdirected graph).

Question What would the number of connected components depending on d ?
(As a percent of "N" - number of points.)

Simulation below suggest 31% for d=2,   20% for d=20, etc:

Percent Dimension:
31 2
28 5
25 10
20 20
15 50
13 100
10 1000

See code below. (One can run it on colab.research.google.com without installing anything on your comp).

If someone can comment on more general questions here:
https://mathoverflow.net/q/362721/10446
that would be greatly appreciated.

!pip install python-igraph
!pip install cairocffi
import igraph

import time
from sklearn.neighbors import NearestNeighbors
import numpy as np

t0 = time.time()

dim = 20
n_sample = 10**4

for i in range(10): # repeat simulation 10 times to get more stat
  X = np.random.rand(n_sample, dim)
  nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree', ).fit(X)
  distances, indices = nbrs.kneighbors(X)
  g = igraph.Graph( directed = True )
  g.add_vertices(range(n_sample))
  g.add_edges(indices )
  g2 = g.as_undirected(mode = 'collapse')
  r = g2.clusters()
  print(len(r),len(r)/n_sample*100 , time.time() - t0)

For $n$ uniformly random points in a unit square the number of components is

$$\frac{3\pi}{8\pi+3\sqrt{3}}n+o(n)$$

See Theorem 2 of D. Eppstein, M. S. Paterson, and F. F. Yao (1997), "On nearest-neighbor graphs", Disc. Comput. Geom. 17: 263–282, https://www.ics.uci.edu/~eppstein/pubs/EppPatYao-DCG-97.pdf

For points in any fixed higher dimension it is $\Theta(n)$; I don't know the exact constant of proportionality but the paper describes how to calculate it.


Are non-deterministic tree-walking automata stronger than deterministic ones? Update: It seems this problem has been studied and solved recently, see this wiki article: http://en.wikipedia.org/wiki/Tree_walking_automaton
And also this survey:
http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf

Suppose that instead of the usual set of words, {0,1}*, our words are not linear but rather given on some tree structure. To prevent our machines from "getting lost", define our words as the set of binary, embedded arborescences. (So every word is a tree, where every edge is directed away from a given a root that has degree two, every other non-leaf vertex has degree three, and every edge is labeled left or right such that any two edges starting from the same vertex have different labels.) A language is a set of such trees. (Note that there is no need to write zeros and ones on the vertices as they can be anyhow simulated by locally modifying the trees.) When a machine is "reading a tree", it starts from the root, it can sense if a given vertex is the root, a leaf or a degree three vertex and can decide if in the next step it wants to go to the parent of the vertex, or on the edge labeled left or right.

Is it true in this model that any language that can be recognized by a non-deterministic finite state automaton can also be recognized by a deterministic finite state automaton?

Note that when the tape is the usual linear tape, this is true, as any 2-NFA can be simulated with a 2-DFA (even with a DFA). I already asked a special instance of the problem here that was solved by Kristoffer. The motivation would be to solve this.

For tree automata, you have the following results:

Deterministic bottom-up tree automata have the same expressive power as non-deterministic bottom-up tree automata.
Deterministic top-down tree automata are weaker than non-deterministic top-down tree automata.

More details can be found in the Tree Automata book.

It seems that you are interested in top-down tree automata, so the answer to your question is no. You will of course have to check whether top-down tree automata are in fact what you are interested in.