texts: Relative consistency of various Martin-Löf style type theories

texts:
I am wondering about relative consistency of various Martin-Löf type theories, when compared to one another, I will use MLTT for the intensional Martin-Löf type theory with $\Pi$, $\Sigma$, $\mathbb{N}$, Id, unit and empty types.
Let's formulate consistency as lack of term of empty type and relative consistency being a proof that given the rules of itself T1 and assumption that they are consistent, we can deduce that another type theory T2 is consistent.
So here are the variants.

MLTT + Predicative Set universes  (ala Agda without induction recursion)
MLTT + Predicative (S)Prop and Set universes (ala Agda without induction recursion and with -prop)
MLTT + Impredicative (S)Prop (ala Coq)
MLTT + Impredicative Set at the bottom (ala Coq with -impredicative-set but without Prop)
MLTT + Impredicative (S)Prop + Impredicative Set (ala Coq with -impredicative-set)
Combinations of the above with large (agda-style) induction-recursion

In the last case I am not even aware of consistency results for the combination with impredicative universes.
Related question seems to be:
Relative consistency of PA and some type theories, but the answer there does not take into account universes.
I am mostly looking for references discussing the relative consistency of these.


texts: Space time lower bound with $\mathsf{PSPACE}$ oracle

texts:
Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem?

What is largest complexity class oracle that a single tape Turing machine could need so that it will need $\omega(1)$ Space time resource (as against separate space and time) to solve $\mathsf{NP}$-complete problem?


texts: A well-known instance of overcomplete dictionaries

texts:
sparse representation is:
A signal can be represented as a linear combination of basis functions where the set of basis functions is called dictionary and data samples are much more than their features. Mathematically, in the system of linear equations $Y=DX$ where $Y \in \mathbb{R}^{n \times N} (n \ll N)$ we seek a dictionary that results in sparse representation of $Y$.

Digging the history of sparse representation, my take is it all started by using transforms as D; wavelet, Fourier and such. They were good in the application they were designed for but a generalization to a wider area was a failure. So a combination of basis functions was used as a dictionary D, an overcomplete one with more basis functions than the size of each basis function. There are lots of examples of different transforms and their result. But I cannot think of an example for an overcomplete dictionary. Is it due to the fact that they are learned and there is no special dictionary to be used? I mean, given an initial dictionary, it is learned in an iterative process to better fit the data, is there a well-known instance of such a dictionary like the case JPEG2000 using wavelet packets as D?


texts: Implications of approximating the determinant

texts:
It is known that one can compute exactly the determinant of an $n\times n$ matrix in determinstic $\log^2(n)$ space.
What would be the complexity implications of approximating the determinant of a real matrix, of norm at most $1$ ($\left\|A\right\|\leq 1$) in randomized logarithmic space, up to say, a $1/\text{poly}$ accuracy?

In this respect, what would be the "correct" approximation to ask for - multiplicative or additive?  (see one of the answers below).


texts: Does Dirac's theorem on Hamiltonian cycles only apply to undirected graphs?

texts:
Does Dirac's theorem on Hamiltonian cycles only apply for undirected graphs? If the theorem applied to directed graphs, the graph with the following adjacency list should have a Hamiltonian cycle, but I can't find one.

  $0$: $1$ $2$ $3$

  $1$: $2$ $3$

  $2$: $1$ $3$

  $3$: $1$ $2$


texts: NP-hardness of a graph partition problem?

texts:
I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic?

Here $E$ is partitioned into two disjoint sets $E_1$ and $E_2$. Sets $V_1$ and $V_2$ are not necessarily disjoint. $E1∪E2=E$ and $V1∪V2=V$.

This problem is at least as hard as Graph Isomorphism Problem. I guess it is harder than Graph Isomorphism but not NP-hard.

  Is this partition problem $NP$-hard?

EDIT 3-3-2012: Posted on MathOverflow.

EDIT 3-5-2012: It turns out that the reference in Diego's answer is one of the unpublished results. After some digging, I found a reference to it in The NP-Completeness Column: An Ongoing Guide by David JOHNSON (page 8). I found other papers  that cite the NP-completeness result of Graham and Robinson as unpublished.


texts: Practical worst-case polylogarithmic dynamic orthogonal range queries?

texts:
There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures typically don’t perform well in practice due to the high constant factors involved.

On the flipside, there’s the R-tree, which solves orthogonal range searches quickly in practice on the types of inputs typically encountered. However, it doesn’t have a nice known upper bound on the cost of searches.

Are there any data structures known that represent the “best of both worlds” in the sense that they have nice provable polylogarithmic bounds on their query costs and run quickly in practice?

Thanks!


texts:
This is a followup to David Eppstein's recent question and is motivated by the same  problems.

Suppose I have a dag with real-number weights on its vertices.  Initially, all of the vertices are unmarked.  I can change the set of marked vertices by either (1) marking a vertex with no unmarked predecessors, or (2) unmarking a vertex with no marked successors.  (Thus, the set of marked vertices is always a prefix of the partial order.)  I want to find a sequence of marking/unmarking operations that ends with all vertices marked, such that the total weight of the marked vertices is always non-negative.

How hard is finding such a sequence of operations?  Unlike David's problem, it's not even clear that this problem is in NP; in principle (although I don't have any examples) every legal move sequence could have exponential length.  The best I can prove is that the problem is in PSPACE.
Is the unmarking operation actually unnecessary?  If there is a valid move sequence, must there be a valid move sequence that never unmarks a vertex?  An affirmative answer would make this problem identical to David's.  On the other hand, if unmarking is sometimes necessary, there should be a small (constant size) example that proves it.


texts: Understanding the talks in Conferences and Workshops

texts:
I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors.

At the end of the talk as usual some people will ask questions and speaker will answer them. But my problem is I am not understanding most of the questions and answers. Even if I ask any question I am unable to understand the answer which given by speaker.

Can somebody share their experience and suggestions to my problem.


texts: Deterministic one way communication complexity for message with arbitrary length

texts:
Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message.
I have been looking into communication complexity material but everything that I found assumes that the receiver (i.e. Bob) knows the length of $n$ in advance.
I would really appreciate a pointer to martial that I should be looking into.
Thank you in advance.


texts: Lower Bounds on Running time of Graph Algorithms

texts:
Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/
models of computation ? I am not looking for the NP-Hardness results here.

Following is a result that I could find [see ref L92]:

3-Coloring of an n-cycle requires $\Omega(\log^*{n})$ time.

I was curious to know whether there has been any progress/work in the direction of getting
lower bounds for problems like: Shortest Paths(with/without negative weights), Mincut,
s-t Maximum flows, Maximum (cardinality/weighted) matching. Any references related to
this are very much appreciated and helpful.

Reference

[ L92 ] N. Linial, Locality in distributed graph algorithms, SIAM Journal on Com-
puting, 1992, 21(1), pp. 193-201

EDIT: As suggested by Robin Kothari in the comments, I am making the question more directed.


texts: Dynamic programming algorithm for NP-complete problem

texts:
Hello everybody here is a problem i have approximated but would like to hear your opinion about. Perhaps someone finds a better solution than me :)

Given a Graph G with undirected edges:

Divide it into the minimal number of sets, so that :

No two nodes in a set are connected to each other
Every node is member of at least one set
for any two distinct nodes x and y, there is a set which contains exactly one of x and y. All nodes appear in a different combination of sets. That means node x and y do not appear only in the same sets together. if you expressed the appearence of the nodes as a bit pattern, the bit pattern would differ at least in one digit.

Put another way, we want to find a 0-1 matrix with $|V|$ rows and a minimum number of columns, such that (1) each column denotes an independent set in the graph $G$, (2) every row has at least one $1$ in it, and (3) every pair of rows differs in at least one bit. Note it is trivial to give an $|V| \times |V|$ matrix of this kind for every $G$: just take the identity matrix. The problem becomes interesting when the number of columns can be made much smaller.

Example: B has no adjacent nodes, D=>A, A=>D

solution:

A B /
/ B D

A : 1 = 10
B : 2 = 11
D : 3 = 01

not a solution:

A D B
/ D B

A : 1 = 10
D : 2 = 11  _ same combination of
B : 3 = 11  / sets

D and B appear in the same combination of sets. D appears in the second and third set, as well as B.

what i need is something of a dynamic programming equation or another kind of solution that gives me an exact solution to this problem. I know that it is NP-hard, so an exponential solution is fine with me. ( i did a reduction onto Clique and Max-Sat)

An optimal solution would give me the composition of the sets, so that the number of sets is minimal, yet all nodes are part of the solution.

thanks for your help.


texts: Is the problem "Binary Sorted Min Sum" already known under an other name?

texts:
A computer scientist oriented toward applications gave me the following problem:

  Given a positive integer $n>0$, an increasing function function $f$
  and a decreasing function $g$, both defined on $[1..n]$, compute the
  minimal index $i\in[1..n]$ such than $f(i)+g(i)$ is minimal among
  values $\{f(j)+g(j)\}_{j\in[1..n]}$.

I named this problem "Binary Sorted Min Sum" for lack of a better name. The computational complexity of this problem in the worst case over instances of size $n$ is clearly $2n$ evaluations, $n-1$ comparisons, and $n$ additions, all within $O(n)$. A linear number of instances of this problem occur in the core of my colleague's solution, which complexity he analyzes as $O(n^2)$.

