texts:
Consider a set of $k$ continuous variables. Each variable $x_k$ is associated with a hidden distribution from which its value is sampled independently of other variables. I am given a set of observations of the sum of $k$ variables, i.e, $\sum_{i = 1}^{k} x_i$. The challenge is to learn the hidden distribution from the given observations.

This is the general variant of the problem I am trying to study. To simplify the problem, I can make the assumption that the hidden distribution is uniform and of the form $[0, u_k]$. Then, the challenge is to find $u_k$ for each variable $x_k$.

I am not very familiar with learning style algorithms but I am sure variants of this problem have been studied in great detail. Are there any references that I can look at to find out more about this problem?


texts:
It is known that generic k-SAT formulas may exhibit the presence of exponentially many solution clusters.

Question:
Is it true also for Monotone-2SAT formulas?

For the definition of cluster, see Kaveh's answer to the question SAT Solution Space - Definition of Cluster of Solutions.


texts: Numerically stable fast convolution algorithm?

texts:
Suppose you have two vectors of real numbers $\langle a_1, \dots, a_n \rangle, \langle b_1, \dots, b_n \rangle$, with $a_i, b_i \geq 0$, and wish to compute the convolution
$$
c_i = \sum_{j \leq i} a_j b_{i-j}
$$

There is an obvious algorithm to compute this in time $O(n^2)$. This obvious algorithm basically involves a sum of many positive summands, so there is no numerical cancellation. Hence the obvious algorithm is numerically stable.

The other obvious algorithm is to use a Fast Fourier transform to compute $\hat a, \hat b$, obtain $\hat c = \hat a \hat b$, and then use an inverse transform to obtain $c$. This algorithm is much faster, like $O(n \log n)$ time. Unfortunately, the Fourier transforms require adding many terms with different complex phases, so there is catastrophic cancellation. So this algorithm is numerically unstable.

Is there any algorithm which is both fast (near-linear time) and numerically stable?


texts: Which formalism is best suited for automated theorem proving in set theory?

texts:
Abbreviations - FOL is first-order logic; NBG is Von Neumann–Bernays–Gödel set theory; SEP is Stanford Encyclopedia of Philosophy; HOL is higher-order logic; ATP is automated theorem proving.

Context - An entire section of TPTP’s [1] axioms is devoted to set theories - for example NBG - for FOL theorem provers. Art Quaife wrote an entire book [2] on axiomatizing NBG in FOL.

It seems to me - These axioms all take membership as a sort of undefined concept, and then build subsets, power sets, union, difference, and so on.

In contrast, here is what SEP has to say on HOL (emphasis mine) -

  Second-order logic is an extension of first-order logic where, in addition to quantifiers such as “for every object (in the universe of
  discourse),” one has quantifiers such as “for every property of
  objects (in the universe of discourse).”   This augmentation of the
  language increases its expressive strength, without adding new
  non-logical symbols, such as new predicate symbols.   For classical
  extensional logic (as in this entry), properties can be identified
  with sets, so that second-order logic provides us with the
  quantifier “for every set of objects.”

It seems to me - that the concept of membership can only be represented in HOL. If that is true, how can FOL axiom schemas, taking membership as an undefined concept, prove theorems in set theory?

What I am trying to do - I need to do ATP in a theory which is FOL+sets. I was unsure whether to use an FOL prover (say, Prover9) or an HOL prover (say, HOL Light). At present, I’m using SNARK (FOL) with Quaife’s axiomatization of NBG, which is unable to prove my theorems (see below for example).

Question - Is this failure to be expected, since FOL cannot ‘understand’ membership, and hence I need an HOL prover? Or am I misunderstanding / doing something wrong?

[1] The TPTP Problem Library for Automated Theorem Proving, http://www.cs.miami.edu/~tptp/
[2] Automated Development of Fundamental Mathematical Theories, by Art Quaife, Kluwer Acadamic Publishers (1992)

Finally, an example -

Here is SNARK code representing three axioms, and a theorem, which SNARK is unable to prove. SNARK has also been given Quaife's axioms of NBG set theory. (Note member, the set membership function.) -

(assert  '(forall (x y z)
    (implies
      (and
        (part-of x y)
        (part-of y z)
      )
      (part-of x z)   ) ) :name '1point1point1)

(assert  '(forall (x y alpha t)
    (exists (z arb-part)
      (implies
        (and
          (and
            (member t alpha)
            (part-of t x)
          )
          (implies
            (part-of y x)
            (and
              (member z alpha)
              (and
                (part-of arb-part z)
                (part-of arb-part y)
        ) ) ) )
        (sum-of x alpha)   ) ) ) :name '1point1point2)

(assert  '(forall (alpha)
    (exists (arb-member sum)
      (implies
        (member arb-member alpha)
        (sum-of sum alpha)
) ) ) :name '1point1point3)

(prove  '(forall (x)
    (part-of x x)   ) :name '1point1point4)

EDIT -

Jake said - "set theories are often defined in first order logic". In fact, the question I was asking was - "Can set theories be defined in first order logic, in an automated theorem prover?". That's what I meant, when I said "is set theory equivalent to first order logic?" (which is an incorrect way of putting it, and for which I apologize).

It turns out that ZFC cannot be represented in an FOL theorem prover, since it is not finitely axiomatizable. NBG and one other set theories can, and several such axiomatizations exist in TPTP.

However, these axiomatizations seem to take the concept of membership as undefined, and build subsets, power sets, etc on that. The SEP paragraph I quoted seems to suggest that representing membership needs HOL. In such a case, it seems paradoxical to me that FOL provers are expected to prove theorems in set theory, knowing nothing of membership.

I'm sure this is not a real paradox - just something I don't understand. Hence the question. I hope that makes it clearer.


texts: Bounds on sum of squares of node degrees in undirected graphs

texts:
Admittedly, this is less of a research-y question (and admittedly, a little non-algorithmic trivial question), but I am hoping to get some meaningful answer.

Given an undirected graph $G = (V, E)$, with $n = |V|$ vertices and $m = |E|$ edges, what is a good upper bound on $\sum_{v \in V} \deg^2(v)$ in terms of $m$ and $n$.

Two obvious upper bounds are $O(n^3)$ and $O(m^2)$, which are quite weak for extremely sparse and extremely dense graphs respectively. Is there any reference to find a non-trivial (asymptotic) bound? For example, can we bound it as $O(m^\alpha n^\beta)$ for some $\alpha < 2$ and $\beta < 3$?


texts: How big is the variance of the treewidth of a random graph in G(n,p)?

texts:
I am trying to find how close $tw(G)$ and $E[tw(G)]$ really are, when $G \in G(n,p=c/n)$
and $c>1$ is a constant not depending on n (so $E[tw(G)] = \Theta(n)$). My estimate is that $tw(G) \leq E[tw(G)] + o(n)$ w.h.p, but i haven't been able to prove it.


texts: The time hierarchy theorem implies TIME($n$) is strictly contained in TIME($n\log^{1+ε}n$) for all ε>0. Is the relationship between TIME($n$) and TIME($nlogn$) known?


texts: When does (or should) Theoretical CS care about intuitionistic proofs?

texts:
From what I understand (which is very little, so please correct me where I err!), theory of programming languages is often concerned with "intuitionistic" proofs. In my own interpretation, the approach requires us to take seriously the consequences of computation on logic and provability. A proof cannot exist unless there exists an algorithm constructing the consequences from the hypotheses. We might reject as an axiom the principle of the excluded middle, for instance, because it exhibits some object, which is either $X$ or $\lnot X$, nonconstructively.

The above philosophy might lead us to prefer intuitionistically valid proofs over ones that are not. However, I have not seen any concern about actually using intuitionistic logic in papers in other areas of theoretical CS. We seem happy to prove our results using classical logic. For example, one might imagine using the principle of the excluded middle to prove that an algorithm is correct. In other words, we care about and take seriously a computationally-limited universe in our results, but not necessarily in our proofs of these results.

