texts: Is there a set theoretic way to look at SQL?

texts:
I have been learning about SQL and at times it feels like set theory.  A statement like SELECT * FROM myTable is like a set $\{ x: x \in \text{myTable} \}$.

A table could be defined as any subset of the Cartesian product.  We could define a table called zipcodes with a schema city STRING(30), state CHAR(2),  zip INTEGER(5)  then in set theory we could define the zipcodes stable as:
$$ zicodes \subseteq \text{cities} \times \text{states} \times \text{zips} \simeq \{a, \dots, Z\}^{30} \times \{a, \dots, Z\} \times \{1, \dots, 10^5\}$$
So any table is a subset of a cartesian product.

My theory has limitations, since you can't store all of $\mathbb{R}$ as a SQL database (e.g. by cantor diagonalization) since $|\mathbb{R}| > |\mathbb{Z}|$ in cardinality.

In any case, do any theories of SQL exist that compare it to set theory?


texts: Art gallery variants with pairwise visibility?

texts:
The traditional art gallery problem sets up a region and guards with some notion of visibility, and asks for the minimum number of guards that need to be placed to see the entire region.

Has anyone ever looked at art gallery variants where the visibility region is instead defined by a pair of guards. For example, one formulation might be that a point is covered if there's a pair of guards whose minimum bounding disk covers it ?


texts: I am doing a little literature review and I was trying to know if, for a directed acyclic graph, the minimum k-path cover problem is solvable in polynomial time. A k-path cover is a set of paths with length at most k such that every vertex  must belong at least to a path (can belong to more than one). The minimum k-path cover problem asks for the minimum size of a k-path cover.


texts:
It was an open question whether multiple knapsack is fpt wrt standard
parameter. Since at SODA 2009 Jansen has presented an EPTAS for
multiple knapsack and an EPTAS implies the existense of an fpt algoritm
[Cesati and Trevisan 1997] this problem should be solved? I ask, since
the EPTAS has a "parameterized" running time.


texts: Drawing graphs with few "sharp" vertices?

texts:
For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other words, if there exists a line passing through that vertex in the embedding such that all the edges incident on that vertex lie on one side of the line, then the vertex is "sharp" otherwise it's not. Also, let us worry only about vertices with degree at least 3.

I want to draw planar graphs with few sharp vertices. Has anyone studied such drawings before?

In particular, I want to draw planar graphs with max degree 3 such that the number of sharp vertices of degree 3 in the embedding is $O(\log n)$ and the coordinates of the vertices can be written down with a polynomial number of bits.

Here's what I can find after spending some time on Google Scholar:

My measure of sharpness of a vertex is related to an already studied concept called the Angular Resolution. From Wikipedia:

  The angular resolution of a drawing of a graph refers to the sharpest angle formed by any two edges that meet at a common vertex of the drawing.

Thus a planar drawing with angular resolution $\pi/2$ around degree 3 vertices will be good for my purpose.

For a vertex with degree $d$ in the drawing, the angular resolution around it can be at most $2\pi/d$.

The question of whether this is tight has been studied in the past, but I can only find asymptotic results. For example, Malitz and Papakostas prove that any planar graph with maximum degree $d$ can be drawn with an angular resolution of $\alpha^d$. But this result doesn't give good bounds for the case when $d=3$.


texts: Easier and Harder instances of NP-complete problems?

texts:
Following previous questions here and here around $NP$-complete problems (and P vs NP).

Are there "easier" or "harder" (sets of) instances of an $NP$-complete problem?

If yes (which i assume), how a polynomial-time mapping between $NP$-complete problems maps between easier or harder (sets of) instances?

A conjecture  (related to directions of previous questions) is that there should be considerable mapping betwen "easier" to "harder" and "harder" to "easier" (if i may, with probability almost 1).

PS. This in effect tries to study (a little more in depth) the role of polynomial-time mappings used in $NP$-complete reductions.

Thankx


texts:
The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an unsatisfiable formula - then NP=RP. This theorem is proved by showing that UNIQUE-SAT is NP-hard under randomized reductions.

Subject to plausible derandomization conjectures, the Theorem can be strengthened to "an efficient solution to UNIQUE-SAT implies NP = P".

My first instinct was to think that implied there exists a deterministic reduction from 3SAT to UNIQUE-SAT, but it's not clear to me how this particular reduction can be derandomized.

My question is: what is believed or known about "derandomizing reductions"? Is it/should it be possible? What about in the case of V-V?

Since UNIQUE-SAT is complete for PromiseNP under randomized reductions, can we use a derandomization tool to show that "a deterministic polynomial time solution to UNIQUE-SAT implies that PromiseNP = PromiseP?


texts: Gentle introduction to the algorithmic aspects of tree-depth

texts:
Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and lecture notes that give (even very gentle) introductions to the algorithmic aspects of treewidth (see e.g. the Downey & Fellows book). Typically, these resources explain how some NP-hard problem (e.g. independent set) is solved in polynomial time through dynamic programming on a tree decomposition.

However, it is sometimes the case a graph problem remains NP-complete for both bounded treewidth and bounded pathwidth graphs. But such hardness results don't imply hardness for bounded tree-depth, which informally measures the closeness to a star.

It seems fair to say tree-depth is not as widely known as treewidth. For someone wanting to learn more about algorithms parameterizing by tree-depth, are there (similarly to treewidth) some nice resources available for learning how such algorithms perhaps typically work?


texts: What do we know about the phase transition of #P-Complete problems?

texts:
What is known about the phase transition in #P-Complete problems? Specifically, does there exists a different phase transition for #DNF-k-SAT and #CNF-k-SAT? Update:
As we know, there is a phase transition in Random k-SAT where solving the problem goes from being easy to hard and back to easy again. I would like to know if there is such a phenomenon for #P-Complete problems as well. More importantly, if there exists a phase transition, is it same for #CNF-k-SAT and #DNF-k-SAT? I am thinking that there is some type of phase transition for #CNF-k-SAT. On the other hand, I do not think there is phase transition for #DNF-k-SAT and the problem gets harder as we add more clauses....


texts: Probability of generating a desired permutation by random swaps

texts:
I'm interested in the following problem.  We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$.  Then, starting with the list $L=(1,2,\ldots,n)$ (i.e., the identity permutation), at each time step $t\in [m]$ we swap the $i_t^{th}$ element in $L$ with the $(i_t+1)^{st}$ element, with independent probability $1/2$.  Let $p$ be the probability that $\sigma$ is produced as output.

I'd like to know (any of) the following:

Is deciding whether $p>0$ an $NP$-complete problem?
Is calculating $p$ exactly $\#P$-complete?
What can we say about approximating $p$ to within a multiplicative constant?  Is there a PTAS for this?

The variant where the swaps don't need to be of adjacent elements is also of interest.

Note that it's not hard to reduce this problem to edge-disjoint paths (or to integer-valued multicommodity flow); what I don't know is a reduction in the other direction.

Update: OK, checking Garey & Johnson, their problem [MS6] ("Permutation Generation") is as follows.  Given as input a target permutation $\sigma\in S_n$, together with subsets $S_1,\ldots,S_m\in [n]$, decide whether $\sigma$ is expressible as a product $\tau_1 \cdots \tau_m$, where each $\tau_i$ acts trivially on all indices not in $S_i$.  Garey, Johnson, Miller, and Papadimitriou (behind a paywall, unfortunately) prove that this problem is $NP$-hard.

If the swaps don't need to be adjacent, then I believe this implies that deciding whether $p>0$ is also $NP$-hard.  The reduction is simply this: for each $S_1,S_2,\ldots$ in order, we'll offer a set of "candidate swaps" that corresponds to a complete sorting network on $S_i$ (i.e., capable of permuting $S_i$ arbitrarily, while acting trivially on everything else).  Then $\sigma$ will be expressible as $\tau_1 \cdots \tau_m$, if and only if it's reachable as a product of these swaps.

This still leaves open the "original" version (where the swaps are of adjacent elements only).  For the counting version (with arbitrary swaps), it of course strongly suggests that the problem should be $\#P$-complete.  In any case, it rules out a PTAS unless $P=NP$.


texts: Can a probabilistic Turing machine solve the halting problem?

texts:
A computer given an infinite stream of truly random bits is more powerful than a computer without one.  The question is: is it powerful enough to solve the halting problem?

That is, can a probabilistic computer determine whether or not a deterministic program halts?

Example of a probabilistic computer doing something a deterministic one can't: Consider a small program (less than a kilobyte in length) that outputs a string with Kolmogorov complexity greater than a gigabyte.  The Kolmogorov complexity of a string is the length of the shortest deterministic program producing that string.  Thus, by definition, a deterministic program cannot produce a string whose complexity is greater than its own length.  However, if given an infinite stream of truly random bits, a small program is capable of achieving the task with 99.99999...% success by simply echoing out, say, 10 billion random bits and hoping the Kolmogorov complexity of those bits is high enough.  Hence, producing a string of superior Kolmogorov complexity is within the possibility horizon of the probabilistic program, but not possible at all for the deterministic program.

That said, I'm wondering if it is possible to use truly random bits to hacksaw at the halting problem.  For instance, an algorithm might randomly generate theorems and prove/disprove/discard them until it knows enough to prove/disprove that a given deterministic program halts.


texts: Are there any intersections between Theory A and Theory B?

texts:
In the following two questions Origins and applications of Theory A vs Theory B? and Solid applications of category theory in TCS?, many people shared their knowledge and opinions about the division of those two areas in theoretical CS.

I am a student in mathematics with experience in both graph theory and category theory, crucial mathematical knowledge for theory A and B, respectively, and I am seeking to learn more and probably even do some serious research in theoretical CS. I am interested in whether there are any intersections between theory A and B, and if so, are there any people who have done some work in the intersections or at least are there any references in this topic?


texts: How can we derive this lower bound of a special cut in a graph?

texts:
I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in this situation on page 9.

