texts: One-way functions with polynomial inverting complexity

texts: Is there a trap-door-like function whose encoding complexity is polynomial time $n^{k_{1}}$ and inverting complexity(without secret key) is also a polynomial function in input length $n^{k_{2}}$ with $k_{1} << k_{2}$ (say $k_{1} = 2$ and $k_{2}$ is unconditionally provable to be bounded below by $1000$)? What are the implications of such functions if $VNP = VP$?


texts: Are there any well known algorithms for synthetic handwriting?

texts:
Please excuse if this is too practical. I decided it was not technical enough for stack overflow and probably suitable for here.

Given a set of letters, A-Z, what is the best scalable way to represent them in some form of synthetic handwriting.

I define synthetic handwriting to be a set of paths drawn on a canvas by a cursor, guided by the machine as if a human were writing with a pen.

The reason I am asking this is because I'm writing black box tests for one of my projects and want to fill up a database with fake signatures. Of course, I am also interested in the algorithms.

My first inclination is to take A-Z and draw paths myself, perhaps as SVGs and use those, but I think there must be some best way to do this so I am asking here.

I will post my research as I find information, as well.

EDIT:

This one looks nice: https://docs.google.com/open?id=1Hu2-dkqFDTBkDirjdemfBqln4-dS4I5QfYTF-6o-DsaxdCbkDDJ4LH1gkjal

Style-preserving English handwriting synthesis
Zhouchen Lin a,∗ , Liang Wan b
a Microsoft Research, Asia, Zhichun Road #49, Haidian District, Beijing 100080, PR China


texts: Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

texts:
This question has inspired the following two questions.
Given a first order logic language, with only unary predicates, finite number of variables, $\forall$ and $\exists$ i.e no equality and functions.

what is the complexity class of model enumeration in monadic first order logic ?
How expressive is this language, are there sentences in this language which cannot be expressed in function-free, equality free fragment of  $FO^{2}$  ?

I have asked a similar (but not the same) question here but after reading the linked question, I felt TCS-SE was probably a better choice for this question. And I did not delete it because it has an upvoted answer.


texts:
During my work i came up with the following problem:

I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties:

The determinant of $M$ is even.
For any non-empty subsets $I,J\subseteq\{1,2,3\}$ with $|I| = |J|$, the submatrix $M^I_J$ has odd determinant if and only if $I=J$.

Here $M^I_J$ denotes the submatrix of $M$ created by removing the rows with indices in $I$ and the columns with indices in $J$.

So far, I tried to find such a matrix via random sampling but I am only able to find a matrix that has all properties except the first one, i.e., the matrix always has an odd determinant. I tried various dimensions and different input/output sets without any success. So this makes me think:

Is that there is a dependency among the requirements, which prevents them from being simultaneously true?

or

Is it possible that such a matrix exists and can someone give me an example?

Thanks,
Etsch


texts: Are the intermediary sets in maximum cardinality search optimal in some way?

texts:
The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do the following:

Set $A = \{a\}$.
While $A \ne V$:

Choose a node $v \in V - A$ adjacent to at least one node in $A$ maximizing $\sum_{u \in A, \{u, v\} \in E} w(u, v)$.
Add $v$ to $A$ (set $A := A \cup \{v\})$.

Maximum cardinality search has applications in finding chordal graphs and as a substep in the Stoer-Wagner global min cut algorithm.

The structure of MCS is similar to the procedures used by Prim's algorithm and Dijkstra's algorithm - we begin with a single node in a set $A$, then iteratively and greedily expand that set by picking a node adjacent to $A$ optimizing some quantity and add it to $A$ until we're done.

One of the ways we can show correctness of Prim's algorithm or Dijkstra's algorithm is to argue that as $A$ is built up through the course of the algorithm, it is optimal with regards to some quantity. For example:

In each step of Prim's algorithm, the set $A$ is, of all subsets $X \subseteq V$ of cardinality $|A|$ containing the source node $a$, the one that induces the subgraph $G[X]$ with the least-cost MST.
In each step of Dijkstra's algorithm, the set $A$ is, of all subsets $X \subseteq V$ of cardinality $|A|$ containing the source node $a$, the one whose longest shortest paths in $G[X]$ has minimum length.

I've been trying to find some sort of similar invariant maintained by MCS. Specifically, I'd like to be able to say something like this for some function $F$:

  In each step of MCS, the set $A$ is, of all subsets $X \subseteq V$ of cardinality $|A|$ containing the source node $a$, the one for which $F(G[X])$ is maximum.

However, I can't seem to find a quantity that MCS actually maximizes. Here are some ideas I tried that didn't pan out:

Because MCS greedily adds nodes to $A$ based on the sum of the edge costs crossing into $A$, I thought that, perhaps, the set $A$ has the highest sum of edge costs among all comparable sets. However, this can be shown to be false with a simple line graph counterexample.
Because MCS is used as a subroutine in the Stoer-Wagner algorithm for finding minimum cuts, I considered that MCS might build a set $A$ that represents some optimal cut containing the node $a$. However, this can be falsified simply by looking at the starting set $A = \{a\}$, which is not guaranteed to be a minimum cut of any sort.

The literature I've seen on MCS mostly looks at applications in network detection or in the recognition of chordal graphs, where the concern is less about greedily optimizing some quantity and more about looking at the connectivity strengths of each added node.

Is MCS known to optimize some quantity at each step?


texts: Problems that are NP-complete under randomized or P/poly reductions.

texts: In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which unproven assumptions in number theory are true). Are there any other such problems known? Are there any natural problems that are NP-complete under P/poly reductions, but not known to be under P reductions?


texts: Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages.

texts:
Immerman (Descriptive Complexity, 1999) presents the EF games for existential monadic second order (Ajtai-Fagin games) on page 127.  As $\exists$MSO on words is equivalent to regular languages, the game can be written as follows.

A language $L \subseteq \{a, b\}^*$ is regular if and only if Delilah has no winning strategy in the following game:
1. Samson chooses $c, m \in \mathbb{N}$,
2. Delilah chooses $w \in L$,
3. Samson chooses $c$ subsets $C_1^w, \ldots, C_c^w$ of the set of positions in $w$ (i.e. $\{0, \ldots, |w|-1\}$),
4. Delilah chosses $v \not\in L$ and $c$ subsets $C_1^v, \ldots, C_c^v$ of the set of positions in $v$,
5. Samson and Delilah play the $m$-turn EF game on $(\mathfrak{S}(w), C_1^w, \ldots, C_c^w)$ and $(\mathfrak{S}(v), C_1^v, \ldots, C_c^v)$,
where $\mathfrak{S}(w)$ is the structure associated with the word $w$, i.e. :
$$\mathfrak{S}(w) = \langle \{0, \ldots, |w|-1\}, SUCC, Q_a, Q_b \rangle$$
with $Q_l = \{p \;|\; w_p = l\}$, and $SUCC$ is the binary successor predicate.

I have two questions:
- How does one show that $\{a^nb^n \;|\; n \in \mathbb{N}\}$ is not regular, using an EF argument like this,
- Is it easier/harder to play those games (to show non-regularity) when one has an ordering rather than the successor relation? (Those are equivalent in existential MSO).


texts: How are Futures described in terms of category theory?

texts: Is there a useful description of futures or promises in terms of category theory? In particular, what could the categorical dual of Future be?


texts: Idea for a white-box PIT deterministic algorithm in polynomial time

texts:
Just a warning, I am an amateur and this algorithm probably doesn't work.

A high level description of the algorithm:

Be $f(x_1,...,x_n)$ a polynomial, $n$ the number of variables and $d$ is the maximum degree of a variable in $f$.

Find a vector set with at least $m=n*d$ elements such that any combination of $n$ elements forms a linearly independent subset of vectors.

As pointed out by @SashoNikolov and @kodlu in another question, just use the geometric progressions in a Vandermonde matrix to create this set:
$$
\begin{bmatrix}
1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{n-1}\\
1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-1}\\
1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{n-1}\\
\vdots & \vdots & \vdots & \ddots &\vdots \\
1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{n-1}
\end{bmatrix}
$$

Where $\alpha_i = i$
Now we use the line-vectors of the Vandermonde matrix above to change the original polynomial $f$ into $m$ univariate polynomials $f_i(t)$ which corresponds to the values of the original polynomial $f$ along the line passing through the origin with the line-vector.

This is where it needs to be white-box, you go in the arithmetic circuit changing all variables according to the transformation:
$$f_i(t)=f(\alpha_i^{0}t,\alpha_i^{1}t,...,\alpha_i^{n-1}t)$$
Being a univariate polynomial, it is trivial to normalise this polynomial and check if it is identically $0$ or not.
If and only if all the univariate polynomials are identically $0$ then the original polynomial $f$ is identically $0$.

The geometrical reasoning:

Supposing $f$ is not identically $0$, to maximize the amount of non-colinear lines through the origin where $f=0$, $f$ should be a union of hypersurfaces (homogeneous polynomial).

Supposing $f$ is an homogenous polynomial (worst case), each hypersurface is able at best to make $f=0$ along $n-1$ of the Vandermonde line-vectors. So a union of $d$ hypersurfaces (best case as d is the maximum degree of a variable in $f$) is able at best to make $f=0$ along $(n-1)*d<m$ vector-lines.

Would this work? What is wrong?


texts: Graph class with easy chromatic number, but NP-hard coloring

texts:
Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard?

Without any further restriction the answer would be yes. For example, it is known that in the class of 3-chromatic graphs it is still NP-hard to find a 3-coloring, while the chromatic number is trivial: it is 3, by definition.

The above example, however, could be called "cheating" in a sense, because it makes the chromatic number easy by shifting the hardness to the definition of the graph class. Therefore, I think, the right question is this:

Is there a graph class that can be recognized in polynomial time, and the chromatic number of any graph $G$  in this class can also be computed in polynomial time, yet finding an actual $k=\chi(G)$-coloring for $G$ is NP-hard?


texts: VC-dimension of Cylinders within a Cylinder

texts:
I wish to know the VC-dimension of a range space $(X,\mathcal{R})$ constructed as follows:

$X$ is the cylinder $\{(x,y,z)\in\mathbb{R}^3|x^2+y^2\leq 1\}$
The ranges in $\mathcal{R}$ are formed by taking the union of circular disks such that:

the plane containing the disk is orthogonal to the z axis (we "stack" the disks in the z direction)
a disk is tangent to the cylinder boundary at the point $(1,0,z)$
a disk has diameter $f(z)+1$, where $f(z)$ is bounded (strictly) by $-1<f(z)<1$, and strictly monotonically increasing, strictly monotonically decreasing, or constant.

Any set constructed by rotating one of these ranges about the z axis by an arbitrary angle is also a range.

Intuitively, imagine taking a set of coins (circular, of course) and sorting them by diameter, either decreasing or increasing. Then drop them carefully into a tube (the main cylinder) in that order, so each rests on the last. Now tip the tube slightly so that they all rest against the side of the cylinder. If our coins had zero thickness and we had one for every real number, this would be our range.

I'm mostly interested in the case that $f(z)$ is sigmoid, like the error function or $\tanh$. Specifically, I'm interested in the cylindrical ranges formed by the family of functions $\tanh(\alpha(z-\beta))$, where $\alpha,\beta\in\mathbb{R}$.

I know that this range space has at least VC-dim 4 (I can construct a set of four points that it shatters), but I'm interested in putting an upper bound on it and understanding why. I know that:

Circular disks in $\mathbb{R}^2$ have VC-dim 3
Subsets of the strip $\{-1\leq y\leq 1\}\subset\mathbb{R}^2$ that are bounded above or below by $\tanh(\alpha(z-\beta))$ have at least VC-dim 3, probably equal to 3, because the slope part of the $\tanh$ function acts much like a line

Is there any way to combine these facts to obtain an upper bound on the VC-dimension? Is there anything to say about general $f(z)$ that meet the criteria in (2)?


texts: Introductory notes on parallelization, in particular patterns of problems and algorithms

texts:
I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science.

My focus is the following: while I am able to talk about divide&conquer, greedy algorithms, dynamic programming and the like, i.e. basic patterns of sequential algorithms (and problems), and I do not have the appropiate language to classify approaches in parallel algorithms.

For example, I would like to acquire the appropiate terms to express the fact that the obvious parallel approaches to each of the following problems have different qualitative behaviour:

setting an array of integers all-zero (scales perfectly.)
summing an array of integers (the more threads you use, the more overhead.)
Given an array, list the products of each entry with each other entry (if we parallelize the canonical double-for-loop, the running-time will scale to the sqrt of the number processors.)

A shared memory enviroment suffices, and interprocess communication is not so relevant for me (in fact, I am interested in algorithms that avoid it at all). Furthermore, the technical aspects are neglegible for me.


texts: Defining primitive recursive functions over general data types

texts:
The primitive recursive functions are defined over the natural numbers. However, it seems as if the concept should generalise to other data types, allowing one to talk about primitive recursive functions that map lists to binary trees, for example. By analogy, partial recursive functions over the natural numbers generalise nicely to computable functions on any data type, and I'd like to understand how to make the same kind of generalisation for primitive recursive functions.

Intuitively, if I were to define a simple imperative language that allowed basic operations on, say lists (such as concatenation, taking the head and tail, comparison of elements) and a form of iteration that requires knowing in advance how many iterations will occur (such as iterating over the elements in an immutable list), then such a language should at most be able to compute the primitive recursive functions over lists. But how can I understand this formally, and more specifically, how would I go about proving that my language computes all primitive recursive functions over lists and not just a subset of them?

To be clear, I'm interested in understanding primitive recursive functions as a well-defined class of functions (if indeed they are), rather than just in the operation of primitive recursion itself, which seems straightforward. I'd be interested in pointers to anything that's been written on primitive recursion over general data structures, or indeed in any context other than the natural numbers.

update: I may have found an answer, in a paper called Walther Recursion, by McAllester and Arkoudas. (Proceedings of CADE 1996.) This seems to contain a generalised version of primitive recursion as well as the more powerful Walther recursion. I intend to write a self-answer once I've digested this, but in the meantime this note might be helpful to others with the same question.


texts: Relationship between shift-reduce parsing and delimited continuations?

texts:
Has anyone formalized the relationship between shift-reduce parsing techniques and delimited continuations?

When constructing a bottom-up parser (eg, LR parsers), we take a grammar and then represent parse states as sets of items: augmented productions of the form $A \to \alpha \bullet \beta$, where $\alpha$ and $\beta$ are sequences of terminals and nonterminals. The marker $\bullet$ represents how far the parser has gotten into the string, with $\alpha$ representing what has been seen so far, and $\beta$ representing a prediction of what yet may be parsed.

A shift action in a transition of the LR parse automaton matches a prefix of the stack against $\alpha$, and replace it with $A$. Such a deep manipulation of the stack resembles the effect of a control operator, but this is just a qualititative observation.

Has anyone studied the connection between shift-reduce parsing and delimited control operators such as shift/reset?


texts: $XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?

texts:
Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following:

$FPT = XPuniform\implies EPTAS = PTAS$.

Fundamentals of Parametrized complexity on page $534$ has

which from "we will only look at XP and
remark that all the results hold with no change for uniform XP as well. By
standard diagonalization, we have the following basic result:

Proposition $27.3.1$. FPT is a proper subset of XP."

means $FPT$ is a proper subset of $XP_{uniform}$ as well.

Is this correct information? If so this result has been known for a long time. So is there any updates that need to be made to complexity zoo section https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas and is there any consequences to approximation algorithms because of this?
Does $FPT=W[P]$ have any consequences to approximation algorithms? I see only reverse consequences in complexity zoo:


texts: Error reduction with expanders and derandomization

texts:
In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability.
Now, if the algorithm has a good error probability to begin with, say 1/n, without expanders we need to run it only O(n/log n) times to achieve the same error and use $n^d\times O(n/\log n)$ random bits.
If I'm correct with expanders it doesn't help (beside a little in the first step), meaning we still need $n^d+O(n)$ random bits.
There exist some method, such that a good algorithm does have an affect on it (uses say $n^d+O(n/\log n)$ random bits)? There exist some barrier for achieving such a result?

*The question refers to the randomized algorithm in a black-box manner.


texts: Decidability of inductive invariant existence in Presburger arithmetic

texts:
Problem:

Consider a finite number of control states (including an "initial" and a "bad" state), a finite number of integer variables, and for each ordered pair of states a transition relation expressed in Presburger arithmetic.

Decide whether there exists an inductive invariant (= stable by post-states of the transition relation) containing the initial but not the bad state, definable in Presburger arithmetic.

(Note that this problem is different from the reachability problem in Presburger arithmetic, which is clearly undecidable (by reduction from two-counter machines).)

I suspect this problem is undecidable, but do not know of any proof for it. (It is obviously semidecidable.) Has somebody proved this ?


texts: Is optimal equal-point graph splitting NP-Complete?

