texts: How does one determine if a mixed bipartite quantum state is entangled or not?

texts:
My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf

Mathematically one can think of being given a positive semi-definite linear map $\rho : \mathbb{C}^n \otimes \mathbb{C}^m \rightarrow   \mathbb{C}^n \otimes \mathbb{C}^m$ such that its trace is $1$ and one wants to determine if there exists some $k$ (column) vectors $x_i \in \mathbb{C}^n$ and another $k$ (column) vectors $y_i \in \mathbb{C}^m$ such that $\rho = \sum_{i=1}^{k} x_i x_i ^{\dagger} \otimes y_i y_i^{\dagger}$

If I understand right then this linked paper is proving the decision version of the above question to be NP-hard. (please correct me if my reading is wrong!)

But I am curious to know as to what would be even a brute-force algorithm to solve this! (in my limited experience for all NP-hard questions there is a trivial brute force solution that is always obvious - but not here!)

[Expanding the questions formulated in the comments]

Trivially it seems that there is no hope of being able to check this unless one allows for some finite precision error. But if with such a discretization the question is redefined then is the corresponding decision question still NP-Hard?
So is there a difference between the decision question that is being shown to be NP-Hard and the actual entanglement question that needs to be solved?

EDIT [$4^{th}$ August 2015]

I found this presentation by Aram Harrow which explains many of the issues that I was trying to get to but couldn't explain properly : http://simons.berkeley.edu/talks/aram-harrow-2014-09-25 (he explains pretty much this exact same question inside his lecture!)


texts: Church's Theorem and Gödel's Incompleteness Theorems

texts:
I have recently been reading up on some of the ideas and history of the ground-breaking work done by various logicians and mathematicians regarding computability. While the individual concepts are fairly clear to me, I'm am trying to get a firm grasp of there inter-relations and the abstract level at which they are all linked.

We know that Church's theorem (or rather, the independent proofs of Hilbert's Entscheidungsproblem by Alonzo Church and Alan Turing) proved that in general we cannot calculate whether a given mathematical statement in a formal system is true or false. As I understand, the Church-Turing thesis provides a pretty clear description of the equivalence (isomorphism) between Church's lambda calculus and Turing machines, hence we effectively have a unified model for computability. (Note: As far as I know, Turing's proof makes use of the fact that the halting problem is undecidable. Correct me if I'm wrong.)

Now, Gödel's first incompleteness theorem states that not all statements in a consistent formal system with sufficient arithmetic power may be proven or disproven (decided) within this system. In many ways, this appears to me to be saying exactly the same thing to me as Church's theorems, considering lambda calculus and Turning machines are both effectively formal systems of sorts!

This is however my holistic interpretation, and I was hoping someone could shed some light on the details. Are these two theorems effectively equivalent? Are there any subtleties to be observed? If these theories are essentially looking at the same universal truth in different ways, why were they approached from such different angles? (There were more or less 6 years between Godel's proof and Church's). Finally, can we essential say that the concept of provability in a formal system (proof calculus) is identical to the concept of computability in recursion theory (Turing machines/lambda calculus)?


texts: Question about the definition of projecting concepts in learning

texts:
I am self-studying in the area of query learning and having a difficulty in understanding the definition of closed under projection for concept classes discussed in several papers (for example, here (page 2), here page 18 and here page 8) with regard to learning from membership queries in Query learning.

I have a set of elements X. Each concept is a subset of X and the concept class C is a set of concepts. For example the following is a concept class over $X=\{x_1,x_2,x_3,x_4,x_5\}$ with three concepts $f_1$,$f_2$ and $f_3$ represent respectively the sets $\{x_2,x_3,x_4\}$ $\{x_1,x_5\}$ and $\{x_1,x_2,x_4\}$.

      x1|x2|x3|x4|x5
  f1  0 |1 |1 |1 |0
  f2  1 |0 |0 |0 |1
  f3  1 |1 |0 |1 |0

The definition is different from restricting boolean functions to a specific range $A\subseteq X$ and can be stated as follows :

  $C$ is a set of boolean functions $\{0,1\}^n\rightarrow\{0,1\}$. A partial assignment $p$ is $(p_1,p_2,\dots,p_n)$ where $p_i\in\{0,1,*\}$. $C$ is closed under projection if for every concept $f\in C$ and for every partial assignment $p$, $f(p)\in C$.

My issue is what's the shape of $f(p)$. What I understand from the definition, is that first I need to see the class as set of boolean functions:

      000|001|010|011|100|101|110|111
  f1  0  |1  |1  |1  |0  | 0 | 0 | 0
  f2  1  |0  |0  |0  |1  | 0 | 0 | 0
  f3  1  |1  |0  |1  |0  | 0 | 0 | 0

(as |X|=5, three new elements were added and mapped to 0).

Then for $x\in X$ the projection of $x$ to $p$, $p(x)=(d_1,d_2,\dots,d_n)$ such that $d_i=p_i$ for all $p_i\in \{0,1\}$ and the $ith$ value in $x$ if $p_i=*$. For example, $x=(0,1,1)$ and $p=(1,*,0)$ will result in $(1,1,0)$.

It is assumed that most of the classes in the literature are projecton-closed.

Consider the concept $f_3$ and $p=001$, the projection $f_p$ is a new concept such that $f_p(x)=f_3(p(x))$ for every $x\in X$. As $p$ projects every $x$ to $001$ and $f_3(001)=1$ we have $f_p=\{1,1,1,1,1,1,1,1\}$ . If my understanding is correct then any concept class where initially $|X|\neq 2^n$ will not be projection-closed. Is this true? I'm 99% sure I'm wrong but don't know where.


texts: In the paper Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps and spectral techniques for embedding and clustering." In NIPS, vol. 14, pp. 585-591. 2001 The author uses methods from spectral geometry, specifically Laplace-Beltrami operator, after searching around about the topic of spectral geometry I found the lectures and books beyond my background. What are the background materials I need to study/read (Lecture notes-references-...) before reading a book or a lecture about spectral geometry?


texts: Langton's ant highway conjecture and undecidability

texts:
I was recently reading about Langton's ant and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'.

I also read that it has been shown that Langton's ant can be used to simulate any boolean circuit thus the ant is capable of universal computation.

But I am confused by those two facts because if the conjecture is true, then every computation performed by the ant will eventually end up to a highway which is easily detectable thus making any problem related to Langton's ant decidable. But how can this be true if Langton's ant is computationaly equivalent to a Turing machine for which there exist many undecidable problems?

I also read this paper and it specifically says in section 1.2: "If the conjecture is true, then any problem associated to the ant, whose input is an initial configuration with finite support, is decidable" whereas in section 1.3 it states: "There are undecidable problems associated to the behavior of the ant."

I suspect that my confusion on the matter has something to do with the finiteness/infiniteness of the input since in section 4 of the previous paper it says that Langton's ant universality is "a rather weak notion of universality (which requires an infinite - but finitely described - configuration)" which I'm not entirely sure I understand.

So my question is what's wrong with the above reasoning which suggests that the highway conjecture should be false (otherwise there would be no undecidable problems)?


texts: Extensions of beta-theory of lambda calculus

texts:
The beta-eta-theory of the lambda-calculus is Post-complete.  Can additional rules be added to extend the beta-theory of the lambda-calculus to get confluent theories other than the beta-eta theory?

Postscript

This question violated my own rule that questions should explain why the questioner cares.

It struck me one night, not long before this site went into private beta, that because extensionality and the principle of the excluded middle are related, the eta rule is some sort of extensionality rule, and there are intermediate logics between intuitionistic and classical logic, then it would be interesting if there was such a thing as "intermediate eta" theories.

If I has done so, it would have been obvious that Evgenij's answer raises an obvious problem in the way I'd formulated the question, rather than being what I was after.


texts: Interdisciplinary topics between control theory and theoretical computer science

texts:
I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, nonlinear, optimal, stochastic), advanced signal processing and convex optimization.

I am trying to figure out a good area to tackle for my dissertation paper and I was wondering whether I can somehow relate to some TCS subject.

The only area that I can think of it could relate is optimization, but I don't have anything particular in mind, the whole subject being very interesting.

It would be great if you could share which topic you think belongs to both worlds.

PS: This question might be totally out of the scope of this Q&A site, so I totally agree if you feel like it's worth closing. Thanks!


texts: Canonical labeling of special classes of DAGs

texts:
Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.

  What are some special classes of DAGs that can be canonized in polynomial time ?


texts:
Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a $(0,1)$-matrix with $1$'s at places corresponding to entries where the vertices are adjacent and $0$'s otherwise).

It is known that for a given connected graph $G$ with $n$ labeled vertices, let $λ_1,λ_2,...,λ_{n−1}$ be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of $G$ is $t(G)=\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}\,$

Now I want to extend it to the steiner tree. A $T$-Steiner tree is a subgraph of $G$ that is a tree and that spans $T$. When $T=V(G)$, a $T$-Steiner tree is a spanning tree. My question is that what is the connection between general $T$-Steiner tree and the Laplacian matrix? So far I didn't find any known results about this extension. Your comments and discussion are welcome.


texts:
I'm a fourth year PhD student in theoretical computer science. I'd like to stay in academia, so I'm thinking about how best to advance my career. Obviously the best way to do that is write lots of good papers, but another question is whether I should be trying to have more of those papers be single author.

So far I only have one single author paper (out of six). It's neither my best work, nor very recent. Is that a red flag when applying for postdoc or faculty positions? Should I try to have more single author papers?

This comes down to my approach to research. I like talking to people. I like telling people what I'm working on and, if they are interested, I'm keen to work with them. In other words, I'm very open to collaboration even when it isn't strictly necessary. Should I change that? That is, should I try to keep projects to myself more so that I end up with some single author papers?

Apologies if this question is off topic. I want to ask this question to people in my area, rather than on a general forum like academia.se. In particular, on all my papers, authors are ordered alphabetically. This makes single author papers a more important signal in TCS than in other areas, where author ordering conveys this information.


texts: Are there alternatives to using polynomials in defining the different notions of efficient computation?

texts: Is invoking polynomials in defining the different notions of efficient computation the real obstacle to resolve the P vs NP problem? Do we need a paradigm shift by redefining what constitute an efficient computation?


texts:
There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one available? As I assume there isn't, I open this question (is this supposed to be a community wiki? I don't know about this stuff).

Ideally the list should cover the different "types" of NEXP-complete problems, perhaps with some healthy redundancy to get the big picture, but without repeating itself too much. For example, it is good to have two or three different succinct versions of the same NP-complete problem as examples, if the succinct encodings come in slightly different forms. Not a dozen. A clean way to add the redundancy is by adding clauses of the form "Also NEXP-complete if BLAH". Clauses of the form "Remains NEXP-complete if the input graph has degree at most BLAH" are also welcome.