If you have a partition $C\cup (V\setminus C)$ with $s\in C$ and $t\in V\setminus C$, the $k$-uniform cut capacity $c_k(C)$ is the maximal volume of a packing of $k$ identically sized packages into the bins with size corresponding to the edges from $C$ to $V\setminus C$. The minimum $k$-uniform $s$-$t$ cut, $c_k(s, t)$, is defined by $c_k(s,t):=\min\{c_k(C)|s\in C\subset V\setminus \{t\}\}$

My question is then about Theorem 7. How can we derive this lower bound of $k$ for a standard minimum $s$-$t$ cut in the graph $G'$?


texts: Separation Oracle for Inverse Bipartite Matching Polytope

texts:
The $N$x$N$ bipartite matching problem can be written as finding a configuration of variables ${\mathbf y}^* = \{y^*_1, \ldots, y^*_N\}$, $y_i \in \{1, \ldots, N\}$ such that

$${\mathbf y}^* = \arg\min_{{\mathbf y}} \;\; E({\mathbf y}; {\mathbf w}),$$

where $y^*_i$ is the index of the point in partite set $B$ that the $i$th point in partite set $A$ is matched to in the optimal matching$^1$, and ${\mathbf w}$ is a $N$x$N$ matrix of matching costs, giving the cost of matching $A_i$ to $B_j$.  The 1-to-1 constraints are implicit in $E$.  For purposes here, further restrict ${\mathbf w}$ to lie inside a unit hypercube ${\mathbf w} \in [0,1]^{N\cdot N}$.

I'm interested in what I'm calling the inverse bipartite matching polytope, $R({\mathbf y})$, which contains all ${\mathbf w}$ that lead to ${\mathbf y}$ as a minimum cost matching, ie.,
$$R({\mathbf y}) = \{{\mathbf w} \mid \arg\min_{{\mathbf y'}} \;\; E({\mathbf y'}; {\mathbf w}) = {\mathbf y} \}.$$

It is straightforward to show that this is a convex polytope, but I don't know of any way to define it without using an exponential number of linear inequalities.  So I'm interested in a separation oracle for $R({\mathbf y})$: given a $\hat {\mathbf w}$ that lies outside $R({\mathbf y})$, I'd like a linear constraint that separates $\hat {\mathbf w}$ from $R({\mathbf y})$, ideally cutting away as much space outside of $R({\mathbf y})$ as possible.  (So while one simple solution is to find the optimal matching under $\hat {\mathbf w}$,
$\hat {\mathbf y} = \arg\min_{{\mathbf y}} \;\; E({\mathbf y}; \hat {\mathbf w})$,
then to enforce that the cost of ${\mathbf y}$ is less than the cost of $\hat {\mathbf y}$, this is unappealing because it seems to be a pretty shallow cut).

Is this a problem that has been studied, or is it closely related to a problem that has been studied?  I'd appreciate any references or terms to narrow down my search.

[1] I'm assuming throughout that the minimum cost matching is unique.


texts:
I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must admit I am getting somewhat out of my depth.

From what I have read, a randomness extractor is a function:

$E:\{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$

such that for every distribution $X$ on $\{0,1\}^n$ with minimum entropy $k$ and $Y$ (a "truly random seed") uniformly distributed on $\{0,1\}^d$, we have $E(X,Y)$ is $\epsilon$-close to a uniform distribution on $\{0,1\}^m$.

I understand the motivation to produce truly random bits, but do not understand how the concept of an extractor is useful if it already requires a truly random seed. Surely if we can already produce a truly random seed we have already solved the problem of producing truly random bits?

Also, are there any examples of an explicit use of extractors in areas such as cryptography or coding theory?


texts: Is there a concept of "Lego complete"? If not, does it make sense to develop one?

texts:
We know the concept of Turing Completeness. These days when I play lego with my kids. I realised that Lego is kinda like programming language: we can build a lot of things with a fairly small set of Lego shapes.
This makes me wonder, is there a math/computing theory similar to Turing Completeness for Lego: given a set of lego shapes, can we prove that, these lego shapes could generate all possible objects we can think of.
Obviously this idea sounds a bit silly. If this question is not suitable for this site, please help to point me to the right forum. Thanks!


texts: To what extent can an algorithm predict the time complexity an arbitrary input program?

texts:
The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs.

I can, however, certainly write a program that can compute the running time of a program of  like:

for(i=0; i<N; i++)
    { x = 1; }

and return a time complexity of $N$, without ever running it.

For all other input programs, it would return a flag indicating it was unable to determine the time-complexity.

My question is this:

What conditions must hold, such that we can algorithmically determine the time-complexity of a given program?

*If there is a canonical reference or review article to this I would appreciate a link to it in the comments.


texts: If SAT is in PCP, for some constant q, then P = NP

texts:
I have seen this statement before, but I haven't really seen a proof of it:

If $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, for some constant $q$, then $P = NP$.

Now, if $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, then SAT reduces to $GAP-q-CSP[1,2^{-q}]$. So to show $P = NP$, how do we show then that $GAP-q-CSP[1,2^{-q}]$ is in $P$?


texts:
Complexity theory seems to capture something fundamental about the
structure of the universe, in that it formalizes the intuitive notion
that some problems are harder than others.

Scott Aaronson predicted, "The NP Hardness Assumption will eventually be
seen as analogous to the Second Law of Thermodynamics or impossibility
of superluminal signaling."

So-called "hard problems" are the basis of modern cryptography.

Are there any other applications that utilize, depend on, or exemplify the
existence of computationally hard problems?


texts: How can non-terminating $\lambda$-terms be turned into fixed-point combinators?

texts:
I've been thinking about these questions:

Is there a typed lambda calculus which is consistent and Turing complete?

https://cs.stackexchange.com/questions/65003/if-%CE%BB-x-x-x-has-a-type-then-is-the-type-system-inconsistent

and there are already some hard to answer related questions in the untyped setting! More specifically, I'm curious to know whether we can recover Turing-completeness from non-termination in the following way:

  Question: Given a (pure) $\lambda$-term $t$ with no weak head normal form, does there always exist a fixed-point combinator $Y_t$ such that
  $$ Y_t\ (\lambda x.x) = t$$

Equalities are all taken modulo $\beta\eta$.

I actually suspect this version of the question to be false, so one can relax the question to looping combinators, where a looping combinator $Y$ is defined to be a term such that for every $f$
$$ Y\ f=f\ (Y'\ f)$$
where $Y'$ is again required to be a looping combinator. This is enough to define recursive functions as usual, of course.

More generally, I'm interested in finding "natural" ways to go from a non-terminating $t$ to a looping combinator, even if the above equation isn't satisfied.

I'm also interested in weaker versions of the above question, e.g. $t$ may be taken to be an application $t\equiv t_1\ t_2\ldots t_n$ with each $t_i$ in normal form (though I'm not sure that really helps).

So far: the natural approach is to take $t$ and "pepper" applications of $f$ throughout, e.g.

$$ \Omega:=(\lambda x.x\ x)(\lambda x.x\ x)$$

becomes the usual

$$Y_\Omega:= \lambda f.(\lambda x. f\ (x\ x))\ (\lambda x.f\ (x\ x))$$

The idea is to reduce the head of $t$ to a lambda application $\lambda x. t'$ and replace it with $\lambda x.f\ t'$, but the next step is unclear (and I'm skeptical that this can lead to anything).

I'm not sure I understand enough about Böhm trees to see whether they have anything to say, but I highly doubt it, since $\Omega$'s Böhm tree is simply $\bot$, which looks nothing like the one for $Y_\Omega$: an infinite tree of abstractions.

Edit: A friend of mine remarked that this naive approach does not work with the term:
$$ (\lambda x.x\ x\ x)(\lambda x.x\ x\ x)$$
The naive approach would give
$$ (\lambda x.f\ (x\ x\ x))(\lambda x.f\ (x\ x\ x))$$
But this is not a fixed point combinator! This can be fixed by replacing the second application of $f$ by $\lambda y z.f\ y$, but then $f\mapsto \mathrm{I}$ does not give the original term. It's not clear whether this term is a counter-example to the original question though (and it certainly is not a counter example to the more general one).


texts: Given a domain, how do we build a language whose denotation is the domain?

texts:
Say we have an arbitrary domain $D$ with a countable basis $B$. Now, how do i build a "language" whose "denotation" lives in the domain?
My understanding is that Dana Scott initially built domains to get a model of typed lambda calculus. Then, people bgan studing domains in their own right. So if I know that something forms a domain, can I "extract computation" / "extract a language" out of it?
Perhaps said differently, does every domain $D$ [with more conditions as necessary] always come equipped with the structure of a closed cartesian category?


texts: Las Vegas vs Monte Carlo randomized decision tree complexity

texts:
Background:

Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of $f$, denoted $D(f)$, is the minimum number of bits of the input $x\in\{0,1\}^n$ that need to be read (in the worse case) by a deterministic algorithm that computes $f(x)$. Note that the measure of complexity is the number of bits of the input that are read; all other computation is free.

Similarly, we define the Las Vegas randomized query complexity of $f$, denoted $R_0(f)$, as the minimum number of input bits that need to be read in expectation by a zero-error randomized algorithm that computes $f(x)$. A zero-error algorithm always outputs the correct answer, but the number of input bits read by it depends on the internal randomness of the algorithm. (This is why we measure the expected number of input bits read.)

We define the Monte Carlo randomized query complexity of $f$, denoted $R_2(f)$, to be the minimum number of input bits that need to be read by a bounded-error randomized algorithm that computes $f(x)$. A bounded-error algorithm always outputs an answer at the end, but it only needs to be correct with probability greater than $2/3$ (say).

Question

What is known about the question of whether

  $R_0(f) = \Theta(R_2(f))$?

It is known that

  $R_0(f) = \Omega(R_2(f))$

because Monte Carlo algorithms are at least as powerful as Las Vegas algorithms.

I recently learned that there is no known separation between the two complexities. The latest reference I can find for this claim is from 1998 [1]:

[1] Nikolai K. Vereshchagin, Randomized Boolean decision trees: Several remarks, Theoretical Computer Science, Volume 207, Issue 2, 6 November 1998, Pages 329-342, ISSN 0304-3975, http://dx.doi.org/10.1016/S0304-3975(98)00071-1.

The best known upper bound of one in terms of the other is

  $R_0(f) = O(R_2(f)^2 \log{R_2(f)})$

due to [2]:

[2] Kulkarni, R., & Tal, A. (2013, November). On Fractional Block Sensitivity. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, p. 168).

I have two specific questions.

[Reference request]: Is there a more recent paper (after 1998) that discusses this problem?
More importantly, is there a candidate function that is conjectured to separate these two complexities?

Added in v2: Added ref [2], emphasized second question about existence of candidate function.


texts:
Is there a constructive way to generate a graph with a fixed min cut equal to $k$?
One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to get the desired min cut -- but I am wondering if there is a more systematic procedure?

Ideally I would want to generate a random instance of a graph with min-cut=$k$, and I would want it to be bipartite, but insight on any part of this question would be helpful!

Thanks in advance!


texts: Maximum cardinality subgraphs meeting a Jaccard overlap threshold

texts:
Consider two undirected connected graphs $G_0$ and $G_1$. The graphs are subgraphs of a given connected graph $G$ and share at least one node.

I want to find two subgraphs $G_0'\subseteq G_0$ and $G_1'\subseteq G_1$ such that they are connected, and the Jaccard index of their node sets is greater than a threshold $\alpha$ (fixed, between 0 and 1), that is $J=\frac{\left\vert V_0' \cap V_1'\right\vert }{\left\vert V_0' \cup V_1'\right\vert} \geq \alpha$ and these subgraphs are such that the sum $\left\vert V_0'\right\vert+ \left\vert V_1'\right\vert$ is maximized.

Starting from $G_0' = G_0,G_1' = G_1$, for the purpose of increasing $J$, while keeping connectedness of both graphs, I know I can unilaterally decrease the denominator of J by progressively removing as many nodes as possible that are in the nodes set difference $S=(V_0 \cup V_1) \setminus (V_0 \cap V_1)$, and are leaves of a spanning tree of $G_0'$ or $G_1'$. However it might be the case that no such leaf exists, yet I can obtain a higher overlap cutting bigger parts of possibly both graphs and renouncing to part of the intersection, yet having a lower $\left\vert V_0'+V_1'\right\vert$.

An example with an optimal solution (the intersection of the two subgraphs is highlighted in gray):

Can you think of an efficient algorithm that explores the subsets with some guarantee, maybe exploiting the upper bound $J \leq \frac{\min(\left\vert V_0'\right\vert,\left\vert V_1'\right\vert)}{\max(\left\vert V_0'\right\vert,\left\vert V_1'\right\vert)}$. Is this problem tractable?


texts: High-level overview of Razborov's method of approximations

texts: What is Razborov's method of approximations? Can someone give a high-level overview and the intuition behind it?


texts: Applications of "Seemingly Impossible Functional Programs"

texts:
What are some practical applications (existing or potential) for Martin Escardo's "Seemingly Impossible Functional Programs"?

For starters, here are a few from:

Alex Simpson’s Lazy functional algorithms for exact real functionals.
Compute maximum value and integral of a real function, with real numbers
represented as infinite sequences of digits.
Verification of real-number programs by checking infinitely many cases.


texts: Alternatives to Normalization by Evaluation

texts:
Reading about lambda calculus I got the impression that normalization is evaluation.
So I don't understand what is meant by Normalization by Evaluation (used e.g. in several publications of A. Abel).
Can you explain what are the alternative paths to the goals achieved by NbE?


texts: What is the name of this data structure? (hash table with a limit on the number of entries)

texts:
Denote $[n] \triangleq \{1,2,\ldots,n\}$.

Assume we would like to have a data structure $S$ which kinda works as a dictionary from $[k]$ to $[v]$, and supports add/remove/update/query functionality, without any dynamic memory allocation (everything has to be pre-allocated).

In general, one cannot do better than using $\Omega(k\log\frac{v}{k})$ bits in a succinct implementation or $k\log v$ bits in a simple array/hash table..

But if we assume that no more than $m$ items may be added to $S$ (assume you may ignore any additional add operation until some item is removed), we can improve the memory requirements, especially if $m<<k$.

Without getting into succinct implementation (is such known (which takes $m$ into consideration)?), one may simply allocate an array of $c\cdot m$ (where $c$ is a space/time performance parameter) linked lists, and whenever key $x$ is added to the structure, place it in list $h(x)$ for some function $h:[k]\to [cm]$.

If $h$ spread the actual keys (about) evenly, then the structure may still perform operations in $O(1)$ time for constant $c$ (as $\frac{1}{c}$ is the expected list length), while reducing the space requirement to $O(m(c+\log (vk)))$ (this can be done without any need for dynamic allocation).

I'm currently working on a succinct implementation of such structure for some application, and was wondering if there is a name for it.


texts: Proof that the calculus of constructions extended with recursive types isn't strongly normalizing?

texts: What is the proof that the calculus of constructions, extended with recursive types (i.e., Fix at the type-level) isn't strongly normalizing?


texts: Is public-key spread-spectrum communication possible?

texts:
Alice wants to get a message to a large number of people living under a censorship-happy government, run by Eve.
The traditional way of doing this is samizdat, but that process requires each person passing a message to take a certain risk. It would be nice of there were some way of doing this directly.

Spread-spectrum communications are resistant to jamming. However, this method assumes a shared secret key. It is implausible for this to remain secret when distributed to the audience, and when Eve obtains the key, she can jam the channel.

So, the question is: Is it possible to device a communications method like spread-spectrum, which does not require a shared key?

To be specific: A solution would require resistance to jamming, and that the
receivers can authenticate that the message was sent by Alice. Secrecy is not a requirement (and is implausible anyway).

More formally: Alice wants to send a message m over the radio spectrum. Alice has a public/private key pair, and uses it to encode the message into a cyphertext C, (we can take C to include the details of how the message is modulated for transmission). Alice can only transmit at some power level Ap. Eve only knows the public key. Alice's recipients only know the public key.  Eve can transmit a jamming signal, presumably at a much higher power level than Alice, although not without limit (especially on areas of the spectrum already being used for, say, TV channels). In a solution, Alice's followers will still be able to decode the message using only the private key.

Additionally, Alice would like to be able to repeat the exercise without having
to circulate a new public key. Suppose that the system worked on the first message, but that Eve was able to obtain the cyphertext C. Then, if the system does not vary over time, Eve will be able to jam the channel using the C. So either the system must vary with time, or Eve must not be able to obtain the cyphertext.

Some authors have described public-key steganography schemes, eg [1]. considers active attacks that attempt to break the secrecy or authenticity  of the scheme, by sending additional messages, but not than ones which perturb existing messages. [2] Does consider these kind of attacks, but their scheme is not obviously applicable to spread spectrum (to me, at least): It only copes with a limited amount of perturbation, and in doing so reduces the bandwidth of the channel a great deal.

Fingerprinting and covert channel schemes do consider 'jamming' type attacks, but I am not aware of them using public key crypto to counter such attacks.

[1] "Public-key steganography with active attacks", Michael Backes and Christian Cachin

[2] "On the limits of Steganography", Anderson and Peticolas


texts: What do we know about provably correct programs?

texts:
The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in which you have to give a formal proof that your code works correctly.

I believe the term is a 'certifying compiler' (I found it here): a compiler compiling a programming language in which one not only has to write the code, but also state the specification of the code and prove that the code adheres to the specification (or use an automated prover to do so).

While searching the internet, I only found projects that either use a very simple programming language or failed projects that try to adapt modern programming languages. This leads me to my question:

  Are there any certifying compilers implementing a full-blown programming language, or is this very hard/theoretically impossible?

Additionally, I've yet to see any complexity class involving provable programs, such as 'the class of all languages decidable by a Turing machine for which a proof exists that this Turing machine halts', which I shall call $ProvableR$, as an analogue to $R$, the set of recursive languages.

I can see advantages of studying such a complexity class: for instance, for $ProvableR$ the Halting problem is decidable (I even conjecture $ProvableRE$ defined in the obvious way would be the largest class of languages for which it is decidable). In addition, I doubt we would rule out any practically useful programs: who would use a program when you can't prove it terminates?

So my second question is:

  What do we know about complexity classes which require their containing languages to provably have certain properties?


texts: Finding distances in graphs where shortest path has a large number of nodes

texts:
I was wondering what is the most efficient way to find the shortest distances between all pairs of vertices in a graph where the shortest path between those vertices has length $\geq L$.  The only way I know of so far is to choose a smaller "hitting set" $B$ such that each long shortest path contains at least one node from $B$ with high probability.  Then you can find all distances from nodes in $B$ to all nodes in the graph, and get $d(u, v) = \min_b d(u, b) + d(b, v)$.

Are there any faster methods?

Thanks!


texts: Looking for an "additive" binary graph operation that preserves subgraphs of high degree

texts:
I'm looking for a binary graph operation $\oplus$ that has the following properties for all undirected graphs $G_1$ and $G_2$.

If $d_1$ is the largest number for which $G_1$ has a subgraph of minimum degree $d_1$, and $d_2$ the largest such number for $G_2$, then the largest such number for $G_1 \oplus G_2$ should be $d_1 + d_2$. In other words, $$\max_{H \subseteq G_1} \delta(H) + \max_{H \subseteq G_2} \delta(H) = \max_{H \subseteq G_1 \oplus G_2} \delta(H),$$ where $\delta(H)$ denotes the minimum degree of the subgraph $H$.
$|G_1 \oplus G_2| \in O(|G_1| + |G_2|)$.
$G_1 \oplus G_2$ is computable in logarithmic space.

I believe the Cartesian product for graphs satisfies the first and the third conditions, but the size of the product graph in this case is multiplicative (specifically $O(|G_1| \cdot |G_2|)$), not additive. I will be performing this operation a polynomial number of times, so a multiplicative increase in size is unacceptable.

Edit: changed condition 3 to require a logarithmic space computation instead of a polynomial time computation.

Edit: changed condition 1 to require the maximum minimum degree over all subgraphs should be preserved.


texts: Separation result for proper learning under the uniform vs. adversarial distributions?

texts: Does anyone know of a concept class known to be (1) efficiently learnable under the uniform distribution but (1) NP-hard to learn under arbitrary [adversarial] distributions? I mean "learning" in the proper PAC sense.


texts: Model of MLTT with $\eta$ rule where function extensionality fails

texts: Consider intensional Martin-Löf type theory with judgmental $\eta$ rule for dependent product types. Is there a model of it where function extensionality fails?


texts: How Univalence can be used for proofs about algorithm correctness

texts: I read a book on homotopy type theory. HoTT has the univalence axiom. This axiom seems to simplify working in category theory, but which other fields of mathematics it simplifies? I.e. how can I use it, for example, to simplify a proof of correctness of an implementation of red-black trees?


texts:
MCTS/UCT is a game tree search method that uses a bandit algorithm to select promising nodes to explore. Games are played to their completion randomly and nodes leading to more wins are explored more heavily. The bandit algorithm maintains a balance between exploring nodes with high win rates and exploring unknown nodes (and in its pure form doesn't necessarily use a heuristic evaluation function). Programs based on this general technique have achieved pretty amazing results in computer Go.

Have bandit-driven monte-carlo searches been applied to any other search problems? For instance, would it be a useful approach in approximating solutions to MAX-SAT, BKP, or other combinatorial optimization problems? Are there any particular characteristics of a problem (structural/statistical/etc.) that would suggest whether or not a bandit-style approach would be effective?

Are there any known deterministic problems that would be totally resistant to bandit methods, due to the nature of the solution space?


texts: Minimal bandwidth required to synchronize two sets of values

texts:
We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the values are present on both hosts). We want to find an protocol to synchronize the two sets (ie. give to each host the knowledge of the values of the other hosts) in a way which minimizes the quantity of information transferred between the two hosts.

In particular, if we denote by $N_1$, $N_2$ the size of the sets and $K_1$ (resp. $K_2$) the number of values present only on computer 1 (resp. only on computer 2), the trivial algorithm where both computers exchange their sets is $O(N_1+N_2)$, and the trivial lower bound on the quantity of information to exchange is $O(K_1+K_2)$. Is it possible to reach this bound?


texts: Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

texts:
It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in less than $2^{\epsilon n}$ time, unless the Exponential Time Hypothesis(ETH) is false. I want to know whether something can be said about the approximation of Exact Set Cover.

For concreteness, I will define the approximate version of the problem below.

Let $\mathcal{U}$ be the universe and $\mathcal{S}$ be the collection of subsets. Then, an instance of Exact set-cover($\mathcal{U}$,$\mathcal{S}$,$d$) is a yes instance, if there is a collection $\mathcal{S'} \subseteq \mathcal{S}$ with $|\mathcal{S'}| \leq \eta d \quad (\eta <1)$ that exactly covers $\mathcal{U}$ (that is each element of the universe appears in exactly one set in $\mathcal{S'}$). The input instance is a no-instance if there are no exact covers, or all exact covers need more than $d$ subsets. Here $\eta$ (or rather $1/\eta$) is the approximation factor.


texts: Maximal Unit interval graph construction

texts:
Is it possible to construct a unit interval graph with $n$ vertices and clique number $k$ such that any other unit interval graph with same number of vertices and clique number is a sub-graph of that graph or isomorphic to a sub-graph of that graph?

My construction for k=3 is,

However, i could not generalize my proof. Please help.


texts: How does one augment AdaBoost with cross-validation?


texts:
Stating the title in another way, how to convince a strong applied CS department that a theorist would be a better choice than one more applied computer scientist?

I understand that it is natural for a applied department to want one more expert on a specific field. On the other hand, diversity is important and I think the importance of a theorist goes beyond better theory courses.

What is the importance of a TCS researcher in a mostly applied CS department?


texts: 3-Clique Partition for graphs of fixed diameter

texts:
The 3-Clique Partition problem is the problem of determining whether the vertices of a graph, say $G$, can be partitioned into 3 cliques. This problem is NP-hard by a simple reduction from the 3-colorability problem. It is not hard to see that the answer to this problem is easy when $\textrm{diam}(G) = 1$ or $\textrm{diam}(G) > 5$. The problem remains NP-hard when $\textrm{diam}(G) = 2$ by a simple reduction from itself (given a graph $G$, add a vertex and connect it to all other vertices).

What is the complexity of this problem for graphs with $\textrm{diam}(G) = p$ for $3\le p \le 5$?


texts: Is the isomorphism problem between posets represented by DAGs GI-complete?

texts:
Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete?

I believe this problem is equivalent to asking whether their transitive closures (or their transitive reductions) are isomorphic.


texts: Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra

texts:
Consider the space $\mathbb{Q}^n$.

A convex polyhedron is defined, equivalently, by a system of linear (in)equalities (with integer coefficients) or by a system of generators: vertices, and in case of unbounded polyhedra, rays and lines. (In some of the literature, these two descriptions are called H-representation and V- or W-representation.)

Are there recent results on the complexity of the problem of checking the equivalence of a constraint and a generator representation?

What I know:

Checking whether a polyhedron defined by constraints is included in another defined by generators (even if the second one is bounded) is co-NP-complete (Freund & Orlin, 1985).
Enumerating all vertices of an unbounded polyhedron (note: I have not discussed the other generators) is NP-hard. If I understand this result correctly, checking, given a list of constraints and a list of vertices, whether the list of vertices is exhaustive, is co-NP-complete (Khachiyan et al., 2008).


texts: Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

texts:
Given:

A bipartite graph G=(U,V,E)
Integers n and k.

Decision Problem:

Is there a subset of U of size k that has at most
n neighbours?

I am trying to figure out whether this problem is NP-hard (I suspect so), but couldn't find any reduction so far. The only well-known NP-hard problems for bipartite graphs seem to be finding bipartite subgraphs in graphs [1], and railway schedule optimization. It seems somewhat like an inverse of set cover, but is also different from set packing (which appears called as inverse of set cover).

Does anyone have ideas which problems could be related?

[1]: Computers and Intractability: A Guide to the Theory of NP-Completeness


texts: Questions about algebraic effects and handlers, decomposed handlers

texts:
Can a handler always be decomposed? Say a handler for Get and Set effects could be decomposed to a handler for Get and a handler for Set.
After they could be composed again by first applying the handler for Set and after the handler for Get.

Also why do handlers have special type instead of just being a function type from effectful type to effectful type.

And last question: why are computation types used so often in the papers instead of something more like monads in Haskell (where pure functions still exist).


texts: What is the best known FPT result for 3-hitting set?

texts:
My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for 3-Hitting Set).

I'm specifically interested in the case where the parameter is the optimal hitting set size.

I know the paper by Niedermeier and Rossmanith that presents an algorithm of run-time $O(2.27^k + n)$, but that paper is pretty old.


texts: Counting grid colorings that avoid certain features

texts:
A $k$-coloring of an $m \times n$ grid is a function $C:[m] \times [n] \to [k]$. A broken rectangle in $C$ is a tuple $(i,i',j,j')$ satisfying $C(i,j) = C(i',j) = C(i,j') \ne C(i',j')$ -- that is, exactly three corners of the rectangle are the same color.

I'm interested in the following question:

  As a function of $k$, how many $k$-colorings exist (for grids of any size) that avoid duplicate rows, duplicate columns, and broken rectangles?

So far I know that the answer is finite, and the best upper bound I can prove is $k^{(1.5 k!)^2}$ (see below).

I'll also just point out that this is a different question than the one talked about by Gasarch frequently on his blog (and in this paper). He wants to avoid all monochromatic rectangles, whereas I don't mind monochromatic rectangles, it's just the "broken" ones that I want to avoid.

What is the motivation? In cryptography, we consider the problem of Alice (who has $x$) and Bob (who has $y$) both learning $f(x,y)$ for an agreed-upon function $f$, in such a way that they learn no more than $f(x,y)$. You can associate $f$ naturally with a 2-dimensional table, hence, a grid coloring. There are characterizations for this kind of problem of the following form (but with different notation): "$f$ has some cryptographically interesting property if and only if $f$ contains a broken rectangle." For examples, see Kilian91 and BeimelMalkinMicali99.

So this problem has come up in some setting of cryptography that I was investigating. For my purposes, it was enough to know that there are a finite number of grid colorings that avoid broken rectangles and duplicate rows/columns. But I thought the combinatorial problem itself is interesting and I believe better bounds should be possible.

The best bound I can prove: Define $R(2)=3$ and $R(k) = k \cdot R(k-1)$; hence $R(k) = 1.5 k!$. First, one can prove that if $C$ is a $k$ coloring with at least $R(k)$ rows, then it either has a duplicate row or a broken rectangle. Symmetrically, one can show the same thing with respect to columns. (The proof is pretty basic, following from the pigeonhole principle on the # of colors.) From this, we know that the colorings we care about all have dimensions smaller than $R(k) \times R(k)$, and we can get a very loose upper bound of $k^{R(k)^2}$ such colorings.

I think this can be improved in two ways: First, I think the optimal value of $R(k)$ is $2^{k-1}+1$. Below is a (recursively defined) family of colorings, where $C_k$ is a $k$-coloring of size $2^{k-1} \times 2^{k-1}$ that avoids these forbidden features:

$
     \qquad
     C_1 = [1];
        \qquad
     C_k = \left[ \begin{array}{ccc|ccc}
                k & \cdots & k & \\
                \vdots & \ddots & \vdots &  & C_{k-1} \\
                k & \cdots & k & \\
                    \hline
                 & & & k & \cdots & k \\
                 & C_{k-1} & & \vdots & \ddots & \vdots \\
                 & & & k & \cdots & k
            \end{array} \right].
$

I believe these to be the largest $k$-colorings that avoid these forbidden structures.

Second, even if one could improve the bound on $R(k)$ described above, we still have the fact that $k^{R(k)^2}$ is a very coarse bound for the total number of colorings. This counts all possible $R(k) \times R(k)$ grid colorings, of which a large portion presumably have the forbidden features.


texts: Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

texts:
DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question.

According to this paper, if there is a solution to a quantifier free Presburger formula, there is a solution whose size in bits is polynomial in the problem size. This allows the problem to be in $NP$, easier than arbitrary Presburger formulas.

However, the paper doesn't explicitly reference where this bound comes from, just mentioning a connection to Integer Linear Programming.

I was wondering if anyone knew, what was the exact bound on the solution size, or if they could provide a reference for such? I have another problem which I can phrase as a QF Presburger formula, and I'd like to find a definite bound on the solution size. But I'm also trying to work it into an actual software system, so simply knowing "there exists a polynomial" doesn't help me much.


texts: Agnostic Learning of K-Juntas over "small" distribution

texts:
I have two questions related to agnostic learning, one specific and one more general, specifically when the distribution relative to which the learner must operate is given explicitly as part of the input.

The specific question is closely related to proper agnostic learning of k-Juntas, though the connection is fuzzy. Consider the following optimization problem.

Problem statement: You are given a set $S$ of $m$ binary strings in $\{0,1\}^n$, a boolean function $f: \{0,1\}^n \to \{0,1\}$, and a parameter $k$. Find a k-Junta $g:\{0,1\}^n \to \{0,1\}$ which agrees with $f$ on as many elements of $S$ as possible.

Question: What is the best (multiplicative or additive) approximation algorithm for this problem if you are allowed to query f on points in S, and are allowed to run in time polynomial in m, n, and k? What about if you are allowed to run in time polynomial in m,n and $2^k$?

I sense that the answer to this question may be known or follow directly from existing techniques. A literature search reveals several works on agnostic learning of k-Juntas relative to the uniform distribution, where additive approximation schemes are possible (see, e.g. here). Observe that the problem above differs from the settings considered in much of the literature in that the set of points S in the hypercube that we "care" about classifying correctly is explicitly given in the input. In essense, this can be thought of as learning with respect to a uniform distribution on a subset S of the hypercube, where the runtime of the learner may depend on the size of S and the learner is allowed to query $f$ on $S$. This interpretation raises a more general reference-request question.

Question: Is there literature on agnostic learning relative to "succinctly given" distributions? Anyone know of example papers? What are the keywords one should search for? Also, to what extent do upper/lower bound results on agnostic learning w.r.t the uniform distribution imply something for succinct-distribution variants of the same problem?


texts: Necessary and sufficient condition for an infinite tree to be context-free

texts:
A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that form. This is folklore; to prove this just take a cycle in the Buchi automata containing a final state (which gives one $v$) and a path from the initial state to that cycle (which gives one $u$).
This extends to infinite trees as well. A tree automata accepting infinite trees is non-empty iff it accepts a regular tree i.e. an infinite tree with finitely many subtrees. (Safra)
Push-down automata on infinite words are exactly the $\omega$-Kleene closure of context-free languages over finite words [2,3]. Hence, any push-down automata on infinite words contains a word of the form $uv^{\omega}$.
But, push-down tree automata for infinite trees do not enjoy this characterization. In fact, there exists pushdown tree automata which do not accept any regular trees [1].
However, we can still ask if given an tree $T$ if there is a push-down tree automata on infinite trees that accepts exactly $\{T\}$. We just know that $T$ being regular would guarantee anything. I was wondering if we could formulate a necessary and sufficient condition.

Saoudi, A., Pushdown automata on infinite trees and nondeterministic context-free programs, Int. J. Found. Comput. Sci. 3, No. 1, 21-39 (199

Cohen, Rina S.; Gold, Arie Y., Theory of (\omega)-languages. I: Characterizations of (\omega)-context- free languages, J. Comput. Syst. Sci. 15, 169-184 (1977). ZBL0363.68113.

Linna, M., On (\omega)-sets associated with context-free languages, Inform. and Control 31, 272-293 (1976). ZBL0329.68066.2). ZBL0769.68099.


texts: How to come up with an non-trivial idea in theoretical computer science?

texts:
I am a PhD student working in theoretical computer science. I have read the research papers of many researcher and I have seen many tools and mathematics they use for designing an algorithm. For example see this research paper [Primality in P]. I would not say this research paper is based on one or two ideas but it is based upon many ideas which requires serious mathematics. I am struggling to come up with those kind of ideas from couple of years. I have worked on one problem for many months, but there is nothing non-trivial coming into my mind. All the ideas which have come into my mind till now are trivial and of very little use to theoretical computer science researchers. I am wondering how to come up with a machinery which will enable me to generate non-trivial results.

Question : How to come up with a non-trivial idea in theoretical computer science? I know there are different meanings to the word "non-trivial idea". For me, it is something publishable and interesting to the theoretical computer science community. I have seen some research papers in which they define few (mathematical) terms then design the algorithm using the defined terms. I wondering how to come up with such things.

One advice I have got from my research friends and seniors is to read the research papers carefully and read the mathematics (theorems and proofs) very carefully, try to do the proofs on your own and try to extend them.


texts:
We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$.

We also know there are degree $3$ bipartite graphs that are planar whose perfect matching count is in $P$.

What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
Is there a cutoff degree $\alpha\in[2,3]$ such that if max degree $3$ holds then counting perfect matching count is in $P$?
Is there any relevant literature?


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


texts: Completeness and Context-Sensitive Languages.

texts:
I'm interested in two questions regarding context-sensitive languages (CSL) and completeness:

 Is there a notion of completeness for CSL, and which languages are complete?
 Are there natural CSL that are NP-complete?

For 2., I can certainly think of natural NP-complete languages that are CSL (as CSL is equal to NSPACE[$n$], SAT is a CSL), but I'm searching for the other way around, i.e., a context-sensitive grammar describing an NP-complete language.


texts: The weakly NP-complete problems and their associated counting problem

texts:
Are there weakly NP-complete problems whose associated counting problem can be computed in pseudo-polynomial time? And if one were to be found (and assuming it is #P-complete), what would be the consequences on the polynomial hierarchy?

I'm aware of pseudo-polynomial time approximate counts to the knapsack problem. I'm only interested in exact ones.


texts: Time complexity of a branching-and-bound algorithm

texts:
Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching vector, and recently developed techniques such as measure-and-conquer may help us to obtain a better bound.
While branch-and-bound algorithms are usually used in practice and seem more efficient (in my experience), I find no result of analyzing the worst-case time complexity of a branch-and-bound algorithm. Does anyone know such an example?


texts: Interesting results in TCS which are easily explainable to programmers without technical background

texts:
Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math.

In order to show them the beauty of TCS, I'd like to gather some nice results/open questions coming from TCS which can easily be explained.

A good candidate for this purpose (IMHO) will be showing that the halting problem is not decidable. Another will be showing a lower bound on the running time of comparison based sorting (although that's a bit pushing it from what I expect them to understand).

I can also use the ideas from Explain P = NP problem to 10 year old, assuming some of them are unfamiliar with it.

So, questions has to be:

(0. Beautiful)

Explainable with (at most) high school math.
(preferably) not trivial enough to be shown in professional programming courses (for C++/Java/Web/etc.).


texts: Is Kolmogorov complexity a surjective function?

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

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

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


texts: Do combinatorial discrepancy upper bounds lead to smaller $\epsilon$-nets (as with $\epsilon$-samples)?

texts:
An $\epsilon$-sample (or $\epsilon$-approximation) of a family of subsets $\mathcal{S}$ of a ground set $X$ is a subset $P \subseteq X$ which preserves relative sizes of sets up to $\epsilon$. I.e., for any $S \in \mathcal{S}$,

$$
\left| \frac{|S\cap X|}{|X|}  - \frac{|S \cap P|}{|P|} \right| < \epsilon
$$

The (combinatorial) discrepancy $\mathsf{disc}(\mathcal{S})$ of $\mathcal{S}$ on the other hand is the minimum of

$$
\max_{S \in \mathcal{S}} \left|\sum_{e \in S}{\chi(e)} \right|
$$

over all colorings $\chi:X \rightarrow \{\pm 1\}$. You can think of this as coloring $X$ with blue and red so that each set is as balanced as possible; the discrepancy is the imbalance of the most imbalanced set in the most balanced coloring.

Finally, an $\epsilon$-net is a set $P \subseteq X$ such that every set $S$ of size $|S| \geq \epsilon |X|$ has non-empty intersection with $P$.

There is a close relationship between combinatorial discrepancy and $\epsilon$-samples. More precisely, if $\mathsf{disc}(\mathcal{S})<\frac\epsilon2 |X|$, taking either the red or the blue colored points, whichever set is smaller, gives an $\epsilon$-sample of size at most $|X|/2$. This construction can be repeated recursively. Thus upper bounds on discrepancy imply better size vs. error tradeoffs for $\epsilon$-samples.

The question is if small discrepancy also implies better size vs error tradeoffs for $\epsilon$-nets.

For example for set systems with finite VC-dimention we have discrepancy bound $O(\sqrt{|X|\log |X|})$. We can construct an $\epsilon$-net of size $O(\frac1\epsilon\log\frac1\epsilon)$.
How much smaller $\epsilon$-nets can we get  from better bounds for discrepancy?


texts: Does Factoring have a Statistical Zero Knowledge Proof?

texts: The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to determine whether $x$ has a prime factor less than $k$. Does this decision problem have a statistical zero knowledge proof?


texts: Pop desired elements on stacks of bounded capacity

texts:
Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color.
Only push and pop are allowed on the stacks.

We are interested in removing all the red elements from the stacks while maintaining the blue elements. That is, if we pop a blue element, we have to immediately push it into another stack before any other operation. Each stack has an upper bound capacity $b$, so it cannot hold more than $b$ elements.

We are interested in the minimum number of pop operations to remove all red elements from the stack (or respond it is infeasible).

One can devise a polynomial time algorithm when $k$ is a constant. Is there a polynomial time algorithm with respect to $n$ and $k$?

If we replace stacks with queues, then the problem is trivial.


texts:
I have a jigsaw type problem with 192 pieces which I am trying to find solutions to.  I have written a GA which starts from a random allocation then 'crosses' by taking rectangular blocks  from one solution then filling in from another then 'mutates' by switching pieces at random.  Through a complex procedure I can evaluate a solution and calculate a score.

I have a population size of 1000 and take 40% of the first parent in the cross and mutate up to 4% of the pieces in each solution generation.  I select the parents with a weighted selection and do not allow any exact duplicates in my population.

The problem I am having is that the algorithm gets stuck at about 70% score, with (I assume) a population full of near identical solutions.

What can I do to improve the performance of the algorithm, am I making any glaring mistakes?
Should I be mutating more, or directing the mutation more towards poor scoring pieces?
Should I have a larger population, or run several populations in parallel and share high scoring solutions between them?

Update

I have replaced my roulette with a tournament selection (with 4 solutions picked at random and the best selected) and implemented mutations up to 4 times on each new child in the generation.  I rearranged the process so that I cull half the population, then add some new random results then repopulate with crossovers.

Unfortunately, I seem to get a marginal performance increase, but I still seem to be converging at around 70% score.

Does anyone have any other ideas of things I can tweak to try and break through this barrier?


texts: What is the parameterized complexity of following model checking problem?

texts:
Input: Graph $G$ and formula $\varphi_1(\vec x),\varphi_2(\vec x)$

Parameter: $tw(G)+|\varphi_1|+|\varphi_2|$

Problem: Decide if $|\varphi_1(G)|=|\varphi_2(G)|$

where $tw(G)$ is the treewidth of $G$ and $\varphi(G):=\{\vec a|(G,\vec a)\models\varphi\}$.

What is the parametrized complexity of this problem for $\varphi_i\in FO$ or $\varphi_i\in MSO$?


texts: Is bounded-width SAT decidable in logspace?

texts:
Elberfeld, Jakoby, and Tantau 2010 (ECCC TR10-062) proved a space-efficient version of Bodlaender's theorem.
They showed that for graphs with treewidth at most $k$, a tree decomposition of width $k$ can be found using logarithmic space.
The constant factor in the space bound depends on $k$.
(Bodlaender's theorem shows a linear time bound, with an exponential dependence on $k$ in the constant factor.)

SAT becomes easy when the set of clauses has low width.
Specifically, Fischer, Makowsky, and Ravve 2008 showed that satisfiability of CNF formulas with treewidth of the incidence graph bounded by $k$ can be decided with at most $2^{O(k)} n$ arithmetic operations when the tree decomposition is given.
By Bodlaender's theorem, computing the tree decomposition of the incidence graph for fixed $k$ can be done in linear time, and therefore SAT can be decided for bounded treewidth formulas in time that is a low-degree polynomial in the number of variables $n$.

One might then expect that SAT should actually be decidable using logarithmic space, for formulas with bounded treewidth of the incidence graph.
It is not clear how to modify the Fischer et al. approach for deciding SAT into something space-efficient.
The algorithm works by computing an expression for the number of solutions, via inclusion-exclusion, and recursively evaluating the number of solutions of smaller formulas.
Although the bounded treewidth does help, the subformulas seem to be too large to compute in logarithmic space.

This leads me to ask:

  Is SAT for bounded treewidth formulas known to be in $\mathsf{L}$ or $\mathsf{NL}$?


texts: What is the etiquette of naming concepts after people?

texts: There is a concept introduced by other researchers that I use in my work, and IMO it is appropriate to rename it to honor the inventors. Is it considered normal to just go ahead and name it like that in my own paper? Should I ask the inventors for their permission? Are there any other considerations I should be aware of?


texts: question about probability ranking principle

texts:
I am studying IR and

I am not clearly understand  "probability ranking principle" ( I tried to google the definition, but i couldn't find clear answer.)

I am assuming that it's system which response to each request is a ranking of the documents in the collection in order of decreasing probability.

but, I am not clearly understand concept of probability ranking principle

does anyone can explain it ?

thanks


texts: Does Conway's PRIMEGAME generate all prime powers of 2?

texts:
Most sites I have visited reading on this interesting topic state something along the lines

  "the only powers of two (other than 2 itself) that occur in this sequence are those with prime exponent" (MathWorld)

or

  "After 2, this sequence contains the following powers of 2: [...] which are the prime powers of 2." (Wikipedia)

These careful formulations would imply that the set of powers of 2 generated in the sequence is a subset of prime powers of 2.

However, the OEIS seems absolutely certain that the two sets are equal: http://oeis.org/A034785

This result is also cited on other sites I do not consider very reliable for exact wording, like
http://esolangs.org/wiki/Fractran.

Honestly, I have not understood the internal mechanics of PRIMEGAME enough to answer my own question yet. However, I think it makes a significant difference in the interestingness of PRIMEGAME. Why would sites like MathWorld not state the full fact?


texts: Permuting the columns of a 0/1-matrix to avoid short segments

texts: Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment short if its length is at most $\log n$. It is not difficult to show that under a random permutation of the columns, the number of short segments is at most $O(\log^4n)$. Can you design a deterministic $O(n)$ time algorithm that takes the positions of $n$ stars as an input and outputs a permutation of the columns such that the number of short segments is at most $O(n/\log n)$?


texts: How small can be a layered boolean circuit for a function with circuit complexity $s$?

texts:
Consider a function $f$ computed by a boolean circuit $C$ with $n$ inputs of size $s(n) = \mathsf{poly}(n)$ over the basis $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ (with indegree 2 for the $\mathsf{XOR},\mathsf{AND}$ gates).

A boolean circuit is layered if it can be arranged into $d$ layers ($d$ being the depth of the circuit) of gates such that any edge between two gates connects adjacent layers.

Given that $f$ has a boolean circuit of size $s$, what can we say about the size of a layered circuit computing $f$? There is a trivial upper bound: by adding dummy nodes to $C$ at each layer crossed by an edge, we get a layered circuit of size at most $O(s^2)$. But can we get better in general (e.g. $O(s\cdot \log s)$, or $O(s)$), or for interesting class of circuits?

Background. This question stems from recent results in cryptography which show how to securely compute layered boolean circuits of size $s$ with communication $o(s)$ (e.g. $s/\log s$ or $s/\log\log s)$; I'm trying to understand how restrictive this restriction to layered boolean circuits can be in practice, either for general circuits or for "natural" circuits. However, I've not found much about layered circuits in the literature; appropriate pointers would also be welcomed.


texts: What is the smallest Turing machine where it is unknown if it halts or not?

texts: I know that the halting problem is undecidable in general but there are some Turing machines that obviously halt and some that obviously don't. Out of all possible turing machines what is the smallest one where nobody has a proof whether it halts or not?


texts: Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

texts:
This is a question related to this one. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question.

The classical proof of the undecidability of the halting problem depends on demonstrating a contradiction when trying to apply a hypothetical HALT decider to itself. I think that this is just denoting the impossibility of having a HALT decider that decides whether itself will halt or not, but doesn't give any information beyond that about the decidability of halting of any other cases.

So the question is

  Is there a proof that the halting problem is undecidable that doesn't depend on showing that HALT can not decide itself, nor depends on the diagonalization argument ?

Small edit: I will commit to the original phrasing of the question, which is asking for a proof that doesn't depend on diagonlization at all (rather than a just requiring it to not depend on diagonalization that depends on HALT).


texts: ETH based lower bound for $k$-COLORING of bounded degree graph

texts:
It is known that there is no $2^{o(n)}$-time algorithm for 3-COLORABILITY of graphs of maximum degree four, unless ETH fails [1]. Is a there a similar result for $k$-COLORABILITY assuming only ETH (not SETH)?
Emden-Weinert et al. [2] proved that for all $k\geq 3$, $k$-COLORABILITY is NP-complete for graphs of maximum degree $k-1+\sqrt{k}$. By an alternate reduction, I can show that there is no $2^{o(n)}$-time algorithm for $k$-COLORABILITY in graphs of maximum degree $k-1+\sqrt{k}$ (assuming ETH). I suppose this is not a new result. Could you please point me to a paper that gives this result? (I hate to brand results as folklore). Thanks in advance.
References
[1] Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz, Tight bounds for graph homomorphism and subgraph isomorphism, Krauthgamer, Robert (ed.), Proceedings of SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: SIAM; New York, NY: ACM. 1643-1649 (2016). ZBL1409.68209.
[2] Emden-Weinert, Thomas; Hougardy, Stefan; Kreuter, Bernd, Uniquely colourable graphs and hardness of colouring graphs of large girth, Comb. Probab. Comput. 7, No. 4, 375-386 (1998). ZBL0918.05051.


texts: Non-uniform version for the whole polynomial hierarchy

texts:
The non-uniform versions of P, NP and coNP are P/poly, NP/poly and coNP/poly.
Similarly, we can define a non-uniform version for each level in the PH.

For example: $\Sigma_2$/poly consists of problems of the form $\{x : \exists y \forall z \; C(x,y,z)\}$, where C is a circuit of polynomial size that may vary depending on the length of the input string $x$, and $y,z$ also have lengths polynomial in $x$.

Doing this for all levels of PH, we get a non-uniform version PH/poly.

QUESTIONS:  Is there anything known about this hierarchy? Does it collapse? Or is there another name for it in the literature?


texts: What's the intuition behind Rademacher complexity?

texts:
As stated, what exactly is the intuition behind Rademacher Complexity which is defined:

Rademacher complexity captures the richness of a family of functions by measuring the degree to which a hypothesis set can fit random noise.


texts: Why is Shor's algorithm in $BPP^{BQNC}$ when needing to uncompute subprocedure call?

texts: Why is Shor's algorithm in $BPP^{BQNC}$? It's true the quantum Fourier transform is in $BPP^{BQNC}$, but the algorithm needs to call a number theoretic function f which has period p which is a factor of n. f is computed by exponentiation by squaring, but the important thing is it has to be uncomputed reversibly. Doesn't the reversibility requirement place it out of BPP even though it superficially looks like it belongs there?


texts:
While studying chordal bipartite graphs, I have come across weakly simplicial vertices. I have searched for some time to understand what a weakly simplicial vertex is but I haven't succeeded.

A simplicial vertex is a vertex whose neighborhood induces a clique.

So, what is the weak form of this definition?


texts: Linear space language that requires exponential time without ETH

texts:
The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that

  There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$
  requires $\Omega(n^k)$ deterministic time to decide.

But I need a stronger assumption

  There is a language in $\mathsf{DSpace}(O(n))$ that
  requires exponential ($2^{\Omega(n)}$) deterministic time  to decide.

Obviously the Exponential Time Hypothesis (ETH) implies the statement above:
3SAT is in linear space.
But I don't want to assume ETH.

Is there a weaker conjecture (something that is plausible even if ETH is false)
that I can use?


texts: Are there applications of experimental mathematics in TCS?

texts:
In recent years there have been major, diverse, sometimes surprising advances in experimental mathematics [1] for a variety of sophisticated uses such as developing/deriving exact formulas, theorem proving, resolving previously unresolved conjectures (some deep), etc., ie basically core areas of mathematical research activity.

  Are there applications of this "experimental mathematics" in TCS/complexity theory?

[1] Experimental mathematics: examples, methods, and implications. by Bailey & Borwein, Notes of the American Mathematical Society, 2005

[2] Is "Experimental Complexity Theory" being used to solve open problems?, tcs.se

[3] A reading list on experimental algorithmics, tcs.se


texts: Combinatorial characterization of exact learning with membership queries

texts:
Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I may not know it. Even a comment like "I work in the area, but I haven't seen a characterization like this" would be helpful!

Background:

There are several well-studied models of learning in learning theory (e.g., PAC learning, online learning, exact learning with membership/equivalence queries).

For example, in PAC learning, the sample complexity of a concept class has a nice combinatorial characterization in terms of the VC dimension of the class. So if we want to learn a class with constant accuracy and confidence, this can be done with $\Theta(d)$ samples, where $d$ is the VC dimension. (Note that we're talking about sample complexity, not time complexity.) There is also a more refined characterization in terms of the accuracy and confidence. Similarly, the mistake bound model of online learning has a nice combinatorial characterization.

Question:

I want to know if a similar result is known for the model of exact learning with membership queries. The model is defined as follows: We have access to a black box which on input $x$ gives you $f(x)$. We know $f$ comes from some concept class $C$. We want to determine $f$ with as few queries as possible.

  Is there a combinatorial parameter of a concept class $C$ that characterizes the number of queries needed to learn a concept in the model of exact learning with membership queries?

What I know:

The best such characterization I have found is in this paper by Servedio and Gortler, using a parameter they attribute to Bshouty, Cleve, Gavaldà, Kannan and Tamon. They define a combinatorial parameter called $\gamma^C$, where $C$ is the concept class, which has the following properties. (Let $Q_C$ be the optimal number of queries needed to learn $C$ in this model.)

  $Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^C)$

This characterization is almost tight. However, there could be a quadratic gap between the upper and lower bounds. For example if $1/\gamma^C = \log |C| = k$, then the lower bound is $\Omega(k)$, but the upper bound is $O(k^2)$. (I also think this gap is achievable, i.e., there exists a concept class for which the lower bounds are both $\Omega(k)$, but the upper bound is $O(k^2)$.)


texts: What is the difference between proofs and programs (or between propositions and types)?

texts: Given that the Curry-Howard Correspondence is so widely spread/extended, is there any difference between proofs and programs (or between propositions and types)? Can we really identify them?


texts: Question about Mapping Reductions (Clarify Example)

texts:
I cannot for the life of me wrap my head around these reductions.

Specifically, the example I'm wrestling with:

REGULAR = {<M> | M is a Turing Machine and L(M) is regular}

Reduction to ACCEPT_TM where ACCEPT_TM = {<M,w> | M is a TM and w is a string, M accepts w}

Construct TM M':
M' = "On input x
    1. If x has the form 0^n1^n, accept
    2. Otherwise, run M on input w and accept if M accepts w."

If M accepts w, M' accepts SIGMA*
If M does not accept w, M' accepts 0^n1^n

I understand the first implication (if M accepts w, M' accepts SIGMA*).

What I don't understand is the implication that if M does not accept w, then M' accepts strings of the form 0^n1^n.  How are they reaching this conclusion?  To me, it seems like "If x is in the form 0^n1^n, then don't run M", which doesn't seem logically equivalent.


texts: How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

texts:
AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1].  (Note that AIC refers to Akaike Information Criterion)

However, AIC relies solely on the number of parameters in the model to assess/penalize model complexity.  And yet models can have infinite representational capacity even with just 2 parameters, as measured by VC-dimension [2], e.g. {sign(sin(ωx + θ) : ω}.  So this infinite VC model can act as a lookup table and perfectly overfit the data, while only having 2 parameters in the penalty term, so it would have low AIC, but no guarantee of low error out-of-sample.

I'm assuming that the issue is that the AIC convergence theorems don't apply to all models, and in particular perhaps these infinite VC-dimension models violate one of the assumptions.  But at least based on the papers I've looked at so far it's not clear to me what assumption that might be (if any)?

By the way, according to this review article [1] the convergence theorems apply quite broadly e.g.:

  When the true model is not in the candidate model set the AIC is
  efficient, in that it will asymptotically choose whichever model
  minimizes the mean squared error of prediction/estimation...
  The AIC's minimax rate of convergence in risk (and the BIC's lack of
  it) is a highly general result in regression and density estimation,
  and holds under more general circumstances than required for
  consistency properties discussed above. For example, the AIC is
  minimax-rate optimal regardless of whether the true model is finitely
  or infinitely dimensional; it is optimal whether the true model is
  among the candidates or not; and it extends to highly non-linear
  models, such as functions defined in Sobolev spaces

[1] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3366160/

[2] http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf


texts: Are there nice generalizations of SPQR trees to k-connected components for k>3?

texts: I'm curious how one should best understand the connections between the k-connected components when $G$ has minimum cuts of size $k>3$, or perhaps approximate minimum cuts produced by Karger's algorithm.  SPQR trees answer this question for 2-connected graphs.  And obviously 1-connected graphs are simply a tree of their 2-connected components.


texts: Fewest number of gates for Multiplication

texts:
What is the best result for the number of gates in a circuit multiplying two n-bit integers?

The obvious method generates $\theta(n^2)$ gates. There are better approaches with $\theta(n\log n \log\log n)$ and $\theta(n\log n2^{\log^*(n)})$ gates.

I could not find any Boolean circuit family which can handle multiplication with $n\log n$ gates. I wonder if such a family of circuits exists.


texts: Are there websites for TCS announcements that maintain mailing-lists  or web feeds?

texts:
For a while, I have been wondering if there exists some site where you can subscribe to receive TCS-conference announcements via e-mail, or, alternatively, that offers some periodically-updated web-feed. This is obviously very useful, but I have been unable to find one myself. Does anyone know of some reliable options?

Two examples of what I had in mind, which I use to look for conferences in quantum information/quantum physics and to keep track of their deadlines.

Quantum Meetings, has a RSS channel.
QUROPE, for European events, has a mailing list.

Related posts: List of TCS conferences and workshops.


texts: Randomized identity-testing for high degree polynomials?

texts:
Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime.

Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with  time $\mbox{poly}(n)$ and error probability $\leq 1-1/\mbox{poly}(n)$, even if the degree is not a priori bounded? What if $f$ is univariate?

Note that you can efficiently test if $f$ is identically zero as a formal expression, by applying Schwartz-Zippel over a field of size say $2^{2|f|}$, because the maximum degree of $f$ is $2^{|f|}$.


texts:
I'm a first year PhD student in a CS department at what some would probably consider a mid-tier university. I've been reading from Vershynin's High-Dimensional Probability and been trying to learn about concentration; I like problems relating to probability and geometry (e.g compressed sensing, dimension reduction, matrix recovery, etc.) But I'm wondering, more broadly:

If you could go back to grad school, what would you be doing during your first couple of years to learn techniques, etc.?
One thing I struggle with is determining which papers to read. There are so many to pick from; is there a better strategy than just reading whatever seems to pique interest/come from authors you know?
Are there books/problems/papers you read during grad school that helped you either technically or in forming your research interests/problem taste?

Thanks!


texts: Number of Hamiltonian cycles on random graphs

texts:
We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$.
Then the following fact is well known:

\begin{eqnarray}
Pr [G\mbox{  has a Hamiltonian cycle}]=
  \begin{cases}
    1 & (c(n)\rightarrow \infty) \\
    0 & (c(n)\rightarrow - \infty) \\
 e^{-e^{-c}} & (c(n)\rightarrow c)
  \end{cases}
\end{eqnarray}

I want to know results about the number of Hamiltonian cycles on random graphs.

Q1. How many is the expected number of Hamiltonian cycles on $G(n,p)$?

Q2. What is the probability $Pr [G \textrm{ has a *unique* Hamiltonian cycle}]$ for the edge probability $p$ on $G(n,p)$?


texts:
To better understand a paper I'm trying to get a brief understanding of least-fixed point logic. There are a few points where I am stuck.

If $G = (V,E)$ is a graph and

$$ \Phi(P) = \{(a,b) \mid G \models E(a,b) \lor P(a,b) \lor \exists z (E(a,z) \land P(z,b)) \}$$

is an operator on the binary relation $P$. I do not understand why the least fixed point $P^*$ of $P$ is the transitive closure of $E$. The example is taken from Finite Model Theory and Its Applications (p. 60).

When extending the first-order logic with the least-fixed pointer operator I do not understand why the relation symbol $S_i$ needs to be positive in the formula. Positive means  that every occurence of $S_i$ in the formula is within an even number of negation symbols.

Does anyone have idea what is good to read for an intuitive understand of least-fixed pointer logic and its syntax and semantics?


texts:
Are grammars programs? That is, are languages for grammar specification programming languages?

Update.

Motivation for the question is follows:

To know whether languages for grammars are programming languages.
Desire to know what words I use mean. Since no precise definition of term "programming language" exists we may bring it close to being by figuring out answers for such a tricky questions.
Which programs can and which can't be written as grammars? (idea by Rehno Lindeque)

Update.

Observation that caused a question was:

Language of grammars has executable semantics like a programming language: every grammar relates input to output (sequence of characters of given alphabet to boolean or AST, depends on implementation), deterministically or not. For example, grammars written in PEG are deterministic "programs" while in BNF are not. CFGs are not Turing complete while unrestricted grammars are.
Grammar can be designed to carry out a computation on a computer -- actually a parser.


texts:
I was wondering about what sets of languages are generated by restrictions of regular expressions.  Supposing that all the restrictions have a constant symbol for each element of $\Sigma$ and concatenation.  Then eight classes can be formed by the presence or absence of complement/negation, alteration/union, and the Kleene star.  (Yes, 'normal' regular expressions don't have a $^C$ operator, but it's convenient here.)

Expressions allowing alternation and the Kleene star, with or without complement (what's a little double-exponential blowup amongst friends?), generate the regular languages. Expressions allowing alternation and complement but not the Kleene star generate the star-free languages. Expressions allowing alternation but not complement or the Kleene star generate the finite languages.

But can any interesting classes of languages be generated without alternation?  Without any of the three operators all that can be generated is a single word.  The complement operator doesn't help much here.

With just the Kleene star the class is somewhat interesting... it's not clear if they can be recognized any faster than regular languages.  (Is anything nontrivial known about these?)

With both the Kleene star and complement... do you get anything interesting?  Does this class have a name?

This question was inspired by Regular Expression question on math.se.


texts: Finding a positive point for a collection of polynomials

texts:
I am wondering about the complexity of the following problem:

  Given $k$ polynomials $p_1(x_1, \ldots, x_n)$, $p_2(x_1, \ldots, x_n)$,
  $\ldots$, $p_k(x_1, \ldots, x_n)$ over the $n$ real variables $x_1,\ldots,x_n$.
  Find a point ${\bf x} = (x_1, \ldots, x_n) \in \mathbb{R}^n$ such that $p_1({\bf x}) > 0$, $\ldots$, $p_k({\bf x}) > 0$ (or declare that no such point exists).

Let us furthermore assume that each polynomial is given in the form $p_i(x) = \det(A_0^i + \sum_k x_k A_k^i)$, where we are given the matrices $A_0^i, \ldots, A_k^i$.

Questions:

Is this problem NP-hard?
When $k=1$ there is a randomized algorithm (simply choose a random point). Is there also a randomized algorithm for any $k\ge2$?


texts: Would it be possible to derive `transp` natively from Path, Interval and typecase?

texts:
Assume for a moment that we extended Agda with an Interval and a Path type, but not transp (which is a primitive currently). I'm aware it is internally defined by pattern-matching on types, as explained here. But I'm slightly confused by the notation of this paper (and the presence of ϕ : F, which isn't cited on Agda's docs). My question is: is my understanding right that, if we further extended Agda with typecase, we would be able to recover transp as a function rather than a primitive? In other words, could we write:

transp : (I -> Type) -> I -> P(i0) -> P(i1)
transp (\ i -> Set)          i0 f = ...
transp (\ i -> ((x: A) -> B) i0 f = ...
transp A                     i1 f = f

Directly? How would such a proof work, and, for illustration purposes, what it would look like in Agda pseudocode? Obviously, no need to cover all types, just Set, dependent functions and perhaps pairs.

Additionally: 1. It seems that typecase itself isn't quite enough since we have A
: I -> Type, not A : Type, so do we also need some kind of lamcase? 2. How could we enforce the "A must be a constant when r=i1" requisite interally?


texts: What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

texts:
I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The continuous optimization community seems to claim that all convex programs can be solved efficiently, but I believe their definition of "efficient" does not coincide with the TCS definition.

This question has been bothering me a lot in the last few years, and I can not seem to find a clear answer to it. I hope you could help me settle this once and for all: Which classes of MPs can be solved exactly in polynomial time, and by which means; and what is known about approximating the optimal solution of MPs that we can not solve exactly in polynomial time?

Below, I give an incomplete answer to this question that is also possibly incorrect at some places, so I hope you could verify and correct me at the points where I'm wrong. It also states some questions that I cannot answer.

We all know that linear programming can be solved exactly in polynomial time, by running the ellipsoid method or an interior point method, and subsequently running some rounding procedure. Linear programming can even be solved in time polynomial in the number of variables when facing a family of LPs with any super large amount of linear constraints, as long as one can provide a "separation oracle" for it: an algoritm that, given a point, either determines whether that point is feasible or outputs a hyperplane that separates the point from the polyhedron of feasible points. Similarly, linear programming in time polynomial in the number of constraints when facing a family of LPs with any super large amount of variables, if one provides a separation algorithm for the duals of these LPs.

The ellipsoid method is also able to solve quadratic programs in polynomial time, in case the matrix in the objective function is positive (semi?)definite. I suspect that, by using the separation oracle trick, we can in some cases also do this if we are dealing with an incredible number of constraints. Is that true?

Lately semidefinite programming (SDP) has gained a lot of popularity in the TCS community. One can solve them up to arbitrary precision by using interior point methods, or the ellipsoid method. I think, SDPs cannot be solved exactly due to the problem that square roots can not be computed exactly. (?) Would it then be correct if I say there is an FPTAS for SDP? I have not seen that stated anywhere, so that's probably not right. But why?

We can solve LPs exactly and SDPs up to arbitrary precision. What about other classes of conic programs? Can we solve second-order cone programs up to arbitrary precision, using the ellipsoid method? I don't know.

On which classes of MPs can we use the ellipsoid method? What properties does such an MP need to satisfy such that an answer can be given up to arbitrary precision, and what additional properties do we need in order to be able to obtain an exact solution in polynomial time? Same questions for interior point methods.

Oh, and finally, what is it that causes continuous optimizers to say that convex programs can be solved efficiently? Is it true that an arbitrary-precision answer to a convex program can be found in polynomial time? I believe not, so in what aspects does their definition of "efficient" differ from ours?

Any contribution is appreciated! Thanks in advance.


texts: How can I find dependent rounding procedures with the desirable properties?

texts:
I'm seeking for materials on dependent rounding. However, what I've found are two papers:

Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A., 2006. Dependent rounding and its applications to approximation algorithms. J. ACM
Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K., 2015. An Improved Approximation for K-Median, and Positive Correlation in Budgeted Optimization. SODA ’15

The first one can be used to deal with problems with hard cardinality constraints, while the second one can be used to deal with weighed constraints. I'd like to use dependent rounding as a tool to design (approximation) algorithms and I'm not interested in the mechanism behind the specific dependent rounding procedure. (I think)There should be other dependent rounding procedures with other nice properties. My question is:

How can I find dependent rounding procedures with the desirable properties when designing  approximation algorithms?
Are there tuitorial-level materials on how to use dependent rounding to design approximation algorithms?


texts: Finding self-similar homomorphisms of a FSM transducer

texts:
Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function which maps from $\Sigma \to \Sigma^*$. (Here, $h(x)$ is extended in the standard way to strings, $h(\epsilon)=\epsilon, h(x c) = h(x) h(c)$, where $x$ is a string and $c$ is a symbol from $\Sigma$.) Let $f(x)$ be the output of $F$ on $x$.

  Problem: Given $F$, find a non-trivial $h(x)$ such that for all $x \in L$, $h(f(x))$ = $f(h(x))$.

Call this a self similar homomorphism (SSH). Has this been studied anywhere? I'm looking for any (partial) insight, or related or nearby references on the following:

  What is an algorithm for finding an SSH? What is its complexity?
  What are sufficient and/or necessary conditions for a solution?
  Are there any applications?

[1] Introduction to automata theory, languages, and computation / Hopcroft & Ullman


texts: Techniques to get nodes in the best Markov Cluster?

texts:
I was using Markov Clustering to cluster nodes in my bidirectional graph, and overall the results were great.  However, there were a couple instances where a weakly connected node would attract a node that's much more strongly connected to other nodes.  So, for instance (this is a bit contrived, but it gets the point across) if I have a strongly connected clique of A,B,C,D, and a small offshoot between A and E the Markov algorithm may cluster B,C,D together and A and E together, because E is connected 100% to D.

A--[weight:10]--B
A--[weight:10]--C
A--[weight:10]--D
B--[weight:10]--C
B--[weight:10]--D
C--[weight:10]--D
A--[weight:1]--E

I'd prefer A,B,C, and D to be clustered together at minimum.  Are there any known techniques for adjusting the probability matrix to account for this?  Or is there a better algorithm?  I like Markov Clustering because it uses a probability matrix which takes into account the weight of each connection, but in this instance it's problematic.


texts: It seems to be commonly believed that quantum computer cannot efficiently solve NP-hard problems. What about the challenging problems in average-case, such as Planted Clique and Random 3-SAT?


texts: What is the role of "universe" types in intuitionistic type theory?

texts:
According to the Wikipedia article on intuitionsitic type theory:

  The universe types allow proofs to be written about all the types created with the other type constructors. Every term in the universe type $U_0$ can be mapped to a type created with any combination of $0, 1, 2, \Sigma, \Pi, =$, and the inductive type constructor.

Would you please explain and elaborate further on how the universe types allow proofs to be written about other types?


texts: Generate connected induced subgraphs as the satisfying assignments to a SAT instance

texts:
I want a SAT instance (in CNF) whose set of satisfying assignments are the connected induced subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the input is a subgraph of a 2D grid graph.

Of course, I want the size of the SAT instance to be polynomial in the size of the input graph, so that rules out ideas like encoding every path between each pair of vertices.

Edit: The answer I needed and accepted allows the use of extra variables to formulate a SAT instance.  Interestingly, @DavidEppstein shows that if no new variables are allowed, the required SAT instance cannot, in general, be found.