Inspired by the fact that many instances of this problem can be solved in sublinear time (e.g. when $f$ is increasing much faster than $g$ is decreasing, one can certify that the minimum is at index $1$ in one single comparison, 4 accesses and 2 sums), I got some interesting adaptive results, showing tight bounds within $O(\delta\lg(n/\delta)$ for some parameter $\delta\in[1..n]$ measuring the difficulty of the instance, implying both the $\Theta(n)$ bound in the worst case and the $\Theta(\lg n)$ bound in easy instances: it is actually quite similar (but not reducible, it seems) to the "Binary Sorted Intersection" problem which I studied previously.

A quick search on "Binary Sorted Min Sum" did not yield anything meaningful, yet the problem is quite simple, so I am wondering if someone introduced it before under another name?


texts: What is the probability that a random Boolean function has a trivial automorphism group?

texts:
Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.

Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there anything known for quantities of the form $Pr_f(G  \leq Aut(f))$ for some group $G$?


texts: Bounded Post Correspondence Problem NP-Complete Proof

texts:
I'm looking for a simple proof that shows that the Bounded-PCP problem belongs to NP-Complete as many text books say so.
It is clear to me that the problem is decidable but I cannot find any reduction from an NP-Hard problem to this one.

Moreover, the verifying algorithm might go through a series of N indexes which is exponential in comparison to the input size (N) which is logN, so how can this problem be in NP?

Thanks.


texts: In what sense are Scala's Try[T] and Future[T] dual?

texts:
In a recent course based on Scala I found a hint that the Scala types Try[T] and Future[T] are dual. This was explained only informally and the reader was referred to duality in category theory for a more precise definition.

I have some basic knowledge of category theory but I cannot see how these two types can correspond to categories that are dual to each other.

So, what categories correspond to the Scala types Try[T] and Future[T], and why are these categories dual?


texts:
For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$.
We define $P(k,n)$ to be the minimum of $p(M,n)$ taken over all DFAs $M$ having $k$ states. I want to know asymptotic bounds for $f$ such that $P(k,f(k)) \to 1$ exponentially fast (so there is  $c <1$ such that $P(k,f(k))>1-c^k$ asymptotically). I know how to prove that $f(k) = k^42^{k^2}$ suffices. For any two states in a DFA, there will exist a string with length at most $k^2$ which synchs the two states, thus the probality that $k^2 2^{k^2}$ random bits will not synchronize a new pair of states is at most $1/e$. The rest quickly follows.
Can this upper bound be improved? What kind of lower bounds are possible?


texts: hardness of approximation result for a Min-CSP, by reduction from PCPs

texts:
Reduction from PCPs allow us to prove hardness of approximation results for a number of constraint satisfaction problems. I've seen such a reductions only for Max-CSPs. Is this possible only for Max-CSPs? In other words, can someone get hardness of approximation result for a Min-CSP (for example, Vertex-Cover or sparsest-cut) by reduction from PCPs?

If it is always possible to convert a Min-CSP to an equivalent Max-CSP, then maybe this answers my question. But, I don’t know whether it is always possible or not.


texts: Generating hard satisfiability problems with given constraint graph

texts: Is there a systematic way to tune the hardness of a set of satisfiability problems (say 3-SAT or MAX2SAT) where the constraint graphs are always embeddable into a fixed given graph?


texts: Is this problem mappable to 3SAT or is it weaker than 3SAT?

texts:
Consider a variant of a satisifiability problem.

Given n dimensions (n >= 3, n < 10,000 think of n as large but finite)
The range of each dimension is either an interval over the integers or an interval over the fixed-point decimals (which can be mapped to be the integers).
Given a truth predicate which can use these operations:

  (<, =>, ==, !=, *, +, -, /, if/then, and}

Example in Prolog of a predicate of truth:

Predicate(V1, V2, V3) :-
   V2 =< V3,
   V1 * 5 =< V3,
   V1 * 50 >= V3.

Is this mappable to 3SAT?
Is this less hard than 3SAT?
What are pragmatic and efficient solutions to select some true point (or set of points) in the space?


texts: Deterministic Parity Automata require unbounded index

texts:
Deterministic parity automata $(Q, \Sigma, q_0, \Delta, c)$ are powerful enough to recognize all $\omega$-regular languages. However, the number of priorities they require for a language can become arbitrarily high. For example, the languages $L_{i,j} = \{ \alpha \in \{i, \dots, j\}^\omega \mid \text{The highest number occurring infinitely often in } \alpha \text{ is even} \}$ require at least $j-i+1$ priorities. I was not able to prove this theorem so far by myself, in particular I am stuck at the case that the automaton uses exactly the priorities from $i+1$ to $j$. I could not lead this assumption to a contradiction.

Any help or link to a paper would be appreciated.


texts:
Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$.

Furthermore, consider two polytopes

$$\begin{align*}
P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\
P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\}
\end{align*}$$

where $f$'s and $g$'s are affine mappings. Namely, they are of the form $\vec{c}\cdot \vec{x} +d$. (We note that $P_1$ and $P_2$ are polytopes because they are "affine mappings" of the polytope $A\vec{x}\leq b$.)

The question is, how to decide whether $P_1$ and $P_2$ are equal as sets? What's the complexity?

The motivation of the problem is from sensor networks, but it seems to be a lovely (probably basic?) geometry problem. One can solve this in exptime, possibly by enumerating all the vertices of $P_1$ and $P_2$, but is there a better approach?


texts: Known generalizations of Gauss pivot method?

texts:
The well-known Gauss pivot method can be used to solve a system of linear equations over a field. I'm aware of two extensions of this method: (i) the Büchberger algorithm for computation of Gröbner bases, (ii) the resolution algorithms for CSPs with Maltsev polymorphisms (see 'Malt'sev Constraints made Simple' by V. Dalmau, 'Constraint satisfaction on finite groups with near subgroups' by T. Feder).

I would like to hear about other variants/extensions of Gauss pivot to settings where we don't have an explicit field/group structure. For instance, can we solve efficiently a system of equations over a permutation group by a similar approach? This problem does not fall in case (ii) above as in general the solutions of an equation will not form a coset, although it should contain problem (ii) as a special case.


texts: Arguments for existence of one-way functions

texts: I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-way functions?


texts: Is there a formal proof that quantum computing is or will be faster than classical computing?

texts: Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?


texts: Decide if number is negative (in URM machine like language)

texts:
So I'm learning to program in an assembly language for an abstract machine wich is very similar to an URM Machine.
An URM machine has 3 basic instructions (or 4 in some literature):
        To zero a register: Z(r)
        To increment a register: S(r)
        To Jump to a line or label if registers r1 and r2 contain the same value: J(r1,r2,l)
Now, my abstract machine is even weaker because, for jumping it only alows a comparison between a register and the literal 0.
To compensate it allows to assign any value to a register (not just zero as in the URM) and basic arithmetic operations.
Both machines allow an infinite number of registers.

I was able to write a program that successfully compares two positive numbers and returns the maximum.
Now I would like to make my program able to receive also negative numbers.

My question: How can I check if a number is negative? Is it even possible with only these instructions?

I confess that I'm not very clever with this kind of low level languages...

My maximum program follows: (input goes on r1 and r2 and output comes on r3)

maximo(){
    r5 := r1 - r3
    jump (r5,0,maxr2)

    r5 := r2 - r4
    jump (r5,0,maxr1)

    r3 := r3 + 1
    r4 := r4 + 1
    jump (r1,r1,maximo)
}

maxr1(){
    r3 := r1
}

maxr2(){
    r3 := r2
}

Thank you!


texts: $\mathcal{MA}$ in terms of $\mathcal{PCP}$

texts:
The probabilistic proof system $\mathcal{PCP}[f(n),g(n)]$ is commonly referred to as a restriction of $\mathcal{MA}$, where Arthur can only use $f(n)$ random bits and can only examine $g(n)$ bits of the proof certificate sent by Merlin (see, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP).

However,  In 1990 Babai, Fortnow, and Lund proved that $\mathcal{PCP}[poly(n), poly(n)] = \mathcal{NEXP}$, so its not exactly a restriction. What are the parameters ($f(n),g(n)$) for which $\mathcal{PCP}[f(n), g(n)] = \mathcal{MA}$?


texts: Concurrent data structures vs. Distributed data structures

texts:
In the context of multi-processor/multi-threaded systems, there are plenty of well-studied concurrent data structures, including stacks, queues, linked lists, etc. Here is an excellent survey on concurrent data structures by Mark Moir and Nir Shavit.

Even though they use a "shared memory" model similar to the one used by concurrent data structures, I can only find information on a few distributed data structures: those data structures designed specifically for distributed systems. Such data structures are typically characterized by replication and certain consistency models. The examples I have found include

An Optimized Conflict-free Replicated Set (arXiv, 2012)
Randomized Shared Queues (PODC, 2001)

My questions are

What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?
Did I miss other distributed data structures in the literature?


texts: Is every well-founded simplification order a well-partial order?

texts:
I'm contemplating the proof of Kruskal's Tree Theorem, as presented in the book "Term Rewriting and All That." They use it to prove that every simplification order is well-founded: first by showing that the homeomorphic embedding is a wpo, and then by showing that every simplification order contains the homeomorphic embedding.

It seems to me that the only properties they use of the homeomorphic embedding in the proof are that it's well-founded, and that each term is > its subterms -- exactly the property that defines a simplification order. Does the same proof work if I instead use an arbitrary simplification order*? Does this mean every simplification order is a well-partial order*?

*One caveat: restricting terms to a finite set of variables, because it's trivial to construct a counterexample with an infinite set of variables.


texts: A square with entries whose adjacencies never repeat

texts:
Suppose we have an $n \times n$ square, and an alphabet $\Gamma$.  We put an element of $\Gamma$ in each location of the square. An element can appear in more than one location.  The constraint is that a pair $a,b$ of neighbors (either east-west of each other, or north-south of each other) can only appear in that configuration once.

Example of a prohibited square:

a b c
d e f
g d e

Since "de" appears on both the second and the third row, the entries of the square are not acceptable. The same problem would arise if, say, a appeared above d anywhere except the top left corner.

  Given $n$, the width of the square as a parameter, what is a lower bound on the size of the alphabet $\Gamma$?

I would love (suggestions toward) a direct proof, but also, has this type of square-filling problem been studied?  I can't connect it to either a Latin square, or a block design.  Does this map onto any already-named combinatorial object?

(Note: this is related to a previous question of mine about avoiding partial words, but that question only required avoidance east-west, so to speak, whereas here I need to avoid north-south repetitions also.)


texts: Why does the Fibonacci sequence produce a worst-case Huffman encoding?

texts: I noticed this in my Algorithms class, but just now got around to asking.


texts: Exact exponential-time algorithms for 0-1 programming

texts:
Are there known algorithms for the following problem that beat the naive algorithm?

Input: A system $Ax \le b$ of $m$ linear inequalities.
Output: A feasible solution $x^*\in \{0,1 \}^n$ if one exists.

Assume that $A$ and $b$ have integer entries. I'm interested in worst-case bounds.


texts:
Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average weight per node then is $\bar w = m/n$. Let $e_i = w_i - \bar w$ denote the deviation of node $i$ from the mean. We call $|e_i|$ the imbalance of node $i$.

Suppose that the weight between any two adjacent nodes can differ by at most $1$, i.e.,
$$ w_i - w_j \le 1\; \forall (i,j) \in E.$$

Question: What is the largest possible imbalance the network can have, in terms of $n$ and $m$? To be more precise, picture the vector $\vec{e} = (e_1, \dots, e_n)$. I'd be equally content with results concerning $||\vec{e}||_1$ or $||\vec{e}||_2$.