texts: The problem is "Given a graph G with kn points, divide it into k pages of n points such that the number of edges between points on different pages is minimal." (I've worked on it with undirected graphs, but I think the basic problem is the same with directed graphs and multigraphs.) I've attacked with branch and bound and linear programming, and it's behaved as an NP-complete program--a 12 point, 4 page problem is solved almost instantly, but a 40 point, 8 page problem took over a day. Then again, those are solutions you use for NP-Complete problems. I see no obvious reduction of 3SAT or Travelling Salesman into it, but it feels like an NP-Complete problem--though that may be because I took a class on solving NP-Complete problems, so hammer and nail.


texts:
In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote

  Most computer scientists regard synchronization problems, such as the mutual exclusion problem, to be problems of mathematics. How can you use one class of mathematical objects, like atomic reads and writes, to implement some other mathematical object, like a mutual exclusion algorithm? I have always regarded synchronization problems to be problems of physics.  How do you use physical objects, like registers, to achieve physical goals, like not having two processes active at the same time?

My question is on the mutual exclusion problem particularly.

  What is the significance of regarding the mutual exclusion problem as a problem of physics? More specifically,

  What are the differences between the mathematical perspective and the physical one on the mutual exclusion problem?
  What inspirations and results have been gained directly from the physical perspective?


texts: Insertion and deletion operations for Turing machines

texts:
A Turning machine with insertion and deletion operations can be simulated by an ordinary Turing machine with a quadratic time cost.  Do we know how insertion and deletion fit into the polynomial time hierarchy though?

In particular, does anyone know a quadratic single-tape Turing machine that cannot be simulated by a linear time single-tape Turing machine with insertion and deletion?

I've gathered that separation results are often more powerful, and maybe easier to prove, for the nondeterministic time hierarchy.  Is that perhaps an easier place to attack this?  If so, that's great because I'm ultimately most interested in rewrite systems anyways.


texts: Complexity of the search version of 2-SAT assuming $\mathsf{L = NL}$

texts:
If $\mathsf{L = NL}$, then there is a logspace algorithm that solves the decision version of 2-SAT.

Is $\mathsf{L = NL}$ known to imply that there is a logspace algorithm to obtain a satisfying assignment, when given a satisfiable 2-SAT instance as input?
If not, what about algorithms which use sub-linear space (in the number of clauses)?


texts: Partition edges into edge disjoint walks

texts:
Consider an undirected graph $G=(V,E)$ and two sequences of $k$ vertices $S=s_1,\ldots,s_k$ and $T=t_1,\ldots,t_k$.
A set of $k$ walks is called a $(S,T)$-walk partition if

the walks form a partition the edges of $E$, and
there exists a permutation $\pi:[k]\to[k]$, such that the $i$th walk is a $s_it_{\pi(i)}$-walk. (A $st$-walk is a walk that starts with vertex $s$ and ends with vertex $t$)

We consider the following problem.

  $k$-walk partition

  Input: Graph $G$ and two sequence of $k$ vertices $S$ and $T$.

  Output: Does there exists a $(S,T)$-walk partition in $G$.

Is this problem studied? I'm interested when $k$ is a constant.
When $k=1$, this is the same as checking if there is a Eulerian trail from $s_1$ to $t_1$.


texts: Special properties of bipartite expanders

texts:
It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc.

However, I am curious if there are any special properties of bipartite expanders that more general families of expanders don't have (or vice versa). In particular, are there any extreme differences, where bipartite and non-bipartite expanders differ greatly (especially in a combinatoric, algorithmic, or complexity-theoretic sense)?

A priori, we might expect that bipartite and non-bipartite expanders would likely share many pseudorandom properties, and in fact are constructible from each other. So that would suggest a negative answer to this question.

On the other hand, bipartite graphs in general have many special properties (eg. König's theorem) that have complexity-theoretic implications. So it's not unreasonable to think that differences between random bipartite and non-bipartite graphs may yield interesting differences between bipartite and non-bipartite expanders.

This is sort of a vague, open ended question, since I'm not exactly sure what kind of answer I'd like, and I am open to any interpretation. However, an example of a 'non-answer' might be 'bipartiteness is distinguished by the smallest eigenvalue in the spectrum'; I'm more interested in specifically bipartite expanders rather than spectral properties of bipartite graphs as a whole.


texts: Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

texts:
First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold regularization).

I do not necessarily require that guarantees are with respect to generalization. However, those are always nice though but I just want to emphasize that the main focus of the question is about algorithms (with guarantees), not necessarily about generalization.

What I do want is that given a finite sample of data (maybe mixed with labeled and unlabeled data) if we can provably learn. For example, are there algorithms that guarantee that we learn the manifold or its structure? Or maybe, are there algorithms that theoretically guarantee better prediction with the manifold assumption? Any algorithm with provable guarantees is good.

To be clear of what I mean with provable guarantees I will give a couple of examples of scenarios/problems (and algorithms) where there are provable guarantees for (learning) algorithms.

Consider the non-negative matrix factorization problem where we have:

$$M =  AW$$

s.t. A and W are $m \times k$ and $k \times n$ and are required to be entry-wise nonnegative. In fact, lets suppose that the columns of M each sum to one. One can interpret this problem as follows. Each column is a document from our model. Its generated as a convex combination from topics (i.e. the columns of A). The combination is specified by the columns of W. Can we recover the best non-negative factorization of the model? It turns out that Vavasis proved its NP-hard 1. However, under the separability condition on the topics, one can show that there exists a polynomial time algorithm to compute such a non-negative factorization (of minimum inner-dimension). So this scenario has two things that are interesting:

We can learn the true model (the negative factorization) from the (samples) documents (with some probability conditions)
There a polynomial time algorithm for it.

The algorithm for this is based on finding the "Anchor words" (i.e. the highly technical words for each document) and then taking advantage of that to find the factorization. The some of the details for this can be found on this monograph on algorithmic aspects of machine learning.

This is exactly the type of thing I am interested in, on learning algorithms with some provable guarantees under some conditions. For more example, the following monograph has many that are appropriate examples. To name the monograph explains tensor methods, ICA, alternating minimization, mixtures of gaussians, matrix completion, phylogenetic trees, noisy parity and more!

References:

1 S. Vavasis. On the complexity of nonnegative matrix factorization. SIAM
Journal on Optimization, pages 1364-1377, 2009.


texts: Deciding whether a unary context-sensitive language is regular

texts:
It is a well-known result that the question

  Does a context-free grammar generate a regular language?

is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case, the classes of context-free and regular languages coincide.

My question is to know what happens for unary context-sensitive languages.

  Is it decidable to know whether a given context-sensitive grammar on a
  unary alphabet generates a regular language.

If the answer is positive, an estimation of the complexity would be welcome.


texts:
Suppose I have some pre-existing knowledge of where within a sorted array the element I am looking for lies, in the form of a probability distribution $P(i)$ that tells me the probability of the goal element being found at position $i$.

When executing a binary search, the pivot has to be chosen at each step. I have a vague sense that I could, somehow, exploit my pre-existing knowledge of the element's location while retaining the $\Theta(\log N)$ asymptotic performance of binary search by using $P(i)$ to inform my choice of pivot at each step. If this is indeed a good idea, how should it be done?


texts:
Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$.

Now lets analyze the following statement:

  If $\Sigma^{\leq f(|Q|)} \subseteq L(A)$, then $L(A) = \Sigma^*$.

It is easy to show, that for $f(n) = 2^n+1$ it is true, hence if the automata produces every word with length upto $2^{|Q|}+1$, then it produces $\Sigma^*$.

But does it still hold if $f$ is a polynom?

If not, what could a construction of a NFA $A$ for a given polynom $p$ look like, s.t. $\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$?


texts: Finding shortest path while maximizing the number of overlapping edges

texts:
The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however the cost is considered to be the length of the paths minus a positive coefficient times the number of common edges in the two paths, i.e. cost is $|P_1|+|P_2|-C|P_1\cap P_2|$.

Has this problem been addressed before?


texts:
The complexity class $\exists \mathbb{R}$ (the existential theory of the reals, i.e. problems that can be reduced to deciding if a collection of polynomial inequalities has a solution) is known to be contained in PSPACE and to contain NP. See this paper for a reference; as far as I can tell, that's the paper that introduced $\exists\mathbb{R}$ as a distinct complexity class.

However, Reif gives an explicit construction which takes a Turing machine with a polynomial space bound and a string, and constructs a motion planning instance which has a solution if and only if the machine accepts the string. Since motion plan existence can be reduced to $\exists\mathbb{R}$ (see, e.g., this paper by Schwartz and Sharir), this seems to imply that $\mathbf{PSPACE} \subseteq \exists\mathbb{R}$, and thus that $\mathbf{PSPACE} = \exists\mathbb{R}$.

I don't come from a CS theory background, and I feel like I must be missing something fundamental, because there looks to be a whole subfield  of authors writing papers placing various problems in $\exists\mathbb{R}$.


texts: Is there a PPAD algorithm for computing primes that sum to even numbers?

texts:
Goldbach's conjecture states that every even number greater than 2 can be expressed as the sum of 2 primes.

I'm interested in this function problem:

Given an even natural number n greater than 2, find a natural number p such that p and n - p are both prime.  (Inputs that are not even natural numbers may be mapped to 0.)

If we assume that Goldbach's conjecture is true, this function f(n) = p is a member of TFNP.  The reason for this is that we are guaranteed by our assumption that Goldbach's conjecture is true that there exists an answer to the problem, and we can easily guess this answer (it is no greater in size than n), and then verify its accuracy in linear time.

Can we do any better than TFNP here?  Could there be some algorithm in PPAD that computes this, or could there even be an FP algorithm?


texts: Complexity of computing the discrete Fourier transform?

texts:
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?

The classical algorithm for fast Fourier transforms, inappropriately[1] attributed to Cooley and Tukey, is usually described as running in $O(n \log n)$ time.  But most of the arithmetic operations executed in this algorithm start with complex $n$th roots of unity, which are (for most $n$) irrational, so exact evaluation in constant time is not reasonable.  The same issue arises with the naive $O(n^2)$-time algorithm (multiplying by a Vandermonde matrix of complex roots of unity).

It's not even clear how to represent the output of the DFT exactly (in any useful form).  In other words, it's not clear that computing DFTs is actually possible!

So suppose we only need $b$ bits of precision in each output value.  What's the complexity of computing the discrete Fourier transform, as a function of $n$ and $b$?  (For concreteness, feel free to assume $n$ is a power of $2$.)

Or does every instance of "FFT" in the literature actually mean "fast number-theoretic transform"?[2]

See my related questions on the complexity of Gaussian elimination and Euclidean shortest paths.

[1] It should really be called (some prefix of) the Gauss-Runge-König-Yates-Stumpf-Danielson-Lánczos-Cooley-Tukey algorithm.

[2] And if so, why do most textbooks describe only the complex-number algorithm?


texts: Exact catchup point between SGH and FGH of ordinals?

texts:
An ordinal hierarchy is a way to assign a function $f_{\alpha} : \mathbb{N} \rightarrow \mathbb{N}$ to each (recursive) ordinal $\alpha$. The corresponding functions are expected to be monotone and correspond to even faster growth rates as the ordinal increases.

Two well-known definitions in the field are the slow-growing hierarchy $(g_{\alpha})$ and the fast-growing hierarchy $(h_{\alpha})$. Although the latter grows much faster than the former, some authors have claimed the existence of a 'catch-up' point, i.e. that both hierarchies attain the same growth rate at some large ordinal $LN_0$ - the notation is mine, and we have the expected relations $\epsilon_0 < FS_0 < BH_0 < LN_0$ where $FS_0$ and $BH_0$ respectively denote the Fefermann-Schütte and the Bachmann-Howard ordinals.

Specifically, it seems that S.S. Wainer first claimed that $LN_0 = FS_0$, then retracted its claim after J.Y. Girard proved that $LN_0$ corresponded to the ordinal of the theory $ID_{<\omega}$. I have two questions in this respect:

(1) is this ordinal $LN_0$ canonical, or does it depend on the choice of a fundamental sequences for the hierarchies?

(2) does there exist an ordinal notation system for the ordinals up to $LN_0$? It seems that the most generic ONS known is tree-based and is due to Takeuti (?) but it's unclear to me whether it reaches $LN_0$...


texts: Suppose I have a collection of $m$ subsets of $\{1,\dots,n\}$, all of size $k$. I want to list these subsets so that two subsets adjacent to one another in the list are as close to one another as possible in that their intersection is as small in cardinality as possible. Can I do this in $o(m^2)$ time?


texts: Approximate answer to Max-SMT (bitvector) query

texts: I have a problem that could be completely solved as Max-SMT instances in the theory of quantifier-free bit-vectors, but it apparently is too complex to be tractable with current Max-SMT technology.  My application in practice could tolerate a fair amount of error, so I'm interested in the following problem: "Satisfy as many clauses as possible while terminating in x minutes." How would I go about approaching this? Is there a way I can leverage existing solvers?


texts:
A naive question perhaps: are there any results/references about $AC^0$ circuits with multiple outputs? Namely, I'm interested in the natural generalization of the Min-$AC^0_d$ problem (find a circuit of depth $d$ with minimal size that implements a given Boolean function). The generalization would be: find a circuit of depth $d$ with minimal size and $\log_2k$ outputs (or $k$ outputs if this encoding is more convenient -- $k$ is small anyway) that implements a given function $f:{\mathbb B}^n\to \{0,\ldots,k-1\}$.

I've tried googling but without effect (it's hard to google for $AC^0$ anyway). Any pointers would be much appreciated -- hardness results, inapproximability results, heuristics for solving the problem in practice...


texts: Edge-partitioning into rainbow triangles

texts:
I'm wondering if the following problem is NP-hard.

  Input: $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges
  ($f$ does not verify any specific property).

  Question: is it possible to partition $E$ into $|E|/3$ triangles,
  such that each triangle has one edge of each color?

I know that without the colors the problem of "edge partitioning" a graph into
$K_n$, $n \geq 3$ is NP-hard
(see The NP-Completeness of Some Edge-Partition Problems)
but with the colors I don't know.

