Does this pairwise independent random process have expected max load $\sqrt{n}$? This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ .  There the following question is asked and answered in the affirmative:

  Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the
  expected max load to be $\Theta(\sqrt{n})$ asymptotically?

Imagine we choose the explicit pairwise independent hash function family $h((ax+b) \bmod p) \bmod n)$. It is a straightforward standard exercise to show an upper bound of the following form:

$$P(\text{max number of values hashed to the same value} \geq 1 + \sqrt{2n}) \leq \frac{1}{2}$$

However, can a matching or near matching lower bound be found for the expected max load for this specific hash function family?

The hash family you give has expected max load $\tilde{O}(n^{1/3})$, as shown in this recent paper:

Mathias Bæk Tejs Knudsen, "Linear Hashing is Awesome"


When should you say what you know? What should you do when you see a question raised in public, say here on stack-exchange, that you know the answer to, because you are looking into as part of current research project?

For example, I see a TCS.SX question that I know the answer to, because I worked on the problem recently.  I haven't finished writing up the results yet and am trying to get a few more results to make an acceptable paper.

Should I contact the asker personally?  Claim credit publicly by publishing answer on the site?  What should I do?

I'll share my side of the story that is mentioned in Shiva's answer.

Shiva had several questions related to my own research (space-bounded algorithms for reachability problems). We were currently putting the final touches on a full draft of the proof, and were not ready to announce the result.  However, it was clear that Shiva was very interested in this area, so I emailed him saying we had a result in the works and gave him just the theorem statement.  A week later, we had our draft complete and I sent him a copy.  A few weeks later we shared our updated draft on the ECCC.

This worked well for several reasons.

Shiva and I have never met in person, but now we know each other as colleagues interested in similar problems.
Shiva also sent me a copy of his most recent work, which is also related and interesting.
The questions gave me an extra boost of motivation to complete a full draft quickly.

I recommend this course of action in the future: partial disclosure via private communication, full disclosure, and public announcement.


Maximum fractional packing of spanning trees. Given a graph $G$, let $\{T_1,\ldots,T_k\}$ be a set of spanning trees with associated nonnegative weights $\{w_1,\ldots,w_k\}$ such that for every edge $e$, $\sum_{e\in T_i}w_i \leq 1$.  This is a fractional packing of spanning trees.

What is the maximum total weight of such a fractional packing, i.e. the maximum possible value of $\sum_{i=1}^kw_i$?

Can this be done in polynomial time?  If so, how?

(Note that the dual linear program asks for the minimum total edge weight such that every spanning tree receives weight at least one, so the dual is a minimum fractional edge cut problem.)

The problem gets very easy if you look at the feasible space, which is simply the spanning tree polytope, intersected with a linear number of half-spaces, one for each packing constraint.

The spanning tree polytope has a separation oracle (check this for example), therefore since you only have an additional linear number of constraints, it carries over to yield a separation oracle for your problem. Using this oracle, you can optimize any linear functional of the polytope in polynomial time.

If I remember well, using the ellipsoid algorithm, you can get a running time of $\tilde{O}(m^2 \cdot T)$, where $T$ is the running time of the separation oracle (which in this case you can get from a min-cut algorithm). Probably not as good as other existing algorithms, but it gives you an idea of how you can quickly check that the problem is polynomial time solvable.


Looking for reference on NP-Completeness of proofs of length n Given a deductive system $\Lambda$, and some well-formed-formula S, one can ask the question "Is there a proof S in $\Lambda$ of length n?"  If n is presented in base-1 and if all the axioms of $\Lambda$ are polynomial-time verifiable, and if $\Lambda$ is sufficiently powerful to express the verification for some NP-Complete problem like 3-SAT, this problem is known to be NP-Complete.  It requires super-polynomial time if n is not.

I know how to prove this, but I am also sure that somebody else has already proven this.  Can somebody direct me to an existing published reference?

See this paper: On Godel’s Theorems on Lengths of Proofs II:
Lower Bounds for Recognizing $k$ Symbol Provability by Samuel R. Buss, 1995.

  This paper discusses a claim made by Godel in a letter to von
  Neumann which is closely related to the P versus NP problem.
  Godel’s claim is that $k$-symbol provability in first-order logic can
  not be decided in $o(k)$ time on a deterministic Turing machine.
  We prove Godel’s claim and also prove a conjecture of S. Cook’s
  that this problem can not be decided in $o(k/ \log k)$ time by a
  nondeterministic Turing machine. In addition, we prove that the
  $k$-symbol provability problem is NP-complete, even for provability
  in propositional logic.


Does zero integrality gap imply zero duality gap for certain problems? We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the relaxation, both admit integral solutions (zero "integrality gap"). I want to know if the converse holds, at least in some cases.

Suppose I have a 0-1 integer program $P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$, where the matrix $A$ is a $0-1$ matrix. Suppose the linear programming relaxation $P'$ of $P$ has an integral optimal solution. Then does the linear programming dual of $P'$ also admit an integral solution?

I would appreciate any counter-examples or pointers..

Here is an instance that could be close to a counterexample to the
claim.

Consider the LP $P = \max \{ 1^T x \,|\, Ax \leq 1, x \leq 1, x \geq
0\}$ and its dual $P' = \min \{1^Ty + 1^Tz ~|~ A^Ty + z \geq 1, ~y
\geq 0, z \geq 0 \}$ for the $12 \times 6$ matrix

$ A =
\begin{bmatrix}
 1 & 0 & 0 & 0 & 0 & 1\\
 0 & 1 & 0 & 0 & 1 & 0\\
 1 & 1 & 0 & 0 & 0 & 0\\
 0 & 0 & 1 & 0 & 1 & 1\\
 0 & 1 & 0 & 0 & 0 & 0\\
 1 & 0 & 0 & 0 & 1 & 0\\
 0 & 0 & 0 & 0 & 0 & 1\\
 0 & 0 & 1 & 0 & 0 & 0\\
 1 & 0 & 0 & 0 & 1 & 0\\
 0 & 0 & 0 & 1 & 0 & 0\\
 0 & 1 & 1 & 0 & 0 & 1\\
 0 & 0 & 1 & 1 & 0 & 0
\end{bmatrix}\,.
$

An optimal solution of $P'$ is given by $y_1=y_2=y_{12}=1$ (all other
variables are zero), with the objective function value of $3$. The
Optimal solution of $P$ is given by the vector $x =
[0.5~0.5~0~1~0.5~0.5]^T$. If you solve $P$ as an integer program, the
optimal objective function value is only $2$, and $x = [1~0~0~1~0~0]$
is an optimal solution.

In summary, the LP $P'$ has an integral optimal solution, but its
dual, $P$ does not have an integral optimal solution. The primal-dual
roles are reversed from the set up that Ankur wanted. But given the
nature of LP duality, this instance could still be considered a
counterexample to the general statement of the original claim.


Lower bound for testing closeness in $L_2$ norm? I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem:

Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, test (whp) whether

$D_1=D_2$
or $\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon$

Batu et al. [BFR+00] showed that $O\left(\frac{1}{\epsilon^4}\right)$ samples were sufficient, but I haven't found any mention of a lower bound?

I reckon one could always show a $\Omega(\frac{1}{\epsilon^2})$ lower bound by reducing the task of distinguishing a fair vs. $\epsilon$-biased coin to this problem (simulating a distribution supported on only two points, and answering the queries of the tester according to the iid coin tosses), but that still leaves a quadratic gap...

(Another point I'd be interested in is a lower bound in estimating (up to an additive $\epsilon$) this $L_2$ distance — again, I have found no reference to such result in the literature)

Thanks for your help,

It appears that $O(1/\epsilon^2)$ samples — as usul showed below — is enough for testing, so that the sample complexity is exactly $\Theta(1/\epsilon^2)$; actually, it turns out this number of samples us even enough for learning $D$ up to an additive $\epsilon$ wrt the $L_2$ norm.

Let $\hat{D}$ be the empirical density function obtained by drawing $m$ i.i.d. samples $s_1,\dots, s_m\sim D$ and setting
$$
\hat{D}(k) \stackrel{\rm{}def}{=} \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}},\qquad k\in[n]
$$
Then
$$
\begin{align*}
\lVert D - \hat{D} \rVert_2^2 &= \sum_{k=1}^n \left( \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - D(k) \right)^2 = \frac{1}{m^2}\sum_{k=1}^n \left( \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - mD(k) \right)^2 \\
&= \frac{1}{m^2}\sum_{k=1}^n \left( X_k - \mathbb{E} X_k \right)^2
\end{align*}
$$
where $X_k\stackrel{\rm{}def}{=} \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}}\sim\operatorname{Bin}( m, D(k) )$. The $X_k$'s (for $k\in[n]$) are not independent, but we can write
$$
\begin{align*}
\mathbb{E}\lVert D - \hat{D} \rVert_2^2 &= \frac{1}{m^2}\sum_{k=1}^n \mathbb{E}\left[ \left( X_k - \mathbb{E} X_k \right)^2 \right]
= \frac{1}{m^2}\sum_{k=1}^n \operatorname{Var} X_k \\
 &= \frac{1}{m^2}\sum_{k=1}^n mD(k)\left( 1- D(k) \right) \leq \frac{1}{m}\sum_{k=1}^n D(k) \\
&= \frac{1}{m}
\end{align*}
$$
so that for $m\geq \frac{3}{\epsilon^2}$,
\begin{equation}
\mathbb{E}\lVert D - \hat{D} \rVert_2^2 \leq \frac{\epsilon^2}{3}
\end{equation}
and applying Markov's inequality
\begin{equation}
\mathbb{P}\left\{ \lVert D - \hat{D} \rVert_2 \geq \epsilon \right\} \leq \frac{1}{3}.
\end{equation}


Program transformation using partial functions which preserve partial correctness Much work has been done demonstrating that certain program transformations preserve particular properties.  That is, for any program $P$ which has property $\alpha$, show that $P$ transformed under transformation $T$ still has property $\alpha$.

I'm interested in a transformation which replaces every usage of function $f$ in $P$ with partial function $g$, where $g$ is a restriction of $f$ (meaning that $g(x) = y \implies f(x) = y$). It seems intuitively obvious that this transformation, while not necessarily preserving totatlity, preserves partial correctness.  Yet I cannot find a standard proof or reference on this or even mention of this seemingly elemental fact.

Can anyone help me out? A reference, a proof, a different formalism?

I imagine that you can prove this straight from the operational
semantics using the standard operational precongruence (assuming that
you have a sequential language). Some of the relevant techniques
have been collected in Operationally-based theories of program equivalence by
Andy Pitts.