1. Are researchers in theoretical CS ever concerned about writing intuitionistically valid proofs? I could easily imagine a subfield of theoretical computer science that seeks to understand when TCS results, especially algorithmic ones, hold in intuitionistic logic (or more interestingly, when they don't). But I have not yet come across any.

2. Is there any philosophical argument that they should? It seems like one could claim that computer science results ought to be proven intuitionistically when possible, and we ought to know which results require e.g. PEM. Has anyone tried to make such an argument? Or perhaps there is a consensus that this question is just not very important?

3. As a side question, I am curious to know examples of cases where this actually matters: Are there important TCS results known to hold in classical logic but not in intuitionistic logic? Or suspected not to hold in intuitionistic logic.

Apologies for the softness of the question! It may require rewording or reinterpretation after hearing from the experts.


texts: Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

texts:
We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC.
My question is, can we do better for planar graphs? It is easy to identify lots of "tight" graphs: a graph has $(2k-1)$ vertices and its minimum Vertex Cover has size $k$.  The only known bound is $1.33k$ by Chen et al. [2007 SIAM J. COMPUT.]


texts:
Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* \subseteq \mathcal{S}$ such that $|\mathcal{S}^*| = K$ and such that each element of $U$ is contained by exactly one subset from $\mathcal{S}^*$.

What is parameterized complexity of the $\mathrm{ExactCover}$ problem for the parameter $K$ (the number of sets used in coverage)? It is known that  $\mathrm{SetCover}$ is $\mathrm{W}[2]$-complete, but is there anything known about $\mathrm{ExactCover}$ for $K$?


texts: Early history of certain results on space-time tradeoffs?

texts:
I'm interested in the early history of published results on general-purpose space-time tradeoffs.  In particular, I want to know who first described the following type of algorithm for evaluating a computation having an arbitrary dataflow graph with in-degree O(1) using space proportional to the depth (not width) of the dataflow graph (plus the size of the input) by doing a straightforward depth-first evaluation of the graph.  In more detail:

Let the dataflow graph be G=(V,E) where V is the set of computational vertices (O(1)-size data values) and E is is the set of edges (v_p, v_s), such that the value of successor vertex v_s \in V depends immediately on the value of predecessor vertex v_p \in V.  Let v_f be the vertex with no successors representing the final result of the computation.  Let I be a canonically ordered set of input vertices (with no predecessors), for i \in I its value x(i) is given.  For other vertices v \in S, their values are defined by x(v) = F_v(x(P(v))) where P(v) is a canonically ordered list of v's predecessors, x(P(v)) is the corresponding list of their values, and F_v is the vertex's function that determines its value as a function of the list of values of its predecessors.  Assume that the length of P(v) is O(1) for all dataflow graphs in some given class of interest (e.g., Boolean circuits with 1- and 2-input gates).

Given this setup, the algorithm in question is fairly obvious & trivial:

def eval(v):     (v can be any vertex in the graph)
   let P := P(v), the list of v's predecessors  (has O(1) elements by assumption)
   let val[] := uninitialized array of |P| data values
   for each predecessor p[i] in P (i.e. for i from 1 to |P|):
      if p[i] is in I then
         val[i] = x(p)      (look up a given input)
      else
         val[i] = eval(p[i])   (recursive call)
   return F_v(val[])        (apply vertex's function to list of predecessor values)

This takes O(d) levels of recursion, where d is the depth of the dataflow graph, and the stack space at each level is constant due to the assumptions that the in-degree of the dataflow graph is constant, and that the size of the data values is constant.  (For simplicity here, I'm treating the size of the vertex references as constant as well, even though they are really logarithmic in |V|.)  Thus, total space usage is O(d + |I|).  The maximum width of the dataflow graph can be exponentially larger than this, so in the best case this technique can provide a pretty extreme space savings, in comparison to, say, a greedy forwards evaluation of the graph (which might be to, at each step, evaluate all vertices that directly depend only on vertices whose values are already known, and discard all vertices that are no longer needed because all of their immediate successors have already been computed).

Anyway, it's a fairly obvious technique, at least in retrospect, and it's certainly long-known, but I was wondering just how back the literature on it goes.  Anyone know the early history of results of this sort (whether described in these terms, or other analogous ones), and what would be a good reference for digging into this subject?

Thanks very much,
-Mike Frank


texts: Optimal boolean function encoding with bounded error

texts:
Let $F = \{f:\{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions on $n$ bits. Any such function can be written as a polynomial

$f(x) = a_0 + \sum_i^n a_i x_i + \sum_{i,j}^n a_{i,j} x_i x_j + \cdots $,

where addition and multiplication is modulo 2. The values of these coefficients constitute a perfect encoding of the function in $2^n$ bits.

Now suppose that we wish to encode any function $f \in F$ into $m < 2^n$ bits. One example, $f \mapsto f_l$, is to keep only first $l$ orders of the polynomial expansion, setting all higher terms to zero.

We want to minimize the worst-case error probability $\epsilon = \max_{f \in F} \frac{1}{ 2^n} \sum_{x\in \{0,1\}^n} |f(x)-f_l(x)|$.

Is truncating the polynomial expansion the optimal way to approximate the functions in order to minimize the error or is there a better way?


texts: $NotTooManyP^{cc}$ class in communication complexity

texts:
Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication.

Class $NP^{cc}$ is class of languages admitting nondeterministic communication protocol with polylog size witness.

Class  $FewP^{cc}$  is class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polylog correct witnesses.

It was proven that $FewP^{cc} = P^{cc}$ [1]. My question is about what happens if we allow not too many correct witnesses instead of few.

Let class $NotTooManyP^{cc}$ be class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polynomial correct witnesses. Is this class different from $P^{cc}$? If yes, how much weaker is this class then $NP^{cc}$?


texts: Efficient recognition of sequences sortable by transpositions?

texts:
While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in restricted sorting problem:

If we restrict sorting algorithms to use transpositions (swapping integers in two non-adjacent positions) and restrict the number of transpositions then some sequences are sortable and others are not.

Note that sequence $A$ may contain some repeated integers

Formally, the problem is:

Input: a sequence $A=[a_1, a_2, ..., a_{2N}]$ of $2N$ positive (possibly repeated) integers.

Question: Is it possible to sort sequence $A$ using $N$ transpositions of non-adjacent positions?

  Is there a polynomial-time algorithm to solve this problem? Or Is it NP-complete?

This was post on MathOverflow.

P.S. This problem has a nice geometric interpretation: It is equivalent to deciding the existence of a path of length at most N between two points on a special 2N-Permutahedron.

Special permutahedron means that two nodes are connected by an edge if and only if the corresponding permutations are separated by one non-adjacent transposition.


texts:
I am unable to understand the definition of locally monotone Boolean function which is defined in Gotsman and Linial, "Spectral Properties of Threshold Functions", 1994, p. 40:

  A function $f$ is called locally monotone if it is increasing or decreasing in each variable.

Can somebody explain the definition with two examples (a function which is locally monotone and a function which is not)?


texts: Can decoying provide security against traffic analysis?

texts:
Eve is an intelligence agency with the capability to scan all cleartext communications and do traffic analysis against encrypted communications.

There are n Alices, who each want to communicate secretly with some of the other Alices. So, they want the content of their communication to be secret, and the fact that they are actively trying to communicate secretly to be secret.

There are also N>>n Bobs, who disagree with mass surveillance but don't want to do anything  which would give them any legal liability, such as transmitting illegal material (IE, they don't want to run TOR nodes).

So the Bobs decide to help by sending junk communications to other Bobs, which are indistinguishable from encrypted data. An individual Bob, if challenged, can show that his transmissions are junk, thus avoiding legal liability (NB -  I Am Not A Lawyer). For the purpose of the exercise Eve in not allowed to challenge 'many' Bobs.

Eve wins if she can distinguish the Alices from the Bobs, or at least, as many Alices as possible. In particular, Eve may start by knowing at least some of the Alices; we don't want the security of the other Alices to collapse if she does.

A dumb approach is as follows: For each period of time, each Bob (or masquerading Alice) chooses another Bob(Alice) to communicate with at random from a public list. The Bobs send junk, the Alices send their encrypted message. In this scheme, the Alices are indistinguishable from the Bobs, but the Alices only obtain 1/N of the bandwidth of an individual communication, which is very low since N is large, and have very high latency, since they have to wait many time periods before they happen to communicate with who they want.

Is it possible to do better?


texts: Realizability theory: difference in power between Lambda calculus and Turing Machines

texts:
I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering).
Andrej Bauer wrote, here, that some functions are realizable through a Turing machine, but not through lambda-calculus. A key step of his reasoning is:

  However, if we use the lambda
  calculus, then [the program] c is supposed to
  compute a numeral representing a
  Turing machine out of a lambda term
  representing a function f. This cannot
  be done (I can explain why, if you ask
  it as a separate question).

I would like to see an explanation/informal proof.

I don't see how to apply Rice's theorem here; it would apply to the problem "are this turing machine T and this lambda-term L equivalent?", because applying this predicate to equivalent terms gives the same result. However, the required function might compute different, but equivalent, TMs for different, but equivalent, lambda-terms.

Moreover, if the problem is with introspection of a lambda-term, I think that passing a Gödel encoding of a lambda-term would be also acceptable, wouldn't it?

On the one hand, given that his example involves computing, in the lambda calculus, the number of steps needed by a Turing Machine to complete a given task, I'm not very surprised.

But since here lambda-calculus can't solve a Turing-machine-related problem, I wonder whether one can define a similar problem for lambda-calculus and prove it unsolvable for Turing machines, or there is actually a difference in power in favor of Turing Machines (which would surprise me).


texts: Stackelberg solution to $n$-player Hotelling's game on a segment

texts:
Suppose that several agents need to place points (one per
agent) on the interval $[0,1]$. An agent's goal is to maximize the
volume of the Voronoi cell that contains his point. When $n$ agents must
place their points sequentially, is an optimal strategy known?

From what I was able to glean from the literature so far, it appears I am asking for the Stackelberg solution to an $n$-player Hotelling's game on a segment.


texts: How powerful are weak complexity classes with powerful oracles?

texts:
I am interested in complexity classes of the form $A^{B}$, where $A$ and $B$ are complexity classes such that $A \subsetneq \mathsf{P}$ and $\mathsf{NP} \subsetneq B$ are (believed to be) true.

First, is this a well-defined question? Are there any known results about the structure of such classes?

Second, is there an explicit problem in one of $\mathsf{NC}^{\mathsf{NP}}$, $\mathsf{NL}^{\mathsf{NP}}$, $\mathsf{FNC}^{\# \mathsf{P} }$, or $\mathsf{FNL}^{\# \mathsf{P}}$ and which is not in $\mathsf{P}$ under some assumption? After some research, I have not been able to find such a problem.


texts: Efficient algorithm for finding segregators in a directed acyclic graph

texts:
Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ancestors in $G\setminus S$. By "ancestor of a vertex $v$ in $G\setminus S$", I mean any vertex $u$ for which there is a path from $u$ to $v$ that contained in $G\setminus S$.

I am curious as to whether there is an algorithm which, given a graph $G$ and a value of $\alpha$, returns the minimum value of $\beta$ such that a $(\alpha,\beta)$-segregator exists for $G$. Is the decision problem of whether a given $(\alpha,\beta)$-segregator exists in a graph $G$ known to be NP-complete? Are there at least good approximation algorithms to the problem of finding whether a graph has "good" segregators?


texts: Living in Minicrypt, but sampling hard instances without the solution

texts:
In Impagliazzo's worlds, Minicrypt is the one, where one way functions exist.
In other words, we can sample hard-on-average instances of NP complete problems.
Question:
Is living in Minicrypt, where we can efficiently sample hard problems along with their solutions, equivalent to a Minicrypt, where we can efficiently sample hard problems without knowing their solution?


texts:
I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a distinct key. We are looking for the value of each key (that is, $v(q _i)$. Noticing that, a set of keys $Q' \subset Q$ may have the same corresponding value [that is, for each $q _i, q _j \in Q' \subset Q, v(q _i) = v (q _j)$].

What is the minimum time complexity to search for the values of all keys in $Q$?

Can it be less then searching individually and sequentially for each $q \in Q$?

N.B: I noticed most research in this field considered sequential files. But what would the answer be if the files was indexed using hash table or B+-tree ?

Example: the database D can be a Domain Name Server .. the queries may be any number of url's ? url's are the keys and the value are the IP addresses .. Some URL's may have the same value ... for instance, google.com and goolgle.com returns the same IP ... [hypothetically]


texts: Concentration Bounds for functions of matrices

texts:
This is a question about properties of large directed graphs which are preserved when we randomly sample edges.

Imagine I have an infinite sequence of positively weighted directed graphs.  The graphs are represented by adjacency matrices

$$M_1,M_2,...,M_n,...$$
where each $M_n \in \mathbb{R}^{n \times n}$. The sup-norm $\|M_n\|_{\infty} = \max_{i} \sum_{j=1}^n |M_{n}(i,j)|$ is uniformly bounded by some bound $B$  for all $n \in \mathbb{N}$. Furthermore, for any $\ell < n $ we have $M_{\ell}(i,j) = M_n(i,j)$ as long as $i,j \leq \ell$.

Many times we do not observe the full graph. Instead of observing $M_n$, we observe a random variable $\tilde{M_n}$
where
$$\tilde{M_n}(i,j) = \begin{cases} M_n(i,j) & \text{ with probability } \pi \\ 0   & \text{ with probability } 1-\pi.\end{cases}$$

Let $\tilde{y_n} = f(\tilde{M_n})$ be a real-valued function of the matrix $\tilde{M_n}$. Using a Chernoff bound, I know that if $f(\tilde{M_{n}}) = \sum_{i,j} a_{ij} \tilde{M_n(i,j)}$ is a linear function, then the value of $f(\tilde{M_{n}})$ is tightly concentrated around its expectation, with the probability of it being ``far away'' form $E[f(\tilde{M_n})]$ decreasing exponentially with $n$.

Is this true for non-linear properties? For example, if $f(\tilde{M_n})$ is a convex function, do we have a similar concentration bound?


texts: Rules between UIP with function extensionality and univalence

texts:
I am wondering if there are any interesting rules/judgemental equalities, denoted $A$, which satisfy the following properties:

$iMLTTfe+UA \implies \neg A$

$iMLTTfe+UIP \implies \neg A$, or more specifically Observational type theory.

$iMLTTfe+A$ is consistent and satisfies canonicity.

Where abrrevations mean:
iMLTTfe - intensional Martin-Löf type theory with function extensionality
UA - univalence axiom
UIP - uniqueness of identity proofs


texts: Extending EAL with recursion makes it incompatible with the abstract algorithm?

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

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

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


texts: Machine Learning: Calibrating SubGroups of Probability Predictions inside a Dataset which should sum to 100%

texts:
I am working on an interesting type of problem where I want to make predicitons for individual elements within subgroups- with the knowledge that the sum of the probabilities within a subgroup should sum to 1. The initial response will probably be to use a softmax system but this is subtley different (unless I have misunderstood something).
I will use an analogy to keep it straighforward:
Effectively in a flowerpot there are 10 flowers- only 1 of which is certainly is a daffodil and the other 9 are certainly not- some are quite similar to daffodils while others are more similar to flavorsome herbs or thorny bushes.
I have a dataset of 100,000 flowers (which are in 10,000 flagged lower pots/subgroups). I know characteristics for each of the flowers such as stem height, petal colour, odour pleasure, diameter etc. as well it being flagged whether or not it is indeed a delightful daffodil.
I am able to generate a logistic ML model quite easily which informs me of the probability that a certain flower is a daffodil based on the data from the other flowers. But I am unable to get it to work so the sums of probabilities within sub groups equal one- generally they are close but often as low as 65% or as high as 130%.
My interim solution is to carry out a post prediction clean, which determines the total probability assigned to the group and normalises predictions so they sum to one. Not awful but not great.
Am I a moron? Is this a softmax problem? Or something that a ML algo in existence can handle?
Thank you, a daffodil to those who help :)


texts: Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

texts:
A function $f: A^* \to A^*$ is regularity-preserving if, for each regular language $L$ of $A^*$, the language $f^{-1}(L)$ is regular. I think I have a proof, as a consequence of more general results, that the function defined by
$$
f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)
$$
is regularity-preserving. If this result is correct, could someone provide an elementary proof?


texts:
My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or Evoloop, are designed by painstaking, lengthy, meticulous design/engineering, which often involves composing units designed by previous mathematicians/hobbyists into more advanced and better behaved self-replicators. In other words, I believe that the current process of designing a self-replicator is following:

Take a self-replicator somebody designed before.
Get an idea of improving it, based on some theoretical research that somebody did, a gut feeling, an idea that's been floated around, a dream you had last night etc. The idea should improve the self-replicator with respect to some property that is commonly recognised to be worth improving (lower period, less fragility, sexual reproduction, etc.).
Try to make it work by working through multiple versions of the design, continuously refining the idea, and doing a ton of micro-optimisation. If you succeed go to step 1, and try to improve your new replicator. If you fail, go to step 2 and pick a different idea.

This method obviously works very well, as shown by the progress in the field, and is not very different from how in general progress in mathematics works. However, I've been thinking lately of a different approach to the problem, and I couldn't find any prior art trying this approach.

The process, let's call it "Self-Replicator Data-Mining" would be following:

Take the largest grid you can quickly evolve on your hardware. Size would most likely be limited by the amount of RAM you can devote to a GPU shader, which assuming to be 12 GB, gives a grid of about 100,000^2 squares.
Pick a "rich" set of rules, like Brian's Brain, to get a lot of chaos (you'll have to work on a torus).
Run it for about 8 months, periodically saving the state to a hard drive for backups. A back-of-envolope calculation shows that this would give you about billion steps of a simulation.
In meantime, design an algorithm which can recognise a self-replicator by looking at the grid after the nth iteration. The algorithm might be very slow, because it only needs to work once. It does sound like the biggest challenge -- and probably would involve some machine learning/ pattern recognition. In principle a parent can replicate to a slightly mutated child, which would make data mining of self-replicators even more difficult.
Publish your newly discoverd self-replicator(s) if you manage to find any. Or go to step 2 and pick a different set of rules, or wait for a graphics card with 120 GB of RAM, or run your simulation for 8 years, or abandon the method entirely in favour of something more fruitful.

Has anything like this ever been tried? Is it a path worth pursuing or are there any obvious flaws?


texts: Fast Finding Main Diagonal of Matrix Multiplication

texts: Suppose we have two matrices $A_{m\times n}$ and $B_{m\times m}$. Such that $B$ is a symmetric positive definite matrix. Is it possible to compute main diganoal of $A^TBA$ in $O(n\times m)$?


texts: What, in simple terms, are the restrictions imposed by Elementary Affine Logic?

texts:
The answer to my last question on the subject made several insightful points on how EAL could be used as the basis of a practical programming language, which, in turn, could be evaluated using the abstract part of Lamping's algorithm. I understand most of the practical remarks and they match my experimentation. I don't, though, understand, in a precise manner, the restrictions that I must follow in order to ensure my terms are EAL-typeable.

Those are the typing rules for EAL*, as presented here:

I have a vague understanding of what this is saying. I do understand functions can only be applied on terms without !s, and I understand there is a rule to introduce and remove those !s, but I don't fully grasp it. What, exactly, are the restrictions imposed by EAL? What means for a term to be "stratified"? What are those "boxes" about? I'd highly appreciate (non-PHD) resources to catch up with the understanding I'm missing here.


texts:
I have a problem on distributed graph, with the following model:
1. There is a Global Graph $G=(V,E)$
2. There are $k$ computers.
3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph, i.e. $V$, and subset of the edges, i.e. computer $i$ knows $V_i \subseteq V$.
4. Each computer observes different subset of edges, i.e., for all $i,j$ : $V_i \cap V_j = \emptyset$.

I searched for papers which handle the same model, but I didn't find anything. Do you know if such model is being studied?


texts: A simple approximation algorithm for the TSP

texts:
Consider the following extremely simple approximation algorithm for the TSP.

Input: A complete weighted graph $G=(V,E).$

Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$
While there are vertices in V that are not in H:

Take one of them, say $v.$ Let $H=(v_1,v_2,...,v_k,v_1),$ where $k$ is the number of distinct vertices currently contained in $H.$
Take as new $H$ the shortest of all the Hamiltonian cycles $(v,v_1,v_2,\ldots,v_k,v),$ $(v_1,v,v_2,\ldots,v_k,v_1),$ $(v_1,v_2,v,\ldots,v_k,v_1),$ $\dots,$ $(v_1,v_2,\ldots,v,v_k,v_1),$ i.e., insert $v$ before every vertex in $H$ and find the shortest Hamiltonian cycle among all those.

Output: $H.$

Obviously, this algorithm has runtime $O(n^2).$

Can anyone give me a lower (or upper) bound on the approximation ratio of this algorithm? Or a worst-case example, for that matter?


texts: Is there a formalization of normalization of impredicative system F?

texts:
In particular Agda seems not strong enough to prove that.

Is the predicative Calculus of Inductive Constructions universes (Coq without Prop) sufficient?

How about with the impredicative Prop?


texts: Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?

texts:
This is a follow up to my previous question:

Best known deterministic time complexity lower bound for a natural problem in NP

I find it bewildering that we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem that people care about and try to design better algorithms for. Our Exponential Time Hypothesis conjecture states that SAT cannot be solved in subexponential deterministic time, yet we cannot even prove SAT (or any other interesting NP problem) requires quadratic time!

I know interesting is somewhat subjective and vague. I don't have a definition. But let me try to describe what I consider to be an interesting problem:
I am talking about problems which more than a few people find interesting. I am not talking about isolated problems mainly designed to answer some theoretical question. If people are not trying to find faster algorithms for a problem then it is an indication that the problem is not that interesting.
If you want concrete examples of interesting problems consider the problems in Karp's 1972 paper or in Garey and Johnson 1979 (most of them).

  Is there any explanation for why we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem?


texts: Cannot understand the problem of Bitonic Euclidean Traveling-Salesman

texts:
I am referring to the problem in Introduction to Algorithms. I kind of fail to understand the problem.

From what I see, I need to sort the x-coordinates of the given set of points and then form a optimal path from the smallest x coordinate to the largest x coordinate.

For eg. (x1,y1) (x2,y2) ...(xn,yn) are sorted points. Isnt the optimal path simply x1,x2,x3,...xn-1,xn,xn-1,...,x3,x2,x1.

What am I missing here? How does dynamic programming come into picture here?


texts: Information on k-SAT (Introduction, Bounds, Methods, etc.)

texts:
I'd like to know where I can turn for a good, gentle introduction to k-SAT (this may be for mathematicians that may not have a good computer science background).  I'd also like to know papers that maybe survey or explain current methods used to solve k-SAT.  Finally, I'm interested in the best known methods for solving k-SAT.  I'd like to get an idea of the best average case and best worst case behavior.

In short, I'm looking for papers that will help someone in mathematics (not computer science) become much more of an expert in k-SAT.


texts: How fast can we group clauses with few variables in common in k-SAT?

texts:
Given a k-SAT problem with $C$ clauses and $V$ variables, we can group the clauses together into groups of $g$ clauses with few exceptions, where the exceptions contain $g-1$ or fewer clauses.  If we add the constraint that each group should contain at most $n$ variables in common, and no clause is in more than one group, how quickly can we find a "grouping" that satisfies these conditions?

I'm wondering if this problem has been considered before, and in what circumstances this problem needs to be resolved.  My motivation for considering this question stems from another attempt at making use of the clause counting that I describe in this question.


texts: Complexity of the mandelbrot set on rationals

texts:
(Also posted on mathoverflow) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals.

A point $c$ is contained within the Mandelbrot Set $M$ if the following procedure never halts:

$z = c$

$while (abs(z) <= 2)$

$\hspace{0.3in} z = z*z+c$

Normally we pick some $k$ (say, 50) and then if it doesn't halt after that many iterations we assume it is in the Mandelbrot set and stop looping. Is there a polynomial time algorithm for determining if a given $c$ does not break out of this loop after $k$ steps, in terms of the magnitude of $k$ and in terms of $n$ bits representing the numerator and $n$ bits representing the denominator of $a$ and $b$?

For reference, $abs(c) = \sqrt{a^2 + b^2}$ and $c*c = a^2 + 2abi +b^2i^2 = a^2 - b^2 + 2abi$ because $i^2 = -1$.


texts: Size of solutions in integer programming

texts: Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\log_2\|x\|_2$ where $x\in\mathbb Z^n$ is unknown?


texts: What else (besides the usual) can be said about a Scott Information System if the constructed domain is required to be Hausdorff?

texts:
As per subject, if a Scott domain with $T_2$ topology is to be constructed from a Scott information system, then what besides the usual definitional requirements, e.g., https://en.wikipedia.org/wiki/Scott_information_system , does the information system have to satisfy?

Information systems are more completely discussed in (Scott's original paper) https://www.researchgate.net/publication/220897586_Domains_for_Denotational_Semantics (note: the original paper is followed by a three-page bibliography missing from this pdf) containing a section "Topological Considerations" starting on page 586, where "Hausdorff" is briefly mentioned on page 588 with respect to (what Scott calls) "total elements", $Tot_A$, assuming no unique top. But the domain itself, what Scott calls $\mid A\mid$, is still $T_0$ in general. And I'm asking for additional definitional requirements so that $\mid A\mid$, when contsructed from the corresponding information system, is "automatically" $T_2$.


texts: Can someone suggest a recent survey on product form Markov chains?

texts: I'm especially interested in their use in model checking applications.  I have Open, Closed and Mixed Networks of Queues with Different Classes of Customers by Baskett et al.  Any other suggestions for reading material?  Thanks.


texts: Constraint Satisfaction Problem: Choosing real numbers with certain characteristics

texts:
I have a set of n real numbers. I also have a set of functions,

f_1, f_2, ..., f_m.

Each of these functions takes a list of numbers as its argument. I also have a set of m ranges,

[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].

I want to repeatedly choose subsets {r_1, r_2, ..., r_k} of k elements such that

l_i <= f_i({r_1, r_2, ..., r_k}) <= u_i for 1 <= i <= m.

Note that the functions are smooth. Changing one element in {r_1, r_2, ..., r_k} will not change f_i({r_1, r_2, ..., r_k}) by much.

These are the m constraints that I need to satisfy.

Moreover I want to do this so that the set of subsets I choose is uniformly distributed over the set of all subsets of size k that satisfy these m constraints. Not only that, but I want to do this in an efficient manner. How quickly it runs will depend on the density of solutions within the space of all possible solutions (if this is 0.0, then the algorithm can run forever).

Note that n is large enough that I cannot brute-force the problem. That is, I cannot just iterate through all k-element subsets and find which ones satisfy the m constraints.

Is there a way to do this?

What sorts of techniques are commonly used for a CSP like this? Can someone point me in the direction of good books or articles that talk about problems like this (not just CSPs in general, but CSPs involving continuous, as opposed to discrete values)?

[Note that this question is a special case.]


texts: Problems with Unknown Single Exponential Time Agorithms

texts:
I'm looking for examples of problems for which it is easy to get algorithms running in time $2^{O(n\log n)}$, or $2^{O(n^c)}$ for some $c>1$ but for which it is not known whether there is an algorithm running in time $2^{O(n)}$.

I'm mostly interested on graph theoretic problems, but other nice examples would also be welcome.

For instance, it is trivial to develop an algorithm running in time
$O(n!) = 2^{O(n\log n)}$ for the Hamiltonian path problem. Just test all permutations. Using dynamic programming however, one can achieve time $2^{O(n)}$. Are there other natural connectivity problems, or variations of the Hamiltonian path problem for which no algorithm running in time $2^{O(n)}$
is known?


texts: On FFT and trigonometric matrix eigenvalues

texts:
Let $N=2^n$ for a natural number $n$ and $B$ be the $N\times N$ square matrix of $0$'s and $1$'s
$$
B=\begin{pmatrix}
 0     & 1 & 0 & \ldots & 0 \\
 1     & 0 & 1 & \ldots & 0 \\
 0     & 1 & \ddots & \ddots & \vdots \\
 \vdots    & \vdots & \ddots & 0 & 1 \\
 0     & 0  & \ldots & 1 & 1 \\
\end{pmatrix}.
$$
 Is there a way (FFT or another) to find the $N\times N$ diagonal matrix D, such that the eigenvalues of the product matrix $DB$ are
$$
 2\sin\left(\frac{k\pi}{2N}\right), \,\, k=1,2,\dots,N.
$$
 The solution for an odd $N$ is in my old question: https://math.stackexchange.com/questions/400664/eigenvalues-of-a-tridiagonal-trigonometric-matrix


texts: Padding Arguments for Probabilistic Classes

texts: Do padding arguments exist for probabilistic classes? For example, would $P=BPP\Rightarrow EXP=BPEXP$? What about for space bounded computation? Would constant space derandomization imply $L=RL$ or $L=BPL$?


texts: How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?

texts:
I am not a computer science theorist, but think this real world problem belongs here.

The problem

My company have several units accross the country.

We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.

That means: We'll allow a employee to left his unit if someone wants his place.

Example (ficticious) request data:

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

The above, plotted:

See how we have to choose between the red, blue or black options?

The real problem is a little more complex, because we have 27 units and 751 requests. Please take a look at the visualization

The goal

Having collected all the requests, how to satisfy most of them?

Theory(?) application

Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.

Each cycle must use $E$ only once (a worker cannot leave his unit twice), but can visit $V$ several times (a unit can have many workers wanting to leave).

The question

If this problem is expressed as

  "How to find the cycles which, together, involve the biggest number of
  non-shared edges in a directed graph"?

Will we satisfy most of the requesters?

That being true, there is an algorithm to find that optimal set of cycles?

Will this greddy approach solve the problem?

Find the biggest directed cycle on $G$;
Remove it's edges from $G$;
Repeat 1 until there is not a directed cycle on $G$;

Can you help me?

Do you know another way to describe the original problem (making most of requesters happy)?

Edit: changed department to unit, to better describe the problem.


texts: Why should we believe that $NEXP \not \subset P/poly$

texts: I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used is derandomization and they believe that $P=BPP$ and I know Nissan and Wigderson's generator which exist if $EXP \not \subset P/poly$($E \not \subset Size(2^{o(n))}$). On the other hand, I see some theorems like IP = PSPACE which thought to be false. Recently I read the IKW and there is a theorem states that $NEXP \in P/poly$ then there is a polynomial witness description for any language in $NEXP$. For me, it is likely to happen for example Succinct-HC is an $NEXP$-Complete language and it is likely to have a succinct witness. On the other hand, there are undecidable problems in P/poly that we don't know, maybe we could use them as an oracle to solve Succicnt-HC, They are some reasons in IKW's paper but I need more references that help me to understand why should we believe that $NEXP \not \subset P/poly$.


texts: Dependency of Algorithms, Data structures on Instruction sets ex: Classical vs Quantum computing

texts:
It seems to me that

All/any algorithm(s) evolve based on what's feasible on a machine. This is captured within its instruction set.
By Analogy data structures are closely associated with physical layout of memory hierarchy on a machine including addressing schemes

Is there a non-formal(with/without math) description of the above dependencies in the form of a set of programming experiments with different instruction sets, memory hierarchies and how they impact design of data structures and algorithms that follow?

Few links that I got :

a paper on "Data Structures in Classical and Quantum Computing"
Elements of computing systems: Building a modern computer from first principles

(PS: Not thinking of expanding the scope to distributed and/or parallel processing systems)


texts: Increasing Functions in Non-deterministic Time Hierarchy Theorems

texts:
I was going over the proofs of the non-deterministic time hierarchy theorem (the one in Arora-Barak and the one by Fortnow and Santhanam). They are available here:

http://theory.cs.princeton.edu/complexity/book.pdf : page 67
https://blog.computationalcomplexity.org/2011/04/new-proof-of-nondeterministic-time.html

It seems to me that we need $f$ and $g$ to be increasing functions, in addition to the usual assumptions that $f(n+1)=o(g(n))$ and time-constructibility.

In the Arora-Barak proof, we divide the natural numbers into disjoint intervals. I'm not sure how one can find, given a number $n$, which interval it lies in, without assuming that functions are increasing.
In the Fortnow-Santhanam proof, this is needed to ensure that $t_1(i+m+2)$ (which I believe may be a typo and should be in terms of $t_2$) can be computed in time $O(t_2(n))$.


texts:
With the advent of internet (and common sense) there is more and more demand for open-access research. Several researchers (including me) find it frustrating that published peer-reviewed research articles are behind paywalls. I am looking for journals and conferences (related to theoretical computer science, graph theory, combinatorics, combinatorial optimization) that make all accepted publications freely available to everyone.

Some such journals are Theory of Computing, The Electronic Journal of Combinatorics, Logical Methods in Computer Science

If you know more such journals (or) conferences, please mention them in your answers.

EDIT : As suggested by David Eppstein in his answer, I am adding one more constraint. Please write only those journals/conferences that do not charge authors exorbitant fees to publish.


texts: Hypersequents: proof term assigments or translations to hybrid logic

texts:
I've been looking at a modal logic with the axiom

$$
(\Diamond A \land \Diamond B) \to \Diamond((A \land \Diamond B) \vee (A \land B) \vee (A \land \Diamond B))
$$

Roughly, this says that the accessibility relation is linear.

It seems like you can give a proof theory for this language using hypersequents (see Andrzej Indrzejczak's Cut-Free Hypersequent Calculus for S4.3), and I was wondering if anyone has investigated giving proof term assignments to hypersequent calculi.

Alternatively, I'd be just as happy if someone had shown how to translate hypersequent calculi into hybrid logics.

Any pointers?


texts: Applications of fat shattering dimension in computational geometry

texts:
The fat shattering dimension generalizes the notion of VC-dimension to handle function classes where the range is $(0,1)$, instead of $\{0,1\}$. Fat shattering dimension plays the same role as VC-dimension in generalization bounds in machine learning.

While the concept (and related notions) is quite useful in machine learning, I've never seen it being used in "traditional" computational geometry, where VC-dimension (and the shatter dimension) play a significant role.

  Are there any places where the fat
  shatter dimension has been used in
  computational geometry ?


texts: What is the right theoretical model to design algorithms for current and upcoming high performance computers

texts:
This question is similar to a more general question for what is the right theoretical model of a computer to design algorithm and data structures in.
Here, I ask specifically about current high performance computers (like the ones listed as the Top 500) or even about upcoming supercomputers.

Given that these computers are typically working on huge data sets (it seems that some people use such machines mainly because they have enormous combined main memory) aspects of the I/O-model (introduced by Aggarwal and Vitter in 1988) and its parallel version, the PEM (Arge, Goodrich,  Nelson and Sitchinava in 2008) should be present.
On the other hand, there should be something about communication, in particular punishing ultra small packages to all other computing nodes.

As you might imagine, I am not afraid that I am running out of ideas when creating a new model, but I am a little worried that I might overlook previous attempts in doing so, in particular because I have the impression that the years 1980-1995 or so saw many such modeling attempts (like BSP or bridging models) that seem to not have been widely used.

What models should I take a closer look at?


texts: Finding minimum weight $k$ cliques in a complete graph

texts:
For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar towards each other.

I'm trying to find a subset of size $k$ nodes such that they look not so "similar" towards one another, $\textrm{i.e.}$ $k$ nodes $G_k = (V_k, E_k)$ s.t. $\sum_{(i,j) \in E_k} w_{ij}$ is maximized.

I'm not looking for an exact solution but I do want to know whether there is an approximation algorithm that is easy to implement and can still have some kind of performance guarantee.


texts:
I'm interested in a problem akin to combinatorial circuits, but in terms of complexity. Apologies for missing the correct terminology, I'll appreciate any corrections.

Given $n$ inputs numbered $1 ... n$, there are $n!$ ordered permutations. I wish to reason about the time complexity of programs which generate a single such combination.

Clearly, the simplest program will be f(x): x, with $O(1)$. If I write down all programs for a given problem size $n$ in the most efficient way, what will be the lower bound time complexity for the one with most operations?

A trivial solution is a switch statement of length $n$, with $O(n)$, but this is clearly not the most efficient way. Is there theory to answer this question?


texts: Determine whether a categorical grammar is minimal concerning lexical entries

texts:
In order to compare the descriptional complexity of context-free and (combinatoric) categorical I need a way to check if a categorical grammar of a formal language is minimal concerning lexical entries.

Any ideas on how to do that? Any work on this, that you might know of?

Thanks!


texts:
Have there been any studies to determine whether human intelligence can outperform algorithms (i.e. test whether the No Free Lunch Theorem applies to human intelligence)?

Along the same lines, has anyone developed a technical method to take advantage of any unique, supra-computational properties of human intelligence?


texts: Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time

texts:
Does there exist a stable comparison sort using $O(1)$ auxiliary memory and achieving $O(n \log n)$ average run time?

Context: There are comparison sorts with any two of those three desirable characteristics (see this list). Is there a reason why the three cannot be achieved simultaneously? [Edit: I added the algorithm from the accepted answer to the list on Wikipedia, obviously it wasn't there when I asked the question.]


texts: Natural NP-complete problems with high density?

texts:
(This question is related to a previous one, see the discussion in "Almost easy" NP-complete problems, but it may also be of independent interest, so I post it as a separate question.)

Let us say that a language $L\subseteq \{0,1\}^*$ has high density, if it contains a positive constant fraction of all $n$-bit strings. That is, there is a constant $c>0$, such that $$|L\cap \{0,1\}^n|\geq c2^n$$ holds for all $n$.

It is not hard to construct artificial examples of NP-complete problems with high density. For example, let $L$ be any NP-complete language. For a binary string $z$, let $w(z)$ denote the weight of $z$, which is the number of 1-bits in $z$. Now define
$$ L'=\{xx\,|\,x\in L\}\cup \{y\,|\, w(y)\:\mbox{is odd}\}. $$
It is easy to see that $L'$ has high density, and it still remains NP-complete.

The above example, however, is quite artificial, it is constructed for the sole reason of exhibiting this property. I expected that one could easily find natural NP-complete problems with high density, and I was surprised that this turned out harder than I thought. So, the question is:

  What are some examples of natural NP-complete problems with high density?

Edit:

From the discussion in the comments I realized that a better question would be this:

  What are some examples of natural NP-complete problems with the property that both the yes-instances and the no-instances have high density?


texts: Is there a relationship between the probabilistic interepretation of Sherali-Adams SDP hierarchy and the Lasserre SDP hierarchy?

texts:
Firstly note this paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf where a Lasserre SDP is being setup for the independent set probblem at the bottom of page 4 where the author says says, "It can be shown that for any set S with |S| ≤ t, the vectors $U_{S'}$, S' ⊆ S induce a probability distribution over valid independent sets of the subgraph induced by S."

I guess that the author is claiming the following identity,for all subsets $S$ of size at most $t$, $\sum_{S' \subseteq S, S' \text{independent in the subgraph induced by }S} ||U_S'||_2^2 = 1$ Can someone clarify/prove that this above statement follows from whatever has been defined about these vectors $U_{S'}$ on page 4? (Is the author claiming that this equality above is a consequence of how he has defined the feasible set of $U_{S'}$ vectors in the top box of page $5$?)

I guess these vectors $U_{S'}$ can be interpreted as what I would call "Lasserre vectors" (is there any standard term for these?) (By ``Lassere vectors" I mean the rows of the matrix $V$ which factorizes the degree $d$ pseudo-moment matrix $M$ as $M = VV^T$) So is the author claiming that there is such a probabilistic interpretation for any Lassere vector?

For the Sherali-Adams SDP hierarchy let me follow the definition of $SA_r$ as in the box at the top of page $5$ here, http://dsteurer.org/paper/cspgaps.pdf. (...I haven't seen any book or other older paper define this notion! People seem to typically refer to a certain LP hierarchy as the Sherali-Adams hierarchy!...)
Is there any relationship between this local integral distribution $\mu_S$ defined in this paper and the probability distribution alluded to in the first paper? Are the SDP vectors $v_{i,a}$ used in the $SA_R$ definition to be also thought of as or are even remotely related to Lasserre vectors?


texts: Consequences/existence of problems without any "optimal" algorithm

texts:
Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off this, let $S'_P$ denote the set of "optimal" algorithms that solve $P$, in other words:

$$S'_P :=  \{A_i ∈ S_P | \nexists A_j ∈ S_P  \textrm{ s.t.} \lim_{n \to \infty} \frac{O(A_i)}{O(A_j)} = 0 \}$$

Is there an example of a problem when $S_P$ is non-empty, but $S'_P = \emptyset$? Also, are there any significant implications concerning the existence/non-existence of such a problem?


texts: What subjects, topics does a computer science graduate need to learn to apply available machine learning frameworks, esp. SVMs

texts:
I want to teach myself enough machine learning so that I can, to begin with, understand enough to put to use available open source ML frameworks that will allow me to do things like:

Go through the HTML source of pages
from a certain site and "understand"
which sections form the content,
which the advertisements and which
form the metadata ( neither the
content, nor the ads - for e.g. -
TOC, author bio etc )
Go through the HTML source of pages
from disparate sites and "classify"
whether the site belongs to a
predefined category or not ( list of
categories will be supplied
beforehand ) based on the page content derived from 1
... similar classification tasks on
text and pages.

As you can see, my immediate requirements are to do with classification on disparate data sources and large amounts of data.

As far as my limited understanding goes, taking the neural net approach will take a lot of training and maintenance than putting SVMs to use?

I understand that SVMs are well suited to ( binary ) classification tasks like mine, and open source frameworks like libSVM are fairly mature?

Taking forward the question assuming SVMs to be a better answer to classification of the likes of mine, how do I understand things like:

What $R^n$ stands for
or hyperplanes
or how to transform a space so that
it can be broken into two parts etc?2.

  In that case, what subjects and topics
  does a computer science graduate need
  to learn right now, so that the above
  requirements can be solved, putting
  these frameworks to use? Especially those related to SVMs.

I am willing to learn and put in as much effort as I possibly can.

Recommendations from you on learning specific portions of statistics and probability theory is nothing unexpected from my side, so say that if required!

I will modify this question if needed, depending on all your suggestions and feedback.

Cross-posted on SO:

https://stackoverflow.com/questions/3764444/what-subjects-topics-does-a-computer-science-graduate-need-to-learn-to-apply-ava


texts: What are theoretically sound programming languages for graph problems?

texts: There are numerous graph theoretic tools/packages. Each with its pros and cons. What should be the semantics/syntax of a programming language meant to solve graph theoretic problems?


texts:
I would like to know if somebody has studied the following very simple fragment of the modal mu-calculus:

$$F::= X \;| \; p \; | \; F \wedge G \; | \; [a]F \; | \; \nu X.F$$

where p ranges over propositional letters. In other words this is the mu-calculus where no disjunction, diamond or least fixed point operators are ever used.

This is a almost trivial fragment, of course. But i'm interested in the following two questions:

A) Is it true that if F is satisfiable, then it is satifiable in a finite model such that every vertex $X$ in the labeled Kripke structure has at most one $a$-labeled children?
i.e., such that $X\xrightarrow{a}Y$ and $X\xrightarrow{a}Z$ then $Y=Z$?

B) What is the complexity of the satisfiablity problem for this logic?

C) What is the complexity of model checking?


texts: How good of an approximate 2-coloring can you get of the halved cube graph?

texts: We say that a 2-coloring $col : V_G \rightarrow \{0, 1\}$ of a graph $G$ is $\epsilon$-approximate if $Pr_{(w, v) \in E_G}(col(w) \neq col(v)) \geq \epsilon$. For every $n$, what is the maximum $\epsilon_n$ for which the halved cube graph has an $\epsilon_n$-approximate coloring $col_n$? The halved cube graph is the graph you get by using the same construction as the Boolean cube but flipping 2 bits instead of 1 to get from vertex to vertex, and then throwing out one of the two identical connected components. What is the family of colorings which witnesses this? Is there a natural coloring which comes close to the optimum, ideally approaching it asymptotically?


texts: Can coNLogTime verification be used instead of PTime verification when characterising NP?

texts:
I recently read a paper that presented a proof calculus where the verification of whether a given proof is valid was NL-complete. The authors apparently decided that the checking procedure was not local enough, and defined a modified notion of proof where (practically speaking) the execution trace of the dynamic programming algorithm doing the NL-complete checking in polytime was part of the proof. That modified notion of proof could now obviously be verified by very local checks.

I was both negatively shocked and positively surprised by this:

The negative shock was that this gratuitous size increase of the witness string of an NP problem during a reduction doesn't seem to be penalised or even noticed for the common notions of reduction. I wondered whether there is any way to fix this, but I guess this is a difficult question. But if you know how to fix this, please let me know.
The positive surprise was that their trick seems to be applicable to arbitrary problems from NP to make the verification of the witness string locally checkable. The idea is to just declare the execution trace of the PTime verification algorithm to be a part of the witness string.

Is the observation correct that the extended witness string still satisfies the polynomial size bounds as required by the definition of NP? What is the correct notion to capture what is meant by "can be verified by very local checks"? I initially proposed ALogTime, but the comments by Kaveh and  Emil Jeřábek indicate that DLogTime-uniform AC0 would be more appropriate (and that coNLogTime is already sufficient).

Note that

  coNLogTime $\subset$ DLogTime-uniform AC0 $\subset$ ALogTime and
  ALogTime = DLogTime-uniform NC1 = $U_{E^*}$-uniform NC1 $\subset$ L-uniform NC1.

and that the abstract of The Boolean formula value problem is in ALOGTIME by Sam Buss says

  These results are optimal since the Boolean formula value problem is complete for alternating log time under deterministic log time reductions.


texts: Oracle that will provide any computable information about another oracle

texts:
Suppose I have an oracle X.  Then let Y be an oracle which will answer any computable question about X.  In other words, Y takes as input a Turing program which can in turn make calls to X.  Y then returns the output of that program (assuming the output is one bit, otherwise, or if the program doesn't halt, then the definition is open to interpretation).

Has this concept been studied?  Is there a name for such oracles?

This relates to communication complexity.  In that case X would be Alice's input, X' would be Bob's input, and Y and Y' would be sufficient to efficiently compute their strategies.  The Y and Y' oracles are a way to express the fact that in communication complexity one usually doesn't care how much time the parties spend on computation.


texts: Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

texts:
I've given an optimization problem for which I want to show that it is solvable in polynomial time.

Now, I have two questions:

Can this be done by formulating a mixed-integer linear program such that the coefficient matrix A has only values of -1, 0 or +1 and show that A is total unimodular? Because solving the relaxation of this problem with appropriate LP-techniques delivers an optimal solution in polynomial time.
What alternatives do I have to show that an optimization problem is solvable in polynomial time? I'm searching for an elegant proof for writing down this result.

EDIT: I reformulated my questions and hope my request becomes clearer.


texts: In homotopy type theory, is there a IsManifold predicate?

texts:
Any type $A: \mathcal{U}$ can be thought of as a homotopy type, or a sufficiently nice topological space up to homotopy equivalence. Now, manifolds are topological spaces with some extra structure.

Some questions in manifold theory are still interesting up to homotopy, for example 2-manifolds are isomorphic whenever they are homotopy equivalent, and it is suspected that 4d extended topological quantum field theories only carry homotopy information.

Other questions in manifold theory are exactly whether homotopy equivalence implies isomorphism under certain circumstances, for example the question of homotopy spheres.

So I'm wondering whether it's possible to define a predicate like $\text{IsManifold}: \mathcal{U} \to \mathcal{U}$, such that $\text{IsManifold}(A)$ is inhabited by possibilities of defining a manifold that is homotopy equivalent to $A$.

As an application, we can define any homotopy invariant of manifolds (like the genus of surfaces) on types satisfying this predicate.

Since in all generality, this is probably too much to ask for a start, so here is an easier version:

Surely it is feasible to define a type of simplicial sets $\text{sSet}$. Can we define a proposition $\text{IsManifold}': \text{sSet} \to \text{Bool}$ that decides whether the realisation of a given simplicial set is a manifold?


texts: Is there any connection between the diamond norm and the distance of the associated states?

texts:
In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such as the trace distance, fidelity, etc. The Jamiołkowski isomorphism provides a duality between quantum channels and quantum states.

This is interesting, to me at least, because the diamond norm is notoriously hard to calculate, and the Jamiołkowski isomorphism would seem to imply some correlation between distance measures of quantum channels and quantum states. So, my question is this: Is there any known relation between the distance in the diamond norm and the distance between the associated states (in some measure)?


texts: Decidability one relation, binary FOL over finite models

texts: Suppose $\sigma$ is a vocabulary consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence. Is it decidable whether there is a finite directed graph $G$, with all in- and out-degrees $0$ or $1$, such that $G\models \phi$ ?


texts: Dynamic Programming with two optimization goals

texts:
I am working on the problem of distributed database query planning. Existing work [1] uses dynamic programming to search the potential query plan space and find the one with minimal cost. However, I am interested in an additional value (e.g. security risk) of a query plan, and would like to minimize this value also.

My current idea is to first minimize the cost goal to a certain extent, and then minimize the second goal. More specifically, we can let the user specify a Delta value, and then the dynamic programming algorithm can find a set of near optimal candidates whose costs fall in [optimal cost, optimal cost + Delta]. Then, we can minimize the second goal in this set.

My question is, is there any algorithmic work that offers similar capabilities? Or is there any method to modify a dynamic programming algorithm so that it can consider two goals simultaneously? Other relevant information will also be appreciated. Thank you!

References:

[1] Kossmann, Donald, and Konrad Stocker. "Iterative dynamic programming: a new class of query optimization algorithms." ACM Transactions on Database Systems (TODS) 25.1 (2000): 43-82.


texts: Two matrices related by a permutation $B = P A P^T$ - complexity

texts:
What is computational complexity of the following problem:

given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that:
$$B = P A P^T.$$

If it helps, one can assume that $A$ and $B$ are hermitian (or even that $A$ and $B$ are real and symmetric).

Notes:

The problem stems from checking if two sets of vectors are related by an unitary rotation, see Sets of vectors related by a rotation - MathOverflow. In that context $A$ and $B$ are their Gramian matrices.

The problem is at least as hard as the graph isomorphism problem - take $A$ and $B$ as adjacency matrices.


texts: Additive welfare maximization under matroid constraints

texts:
In the welfare maximization problem, there is a set $[m]$ of items, and $n$ functions $w_i: 2^{[m]} \to \mathbb{Z}_+$. The goal is to partition the items into $n$ subsets $S_1,\ldots,S_n$ such that the sum $\sum_{i=1}^n w_i(S_i)$ is maximized.
In this paper, Jan Vondrák presents several constant-factor approximation algorithms for this problem, assuming that the functions $w_i$ are monotone submodular set functions. In general, the problem cannot be solved exactly unless P = NP.
I am interested in the special case in which the $w_i$ are additive set functions (a special case of submodular), and all sets $S_i$ should be independent sets of a given matroid.
Is anything known about exact solutions to this problem?


texts: Permanent in Bounded error Quasi Poly time

texts:
Is there any consequence to complexity theory if Permanent has a BQP (classical quasipoly version of BPP)?

Is there any consequence to complexity theory if Permanent has a QP (classical quasipoly version of P)?

I could not find any consequences from quick search on google (except for a result by Jin Cai on #P, EXP and BPTIME) and Valiant's original hypothesis only says VP is not VNP.

It could be that permanent has a quasipoly algorithm or circuit. Is there any arguments for and against this?


texts: Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this value is $\vartheta(G)$). Assuming the Shannon capacity problem is non-computable, can one expect to have a different computable function that can lower the lower limit on $r$ (assume that function takes values of $\vartheta(G)$ wherever it is tight)?


texts: techniques or examples of analyzing a series of graphs

texts:
Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "systematic" way. in this particular case $G_n$ is "more complex" than $G_{n-1}$ and generally has more edges/vertices.
Question:
What is some systematic method of determining the "basic differences" between $G_n$ and $G_{n-1}$?  In some sense, how does one derive a "recurrence relation" like a formula that derives $G_n$ from $G_{n-1}$ (similar to [1] but instead of using integers as parameters, here with graphs as the parameters)?  What are some famous examples of graph sequences like this, successfully analyzed in the literature?
Presumably this general question is undecidable for some contrived cases [exercise for reader] but is decidable for special cases.  I am interested in the subset of decidable cases.
Background
This is an old problem that first occurred to me about 2 decades ago which to my knowledge has not been studied too much in particular but which seems significant.  I have a particular algorithm in mind for generating $G_n$ from $G_{n-1}$ for which I suspect there is not much research (hint, see other question [2]), and might mention/further clarify at a later date; but for now I am interested in a more general approach.
Another analogy would be with textual "diff" programs which find lines added, deleted, modified between two text files.  Is there an analogous approach for graphs that has been used somewhere?  Actually, I suspect this type of construction is somewhat widespread in graph theory proofs, maybe even key/famous ones, but not necessarily studied so much in isolation.
In the best case scenario, there would be a software package that would actually successfully derive such formulas in some cases, but to my knowledge it does not exist right now.
[1] solving recurrence relations, wikipedia
[2] largest language class for which inclusion is decidable


texts: $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ problems

texts:
All the problems which are either $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ cannot admit a $\mathsf{PTAS}$, unless $P=NP$. I would like to know whether $\mathsf{MaxSNP}$ hardness results also give an explicit constant in their hardness proofs, or only $\mathsf{APX}-\mathsf{Hard}$ proofs do that? Are there any exceptions? Please support your answers with some examples from literature.

Thanks you.


texts: I couldn't find any source speaking about the consistency of [Weak] Monadic Second Order Logic over Binary Trees (or over graphs with finite tree/clique width). I did find decidability results, and it all looks to me like a finite amount of "interleaved Presburger arithmetics" with monadic second order quantification, roughly speaking. But I cannot find proofs or discussions about the topic. Can someone please enlighten me with a reference or an argument?


texts: Relationship between context-free/decidable languages and NP

texts:
As far as I understand all languages in NP are decidable. But not all decidable Languages are in NP, because NP only contains decision problems.
Are there also decision problems that are decidable but not in NP?

What is the relationship between NP and context-free/regular languages?
Are there context-free languages in NP?
Are there regular languages in NP?

Are there languages in NP that are not context-free?
Are there languages in NP that are not regular?


texts:
I read Freyd's paper "Algebraically Complete Categories" in the famous Como90 and I have two questions about the notion of algebraic compactness he defined in that paper. (If you are not familiar with the definition, here it is: A category is called algebraically compact if every endofunctor has an initial algebra and a final co-algebra which are canonically isomorphic.)

What are some examples of algebraically compact categories? Freyd mentions an example but strictly speaking the condition in the definition holds only for certain endofunctors of interest. From reading other papers (such as "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire") I guess that category of cpo's, omega-cpo's or categories enriched over (omega-) cpo's are algebraically compact. What is the standard reference for this fact?
Freyd says that the definition is motivated by the "principal of versality" and, being a nonnative speaker of English, I am confused. First of all, I think it should be principle, not principal. Also what is versality? Does he mean versatility? Is this a game on words like (uni)versality?


texts: Infinitary Counting Logics: 1-sorted vs. 2-sorted framework

texts:
There are two ways to extend infinitary logic with counting:

Grädel's way (cf. p. 11):

We extend $L_{\infty\omega}$ by introducing a counting existential quantifier:

$$ \mathcal{A} \models \exists^{\geq m} x \varphi(x) \Leftrightarrow
\textrm{There are at least $m$ $a \in A$ s.t. } \mathcal{A} \models \varphi(a).$$

Introducing such a quantifier for $\mathsf{FO}$ does not increase the expressive power because can easily define it with the usual $\exists$-quantifiers. However, $C^1_{\infty\omega}  \not\leq L_{\infty\omega}$
(One variable is sufficient to express that $|A|$ is even in $C_{\infty\omega}$ yet it is not definable in $L_{\infty\omega}$).

Libkin's way (cf. p. 8):

We define a two-sorted framework. We have two kinds of variables now

Number variables in $N^A = \{ x \in \mathbb{N} \mid 0 \leq x \leq |A|-1\}$
Vertex variables (the old type) in $A$

Additionally, we have the natural ordering on the numbers. Furthermore, we introduce

$$ \#x.\varphi \in N^A$$

which represent the numeric value how many  $x \in A$ satisfy $A \models \varphi(x)$.

  Libkin's way is at least as expressive as Grädel's way, since for
  $\exists^{\geq m} x \varphi(x)$ we write

  $$ \#x.\varphi \geq m.$$

Im trying to define Graph Canonization with Infinitary Counting Logics with finitely many variables. Libkin's way is easier on first glance since we have free numerical variables which can represent graph nodes, edges and so on. Graph Canonization with Fixed-Point Logics works very similar. However, for the Grädel way there are a lot of results like $k$-Pebble-Games and a connection the $k$-dimensional Weisfeiler-Lehman Algorithm which is a direct connection to the Graph-Isomorphism Problem.

Are the Libkin way and the Grädel way equivalent in expressiveness? Do the mentioned results work with the Libkin way? Are their respective restrictions with $k$ variables equivalent? How do I count the variables for the Libkin approach (numerical variables + vertex variables?)?

Any ideas how to define Graph Canonizations with the Grädel way?


texts: Questions about P vs NP and geometric complexity theory

texts:
Reading through various papers on geometric complexity theory (GCT), there is one thing, which pops up, while claimed in various places, that it is an approach to P vs NP, all the results seems to accumulate in conditional statements for VP vs VNP or NC vs #P. Are there any implications known, which connect the obstruction-based approach to VP vs VNP with P vs NP?
One more thing I keep wondering about is whether the attempts at separation through obstructions are strict, i.e. is there a class of obstructions, which exists if and only if $VP \neq VNP$?
Note: I use P vs NP here in the precise sense of Cook's hypothesis, not in the sense of P v NP in fields of certain characteristic as it sometimes appears in GCT papers.


texts: Network / Social network analysis visualization tools?

texts: I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network / social network analysis and visualization.


texts: If you could rename dynamic programming...

texts: If you could rename dynamic programming, what would you call it?


texts:
Let $G$ be a graph with (positively) weighted edges.
I want to define the Voronoi diagram for a set of nodes/sites $S$, to
associate with a
node $v \in S$
the subgraph $R(v)$ of $G$ induced by all the nodes
strictly closer to $v$ than to any other node
in $S$, measuring the length of a path by the sum of weights on the arcs.
$R(v)$ is $v$'s Voronoi region.
For example, the green nodes below are in $R(v_1)$, and the yellow nodes
are in $R(v_2)$.

I would like to understand the structure of the Voronoi diagram.
As a start, what does the diagram of two sites $v_1$ and $v_2$ look like,
i.e., what does the 2-site bisector look like (blue in the above example)?
I think of the bisector $B(v_1,v_2)$ as the complement of $R(v_1) \cup R(v_2)$
in $G$.  Here are two specific questions:

  Q1. Is the bisector of two sites connected in some sense?

  Q2. Is $R(v)$ convex in the sense that it contains the shortest path between any two
  nodes in $R(v)$?

Surely this has been studied before.  Can anyone provide references/pointers?
Thanks!

Addendum for Suresh's comment:


texts: It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer variables also FPT?


texts: A k-approximation to k-way number partitioning

texts:
The $k$-way number partitioning problem accepts as input a multiset $S$ of positive numbers, and returns a partition of $S$ into $k$ subsets such that the subset sums are as nearly-equal as possible, namely,

the largest sum is as small as possible, or -
the smallest sum is as large as possible.

Both problems are NP-hard even for $k=2$. Denote the optimal solutions of both problems by $MinMax(S,k)$ and $MaxMin(S,k)$ respectively. Note that both are weakly-decreasing functions of $k$. Are there polynomial-time algorithms that find a partition of $S$ into $k$ subsets such that -

the largest sum is at most $MinMax(S,k-1)$, or -
the smallest sum is at least $MaxMin(S,k+1)$?

The Wikipedia page on number partitioning describes many polynomial-time approximation algorithms for this problem, but they have guarantees of different forms -  at most $(1+\epsilon)\cdot MinMax(S,k)$ or at least $(1-\epsilon)\cdot MaxMin(S,k)$.
There are also algorithms that give constant-factor approximations to the related problems of bin packing and bin covering. Using these algorithms and binary search, I think it is possible to find approximations to number partitioning in weakly-polynomial time. However, the guarantees would be of the form $MinMax(S,k/(1+\epsilon))$ or $MaxMin(S,k/(1-\epsilon))$, where $\epsilon$ is the corresponding approximation factor.
is it possible to attain in polynomial time, an additive $k$-approximation?


texts: Original reference for Huffman shaped Merge Sort?

texts:
What is the first publication of the concept of optimizing merge sort by

identifying sequences of consecutive positions in increasing orders (aka runs) in linear time; then
repeatedly merging the two shortest such sequences and adding the result of this merging to the list of sorted fragments.

In some of my publications (e.g. http://barbay.cl/publications.html#STACS2009, http://barbay.cl/publications.html#TCS2013) I used this trick to sort faster and to generate a compressed data structure for permutation.

It seems that this trick was introduced before, just in the context of sorting faster, but neither me nor my student have been able to find back the reference?


texts: What is the state of the art in first order stochastic convex optimization?

texts:
What is the optimally fastest convex risk minimizing algorithm which only uses a stochastic first order oracle? Is this SGD?
What is the optimally fastest convex function minimizing algorithm which only uses a stochastic first order oracle?

I think I can find 3 kinds of references :

If the objective is a finite sum of convex functions then I think the optimally fastest algorithm is Allen-Zhu's Katyusha (https://arxiv.org/pdf/1603.05953.pdf)

But without this finite sum assumption and also without any smoothness assumption I believe Shamir-Zhang's result  (https://arxiv.org/pdf/1212.1824.pdf) is optimal who showed that for strongly convex objectives and convex objectives the function value of the $T^{th}-$iterate is getting close in expectation to the global minima at rates $O(\frac {\log T}{ T})$ and $O(\frac {\log T}{ \sqrt{T}})$ respectively. They also show some averaging schemes which try to ameliorate the $\log T$ terms in the numerator.

Upto this log factor I believe Shamir-Zhang is optimal given the lowerbounds in shown in, Hazan, E., Agarwal, A., and Kale, S. ``Logarithmic regret algorithms for online convex optimization" Machine Learning, 69(2-3):169–192, 2007.

If one is allowed smoothness and strong-convexity then Lemma $1$ (page $4$) (https://arxiv.org/pdf/1109.5647.pdf) by Rakhlin-Shamir-Sridharan here  shows $O(\frac 1 T)$ convergence in expectation of the squared distance from the global minima of the $T^{th}-$iterate of the SGD for smooth strongly convex functions. (this also holds for the function value)

This is optimal (reference?) and is also achievable for strongly convex functions by more complicated algorithms without needing smoothness like in Hazan, E. and Kale, S. ``Beyond the regret minimization barrier: An optimal algorithm for stochastic strongly-convex optimization" and this Rakhlin-Shamir-Sridharan paper shows that without smoothness SGD cant achieve this $O(\frac 1 T)$ rate.

Did I miss any case?


texts: Competing against an optimal weighted majority in experts algorithm

texts:
In the experts problem, $n$ experts give you binary predictions on a daily basis, and you have to predict whether it's going to rain tomorrow.

That is, at day $t$, you know the past predictions of the experts, the actual weather for days $1,2,\ldots t$, and the predictions for tomorrows, and have to predict whether it will rain the next day.

In the classic Weighted Majority algorithm, the algorithm makes $O(\log n + m)$ mistakes, where $m$ is the number of mistakes of the best expert.

To me, this seems like an extremely weak promise, as it does not allow any benefit from combining predictions of several experts.

Assume that each outcome is $\{\pm 1\}$, prediction of expert $i$ on day $t$ is $p_{i,t}$, and the outcome of day $t$ is $o_t$. We can define an ``optimal weighted majority'' adversary as an optimal weight function $w\in\Delta([n])$, such that the decision made by the adversary on day $t$ is defined as $sign(w\cdot p_t)$, i.e. the weighted majority of the predictions, with respect to the vector $w$. Using this notation, the previous adversary (best expert) could only pick unit vectors.

We can then define the optimal error for days $1,2,\ldots T$ as:
$$E = \frac{1}{2}\min_{w\in\Delta([n])} \sum_{t=1}^T|sign(w\cdot p_t)-o_t|$$

  How would you minimize the regret, compared to $E$?

To see that this is a much more powerful adversary, consider the case of $3$ experts and $3$ days in which the outcome was always $1$.
If $p_1=(1,1,-1), p_2 = (1,-1,1), p_3=(-1,1,1)$, then each expert had a mistake, but a weighted majority vector of $(1/3,1/3,1/3)$ had none.


texts: Ways for a mathematician to stay informed of current research in complexity theory

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

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

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

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


texts:
While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's.  After some link following, googling and wikipeding, I came across Ladner's Theorem:

  Ladner's Theorem:  If ${\bf P} \ne {\bf NP}$, then there are problems in  ${\bf NP} \setminus  {\bf P}$ that are not ${\bf NP}$-complete.

and to Schaefer's theorem:

  Schaefer's Dichotomy Theorem: For every constraint language $\ \Gamma $ over $\{0, 1\}$, if $\  \Gamma $ is Schaefer then ${\bf CSP}(\Gamma)$ is polynomial time solvable.  Otherwise, ${\bf CSP}(\Gamma)$ is ${\bf NP}$-complete.

I read this to mean that, by Ladner's, there are problems that are neither ${\bf P}$ nor ${\bf NP}$-complete, but by Schaefer's, problems are either ${\bf P}$ and ${\bf NP}$-complete only.

What am I missing?  Why don't these two results contradict each other?

I took the condensed version of the above theorem statements from here.  In his "Final Comments" section, he says "Thus, if a problem is in ${\bf NP} \setminus {\bf P}$ but it is not ${\bf NP}$-complete then it can not be formulated as CSP".

Does this mean ${\bf SAT}$ problems miss some instances that are in ${\bf NP}$?  How is that possible?


texts: How can a problem be in NP, be NP-hard and not NP-complete?

texts:
For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP.

However, in the famous paper "The ellipsoid method and its consequences in combinatorial optimization", the authors claim that the fractional chromatic number problem belongs to NP and is NP-hard, yet is not known to be NP-complete. On the third page of the paper, the authors write:

  ... we note that the vertex-packing problem of a graph is in a sense equivalent to the fractional chromatic number problem, and comment on the phenomenon that this latter problem is an example of a problem in $\mathsf{NP}$ which is $\mathsf{NP}$-hard but (as for now) not known to be $\mathsf{NP}$-complete.

How is this possible? Am I missing a subtle detail in the definition of NP-complete?


texts: Self-organizing Sequential Search Heuristics

texts:
I've read the paper by Jon L. Bentley "Amortized analyses of self-organizing sequential search heuristics". It deals with different schemes for improving linear search. (such as after every access to an element move it to front or transpose neighboring elements) And at the end of the paper was a section for those who are interested in practical applications of this techniques.

It says that such techniques has practical applications if you want to do a linear search quicker (obviously, it's true).
But can you give some example of such problem?
If we need to make fast searching , insertion and deletion why don't you use HashTable? I thought the only reason why we use Linked List is that it preserves order and its very easy to implement. Am I right?
But with such heuristics we don't preserve order. But it's still easy to implement...

So for what purposes do we use such heuristics that don't preserves order for list?
Thank you very much!


texts: Are both safety and liveness properties closed under finite intersection?

texts: Given two safety properties $P_1$ and $P_2$, is their intersection $P_1 \cap P_2$ also a safety property? Similarly, if $P_1$ and $P_2$ are liveness properties, is $P_1 \cap P_2$ also a liveness property?


texts: Set of languages that can represent every c. e. languange

texts:
Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e. L$?

For example, a lot of languages can be formed by  it's union, intersection, complement of context-free languages, but some languages can not be, is, it possible that every L , computably enumerable language with infinity words be formed by union,complement,intersection (finite/infinite) of unabiguous CFLs with infinite words? If not, is it possible that every L , computably enumerable language with infinity words be formed by union,complement,intersection (finite/infinite) or any operation of unabiguous CFLs with infinite words plus some other languages such as  some context-sensitive languages?

$\textbf{update:}$ although the question has been answered, I hope there will be more solution to this problem. Thanks in advance.


texts:
Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize  "for Introduction of New Ideas and Techniques".

What are to your minds the main new ideas and techniques that Lipton developed?

Note. This question shall become community wiki, please put one such idea, technique or result per answer.


texts: Constraint types (IBM/X10) compared to dependent types

texts:
Constraint types have been proposed by IBM in their X10 programming language (it's a commercial programming language, not open source software).

Nystrom, Nathaniel, et al. "Constrained types for object-oriented languages." ACM Sigplan Notices. Vol. 43. No. 10. ACM, 2008.
http://www.model.in.tum.de/um/reading-group/Grothoff.oopsla08.pdf

How do “constraint types” compare to dependent types? Or do they resemble more one of the haskell extensions that simulate dependent types?

Can say the vector append from Agda be typed as say Lists in X10?

_++_ : ∀ {m n} {A : Set} → Vec A m → Vec A n → Vec A (m + n)

Further references on constraint types:

Saraswat, Vijay, et al. "Constrained Types-Future Directions." CP-18th International Conference on Principles and Practice of Constraint Programming-2012. 2012.
http://www.cs.nyu.edu/~lianah/files/CP-2012.pdf

Nystrom, Nathaniel, et al. "Genericity through Constrained Types.
http://www.nanocow.com/nystrom/papers/generics.pdf

Tardieu, Olivier, et al. "Constrained kinds." Proceedings of the ACM international conference on Object oriented programming systems languages and applications. ACM, 2012.
http://www.inf.usi.ch/faculty/nystrom/papers/res0179-tardieu.pdf


texts: Find a string with minimal edit distance from a set of given strings

texts:
Input: a bunch of binary strings: x_0, x_1, ... , x_n

Output: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. the minimum number of insertions, deletions, and substitutions to transform x into y.

What complexity class is this problem in? Does it have an efficient exact or approximation algorithm?


texts: What is the formal definitions of the reduction related to the "call/cc" (call with the current continuation) operator?

texts:
In lambda calculus or in combinatory logic we formally define reduction/expansion rules for terms (and in their typed variants reductions must preserve the type). Then we can talk about properties of such systems, in particular about the normalization property or confluence.

How could one formally define reductions for the call/cc (call with the current continuation) operator in terms of a rewrite system?

The semantics of the operator allows to abandon the current evaluation context and return to the point where the continuation was captured, effectively allowing the evaluation state to become explicit.

I'd be interested in such a definition that'd allow to formally talk about  confluence of such a system (and showing it doesn't hold, as the behavior of the operator depends on the evaluation order).