For $||\vec{e}||_\infty$, a simple bound in terms of the graph diameter can be found: Since all $e_i$ must sum to zero, if there is a large positive $e_i$, there must somewhere be a negative $e_j$. Hence their difference $|e_i - e_j|$ is at least $|e_i|$, but this difference can be at most the shortest distance between nodes $i$ and $j$, which in turn can be at most the graph diameter.

I'm interested in stronger bounds, preferably for the $1$- or $2$-norm. I suppose it should involve some spectral graph theory to reflect the connectivity of the graph. I tried expressing it as a max-flow problem, to no avail.

EDIT: More explanation.
I'm interested in the $1$- or $2$-norm as they more accurately reflect the total imbalance. A trivial relation would be obtained from $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$, and $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$. I expect, however, that due to the connectedness of the graph and my constraint in the difference of loads between adjacent nodes, that the $1$- and $2$-norms should be much smaller.

Example: Hypercube of Dimension d, with $n = 2^d$. It has diameter $d = \log_2(n)$. The maximum imbalance is then at most $d$. This suggest as an upper bound for the $1$-norm $nd = n\log_2(n)$. So far, I have been unable to construct a situation where this is actually obtained, the best I can do is something along the lines of $||\vec{e}||_1 = n/2$, where I embed a cycle into the Hypercube and have the nodes have imbalances $0$, $1$, $0$, $-1$ etc. So, here the bound is off by a factor of $\log(n)$, which I consider already too much, as I'm looking for (asymptotically) tight bounds.


texts: Find a largest cube contained in the union of cuboids

texts:
I have a lot of cuboids in 3D space, each has a starting point at (x,y,z) and has size of (Lx,Ly,Lz). I wonder how to find a largest cube in this 3D space that is contained in the union of the cuboids. Is there an efficient algorithm for this?

For instance,
If I have the following cuboids:

a cuboid starting at (0,0,0) with size (10,10,10),
a cuboid at (10,0,0) with size (12,13,15),
a cuboid at (0,10,0) with size (10,10,10),
a cuboid at (0,0,10) with size (10,10,10), and
a cuboid at (10,10,10) with size (9,9,9).

Then, the largest cube contained in the union of these cuboids will be a cube starting at (0,0,0) with size (19,19,19).

A more general version of this question:

  Given a collection of $n$ boxes in
  $\mathbb{R}^d$, find the largest hypercube
  contained within the union of the boxes.


texts: Fast algorithm for weighted bipartite matching problem

texts:
I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks.

I have an implementation of the Hungarian Algorithm which takes about a minute to solve for my $640 \times 640$ matrix. For forbidden assignments, I set the cost to $\infty$. (There always exists a feasible solution in my problem).

I've also set it up as a binary program in CPLEX, which takes about 9 seconds to solve for the same problem. The BIP model excludes forbidden assignments outright by omitting those variables.

I haven't yet investigated setting it up as a networking model in CPLEX, but that will likely be my next step. There is, however, a performance cost with communicating with CPLEX, so I'm sure a dedicated algorithm should get better performance.

This bipartite matching problem is a kernel within another iterative search algorithm, so it must run as fast as possible.

Are there any algorithms that I can implement that will outperform the Hungarian Algorithm in this case? Or do you have any other suggestions on how I can improve the performance of this kernel?


texts:
The objective is to build a classifier that produces M correct outputs when given N inputs.

Let a "sample" be M outputs and N inputs. Each output is some function some of the N inputs but the functions are not given. You only know that some of the N inputs can possibly combine to produce each of the M outputs.

Several samples are available for the machine learning algorithm to learn from, and in each sample, the functions for each output produced from what input sets are the exactly same.

It sounds like supervised learning but it doesn't seem to match exactly.

I'll provide an example:

__Sample 1:

Inputs: people = 6; salary = 100

outputs: width = 600; height = 100

__Sample 2:

Inputs: people = 3; salary = 60

outputs: width = 180; height = 60

__Sample 3:

Inputs: people = 5; salary = 101

outputs: width = 505; height = 101

The correct functions are then: width = people * salary; height = salary


texts: On collapsing the Exponential time hierarchy

texts:
Define $\Sigma^E_0 = \Pi^E_0=E$,
for every $n>0$, define $\Sigma^E_n=NE^{\Sigma^p_{n-1}}$,
for every $n>0$, define $\Pi^E_n=CoNE^{\Sigma^p_{n-1}}$.

Define the Exponential time hierarchy by $EH=\bigcup_{i\in\mathbb{N}}\Sigma^E_i$.
We know that $\Sigma^p_n=\Pi^p_n$ implies $PH=\Sigma^p_n$. My question is whether something like this is true for $EH$ or not.

Q1. Does $\Sigma^E_n=\Pi^E_n$ imply the collapse of the $EH$ to some level? For example, does $E=NE$ imply $EH=E$?
Q2. If we do not know the answer to the above question, Is there any oracle separation? For example is there any oracle $A$ such that $E^A=NE^A$, but $E^A\not={\Sigma^E_2}^A$?


texts: Is Clique completion for intersection models hard?

texts:
The following seems like a natural problem and I'm surprised I can't find any literature on it... but maybe it's because I don't know the name for it.

Given a list of sets $S_1, S_2, S_3, \ldots$
Can we make $k$ additions (that is, adding an element to any single $S_i$ ) so that every pair of sets has nonempty intersection?

If we treat each subset $S_i$ as a vertex and say two vertices are adjacent if their corresponding sets have at least one common element, this is like an intersection model for a graph and we are augmenting the representation to turn the graph into a clique. I think of this as some sort of "clique completion" problem, but I don't know if it has been studied in another context under a different name.

Does anyone know of this problem?


texts: Computing any information about Max-3SAT

texts:
For a 3CNF formula $C$ let $M(C)$ be the maximal number of satisfied clauses in any assignment to $C$. It is known that Max-3SAT is hard to approximate (subject to P≠NP), i.e. there is no polytime algorithm whose input is a 3CNF formula $C$, and whose output is the number $M'$ such that $M(C)$ is within a multiplicative factor $1+c$ from $M'$, where $c>0$ is an absolute positive constant.

I believe that it is also NP-hard to compute $M(C) \bmod p$ for any constant modulus $p$. I wonder if the following common generalization of these two facts is true: There is no polytime algorithm whose input is a 3CNF formula $C$ with $N$ clauses, and a string of $\log_2 N-B$ advice bits, and whose output is $M(C)$. Here $B$ is an absolute constant. In plain words, there is no algorithm that computes $B$ bits of information of $M(C)$.

I apologize if the question has a well-known answer, for I am not a complexity theorist by the way of background.


texts: Is there a candidate for a post-quantum one-way group action?

texts:
Is there a known family of group actions with a designated element

in the set that is being acted on, where it is known how to efficiently

$\:$ sample (essentially uniformly) from the groups, compute the inverse operations,

$\:$ compute the group operations, and compute the group actions

and there is no known efficient quantum algorithm

for succeeding with non-negligible probability in

$\:$ given as inputs the index of a group action and the result of

$\:$ a sampled group element acting on the designated element,

$\:$ find a group element whose action on the designated element is the second input

?

As far as I am aware, those provide the only known constructions of non-interactive statistically hiding commitments in which knowledge of a trapdoor enables efficient and undetectable equivocation, a property that is useful for zero knowledge protocols and adaptive security.

Any family of one-way group homomorphisms with the first three properties (from the third and fourth lines of this post) can be converted into such a thing by having the domains act on the codomains via $\: \langle a,b\rangle \mapsto h(a)\cdot b \:$, $\:$ with the identity elements as the distinguished elements.

A restricted version of the Pedersen commitment scheme can be obtained as a special case of applying the above conversion to the group exponential homomorphism, whose one-wayness is equivalent to the hardness of the discrete logarithm problem, although that is not hard for quantum algorithms.  (See Shor's algorithm and that page's section on discrete logarithm.)


texts: Is there an official name for a notion of "reusably universal"?

texts:
There are several different (probably inequivalent) notions of computational universality (see for example the last couple pages of http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf) and there is no consensus among experts about which notions are most correct (see for example http://cs.nyu.edu/pipermail/fom/2007-October/012148.html).

I'm trying to say something about a particular model of biomolecular computation.  I'd like to argue that it's "more universal" or "more usefully universal" than some other models, because you can construct a universal machine that runs a program and then deletes the input at the end and is ready to run another program.  Contrast this to, say, cellular automata, which can emulate any Turing machine, but then at the end of the computation, you've got a final, unchangeable configuration.  To emulate another TM, you need to define a completely separate CA.  So I'd like to say something is "reusably universal" if it behaves like your desktop, not a CA (i.e., can execute multiple programs without needing to recreate the universe).  Has this notion been formalized anywhere?


texts: How efficient are DPLL-based SAT-solvers on satisfiable instances of PHP?

texts:
We know that DPLL based SAT-solvers fail to answer correctly on unsatisfiable instances of $\mathrm{PHP}$ (pigeon hole principle), e.g. on "there is a injective mapping from $n+1$ to $n$":

$$\mathrm{PHP^{n+1}_{n}} := \left(\bigwedge_{i\in[n+1]} \ \bigvee_{j\in[n]} \ p_{i,j}\right) \wedge \left(\bigwedge_{i\neq i'\in[n+1]} \ \bigwedge_{j\in[n]} \ (\lnot p_{i,j} \vee \lnot p_{i',j})\right)$$

I am looking for results about how they perform on satisfiable instances of $\mathrm{PHP}$, e.g. on "there is a injective mapping from $n$ to $n$".

Do they find a satisfying assignment quickly on such instances?


texts: Can we quantify the "degree of quantumness" in a quantum algorithm ?

texts:
Entanglement is often held up as the key ingredient that makes quantum algorithms well... quantum, and this can be traced back to the Bell states that destroy the idea of quantum physics as a hidden-state probabilistic model. In quantum information theory (from my rather weak understanding), entanglement can also be used as a concrete resource that bounds the ability to do certain kinds of coding.

But from other conversations (I recently sat on the Ph.D committee of a physicist working in quantum methods) I gather that entanglement is difficult to quantify, especially for mixed-state quantum states. Specifically, it appears hard to say that a particular quantum state has X units of entanglement in it (the student's Ph.D thesis was about trying to quantify amounts of entanglement "added" by well known gate operations). In fact, a recent Ph.D thesis suggests that a notion termed "quantum discord" might also be relevant (and needed) to quantify the "quantumness" of an algorithm or a state.

If we want to treat entanglement as a resource like randomness, it's fair to ask how to measure how much of it is "needed" for an algorithm. I'm not talking about complete dequantization, merely a way of measuring the quantity.

So is there currently any accepted way of measuring the "quantumness" of a state or an operator, or an algorithm in general ?


texts: How hard is a variant of graph automorphism problem?

texts:
I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate).