If you have a Hoare logic of partial correctness for the language you are interested
in, you can probably
establish a meta-theorem to the effect that for all programs $M$, all
models $\xi, \xi'$ such that $\xi$ is less defined than $\xi'$, and
all formulae $A, B$, we have
$\xi \models \{A\} M \{B\}$ implies $\xi' \models\{A\} M \{B\}$.  Proving such
a meta-theorem typically boils down to the operational reasoning
mentioned above.

Such questions come up all the time in proving observational and
descriptive completeness of Hoare logics. As Neel points out in
an answer to your other question, domain theory is based upon
related ideas.


Keyword selection problem in search engine marketing auction First of all, I am still not sure whether cstheory is well adapted for this question, so I won't be offended if the crowd thinks it is not the case...

In search engine marketing, several problems are interesting. Design of fair (and profitable) auction mechanisms and computation of optimal bidding strategies under bounded monetary resources are two examples of interesting (and well documented) problems.

Another problem of interest is the one of keyword selection: how to select the most profitable keyword (without any link to the amount of money available or to the "topic" of the keyword). "Profitable" can be either giving the best revenue, or the best profit. These problem deals with uncertainty: the clickthrough rate of a keyword is not known, the conversion rate is not known either.

Are you aware of some theoretical work related to this problem?

In the most basic form this can be viewed as a learning problem: each keyword gives some profit (taking into account CTR, conversion rate, prices, etc.) which is not known and needs to be learned.  More or less a Multi-armed bandit problem.


Does the Law of Excluded Middle imply the Axiom K in Martin-Löf's Intensional Type Theory? So I've been wondering if the Law of Excluded Middle (LEM) implies the so-called Axiom K in Martin-Löf's Intensional Type Theory. The Axiom K states that
$$\Pi_{A : Type} \Pi_{x : A} \Pi_{p : \text{Id}(x,x)}, \text{Id}(p,\text{refl}_x)$$
In fact, I've been trying to prove the more general statement that
$$\Pi_{A : Type} \Pi_{x, y : A} \Pi_{p,q : \text{Id}(x,y)}, \text{Id}(p,q)$$
but after reducing $q$ to $\text{refl}_x$ by equality-induction I am stuck into the first problem. I also tried to proceed by contradiction, but it doesn't seem to work..

Is this provable at all?

Yes, LEM implies K. See HoTT book Theorem 7.2.5, known as Hedberg's theorem, which shows that any type with decidable equality satisfies axiom $K$. If we assume excluded middle, all types have decidable equality.

Your second principle is known as UIP or Uniqueness of Identity Proofs. It is equivalent to Axiom K, see Theorem 7.2.1 in the HoTT book (just scroll up from 7.2.5 by one page). Neither of these can be derived in Martin-Löf intensional type theory, by a famous result of Thomas Streicher and Martin Hofmann.


Gröbner bases in TCS? Does anyone know of interesting applications of Gröbner bases to theoretical computer science?

Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was wondering whether some tractable special cases were used to provide efficient algorithms/constructions/proofs in TCS or TCS-related areas (combinatorics, coding theory).

Gröbner basis computation, while EXPSPACE-complete in general, are in PSPACE over Boolean rings. This has applications in model-checking to replace BDDs: Quoc-Nam Tran, "A PSPACE Algorithm for Groebner Bases Computation in Boolean Rings", Proc. WASET, Vol. 35, Nov. 2008, ISSN 2070-3740

[NOTE] The result stating that Groebner basis computation is in PSPACE over Boolean rings seems wrong, see Mark van Hoeij, Gröbner basis in Boolean rings is not P-SPACE, arXiv:1502.07220, 2015.

[NOTE] The claim that the result stating that Groebner basis computation is in PSPACE over Boolean rings seems wrong, is wrong. The author confuses PSPACE-computability with having a polynomial size. A PSPACE function may well have exponentially long output.


Are any of the state of the art Maximum Flow algorithms practical? For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year.  Orlin's Max flows in O(mn) time or better gives an algorithm that runs in O(VE).

On the other hand, the algorithms I most commonly see implemented are (I don't claim to have done an exhaustive search; this is just from casual observation):

Edmonds-Karp: $O(VE^2)$,
Push-relabel: $O(V^2 E)$ or $O(V^3)$ using FIFO vertex selection,
Dinic's Algorithm: $O(V^2 E)$.

Are the algorithms with better asymptotic running time just not practical for the problem sizes in the real world?  Also, I see "Dynamic Trees" are involved in quite a few algorithms; are these ever used in practice?

Note: this question was originally asked on stack overflow, here, but I was told it would be a better fit here.

EDIT: I asked a related question on cs.stackexchange, specifically about the algorithms that use dynamic trees (aka link-cut trees), which may be of interest for people following this question.

I am one of the authors of the paper linked above.

Just want to mention that we used ``state-of-the-art'' to mean algorithms (with publicly available implementations) that perform well on max-flow instances arising in computer vision.

I would also like to add that within that narrow (yet practical) context, often the algorithms that perform well are the ones with poor theoretical guarantees. For instance, ref [5] from our paper (Boykov-Kolmogorov algorithm) is widely used in the computer vision community, but does not have a strongly polytime runtime bound.

Finally, in case anyone is interested, the data from our experiments is available here:
http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

The code will also soon be available too.


Can we infer the next player in chess from the current board configuration? Presume that a program memory only includes the current state for instance of a chess board. Does it need the variable which player, black or white, has the next turn to move or is it redundant recognizing the state?
Clearly its redundant during the first moves and then chess has so many combinations that there are combinations that can't guarantee that its deducible from just the state whether white or black has the next move, it needs that variable that wasn't needed during the first moves. How can I know the existence or non-existence of an algorithm in this case to know how the state went from deterministically knowable whether white or black has the next move to a state later in the game where the only possibility appears to keep a side variable to know whether white or black has the next move?
Is the logical consequence that I can't find a method to predict something like "making this move must activate a new boolean variable."
I'm trying to answer whether there is a method to know or just practically using the boolean variable blackHasNextMove to also include the information who is next to move for a chess game and there might be no method but in that case how do I prove that there is no method?.
Edit:
I'm asking how to know if changing a state from computable to unknown has an algorithm and I'm very thankful you even brought up the idea of time bounds for a solution using ordo notation.

There is, in fact, a subcategory of chess problems, the goal of which is to determine whose turn it is to move in the given position. Examples here. So while you need the "who moved flag" in general, for all the reasons given above, it seems to me that classification of all types of positions where you don't need the flag is a genuine research problem. Another question:

Given a mover-determinable position in chess on an n by n board, what is the complexity of determining who moved?

So you might want to look at things like that, if you want a theoretical project out of the problem.


How can I find the PhD thesis of C.A. Ellis? I've searched for this article all over the web but couldn't find it. can anyone help me?
Ellis, C.A. 1969. Probabilistic languages and automata. Rept. no. 355. Dept. Comp.
Sc. University of Illinois, Urbana, Ill.
PhD Thesis

You can find a pdf with the thesis in the following way:

Find the wikipedia page for Clarence Ellis;
On the wikipedia page find the link to his thesis "Probabilistic languages and automata";
Click on this link to find the corresponding archive.org page;
Download the thesis at archive.org.


Is there a reasonable automated proof system for TCS theorems? Suppose I wanted to formalize Turing's proof regarding the halting problem so that a machine could check it.  Some of the well-known automated theorem proving systems include Mizar, Coq, and HOL4.  I downloaded and experimented with Coq, but it doesn't have a library for Turing machines.  I thought to code one myself, but found the tutorial lacking and the language difficult to pick up.

My question is:  Is there an automated theorem prover that is generally good at proving theorems that involve Turing machines?  I would consider such a theorem prover "good" if it can formalize a proof of the undecidability of the halting problem using already-existing libraries.  I would consider it even better if it's relatively easy to pick up.  (For the record, I don't usually have difficulty with programming languages.)

Thanks,

Philip

Here is an Isabelle/HOL library containing Rice's theorem, which states undecidability of a wide range of problems. Since this library models computability via recursive functions, you have to encode a universal Turing machine as a recursive function in order to use this theorem for proving undecidability of the halting problem of Turing machines.  However, the essential parts of the undecidability proof is already done.

http://afp.sourceforge.net/browser_info/current/HOL/Recursion-Theory-I/index.html


More questions about permutations I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically.

the skew-merged permutations consist of the permutations that can be partitioned in an increasing and a decreasing subsequence; their basis is $\{3412, 2143\}$.
the vexillary permutations have basis $\{2143\}$; they have been introduced by Lascoux and Schützenberger in connection with Schubert calculus ('Schubert polynomials and the Littlewood–Richardson rule', Letters in Mathematical Physics 10(2), 111-124).

By the basis definition, it is immediate that a permutation $\pi$ is skew-merged iff both $\pi$ and $\pi^r$ are vexillary; this suggests some possible link between these two classes. I am interested in the following algorithmic questions:

Are there linear-time recognition algorithms for these classes? By the previous remark, an algorithm for class 2 would immediately yield an algorithm for class 1, although I suspect a more direct algorithm to exist in that case.
What is the complexity of the subpattern problem for two skew-merged or two vexillary permutations? The subpattern problem is known to be polynomial for separable and 2-increasing permutations, and these classes seem the next to study.

Re your question 1: Guillemot and Marx, "Finding small patterns in permutations in linear time", SODA 2014 solves these problems in linear time, and more generally gives a linear time recognition algorithm for every fixed permutation class with a finite basis.

I don't know of an answer for question 2 (when the subpattern may be variable in size).


Number of points on the interior of the convex hull of a random subset This question is in regards to the following problem:

  Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally likely. What is the expected number of points of $S$ that lie on the interior of the convex hull or $R$? I.e. What is $E[|S\cap \operatorname{int}(\mathcal{CH}(R))|]$?

I have been looking in Clarkson and Shor's Applications of Random Sampling in Computational Geometry, II, Mulmuley's chapter in the handbook of computational geometry, and related papers. As far as I understand it, these methods all apply to bounding the number of points of $S$ outside the convex hull, but do so by finding the expected sums of the sizes of conflict lists. For instance, the conflict list of an edge in the problem above is the number of points in $S$ that are beyond it, and the sum of the sizes of all conflict lists is $O(n)$. But because the same point may appear in $O(n)$ conflict lists itself, this doesn't seem to say anything about the number of points on the interior.

Any help in understanding the problem, or useful references is appreciated. Unfortunately, I have a sneaking suspicion that the answer is obvious, but find myself a bit stuck. Thanks.