I would also be interested in a result for edge partitioniong into rainbow $K_c$, with $c$ a constant. Of course, in this case the problem becomes:

  Input: $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,\ldots,c(c-1)/2\}$ of the edges ($f$ does not verify any specific property).

  Question: is it possible to partition $E$ into $|E|/(c(c-1)/2)$ $K_c$'s,
  such that each clique $K_c$ has one edge of each color?


texts: is determining an unknown CFL from intersection of two CFLs decidable?

texts:
this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it to them. eg it is known that CFLs are not closed under intersection but thats not the immediate answer.) a proof is ok but also looking for ref(s) if known. analysis of nontrivial special cases also might be interesting. also a single non empty/non trivial example case has not been given so far (eg plz exclude both languages regular languages).

  let $L_1, L_2$ be CFLs and $L=L_1 \cap L_2$ is known to be a CFL. is there an algorithm for constructing $L$?


texts: Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization

texts:
In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if anyone knew of a smaller textbook/course-notes exposition of the at least maybe the main point there.

For example, if I understand correctly, a consequence of all this was an estimate on the running time of solving any polynomial optimization problem (min/maximizing a polynomial with polynomial constraints). If at least this part can be read up from a simpler exposition somewhere else.


texts: Complexity of a variant of matrix multiplication

texts:
Assume a family of $n\times n$ integer matrices $\{M_a \mid a\in A\}$ for some finite set $A$, I want to decide whether for given vectors $\alpha$ and $\beta$,

$\alpha M(w) \beta=0$ for all $w\in A^{\leq n}$. Here $M(w)= M_{a_1}\cdot M_{a_2}\cdots M_{a_m}$ when $w=a_1\cdots a_m$, and $A^{\leq n}$ denotes the set of words over $A$ whose length is less than $n$.

I think this problem can be reduced to polynomial identity testing and has an RNC algorithm. But is there a better upper-bound or any nontrivial lower-bound?


texts: Topological sort with alternative choices of predecessors

texts:
I have a family of directed graphs over the same set of nodes $V$ defined as follows.

Each node $v \in V$ has $k_v$ alternative choices for its set of predecessors. In other words, I am given a relation $\rho\colon V \to 2^{V}$ such that $|\rho(v)| = k_v$ (where $\rho(v) = \{S \subset V \mid (v, S) \in \rho\}$, I'm abusing the relation notation a little bit). This relation induces a family of graphs: if we pick one predecessor set $S_v \in \rho(v)$ for each $v$, we obtain a fixed set of edges $E = \{ (u, v) \mid u \in S_v \}$ for the entire graph.

There are $\prod\limits_{v \in V} k_v$ such possible graphs, some of them are acyclic, some are not. I want to find at least one acyclic graph among these possibilities, and sort it topologically. Can it be done in polynomial time (i.e., faster than enumerating all possible combinations of choices explicitly)?

(As an illustrative application, imagine a package manager where some packages depend on either one of these other packages, because they all provide similar capabilities.)


texts:
2-SAT is in P.

Additionally, a (CNF) SAT-problem is trivially poly-time solvable if no two expressions can be resolved (via Robinson resolution, ie for every pair of disjunctive clauses, they either share no opposite literals or else two or more opposite literals)

I was wondering if there's a nice common generalization of these two classes of poly-time solvable SAT instance-types which is also poly-time solvable.

What other classes of SAT-problems might such a generalization cover?


texts: Is there a simple argument that shows that  the unique games conjecture implies the PCP theorem

texts:
how can one show that what is relation between "Unique games conjecture" and "PCP theorem"?
how does one explain "Unique games conjecture" is stronger form of "PCP theorem"?


texts: Edit distance algorithms that depend on alphabet

texts:
The best known algorithm for computing the exact edit distance between two strings is I believe an algorithm by Masek and Paterson that runs in time $O(n^2/\log^2 n)$, for binary alphabets.

Is there any algorithm that possibly by taking advantage of larger alphabet sizes (and potentially the possibility of few matches to explore) can run in time that might be strictly better than the above bound for large (i.e non-constant sized) alphabets ? Or is there some easy reason why this would be as hard as the case for a binary alphabet ?


texts: Busy beaver candidate elimination: Minimum space requirements

texts:
I'm currently enrolled in a course that introduces Turing machines. As I wanted to play around a bit, I wrote a little TM engine and had it search for busy beavers (it successfully found the 4-state 2-symbol BB listed in Wikipedia).

To more quickly eliminate bad candidates, I'm searching for conditions that imply indefinite runtime. I found a couple of filters already, but the number of indefinite runs is still rather high (indefinite, as in, either seemingly running forever or sometimes checked manually).

In this questions in particular I would like to inquire what space requirements a BB must have after a certain number of shifts. If it accessed less of the tape than this number, it can be dismissed directly. For this purpose, consider the tape length to extend exactly as far as the head went at most in either direction.

As simple upper bound I guess something like $N_{shifts} \leq {N_{TapeLength}}^{|Q|}$ could work, though I am not sure this is even correct. Also, it should certainly be possible to improve this boundary considerably.

Edit: I currently employ the following eliminations:

Static

Fixed first/last transition (A0-B1R,xx-H1R)
State enumeration ordering
All states in transitive closure of A
H in transitive closure of all states
Trap states
Equivalent states
Inability to change the tape

Dynamic

At either end of the tape, current state's transitive closure (using only 0-transitions) always directs further away


texts: Providence of pumping lemmas for regular languages

texts:
I'm looking to track down who discovered the following pumping lemmas for regular languages.
(where $p$ is the pumping constant.)

Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in \Sigma^*), w= u_1vu_2  \wedge |w| \geq p$
$\rightarrow\exists xyz, v=xyz \wedge |xy| \leq p \wedge y \not = \epsilon \wedge \mathbf{u_1xy^*zu_2} \subset L$

Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_0u_1 \ldots u_p(\in \Sigma^*), w = u_0u_1 \ldots u_p$
$\rightarrow \exists ij, 0 < i \leq j < p \wedge \mathbf{u_0u_1 \ldots u_{i-1}(u_iu_{i+1} \ldots u_j)^*u_{j+1}u_{j+2}\ldots u_p} \subset L$

Thank you


texts: Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

texts:
Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ so that $(v_i,u_i)$ is an edge in $G.$

The book Fractional Graph Theory by Scheinerman and Ullman has a number of wonderful results connecting graph theory to fractional graph theory, some of them having a flavor illustrated by the following result:

If $\chi(G), \chi_f(G)$ are the chromatic number and fractional chromatic number of a graph respectively, then

$$\chi_f(G) = \lim_{n\to\infty} \chi(G^n)^{\frac 1n}.$$

I am interested in the rate of convergence in this and other results of this kind. What can we say about how fast the sequence

$$\log \chi_f(G) - \frac 1n \log\chi(G^n)$$

goes to zero? I suspect it goes as $\frac{1}{\sqrt{n}}.$ If this is true, then what is

$$\limsup_n \sqrt{n}\left(\log \chi_f(G) - \frac 1n \log\chi(G^n)\right)?$$


texts: How is Cooks overlap argument applied in Vitányi's theorem?

texts:
In P.M.B. Vitányi, Relativized Obliviousness, MFCS'80 paper one can read that the proof of Theorem 1 is based on the overlap-argument of Cook, however I don't see how this argument is applied.

The paper defines a language that is decided by a turing machine with $k$ stacks. The movements of those heads are the same for each disjunct pair in the alphabet (for instance equal for $a$ and $b$, for $c$ and $d$,...). The alphabet itself is the union of $k$ of those pairs.

Furthermore the paper states that if we would recombine the alphabet into $k'<k$ groups (and the head movements need to be the same for each element in the same group). It would not be possible to evaluate the language in linear time. I think thats because in that case it doesn't make sense to have more than $k'$ heads (because they should move the same, one could simply concatenate several stacks into one stack). Furthermore after some time the data in a stack will be spread resulting in additional complexity to look back in the stack.

The author however states that this can be proven with Cooks overlap argument. I don't see how this argument is applied in this case?


texts: Complexity lower bound for regular languages

texts:
Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.

I would like to claim that determining the membership of a string of length $n$ in $L$ requires time $\Omega(n\log N)$. The dependence on $n$ is obvious -- I have to read the whole string, in general, to know if it belongs to a language. The $\log N$ factor is because to know what state I am in I need to write it down, and this takes time $\log N$.

This requires arguing that there is no faster way to determine membership in $L$ than to run its minimal DFA (implicitly or explicitly). I think such an argument can be formalized (via equivalence classes, for example), but perhaps I am being naive.

Question: Is the $\Omega(n\log N)$ lower bound correct?

Edit: let me make this more formal. Is there an infinite family of distinct minimal DFAs $A_1, A_2,..$ such that some algorithm simulating the $\{A_i\}$ on a deterministic RAM machine can determine membership of $x$ in $L(A_i)$ in time $o(|x|\log|A_i|)$, where $|x|$ is string length and $|A_i|$ is the number of states?