Restricted GA

Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u \ne v$ ( all pairs $(u_i, v_i)$ are pair-wise disjoint and $0 \le \epsilon \le 1$)

Question: Is there a non-trivial automorphism $f$ of $G$ such that for every pair $p_i$ either $v_i=f(u_i)$ or $u_i= f(v_i)$?

This problem is at least as hard as Graph Automorphism Problem. I guess it is harder than Graph Automorphism but not $NP$-hard.

  Is there a computational evidence that supports (or against) my guess regarding the complexity of this variant of $GA$?

Motivation: My problem is a relaxation of NP-complete problem known as fixed-point free graph automorphism problem.

EDIT: Cross-posted on mathOverflow


texts: Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

texts:
I understand that Disjoint Feedback Vertex Set (= looking for a solution $X$ of size $k$ given a solution $W$ of size $k+1$ s.t. $X \subseteq V \setminus W$ ) can be solved in time $4^k poly(n)$, see 4.3 here.

They also say FVS can be solved in $5^k poly(n)$ using iterative compression with the DFVS algorithm, but I can't see how.
If I start with a $2$-approximation, the total runtime would be $5^{2k} poly(n)$ by iterating over all subsets of a given solution as $W$ and executing the DFVS algorithm for each.

What is the starting point for the iterative compression and how does it lead to the given runtime?


texts:
I am interested in learning connections between "chaos," or more broadly, dynamical systems, and
the $P{=}NP$ question.
Here is an example of the type of literature I am seeking:

  Ercsey-Ravasz, Mária, and Zoltán Toroczkai. "Optimization hardness as transient chaos in an analog approach to constraint satisfaction." Nature Physics 7, no. 12 (2011): 966-970. (Journal link.)

Has anyone written a survey, or made a bibliographic compendium?


texts: Is testing two SO-Horn queries for equivalence decidable?

texts: It follows from Rice's theorem that you cannot determine whether or not two Turing machines decide the same language.  My question is:  Does this also apply in descriptive complexity settings, particularly when it comes to testing a pair of SO-Horn queries to see if they describe the same language?  I'm not aware of any descriptive complexity version of Rice's theorem, and I could conceivably see that it might not be all that difficult to test two second-order formulas for equivalence.


texts: What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?

texts:
$k$ distinct points are selected randomly from a $p\times q$ grid. (Obviously $k\leq p\times q$ and is a given constant number.) A complete weighted graph is built from these $k$ points such that weight of the edge between vertex $i$ and vertex $j$ equals the Manhattan distance of two vertices on the original grid.

I am looking for an efficient way to calculate the expected length of the shortest (minimum total weight) hamiltonian path passing through these $k$ nodes. More precisely, the following naive approaches are not desired:

$\bullet$ Calculating the exact path length for all combinations of k nodes and deriving the expected length.

$\bullet$ Calculating the approximated path length for all combinations of k nodes using the basic heuristic of using minimum spanning tree which gives up to 50% error. (A better heuristic with less error may be helpful)


texts:
This question is closely related to this MO question.

I would like to know, whether any (planar Euclidean) TSP instances are known, that exhibit avalanche effects similar to those ecountered in sandpiles to which grains of sand are added one by one.

The planar Euclidean TSP analogy would be starting with the convex hull of the instance's pointset as the initial tour of size $k$ and then repeatedly expanding the tour by:

integrating as the point, the one, that incurs the least tour-elongation
restoring the optimality of the tour by exchanging a set of edges.

The avalanche effect would then correspond to the cardinality of the set of edges, that has to be exchanged in order to restore optimality of the tour after the next point had been integrated into the previous (optimal) tour.

Question:
do there exist examples of infinite, discrete point sets of which only finitely many are on the convex hull, that exhibit avalanches of arbitrary size, if the next point is integrated, after the cuurent tour has been optimized.


texts:
Suppose we have a graph $G$ with $n$ vertices that contains neither a clique of size $3 \log(n)$ nor an independent set of size $3 \log(n)$ (for example $G(n,0.5)$ satisfies this property with with high probability). Is it true that the number of edges of $G$ is at least $n^2/100$, i.e., it cannot be too sparse?

More generally, I would like to know whether such graphs have some kind of pseudo-random properties.


texts: Parallel algorithms for reachability in directed planar graphs

texts:
Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors.

What is the best known parallel algorithm for st-connectivity in directed planar graphs ?

Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial).

This question is related to one of my previous questions. My previous question is about general directed graphs which are not necessarily planar.


texts: How large a treewidth can a tree plus half the edges have?

texts:
Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible?

It seems somehow that tw(H) should be O(sqrt(n)) , but this is just a vague hunch. Do we know better upper bounds than O(n) for the treewidth of a graph obtained by adding n edges to a tree on 2n vertices?


texts: Cryptography without assumptions -- seeking an overview

texts:
Suppose $P = NP$ and a fast linear-time algorithm for SAT appears tomorrow.  Suddenly RSA is insecure, much of our modern communication system is broken, and we need to reconsider how to keep secrets from each other.

Question: Is there a good single reference (or short list) to gain a big-picture view of what is possible in crypto (and in the allied field of "security") without intractability assumptions? This could save civilization one day, and would also be nice to peruse in the meantime.

Discussion: Most of the cryptographic tasks we now study (OWFs, PRGs, PKE) are provably impossible in the $P = NP$ world (a world dubbed "Algorithmica" in an influential essay by Impagliazzo), but some things remain possible: communication with a one-time pad; distributed secret sharing; private info retrieval; and some other nice things.
(Certain kinds of physical mechanisms such as locked boxes, devices implementing oblivious transfer, and quantum states can also come in handy.  Of course there is always some kind of physical assumption about who can see what information.)

One can distinguish between information-theoretic security (which works against a computationally unbounded adversary) and "unconditional" security (which may require a bounded adversary, but still shows security under no unproven assumptions).  I'm most interested in the info-theoretic case.

For starters, here is one bibliography of information-theoretic security (which, for my purposes, is unmanageably long and disparate).


texts: Optimal distribution of integer edge weights

texts:
I am not sure whether the following problem has been studied. Any help would be greatly appreciated. I have $L$ sets, $S_1, S_2,...,S_L$, each of $n$ elements, taken from a universe of $N$ elements. My aim is to find subsets $S'_1 \subseteq S_1, S'_2 \subseteq S_2,...,S'_{M} \subseteq S_M$ of $k$ elements each, such that the subsets are pair-wise disjoint and the number of subsets is maximal.

As an example, consider the three sets ${S_1} = \left\{ {1,2,3,4} \right\},{S_2} = \left\{ {2,3,5,6} \right\},{S_3} = \left\{ {1,3,6,7} \right\}$ where $n=4$ and $k=2$. Then an optimal solution is 3 sets: $S'_1 = \left\{ {1,2} \right\},S'_2 = \left\{ {3,5} \right\},S'_3 = \left\{ {6,7} \right\}$.

The problem above is hard in general. However, it turns out that when the maximum pair-wise intersection is $2(n-k)/(L-1)$, a solution of $L$ subsets is guaranteed to exist. Assume that the maximum pair-wise intersection is $2(n-k)/(L-1)$, and that no element appears more than twice in the sets $S_1, S_2,...,S_L$. Denote by $\tilde S_i$ the elements in $S_i$ that belong to $S_i$ only (i.e., not shared by any other set). Then we can represent the problem as a complete graph with $L$ nodes, where an edge between edge $i$ and edge $j$ is of weight $|S_{ij}|$ units.

The problem: How can we distribute the weights between the nodes such that node $i$ receives $k-|\tilde S_i|$ units (if $|\tilde S_i| < k$) out of the weights on edges connected to node $i$ (i.e., together with the elements in $\tilde S_i$ it has $k$ elements)?.

In other words, we want to distribute non-negative integer edge weights between nodes such that each node receives at least $k$ units. It can be shown easily that if node $i$ receives $1/2$ of each weight on its connected edges, then the node will have at least $k$ units. However, the weights are not necessarily even, so this "solution" cannot be applied in general.


texts:
Peter Taylor and Tsuyoshi Ito solved a previous question that I posted:

Covering a set of intervals

I have a slight variation on that question that I'd also like to ask. I'm not sure what the etiquette here is here but I'll post the original question + modification here (if that's discouraged then I sincerely apologize!)  The question posted was:

Is the following question in NP:  "Given a finite set of half-open intervals and integers $k$ and $L$, is there a subset of the intervals so the sum of their characteristic functions can be expressed as a sum of characteristic functions of $k$ intervals of length $L$?"

The problem is NP-complete via a reduction from the subset-sum problem.  My variation is:

  Does the complexity change if we
  require that all of the given
  intervals have length less than $L$?

Thanks!


texts: What are some examples where the Catalan numbers show up in algorithms/data structures?

texts: For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up (either in a data structure itself or in a run-time analysis)?


texts: Just how bad is the fooling set method in communication complexity?

texts: I know that if we take a random function, it's likely that the maximal fooling set is at most $kn$ for some constant $k$, while the CC is almost $n$. What bound can I get from above on the communication complexity given the maximal fooling set? For example, is it possible that the fooling set is $O(1)$ while the communication complexity is about $n$?


texts: Janson-type inequality, limited dependence

texts:
So I am trying to figure out an upper bound on the probability of the following...

This is a question related to a problem I am working on (not for a class, just for fun)

Let $\Omega=\{X_{1},\dots,X_{n}\}$
  where each $X_{i}$
  is i.i.d
  Bernoulli with success probability 1/2.
  Let $Y=\{Y_{1},\dots,Y_{N}\}$
  where $Y_{i}\subset\Omega$
  and $|Y_{i}|=t$.
  Let $Z_{i}$
  indicate the event that $\sum_{X\in Y_{i}}X\geq k$,
  where $k$
  is some value close to $t$. Let $Z=\sum_{i=1}^{N}Z_{i}$

Say that $I_{r}=
  \{\{Y_{i},Y_{j}\}:|Y_{i}\cap Y_{j}|=r\}$,
  that is, $I_{r}$
  is the set of all pairs from $Y$
  that share $r$
  elements from $X$.
  I am looking for an upper bound on $Pr[Z\leq\mathbb{E}[Z]-t]$.