Finally, let me add a personal preference. I am most of all interested in complete problems of "algebraic" flavor, if there are any. For example, my favorite #P-complete problem is the permanent for its algebraic flavor. I hope the equality NEXP = MIP can also provide some nice algebraic NEXP-complete problem that I am not aware of.


texts: Guarding paths variant of the Art Gallery Problem

texts:
The optimization version of the traditional Art Gallery problem asks for a minimum set of point guards that can be placed within a polygon, such that any point in the polygon is visible from at least one guard.

Has there been a study of guarding a given set of paths (e.g. piecewise linear) that lie within the polygon (instead of guarding the entire polygon) with minimum number of guards? The closest related works I found are

Chapter 4 from Urrutia's book covers a set of problems about "illuminating" a set of lines with floodlights. This is fundamentally different since the lines themselves act as obstacles, whereas I'm interested in the version where the paths can be thought of as transparent and only the polygon boundary affects the visibility.
Minimum Line Cover Problem which asks for the minimum set of points to cover a set of lines (or vice versa) lying in the plane. There is no notion of visibility.

If there is a finite set of candidate guard locations, then general set cover techniques can be applied to yield a log approximation. However, I'm wondering if there has been a systematic study of this variant of the problem.


texts: Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

texts:
As explained on MO computing
the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough
for deciding 3-colorability.

For non adjacent vertices $u$ and $v$, $G+uv$
is the graph with the edge $uv$ added and
the graph $G/uv$ is obtained by merging the two vertices.

According to wikipedia

$$P(G,k)= P(G+uv, k) + P(G/uv,k) \qquad (1) $$

The recursion for computing $P(G,x)$ modulo $x-3$
is siginificantly faster since induced $K_4$ stops
computing further.

Consider the following naive algorithm for checking
3-colorability using $P(G,x) \pmod{x-3}$.

 function color3(G: connected graph)
 #returns 0 if G is not 3-colorable, otherwise reports it is and stops
 if G contains induced K_4
     return 0
 if G is a clique on 3 or less vertices
     report '3-colorable'. Stop.
 if we can add edge uv which induces K_4 in G
     return color3(G/uv) #the induced K_4 contributes 0 to the sum
 #the above makes the problem strictly smaller
 #this might be greatly improved by trying to induce K_4-e
 [C] pick the lexicographic first non-adjacent u,v and return color3(G+uv)+color3(G/uv)

One call to color3 is polynomial, so the complexity
depends on the number of double recursion in [C].

According to Wikipedia the worst case for computing (1)
is $\phi^{n+m}$. 3-coloring 4-regular graphs is NP-complete,
so for 4-regular it is $\phi^{3n}$.

Appears to me terminating by induced $K_4$ would greatly
improve the running time.

Questions:

  Q1 What is the complexity of color3?

$O(c^n)$ for small $c$ will be of practical interest.
$2^{o(n)}$ might indicate complexity collapse.

  Q2 How to improve [C]?

There might be other improvements like other 4-chromatic
subgraph or $F$ being in a graph class where coloring is polynomial.

Experimental results:

For several 4-regular graphs on 246 vertices which are the line
graphs of 3-regular graphs color3 found 3-coloring in less than
a minute in sage 6.2 implementation. For several smaller
graphs which are not 3-colorable it correctly returned 0.
For reduction SAT to 3-color the running time was fast too.

Sage implementation:  https://gist.github.com/jor0/039127ab69dd8934c105


texts: s-t connectivity on infinite planar graphs with finite description

texts:
I would like to know if the following problem is known and has been studied:
Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, more formally:

the set of vertices $V$ is a subset of the infinite lattice ($V \subseteq \{ (x,y) \mid x,y \in \mathbb{N} \}$), and
the set of edges $E = \bigcup E_i$ (which also defines $V$) is given using a finite set of linear equations:

$E_i = \{ (P_i,P_i') \}$ where the two nodes $P_i,P'_i$ are nodes at coordinates:
$P_i = (x_{i} + a_ix, y_{i} + b_i y)$,
$P_i' = (x'_{i} + c_i x, y'_{i} + d_i y)$
For each $E_i$ we can have one the following cases: $x,y\geq 0$ (which creates an infinite rectangle of "tiles"); $x \geq 0, y = 0$ (which creates an infinite horizontal strip of "tiles"), $x = 0, y \geq 0$ (which creates an infinite vertical strip of "tiles"); $x=y$ (which creates an infinite diagonal strip of "tiles").
So the set $E_i$ is defined by the constants $x_i, x'_i, y_i, y'_i, a_i, b_i, c_i, d_i$ and there is an edge for every value taken by $x,y$.
The set of nodes is given by the union of all the endpoints of the edges.

It's not so hard to prove that the s-t connectivity problem ("Given two nodes $s,t$; is there a path from $s$ to $t$?") is undecidable for non planar graphs (using for example a set of "graph tiles" arranged to simulate the configurations of a two counters machine, in which the value of the counter $c_1$ is the $x$-coordinate, and the value of the counter $c_2$ is the $y$-coordinate).

But, is it still undecidable if the graph is planar ?
If it is still undecidable on planar graphs, for which subclasses of graphs the problem becomes decidable ?


texts: Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

texts:
I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ and $\varepsilon \in (0,1)$, with the promise that either $\sum_{k=1}^n a_k = 1$ or $\sum_{k=1}^n a_k \leq 1-\varepsilon$.

How many queries (lookups) are sufficient and necessary for an (adaptive) randomized algorithm to distinguish between the two cases, with probability at least $2/3$?

I have found a previous post that gives a logarithmic (in $n$) upper bound for the related problem of approximating the sum, and a roughly matching lower bound on that problem for deterministic algorithms; but couldn't find a result for the specific problem I am considering (in particular, randomized algorithms).

Edit: Following the answer below, I guess I should have been clearer: in the above (and particularly in the asymptotics for the lower bound), $n$ is the "main" quantity seen as going to infinity, while $\varepsilon$ is an (arbitrarily small) constant.


texts: LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?

texts:
Given any Integer Linear Program (ILP) there are 2 ways to approximate it:

Write down ILP, convert to LP by relaxing the integer constraints and round the solution
Write down the ILP, convert to LP by relaxing the integer constraints, write it's dual and solve it

Why is the second approach considered 'better'? What makes it the preferred way of approximating the solution to an ILP? What is that #2 has that #1 doesn't?

In Vazirani's Approximation Algorithms book he approximates set cover using both of the methods above, but I'm unable to discern the underlying concept of choosing #2 over #1? What "IS" the intuitive 'aha' to help me understand this?


texts: Tool for specifying operational semantics for given formally specified programming language

texts:
I am trying to translate code from one programming language into another (to be specific - from RuleML to Drools, but other pairs can be expected as well) and it would be nice to know - whether there exists more general workbenches for this.

E.g. one can formally specify programming language, that is clear. But are there any tools that can be used for capturing the formal semantics for formally specified language. It is obvious that the operational semantics is the most suitable for industrial programming languages. And - if semantics is specified then the translation from one programming language into other can be done at the meta-level. I guess, that this maybe too hard for C-to-Java translation, but it should work for more modest, recent languages that are created by academia.

I have heard about Maude, but I guess that there can be something more. My experience is that Google can not replace bibliographies or suggestions from community. Thanks.


texts: SAT in finite model theory without order

texts:
It is well known in finite model theory that without an order on the input, the expressivity is very limited. For example it is known that $FO(<,\textit{PFP})$ is equal to  PSPACE, and  $FO(\textit{PFP})$ (without any order in the input) is only PSPACE-relational, a notion defined by Abiteboul and Vianu when they proved their theorem:$FO(\textit{IFP},<)=FO(\textit{PFP},<)$ iff $FO(\textit{IFP})=FO(\textit{PFP})$. (Equivalently P = PSPACE iff P-relational = PSÄCE-relational.)

Relational machines are Turing machines with a finite number of relations. As in a database, a relation is a set of tuples of elements from a finite universe. The machine can check if a relation is empty (if a table is empty), perform Boolean operations over the relations (union, intersection, join, projection), and the usual Turing machine operations. Note that the input of relational machines is given in the relations and not on the tape. It is well known that PSPACE-relational ($FO(\textit{PFP})$) can not even compute parity, hence is less expressive than PSPACE.

One can define queries with relational machines, but one can also define functions, the answer of a function being the content of some relations and of the tape at the end of the computation. Such a machine has the property that if there are two elements $a$ and $b$ of the input such that there is an isomorphism $\phi$ sending  $a$ to $b$ and $b$ to $a$, then it is never possible to distinguish $a$ from $b$. In particular in every relation $R$ of the output, if $R(a,\overline x)$ is true, then $R(b,\phi(\overline x))$ is also.

The reason for this is that the allowed operations (union, intersection, projection and join) all respect the isomorphism. Hence the output respects every isomorphism respected by the input.

In $(a\lor b)\land(\neg a\lor\neg b)$, $a$ and $b$ are symmetric, and the function $\phi$ switching $a$ and $b$ is clearly an isomorphism of the input. Suppose there exists a function to compute satisfying assignments for $3-SAT$ instances, and whose output is $P$ (the set of variables assigned to true in a correct assignment).  Then we would either want to have $P=\{a\}$ or $P=\{b\}$. However, the isomorphism means that $P$ contains either both $a$ and $b$, or neither.

Hence we have proved that there is no PSPACE-relational function that can output an assignment to a 3-SAT instance.

My question is: how do you prove that there is no PSPACE-relational (i.e. $FO(\textit{PFP})$) that accepts only the input which has a satisfying assignment? The question is different, since I don't intend to compute the assignment and I do not ask to see $a$ or $b$ in the output, I just want to see "accept" or "reject. And contrary to the usual world of Turing machines, it is not equivalent to know if an answer exists and to find the answer, because there is no way for us to use our relational machine for the question "is there an answer with $a=true$" because we can not differentiate $a$ from $b$.


texts: For what languages is there already a theory of observational equivalence?

texts:
For a correctness proof, I'm looking for a usable notion of program equivalence $\cong$ for Barendregt's pure type systems (PTSs); missing that, for enough specific type systems. My goal is simply to use the notion, not to investigate it for its own sake.

This notion should be "extensional" — in particular, to prove that $t_1 \cong t_2$, it should be enough to prove that $t_1\; v \cong t_2\; v$ for all values $v$ of the appropriate type.

Denotational equivalence

Denotational equivalence easily satisfies all the right lemmas, but a denotational semantics for arbitrary PTS seems rather challenging — it'd appear hard already for System F.

Contextual/observational equivalence

The obvious alternative are then various forms of contextual equivalence (two terms are equivalent if no ground context can distinguish them), but its definition is not immediately usable; the various lemmas aren't trivial to prove. Have they been proved for PTS? Alternatively, would the theory be an "obvious extension", or is there reason to believe the theory would be significantly different?

EDIT: I didn't say what's hard above.

Easy part: the definition

Defining the equivalence is not too hard, and the definition appears in many papers (starting at least from Plotkin 1975's study of PCF, if not earlier — the source might be Morris's PhD thesis from 1968).
We $t_1 \cong t_2$ if for all ground contexts $C$, $C[t_1] \simeq C[t_2]$ — that is, $C[t_1]$ and $C[t_2]$ give the same result. You have a few choices here with lots of alternatives: For instance, in a strongly normalizing language, if you have a ground type of naturals, you can say that ground contexts are the ones that return naturals, and then $a \simeq b$ means that $a$ and $b$ evaluate to the same number. With nontermination, for reasonable languages it is enough to use "X terminates" as observation, because if two programs are equivalent when observing termination, they're also equivalent when observing the result.

Hard part: the proofs

However, those papers often don't explain how hard it is to actually use this definition. All the references below show how to deal with this problem that, but the needed theory is harder than one thinks. How do we prove that $t_1 \cong t_2$? Do we actually do case analysis and induction on contexts? You don't want to do that.

As Martin Berger points out, you want to use, instead, either bisimulation (as done by Pitts) or a logical equivalence relation (that Harper simply calls "logical equivalence").

Finally, how do you prove extensionality as defined above?

Harper solves these questions in 10 pages for System T, through considerable cleverness and logical relations. Pitts takes more. Some languages are yet more complex.

How to deal with this

I'm actually tempted to make my proofs conditionally on a conjectured theory of equivalence for PTS, but the actual theories require nontrivial arguments, so I'm not sure how likely such a conjecture would be to hold.

I'm aware (though not in detail) of the following works:

Andrew Pitts (for instance in ATTAPL for an extended System F, and in a few papers, such as the 58-page "Operationally-Based Theories of Program Equivalence").
Practical Foundations of Programming Languages (chapters 47-48), which is inspired by Pitts (but claims to have simpler proofs).
A logical study of program equivalence. I can't find an English abstract, but it seems to spend a great deal of effort for side effects (references), which seems an orthogonal complication.


texts: Why does ML's Value Restriction stop you from capturing parametric values?

texts:
Here the MLton manual explains ML's value restriction. Specifically, it disallows functions to take on multiple parametric instantiations if they have a closure over local variables.

  Edit: note from the answer that the MLton manual is wrong about the
  value restriction. See instead Real World Ocaml.

Why is this a problem in ML when C# can easily form closures over parametric variables?

For example, this code is invalid, because ML will not allow this function to parameterize over int and string in the same program, because it has a let binding.

val f = let in fn x => x end
val _ = (f "foo"; f 13)

However, I can easily make a C# function which captures a parameterized variable, and parametrically instantiate it over both int and string. I've made the example more convincing, because a literal translation of the above ML is a trivial C# program.

class Program {

    static Func<A> foo<A>(Func<A,A,A> fn, A initial, A accumulate) {
        A cur = initial;
        return () => {  cur = fn(cur,accumulate); return cur;};
    }

    static void Main(string[] args) {
        var my_bar_a = foo( (x,y) => { return x+y;}, 0, 1);
        var my_bar_b = foo( (x,y) => { return x+y; }, ":", "-");

        Console.WriteLine("a: " + my_bar_a().ToString());
        Console.WriteLine("a: " + my_bar_a().ToString());
        Console.WriteLine("b: " + my_bar_b().ToString());
        Console.WriteLine("b: " + my_bar_b().ToString());
        Console.WriteLine("a: " + my_bar_a().ToString());
        Console.WriteLine("b: " + my_bar_b().ToString());
    }
}

output as expected:

a: 1
a: 2
b: :-
b: :--
a: 3
b: :---

Why does ML prevent us from doing this?


texts:
I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space.

Given $n$ points in $d$-space ($d>3$), I can compute an initial Delaunay graph in $\mathcal{O}(n^{ \lfloor\frac{d}{2}\rfloor })$ time.
My algorithm then operates on this graph recursively by selecting a subset of simplices, in each of which I would like to insert a single new vertex.

I do not have any preference as to where a new vertex is inserted in each selected simplex. Knowing this, I think intuitively that if I choose to insert it at the barycenter of the simplex, I can extend my Delaunay graph in constant time for each selected simplex. Is that correct?


texts: Estimate smooth vector, from dot-product queries

texts:
I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$.  I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$.  I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^n \to \mathbb{Z}$, defined by

$$f_\mathbb{s}(\mathbb{x}) = \mathbb{s} \cdot \mathbb{x}$$

(the dot-product of $\mathbb{s}$ and $\mathbb{x}$).  Also, I know that $\mathbb{s}$ is smooth, in some sense: $\mathbb{s}_i$ varies slowly as a function of $i$.  I'm open to reasonable ways to formalize that, but one formulation is that we can assume that $||\mathbb{s}'||_2$ is very small, where $\mathbb{s}'$ is the vector of first-order discrete derivatives, namely,

$$\mathbb{s}'_i = \mathbb{s}_{i+1} - \mathbb{s}_i.$$

The goal is to estimate/approximate $\mathbb{s}$: i.e., to output a vector $\mathbb{t}$ such that $||\mathbb{t}-\mathbb{s}||_2$ is small.

One can recover $\mathbb{s}$ exactly given $n$ queries to $f$, by using linear algebra (even without needing the smoothness constraint).  But given knowledge that $\mathbb{s}$ is smooth, is there a more efficient way to estimate $\mathbb{s}$, using fewer queries?

In other words, the algorithm task is as follows:

Input: $n$, an oracle for $f_\mathbb{s}$, an upper bound on $||\mathbb{s}'||_2$
Output: $t \in \mathbb{Z}^n$ such that $||\mathbb{t}-\mathbb{s}||_2$ is small

In my application, $n$ is large (say, around 10,000) but $\mathbb{s}$ is very smooth, so I'm hoping it might be possible to estimate $\mathbb{s}$ with many fewer than $n$ queries.  It would be fine to assume we are working over $\mathbb{R}^n$ if that's easier.  In practice I have $\mathbb{s} \in \{0,1,\dots,255\}^n$.  I'm not wedded to this exact definition of smoothness or of approximation of $\mathbb{s}$ (e.g., some sparsity constraint or other norm might also be a reasonable formulation).

Are there any techniques for this type of problem?


texts: Do circuits allow to derive EXPSPACE hardness results?

texts:
It seems that encoding an NP-complete problem succinctly often makes it nexptime-complete. For instance, 3SAT or HAMILTONIAN PATH become NEXPTIME-complete when the encoding is succint, eg using circuits.

Can a similar approach be taken for PSPACE-complete problems? For instance, do we get EXPSPACE-completeness if QBF or GENERALIZED GEOGRAPHY are encoded using circuits?

I see Ryan Williams has a paper discussing SUCCINT-QBF but I am not familiar enough with complexity theory to understand it.


texts: Adding integers represented by their factorization is as hard as factoring? Reference request

texts:
I'm looking for a reference for the following result:

  Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.

(I'm pretty sure it's out there because this is something I had wondered at some point, and then was excited when I finally saw it in print.)

"Adding two integers in the factored representation" is the problem: given the prime factorizations of two numbers $x$ and $y$, output the prime factorization of $x+y$. Note that the naive algorithm for this problem uses factorization in the standard binary representation as a subroutine.

Update: Thanks Kaveh and Sadeq for the proofs. Obviously the more proofs the merrier, but I would also like to encourage more help in finding a reference, which as I said I'm fairly sure exists. I recall reading it in a paper with other interesting and not-often-discussed ideas in it, but I don't recall what those other ideas were or what the paper was about in general.


texts: Rearranging strings to minimise storage in a trie

texts:
I'm currently thinking about the following problem.

Problem

Input: a set $W$ of strings over an alphabet $\Sigma$.

Goal: permute the characters in each string so that the trie that will contain the rearranged strings has as few edges as possible.

(by "permuting" and "rearranging", I mean that any permutation of the characters is valid).

Example

Given strings $S=$"ABRACADABRA" and $T=$"BARRACUDA", storing them without rearrangement would require a trie of size 20, since they share no common prefix; however, if we are allowed to rearrange them, we can obtain the following optimal solution of size 12:

0-A-B-R-A-C-A-D-R-A-B-A (S')
                 \
                  U     (T')

(where 0 denotes the root, and $S'$ (resp. $T'$) is the rearranged $S$ (resp. $T$)).

Question(s)

Has this problem been studied before, and can you give me references? What is its complexity (for $|W|\geq 3$; the problem is easy otherwise)?


texts:
I've been given a task to implement two algorithms (an exact algorithm and fully polynomial approximation scheme) for number partitioning problem. I found out that I can use some modification of heuristic approach (like complete differencing tree method) or just plain brute-force for the former, but I have a lot of trouble with the latter... can anyone point some resources where FPTAS for NPP is discussed or guidelines how to construct one?

Cheers


texts: Pi-calculus (or session types) - proof for weakening lemma

texts:
I'm writing a thesis about session types and am currently writing a section concerning type soundness for the system. I started to proof weakening lemma, which states, that
$$
\text{If } \Gamma \vdash P, \text{ then } \Gamma, x:T \vdash P.
$$
That is, names not free in a process can be added to the typing environment. However, I can't understand how to find a derivation for
$$
\Gamma, x:T \vdash (\upsilon x)P
$$
The rule T-RES for restriction is
$$
\frac
{
  \Gamma, x:T \vdash P
}
{
  \Gamma \vdash (\upsilon x)P
}
$$
I tried to find a proof for the lemma (for session types, pi-calculus or other calculi), but all the proofs seemed to be something like "a straightforward induction on the derivation of $\Gamma \vdash P$".
I'm trying to understand, what I'm misunderstanding or missing. The rule T-PAR explicitly states, that $x$ is not in the environment in $\Gamma \vdash (\upsilon x)P$. However, the lemma states, that $\Gamma, x:T \vdash (\upsilon x)P$ is valid.


texts: Partitioning a connected shape into rectangles

texts:
I imagine this must be an introductory computational geometry question, but I'm not sure of the best search phrases, and I'm interested in variations of the question, also, so I'm hoping for pointers to useful references. I'm interested in feasible algorithms for the following problem.

  Input: A connected set of points (shape) in $\mathbb{Z} \times \mathbb{Z}$.
  Output: A partition of the shape into rectangles, such that the rectangles do not overlap one another, and they cover only the shape, no "empty" space.

I'm interested in finding the minimum number of rectangles, the "best" set of rectangles for any notion of best, whether this problem becomes easier or harder for different classes of shapes.

Thank you. :-)


texts: Are there stronger notions of equivalence over lambda terms than beta equivalence?

texts:
I should add the context that I am concerned with strongly normalizing systems like System-F.

I have what I consider a very strong notion of equivalence for lambda terms that goes something like the following (not super formal)

if $E_1$ and $E_2$ have WHNFs $\lambda x:t.E_1'$ and $\lambda x:t.E_2'$ then $E_1 = E_2$ if $\forall x:t. E_1' = E_2'$
if $E_1$ and $E_2$ have WHNFs that are not $\lambda$s then they must be constructively equivalent. If $\lambda$s are elements of $E_1$ and $E_2$ they must be in the same structural locations and be equivalent by 1.

Is this notation of equivalence stronger than beta equivalence for strongly normalizing systems? If not is it equivalent? Are there stronger kinds of equivalence (or perhaps ones in the same spirit but more formal)?

Thanks!


texts: What would a PDA be with a queue instead of a stack?

texts:
A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton with a deque model is TM equivalent. Intuitively because analogous to moving a head over a fixed tape, the deque model allows for moving the tape under a fixed head. Formally I think this could be proved nicely via equivalence with a dual stack PDA.

The queue model continues to puzzle me however, since it seems to define a class of languages quite different from the context-free languages (stack vs. queue seems to be analogous to nested vs. cross-serial character dependencies). I haven't been able to prove or disprove whether the queue model also accepts context-free languages though, so it might just as well turn out to be TM equivalent too. On the other hand I also couldn't construct the equivalents of the TM transition relations using the queue model, it seems to fall just short of 'full TM power'.

At this point I've started going in circles, so I'm left with the question whether the queue model would really define a separate (not necessarily useful) class of languages or not. It seems a simple question but I haven't been able to find any conclusive literature on this, so I was hoping someone could point me to an answer to this question.


texts: Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$

texts:
The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary code of length $n$ and distance $d$. More specifically, let the hamming weight of an element of $\mathbb{F}_q^n$ be its $l_0$-pseudonorm, the number of non-zero components, and the hamming distance between two elements $f,g$ the weight of their difference $d(f,g)$. Then $A_q(n,d)$ is the largest set $S \subset F_q^n$ s.t. for two elements $f,g \in S$, $d(f,g)\geq d$.

There are a number of famous upper bounds on $A_q(n,d)$, including Hamming's sphere packing bound. The best are given by a linear programming approach (now improved to a semi-definite programming approach) given by Delsarte in the late 70s. I have recently been searching for an explicit formula for Delsarte's Linear Programming Upper Bound for $A_q(n,3)$ in the literature, which correspond to single error correcting codes, and have not had much luck for non-binary codes. For binary codes this appears to be well known, and shown as early as 1977 by Best and Brouwer.

Non-binary codes seem to be a completely different story. There is a paper called "Some upper bounds for codes derived from Delsartes inequalities for
Hamming schemes" by C. Roos and C. de Vroedt, which the authors claim deals with the q-ary case, but I have not been able to find a copy. There appears to have been a very large amount of work in this field so I would be shocked if no such formula exists (well, at least a formula for some special cases of n,q).

Is there a body of work in this area I am missing? Do such formulae exist?

Note: I have also posted this question to MO, since I think $A_q(n,d)$ has received significant attention from both communities. The link is: https://mathoverflow.net/questions/293549/explicit-formula-of-delsartes-linear-programming-upper-bound-for-a-qn-3


texts: Distinguishability a set of permutations

texts:
Given integers $d<n$, find the largest $k$ such that there exists a set of $k$ permutations $\sigma_1,\cdots,\sigma_k$ on $[n]$, such that any size-$d$ subset $T\subseteq [n]$ is ``distinguishable'' by the permutations.

Here we say that a set $T$ is NOT distinguishable by two permutation $\sigma,\sigma^*$ if we view both permutations as arrangements of $[n]$ into a sequence, and the restricted orders on $T\subseteq [n]$ in both arrangements are the same, otherwise it is distinguishable by $\sigma$ and $\sigma^*$. We say that a subset $T\subseteq [n]$ is distinguished by a collection of permutations if it is distinguishable by every pair of permutations in the collection.

Probably it is hard to express $k$ in terms of $n$ and $d$, so we shoot for asymptotic lower or upper bounds on $k$. Actually I am more interested in the case where $d$ is small (let's say $d=O(\sqrt{n})$). Any previous results or relevant ideas are appreciated.


texts: Lower bounds for quantum circuits using the geodesic framework

texts:
Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance from $I$ to an element $U$ is a lower bound on the number of gates in a quantum circuit that computes $U$).

I was wondering if there were concrete examples of problems where this program led to a lower bound that came close to, matched or beat prior lower bounds obtained by other means ?


texts:
I'm given a universal set $N = \{1, 2, \dots, n\}$, a family of sets $\mathcal{F} = \{ S_1, S_2, \dots, S_m \}$, $S_i \subseteq N$, and I need to count the number of distinct ways to cover the universal set using sets from $\mathcal{F}$.

I've found a couple of articles describing the usage of inclusion-exclusion principle to tackle a similar problem:

Set partitioning via inclusion-exclusion
Dynamic programming based algorithms for set multicover and multiset multicover problems

The papers describe how to compute the number of $k$-covers $c_k$. A $k$-cover is a tuple $(S_1, \dots, S_k)$ over $\mathcal{F}$ such that $S_1 \cup \dots \cup S_k = N$. According to the papers,
$$c_k(\mathcal{F}) = \sum_{X \subseteq N} (-1)^{|X|} a(X)^k$$ where
$a(X) = |\{S \in \mathcal{F} \mid S \cap X = \emptyset\}|$ (the number of sets in $\mathcal{F}$ that avoid $X$).

I like this method because it (at least, theoretically) allows to compute the number of covers in $O(n 2^n)$ time. A simple DP approach I can think of requires $O(|\mathcal{F}| 2^n)$ time and is too expensive since in my case $|\mathcal{F}|$ is slightly less than $2^n$.

I tried this formula on a simple example $\mathcal{F} = \{ \{1\}, \{2\}, \{1, 2\}\}$

$$
\begin{array}{c|c|r}
X & a(X) & (-1)^{|X|} \\
\hline
\emptyset & 3 & 1 \\
\{1\} & 1 & -1 \\
\{2\} & 1 & -1  \\
\{1, 2\} & 0 & 1
\end{array}
$$
$$
\begin{array}{c|c|c|c}
k & c_k(\mathcal{F}) & c_k \text{(computed)} & \text{Number of covers} \\
\hline
1 & 3 - 1 - 1 + 0 & 1 & 1\\
2 & 3^2 - 1^2 - 1^2 + 0 & 7 & 3 \\
3 & 3^3 - 1^3 - 1^3 + 0 & 25 & 1  \\
\end{array}
$$

I don't know how to interpret the values of $c_k$ I've got. They look really strange. Is this method correct? Or is there a simpler way to count set covers in $O(n 2^n)$ time?


texts: Hereditary Substitution with Inductives and Eliminators?

texts:
I'm wondering, is there any existing work on hereditary substitution with inductive type families and dependent eliminators?

In particular, normalizing the application of an eliminator to an inductive value "obviously" halts, since the head of the elimination is structurally smaller each time.

But, I'm wondering, how does it fit into the structurally-shrinking argument of hereditary substitution? For example, in Harper and Licata's presentation, hereditary substitution is always strictly decreasing, structurally in the value being substituted into, or in the shape of the type of the variable being replaced.

But, if we have:

$natElim: (m : Nat \to Set) \to m\ 0 \to (k : Nat \to m\ k \to m (succ\ k) ) \to (k : Nat) \to m\ k$

and we are computing $[1/x](natElim\ m\ z\ (\lambda k\ p\ldotp t_1)\ x)$, we must compute:

$[0/x](natElim\ m\ z\ s\ x) = t_2$,
$[0/k]t_2 = t_3$
$[t_2/p]t_3 =t_4$
to get a result of $t_4$.

But these are not decreasing in either the type of $x$ or the term being substituted into. The first two are decreasing in the value replacing the variable, but the third is not.

Is their prior work on this? I can think of ad-hoc ways to make the decreasing size argument work for Nat, Vec, etc. But is there a general argument for inductive types?

This is possibly related to my previous question question: I'm not sure if this falls under the "large eliminators" described there. If this only works for "small eliminators", I'm still interested in a reference for this.


texts: Arranging letters to make a word in a regular language

texts:
Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input:

some number $m \in \mathbb{N}$ of copies of the letter $a$, and
some number $n \in \mathbb{N}$ of copies of the letter $b$ but each copy $1 \leq i \leq n$ comes with a constraint expressed as a pair of integers $(p_i, q_i)$ which means: "there must be at least $p_i$ $a$'s to the left of this $b$ and at least $q_i$ $a$'s to the right of this $b$".

My goal is to decide if I can construct a word of length $m + n$ with $m$ letters $a$ and $n$ letters $b$ that falls in the language $L$ and where every copy of $b$ was put at a position that satisfies its constraints. (Formally: there is an injective function $f$ from $\{1, \ldots, n\}$ to $\{1, \ldots, n+m\}$ such that, letting $A$ be the elements of $\{1, \ldots, n+m\}$ that are not in the image of $f$, for each $1 \leq i \leq n$, the set $A$ contains at least $p_i$ integers that are $< f(i)$ and at least $q_i$ integers that are $> f(i)$.) Note that the $b$'s can be put in any order (as long as their constraints are satisfied), they needn't be put in the order in which they are in the input. In other words, $f$ need not be an increasing function.

Is this problem in polynomial time for every regular language $L$, or is there a language $L$ for which the problem is NP-hard?

I have a PTIME greedy algorithm that works if $L$ has only one word of every length, e.g., it is something like $(ab)^*$. In this case, you should go over the even positions (where $b$'s must go) and at each position put a copy of $b$ which is available and which is as constrained as possible, i.e., the constraint $p_i$ is satisfied, and the constraint $q_i$ is as large as possible. It is clear that this algorithm respects the constraints if it succeeds, and that this is always the best way to place the $b$'s. However when $L$ contains multiple words of length $m+n$ then this no longer works and I can't see a dynamic algorithm to solve the problem.

(This question relates to this earlier question of mine but the main difference that the alphabet is now restricted to be $\{a, b\}$ so the previous proof does not work. The problem can also be equivalently phrased in terms of topological sorts in which case it is a rephrasing of a problem in this list.)


texts: How to generate Extended Finite State Machines Randomly with some properties?

texts:
This is related to my academic project

An extended finite state machine is a tuple $SM=(I,S,T)$ (simplified):

$I$ is the set of identifiers and it's divided into two sets Inputs and outputs, for simplification we will just consider boolean variables. Let $\sigma$ be the evaluation function $\sigma :I \to \{0,1\}$ which associate to very identifier its value, And let $\Sigma$ be the set of all evaluations.
$S$ is the set of states
$T\subseteq S\times S \times G\times A$ the set of transitions, a transition $t=(s_1,s_2,g,a)$ means :

$s_1$ the source state
$s_2$ the target state
$g$ the guard,which is usual expressed in the guard language and here we can just consider it as its semantic $g:\Sigma \to \{0,1\}$ where $g(\sigma)$ is an element of $\{0,1\}$.
$a$ is usually expressed in the action language, and we will here identify it with its semantic $a:\Sigma \to \Sigma $ where $f(\sigma)$ is another evaluation function.

Now a configuration of the state machine $SM$ is a tuple $(s_i,\sigma)$ where $s_i$ is the current state and the $\sigma$ the current evaluation function. A run of the machine is :
$$(\sigma_0,s_0)\to(\sigma_1,s_{1})\to (\sigma_2,s_2)\to \cdots (\sigma_k,s_k)\to(\sigma_{k+1},s_{k+1})\to \cdots $$
where for every $k$ we have $(s_k,s_{k+1},g,a)$ is a transition and $g(\sigma_k)=1$ (meaning true) and $a(\sigma_k)=\sigma_{k+1}$

Example of action : we denote an action by $Rep(a)=[e_1,\cdots,e_n] $ where $e_i$ is a boolean expression over the variables in $I=[o_1,\cdots,o_n,i_1,\cdots ,i_k]$ where $i_j$ are the inputs of the system and are determined by the environment. And from this representation of the action we can have $a(\sigma)(x)=e_j(\sigma) $ if $x=o_j$ and $a(\sigma)(x)=i_j$ if $x=i_j$

The guards  are represented by expressions over the set of the variables $I$

What I am  able to do : I was able to generate some boolean expressions that are valid or satisfiable using either well known examples, or using the threshold density of boolean formulas. Hence I am able to generate the guards and the actions (which are random, and have some properties like satisfiable or valid)

  Question : how could I generate a random Extended State machine with the property that: Every state is reachable and every transition can be executed

you can use that fact that I am able to generate a formula that evaluates to $1$ or $0$ and I can generate a satisfiable or unsatisfiable formula

Any other ideas to do  tests  with Extended State Machines?
Thanks

Edit 29/04/2016

As my question is either not very clear or difficult; I have an alternative question:

  Question 2: what are some well known random Extended State Machines for which every state is reachable.

The purpose of my project is to test the efficiency of an algorithm


texts: Google quantum supremacy experiment data

texts:
I don't know if this is the right place to ask.
Still, I vaguely remember that there was a desire expressed by some people in this community to get access to the data of the 53 qubit Google quantum supremacy experiment, given that the data released for Google previous experiments, which was sometimes cited as evidence,  regarded much smaller number of qubits.
So I want to ask if since then the data for the 53 qubits original experiment was released and, if yes, where one can find it.


texts: Maximum difference between two shortest paths

texts:
My problem is the following maximization problem:

Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two targets $v$ and $w$.

Problem: Compute
$$ \max\{ c_p - c_q | p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path}, c \in [l,u] \} $$
with $c_p$ and $c_q$ being the costs of path $p$ and $q$, respectivly.

I cannot image that that this problem has not been studied, but i cannot find anything. Does someone know the name of this problem and any resources.

Thanks in advance.

The problem can also be formulated as the following bilevel program:

$$ \max ~~~~~~~~~~~~~ c^Tx - c^Ty ~~~~~~~~~~~~~~~~~~~\\
s.t. x \in \arg\min \{ c^Tx| Mx=b^{s,w} \}, \\
~~~~~~~  y \in \arg\min\{ c^Ty | My=b^{s,v} \},  \\
 l \leq c \leq u  $$

with $M$ being the vertex-edge incidence matrix of the graph and $b^{s,v},b^{s,w} \in \{0,1\}^V$ defined as follows: , $b_s^{s,v} = b_s^{s,w} = 1$, $b_v^{s,v} = b_w^{s,w} = -1$, and $0$ otherwise.


texts: Why do constructivists not seem to care too much about call/cc

texts:
So a little while back I first had someone tell me that call/cc could allow proof objects for classical proofs by implementing Peirce's law. I did some thinking about the topic recently and I can't seem to find a flaw with it. However I can't really seem to see anyone else talking about it. It seems void of discussion. What gives?

It seems to me that if you have a construction like $f : \neg(\neg P)$ in some context then 1 of two things is true. Either you have access to an instance $\bot$ somehow in the current context in which case control flow would never reach here and we are safe to assume whatever OR given that $f : \neg(\neg P)$ means $f : (P \to \bot) \to \bot$ the only way $f$ can return $\bot$ is by constructing an instance of $P$ and applying it two it's argument (an instance of $P \to \bot)$. In such a case there was already SOME way of constructing an instance of $P$; it seems reasonable for call/cc to pull this construction out for me. My reasoning here seems somewhat suspect to me but my confusion still stands. If call/cc isn't just creating an instance of $P$ out of thin air (I don't see how it is) then what is the issue?

Do some well typed terms not containing call/cc not have normal forms? Is there some other property of such expressions that causes them to be suspect? Is there any noted reason why a constructivist shouldn't like call/cc?


texts: Unique naming/labeling of $40$-node strongly regular graphs

texts: Brendan McKay's webpage lists all possible $40$-node strongly regular graphs. Is there a standard  way to name them uniquely?


texts: shortest path algorithm taking into account angular deviation

texts:
I am using Floyd-Warshall(1) to compute shortest paths on a road network in order to ultimately compute betweenness centrality of road segments. At present, I am weighting the paths by metric length of road segment. I would also like to take into account angular deviation. The goal would be to favor routes that involve fewer, smaller turns (in addition to some distance weighting).

My attempts at writing a Floyd-Warshall or a Dijkstra that takes into account angle have not been working. Not sure whether this is just an implementation issue, or whether I am making a serious theoretical mistake in thinking that these types of shortest-path algorithms can take into account geometric properties like angle. The issue, I realize, is that to compute angular deviation, the algorithm will need a history of its previous path as it recurses through the network.(2)

Is this possible, and if so, any suggestions for how I can go about implementing a shortest path algorithm that takes into account angular deviation?

(1) I am using an implementation included in the NetworkX library (Python).

(2) I found this related question, but I am afraid I cannot understand if it has any implications for my question.


texts: Question on the Prize-Collecting TSP's ratio related to inapprox. of general TSP

texts:
The Prize-Collecting TSP (PCTSP) is defined as the ordinary TSP with the difference that penalties are added to nodes; so we may avoid visiting a node paying its penalty, which is added to the overall cost. It currently admits a $2-\epsilon$ approximation ratio, where edge costs are considered to satisfy the triangle inequality. Obviously, ordinary TSP is PCTSP where all node penalties are set to inf.

I would like to ask, in the case a graph which does not satisfy the triangle inequality is chosen and ALL of its edges are deleted, replaced by 2 new edges connected to a 2-degree new node for each case of deleted edge, where each edge cost is equal to the deleted edge's cost/2 and having Euclidean distance equal to that (so the new graph is metric), don't we get a $(2-\epsilon)$ approximation ratio for the original (general and therefore non-approximable) graph? (Penalties for old nodes are set to inf and to new 2-degree nodes equal to 0).

Of course, there is a mistake in my thought, since this can't be true, so if somebody finds it, I would be pleased to listen to that. Thank you in priori.


texts: How to homomorphically and "efficiently" evaluate $$(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$$

texts: Can i evaluate a formula $(a_i + b_i) \cdot c_i$ if i have the encryption of $a_i,b_i,c_i$ respectively using a homomorphic encryption scheme that supports multiplications and additions, supposing that each value is a small integer? I am aware of BGN scheme that evaluates 2-DNF formulas but in my scheme i want the other way around. Instead of $a_1 \cdot b_1 + a_2 \cdot b_2 + \ldots +a_n \cdot b_n$ i want to evaluate $(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$


texts: Primal/Dual of the Lasserre/ SOS SDP hierarchy

texts:
Sum of Squares proofs and the Lasserre hierarchy can both be stated as SDPs. It is often claimed without proof that these SDPs are dual to each other, although I do not see that this is obvious. I was hoping to get some help proving that these are in-fact SDP duals of each other.

I will state the two SDPs and then give some background information.
We will have variables $y_I$ for $I \subseteq [n]$ a multi-set and $|I| \leq d$.
Let $Y$ be an $n^d + 1 \times n^d+1$-dimensional matrix, indexed by multi-sets $I \subseteq [n]$, $|I| \leq d$, and let $Y_{I,J} = y_{I \cup J}$ (under multi-set union).
Let $A$ be a diagonal matrix.
Let $B_I$, $C_I$ be matrices of the same dimension as $Y$. Define the trace $\langle A,B \rangle = \sum_{i,j} A_{i,j} B_{i,j}$; that is, the inner product between $A$ and $B$ when treated as vectors.  We can state the primal Lasserre SDP abstractly as

$$\max \langle A, Y \rangle \\
\sum_I y_I B_I \succeq 0 \\
\sum_I y_I C_I \succeq 0 \\
y_\emptyset = 1 $$

Let $e \in \mathbb{R}^{n^d +1}$ be a vector such that $e_\emptyset = 1$ and $e_I = 0$ for all $I \neq \emptyset$. The dual is

$$ \min \lambda \\
A_I - \lambda e_I = \langle Z_1, B_I \rangle + \langle Z_2, C_I \rangle \hspace{3em} \forall I \subseteq [n], |I| \leq d \\
Z_1 \succeq 0 \\
Z_2 \succeq 0 $$

Background: Suppose that we're trying to optimize a polynomial $P_0(x)$ over $ P_1(x) \geq 0$. The Lasserre hierarchy is a hierarchy is a hierarch of SDP relaxations, where the $d$-th level is defined as follows: Let $Y$ be as above and let $p_0, p_1 \in \mathbb{R}^{n^d+1}$ be the coefficient vectors of $P_0(x), P_1(x)$ respectively. That is, $p_{0,I}$ is the coefficient of the monomial $\prod_{i \in I} x_i$ in $P_0(x)$.

Define the matrices $M(y) := Y$ and $M(y,P_1)_{|I|,|J| \leq d - deg(P_1)/2} := \sum_{|K| \leq deg(P_1)} p_{1,K} y_{I \cup J \cup K}$, and let $P$ be the diagonal matrix with $p_0$ arranged along the diagonal. Then, the primal degree-$d$ Lasserre SDP is

$$ \max P \cdot Y \\
M(y) \succeq 0 \\
M(y,P_1) \succeq 0 \\
y_\emptyset = 1 $$

We can obtain the primal SDP that I stated originally from the Lasserre SDP by letting $B_I, C_I$ be such that $M(y) = \sum_I B_I y_I$ and $M(y,P_i) = \sum_I C_I y_I$.
For more information, I recommend Chapter 1.7 in "Handbook on Semidefinite, Conic and Polynomial Optimization" https://link.springer.com/book/10.1007%2F978-1-4614-0769-0#page14


texts: Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area

texts:
I'm trying to find a solution for the following problem.
You have a set of pictures or let us assume they are just boxes with a given aspect ratio. And you have a two-dimensional area with width and height.
The boxes can vary in size only their aspect ratio is fixed, BUT they can have also have a max/min size (optional).

I'm looking for an optimal distribution of the boxes in this area, so that the remaining area is minimal.

Is there a solution to this problem, or a best practice to deal with it? Or are there any papers published on that topic?
(some toolkit for javascript dealing with this problem would be brilliant)

What I already found during my short research? Similar problem:
https://stackoverflow.com/questions/5129221/treemapping-with-a-given-aspect-ratio

I have also thought about a mathematical solution to this problem and what I came up with so far was:

x1+...+xn <= x_dimension            | x1..xn (box width)
a1*x1+...+an*xn <= y_dimension      | a1..an (aspect ratio)

of course there are multiple solution to this problem so what you then need to do is to find out which is the best. So you need to find:

min(x_remainder*y_remainder)

whereas

(x1+...+xn) - x_dimension = x_remainder
(a1*x1+...+an*xn) - y_dimension  = y_remainder

I'm not even sure if I'm on the right path with this approach, so I would also be grateful, if someone could provide me with some food for thought.


texts: Graph problems in P with unknown lower bounds

texts:
I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes:

problems, where we know of a lower bound expression in terms of decision tree complexity, but lower bounds not mentioning decision tree complexity are unknown, this would be the case with minimum spanning tree
problems, where there is no known expression of lower bounds in terms of other complexity measures, an example would be All-Pair shortest paths

Both examples are based on my limited knowledge of the literature


texts:
Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$.
Savitch provides $NL\subseteq L^{2}$.
If $P$ or $CH$ is in $\oplus L$ or $C_=L$ or $UL$ or $NL$ or their promise versions is the quadratic factor improvable to linear in Savitch's theorem (stconn reducing to simpler problem of promiseUL is something which should provide efficiency)?


texts:
Motivated by the question from this blog post,
the following data structure question seems interesting and fun to me.

Preprocess: A list of numbers $A = a_1,...,a_n$
Query(s,t,k): Return the $k$-th rank element of the sublist $A[s:t]$ where $A[s:t] = a_s,...,a_t$.

There are two trivial solutions:

Space = $n^3$, Time = $1$. Construct a look-up table
Space = $n$, Time = $O(n)$. Do nothing for preprocessing. Quick-select the $k$-th element in $A[s:t]$.

Is there some non-trivial solution?


texts: Optimal bounds for $k$-wise non-uniform random bits

texts:
Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$.

  What is the smallest sample space (or, equivalent, how many true independent random bits are needed) to generate $n$ $k$-wise independent Bernoullis with parameter $p\stackrel{\rm def}{=}1/2^t$?

This is not the same as this (related) question, since I don't want to generate uniform marginals in $\{1,\dots,2^t\}$ (which would be one way to simulate the $1/2^t$-biased coins, but one that feels very wasteful).

Alon, Babai, and Itai gave a time bound of $O(n^{k/2})$ for the case $t=1$.  Karloff and Mansour [Theorem 3 of 2] showed that for $2^t = \frac{n}{k}$, a space of size $\Omega(n^k)$ was necessary.

  Is the general trade-off as a function of $t,n,k$ known?

In particular, a simple construction would give an upper bound of
$k(\log n + t)$ bits. However, and here my intuition may be completely off, I would expect it to decrease with $t$? For $k,n$ fixed, increasing $t$ leads to more biased bits, so less entropy overall.

I am not specifically looking for explicit constructions.

[1] Alon, Noga, László Babai, and Alon Itai. "A fast and simple randomized parallel algorithm for the maximal independent set problem." Journal of algorithms 7.4 (1986): 567-583.

[2] Karloff, Howard, and Yishay Mansour. "On construction ofk-wise independent random variables." Combinatorica 17.1 (1997): 91-107.


texts:
Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations of $G$, where $d(x)$ is the degree of node $x$). I say that $\nu$ is satisfying if there exist an edge $e\in E$ such that both endpoints of $e$ are mapped to $e$ by $\nu$. I am interested in the following problem:

INPUT: An undirected graph $G$

OUTPUT: The number of satisfying valuations of $G$

My question: What is the complexity of this problem, and does it already have a name?

My guess is that it is #P-hard, even for bipartite graphs. A closely related #P-hard problem is #POSITIVE-2-DNF, or even [#PARTITIONED-POSITIVE-2-DNF][1]. Indeed, you can see an instance of #(PARTITIONED-)POSITIVE-2-DNF as a (bipartite) graph $G$, and you say that a valuation of $G$ either maps a node $x$ to all of its incident edges or to none of them. So my problem is somewhat a variant of #POSITIVE-2-DNF, but where valuations map variables to a single clause in which they occur, instead of mapping them to $0$ of $1$.

==== UPDATE ====

As a3nm showed in his answer, the problem is hard on 3-regular graphs with multi-edges. My answer shows that the problem is also hard on $2$-$3$ regular simple graphs. There is the minor question of knowing if it is hard one $3-regular simple graphs. I don't really care about it, but I still leave it here for completeness.


texts: Belief Propagation on MRF with complex cliques

texts:
Is there a belief propagation algorithm for exact inference on a MRF with complex clique structures (i.e. ones involving more than 2 neighbours)?

For MRF's with cliques that only involve pairwise interaction, you could just search out far enough and cluster to form an acyclic graph and run the usual BP. With more complex cliques, this seems impossible to me as clustering might involve cutting through a clique with multiple members on either side. Is there a workaround for this? Perhaps some clever conditioning arguments?


texts: Why are these two definitions of PLS equivalent?

texts:
In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm.

  there is a polynomial-time algorithm $C_P$ that, given $x\in\mathcal{I}_P$
  and $s\in\mathcal{F}_P(x)$, either outputs a better solution $s'\in \mathcal{N}_P(x,s)$, or reports that $s$ is locally optimal.

and

  there is a polynomial-time algorithm $C'_P$ that, given $x\in\mathcal{I}_P$ and $s\in\mathcal{F}_P(x)$,  returns
  $\mathcal{N}_P(x,s)$.

Here $P$ is a $\textsf{PLS}$ problem, $\mathcal{I}_P$ is a set of instances of $P$, $\mathcal{F}_P(x)$ is a set of feasible solutions of $x\in\mathcal{I}_P$, and $\mathcal{N}_P(x,s)$ is a neighbourhood of $s\in\mathcal{F}_P(x)$.

It is clear that the existence of $C'_P$ implies the existence of $C_P$. Why the existence of $C_P$ implies the existence of $C'_P$?

If it is not the case, could you give me a counterexample? Maybe it could be the case that $\mathcal{N}_P(x,s)$ has an exponential size and we can determine that $s$ is locally optimal by some other property of the instance $x$ or the solution $s$?


texts: Are there links between Geometry of Interaction and Geometric Complexity Theory?

texts: I'm very much a novice in these subjects, but Geometry of Interaction and Geometric Complexity Theory seem to speak similar language and have vaguely similar goals. Am I not mistaken? Are there any links between them?


texts: Is this volume computation problem #P Hard?

texts:
Let $A_{n\times n}$ be a positive definite diagonal matrix with positive rational entries, and let $b$ be a positive rational. Let $R(A,b)$ be the ellipsoid
$ \{\mathbf{x}\in \mathbb{R}^n : ||A\mathbf{x}||_2\leq b   \}$.

  Given the pair $(A,b)$, is it $\mathsf{\#P ~Hard}$ to compute the fraction of the volume of the unit ball $||\mathbf{x}||_2\leq 1$ contained in $R(A,b)$?

The motivation behind this question is: The answer is "yes" if the 2-norm is replaced with the 1-norm (see Dyer and Frieze). If the answer is "yes" for the 2-norm as well, I would like some tips as to how to do  the reduction, or links to references. This seems to be a reduction from mixed integer quadratic programming (MIQP), but  I'm not sure quite how.


texts:
Is Martin-Löf type theory basically the predicative Calculus of inductive Constructions without impredicative $\mathtt{Prop}$?

If they're closely related but with more differences than just $\mathtt{Prop}$, what are those differences?


texts: How to extend Solomonoff Induction to continuous domain

texts:
Informally speaking, Solomonoff Induction provides an Bayesian optimal way to predict the next symbol from observed symbol sequences $S_1S_2S_3...S_n$ where each $S_i$ belongs to a finite symbol set $\Sigma$. To get the posterior probability distribution of the next symbol, we make a weighted average prediction of all Turing Machines that produces first $n$ symbols. For each Turing Machine $M$ within consideration, the weight would be inverse exponential of "complexity" of that Turing Machine.

$$p(M) = 2^{-L(M)}$$

Where $L(M)$ is the description length of $M$ in context of an universal Turing Machine $U$.

If we replace:

finite symbol set $\Sigma$ to continuous domain $D$, such as $R^n$.
Symbol sequence $S_i$ to discrete time series, for example $x_1x_2x_3...x_n$ where $x_i \in D$
Turing Machine $M$ to discrete time dynamical system, for example $x_{n+1} = f(x_n)$, which is mapping $R^n \to R^n$

The Bayesian inference would still work in this case, however we have to redefine the complexity measure $p(f) \to [0, \infty)$, which is probability density function of $f$.

Question: Is there any work or related theory that extends the complexity measure elegantly to dynamical systems?

I would also be interested in results for continuous dynamical systems, in terms of differential equations.

Thanks.


texts: What languages can be reduced to a NP-complete problem in polynomial time

texts:
NP-complete: Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in polynomial time - other than languages in NP.

NP-hard: A problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H. This is reversed reducing, so I'm not sure if this is a good candidate. We don't know whether one can solve NP-hard problem in polynomial time.

  If P ≠ NP, then NP-hard problems cannot be solved in polynomial time. (NP-hardness wiki)

So, my question is what class of languages can be transformed to a NP-complete problem in polynomial time using Turing reductions and/or many-to-one reductions.


texts: Difference between abstract machines and calculi

texts:
So, first of all: I'm not sure how to tag this question. Feel free to tag it differently.

I recently started reading up on CHAMs, which can express different process calculi. Slightly confused, I go to read up on abstract machines. Okay, so, abstract machines are... machines in which you can express algorithms...

My thought process then was: [...] algorithms, which are expressed in math... which is what the calculi are for.

So, from my understanding, there's some sort of implicit layering going on here where somewhere up the math-ladder there's this abstract machine which can be used to express more mathematically pure calculi, and somewhere embedded in that jumble is the concept of an algorithm expressed in the math... of the abstract machine?

What is the difference between abstract machines and calculi, if there is one?

If there is a difference, what draws the line between abstract machines and calculi?


texts: Naming an algorithm after a copyrighted object

texts:
In machine learning, it is common to give algorithms quirky names. What happens if you think you've found a name that's actually quite fitting for an algorithm (catchy, descriptive, etc) -- but turns out there's registered company with that name (doing something completely unrelated)? Is there any way they can pursue legal action (with any reasonable chance of success) for using their name in an academic paper -- even if a full disclaimer of the two being completely unrelated is made?

[If the question is inappropriate for this forum, I'd be grateful to the moderators for migrating it to the right one!]


texts:
This question arises out of pure curiosity (it came up while thinking about unshuffling a string, but I'm not sure if it's actually related) so I hope it's appropriate.

There are various graph products, and I'm interested in any of them here. What is the complexity of determining whether a graph $K$ is isomorphic to a non-trivial product? (Certainly for the Cartesian product, $K = K \square 1$ where $1$ is the graph with one vertex.)

I've looked at the pages "factor graph" and "graph factorization" on Wikipedia, but neither seem to be related. Is this problem known under another name?


texts: Parallel solution of recurrence equation

texts:
One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the form:

$x_{1}=b_{1}$
$x_{i}=f_{i}(x_{i-1})=f(b_{i},g(a_{i},x_{i-1}))$

can be solved if the following restrictions are satisfied:
1) $f$ is associative, $f(x,f(y,z))=f(f(x,y),z)$
2) $g$ distributes over $f$, $g(x,f(y,z))=f(g(x,y),g(x,z))$
3) $g$ is semiassociative, that is, there exists some function $h$ such that $g(x,g(y,z))=g(h(x,y),z)$.

Question: Are there any other general algorithms that can solve some class of recurrence equations in parallel?


texts: Place n points in a box as far away from each other as possible

texts:
Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized.

In other words, I'm looking to put points down in a box as far away from each other as possible.


texts: About complexity of recovering or learning Bayesian networks

texts:
Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having access to some subset of the vertices?

Are there at least known conditions when this is provably impossible or when some hardness result has been proven?

I am typically assuming that the random variables (one at each vertex) are mapping the same sample space into some finite space which could be different for each random variable/vertex. I would equally well want to know if there are results with continuous distributions.
I would be equally well helped to know if there are such results known with Marokov Random Fields or Factor Graphs.


texts: Difference between locally testable and it's boolean closure

texts:
A language $L$ is called

i) locally testable in the strict sense iff there exists $P, S, I \subseteq X^*$ such that
$$
 w \in L \mbox{ iff } pref^k(w) \in P, suffix^k(w) \in S, infix^k(w) \subseteq I.
$$
for some $k > 0$.

ii) locally testable iff for $u,v \in X^*$ the following holds:

If $pref^k(u) = pref^k(v), suffix^k(u) = suffix^k(v), infix^k(u) = infix^k(v)$ then
$$
 u \in L \mbox{ iff } v \in L.
$$
Meaning if two words coincide in there infixes, suffix and prefix up to a specific length $k > 0$ then they are either both in the language or they are both not.

iii) the class of locally testable events with order is defined as the smallest class of languages containing the locally testable languages and closed under the boolean operations union, intersection and complementation. (this could be equivalently defined with locally testable in the strict sense instead of locally testable)