Computing the probability that a point is inside a random convex-hull is quite interesting, and got some attention recently (under a slightly different sampling model). The exact probability can be computed (but not too quickly). Good estimates follow by looking on the Tukey depth of the points of interest. See the following recent paper, and references therein.

http://sarielhp.org/p/14/prob_ch/


Coloring where all colors are present in closed neighborhood of every vertex I am interested in (proper) vertex colorings of graphs with the following condition:
for every vertex $v$ in the graph, all colors should be present in the closed neighborhood of $v$.
Is this studied in the literature? The closest I found is $r$-dynamic $k$-coloring. For $k$-regular graphs, a ($k-1$)-dynamic $k$-coloring satisfies the above condition. But, I am also interested in a coloring that use less than $k$ colors and satisfies the above condition. Currently, I am more interested in such coloring of regular graphs.
If there is a paper dealing with ($k-1$)-dynamic $k$-colorings of $k$-regular graphs, I would like to read it (I saw a result on ($k+1$)-dynamic $k$-colorings in a paper).
Thank you.
Related Colouring Variants:-

$r$-dynamic $k$-coloring (also called $r$-hued $k$-coloring)
An $r$-dynamic $k$-coloring of $G$ is a (proper) $k$-coloring of $G$ such that every vertex $v$ in $G$ has neighbors in at least $\min\{deg(v),r\}$ different color classes.
b-coloring
A b-coloring is a (proper) coloring such that every color class $V_i$ contains a vertex $u_i$ which has neighbors in all other color classes.
In the coloring variant I am looking for, every vertex has neighbors in all other color classes.

Definition:-
For a vertex $v$ of $G$, the closed neighborhood of $G$, denoted by $N[v]$, is $v$ together with its set of neighbors.
i.e., $N[v]=\{v\}\cup\{u : uv\in E(G)\}$.

I would call this a polychromatic coloring of the closed neighborhood hypergraph.
I don't think this has been studied before for general graphs.
Here is a paper studying the question when edges are colored:
Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex Scott: Cover-Decomposition and Polychromatic Numbers
And here is one that studies the conflict-free coloring problem for your hypergraph:
Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, Rogers Mathew: Conflict-free coloring on closed neighborhoods of bounded degree graphs
If you replace closed neighborhood with geometric range spaces, then you can find a lot more literature, most notably my own amazing papers.