I've seen Janson's inequality and notice that it looks quite similar to this, but I'm not sure where to go from here. Any help or any references would be greatly appreciated.


texts: karger's algorithm contracting nodes not edges

texts:
Karger's algorithm works by contracting edges, not merging nodes (this is different because nodes need not share an edge).

Is there a reason why this is so?


texts: Intermediate/Coding representation for Levenshtein Distance

texts:
The phrases:

  The quick brown fox jumps over the lazy dog [A]

and

  The uick brown fox jumps oower the lazy dog [B]

can be compared using Levenshtein Distance algorithm to determine similarity by calculating the minimum number of single character additions, deletions, or replacements are necessary to transform A into B.

I'm interested to know if there is an intermediate representation, or possibly a coding scheme for the Levenshtein Distance.  Not for use between two phrases, but just a coding applied to a single phrase such that character index does not affect comparisons.

In B, the 'q' is missing compared to A.  A normal string comparison would match 'The ' and then fail at 'uick brown fox...' merely because of a single character offset.  The Levenshtein Distance could be used to compare it to the original phrase A for a more forgiving comparison, but in my case, I won't have two phrases, just one.

So, I'm looking for some way of unambiguously coding a sentence in packets of information, little atoms of truth (I'm thinking one packet per character?) that maintain a local ordering and so-on, but if some of the packets are wrong, it doesn't affect later characters.

Each unique phrase should map to one and only one unique encoding/intermediate representation, Sets A' and B'.  Computing the Levenshtein Distance of A and B would then be the same as computing the intersection of sets A' = B'.

Alternatively - if this problem does not have a solution (and this sure maps to a well-trodden area of research, I wouldn't be surprised), some convincing argument/proof for its unsolvability.


texts: Distributive law between monads in Haskell

texts:
A distributive law between monads must satisfy laws that are usually given in terms of the units $\eta$ and multiplications $\mu$ of the two monads. Among the four laws there are:

$\mu^S T \circ S l \circ l S = l \circ T \mu^S$, and
$S \mu^T \circ l T \circ T l = l \circ \mu^T S$

I would like to state those laws in Haskell in terms of fmap, return and (>>=). By replacing $\mu$ in the above equation I respectively get:

fmap l (l n) >>= id  ==  l (fmap (\m  -> m >>= id) n), and
fmap (\m -> m >>= id) (l (fmap l n))  ==  l (n >>= id)

But those equations in this form are not very useful for making proofs by rewriting because such patterns never arise directly in practice and thus I cannot use them for rewriting.

Is there a nicer, smarter and equivalent way to define a distributive law for monads in Haskell terms of fmap, return and (>>=)? I searched the literature on Haskell but the closer I found were monad transformers which seem to involve special cases of distributive law where one of the monad is fixed. However I am interested in the general case.


texts: Categorical model of binding / first class modules

texts:
Binders are explained using presheaves (Pitts/Gabbay A new approach to Abstract Syntax with variable binding)

What is the equivalent (categorical) theory to explain first class modules as in 1ML ?


texts: an efficient algorithm for mismatch profile

texts:
We have M=10000 binary sequences of length N=1000.

given length L=15, for each pair of sequences, $S_1$ and $S_2$, we define the mismatch profile, mp($S_1$,$S_2$,$L$)[$m$], for m=0,1,...,L as following:

mp($S_1$,$S_2$,$L$)[$m$] = number of all substrings of length $L$ in $S_1$ and $S_2$ that exactly differ in m positions.

for example:

$\begin{array}{ccc}
L=5    \\
N=7    \\
S1='1010101' \\
S2='1011000'

\end{array}$

set of all L-mers in $S_1$ is { 10101, 01010, 10101} and
set of all L-mers in $S_2$ is { 10110, 01100, 11000}

All the pairs of L-mers (one from S1 and the other from S2) are (with the number of mismatches for each pair in the parenthesis):

$\begin{array}{ccc}
10101 & 10110 & (2) \\
10101 & 01100 & (3) \\
10101 & 11000 & (3) \\

01010 & 10110 & (3) \\
01010 & 01100 & (2) \\
01010 & 11000 & (2) \\

10101 & 10110 & (2) \\
10101 & 01100 & (3) \\
10101 & 11000 & (3)
\end{array}$

hence the mismatch profile for $S_1$ and $S_2$ for this example is:
mp($S_1$,$S_2$,$L$)[0]= 0
mp($S_1$,$S_2$,$L$)[1]= 0
mp($S_1$,$S_2$,$L$)[2]= 4
mp($S_1$,$S_2$,$L$)[3]= 5
mp($S_1$,$S_2$,$L$)[4]= 0
mp($S_1$,$S_2$,$L$)[5]= 0

what is a fast algorithm to calculate the mismatch profile for every pair of sequences. The trivial algorithm would be $O(N^2 M^2)$ . can we make this better ?


texts:
Are there examples of practical applications of parity games, ie systems, in the real world, that can be represented as parity games ?

Usually related documentation on parity games has almost never a practical example of this application.


texts: Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time

texts: Assume that you are given a set of n points in the plane and you want to check whether they form a convex n polygon, i.e., if they all lie on the convex hull. I was wondering if anyone knows how to do this in o(nlogn) time, i.e., without computing the CH.


texts: Is { ww' | HamDist(w,w')>1 } context-free?

texts:
After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove:

  Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \}$ context free?

Here we require that the two strings differ in at least two positions (the Hamming distance must be greater than $1$).