In what sense do they differ, that iii) contains more languages is clear, for example the language which contains for example $00$ followed by $01$ is in iii) but not in ii) or i) I think (because it involves some kind of order in requiring that $01$ need to follow $00$), but in what sense are ii) and i) different, what is a languge contained in ii) but no in i)?


texts:
Consider the following problems:

  Orthogonal Vectors Problem

  Input: A set $S$ of $n$ Boolean vectors each of length $d$.

  Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 = 0$?

  Non-Orthogonal Vectors Problem

  Input: A set $S$ of $n$ Boolean vectors each of length $d$ and a positive
  integer $k$.

  Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 \geq k$?

What is the relationship between these two problems?

In particular, here are a few more specific questions that I've been wondering about:

(1) Do either of these problems appear to be harder than the other?

(2) I'm not sure what the current state of the art algorithm is for OVP, but for either of these problems, can you get an upper bound better than $O(n^2 \cdot d)$ time?

(3) Does fixing $k$ make any difference for the second problem's complexity?

By $v_1 \cdot v_2$, I mean the inner product of $v_1$ and $v_2$ over $\mathbb{R^d}$.

  Edit: Most of the responses offer really great insights when $d$ is
  small.

  What can be said when $d$ is larger?  Say $d = n$ or $d = \sqrt{n}$
  or at least $d = n^\alpha$ for some $\alpha > 0$.