Erdos conjecture, number of cliques, Turan`s graph Erdos&Stone conjectured in 1946-08 that

there are at least $ck-1$ (k+1)-cliques in $G=(V,E)$
whenever $|V|=ck$, $|E|-1$ is the edge-count in Turan's
$T(|V|,k)$, i.e.,

$|E|= 1+\lfloor {(k-1)|V|^2} / (2k) \rfloor$.

I am looking to see whether this conjecture has been proved in literature.
Didn't see a trace of it myself.

Thanks in advance.

Isn't the conjecture in the paper that the number of $(k+1)$-cliques in this case is at least $c^{k-1}$? That's the number you get by adding a single edge to the Turan-graph. I think it's proved in 1969-10. Also relevant: 1983-28.
Recently, there has been significant progress on bounding the number of cliques as a function of the quadratic term of the number of edges: arxiv:1212.2454.


Do many-one reductions and Turing reductions define the same class NPC I wonder if NPC classes defined by many-one reductions and Turing reductions are equal.

Edit:
Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class $C$ such as there exists a problem not in $C \cup co-C$ under Karp reduction and which is in $C$ under Turing reduction ?

The "Boolean Hierarchy" BP is a whole hierarchy of combinations of NP problems under Karp reductions which are all in P^NP.


Which subproblems of 3SAT are still NP complete? The $\mathsf{NP}$-complete problems satisfy the property that if any of them is in $\mathsf{P}$, then all other $\mathsf{NP}$-complete problems are in $\mathsf{P}$.
The problem $3$-SAT is $\mathsf{NP}$-complete, as much as every $k$-SAT with $k\geq 3$.
(On the other hand, $2$-SAT is known to be in $\mathsf{P}$).

Obviously, the problem $3$-SAT can be seen as a subset of $k$-SAT for $k\geq 3$ and, in general, all of them are a subclass of SAT.

However my question goes in the opposite direction: which are some smaller subclasses of $3$-SAT that are still $\mathsf{NP}$-complete?

I am interested in studying the $\mathsf{P} = \mathsf{NP}$ conjecture by looking just into smaller class of $3$-SAT problems that are still acceptable.

I asked a similar question on cs.stackexchange.com, perhaps Juho's answer can help you; it contains references to: MONOTONE NAE-3SAT, MONOTONE 1-in-3-SAT, PLANAR 3SAT, k-COLOURABLE MONOTONE NAE-3SAT.

You can find other variants also in this cstheory question: 4-BOUNDED PLANAR 3-CONNECTED 3SAT, POSITIVE PLANAR 1-in-3 SAT.


Special Properties Of DAWGs with Unique Elements A DAWG is a specialized form of a Directed Acyclic Graph.  Admittedly, not terribly specialized.  I was wondering if DAWGs built from proper sets (unique, sorted) had any special properties?  It seems to me that they ought to have a couple of interesting properties regarding dependencies between the "layers" but but I'm at a loss as to how to prove it either way.  Anyone got a bit more knowledge regarding these bits of esoterica?

I could be missing something, but if you took an arbitrary DAG, assigned unique IDs to each vertex, and constructed all words formed by traversing monotone chains from top to bottom, then wouldn't the DAWG of that set be the original DAG ? If so, then a DAWG has no special structure.

Update: Peter Taylor's comment is the key difference. only one node with indegree 0 unlike a regular DAG.


Brackets expression incremental parsing algorithm I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets.

Consider the example with expression like "((1)())(2)". Parse tree for that expression is:

((1)())(2)
    ((1)())
        (1)
            1
        ()
    (2)
        2

Lets assume we inject additional symbols ")(" in the middle of the expression: "((1)()())(2)". My question is how to apply changes in the parse tree without reparsing of the whole input?

Take a look at Tim Wagner and Susan Graham's 1998 TOPLAS paper, "Efficient and Flexible Incremental Parsing", which extends LR parsing to support incremental  update of the document.


Practical consequences of $Parity \notin AC^0$ Background
Circuit complexity $AC^0$ is defined as the set of circuit families (i.e. sequences of circuits, one for each input size) of bounded depth and polynomial size built using unbounded fan-in AND, OR, and NOT.
The parity function $\oplus$ with $n$-bit input is equal to the XOR of the bits in the input.
One of the first circuit lowerbound proven in circuit complexity is the following:

[FSS81], [Ajt83]: $\oplus \notin AC^0$.

Questions:
Let $EC^0$ be the class of functions that can be computed using electronic circuits of bounded depth and polynomial size using electronic parts like transistors. (I made up the name $EC^0$, let me know if you know a better name for this).

Can we compute $\oplus$ in practice using $EC^0$ circuits?

What about unbounded fan-in AND/OR? Can we compute them in $EC^0$?

Does $\oplus \notin AC^0$ have any practical consequences? Is $AC^0$ important in practice?

Why is $\oplus \notin AC^0$ important for (theoretical) computer scientists?

Note:
This post contains interesting questions but OP seems to refuse to make the post more readable and fix the misconception in it for some reason, so I am reposting questions from it. (It would be easier to edit the original post but currently there isn't an agreement if it is OK to heavily edit another user's post.)
Related:

Parity and $AC^0$

Why is parity not in $AC^0$ important? (Computational Complexity Blog)

I am not an electrical engineer, but search for online patents regarding switching circuits for parity gates, and all proposals (I found patents only until the end of the 1970s) discuss the size-versus-depth problem. All three patents I have looked at propose solutions of logarithmic depth, based on fanin-2 gates. So the answer to your first question is possibly "no".

J.J. Moyer: Parity Check Switching Circuit, United States Patent US3011073, 1961

A.F. Bulver et al.: NAND Gate realization of the n-input parity function, United States Patent US3718904, 1973

P.J. Baun, Jr.: Parity Circuits, United States Patent US4251884, 1981


Why do we consider log-space as a model of efficient computation (instead of polylog-space) ? This might be a subjective question rather than one with a concrete answer, but anyway.

In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands for polynomial time, and $\mathsf{L}$ stands for log space. Both of them are considered to be represented as a kind of "efficiency", and they capture the difficulties of some problems pretty well.

But there is a difference between $\mathsf{P}$ and $\mathsf{L}$: while the polynomial time, $\mathsf{P}$, is defined as the union of problems which runs in $O(n^k)$ time for any constant $k$, that is,

$\mathsf{P} = \bigcup_{k \geq 0} \mathsf{TIME[n^k]}$,

the log space, $\mathsf{L}$, is defined as $\mathsf{SPACE[\log n]}$. If we mimics the definition of $\mathsf{P}$, it becomes

$\mathsf{PolyL} = \bigcup_{k \geq 0} \mathsf{SPACE[\log^k n]}$,

where $\mathsf{PolyL}$ is called the class of polylog space.
My question is:

  Why do we use log space as the notion of efficient computation, instead of polylog space?

One main issue may be about the complete problem sets. Under logspace many-one reductions, both $\mathsf{P}$ and $\mathsf{L}$ have complete problems. In contrast, if $\mathsf{PolyL}$ has complete problems under such reductions, then we would have contradict to the space hierarchy theorem. But what if we moved to the polylog reductions?
Can we avoid such problems? In general, if we try our best to fit $\mathsf{PolyL}$ into the notion of efficiency, and (if needed) modify some of the definitions to get every good properties a "nice" class should have, how far can we go?

  Is there any theoretical and/or practical reasons for using log space instead of polylog space?

The smallest class containing linear time and closed under subroutines is P. The smallest class containing log space and closed under subroutines is still log space. So P and L are the smallest robust classes for time and space respectively which is why they feel right for modeling efficient computation.


Does the Hindley-Milner type system (i.e. STLC with prenex polymorphism) have a category-theoretic model? It is well known that any CCC (cartesian closed category) is a model of the simply-typed $\lambda$-calculus. It is less well known that System F admits a categorical model, but it is also well studied (see, e.g., Amadio & Curien, Domains and Lambda-Calculi).
H-M lies between STLC and System F, but can we find a sensible categorical model for it? Particularly, I am interested in studying type inference in this categorical framework. Can we give H-M type inference a category-theoretic specification?
This presentation by Kammar and Moss presents some ideas in this direction, but I wonder if there's more work on this, particularly work that incorporates type inference.

Apart from what's already written in the slides you linked to, let me describe one possible approach.
For studying type inference semantically we need a model in which a term can have many types, or none. This naturally leads to Curry-style typing, i.e., we think of $t : A$ as a relation where both the term $t$ and the type $A$ are meaningful by themselves. (The opposite is Church-style typing where a term is always formed together with its type, and it cannot stand on its own.)
We can proceed as follows:

Give a model of untyped terms, such as a model of the untyped $\lambda$-calculus.
Give a model of types.
Define a "has type" relation between terms and types.

A concrete well-known example of this are PER models (although they model entire System F, not just Hindley-Milner):

Consider any model of the untyped calculus, for example, a reflexive domain $D$.
The types are the partial equivalence relations on $D$ (symmetric transitive relations on $D$).
$t \in D$ has type $T$ when $(t,t) \ni T$.

PERs have a rich structure (they form a CCC), for instance the exponential of $S$ and $T$ is the PER $S \Rightarrow T = \{(f,g) \in D \times D \mid \forall (x,y) \in S . (f x, g y) \in T\}$. This is all well-known.
Polymorphism in this model amounts to taking intersection of partial equivalence relations. For instance, $\lambda x . x$ has type $T \Rightarrow T$ for every PER $T$, and so it also has the type $\bigcap_{X \in \mathsf{PER}(D)} (X \Rightarrow X)$, which is the interpretation of $\forall \alpha . \alpha \to \alpha$.
You'll have to find something more nuanced to capture Hindley-Milner without capturing System F. That's what Kammar and Moss set out to do.


"k-matching" in graphs A matching in a graph is a set of edges that are pair-wise non-adjacent. IOW, each node involved in the matching appears in only one edge.

Now I am wondering is there a ``generalized'' concept of matching, such that it still refers to an edge-set, and each vertex involved can appear in at most $k$ edges in this edge-set, where $k \ge 2$ is a pre-specified positive integer.

If such concept does exist, what are some interesting and representative problems studied for that?

A short answer is http://en.wikipedia.org/wiki/Graph_factorization.  A more comprehensive reference might be the classic "Matching Theory" by Lovasz and Plummer, which is the best on this topic.


Complexity class of a subset problem similar to subset sum What could be the complexity class of the following problem:
Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' \subset S : \sum{S'} = K$ such that the elements of $S'$ form an arithmetic series with difference $d$ and $a = x_1$. So $S' = \{x_1, x_2 ..., x_n\}$ $: x_{i+1} = x_i + d$ for $2 \le x_i \le n$.

The problem is in NP, since given a solution set $A$ it is possible to check in polynomial time if $\sum{A} = K$.

The regular [0,1] Knapsack Problem and Subset Sum problem are NP complete and initially I figured this being similar would also be NP complete. However it differs since there is no relationship between the elements of a solution set of a Subset Sum problem. I was also unable to work out a reduction of any known NP-Complete problem to this problem.

The constraint on the solution set in the problem does not make it solvable in polynomial time. At best I can work out pseudo-polynomial time algorithms to solve this and the time blows up as K increases.

Am I right in suspecting this might be an NP-indeterminate problem or am I missing something?

PS: This is not homework. I am new at this and if this is not the right place for this question please advise and I shall move it. Thanks.

EDIT: After the discussions in the comments below I am providing a few examples towards what I am working on.

The above problem is trivial for the case where $d = 1$ and $n = 2$ for all $K$. It is easy when $K$ is even and for $d = 2$ and $n = 2$. I have been working on cases where $d = 2$ and $d = 4$ for $n \ge 3$ and didn't realise this.

For the case $K$ odd and $d = 2$, say $K = 65$ and I have $S = \{1,2,...,64\}$ and $S'= \{9,11,13,15,17\}$. The best algorithm I have for this takes time proportional to $\sqrt{K}$ and is thus exponential as $K$ grows.

For $K$ even, $d = 2$ and $n \ge 3$, say $K = 24$ I have $S'= \{3,5,7,9\}$.

I have found that when $K$ is odd or even then $|S|$ is odd or even respectively. I am trying to see if I can get a better algorithm to determine $S'$ or if I should concentrate elsewhere.

With some basic arithmetic, we can reduce this to a question about a two-variable Diophantine equation.

Based upon your comments, it sounds like $d$ was intended to be given as input.  Now the question is just: can we choose $x_1 \ge 1$ and $n$ such that $x_1 + (n-1)d < K$ and such that the arithmetic sequence $x_1,x_1+d,x_1+2d,\dots,x_1+(n-1)d$ sums to $K$.

It is easy to compute the sum of this arithmetic sequence.  By the Gauss formula, it sums to

$$n x_1 + dn(n-1)/2.$$

So, given $K,d$, we want to find a solution to the equation

$$n x_1 + dn(n-1)/2 = K$$

where $x_1,n$ are positive integers and where $x_1+ (n-1)d < K$.

You can view this as a diophantine equation in two variables $x,y$ of the form

$$2xy + \alpha x^2 + \beta x + \gamma = 0,$$

where $\alpha,\beta,\gamma$ are integer constants given in advance and there is an additional linear inequality on $x,y$.  (Here I made the replacement $x=x_1$, $y=n$.)  I don't know if this problem has a nice solution.

One thing we can say is that $n$ must be a divisor of $2K$, since we know

$$2nx_1 + dn(n-1) = 2K,$$

and the left-hand side is divisible by $n$.  Therefore, if you know the factorization of $2K$, and if it doesn't have too many different prime divisors, you could try enumerating all divisors of $2K$ as the candidate values of $n$, and then for each candidate value of $n$, solve for $x_1$  and see if it yields an integral solution.  However, in general this will not be efficient: it gives an algorithm that is efficient in the average case but runs in exponential time in the worst case.


How powerful are nondeterministic constant-depth circuits? A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ on input string $x\in \{0,1\}^{n}$ outputs $1$ if and only if there exists some witness string $w\in \{0,1\}^{\mbox{poly}(n)}$ such that the output of $C$ on input $(x,w)$ is $1$.

M.J. Wolf introduced nondeterministic circuits in 1987 and showed that $\mathsf{NC}$ circuits with a polynomial amount of nondeterministic gates are equivalent to $\mathsf{NP}$, and that $\mathsf{NC}$ circuits with $O(\log n)$ nondeterministic gates are equivalent to $\mathsf{NC}$ itself.

How much more power does a polynomial amount of nondeterministic add to constant-depth circuit classes, such as $\mathsf{AC}^{0}$, $\mathsf{ACC}^{0}$, and $\mathsf{TC}^{0}$? Do these classes then contain more powerful circuit classes like $\mathsf{NC}$ or $\mathsf{P/poly}$, or even $\mathsf{NP}$?

A polynomial amount of nondeterministic bits is enough to encode the computation of a nondeterministic polynomial time algorithm. The only thing we need is to check if a given string is an accepting computation which is syntactic task that can be performed by a polynomial-size $\mathsf{AC^0}$ circuit (in fact a polynomial size CNF can do this).

Another way to look at this is to consider the Tseitin translation from arbitrary circuits to CNFs which has a polynomial size increase and uses only polynomially many new propositional variables.

If you look at the $\mathsf{NP}$-compeleteness proof of CNF-SAT (or 3SAT) you see that the part that checks if a given CNF is satisfied by a given truth assignment can be computed by an $\mathsf{AC^0}$ circuit (IIRC $\mathsf{AC^0_d}$ circuits can be evaluated by an $\mathsf{AC^0_{d+1}}$ circuit).


Shortest paths perturbation I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that there is a path from $u$ to $v$, there is, after perturbation, a unique shortest path from $u$ to $v$, and this shortest path is one of the "original" shortest paths, that is, one of the shortest paths before the perturbation. It seems to me that the perturbation can only be additive and at most equal to the minimum difference between two edge weights divided by the maximum number of vertices in a shortest paths between pair of vertices in $G$ (let this number be $\Delta$). That is, the perturbation that I add to the edge $e\in E$ should be some
$$ \varepsilon_e \in\left[0, \frac{\min_{\ell,r\in E}|w_\ell-w_r|}{\Delta}\right]
$$
and distributed according to some distribution (is uniform sufficient?) on the interval.

Possibly, I would also like the "perturbed" shortest path to be chosen uniformly at random from the set of original shortest paths. Is this possible?
Any reference or hint is appreciated.
Thanks.

Probably the simplest approach is to perturb the edge weights symbolically rather than numerically.  Intuitively, you'd like to reassign the weight of each edge as
$$
\tilde{w}(e) = w(e) + \varepsilon \cdot w'(e)
$$
where $w(e)$ is the original edge weight, $w'(e)$ is a secondary edge weight, and $\varepsilon$ is a global scaling factor.  This perturbation scheme has to satisfy two requirements:

Every shortest path with respect to the perturbed edge weights must be also a shortest path with respect to the original edge weights.  It's not hard to prove that for any function $w'$, this property holds for all sufficiently small scaling factors $\varepsilon$.  Rather than spending time figuring out how small "sufficiently small" is, consider instead the limiting behavior as $\varepsilon$ approaches $0$.  Then your perturbed edge weights are best formalized as two-dimensional vectors
$$
\tilde{w}(e) = \big( w(e), w'(e) \big).
$$
The length of any path is also a vector, obtained by summing the vector-weights of each edge on the path.  Comparisons between length vectors are performed lexicographically:
$$
(a, a') < (b, b') \iff a<b \text{ or } (a = b \text{ and } a'<b')
$$
This definition trivially implies that for any paths $\alpha$ and $\beta$, if $w(\alpha) < w(\beta)$, then $\tilde{w}(\alpha) < \tilde{w}(\beta)$.  One nice feature of this scheme is that if shortest paths with respect to $w$ are already unique, the algorithm never even notices $w'$.
Shortest paths with respect to the perturbed edge weights must be unique.  It suffices to choose a function $w'$ such that shortest paths with respect to $w'$ are unique.  There are two standard methods for finding such a function $w'$.

The simplest method is to generate each $w'(e)$ randomly.  The Isolation Lemma of Mulmuley, Vazirani, and Vazirani implies that if each $w'(e)$ is chosen independently and uniformly at random from the set $\{1, 2, \dots, n^4\}$, then with probability $1-O(1/n)$, all shortest paths are unique.  This scheme works for any shortest path algorithm with no run-time penalty and little modification to the algorithm, but it does have a small probability of failure.
A more complex deterministic method (which linear-programming people know as "lexicographic perturbation") indexes the edges from $1$ to $m$ and defines $w'(e_i) = 2^i$.  Clearly every subset of edges has distinct total $w'$eight.  However, using this method requires manipulating $m$-bit integers, so it's more efficient to implement this method symbolically as well.  For any paths $\alpha$ and $\beta$, we have $w'(\alpha) < w'(\beta)$ if and only if the minimum edge-index in $\alpha\setminus\beta$ is smaller than the minimum edge-index in $\beta\setminus\alpha$.  Most shortest-path algorithms only compare paths that share a common prefix (starting at some source node $s$) and are otherwise edge-disjoint.  With an appropriate dynamic tree data structure (e.g., link-cut trees or top trees), it is possible to find the node where the two paths split and the minimum edge-index along the disjoint suffixes in $O(\log n)$ amortized time.  So, this scheme is always correct, but it imposes a penalty in the running time that is only $O(\log n)$ if your algorithm has the right structure, and it requires significant data structure overhead.

You can guess which method I recommend.  My recent journal paper with Sergio Cabello and Erin Chambers describes both of these perturbation schemes in more detail.

There are also more specialized methods for specific algorithms and specific classes of graphs.

  I would also like the "perturbed" shortest path to be chosen uniformly at random from the set of original shortest paths. Is this possible?

I don't know.  In particular, the randomized perturbation scheme I described does not have this property.


Polynomial time solvable instances of Max-Sat The problem Max-Sat ask you to find an assignment of a CNF formula which satisfy as many clauses as possible.

For the simpler problem SAT there are many known special cases which can be solved in polynomial time, e.g. we can solve 2-SAT in polynomial time.

For Max-Sat the situation is different since Max-Sat is NP-hard even for 2-CNF formulas (each clause contains only 2 variables).

Is there any interesting special inputs for which Max-Sat is polynomial?

In particular I would be interested in a standard reference for solving Max-Sat when the incedence graph has bounded treewidth.

This does not answer directly your Max-SAT problem but the references may guide you to the complete answer.

Szeider showed that Satisfiability is ﬁxed-parameter tractable when parameterized by the treewidth of the incidence graph. Samer and Szeider gave an eﬃcient dynamic programming algorithm.

References

S. Szeider. On ﬁxed-parameter tractable parameterizations of SAT. In Proc. 6th
International Conference on Theory and Applications of Satisﬁability (SAT’03),
Selected and Revised Papers, vol. 2919 of LNCS, pages 188–202. Springer-Verlag,
2004.

M. Samer and S. Szeider. Algorithms for propositional model counting. In Proc.
14th Internationial Conference on Logic for Programming, Artiﬁcial Intelligence
and Reasoning (LPAR’07), vol. 4790 of LNCS, pages 484–498. Springer-Verlag,
2007.

Samer and Szeider, Fixed-parameter tractability. In A. Biere, M. Heule,
H. van Maaren, and T. Walsh, editors, Handbook of Satisﬁability, part 1,
chapter 13. IOS Press


Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS? Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science.  The best examples are those where the connection was not obvious, but once it was discovered, it is clearly the "right way" to do it.

This is the opposite direction of the question Applications of TCS to classical mathematics?

For example, see "Green's Theorem and Isolation in Planar Graphs", where an isolation theorem (which was already known using a technical proof) is re-proven using Green's Theorem from multivariate calculus.

What other examples are there?

Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou got the Godel prize in 2004 for their use of algebraic topology in the study of some problems in distributed computing.


Regular languages and constant communication complexity Let $L \subseteq A^*$ be a language, and define $f_L\colon A^* \times A^* \to \{0, 1\}$ by $f_L(x, y) = 1$ iff $x\cdot y \in L$.  I'm searching for a reference for:

Proposition. $L$ is regular iff the deterministic communication complexity of $f_L$ is constant.

In other words, $L$ is regular iff there exists a two-player protocol $P$ for $f_L$ such that the function $$n \mapsto \max\{\text{comm}(P, x, y) : |x\cdot y| = n\}$$  is bounded by a constant, where $\text{comm}(P, x, y)$ is the number of bits exchanged by Alice and Bob when Alice receives $x$ and Bob $y$, following the protocol $P$.

The only place I could find that is in George Hauser's PhD thesis, 1989, available here, where he also generalizes that to other distributions of the input $x\cdot y$ among Alice and Bob, such that the number of "cuts" is constant.

For $\Rightarrow$, you have "Communication Complexity", Eyal Kushilevitz in Advances in Computers, Volume 44, 1997 (http://www.sciencedirect.com/science/article/pii/S0065245808603423).

You can also find a section "Communication Complexity and Chomsky Hierarchy" in the book "Communication Complexity and Parallel Computing" by Juraj Hromkovič where it is proven. It may be that $\Leftarrow$ is also proven somewhere in the book but I fail to find it here. The closest thing there seems to be is Exercise 5.2.5.2 but, it is only an exercise (see the whole Chapter 5 too, which extensively study finite automaton but I do not think it explicitly answers your question).

For what it is worth, the proof of both directions looks easy so I think that if you need it in a paper you can sketch it quickly: for $\Rightarrow$, take a finite automaton for $L$ and observe that it is sufficient for Alice to communicate the state she reaches after having read her part of the input. Then Bob finishes the simulation in the automata. For $\Leftarrow$, if you have a protocol bounded by a constant, then $L$ has a finite number of quotient $w^{-1}L = \{u : wu \in L\}$ which is a well-known characterization of regular languages.


Objective function for stochastic optimization Stochastic Optimization problems in general deals with random variables in the 'loss function'.

Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we usually have,

\begin{equation}
\min_{x} \parallel Ax-b \parallel_2^2
\end{equation}

With some uncertainty or possible variations in the data matrix A, it is natural to use the expected value of the objective function $\parallel Ax-b \parallel_2^2$:

\begin{equation}
\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)
\end{equation}

How is the above objective function different from the following objective function-
\begin{equation}
E\left( \min_{x} \parallel Ax-b \parallel_2^2 \right)
\end{equation}

Certainly, for the basic objective function, first objective has a closed form compared the second objective. But, why aren't we dealing with the second objective in general ?

Which is more precise ?

First, notice that the first objective is a minimization problem, who's solution is a vector $x$, while the second is merely a number.

The objective $\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)$ asks for the vector $x$ which best explains the data.

If $A$ is stochastic, it still looks for the best $x$ which, on average, is the best one.

The lower objective asks for "What's the expected error of the best $x$, in hindsight ", i.e. after we fix $A$, take the minimum over all $x$'s, and ask what's the error.
(more formally, for different $A$ values there are different "best" $x$s, so the each time take the best one for computing the error).

Since we are usually interested in finding the feature vector $x$ which explains the data, and not the expected error of the best $x$ after $A$ is fixed, the first stochastic objective makes more sense. The only reason I can think of as why would someone be interested in the second is for competitive-analysis like proofs (i.e. what's the gap between the best $x$ prior to knowing $A$ and the best one afterwards).


Sensitivity-Block sensitivity conjecture - Implications Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$.

The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c>0$ such that $\forall f,\mbox{ }bs(f)\leq s(f)^c$.

What are the implications of the truth and falsehood of this conjecture?

Please quote references as well.

Here is what Scott Aaronson has to say on the subject:

  What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity measures: the decision-tree complexity of $f$, the certificate complexity of $f$, the randomized query complexity of $f$, the quantum query complexity of $f$, the degree of $f$ as a real polynomial, you name it.  So if, as is conjectured, sensitivity and block-sensitivity are polynomially related, then sensitivity—arguably the most basic of all Boolean function complexity measures—ceases to be an outlier and joins a large and happy flock.

Checking other relevant literature doesn't offer any other compelling implications:

Nisan and Szegedy describe the question but offer no motivation at all.
Kenyon and Kutin mention that is is a "natural open question".
Gotsman and Linial give a somewhat contrived equivalent problem (Conjecture 5.33 on page 18 of the following paper).
P. Hatami, Kulkarni and Pankratov, in their comprehensive survey on the problem, also offer no motivation, but they have several equivalent formulations. For example, the sensitivity conjecture is equivalent to the conjecture that the parity decision complexity of a function is polynomially bounded by the sensitivity. Conjecture 5.31 on page 17, due to Shi, is one reformulation that doesn't mention sensitivity at all.
Ambainis, Bavarian, Gao, Mao, Sun and Zao state that the conjecture "originates from the theory of complexity measures of Boolean functions and
decision tree complexity", and generally offer the same type of motivation as Scott Aaronson does. Their recent preprint is the last word on the conjecture (as of December 2014).


Optimal Self Balancing Trees with Canonical Form? Are any efficient [O(log n)] self balancing trees that are canonical? By canonical I mean that for any set of data inserted into the tree, inserting it after any permutation results in the same tree. I'm particularly interested in trees where data is stored in the leaves.

Andersson and Ottmann's "New tight bounds on uniquely represented dictionaries" has a good survey on the subject of of canonical (or "unique", as they call it) forms for dictionaries.

Before I describe it, I should note that their structure is actually stronger than you are looking for. Their structures are size-unique, so any two trees with $n$ elements will have the same shape, even if the sets of elements are unrelated. They leave the problem of set-unique data structures open, though see below about randomization.

Andersson and Ottmann invented a data structure (a graph, not a tree) where updates and lookups take $O(n^{1/3})$ time. By tuning a parameter, they can get $O(\sqrt{n})$ time for updates and $O(\lg n)$ time for lookups, matching an earlier structure of Sundar and Tarjan (which Ottmann claims in "Trees - A Personal View" is not strictly size-unique due to the way they use an auxiliary structure). Andersson and Ottmann also prove that either update or lookup operations must take $\Omega(n^{1/3})$ time in their particular model. An earlier paper by Snyder showed some $\Omega(\sqrt{n})$ lower bounds, but the model he used was too strict for Andersson and Ottmann's taste.

If you're willing to accept "canonical" meaning "taken from the same sample space of trees", then treaps might be exactly what you're looking for -- any set of elements in a tree has shape independent of the order in which they arrived. However, the shape is randomized.

For storing data in the leaves (by which I assume you mean that each key is stored in a leaf, or that value (in a map structure) are all stored in leaves), views of skip-lists as trees may have this property. I mentioned some tree-views of skip lists on another question at this site. Others that may deserve mention are

Daniel Golovin's The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees
Michael Spiegel and Paul F. Reynolds's Lock-free multiway search trees and      The Dense Skip Tree: A Cache-Conscious Randomized Data Structure

I've also been recently thinking about a treap-like structure in which every key is stored in a leaf, as mentioned in the related question I posed here. I hope to post something there on the matter soon.


What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat? I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.

Dimitris Achlioptas covers this in his survey article from the Handbook of Satisfiability (PDF).

There is conjectured to be a single threshold $r_k$ for each $k \ge 3$, so that when $m/n > r_k$ then a random $k$-SAT formula with $m$ clauses and $n$ variables is unsatisfiable with high probability, and so that when $m/n < r_k$ then a random $m$-clause, $n$-variable $k$-SAT formula is satisfiable with high probability.
(More precisely, the conjecture is that in the limit as $n$ tends to infinity, the probability of satisfiability is 0 or 1 in these two regimes, respectively.)

Assuming that this Satisfiability Threshold Conjecture holds, the best known bounds for $r_k$ are

k                   3      4      5     7     10      20
Best upper bound 4.51  10.23  21.33 87.88 708.94 726,817
Best lower bound 3.52   7.91  18.79 84.82 704.94 726,809

(this table appears on the page indicated as 247 in the draft).

In a more recent manuscript (arXiv:1411.0650), Jian Ding, Allan Sly and Nike Sun showed that for all sufficiently large $k$, there is in fact a single threshold $r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$, and the error term $o(1)$ in this expression goes to zero as $k$ tends to infinity.


Barriers and Monotone Circuit Complexity Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit complexity. Is there any progress towards identifying such barriers ? Are there other barriers in the monotone setting ?

Benjamin Rossman's recent paper summarises the state of the art for the monotone circuit complexity of k-CLIQUE.  In short, Razborov proved a lower bound in 1985, later improved by Alon and Boppana in 1987: $\omega(n^k/(\log n)^k)$, versus the brute force upper bound $O(n^k)$.

Rossman shows a lower bound of $\omega(n^{k/4})$ for the average-case complexity in the Erdős-Rényi model of random graphs; Amano previously showed this was essentially also the upper bound.  The quasi-sunflower lemma that forms a key part of the paper is rather neat.

So the natural proofs barrier does not seem to apply to monotone circuit complexity.

Norbert Blum has discussed why lower bounds for monotone circuits are essentially different from circuits with negations.  The key observation of Éva Tardos is that a small modification of the Lovász theta function has exponential monotone circuit complexity.

Benjamin Rossman, The Monotone Complexity of k-Clique on Random Graphs, FOCS 2010.
Norbert Blum, On Negations in Boolean Networks, LNCS 5760, 18–29, 2009.
É. Tardos, The Gap Between Monotone and Non-Monotone Circuit Complexity is Exponential, Combinatorica 8, 141–142, 1987.  doi:10.1007/BF02122563


Auction theory - Selling Multiple Items via Social Networks I am trying to understand this paper.

The one thing that I cannot wrap my head around is the payment policy for the Generalized Information Diffusion Mechanism. It is explained on page 72 with examples on page 73.

I understand it as follows:

So for any node $i \in N$, the payment is: $\mathcal{SW}_{-D_{i}} - (\mathcal{SW}_{-C_{i}^{\mathcal{K}}}-v_{i}^{'})$

$D_{i}$ is the union of $i$ and its critical children,

$\mathcal{SW}_{-D_{i}}$ sums over all nodes except the nodes in $D_{i}$.

$\pi_{j}(\theta^{'})$ is 1 if $j$ receives an item, else 0.

Thus, $\mathcal{SW}_{-D_{i}}$ is the sum of the bids of the nodes that receive an item and are not $i$ and not a critical child of $i$.

So for node D (figure 5) I get: $\mathcal{SW}_{-D_{D}} = 19 + 17 + 20 = 56$

$C_{i}^{\mathcal{K}}$ is the set of the top $\mathcal{K}$ ranked critical children of $i$ according to their bid. When the set is smaller that 5, we just take all critical children.

For node D: $\mathcal{SW}_{-C_{i}^{\mathcal{K}}} = 19 + 17 + 20 + 14 = 70$ (all nodes that receive an item that are not D's critical children).

Finally, $v_{i}^{'}$ is just node $i$'s reported valuation (bid).

For node D:  $v_{D}^{'} = 14$.

Thus when I calculate D's payment:
$\mathcal{SW}_{-D_{D}} - (\mathcal{SW}_{-C_{D}^{\mathcal{K}}} - v_{D}^{'}) = 56 - (70 - 14) =  0$.

Of course this is wrong because it always comes out as 0 and in reality D has to pay 10.

Has anyone read this paper already and can help me?

the calculation of $\mathcal{SW}_{-D_i}$ and $\mathcal{SW}_{-C_i^\mathcal{K}}$ is incorrect. There are still $\mathcal{K}$ items to be allocated in both allocations, so for node $D$, the first is 20+19+17+11+10 and the second is 20+19+17+14+11. So D's payment is 10.

p.s. there is a typo in one of the constraints for the two allocations, which is updated in the paper.


Calculating the distance to the kth nearest neighbor for all points in the set For a machine learning application, my group needs to calculate the Euclidean distance to the $k$th nearest neighbor in a set $X$ for each $x \in (X \cup Y) \subset \mathbb R^d$ (for $d$ between 5 and about 100, and $|X| \approx |Y|$ a few hundred up to a few million). We're currently using either the brute-force $O(d \lvert X \rvert \lvert X \cup Y \rvert)$ approach or the obvious one with a kd-tree on $X$, which when $d$ is high and $|X|$ is relatively low doesn't ever win. (Everything is in-memory.)

It seems like there must be a better way than brute-force, though -- at least one that takes advantage of the triangle inequality, or maybe with locality-sensitive hashes. A reasonably tight approximation is also potentially okay.

The research I've been able to find seems to focus on the problem of finding the single nearest neighbor (or one that is approximately the nearest). Does the problem I'm looking for go by some other name, or is there a connection to a related problem that I haven't thought of?

Here is a simple trick that might be useful. Consider a random sample that picks every point with probability 1/k. It is easy to verify that with good probability exactly one of your k nearest neighbor would be in the sample. Compute the nearest-neighbor in the sample. Repeat this O( k log n) times. With high probability the k nearest points in the $O(k \log n)$ points computed are the k nearest neighbors to your query. Thus, finding the k nearest neighbor, is equivalent to doing $O( k \log n)$ nearest neighbor queries.

In short, give me a fast data-structure for answering nearest neighbor queries, and I would be happy to give you a fast data-structure of k-nearest neighbor.


Number of reachable vertices in DAG for every vertex Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every vertex and this will take $O(|V||E|)$ time. Is there a better way to solve this problem?

The best exact algorithm will run in time O( min{mn, n^2.38} ) by using fast binary matrix multiplication. However, there is a random algorithm, which runs in time O(m+n) and estimates the number of reachable nodes from each node with a small relative error, please refer to paper "Size-Estimation Framework with Applications to Transitive Closure and Reachability" by Edith Cohen.


Temporally Flat One-Way Quantum Computing I am a physicist at heart, and so I think One-Way Quantum Computing is brilliant. In particular, Graph State Measurement-based Quantum Computing (MBQC) has been a really nice development in Quantum Computing research as originated by Raussendorf & Briegel. One just needs to prepare a multi-partite entangled state as described by a graph, and then perform sequential measurements on each node or qubit (adaptive measurements for deterministic computations).

Another excellent aspect of this approach is that Clifford circuits can be implemented in a single-round of measurements as shown by Raussendorf, Browne and Briegel. These circuits can be classically simulated (efficiently) as shown by Gottesman and Knill so it is an interesting connection between classical simulation and temporal resources.

However, not all temporally flat Graph State MBQC circuits (consisting of one round of measurements) are believed to be simulatable classically. For example, families of circuits in the quantum circuit model consisting of commuting gates called IQP circuits as introduced by Shepherd and Bremner can be implemented in single time-step in MBQC. These IQP circuits are believed not to be classically simulatable (in computational complexity terms, it would lead to a collapse of the polynomial hierarchy).

See also a nice description of a class of circuits implemented in one time-step here. Given that commuting/diagonal unitaries can have some interesting behaviour but non-commuting circuits be classically simulatable. It would be interesting if there were non-commuting circuits that can be implemented but not yet shown to be classically simulatable.

Anyway, my question is:

  Are there other interesting circuits that can be implemented in a single time-step in MBQC?

Though I would prefer relations to computational complexity or classical simulation, I would find anything interesting.

Edit: After Joe's excellent answer below, I should clarify a couple of things. As Joe said (and somewhat embarrassingly I have said in one of my own papers), single measurement-round MBQC circuits are in IQP. To be more precise, I am interested in interesting circuits in the problems in IQP that can be implemented in one round of measurements in MBQC. Clifford circuits are an interesting example. If there any other examples which are classically simulatable that would be extremely interesting. Since simulating IQP circuits is believed to be unlikely classically, it would be interesting to find instances of circuits that are.

It doesn't make sense to me to ask about non-commuting operators being implemented in a single time step (though constant depth certainly makes sense). However, you can implement non-commuting gates on the logical subspace of an MBQC which are implemented using commuting measurements on the resource state, though the implemented gates are not deterministic.

Actually, I believe you are viewing IQP more narrowly than you probably should. The answer to your question is that any MBQC which can be implemented in a single measurement layer in MBQC is contained in IQP. This is simply because rather than expressing the result in terms of the logical Hilbert space, you can express it as a series of commuting operations on the physical qubits. Shepherd and Bremner actually deal with this in their paper (in section 5.2 where such operations are called graph-programs).


Extending simple types to allow `fix` I'm reading some lecture notes saying that “fix cannot be defined in the simply typed lambda-calculus” and that “no expression that can lead to non-terminating computations can be typed using only simple types.”

I'm sure more of this will be covered later, but it left me curious: What is needed in a type system to support defining fix? I.e., how can I simply type (in Haskell): fix f = let x = f x in x and get the type (a → a) → a? Also, is this related to needing to write let rec in ML/F#?

If you want to include a fixpoint combinator in the language, you don't need to change anything to the syntax of types or the rules to type existing expressions. All it takes is adding one constant, a rule to type it and a rule to reduce expressions containing it:
$$
  \dfrac{}{\mathsf{fix} : (\tau \rightarrow \tau) \rightarrow \tau} \qquad
  \mathsf{fix} \, f \to f (\mathsf{fix} f)
$$

If you want to be able to define a fixpoint combinator in terms of the core lambda-calculus syntax, that's a different matter. There are a lot of type systems, some of them allowing arbitrary recursion, some of them not. There isn't a simple way of telling by looking at a type system whether it allows arbitrary recursion. For example, some very sophisticated type systems (e.g. the calculus of inductive constructions which Coq is based on) include a $\mathsf{fix}$ combinator with a typing rule that limits the types at which it can be used in such a way that only terminating functions can be defined. Here are a few ways arbitrary recursion can be added to a typed lambda calculus:

Intersection types: they allow any lambda-term to be typed, in a way that you can read from the type whether the term is strongly normalizing and whether it has a normal form. See Does there exist a Turing complete typed lambda calculus?
If you add (sufficient) recursion to the type language, this adds recursion to the term language as well. In ML, this leads to a recursive function definition without using let rec, by relying instead on a type definition of the form type t = Constructor of (t -> …).
The typing rules for ML-like languages are based on defining a typing rule for let rec that allows the variable to be used in its own definition. This makes let rec not syntactic sugar for a lambda-expression, unlike plain let.

The need to write let rec in ML is unrelated, or at least only loosely related, to the type theory. Here are a few reasons to annotate recursive definitions differently:

ML started out as the metalanguage for a theorem prover, and the designers may have felt that it was best programming practice to explicitly mention the use of unbounded recursion (which has the potential to make the proof building process not terminate).
Having the rec indication can make compiler design and type theory design slightly simpler, because there are cases where let can have a more generalizable type than let rec, and different kinds of terms that can or cannot be defined recursively.
There are cases where it's useful in programs to have a non-recursive let, which defines a new variable of the same name as an existing one: when an object undergoes a series of transformation, but they're intuitively different stages of the same object.

let widget = read_widget_source () in
let widget = parse_widget widget in
let widget = compile_widget widget in
execute_widget widget


Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses? Let $\phi$ be negative monotone 2-CNF on $n$ variables and $n^{3/2}$
clauses.
What is the complexity of finding satisfying assignment with maximum
number of ones $k$?
Alternatively let $G$ be a graph of order $n$ and $n^{3/2}$
edges. $G$ is dense.
What is the complexity of finding $k$-independent set of $G$?
Each variables $x_i$ is in about $\sqrt{n}$ clauses (alternatively
the degrees of vertices of $G$ are about $\sqrt{n}$).
Can we get fixed parameter tractable algorithm with parameter $k$?
Can we increase the exponent $3/2$ to get polynomial solutions?
If necessary assume $n$ is square to get rid of the fractions.
Added later
Third question:
Let $\frac12 \le C < n$ and $d=Cn$. Let $G$ be $d$-regular graph.
It has $C n^2/2$ edges and each vertex has $d$ neighbors.
In CNF notation there are $C n^2/2$ clauses and each variable is in $d$
clauses.

Can we find MIS in $G$ in subexponential or polynomial time?

More details about this construction are on Mathoverlfow

In both questions the answer is the same for any exponent $1 < \alpha < 2$.
For the first question, we can use a degeneracy based algorithm to find an independent set of size $\Omega(\frac{n}{n^{\alpha-1}}) = \Omega(n^{2-\alpha})$ in polynomial time. Therefore we get an FPT algorithm for every constant $\alpha$ simply by outputting YES if $k < c n^{2-\alpha}$ for some constant $c$, and otherwise solving the problem with bruteforce in $2^n = 2^{O(k^{1/(2-\alpha)})}$ time.
For the second question, we can prove that the problem is NP-hard for all $1 < \alpha < 2$ by reducing from maximum independent set problem in 3-regular graphs, which is NP-hard [1].
For some constant $\beta$ we make $n^\beta$ copies of each vertex, making the set of copies a clique for each vertex. Now the new graph has exactly the same maximum independent set as the old graph. It is $4 n^\beta - 1$ regular and has $n^{\beta+1}$ vertices, so we can choose $\beta \approx \frac{\alpha-1}{2-\alpha}$ to make it work for any $1 < \alpha < 2$.
[1] Garey, Michael R., David S. Johnson, and Larry Stockmeyer. "Some simplified NP-complete problems." STOC 1974.


Planar Exact Cover by even-size sets Major edit on June 6, 2019: Replaced the target problem with a simpler (but equivalent) one.

Is the following problem NP-complete?

  Planar Exact Cover by even-size sets

  Input: A set $U$, a subset family $\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$ with the two restrictions below.
  Question: Is there $\mathcal{F}' \subseteq \mathcal{F}$ such that each element of $U$ is included in exactly one set in $\mathcal{F}'$?

  Restriction 1: The bipartite graph $B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$ is planar.
  Restriction 2: $|F_{i}|$ is even for every $i$.

If we forget the 1st restriction, then the problem is NP-complete because of 4-dimensional matching.
If we replace the 2nd restriction with "$|F_{i}| = 3$ for every $i$", then the problem is NP-complete as Planar Exact Cover by 3-sets is NP-complete (1).

Martin E. Dyer, Alan M. Frieze.
Planar 3DM is NP-Complete. Journal of Algorithms 7(2) 174-184 (1986).
doi:10.1016/0196-6774(86)90002-7

Motivation: Such a restriction would be useful when subset gadgets can have only an even number of connections to the rest.

The old version of the problem is as follows:

  Planar Exact Cover by 2- and 4-sets (with at most three occurrences)

  Input: A set $U$, a subset family $\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$ with all three restrictions below.
  Question: Is there $\mathcal{F}' \subseteq \mathcal{F}$ such that each element of $U$ is included in exactly one set in $\mathcal{F}'$?

  Restriction 1: The bipartite graph $B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$ is planar.
  Old restriction 2: Each element of $U$ appears in at most three sets in $\mathcal{F}$.
  Old restriction 3: $|F_{i}| \in \{2,4\}$ for every $i$.

The new problem can be reduced to the old one as follows.

Reducing the number of occurrences:
Assume that there is an element $u$ that appears in sets $F_{1}, F_{2}, \dots, F_{k}$ with $k \ge 4$.
We replace $u$ with three new element $x, u_{1}, u_{2}$ and then replace $F_{1}, \dots, F_{k}$ with $D_{1} = \{u_{1}, x\}$, $D_{2} = \{x, u_{2}\}$, and $F_{i}'$ for $1 \le i \le k$ such that
$F_{i}' = F_{i} \cup \{u_{1}\} \setminus \{u\}$ for $1 \le i \le 2$ and
$F_{i}' = F_{i} \cup \{u_{2}\} \setminus \{u\}$ for $3 \le i \le k$.
We can see that $u_{2}$ appears in $k-1$ sets.

Reducing set size:
Assume that there is a set $F_{i} = \{u_{1}, u_{2}, \dots, u_{2k}\}$ with $k \ge 3$.
We add two new elements $x, y$ to $U$ and then replace $F_{i}$ with three sets
$F_{i}^{(1)} = \{u_{1}, u_{2}, u_{3}\} \cup \{x\}$,
$F_{i}^{(2)} = \{x,y\}$, and
$F_{i}^{(3)} = \{u_{4}, \dots, u_{2k}\} \cup \{y\}$.
Observe that $|F_{i}^{(3)}| = 2k-2$.

Correctness: The reductions preserve the answer and the planarity. See the figure below.

The problem seems to be NP-complete. My reduction is from Planar 1-in-3-SAT, just like in their paper. For each variable, take $2k$ vertices. Each of these is covered by two 4-sets and each 4-set covers two consecutive vertices. Thus, we need to take every second of the 4-sets for each variable, this corresponds to TRUE/FALSE. The other two vertices of the 4-sets are from the clauses. (If the number of negated and unnegated occurrences of some variable differs, then convert some of the 4-sets into 2-sets.) Each clause has 4 vertices; one in the center and the other three in a triangle. Any two vertices of the triangle are contained in a 4-set that belongs to its appropriate literal. The central vertex is in three 2-sets, one for each vertex of the triangle. Not sure how clear this was, so I've made a sketch:

https://photos.app.goo.gl/TMc49pfeT6RZA9Vb8

It is easy to see that this hypergraph is indeed planar.
The proof of the reduction is also quite straight-forward.
Let me know if you have any questions.


Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation? Let's say I had an optimization problem

$$ \min_{x \in D} f(x) $$

Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.

Imagine I had a polynomial time algorithm that - given $f$ - could provide me with an interval for the optimal objective function value $f^*$ using finite numbers $LBD$ and $UBD$ where $LBD < f^* \leq UBD$.

Could I use this to show that the $\epsilon$-evaluation problem can be solved in polynomial time? Here the $\epsilon$-evaluation problem is a problem that for any $\epsilon > 0$ finds a real number $z$ such that $f^* \leq z \leq f^* + \epsilon$.

For the purposes of this problem, we can assume that I have a computer that can store real numbers and perform exact elementary operations with them.

The framework of parametric search allows you to do this in many cases. While it was first developed by Meggido for parallel implementation, the idea is more general. Roughly speaking, you start with an oracle $g(x)$ that tells you, given a point $x$, to which side (left or right) the optimum-achieving $x^*$ lies. The idea is to "pretend" to simulate the cost function on the optimal solution. At some point, you're stuck because you don't know which path of a branch to take (since you don't know $x^*$). You identify the breakpoints of this branch, and then using $g$ decide which ones to explore further.

I'm handwaving a lot, because parametric search is quite complicated. This survey talks about ways of making it practical, and also has a decent explanation of the basic idea. This older survey gives a number of examples of parametric search.


Smallest known formula for the determinant The smallest known formula for the determinant has size $n^{\mathcal O(\log n)}$ according to the folklore (or to Ran Raz in its paper Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size).

Do you have any reference for this? In particular, what is this formula?

One way is described in Berkowitz, On computing the determinant in small parallel time using a small number of processors (see also Soltys, Berkowitz's algorithm and clow sequences). Another way is described in Hrubeš and Tzameret, Short proofs for the determinant identities.


The random densification technique-JL lemma In Ailon's paper (p.3): How $1/(20nd)$ is obtained?

It's not "obtained", but rather the bound the authors want on $\mathrm{Prob}[|u_1|\ge s]$. The Chernoff inequality says how large $s$ needs to be in order to guarantee the desired upper bound. As they assume $d \le n$, it suffices for $s$ to satisfy $s^2 \cdot d/2≥\ln(20n^2)$, which leads to $s=c\cdot d^{-1/2} \sqrt{\log n}$ for some appropriately chosen constant c.


Time complexity for multiplying two lower triangular matrices I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
 A & 0\\
 C & D
\end{bmatrix}
\begin{bmatrix}
 P & 0\\
 R & S
\end{bmatrix}
=
\begin{bmatrix}
 AP & 0\\
 CP + DR & DS
\end{bmatrix}
$$
Initially, I thought the above block decomposition yields an $O(n^2)$ time algorithm since there are 4 recursive instances of multiplication of $n/2 \times n/2$ matrices. However, I quickly realized that we cannot recurse since the lower left blocks are not triangular ($C$ and $R$ above).

With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}^{th}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}^{th}$ block of $3n \times 3n$ matrix $N$ with rest of the blocks all zero. Both M and N are lower triangular. An asymptotically faster algorithm for $M.N$ would then yield faster algorithm for $A.B$ too.

$$
\begin{bmatrix}
0 & 0 & 0\\
0 & 0 & 0\\
0 & A & 0
\end{bmatrix}
\begin{bmatrix}
0 & 0 & 0\\
B & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
=
\begin{bmatrix}
0 & 0 & 0\\
0 & 0 & 0\\
AB & 0 & 0
\end{bmatrix}
$$

It's amazing how this argument does not manifest when trying to embed $A$ and $B$ in $2n \times 2n$ matrices!


Early references for discrete optimization (Apologies if this is misplaced or too broad.  I'm open to suggestions on how to reformulate it.)

I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete optimization algorithms in general.  Ford-Fulkerson is my straw-man of a starting point.  What were the significant advances prior to that?  How far back can we go while still being able to make a reasonable argument that somebody was working on max-flow?  How about graph algorithms?  How about discrete optimization in general?

I'd also be happy to get references to places where this is discussed.

Usually, Schrijver provides a good source for history. You can look at the following books and an article.

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003.
Alexander Schrijver. Theory of Linear and Integer Programming. Wiley 1998.
Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming 91(3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
Alexander Schrijver. On the history of combinatorial optimization (till 1960).  Handbook of Discrete Optimization, Elsevier, 2005.  http://homepages.cwi.nl/~lex/files/histco.pdf


Finding out a set by intersection comparison The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related.

The general setting is the following. We are given $F$, a family of $t$-subsets of $\{1, 2, ..., n\}$, for some parameter $t$ (I am most interested in the case where $t=\lfloor n/2\rfloor$). There is an adversary who picks one set in $F$, denoted by $S$. Our job is to find what $S$ is. To do this, we are allowed to send any two sets in $F$ to the adversary, say $A$ and $B$ and the adversary will output $A$ if $|A\cap S|\geq |B\cap S|$ and $B$ if $|B\cap S|\geq |A\cap S|$. Note that if $|A\cap S|=|B\cap S|$ then the adversary can output either $A$ or $B$.

This problem can be solved trivially if we do not care how many queries we can ask since if we compare all pairs of sets, $S$ will be the only set that is always returned back from the adversary when we send a query $(S, B)$, for any $B\neq S$. However, our goal is to minimize the number of queries.

My goal is to show either that this problem can be solved using $O(poly(n))$ queries or that super-polynomial number of queries are required. I'm particularly interested in the case where $F$ is the set of all $\lfloor n/2\rfloor$-subsets of $\{1, ..., n\}$.

Any pointers to anything related would be appreciated.

This is a variation of the famous puzzle of finding a counterfeit coin by using the balance.  But before proceeding to that, first let’s solve the question, because the technique in solving it is also useful to see the connection to the counterfeit coin problem.

First, suppose that the query sets A and B do not have to be from the family F.  Then you can find the set S by at most $\binom{n}{2}=O(n^2)$ queries as follows.  Make $\binom{n}{2}$ queries ({a}, {b}) for 1≤a<b≤n.  Note that every element i∈{1,…,n} is used in n−1 queries.  If an element i belongs to S, then the set {i} is answered at least when the opponent does not belong to S, and therefore the set {i} is answered at least n−t times.  If an element i does not belong to S, then the set {i} cannot be answered if the opponent belongs to S, and therefore the set {i} is answered at most n−t−1 times.  Therefore, counting how many times each set is answered, we can determine the whole set S.

This requires query sets not from the family F, which is not allowed in the problem.  But we can work around this by adding the same t−1 elements to both sides.  For example, instead of making the query ({1}, {2}), we can make the query ({1,3,4,…,t+1}, {2,3,4,…,t+1}).  Therefore, the problem can be solved by O(n2) queries.

Now fun part begins.  Consider n coins labeled 1,…,n, and t of them are counterfeits and slightly heavier than the real coins.  All the counterfeit coins have the same weights.  You have to find the set S of the labels of the t counterfeit coins by using a balance only poly(n) times.  Every time you use a balance, you can put at most min{t, n−t} coins to each side of the balance.  The balance is slightly inaccurate in the sense that if the two sides have the same weight, either side can go down (adversarially).  As I hope that you can see by now, this is exactly the same problem as the question.

Edit: Revision 4 and earlier had one error or another (oops) in the precise connection to the counterfeit coin puzzle.


References on implementing universe levels over MLTT? I've followed the tutorial on Checking Dependent Types with Normalization by Evaluation: A Tutorial by David Christiansen, where we implement a small dependently typed kernel with the axiom Univ : Univ. The "Projects" section of the tutorial provides a project on replacing this with a universe hieararchy:

7.Replace U with an infinite number of universes and a cumulativity relation. To do this, type equality checks should be replaced by a subsumption check, where each type constructor has variance rules similar to other systems with subtyping.

I've looked around a little, and it seems like both Agda and Lean implement a universe hierarchy using levels, which have the following operations:
lzero : Level
lsuc  : (n : Level) → Level
_⊔_   : (n m : Level) → Level

Who came up with this encoding of universes based on levels originally? Why not simply reuse the natural numbers for universe levels? There must be some reason to introduce a new Level type, instead of reusing the already present Nat?
How does one type-check and perform normalization-by-evaluation on universe levels?
What are the subtleties one should be aware of when implementing universes?
How should I test that my universe hierarchy implementation is correct? Are there short, well-known theorems that depend on a universe hierarchy, which I should try to encode?

I am hesitant to try my hand at naively implementing universes based on my intuition, because all the references I have read (ATAPL, MiniTT, and the above tutorial) all stop short of explaining universe levels. I get the feeling that there is non-triviality which I am unable to see, and thus would like to know how to (a) implement, and (b) test universes, on top of the kernel I now have

IMHO universe hierarchy is particularly complicated to implement while the benefit is very small. It complicates programming in the language and the implementation of the language. The only benefit is to ensure the logical consistency. I guess that's why everybody is not writing about it.
Here are some answers to your questions. I don't know much type theory -- I can't answer everything, sorry.

Why not simply reuse the natural numbers for universe levels?

Nat has an eliminator. You shouldn't be able to pattern match on a level. In fact, introducing Level as a type (not to mention an inductive type) already causes problem. Imagine the following function:
Ty : (ell : Level) -> Set (lsuc ell)
Ty l = Set l

What is the universe level of the type of Ty? Also, what's the universe level of the type of Level? If we don't have a type for levels (but instead built it into the syntax, to eliminate these cases) we could avoid these problems (but then you become less flexible ofc).

How does one type-check and perform normalization-by-evaluation on universe levels?

I guess just like Nat. The relevant operations are strict subset of Nat.

What are the subtleties one should be aware of when implementing universes?

Level is actually not a type. I personally don't like Agda's approach (but prefer Lean's, Arend's approach, where Level is not a type).
You need to compare levels for equality and less than relation. So, your compiler should know max(x, y) >= x, max(x, y, z) >= max(x, y), etc.
There are many styles of universe hierarchy. You can peek cumulativity, impredicativity (be careful, it may lead to inconsistency), typical ambiguity, etc.
You may want to implement a solver for level equations (if you have implicit inference mechanism), but that's very complicated.

How should I test that my universe hierarchy implementation is correct?

Try to refute the construction of the Girard paradox. It's everywhere on the internet. Also, there is another example which I believe that it won't work with universe levels.
I'm also implementing universe polymorphism on a little programming language, but the code is kinda messy.


Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP? An answer to the traveling salesman (and similar) problems can be easily verified on light lambda-calculi. Also, if I understand correctly, the light lambda-calculi can compute every polinomial-time computable function. That way, if one can prove that the traveling salesman problem can't be encoded on the light lambda-calculi, that would also prove the problem can't be solved in poly-time, which would also prove P!=NP. Is that correct, or am I confusing some concepts?

Yes, in the same sense that if you prove that a specific NP-complete problem can't be reduced to a specific P-hard problem, then you also prove P!=NP. The only issue is that the reduction for which P-hardness hold must be "compatible" with the allowed encodings.

From the information you give in the question, I conclude that LAL is P-time hard. The article Light types for polynomial time computation in lambda calculus by R. Baillot and K. Terui confirms this, by showing that DLAL (dual light affine logic) is a P-complete subset of LAL.

My own experience is that many P-complete problems look attractive and natural. My favorites are linear programming and Horn-satisfiability, but I guess that DLAL (or LAL) look even more attractive to you. But even so they are attractive, using them for resolving N!=NP is probably futile. More than one reduction of specific NP-complete problems to linear programming has been published, but the reductions turned out to exponentially increase the size of the problem.


What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why?

Details:

http://en.wikipedia.org/wiki/Powerset_construction states that the worst-case runtime complexity is $\Theta(2^n)$, where $n$ is the number of states of the NFA.

I do not understand how $\Theta(2^n)$ is sufficient: You need up to $2^n$ steps to create the DFA, each creating a new state in the DFA. For each step, you need more time than $\Theta(1)$: you have to consider up to $n$ many states of the NFA (since the DFA-state is a set of up to $n$ states of the NFA) and for each such state up to $b$ (=maximal branching) many outgoing transitions. Thus I would have thought the worst-case time complexity would be $\Theta(2^n \times n \times b)$.

Is there some optimization possible to get to $\Theta(2^n)$? (Above, I have already used the optimization to look in each step at every state of the NFA at most once, instead of iterating through the set of NFA states and for each one doing an epsilon closure with worst case runtime complexity $O(n)$).

At first glance this looks like a mistake in Wikipedia (it wouldn't be the first one), but I think the time bound there is actually correct, with two assumptions and one small idea.

The assumption is: the alphabet size is constant, so you can ignore the $b$ factor in the runtime and output size. The second assumption is: you can represent the output DFA as a graph in memory, in a conventional adjacency list data structure (or whatever). So in particular to be able to store an edge from one state to another, you need memory cells that can store up to $n$ bits of information per cell, and (in the standard RAM model) this also means constant-time bitwise operations on these cells.

The idea is: each nonempty set of states of the NFA (corresponding to a single state of the DFA) can be formed by adding one element to a smaller set. So, to compute the transitions for a state $S$: find an element $s$ and a state $R$ such that $S=R\cup\{s\}$. Then, for each input alphabet symbol, compute the transition from $S$ as the bitwise Boolean or of the transition from $R$ (previously computed in the same construction) and the transition from $s$ (in the input NFA). Doing this takes $O(b)$ bitwise Boolean operations per state for a total time of $O(1)$ per state.

In practice, you'd probably rather use the version of the construction that only constructs reachable states, rather than all sets. But when you do it that way you can't be guaranteed to find an element whose removal leaves another reachable state, so your $n$ extra factor in the runtime presumably still applies to this version.