It is context-free if we require that $HamDist(w,w')\geq 1$ (i.e. the two strings must simply be different).

I suspect that the language is not context-free: if we intersect it with the regular  $0^*10^*10^*10^*$ we get cases in which a PDA should "remember" two positions in reverse order after reaching the half of the string.

Update: if we intersect $L$ with the regular $R = \{  0^*10^*10^*10^* \}$ we get a context-free language as showed by domotorp in his answer; a slightly more complex $L \cap R' $ with  $R' = \{  0^*10^*10^*10^*10^*10^* \}$ (one more $1$ to "keep track" of) still suggest that $L$ should not be context-free.


texts: What is the complexity of counting parse trees?

texts:
A Counting Problem

Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$?

An Example Instance

Let's consider an example instance consisting of a CFG $G$ with grammar rules:

$S \rightarrow aS$

$S \rightarrow aSb$

$S \rightarrow \epsilon$

And, a string $s = aaab$.  Then, there are three parse trees for $s$:

(1) $S \rightarrow aS \rightarrow aaS \rightarrow aaaSb \rightarrow aaab$

(2) $S \rightarrow aS \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$

(3) $S \rightarrow aSb \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$

  Question

  What is the complexity of this counting problem?  Is it hard for any
  notable counting complexity classes?

Edit: Based on @MRC's comments, it seems that this problem is equivalent to calculating the weight of $s$ relative to the weighted CFG obtained by attaching the semiring $(\mathbb{N}, +, \times)$ to $G$ and assigning the weight of 1 to each of $G$'s rules.


texts: Is the topsort from "Structuring Depth-First Search Algorithms" guaranteed to be (reverse) stable?

texts:
In "Structuring Depth-First Search Algorithms in Haskell", implemented in Data.Graph in the Haskell standard library, an algorithm for topologically sorting graphs is given:

postorder :: Tree a -> [a] -> [a]
postorder (Node a ts) = postorderF ts . (a :)

postorderF   :: Forest a -> [a] -> [a]
postorderF ts = foldr (.) id $ map postorder ts

postOrd :: Graph -> [Vertex]
postOrd g = postorderF (dff g) []

topSort      :: Graph -> [Vertex]
topSort       = reverse . postOrd

Experimentally, this topological sort seems to be stable with respect to the reverse of the input graph, e.g.:

Prelude> import Data.Graph
Prelude Data.Graph> let d = buildG (0,3) []
Prelude Data.Graph> topSort d
[3,2,1,0]

Is this actually true? That is, given an ordered list of nodes $N$ with edges $E$, is the result of topSort on this graph an ordering of nodes such that if there is no path from $n_1$ to $n_2$, the ordering of $n_1$ and $n_2$ from the original list is swapped from in the topologically sorted list?

As an extra thought, is there an elegant way to rewrite this algorithm so that it doesn't reverse the original order?


texts: How can relational parametricity be motivated?

texts:
Is there some natural way to understand the essence of relational semantics for parametric polymorphism?

I have just started reading about the notion of relational parametricity, a la John Reynolds' "Types, Abstraction and Parametric Polymorphism", and I am having trouble understanding how the relational semantics is motivated.  Set semantics makes perfect sense to me, and I realise that set semantics is insufficient to describe parametric polymorphism, but the leap to relational semantics seems to be magic, coming completely out of nowhere.

Is there some way of explaining it along the lines "Assume relations on the base types and terms, and then the interpretation of the derived terms is just the natural relationship between ...such and such a natural thing... in your programming language"?  Or some other natural explanation?


texts:
The breakthrough theory of iterative compression introduced by Reed, Smith and Vetta [1] can give positive answers to a number of open problems of parameterized complexity of several important NP-hard minimization problems, such as Vertex Bipartization Problem, Undirected Feedback Vertex Set, Directed Feedback Vertex Set, Almost 2-SAT, etc. Iterative compression can solve the Vertex Bipartization in $O(3^k|V||E|)$.

Iterative rounding is a very successful research in approximation algorithms[2], which lead to an approximation algorithm for the Steiner Tree Problem with the best theoretical approximation guarantee[3]. A recent DIMACS challenge on Steiner Tree Problem workshop has a good experimental result of implementation of Iterative rounding[4].

My Question: Can Iterative Compression lead minimization NP-hard problem to both in low complexity and good approximation?

[1] Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res.
Lett. 32(4), 299–301 (2004)

[2] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization. Cambridge University Press, 2011.

[3] Jaros law Byrka, Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanita. Steiner
tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1{6:33,
February 2013.

[4] Ciebiera, Krzysztof, et al. "Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks." arXiv preprint arXiv:1410.7534 (2014). http://dimacs11.cs.princeton.edu/workshop.html


texts: Intermediate problems between nonuniform $NL$, $Mod_n L$ and $P$?

texts:
A related question asked about intermediate problems between $L$ and $NL$. I'm interested in problems between the nonuniform versions of $NL$, $Mod_n L$ and $P$. This makes sense as it is known that $NL \subseteq Mod_2 L$ nonuniformly (see here).

A motivation comes from the complexity classification of Constraint Satisfaction Problems. To the best of my knowledge, all known dichotomies in this field yield tractable cases that fall in one of the above classes. A seminal result in this area is Schaefer's dichotomy for binary CSPs showing that the tractable instances are reducible to either $2SAT$ (thus $NL$-complete), $HornSAT$ or its dual (thus $P$-complete) or satisfiability of affine equations (thus $\oplus L$-complete).

This question can also be declined in two variants: (i) what about the corresponding counting classes, (ii) what about the corresponding parameterized classes, e.g. parameterized problems non-deterministically solvable in $O(k \log n)$ space vs problems solvable in $n^{O(k)}$ time.


texts: A number-theoretic bijection in modular arithmetic

texts:
Fix an integer $n$. Considered as a multiplicative group, the sets $A = (\mathbb{Z} / n \mathbb{Z})^*$ and $B = \mathbb{Z} / \phi(n) \mathbb{Z}$ have the same cardinality $\phi(n)$, but it does not seem possible to give a 'well-behaved' bijection witnessing this fact. On the other hand, by considering the ring $R = \mathbb{Z} / n \mathbb{Z}$, it is possible to give a bijection between $R^A$ and $R^B$, considered as sets of functions.

Indeed, any element $f \in R^A$ can be written uniquely as $f(x) = \sum_{y \in B} \hat{f}(y) x^y$ with $\hat{f} \in R^B$; this is well-defined as for $x \in R$ we have $x^{\phi(n)}$ congruent to $0$ or $1$ modulo $n$. Conversely, $\hat{f}$ can be recovered as $\hat{f}(y) = \phi(n)^{-1} \sum_{x \in A} f(x) x^{-y}$. This has the desired properties: consider the matrices $K \in R^{A \times B}$ and $L \in R^{B \times A}$ defined by $K(x,y) = x^y$ and $L(y,x) = x^{-y}$, it can then be checked that $K.L = L.K = \phi(n) I$.

I would like to know if there are references to this bijection in the literature, and if there are other examples of 'indirect bijections' witnessing a combinatorial identity for which a direct bijective proof is not known.


texts: Euclidean-squared max-cut in low dimensions

texts:
Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that is at least $\frac 2 3$ of the total weight? If not, which constant should replace the $\frac 2 3$?

The worst example I'm able to find is 3 points on an equilateral triangle, which achieves the $\frac 2 3$. Note that a random split would produce $\frac 1 2$, but it seems intuitively obvious that in low dimensions, one can cluster better than randomly.

What happens for max-k-cut for k > 2? How about a dimension d > 2? Is there a framework to answer such questions? I know about Cheeger's inequalities, but those apply to sparsest cut (not max-cut) and only work for regular graphs.

(Question is inspired by the problem of clustering light sources in computer graphics to minimize variance).


texts:
What is the simplest computational model for which the emptiness problem is undecidable?

Emptiness problem for a computational model (e.g. finite state automaton, alternating pushdown automaton, bounded-error quantum automaton with a counter, deterministic LBA, etc.) is to determined whether, for a given such machine, the language recognized/defined by this machine is empty. Here the description of the machine should be finite!

I know that the word "simplest" is a little vague. There could be more than one answer for some incomparable computational models.

As a special remark, I believe that the question would become more interesting by focusing on unary and binary alphabets separately.

Note that there are many computational models for which the halting problem is decidable but the emptiness problem (and some other problems) is (are) undecidable, e.g. Linear bounded automata (LBAs).


texts: Given an $n$-state DFA (over a binary or any fixed alphabet), what is the complexity of computing its Kleene closure DFA? What is the largest possible/known blow-up in the number of states?


texts: Worst case polynomial in elimination theory under rank conditions?

texts:
Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree $d$ and $r_1,\dots,r_{2n}\in\mathbb Z$ what is the complexity of finding common roots over $\mathbb Z$ for the polynomial system
$$h_{2n}(x_1,\dots,x_{2n})=0,\dots,h_{2n}(x_1,\dots,x_{2n})=0?$$

  Is the time and space complexity $f(B^d)d^{O(n)}$ at some polynomial $f$ if the roots are bound in $B$ and we have the condition $x_ix_{n+j}=x_jx_{n+i}$ at every $i,j\in\{1,\dots,n\}$?

I am unable to find a polynomial system which needs $d^{O(n)}$ choices with $x_ix_{n+j}=x_jx_{n+i}$ true. Is there such a polynomial system?

  I think the complexity might be more like $f(B^dnd)$. Is it possible to prove this?


texts: Inferring optimal utility values from a decision process

texts:
I've been able to model a particular decision problem as a
Markov Decision Process, where the optimal policy (i.e. what decision should be taken at each step) is defined in order to optimize a given utility function. Hence, given the utility function and the probabilistic behaviour of the system, I can calculate what actions to take.

I'm interested in knowing if there exists some "reverse" process: if I know the probabilistic behaviour of the system and which action should be taken, can I calculate what the utility values should be in order to get the expected behaviour?

My first guess was to look at Monte-Carlo simulations, where I would set up some (more or less) random utility values, perform some simulations, see if it's consistent with what I would expect, and keep going until I find something satisfactory. But I'm not sure it's converging, and I have the feeling that I'm not the first one to want to do this.

If it helps, the context is security decision mechanisms, where we would know the actual policy for some base cases, the goal being to calculate the utility values for more complex cases.

EDIT: Give a bit more details following Markus' comment

Let us assume I have a set of states $\Sigma$, a set of actions $A$ and a probabilistic transition function $P : \Sigma \times A \times \Sigma \to [0, 1]$. I also have a boolean function that can tell me, given a trace $\sigma_0, a_0, \sigma_1, a_1, \dots, \sigma_n$, if this trace is "good" or not. Note that I assume here that the system is completely observable, i.e, after executing an action in a state, I know in which state the system is. I also consider working at a finite horizon $n$.

The question becomes: how can I calculate a reward function $W : \Sigma \times A \times \Sigma \to U$, where U is a utility domain (e.g. $\mathbb{R}$) such that the optimal policy (i.e. the  policy returning the maximum utility for a finite horizon $n$) only outputs "good" traces.

Refinement 1: What if I want to define the utility function only on the states and not on transitions, that is, if I just want to define a function $W : \Sigma \to U$?
Refinement 2: What if I consider that the state consists of some attributes $x_1, \cdots, x_k$, and I want to define a reward function only based on the attributes of the state?
Refinement 3: What if, instead of simply classifying the traces into the good ones, and the bad ones, I can define a partial order over them, can I calculate the reward function that always returns the "best" trace?

I hope this clarifies a bit the question, and although any general results is interesting, I'm also interested in practical approaches, that would provide only an approximation (since calculating the general solution is likely to be intractable in general).


texts:
When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy to understand algorithms. However, the decision version of LP is $\mathsf{P}$-complete. This suggests that it is one of the hardest problems we can solve in polynomial time.
Under the assumption that $\mathsf{NC} \neq \mathsf{P}$. What is the 'hardest' natural kind of optimization problems with decision problems in $\mathsf{NC}$?
If this is too vague, then we can restrict to restrictions. What is the minimal set of restrictions we need to place on linear programs (or more generally: convex programs) to allow the decision problem associated with the restricted programs to be solvable in $\mathsf{NC}$?

Motivation
To a large extent, this is idle curiosity. However, it was brought about by Cosma Shalizi's "In Soviet Union, Optimization Problem Solves You". In particular, if LP is too difficult to solve to have a centralized economy (i.e. optimizing in $\mathsf{P}$ is asking too much), then any decentralized system must be doing some sort of parallel processing faster than poly-time (for me: $\mathsf{NC}$).


texts: Two rectangles whose sum of areas is given

texts:
Given is $\mathcal{P} \in \mathbb{Z}$. Are sought two rectangles which edges have integer, positive value and sum of their areas is $\mathcal{P}$. Find this two rectangles, if you know that sum of their perimeters is the smallest possible. If there are many possible answers, find any of them.

This question was on pre-olympic polish computer science workshops and I'm looking good, well proven solution. Below I put solution, which received maximal number of points, I believe it will help, but it is illogical (a little bit) and no one knows, why it works...

Task has limitation $\mathcal{P} \leq 10^{18}$ and was at most ten questions per actuation, but I'm interested in general solution. We had 256MB of memory
and not more than 1.5 second to answer at ten questions (and pre-process).

Solution:
We are looking for $x_1, x_2, y_1, y_2 \in \mathbb{Z}$, such that $x_1\cdot y_1+x_2\cdot y_2 = \mathcal{P}$ and sum $x_1+x_2+y_1+y_2$ is minimal.
Let start from small observation, one of rectangles will be very small, second will be very big. If both were similar, sum will be $2 \cdot 4\sqrt{\frac{\mathcal{P}}{2}} = 4\sqrt{2\mathcal{P}}$, otherwise it is $4\sqrt{\mathcal{P}}$ from big one and something near zero from second, so sum is near $4\sqrt{\mathcal{P}}$.

In our algorithm, we will choose the largest rectangle (and big implicate small) and we will check if it is best, so far. So, we want answer question "best perimeter for area $\mathcal{P}'$" in $\mathrm{O}(1)$ time, where $\mathcal{P}'$ is small.

We can (in $\mathrm{O}(n \lg n)$ time) pre-process table $A[2..10^6]$, in which $A_i$ is best (smallest) perimeter of rectangle with area $i$.

set A[i] = 2*(i+1)
for i in (1, 1KK) :
    while j <= 1KK :
        A[j] = min(A[j], 2*(i, j/i))
            #it is well to keep i, j/i value for best perimeter in B table
        j += i

If we have this table, we can easily answer to above question. And rest of algorithm is easy.
If $\mathcal{P}$ is small, we are using just brute-force. Otherwise we are checking all $x_1$ in range $[\sqrt{\mathcal{P}} - 10^6; \sqrt{\mathcal{P}})$, as $y_1$ we are taking biggest integer, such that $x_1\cdot y_1 < \mathcal{P}$. Now $x_2y_2$ is imposed. We are taking $x_2, y_2$ from $B$ table. $(x_2, y_2) = B_{\mathcal{P} - x_1y_1}$. If $\mathcal{P} - x_1y_1 > 10^6$ we are assuming that such pair of rectangles is incorrect and we are taking the next value of $x_1$.
If we aren't, we will calculate best second triangle in $\mathrm{O}(\sqrt{\mathcal{P}'})$, we receive TLE (Time Limit Exceeded). Unfortunately we have no time for it.