texts: Mergeable Exact Order Statistics Data Structure

texts:
Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that
$$
x < y, \text{ for } \forall x \in S_i \text{ and } \forall y \in S_{i+1}
$$
and let's denote this relationship as $S_i < S_{i+1}$.
For each set, we want to build a data structure that supports the following two operations:

$rank(x)$: Return the rank of $x$ in $S_i$, where $x \in S_i$;
$merge(A, B)$: Let $A$ and $B$ be the structures built on two sets $S_i$ and $S_j$ with $S_i < S_j$. Merge $A$ and $B$.

One implementation is to use an order statistics tree (such as AVL tree, red-black tree), which is able to support $\mathcal{O}(\log n)$ rank operation, but fails(right?) to provide efficient (i.e., logarithmic or constant) merge operation. A linked-list implementation, however, has poor rank performance. A skip-list may be employed, but its worst time complexity is bad.

Can anyone provide a reference about such a structure or proved lower bounds for a structure that supports these two operations at the same time? Any idea is appreciated. Thanks!


texts:
Given an array $A[1...n]$ of non-negative integers,
we want to transform $A$ into $A'$ such that

$|A[I] - A[I + 1]| \leq 1$ in the minimum number of operations.

One operation consist of picking two adjacent elements and perform:

1) Add 1 to $A[I]$ and subtract 1 from $A[I + 1]$