Edit2: Kaveh's and Aaron's answers seem to indicate that my lower bound is false. But I would love to see a non-trivial counter example. Suppose:
(a) I have a family of regular languages $\{L_n\}$
(b) each $L_n$ has a compact description (say, as an NFA) of size $poly(n)$, but the minimal DFA for $L_n$ has size $2^n$
(c) for each $n$, there is no fixed-length prefix that determines membership in $L_n$ (this rules out Kaveh's examples -- you really do need to read the whole string)

Can somebody give an example of a family $L_n$ satisfying (a,b,c) for which there is a TM taking $n$ and $x\in\Sigma^*$ as inputs and deciding $x\in?L_n$ in time $o(n|x|)$?
[Note that we've switched from RAM to TM as the computational model; $n$ is given in binary.]


texts:
I'd like to know what is the best method to parallelize the Dijkstra algorithm.

Thanks.


texts: Setting protocol parameters to achieve concrete security

texts:
Background

One issue with modern security proofs is that they are usually asymptotic. In other words, such proofs are usually formulated as follows: For any polynomial-time adversary $\mathcal A$, we can select a large enough security parameter $n$, such that the probability that $\mathcal A$ breaks the system is a negligible function of $n$.

Unfortunately, concrete values for parameters of the protocol cannot be readily deduced from such asymptotic proofs. For instance, the size of RSA modulus for a secure signature scheme may not be obtained from an asymptotic proof of security for the given scheme.

This issue was first formalized by Bellare and Rogaway, in their famous paper "The exact security of digital signatures: How to sign with RSA and Rabin." They provided a new type of analyzing and proving the security of some scheme, which they termed exact security. Soon after, numerous papers considered this notion, and gave various results on the exact security of signature schemes.

Assumptions

This question considers "exact security" for identification protocols. Since we're going to give concrete parameters, we have to make some explicit assumptions:

The time-complexity of entities is limited to $2^{80}$ operations.
Entities can perform up to $2^{30}$ operations per second.
The best algorithm for factoring an integer is GNFS. Given this assumption, factoring a carefully chosen $1024$-bit integer requires about $2^{86}$ operations, which is infeasible according to assumption 1.
In the identification protocol, there is a $30$-second time-out. The adversary can take its time to perform any preprocessing, but when engaged in protocol execution, he must reply within $30$ seconds, or time-out occurs and he fails. (This is in contrast to signature schemes, where the adversary is not faced with such restriction.)
During the lifetime of the system, the adversary may engage in at most $10^8$ identification sessions. He is successful if he can impersonate in at least one session, and he fails otherwise. In other words, a successful adversary is one whose success probability is at least $10^{-8}$.

Protocol and Proof

The honest prover has the factorization of an integer $n$, and the verifier is going to verify this. Let $L = \Theta(1)$ and $m = \Theta(|n|)$.

The identification protocol is the $m$-time repetition of a $\Sigma$ protocol. The challenge of the $\Sigma$ protocol is chosen randomly from the set $\{0,\ldots,L-1\}$.

Now, we are given the following "tight" security proof (the details of how this proof is obtained is unimportant):

For any adversary $\mathcal A$ whose time-complexity is $T$, and who breaks the identification protocol with probability at least $\epsilon$, there exists another adversary $\mathcal B$, whose (expected) time-complexity is $\frac{TLm}{\epsilon} + \Theta(|n|^2)$, and can factor $n$ with probability 1.

Question

  How can we use these assumptions and facts, to suggest concrete values for $|n|$, $L$, and $m$, such that the system is both efficient and secure? (The efficiency condition is included because the choice of extremely large parameters will obviously make the system secure.)


texts: Vehicle routing problem over Manhattan distances

texts:
I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot.

Is the following problem NP-hard

Problem :The distance constrained version of the vehicle routing problems over Manhattan distance metric considering an complete $N\times N$  grid or a grid where some edges are missing  ?
The grid graph is a weighted one.


texts: Hamiltonian cycle on a subset of 2D points, constrained by maximum total length

texts:
We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a subset of nodes which satisfies all of the following properties:

The total length of the cycle is less than D
The number of nodes included in the cycle is maximal
If there are more solutions satisfying 1. and 2., choose the one having the smallest cycle length

Note that weights of edges satisfy triangle inequality.

I know how to solve a standard shortest Hamiltonian cycle problem. However, I don't know how to choose a subset of points to start with. The naive solution would involve enumerating all subsets of points (NP) and attempting to construct a Hamiltonian cycle on every such subsets (NP again).

It seems totally intractable, even for a small number of nodes (I expect ~15 nodes). The only heuristic I can think of is constructing a minimum spanning tree for every subset, using the length of a MST as a lower-bound estimate and skipping subsets that obviously break constraint #1.

I hope a better solution exists, ideally without enumerating all subsets of nodes.


texts: Definitional equality of recursive function definition by "infinite unfolding"

texts:
The context is checking definitional equality in dependent type theory implementations.

Consider in Coq

Fixpoint predd(a: nat): nat :=
  match a with
  | O => O
  | S b => predd(b)
  end.

Fixpoint preddd(a: nat): nat :=
  match a with
  | O => O
  | S b => match b with | O => O | S c => preddd(c) end
  end.

Fixpoint predd2(a: nat): nat :=
  match a with
  | O => O
  | S b => preddd(b)
  end.

So predd is a function that recursively call itself and return O eventually. it is popositionaly equal to _ => O

preddd is the predd unfold once inside.

predd2 is just predd but calls preddd inside.

predd2 and preddd is not definitionaly equal in Coq. But can we have another definitional equality for recursive functions?

I have an idea of definitional equality of recursive functions, such that if the infinite unfolding of recursive definition is equal, then the two value is equal. such "infinite unfolding" seems can be made precise by requiring the finite unfoldings of values always have a similarity relation.

So, is there a sound definition of "definitional equality of recursive functions by infinite expansions"?

Can this be constructively implemented?


texts: Colourspace Quantisation using Voronoi Diagrams

texts:
I don't know if this counts as an objective question, but...

Say I have an image in RGB space $C=[0,1]^3$ and I wanted to resample it to a restricted palette of $P_1,\ldots,P_n\in C$: Would it be appropriate to check which Voronoi cell, generated by the $P$s and bounded by the edges of $C$, a particular colour fell in and then match that to its respective $P_i$?

Clearly generating the Voronoi diagram for the $P$s would be a bit excessive; but if $n$ is relatively small, we could just check which $P_i$ is closest to an arbitrary colour in $C$. That would be pretty efficient.

EDIT It occurred to me that this method could be extended to also dither the image: Check the distances from your colour $x\in C$ to each $P_i$. If $x=P_i$, for some $i$, then we're good; otherwise, calculate the metric $d(x,P_i),\forall i$ and, rather than choose the closest, weight them inverse-proportionally and then "probabilistically" pick one.

For example, restricting to $C=[0,1]$, we have $x=0.1$ and $P_1=0.01$, $P_2=0.3$. Then $\mathbb{P}(x\mapsto P_i) = d(x,P_i)^{-1}\div\sum_{j=1}^nd(x,P_j)^{-1}$; so $\mathbb{P}(x\mapsto P_1)\approx69\%$ and $\mathbb{P}(x\mapsto P_2)\approx31\%$.


texts: Preservation under Substitution with Telescopes

texts:
In the simply typed lambda calculus, one can show the following result, known as "preservation under substitution":

If $\Gamma \vdash v : \tau_1$ and $(x : \tau_1) \vdash t : \tau_2$,
then $\Gamma \vdash [v/x]t : \tau_2 $.

However, the proof of this relies on the property of permutation, that we can rearrange contexts and it will preserve typing of terms.

I'm wondering, can we prove a similar property for dependently typed languages? The problem is that, here, permutation may not hold, since telescopes are used in place of environments, and the types themselves may refer to variables. Moreover, since the types and terms overlap, we have to substitute in $\Gamma$ and $\tau_2$ as well.

Does anyone have a good reference to proving such a preservation property for a dependently typed language? Are there tricks that are used to avoid the permutations?


texts:
We say that $f$ has a degree $2d$ sum-of-squares certificate if $f=\sum_{i=1}^r (g_i(x))^2$, where for each $i\in[r]$, we have that $g_i$ is a polynomial of degree at most $d$. Thus showing that $f$ has a sum-of-squares certificate is one way of showing that $f\ge 0$.
Let $f_G(x)=\frac{1}{4}\sum_{(u,v)\in E}(x_u-x_v)^2$ for $x_u\in\{\pm1\}$ be the cut size function for an input vector $x\in\mathbb{F}_2^n$, denoting the side of the vertices across a cut and let $\mathsf{OPT}(G)=\max_x f_G(x)$.
Why does literature (e.g., http://web.stanford.edu/class/cs369h/lectures/lec5.pdf) go through work of showing that there exists a degree 2 sum-of-squares certificate for $\frac{\mathsf{OPT}(G)}{0.878}-f_G(x)$? Isn't this vacuously true since $\frac{\mathsf{OPT}(G)}{0.878}\ge\mathsf{OPT}(G)\ge f_G(x)$ or is the input vector $x$ to $f_G(x)$ relaxed in this case, i.e., $x\in\mathbb{R}^n$? Is it correct that any algorithmic statement, such as the Goemans-Williamson algorithm, still needs a separate statement of correctness independent of the degree 2 sum-of-squares certificate? If so, is the purpose of the certificate to lay the groundwork for showing that any minimally lossy rounding algorithm achieves $0.878-\epsilon$ approximation?
Thanks in advance!


texts:
You are playing the following game.

You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a product appears with price $p_d\leq B$ dollars. If your bid is larger than the price, you buy the product, i.e., $b_d\geq p_d$, and you lose $b_d$ from your budget. Otherwise, you will be left with the same budget as before but you don't buy the product, i.e., if $b_d<p_d$. The next day the same thing happens and so forth. You stop the game when you spend all of your budget or day $n$ is reached. Your objective is to buy as much products as possible with budget $B$.

Can we find a policy that competes against an adversary and buy a "good" number of products? Good here means, for example, a policy with low regret, so the difference between what the adversary bought and what you bought is not large. If we can't, what assumptions could we make to make the regret low?

My policy so far is:

For each day $d=1..n$, bid $b_d=B_r/(n-d+1)$, where $B_r$ is your remaining budget.

I was trying to find an input sequence that makes my policy perform badly but I didn't succeed (for large $n$). I think if $n$ is large, then we may reach a low regret with this policy. I am still trying to prove this.


texts: NFA to 2DFA: what are the upper and lower bounds?

texts: Suppose that one has an NFA (from, say, a regular expression).  What is the state complexity of turning it into a 2DFA?


texts: Homotopy type theory and Gödel's incompleteness theorems

texts:
Kurt Gödel's incompleteness theorems  establish the "inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic".

Homotopy Type Theory provides an alternative foundation for mathematics, a univalent foundation based on higher inductive types and the univalence axiom.
The HoTT book explains that types are higher groupoids, functions are functors, type families are ﬁbrations, etc.

The recent article "Formally Verified Mathematics" in CACM
by Jeremy Avigad and John Harrison
discusses HoTT with respect to
formally verified mathematics and automatic theorem proving.

  Do Gödel's incompleteness theorems apply to HoTT?

And if they do,

  is homotopy type theory impaired by Gödel's incompleteness theorem
  (within the context of formally verified mathematics)?


texts: Fast rates generally refers to generalization bounds interpolating between the $1/n$ consistent rate and the $1/\sqrt n$ agnostic rate. I am aware of two basic approaches for obtaining these: (1) Talagrand's Bernstein-type inequality for empirical processes and (2) PAC-Bayesian bounds. Question: are there other methods? More to the point, is there a clean, user-friendly set of notes on this, suitable for (advanced) students?


texts: Balls and Bins analysis in the m >> n regime.

texts:
It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have $O(\log n)$ balls in it. In general, one can ask about $m > n$ balls in $n$ bins. A paper from RANDOM 1998 by Raab and Steger explores this in some detail, showing that as $m$ increases, the probability of going even a little above the expected value of $m/n$ decreased rapidly. Roughly, setting $r = m/n$, they show that the probability of seeing more than $r + \sqrt{r\log n}$ is $o(1)$.

This paper appeared in 1998, and I haven't found anything more recent. Are there new and even more concentrated results along these lines, or are there heuristic/formal reasons to suspect that this is the best one can get ? I should add that a related paper on the multiple-choice variant co-authored by Angelika Steger in 2006 does not cite any more recent work either.

Update: In response to Peter's comment, let me clarify the things I'd like to know. I have two goals here.

Firstly, I need to know which reference to cite, and it does seem like this is the most recent work on this.
Secondly, it is true that the result is quite tight in the r = 1 range. I'm interested in the m >> n range, and specifically in the realm where r might be poly log n, or even n^c. I'm trying to slot this result into a lemma I'm proving, and the specific bound on r controls other parts of the overall algorithm. I think (but am not sure) that the range on r provided by this paper might suffice, but I just wanted to make sure there wasn't a tighter bound (that would yield a better result).


texts: Almost universal string hashing in $Z_{2^n}$ and sublinear space

texts:
Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$:

For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in \mathbb{Z}_p$. Dietzfelbinger et al. showed in "Polynomial Hash Functions Are Reliable" that $\forall x \neq y, P_a(h^1_a(x) = h^1_a(y)) \leq m/p$.
For $x_i \in \mathbb{Z}_{2^b}$, $h^2_{\vec{a} = \langle a_0 a_1 a_2 \dots a_{m+1}\rangle}(\vec{x}) = (a_0 + \sum a_{i+1} x_i \bmod 2^{2b}) \div 2^b$ for $a_i \in \mathbb{Z}_{2^{2b}}$. Lemire and Kaser showed in "Strongly universal string hashing is fast" that this family is 2-independent. This implies that $\forall x \neq y, P_\vec{a}(h^2_\vec{a}(x) = h^2_\vec{a}(y)) = 2^{-b}$

$h^1$ uses only $\lg p$ bits of space and bits of randomness, while $h^2$ uses $2 b m + 2 b$ bits of space and bits of randomness. On the other hand, $h^2$ operates over $\mathbb{Z}_{2^{2b}}$, which is fast on actual computers.

I'd like to know what other hash families are almost-universal (like $h^1$), but operate over $\mathbb{Z}_{2^b}$ (like $h^2$), and use $o(m)$ space and randomness.

Does such a hash family exist? Can its members be evaluated in $O(m)$ time?


texts: Why would the term "dynamically typed" be considered a misnomer?

texts:
In the book "Types and Programming Languages", the author writes:

The word "static" is sometimes added explicitly - we speak of a "statically typed programming language", for example - to distinguish the sorts of compile-time analyses we are considering here from the dynamic or latent typing found in languages such as Scheme, where run-time type tags are used to distinguish different kinds of structures in the heap. Terms like "dynamically typed" are arguably misnomers and should probably be replaced by "dynamically checked", but the usage is standard.

I am not sure if I understand this. Does the author mean that, in type theory, all programs are "statically typed"?


texts: VC-Dimension and sample complexity dependent on size of subsets

texts:
I have a range space $(X,R)$, were $R$ is a collection of subsets of $R$ and I have an upper bound $d$ to the VC-dimension of $(X,R)$. Suppose for simplicity that $X$ is finite. Given $\delta\in(0,1)$ and an integer $m>1$, I know that if I have a random sample $S$ from X of size $|S|=m$, then for $\varepsilon=\sqrt{\frac{d+\log(1/\delta)}{m}}$, we have
$\Pr\left(\exists r\in R ~:~ \left|\frac{|r|}{|X|}-\frac{|r\cap S|}{|S|}\right|>\varepsilon \right)<\delta$.

Notice how $\varepsilon$ does not depend on the sizes of the members of $R$. I was wondering whether I can get a smaller $\varepsilon$ if I know that all members of $R$ have a specific size, or better, if I know that there is a $\phi\in(0,1)$ sucht that $\frac{|r|}{|X|}=\phi$ for all $r\in R$.

Thanks.


texts:
Consider the problem of needing to support an $n$ integers array structure with two operations:

Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$).
Median() - return the median value of the array.

Suppose that the median functionality has to run in $O(1)$ time.

  What is the complexity of the set operation?

You may assume that the array is initialized to zeros, and you can preprocessing to initialize any data structure you want.

Implementing set in $O(\log n)$ time is straightforward.
I'm specifically interested in showing a lower bound.

The special case in which the set function may only increase the value of an element is also of interest.


texts: Relation between different "complexity theories" and complex systems theory

texts:
I know of at least 4 fundamentally different uses of the term "complexity theory":

the study of how hard a problem is to solve using some sort of computing machine (I am ignoring divisions within this category such as time vs space and parallel vs sequential models, etc.)
the expressiveness of a formal language
Kolmogorov complexity (which of course is uncomputable), or any attempts to define algorithms to approximate how hard it is to describe a phenomenon
complex systems theory, which honestly as far as I can tell is a little vague and imprecise about definitions, but seems to study the property of "emergence" or "the whole being greater than its parts"

Obviously it is linguistically possible that these are four completely different concepts that happen to share a name, but have there been any attempts to connect one of the first three definitions to the fourth (complex systems theory)?


texts: Is any chordal graph an incomparability graph?

texts:
I was confused by Wikipedia's definitions of "chordal graph", "interval graph", "string graph", "comparability graph", "incomparability graph" and the complements of these.
Wikipedia says "The complement of any interval graph is a comparability graph". So is any chordal graph an incomparability graph?

Is there a book or survey that contains detailed description of these sorts of different perfect graphs?


texts: Have people explored the problem of regular expressions being matchable?

texts:
I ran into a problem of determining if two regular expressions would have any possible matches in common. For example:

Fo*bar and Fo+bar

More specifically:

if $R_1$ and $R_2$ are two regular languages
can one determine if $R_1 \cap R_2 = \varnothing$ ?
And if one can what algorithms / methods can perform such a determination?
And are these algorithms / method NP hard?


texts: Gradual increase in hardness from P to PH of #SAT

texts:
We know that counting the number of solutions to $3-SAT$ is the canonical $\#P-Complete$ problem. Equivalently, it is the canonical $PH-Hard$ problem.

However, counting the number of solutions to $3-SAT$ that have weight at most $\log_2n$ (that is, have at most $\log_2n$ variables assigned to True) is a problem in $P$.

If we want to look at the complexity of counting solutions to $3-SAT$ with the maximum weight of an assignment, say $w$, as a parameter, it seems that:

$w = \mathcal{O}(\log_2 n):$ the complexity is $P$
$w = \mathcal{O}(n):$ Complexity is $PH-Hard$

It seems fair to tell that:

  $w = \mathcal{O}(\log_2^kn):$ the complexity of counting solutions to $3-SAT$ is complete (or maybe just hard) for $\Sigma^P_{k-1}$.

where $\Sigma^P_{k-1}$ is the $k-1$ level of the polynomial hierarchy.

Can anyone please help me see why the above should be true, or otherwise ? Any reference would also greatly help.


texts: complexity of factoring multivariate polynomials over Fn

texts:
recently multivariate polynomial factoring has been related to Polynomial Identity Testing / PIT (by Kopparty, Saraf, Shpilka).

  where is the complexity of factoring multivariate polynomials over finite fields analyzed/ surveyed, in particular for F2?

(eg is there a complete problem related to that, or does KSS result relate to factorization over finite fields etc?)


texts: Energy cost of adiabatic quantum computation

texts:
I'm not sure whether this question is completely on-topic, since it is a physics-related question. But I'll ask anyway and apologize if I'm off-topic.

In Adiabatic Quantum Computation is Equivalent to Standard
Quantum Computation the autors mention a tradeoff between runtime and energy:

"Observe that we have chosen our definition of running time to be $T · \max_s \lVert H(s)\rVert$ and not T.
Notice that if the Hamiltonians are multiplied by some factor, this divides the bound of Equation
2, and hence T, by the same factor. Hence, if the running time is defined to be T one would be able
to achieve arbitrarily small running times, by multiplying the Hamiltonians by large factors. Our
definition, on the other hand, is invariant under a multiplication of the Hamiltonian by an overall
factor, and so takes into account the known physical trade-off between time and energy.5

5This trade-off between time and the norm of the Hamiltonian (namely, the energy), is manifested in Schrödinger’s
equation whose solution does not change if time is divided by some factor and at the same time the Hamiltonian is
multiplied by the same factor."

But if I understand correctly, adiabatic quantum computation is completely reversible: by inverting the direction of time the system evolves back from the final state to the initial state.

Moreover, any adiabatic quantum computation process can be implemented (with arbitrary precision) in the conventional quantum circuit model, where all the gates are unitary and thus reversible.

According to Landauer's principle, reversible computation could be, in principle, executed without any energy consumption.

So my question is, what exactly the time-energy tradeoff in the choice of Hamiltonians for adiabatic quantum computation means?


texts: Bounded-input bijections of infinite sequences

texts:
Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution.

It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ using the properties of bicartesian closed categories. Andrej Bauer posted an explanation of what this means on his blog as "Constructive gem: juggling exponentials".

This bijection has an interesting property: it is "bounded-input" meaning that each component of the output depends only on boundedly many components of the input. However, for $k,l\geq 2$ it seems that this construction can only show that $ k^\mathbb{N} $ and $ l^\mathbb{N} $ are isomorphic if $k$ and $l$ are both odd or both even. This leaves open the question:

Is there a bounded-input bijection from $ 2^\mathbb{N} $ to $ 3^\mathbb{N} $?

Here is a short note describing the problem in more detail:
A conjecture concerning bounded-input bijections of infinite sequences.

Definitions:

A function $f : \prod_{i \in I} X_i \rightarrow \prod_{j\in J} Y_j $ is bounded-input if there exists
an integer $k$
such that each component of the output of $f$ depends only on at most $k$
components of the input.
More formally, $f$ is bounded-input if for each index $j \in J$
there are indices $i_1,\dotsb,i_k \in I$
and a function $f_m : X_{i_1}\times\dotsb\times X_{i_k} \rightarrow Y_j$
such that for all $x \in X$ the component
$f(x)_j$ equals $f_j(x_{i_1},\dotsb,x_{i_k})$.

A bijection $f$ is a bounded-input bijection if
it is a bounded-input function.

A bijection $f$ is a bounded-input isomorphism if
it and its inverse are bounded-input functions. This is also interesting.


texts: What is the best upper bound on the running time of the graph minor algorithm?

texts:
A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained from the famous result of Roberson and Seymour.

This result, as well as other algorithms for minor testing, is always cited with $f$ being some implicit computable function. I wonder what are the best known upper bounds on $f$, e.g., is it elementary?

In this discussion, user @Saeed mentions that $f$ is at most quadruple-exponential but provides no reference for this claim.


texts: What is known about the stabilizer rank of this simple state?

texts:
Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$,
$$ |\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$
What is known or conjectured about the stabilizer rank of such states? Clearly it is at most $\binom{n}{w}$, because the decomposition above is, in particular, a decomposition into $\binom{n}{w}$ stabilizer states.
If I understand correctly, there are currently no techniques for proving exponential lower bounds on the stabilizer rank of specific states, so I would also be interested references which merely speculate on the stabilizer rank of this (or related) states.


texts:
As a part of my curriculum, I am studying principles of DBMS from the book by Silberschatz and Korth.
A part of it is about Data Definition Language (DDL).

I understand, in normal terms, that DDL is any set of commands that modify the schema and not the actual data. That is the simple way of putting it. A certain paragraph in the book states, in addition to what I said, as below:

We specify the storage structure and access methods used by the database system
by a set of statements in a special type of DDL called a data storage and definition language.
These statements define the implementation details of the database schemas,
which are usually hidden from the users.

Can someone please explain to me what the first two lines mean ?
AFAIK, storage structure here would refer to the tables, in RDBMS, and access methods would refer to the views because they define what the user gets to see ?

Still, a simple explanation on this is welcome :)


texts:
Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$.  Does there exist a similar statement with DCFL, possibly with some restriction on the morphisms allowed?

(See, e.g., M. Autebert, J. Berstel, and L. Boasson. Context-free languages and
pushdown automata. In R. Rozenberg and A. Salomaa, editors,
Handbook of Formal Languages, volume I, chapter 3. Springer Verlag, 1997.)


texts: Is there an efficient algorithm for finding edges that are part of all hamiltonian paths?

texts:
I'm wondering if there is any algorithm known for finding edges in a graph that are part of all hamiltonian paths (operating under the assumption that the graph has at least one such path). Failing that, is there an algorithm for finding as many of these edges as possible, relaxing the requirement that all such edges are found?

One could find all hamiltonian paths in the graph, and then look at all the edges in those paths, but is there a better way?

One type of edge in this class obvious even to me is edges that are directed to vertices with in-degree 1 (or similarly edges from vertices that have out-degree 1). I'm particularly interested in directed graphs but the insight into the undirected version would also be helpful.

My apologies if this question is overly naive - I ran across this problem while doing microbial genomics, and any help would be greatly appreciated.

Thanks in advance,
ben


texts:
In the paper by [Erich Grädel and Martin Otto], the authors state that any formula in First Order Logic with two variables with counting quantifiers can be reduced to a formula of the form
$$ \forall x \forall y \alpha(x,y)\land \bigwedge_{i=1}^{m} \forall x \exists! y\beta_i(x,y)$$
Another reduction mentioned by [Ian Pratt-Hartmann] as
$$\forall x \forall y (\alpha(x,y) \lor (x \approx y)) \land \bigwedge_{1\leq h \leq m}\forall x \exists_{=c_h}y f_h(x,y) \land (x\not\approx y) $$
I am interested in these normal forms, because the reductions preserve the use of two variables only.
I would like to know whether are there other such reductions.
In particular, are there such reductions that would allow only
quantifiers of the type $\displaystyle\exists^{c}\forall$,
where $c$ is an arbitrary counting condition?


texts: Binary multiplication and parity convolution

texts:
This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a better solution to the question from Knuth vol. 2, 3rd edition, page 420 than that given in the book.

"Can the multiplication of polynomials modulo 2 be facilitated by using the ordinary arithmetic operations on a binary computer, if coefficients are packed into computer words."

Knuth gives a reasonably straightforward reduction which expands the number of bits in the input by a log multiplicative factor in the worst case.  Can this log factor be reduced?


texts: Is the exponent in the rectangular matrix multiplication convex?

texts:
My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a $n \times n^c$ and a $n^c \times n$ matrix. The authors show a graph of how the exponent in the time complexity depends on $c$. This graph is clearly convex. This would mean that one can upper bound the time complexity by linearly interpolating the exponent between that case of $c = 0.31389$ (where the exponent is 2) and $c=1$ (where the exponent is $\omega$). This would be useful for stating the time complexity of an algorithm I came up with.
However, they do not prove that the graph is convex. Is it convex? If so, any ideas as to how to cite this fact?
https://arxiv.org/abs/1708.05622


texts: How to calculate this string-dissimilarity function efficiently?

texts:
Migrated from stackoverflow.

Hello,

I was looking for a string metric that have the property that moving around large blocks in a string won't affect the distance so much. So "helloworld" is close to "worldhello". Obviously Levenshtein distance and Longest common subsequence don't fulfill this requirement. Using Jaccard distance on the set of n-grams gives good results but has other drawbacks (it's a pseudometric and higher n results in higher penalty for changing single character).

[original research]

As I thought about it, what I'm looking for is a function f(A,B) such that f(A,B)+1 equals the minimum number of blocks that one have to divide A into (A1 ... An), apply a permutation on the blocks and get B:

f("hello", "hello") = 0
f("helloworld", "worldhello") = 1   // hello world -> world hello
f("abba", "baba") = 2               // ab b a -> b ab a
f("computer", "copmuter") = 3       // co m p uter -> co p m uter

This can be extended for A and B that aren't necessarily permutations of each other: any additional character that can't be matched is considered as one additional block.

f("computer", "combuter") = 3       // com uter -> com uter, unmatched: p and b.

Observing that instead of counting blocks we can count the number of pairs of indices that are taken apart by a permutation, we can write f(A,B) formally as:

f(A,B) = min { C(P) | P ⊆ |A|×|B|, P is a bijective function, ∀i∈dom(P) A[P(i)]=B[P(i)] }
C(P) = |A| + |B| − |dom(P)| − |{ i | i,i+1∈dom(P) and P(i)+1=P(i+1) }| − 1

The problem is... guess what...

... that I'm not able to calculate this in polynomial time.

Can someone suggest a way to do this efficiently (possibly with minor modifications)? Or perhaps point me to already known metric that exhibits similar properties?


texts: Why was there a need for Martin-Löf to create intuitionistic type theory?

texts:
I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place?

Intuitionistic Logic (IL) and Simply-typed $\lambda$-calculus (STLC) and type theory in general predates the very existence of Martin-Löf himself! It seems that one can do everything in STLC that is doable in ITT (I may be wrong, but at least it feels that way).

So what was "novel" about ITT and how exactly did (or does) it advance the theory of computation? From what I understand, he introduced the notion of "dependent types", but it seems they were already there in STLC, in a way. Was his ITT an attempt at abstraction to understand the underlying principles of STLC and IL together? But didn't STLC already held do that? So, just why was ITT created in the first place? What is/was the point?

Here's an excerpt from Wikipedia: But I still don't get the reason behind its creation that didn't already exist before.

  Martin-Löf's first draft article on type theory dates back to 1971.
  This impredicative theory generalized Girard's System F. However, this
  system turned out to be inconsistent due to Girard's paradox which was
  discovered by Girard when studying System U, an inconsistent extension
  of System F. This experience led Per Martin-Löf to develop the
  philosophical foundations of type theory, his meaning explanation, a
  form of proof-theoretic semantics, which justifies predicative type
  theory as presented in his 1984 Bibliopolis book...

It seems from the excerpt that the reason was to develop the "philosophical foundations of type theory" - I thought this foundation already existed (or maybe I assumed it did). Was this the main reason then?


texts: Looking for Research in Cryptographic Computing

texts:
I recall reading in college about a nascent research area regarding cryptographic techniques for secure computing, relating to zero-knowledge proofs, but I am having trouble remembering the exact term.

In particular, you could imagine a theoretical untrusted computer that you could send encrypted data and an encrypted computer program, and that computer could execute the program on the data without being able to learn anything about the data or the program, and it will produce an encrypted output that it also cannot learn anything about. Further, once the output was received, you could verify the output is the result of the computation in a way that is computationally easier than the computation itself.

Obviously, such a general-purpose protocol is highly unlikely to be feasible, but I imagine various subsets are certainly possible, and I was looking for research on such techniques.

One such area of interest is Trusted Computing, which allows some hardware-level assurances, especially if we relax requirements on the system having access to the data and program; but that is not leading me to any cryptographic models for proofs of accurate computation.

Similarly, problems in NP satisfy some of these requirements, since verification of a solution is in P. So I would expect that certain cryptographic techniques could be use for such problems to make assertions about data security in some cases.

Ultimately, I am looking for keywords relating to this type of research.


texts: Decompose a complete graph into smaller cliques

texts:
The following exercise problem is from the book of D.B.West which i could solve:

If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6.

So my questions are the following,

If a complete graph of $n$ vertices can be decomposed into cliques of size $p$ with $p\leq n$ then what should be the relation between $n$ and $p$.

What is the official name of this problem in the literature ?

Any links/hints would be helpful.


texts:
I, like many people, am a keen user of mathematical software such as Mathematica and Maple. However, I have become increasingly frustrated by the many cases where such software simply gives you the wrong answer without warning.  This can occur when performing all sorts of operations from simple sums to optimization amongst many other examples.

I have been wondering what could be done about this serious problem. What is needed is some way to allow the user to verify the correctness of an answer that is given so that they have some confidence in what they are being told. If you were to get a solution from a math colleague she/he might just sit down and show you their working. However this is not feasible for a computer to do in most cases. Could the computer instead give you a simple and easily checkable witness of the correctness of their answer?  Checking may have to be done by computer but hopefully checking the checking algorithm will be much easier than checking the algorithm to produce the witness in the first place.  When would this be feasible and how exactly could this be formalized

So in summary, my question is the following.

  Could it be possible at least in theory for mathematical software to provide a short
  checkable proof along with the answer you have asked for?

A trivial case where we can do this immediately is for factorization of integers of course or many of the classic NP-complete problems (e.g. Hamiltonian circuit etc.).


texts: What are some interesting applications of homotopical algebra in theoretical computer science?

texts:
I am an homotopy theorist, interested in computer science.

I would like to ask what are some interesting applications of homotopical algebra (model categories, infinity categories, simplicial categories, etc) in theoretical computer science?


texts: Lower bound on light spanners in Euclidean space reference

texts:
It is well-known that Euclidean space of dimension $d$ has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}\cdot w(MST)$ (see Chapter 14  of Geometric Spanner Network book by Narashimhan and Smid).

However, I can not find any reference on the lower bound, that showes there is a set of points in dimension $d$ Euclidean space whose $(1+\epsilon)$-spanner has weight at least $\epsilon^{-\Omega(d)}\cdot w(MST)$. Is this a folklore result?

A point set that I came up with that satisfies the lower bound is a uniform point set in a unit ball where the pairwise distance is at least $2\epsilon$. This point set only has  $\epsilon^{-O(d)}$ points, but we can have many unit balls arranged in a path-like fashion to get a bigger point set.


texts: What is logic programming and does it really add anything new to the logic?

texts:
I am acquinted with the basics of such notions as logic programming, monotonic and non-monotonic reasoning, modal logic (especially dynamic logic) and now I am wondering - does logic programming provides anything new to any logic?

As far as I understand, then (at least in dynamic logic) the logic programming refers to the formalization of state transitions (by actions, i.e. - logic programing can be understood just as logic about actions). But the same notion "logic programing" seems to be in use even in domains, where there is not state transition, just exploration of one state (or set of states - in case then the initial set of premises are vague enough to describe more than one state). It seems to me that some authors simply use  the notions "logic programming" for describing the procedure how to evaluate the query (I am reading currently about defeasible logic programming). But such procedure (although practical indeed) does not add anything new to the underlying logic. E.g. there is notion of "rational closure" (e.g. used for adaptive logics; just the consequence set for some set of premises) which should contain all the possible knowledge about state and therefore all the possible results of "logic programing" (if it is indeed perceived just as state exploration, derivation).

So - the question is - does logic programming provides anything new to the logic and does every logic (to be completely understood and readied for applications) need to have its own logic programming?

Maybe I am just missing the point...

Just for reference I find the following works interesting about this subject, if there are more along this line, then it would be great to hear!

Mathematical Aspects of Logic Programming Semantics by Pascal
Hitzler, Anthony Seda
Dynamic Logic (Foundations of Computing) by
David Harel, Dexter Kozen, Jerzy Tiuryn
Adaptive Logics for
Defeasible Reasoning: Applications in Argumentation, Normative
Reasoning and Default Reasoning (Trends in Logic) by Christian
Straßer

The answer to such question can have practical applications as well - e.g. it can help to define some kind of formal semantics of the "business rules" (declarative programming paradigm that is used more and more in business applications, e.g. IBM ILOG, JBoss Drools, Oracle Business Rules, PHP and Python also have their own rules engined) and going further - this can be useful for cognitive robotics as well.


texts: Random variates generation in discrete-event simulation models

texts:
In discrete-event simulation, most university textbooks (e.g., Law & Kelton, Banks etc.) state that for generating variates for each random variable (e.g., interarrival time, service time etc.) in the simulation model (e.g., using the inverse transform method and a uniformly random variate), we should use a different sequence of pseudo-random numbers for each random variable. I guess that requirement is to ensure the randomness of the generated numbers, since pseudo-random number generators are periodic, i.e., the same random number will occur again after a specific period (that is, after a period, the sequence repeats itself). Therefore, using a different sequence of random numbers for each random variable/purpose, it reduces the chance that a particular random number will be used more than once for the generation of the variate of the particular random variable.
However, since recent pseudo-random number generators, such as Mersenne Twister, have really long periods (e.g., Mersenne Twister has a period of 2^19937 – 1), I believe that the requirement for using different random number sequences, one per random variable, is no longer required. In a modern simulation model with a great number of random variables, this would be impractical and the use of modern pseudo-random number generators such as Mersenne Twister, ensure long periods. Thus the same sequence of random numbers  can be used for generating variates for all of the random variables in the simulation model, even for long simulation runs. Of course for each independent replication (i.e., each simulation run) a different seed and thus a different sequence should be used.
I would love to have your thoughts on this matter, do you agree/disagree?


texts: Integer programming with a fixed number of variables

texts:
The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of the data.

I interpret that as follows.

Integer programming in general still is NP-complete but if my typical problem size at hand (say about 10.000 variables, an arbitrary number of constraints) is feasible in practice then I could construct an algorithm that scales polynomially in the number of constraints but not in the number of variables and constraints.
The result is also applicable for binary programming since I can force any integer to 0-1 by adding an appropriate constraint.

Is my interpretation correct?

Does this result have any practical implications? That is, is there an implementation available or is it used in popular solvers like CPLEX, Gurobi, or Mosek?

Some quotes from the paper:

  This length may, for our purposes, be defined to be n · m · log(a +
  2), where a denotes the maximum of the absolute values of the
  coefficients of A and b. Indeed, no such polynomial algorithm is
  likely to exist, since the problem in question is NP-complete

  [...]

  It was conjectured [5], [10] that for any fixed value of n there
  exists a polynomial algorithm for the solution of the integer linear
  programming problem. In the present paper we prove this conjecture by
  exhibiting such an algorithm. The degree of the polynomial by which
  the running time of our algorithm can be bounded is an exponential
  function of n.


texts: Fourth(?) moment method for minimum value

texts:
I would like to lower bound the quantity $\Pr[X\ge t, Y\ge t]=\Pr[\min(X,Y)\ge t]$ using the small moments of $X$, $Y$ and $XY$.
In particular I am interested in the case where $E[X]=E[Y]=0$, but $E[X Y]>0$.

In "The Fourth Moment Method" Berger shows that if $\frac{E[X^4]}{E[X^2]^2}\le b$, then $\Pr[X\ge \sqrt{E[X^2]}/(4\sqrt{t})]\ge1/(4^{4/3}t)$.
Alternative formulations of this principle include the Paley–Zygmund inequality.

Using the fact that $\min(X,Y)=\frac12(X+Y-|X-Y|)$, we get that that
$$
E[\min(X,Y)^2] = E[\min(X^2,Y^2)] = \tfrac12\left(E[X^2+Y^2]-E[|X^2-Y^2|]\right),\\
E[\min(X,Y)^4] = E[\min(X^4,Y^4)] = \tfrac12\left(E[X^4+Y^4]-E[|X^4-Y^4|]\right).
$$
Now using $\frac{E[X^2]^{3/2}}{E[X^4]^{1/2}} \le E[|X|] \le \sqrt{E[X^2]}$ we can get a bound:
$$
\frac{E[\min(X,Y)^4]}{E[\min(X,Y)^2]^2}
= 2\frac{E[X^4+Y^4]-E[|X^4-Y^4|]}{(E[X^2+Y^2]-E[|X^2-Y^2|])^2}
\le 2\frac{E[X^4+Y^4]-\sqrt{E[(X^4-Y^4)^2]}}{\left(E[X^2+Y^2]-\frac{E[(X^2-Y^2)^2]^{3/2}}{E[(X^2-Y^2)^4]^{1/2}}\right)^2}.
$$

Besides being ugly, this has ended up using the eighth moment of $X$ and $Y$, rather than just the fourth.
Is this necessary? Or is there a nicer way taking better advantage of the $\min$ function?

Update:
We may wonder what the ideal result would be. If we let $\hat{X}=[X,Y]^T$, $\Sigma=\text{Cov}(\hat X)$ and $Z=\hat X ^T\Sigma^{-1}\hat X$, then Markov's (or the multivariate Chebyshev) inequality tells us $\Pr[Z \ge \epsilon] \le E[Z]/\epsilon=2/\epsilon$.
If we assume $\text{Var}[X]=\text{Var}[Y]=1$ then $\min(X,Y)\ge t$ implies $Z\ge t^T\Sigma^{-1}t=\frac{2t^2}{1+\text{Cov}(X,Y)}$; and so $\Pr[X,Y\ge t]\le\frac{1+\text{Cov}(X,Y)}{t^2}$.

With Paley–Zygmund we then get $\Pr[Z\ge 2t] \ge 4(1-t)^2/E[Z^2]$, which is a fourth moment bound. Of course this is a lower bound on the entire space outside the ellipse, however we might(?) hope that it is also correct up to a constant factor for any convex region at distance t, if $X$ and $Y$ are nice enough?


texts: Special Properties Of DAWGs with Unique Elements

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


texts: Overlapping BFS Layers in Dominating Set with Baker's Technique

texts:
(I'm not sure if this is an appropriate question for TCS.SE, but I'm not sure what is more appropriate).

When using Baker's Technique to find an approximation to the minimum dominating set of a planar graph, why must we overlap 2 BFS layers in every partition? I understand that for vertex cover each partition needs to overlap 1 layer to handle cases where an edge in the overlapped layer can only be covered by another vertex in the layer.

However, to my knowledge, vertex cover is just a reduction of dominating set, and any vertex cover is also a dominating set. Why do we need to overlap 2 layers for dominating set?

Of course, links to papers are great too--I just haven't found anything explaining the reason yet.

EDIT: David has a great answer below. There's also a paper describing the issue (with pictures) and a correction to Baker's original algorithm for Dominating Set here: http://www.mdpi.com/1999-4893/6/1/43 (PDF link)


texts: Constructing a large bit-vector set with the following property

texts:
I would like to construct a set $S\subseteq\{0,1\}^{2n}$ that satisfy the property:

$$\forall x\neq y\in S\ \ \exists k\in [n]:\forall i,j\in[n], \sum_{t=k+i}^{2n}x_t\neq\sum_{t=k+j}^{2n}y_t$$

In other words, for every two vectors in $S$, there exists $k\in\{0,1,\ldots,n\}$ such that if we delete the first $k$ bits of $x,y$, we can't get the same number of $1$'s in both, after deleting some additional $i,j\in\{0,\ldots,n\}$ bits accordingly.

The motivation for the problem comes from a showing lower bound  for a streaming problem in which the answer may rely on approximate sliding window whose size can vary between $n$ and $2n$.

A simple construction for such $S$ is $$\{0^{n+b}1^{n-b}\mid b\in[n]\},$$

As every two words $0^{n+q}1^{n-q}$,$0^{n+a}1^{n-a}$ satisfy the condition for $k=0$.

This gives a lower bound on the size of such $S$ of $n+1$.

If I am not mistaken (didn't get to fully prove it yet), my algorithm implies an upper bound of $O(n^2)$.

  What is the maximal size of a set $S$ that satisfies the above property?