Pseudocode (skipping all special cases, and small input):

def fun(P) :
answer = inf
for i in range(sqrt(P)-1KK, sqrt(P)) :
    j = floor(P/i)
    perimeter = i + j + best_perimeter(P - (i*j))
    answer = min(answer, perimeter)
      #we have to keep somewhere size of edges of best rectangles
return answer

My live C++ code (100/100 points).
I don't fully believe in this solution. I will be glad, if someone share with me good, correct, well proved solution. Is here any good solution for any range of $\mathcal{P}$?

Thank you for any advices!

Example:
If $\mathcal{P} = 6$, then $(x_1,y_1,x_2,y_2) = (2,2,1,2)$ is correct answer (perimeter is $14$) and $(5,1,1,1)$ is incorrect ($5 \cdot 1 + 1 \cdot 1 = 6 = \mathcal{P}$, but perimeter is equal to $16 > 14$).


texts: What to do as a Theoretical computer science PhD student in a free time?

texts:
I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff Erickson's lecture note etc. I am doing this thing from many months and wondering. Is this a right thing for me to do in free time as now I am a Ph.D. student not an undergraduate student. Now why I do this to become more strong in an algorithm, discrete maths etc part. Another thing which seems more valuable to me is to read more and more research paper of my research domain as my goal after my Ph.D. is to publish more quality research papers in the field related to my current field. I am wondering which one is better or suggest anything else which may be more valuable to me keeping my future perspective in mind.

Question: What to do as a Theoretical computer science PhD student in free time? I am wondering what star experienced researchers do in their time ( assuming they have a free time ).

Some of my free time I also spent on watching video lecture of workshops related to my field.

After looking at all the comments and answers, I have to edit my question. I think, I have not been able to convey what I was trying to ask. My question was how to sharp my technical skills in the free time for a better future. It has nothing to do with my personal life or some one's personal space. I was here for the various possibilities and opinions of users, who have experience in theoretical computer science. Let me clarify my question further, I was to trying to ask in the free time what is more significant to do " continue to think about the research problem at hand or do the problems related to maths or algorithms " and so on. Looking at the comments have made me realise that definitely I need to improve my writing skills also.


texts: Do there exist groups with word problems in arbitrary P-degrees?

texts:
It has been known for a long time that, given any r.e. Turing degree, there is a finitely presented group whose word problem is in that degree.  My question is whether the same thing is true for arbitrary polynomial time Turing degrees.  Specifically, given a decidable set, $A$, does there exist a finitely presented group, with word problem, $W$, such that $W\leq_T^P A$ and $A\leq_T^P W$?  I would also be willing to relax finitely presented to recursively presented.

I suspect that the answer is yes, and I have heard others say they read this somewhere, but I haven't been able to chase down a reference.


texts:
Do CSP solvers have any fundamental advantages over SMT/SAT solvers, in terms of performance?

The answer is going to be problem dependent, so I should also ask: what does a problem need to contain in order for CSP to be faster than SMT/SAT ?


texts:
We have a set of elements $E=\{e_1, e_2, \ldots, e_m\}$, and $n$ subsets of $E$: $S_1, S_2, \ldots, S_n$ The union of those subsets is $E$, and each subset $S_i$ has a non-negative weight $w_i$.

The standard set cover problem is to find set of $S_i$'s whose union is $E$ and whose total weight is the smallest possible.

In the partial cover variation of this problem, we are given a $p \in (0,1)$ and are asked to find a minimum total cost set of $S_i$'s whose union has at least $p|E|$ elements.That is, find and index set $I \subseteq \{1,\ldots,n\}$ such that $|\bigcup_{i \in I}S_i| \geq p|E| $ and this is the cheapest set of $S_i$'s which have this property.

Give a polynomial time algorithm which finds a set of $S_i$'s whose union has at least $p|E|$ elements and whose total cost is at most $c(p)OPT$ where $OPT$ is the optimal cost of the set cover problem and $c(p)$ is a constant that depends on $p$.

My initial thought was that you could solve the relaxed version of the set cover problem, and do a rounding of the variables, where you round a variable $x_i$ (being associated with set $S_i$) to $1$ if $x_i \geq 1-p$, and otherwise round it down. This means the cost will be multiplied by a factor of no more than $1/(1-p)$.

The problem with this is that an element may be in many sets $S_i$ and so it may be the case that no $x_i > 1-p$ for the constraint corresponding to this element.


texts: Learning Mixture of Univariate Gaussians

texts:
There are many papers on learning mixtures of multivariate Gaussians, which exploit various separation/projection techniques. What about one-dimensional (univariate) Gaussians -- any formal guarantees for learning these?

UPDATE: I should clarify: I am particularly interested in polynomial-time algorithms, in the number of mixture components.


texts:
Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected due to edge failures) is known to be #P-hard. In the decision version of Network Reliability, we are given $G$ and a threshold $\gamma$ and we need to check if the probability of $G$ being disconnected is at most $\gamma$.

Since using binary search on $\gamma$ and the answer to the decision version, I can get arbitrarily close to the probability of $G$ being disconnected, can I say that the decision version is also #P-hard? The fact that I can only get close to the true value is confusing.


texts:
I have specific question about suffix trees. I am reading the book  Algorithms on strings_trees and sequence.
I cannot understand details of Ukkonen's algorithm for constructing suffix trees. Why using the skip/count trick, any phase of Ukkonen's algorithm takes O(m) time (theorem 6.1.1)? In particular why over the entire phase, the total number of edge traversals during down-walks is bounded by by 3m?


texts: Bounding the spectral radius of a sub-stochastic matrix

texts:
Suppose that I have a "sub-stochastic" matrix, namely, for an $n\times n$ matrix $A$ with nonnegative entries such that
for any $i$, $\sum_j a_{ij}\leq 1$ and there exists some $i$ with $\sum_j a_{ij}<1$.

It is not hard to see the spectral radius of $A$, $\rho(A)<1$. I am wondering how can I bound $\rho(A)$ tightly in terms of entries of $A$ (e.g., the minimal nonzero entry of $A$). One can make reasonable assumptions (e.g. irreducibility).

Note that I do NOT have that for any $i$, $\sum_j a_{ij}<1$. That case would be much easier.

Thanks!


texts:
Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)?

Presumably a free monoid can be considered to be isomorphic to the familiar Nil, Cons construction for lists. Can finitely-presented monoids be represented as an ADT?

If ADTs can't model structures having inverses, then is there a generalisation which can?


texts: What is the probability of a virus spreading through a network given a virus source node?

texts:
Model: Consider an infinite undirected connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. At time $t=0$, a given virus node $s\in\mathcal{V}$ starts infecting the network $\mathcal{G}$. Specifically, for each edge $(u,v)\in\mathcal{E}$, if either $u$ or $v$ becomes infected, then the other uninfected node on the edge $(u,v)$ will be infected after a random time following an exponential distribution with rate $\lambda$. Assume the spreading times for each edge are independent and identically distributed.

Question: Now given a connected subgraph $G\subset\mathcal{G}$ ($s\in G$ ), what is the probability that all the nodes in $G$ are infected at time $t>0$?

I tried to find a mathematical model to track such an infection process on different kinds of networks (trees, grids, regular networks, etc.). However, after checking the classical epidemic models (SIS, SIR, etc.), I found these models often use the mean field approximation to find the percentages of population in different states (Suspicious, Infected, etc.) without considering the network structures. Thus I think they might not be useful in modeling the infection process described above.

Any insights or references to papers/books would be helpful and greatly appreciated.


texts: Semiprime factorization, Groebner bases and a Nullstellensatz certificate

texts:
Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}^n 2^k y_k$, where $n = \lfloor \log_2 N \rfloor $ is one less the number of bits required to represent $N$, and $x_k, y_k$ are binary indeterminants. By abuse of notation, we can write the following system of equations (here $x, y \in \mathbb{C}^n$)