2) Subtract 1 from $A[I]$ and Add 1 to $A[I + 1]$

E.g.: 1 3 5 2
1 4 4 2 (picking 3,5)
2 3 4 2 (picking 1,4)
2 3 3 3 (picking 4,2)


texts: Online transitive closure better than O(N^2) per edge addition

texts:
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:

For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v }.

For O(N^2) edges this translates in a total time complexity of O(N^4) which much worse than, for example, Floyd-Warshall.


texts:
This is a generalization of my previous question.

Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be some string.

Consider the following Alice and Bob game. Initially, Alice and Bob have $m_A$ and $m_B$ dollars respectively. Alice wants $M^A(x)=1$ and Bob wants $M^A(x)=0$.

At every step of the game a player can add some string $y$ to $A$; this costs $f(y)$ dollar, where $f: \{0,1\}^* \to \mathbb{N}$ is a polynomial-time computable function. Also a player can miss his or her step.

The play ends if both players spends all money or if some player missed step when he or she in a losing position (that defines by the current value of $M^A(x)$).

Question: is the problem of defining the winner of this game for given
$M, f, x, m_A, m_B$ is an

EXPSPACE-complete task?

Note that $M$ can ask (for belonging to $A$) only strings of polynomial length so there is no  sense for Alice or Bob to add more longer strings to $A$. Hence, this problem is in EXPSPACE.