$\left\{ \begin{array}{lll} f_k= &x_k^2-x_k & =0 \\ g_k= &y_k^2-y_k &=0  \\ h= &\left( 1+ \sum_{k=1}^n 2^k x_k \right) \left( 1+ \sum_{k=1}^n 2^k y_k \right) -N & = 0  \end{array} \right.$

Finding the solution of this system using Groebner basis is computationally expensive (using standard algorithms). On the other hand, this system has only two solutions for semiprimes - $x$ encoding $p$, $y$ encoding $q$, and vice verse. Therefore, the Groebner basis will consist of $n-1$ linear equations encoding line passing through $p$ and $q$, and one quadratic equation selecting $p$ and $q$ along this line (in constrast to NP-complete problems, where many quadratic equations possible for the same problem with different input).

Q1. Does the knowledge of the form of Groebner basis helps to compute it?

Using ideas from Nullstellensatz linear algebra algorithm we can try to express Goebner basis using a linear combination of our equations with polynomial coefficients. For example linear part should be expressed as $c+ \sum_k a_k x_k +b_k y_k = P_1 h+ \sum_k P_{2,k} f_k + P_{3,k} g_k $ with $P_{...} \in \mathbb{C}[x_1,..., x_n, y_1, ..., y_n] $, Here the coefficients are treated as indeterminates. The nullspace of the solution in terms of coefficients of polynomials $P$ will lead to the solution of system of equations. My little experiments show that terms with monomial $x_1 ... x_n y_1...y_n$ are required on the right part of expression to obtain the solution (which is consistent with the Nullstellensatz certificate degree for the same system if it has no solution see DeLoera et al. paper Corollary 2.5).

In solving for $P$ we can start with all possible polynomials $P$ that lead to the monomial $x_1...x_n y_1...y_n$ with coefficients being indeterminates and find linear subspace of coefficients that eliminate it. Then, repeat this with (fixing monomial ordering) leading term in resulted polynomial on the right side. The naive application of this algorithm will lead to exponentially many monomials, on the other hand, the number of terms in encoding the solution line is at most quadratic with n.

Q2. Are there are any references that deal with optimization of monomial elimination in computing Nullstellensatz certificate?

Nullstellensatz certificate for the system of polynomials $f_k=0$ that does not have common solution in algebraically closed field $K$ is a set of polynomials $P_k \in K[...]$ that lead to expression $1= \sum_k P_k f_k $.


texts: Reduction from SAT to binary matrix subset problem

texts:
I'm trying to understand the answer by @Denis on this question, where he showed a way to reduce from SAT to the binary matrix column subset selection problem. The reason I'm having to post a new question is because I have not an account on cstheory.stackexchange before, so I'm unable to ask him directly.

In his explanation of his method in the comments, he mentioned that by the construction of the matrix, one is forced to pick only 1 of the $x_i, \neg x_i$ columns for all $i \in [1,m]$, i.e. forcing an assignment to the CNF (I believe due to the earlier claim that one must choose $m$ out of the $2m$ columns). I am struggling to understand as to why this is the case - I see nothing wrong at the moment with choosing more than $m$ columns or choosing both the columns representing $x_i$ and $\neg x_i$.


texts: How to contribute incrementally to Theoretical CS - similar to github

texts:
I have been through all the basic undergrad classes in CS. I have finished a masters in CS. I have learned a decent amount about applying Haskell to engineering. I haven't studied abstract math yet. I have attended two STOC conferences. I have about 2 hours per week that I could contribute in some way to move Theoretical CS forward in some way.

For Haskell, I could spend that time writing documentation, adding test suites, or implementing features for open source Haskell libraries on github. Is there an equivalent way incrementally contribute as a beginner to theoretical CS? Is there anything like github or are people using github for such purposes?

The best idea I have currently is to try to teach undergrad discrete math or algorithm courses.


texts: Systematic studies of sum of quadratic polynomials squared

texts:
I'm wondering if there exists systematic studies of sums of quadratic forms squared, similar to the quadratic forms, which is practically reflected in eigenvalue decomposition (that has huge practical implication). Couple of examples related to the importance of the question.

Principal component analyses (PCA).
Given a set of points $x_i \in \mathbb{R^n}, i=1..k$ find the set of axes $u_1$, ... $u_m$, written as matrix $U \in \mathbb{R^n x R^m}$, and projections $\xi_1$, ..., $\xi_k, \xi_{\circ} \in \mathbb{R^m}$ that minimizes unexplained variance, i.e. solve the following quartic optimization problem
$$ \arg\min_{u_1,\dots, u_n,\\ \xi_1,\dots, \xi_k} \sum \limits_{i} \left( U^T \xi_i - x_i \right)^2$$
By the magic of symmetry it has the solution by singular value decomposition

Generalized PCA. Same as PCA, but now there is a precision matrix $A_i \in \mathbb{R^n x R^n} $ associated with each observable $x_i$. The problem becomes more complicated
$$ \arg\min_{u_1,\dots, u_n,\\ \xi_1,\dots, \xi_k} \sum \limits_{i} \left( A_i U^T \xi_i - x_i \right)^2$$
(when all $A_i$ are identity matrix this problem is equivalent to PCA, when $A_i = A_j, \forall i,j$, and diagonal it is weighted PCA ). This problem can also be solved in polynomial time via semi-definite programming (SDP) -- Since the solution has the form of sums of squares, by NZ Shor (1987) it is convex problem , and Parillo thesis (2000) gives a practical way to compute it via SDP $ \square $

In SDP approach the quartic polynomial is written as a sum of quadratic polynomials squared. Therefore, it is of major importance to know what kind of quartic polynomials can be written as a sum of quadratic forms squared (by the analogy to biquadratic function they can be called biquadratic forms). Most of the literature, I've encountered stop at the point where they find that the minimum of quartic polynomial $p= \sum_k^n (x_k^2-1) + (a^T x)^2, a \in \mathbb{Z^n}$ is encoding partition problem, and there are no arguments why $p$ cannot be represented as a sum of squares of quadratic polynomials, beyond that.
I'm wondering if anyone made systematic studies of polynomials representable by the sum of squares of quadratic polynomials.


texts: Reference request: exponential growth rates of subsequence-closed languages are integers

texts:
This question is migrated from MathOverflow, where it did not receive any answers a year ago.

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subsequence of $w$ if $u$ can be obtained from $w$ by deleting letters (note that $u$ does not have to occur consecutively in $w$). The language $L$ is subsequence-closed if whenever $w\in L$ and $u$ is a subsequence of $w$ then $u\in L$ (thus subsequence-closed languages are piecewise testable, but not vice versa). It can be shown (see below) that for all subsequence-closed languages $L$,
$$
 \lim_{n\to\infty} \sqrt[n]{|L_n|}
$$
exists and is an integer. Does anyone know of a reference for this fact? (I have stated it with proof in one of my papers, but I am trying to find the "correct" reference for it now.)

Here is the proof I know, thanks to Michael Albert. First, subsequence-closed languages are necessarily regular (if $L$ is subsequence-closed then there are only finitely many minimal words not in $L$ by Higman's Lemma, and this leads quickly to the existence of a regular expression for it).

Next we claim that every subsequence-closed language $L\subseteq\Sigma^\ast$ can be expressed as a finite union of regular expressions of the form
$$
 \ell_1\Sigma_1^\ast\ell_2\Sigma_2^\ast\cdots\ell_k\Sigma_k^\ast\ell_{k+1}
$$
for letters $\ell_i\in\Sigma$ and subsets $\Sigma_i\subseteq\Sigma$. (I would also be interested if anyone has a reference for this decomposition of subsequence-closed languages.) This follows by induction on the regular expression defining $L$. The base cases where $L$ is empty or a single letter are trivial. If the regular expression defining $L$ is a union or a concatenation then the claim follows inductively. The only other case is when this regular expression is a star, say $L=E^\ast$ for a regular expression $E$. In this final case we see that $L=\Pi^\ast$ where $\Pi\subseteq\Sigma$ is the set of all letters occurring in $E$ because $L$ is subsequence-closed.

With the claim above established, it follows that $\lim\sqrt[n]{|L_n|}$ is equal to the size of the largest set $\Sigma_i$ occurring in such an expression for $L$.


texts: Computing the period of a function using a quantum computer

texts:
Consider a blackbox function

$$f(x): Z \rightarrow \lbrace 0,1 \rbrace  $$

Which inputs an integer and outputs 0 or 1 with bit complexity n.

If the period P of this function satisfies

$$P \in O(2^{n})$$

Can a quantum computer determine the period of this function within $\frac{2}{3}$ probability of correctness in polynomial in $n$ time using polynomial in $n$ space?

===========================================================================================

Let me correct this:

the problem is equivalent to asking if Simon's Algorithm or some variant of it can be used to find the period of a function $f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$


texts:
Loosely speaking, permutation pattern matching deals with problems of the following kind:

  Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a subsequence $\tau$ of length $m$ whose elements are ordered according to $\sigma$?

For example, if $\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$ and $\sigma=\langle 2\ 1\ 3\rangle$, then the subsequence $3\ 1\ 4$ matches $\sigma$. As you can see, we're not looking here for an exact match, but rather for something that "looks like" the specified pattern.

Does anyone know whether work has been conducted on extending permutation pattern matching problems to strings? Google unfortunately did not help, since the well-known pattern matching problem on strings has nothing to do with this.


texts: Convergence of iterated stochastic matrices

texts:
(This question has been unsuccessfully asked on mathoverflow: https://mathoverflow.net/questions/161728/convergence-of-iterated-stochastic-matrices)

It is well-known that for a stochastic aperiodic matrix $M$,
the sequence of iterated powers $(M^n)_n$ converges.

Here I would like to a have a more precise analysis. Consider now a sequence of stochastic matrices $(M_n)_n$, converging to $A$. We even assume that there exists $0 < \alpha < 1$ such that for all $n$, we have $||M_n - A|| \le \alpha^n$.
Is it true that $||M_n^n - A^n||$ converges to $0$?


texts:
Lets recall the definition of $k$-means clustering for euclidean spaces.
Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $C$
$\phi(C) = \sum_{i=1}^k \sum_{x \in C_i} \|x-\mu_i\|_2^2$
where $\mu_i = mean(C_i)$.
Then the goal is to find a $C^*$ minimizing $\phi$. This problem is NP-Hard, even for $k=2$.
However there several approximation algorithms for it, e.g. k-means++; but also constant factor approximation algorithms and PTAS.
What I'm looking for is a reference for exact algorithms (i.e., algorithms finding an optimal clustering) which are not polynomial but better than exhastive search. The only reference I'm aware of is (https://dl.acm.org/doi/10.1145/177424.178042), which is quite old.


texts: Running multiple rounds of a BQP computation, without multiple measurements?

texts:
BQP as usually defined is: the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

Just like BPP, the choice of 1/3 in the definition is arbitrary because we could just have a "higher level" algorithm that runs the "basic algorithm" many times and take a majority vote to achieve higher probability of correctness.

I can imagine this as:

initialize qbits based on the input of length n
apply polynomial(n) quantum gates
measure output qbit
repeat steps 1-3, K times and report the majority measurement from step 3

Essentially, having a classical computing loop call a quantum routine K times.

Is it possible instead to somehow do ALL the computation on the quantum computer, and only make a single measurement at the end which is equivalent to this?

I'd hope for something like:

initialize qbits based on the input of length n
apply K * polynomial(n) quantum gates
measure just a single output qbit

Or is making multiple measurements absolutely necessary to the computational power here?


texts: Is System-F with higher-kinded newtypes equivalent in computational power to System-F omega?

texts:
If we have System-F with higher-kinded types and newtypes, then we can express everything (I think) of System-F omega, except we have to manually (un)pack.
For example:

newtype List t = List (forall r. r -> (t -> r -> r) -> r)

unList :: List t -> (forall r. r -> (t -> r -> r) -> r)
unList (List f) = f

Is (I think) equivalent to System-F omega:

List = \t. forall r. r -> (t -> r -> r) -> r

Except you have to call List and unList at the right moments.

Does this language with newtypes have more computation strength than System-F, equal to System-F omega?


texts: About learning a single Gaussian in total-variation distance

texts:
I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown!

  Let $G$ be an $n-$dimensional Gaussian and let $\delta >0$. Then there
  exists a polynomial time algorithm that given $O(\frac {n^2}{\delta^2})$ independent samples from $G$ returns a probability
  distribution ${\bf P}$ so that with probability at least $\frac 2 3$
  we have, $d_{\text{TV}}(G,{\bf P}) < \delta$

To clarify the notation of "TV" used above :

Given two distributions $\bf P$ and $\bf Q$ with p.d.fs (which we denote by the same symbols) we define the ``Total-Variation" distance between them as,

$ d_{\text{TV}}({\bf P},{\bf Q}) := \frac {1}{2} \int_{\bf x \in \mathbb{R}^n} \vert {\bf P}(\bf x) - {\bf Q}(\bf x) \vert d{\bf x} =: \frac {1}{2} ||{\bf P} - {\bf Q}||_1 $


texts: What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?