In my previous question adding of every string to $A$ costs one dollar (i.e. $f \equiv 1$). Then (as it was shown by Lance Fortnow) this game belongs to EXPH and even to PSPACE if $m_A = m_B$.


texts: What is the importance of linear languages?

texts: What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have been studied, or make them worthwhile to study?


texts: Bidirectional typing for dependent types: Why are Sigma, Pi synthesized?

texts:
According to the Pfenning philosphy of bidirectional typing, as also explained by Dunfield and Krishnaswamy 2013, constructors should be checked, while eliminators should be synthesized. Cconvention is followed for the most part in the tutorial Checking Dependent Types with Normalization by Evaluation: A Tutorial
by David Christiansen. I cannot explain some choices in the tutorial according to the Pfenning philosophy:
The types Sigma x A B and Pi x A B, Nat, Eq A from to, Trivial, and Absurd are all checked in synthesis mode. However, these are kind constructors, as they let us construct values that live in Univ. Why are they checked in synthesis mode?
Can we view these as eliminators of some object that I am unaware of? As an example of what I mean by this, recall that identifiers such as x are also run in synthesis mode. With a bit of squinting, one can convince themselves that identifiers are projections on the context Γ
, and thus deserve to be run in synthesis mode.
Is there a similar explanation for why Pi, Simga, Eq, Trivial, Absurd are typed in synthesis mode? what rule-of-thumb does one use to decide whether these should be typed  in checking or synthesis mode?


texts:
Is there any result on approximating a minimum (weighted) bipartite vertex cover? I'm interested in the problem that given a bipartite graph ( probably with weight on its vertex ), find a vertex cover of size (or weight) at most ($1+\epsilon$) of the optimal value. I've been searching on internet and although it seems the problem was quite simple, there's no paper or lecture notes about it. (maybe because everybody know :)).

Can anyone give a link to related work if you know any :D

thanks


texts:
Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing machine using an alphabet of size $3$ (say, $0,1,$ and blank)?

(From comments below by the OP)
Note the input is written using $0,1$, but the Turing machine using alphabet of size $k$ can overwrite the input symbols with symbols from the larger alphabet. I don't see how to encode symbols in the larger alphabet in the smaller alphabet without having to shift the input around which would cost time $n^2$.


texts: Language recongized by a "quasi realtime register machine"?

texts:
Counter machines are very powerful. Even two counters suffice for making these Turing complete.
But, in simulating a Turing machine the counter machine encodes in its integers a large amount of data. The encoding requires quite some time to process.

What if we restrict the counter machines to reasonably sized integers, and to a reasonable amount of time? Restricting the counter machine to increments and decrements limits the computation to unary representation, so allow addition and subtraction of registers. Restricting time is to a constant amount of work for each input letter, what is called quasi-realtime. Let quasi-realtime register machine (QRRM) be a machine that does a constant amount of work on each input letter and allowed additions and substractions of integer registers and may take action based on comparing these registers to zero.

More precisely a QRRM is similar to a pushdown automaton (PDA). Like a PDA, a QRRM has a finite set of internal states $Q$, an initial state $q_0\in Q$, and a set of accepting states $F\subseteq Q$.
A PDA uses a pushdown (stack) as auxiliary storage---A QRRM uses instead a finite number of integer registers. Like a PDA, a QRRM has two kinds of transitions:

Consuming transition, in which action is determined by the next input letter, which is consumed by this transition.
Eplsion transition ($\epsilon$-transition), in which action does not depend on the input, and no input letter is consumed.

Both kinds of transitions depend on the current state $q\in Q$ and on the value of the auxiliary storage. In a consuming transition, the dependency is also on the next input letter $\sigma\in\Sigma$. Quasi-realtime means that there is a constant that bounds from above the number of $\epsilon$-transitions that follow a consuming transition.

The dependency on auxiliary storage is by popping a symbol from a stack in a PDA. The dependency on auxiliary storage is by checking whether each of the registers is equal to zero.

In both kinds of transitions, the automaton may change its internal state from a state $q\in Q$ to a state $q'\in Q$ and update auxiliary storage. A QRRM updates it auxiliary storage by incrementing, decrementing, or clearing any of its registers. It is also allowed to change the value of some register $i$, by setting $r_i \leftarrow r_i + r_j$ or $r_i \leftarrow r_i- r_j$.

The question is with regard to the class of languages accepted by QRRM. It can clearly recognize languages such as expressions, and also context-sensitive languages such as $a^nb^nc^n$. Can a QRRM emulate a linear-bounded-automaton (LBA)? Any difference between the deterministic and the non-deterministic versions of the machine? How is this related to the result of Book and Greibach?

A related problem is that of a one-counter machine, which can recognize non CFL languages. Checking out the example in Patrick C.Fischer (66), we see that it can be done in quasi-realtime.


texts: polygonal triangulation and 3-colorability

texts:
Lets define polygonal triangulation a triangulation which has a hamiltonian cycle.

It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable.

Is any 3-colorable triangulation also polygonal triangulation?
In other words, is any 3-colorable maximal planar graph hamiltonian?


texts: Given a LL(2) grammar , how can i determine if it is strong ?


texts: Majority function stability under deletion and addition of entries

texts:
It is well known that the majority function is stable under random flipping of bits. That is, if $v$ is a random binary vector, and then we re-sample each bit of $v$ with probability $\delta$ and get $v^{'}$, then $\Pr[Maj(v) = Maj(v^{'})] = 1 - \frac{arccos(\delta)}{\pi}$

However, how will the majority function behave under addition or substruction of entries? Say we delete t random bits of v and add s random bits to get $v^{'}$. Is there any similar connection between $Maj(v)$ and $Maj(v^{'})$ in this scenario?

I conjecture that yes because the two cases are of course equivalent when s=t, however, I'm not sure how the connection behaves as a function of s,t, nor how to formally start to prove such connection.

Thanks!


texts: Can any computational challenge be transformed to proof-of-work?

texts:
The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO.
I wonder whether there exists an algorithm that can convert practically any computational challenge $\mathcal C$ (whose solution can be verified efficiently) into another such challenge $\Psi(\mathcal C)$ (which is used for proof-of-work) such that

The function $\Psi$ is randomized, using some (public) random sequence $r$.
Solving $\Psi(\mathcal C)$ is typically as hard as solving $\mathcal C$.
If a solution $x$ is found for $\Psi(\mathcal C)$, then a solution $\Psi^{-1}(x)$ can be efficiently computed for the original challenge $\mathcal C$.
Knowing a solution for $\mathcal C$ does not help in finding a solution for $\Psi(\mathcal C)$.

$\;\:\:$4' (Update). As pointed out by Noah in a comment, the previous condition should be strengthened to requiring that preprocessing $\mathcal C$ should also not give any advantage in solving $\Psi(\mathcal C)$.

This last condition is required so that no one can be put into an advantageous position just because they know a solution of $\mathcal C$.
Using this method, people could submit computational problems that they want solved and a central authority could pick some worthy of solving (like finding aliens vs. breaking passwords).
Note that it doesn't seem to be an issue if the problem takes even a week to solve (I guess those aliens can't be that good in hiding ;), as this could result in a bigger reward for a solution.
Anyways, these topics are not related to the solution of my theoretical problem, but of course I'm happy to discuss them in the comments/on the forum.

A possible solution would be the following: $\Psi$ maps $\mathcal C$ into $(\mathcal C,HASH_r)$, that is, to solving $\mathcal C$ and some other, computationally hard challenge.
One problem with this is that knowing a solution to $\mathcal C$ does make solving $\Psi(\mathcal C)$ somewhat easier (how much easier depends on the difficulty of $HASH_r$).
Another issue is that $\Psi(\mathcal C)$ became more difficult than $\mathcal C$.


texts: Many-one reduction from inequality problem to equality problem

texts:
Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is:

$$\mathbf{M}_{ineq} = \{(G,k): \exists V'\subset V, |V'|\geq k \wedge V'\in MIS(G)\},$$

where $MIS(G)$ collects all possible maximal independent sets of $G$.

Let the k-equality-MIS problem be the decision problem whether $G$ contains such a set exactly of size $k$. Its language being:

$$\mathbf{M}_{eq} = \{(G,k): \exists V'\subset V, |V'|=k \wedge V'\in MIS(G) \}$$

I'm wondering whether $\mathbf{M}_{eq}$ is many-one reducible to $\mathbf{M}_{ineq}$. My intuition tells me it should be but I cannot get it working. As I suspect similar problems pop up quite often, I figured someone here might know.

Note that this is not trivial as the corresponding independent sets problem, $\mathbf{I}$, where $(G,k)\in\mathbf{I}_{ineq}\Leftrightarrow (G,k)\in\mathbf{I}_{eq}$. As an example, for a graph, $G'$, that is a perfect matching with more than two vertices we have $(G',1)\in\mathbf{M}_{ineq}$ but $(G',1)\not\in\mathbf{M}_{eq}$.

And how about the other way around, is $\mathbf{M}_{ineq}$ many-one reducible to $\mathbf{M}_{eq}$?

I'm quite new to complexity theory, so I hope I get this right and the question is not obvious. Also sorry for the rather vague title, but my question is a bit vague. I hope my example made it clear. My question is, however, really about all problems with similar characteristics.


texts:
Reading Introduction to Modern Cryptography by Katz and Lindell, I noticed that they talk about CPA security for block ciphers (in Section 3.6.4 where they explain mods of operation) -- and mention that most modes of operation described there are CPA-secure. Then they prove that CTR mode is CPA-secure using the key length as security parameter: "${\tt Gen}(1^n)$ chooses a random function ..." and later, in the displayed equation,
$\left[ {\tt PrivK}^{cpa}_{{\cal A},\tilde\Pi}(n)=1 \right]\leq \frac{1}{2} + {\tt negl}(n)$".

However, in Chapter 5 (paragraph about "Attacks on block ciphers") they also mention that any pseudorandom permutation is secure againse CPA attacks, and that it makes no sense to use asymptotic notions of security for block ciphers, since their block and key length are fixed (and that makes perfect sense to me).

So I am confused now -- what is the point of the previous demonstrarion, on Chapter 3, that CTR mode is CPA-secure?

Or, making this question not specific to this book in particular: how do people define security against CPA (and known-plaintext, CCA etc) for block ciphers?


texts:
Are there any ways of getting to know about new PhD positions in TCS other then just looking trough ubniversity/research groups web sites?

Maybe people from different branches (type theory, verification, complexity, etc.) can name some specialized mailing-lists where PhD positions announcements are quite usual.

PS In my university we haven't got huge TCS research and we always have smart students “at hand” which are good candidates for sending for PhD positions, but in order to make this process more effective it would be nice to have some sources of new positions opening.


texts: An analog of DP for the second level of the polynomial hierarchy

texts:
The complexity class DP can be defined as the set of all languages that are the intersection of an NP language with a coNP language.

I have a language for which I wish to determine the exact complexity class. I know that the language is:

It is $\Sigma_2^P$-hard
It is $\Pi_2^P$-hard
It can be represented as the intersection of a $\Sigma_2^P$ and a $\Pi_2^P$ languages.

Here $\Sigma_2^P$ and $\Pi_2^P$ are the second-level classes in the polynomial hierarchy.

It seems that what I know about my language indicates that it is complete in a complexity class which is analogous to DP, but where DP corresponds to the first level of PH, my class corresponds to the second level.

My questions:

Am I correct in deducing the completeness of my language? It seems plausible but I can't find a proof.
What is the usual name of "my" complexity class? Where has it been studied so far? Is it interesting? Are there known (non-artificial) complete problems for it?

Thanks.


texts:
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input.

Is there a way to compute $Per(M)$ faster than $O(n2^n)$ in this case? Note if $B=2^{o(n)}$ there is a faster way. So I am interested in $B=2^{\Omega(n)}$ case.

Given any $\alpha\in(0,1)$ is there an efficient algorithm to compute $Per(M)$ approximately to any non-trivial (say $2^{o(n^\alpha)}$) factor when $B=2^{\omega(n^\alpha)}$ holds that runs in $2^{o(n^\alpha)}$ time?


texts:
First of all, I am not sure whether this is a research level question. Please let me know if it is not.

The question is about streaming algorithms for the sum of the given data stream. From literature, it is common to consider the questions related to the frequency vector, say, $\vec{m}$, and one has standard algorithms to approximate the p-norm of such a vector. However, a very natural question is, is it possible to approximate the sum of the stream. More formally, suppose we have a frequency vector $\vec{m}$ for the "value vector" $\vec{a}$, i.e., each $a_i$ appears $m_i$ times in the stream, the sum  is
$\sum a_i\cdot m_i$. (Of course, we assume each $a_i$ is within some interval $I$, as otherwise the question might not be very interesting.)

I noticed that Braverman has papers regarding approximate $\sum_i G(m_i)$ for reasonably general function $G$, but here, with different index $i$, $G$ varies. Hence it is not clear to me how to apply.


texts: On the optimal solution of the CKR formulation for MULTIWAY CUT

texts:
Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1].  Let $U_i$ be those vertices in $V-T$ which is assigned $e_i = \{0, \dots, 1, \dots, 0\}$, that is, $1$ at the $i$-th coordinate and $0$ at all others.  My question is: is there always an optimal solution that keeps vertices $U_i$ with $t_i$ (the $i$-th terminal)?

Remark. For the multicommodity-flow-based linear program for the MULTIWAY CUT problem (see [2]), it is not hard to show the existence of an optimal solution.  It should be verified with the similar idea as [3], which proves the existence of such an optimal solution on the NODE MULTIWAY CUT problem.

Calinescu, G., H. Karloff, Y. Rabani. 2000. An improved approximation algorithm for Multiway Cut. J. Comput. System Sci. 60(3) 564–574.
E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiterminal cuts, SIAM J. Comput. 23 (1994), 864894. [Preliminary version appeared in STOC '92]
Sylvain Guillemot, FPT algorithms for path-transversal and cycle-transversal problems, Discrete Optimization 8 (2011) 61–71

P.S. I'm aware of Karger's result, but that is irrelevant.