texts:
Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the same proofs also goes through for $\mathrm{Perm}_n$ as well. To add to this, quite a few papers in arithmetic circuit complexity state in passing that the lower bounds is for $\mathrm{Det}_n$ and $\mathrm{Perm}_n$.

As far as I can see, the proof technique of Grigoriev and Karpinski when applied to the $\mathrm{Perm}_n$ fails at a subtle technical point. Their proof (for $\mathrm{Det}_n$) uses the following fact:

  If $X$ is a matrix of indeterminates, and $A$ is an arbitrary matrix,
  then any minor of $AX$ is a linear combination of minors of $X$.

This is not true for the permanent though. For this technical reason, the proof doesn't quite seem to go through. Perhaps there is a simple fix for this that I am missing? Or is this is a really a subtle misconception of a fair number of people?

PS: I noticed this only while making a consolidated exposition of all known lower bound proofs for myself. The exact place where Grigoriev-Karpinski fails for the $\mathrm{Perm}_n$ is in Lemma 12 of page 7 in the above write-up, or the $T_g$ operator in the original paper.


texts: Graph theoretic restriction to Proofs in Proof Complexity Theory

texts:
Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of given input formula.
A graph is one of formal model of proofs.  My question is about further restriction to this model.
A proof is represented as a DAG. Nodes with fan-in 0 have axiom-labels. The unique node with fan-out 0 corresponds to "false." For given input rules of deduction, each node which has both in-degree and out-degree has the  label representing proposition.
My question is:

Are there proof systems and related researches in the case that the class of proof-DAGs are restricted?
Papers, survey, and lecture note are welcome.
Do Proof Systems which are previously studied such as Nullstellensatz, Resolution, LS, AC0 Frege, RES(k), Polynomial Caluculus, and Cutting Planes, have some graph theoretic characterization??


texts: "right" uniformity condition for Nick's Class

texts:
DLOGTIME is defined at http://en.wikipedia.org/wiki/DLOGTIME

$\operatorname{L}$ is defined at http://en.wikipedia.org/wiki/L_%28complexity%29

$\operatorname{NC}$ and $\operatorname{NC}^n$ are defined at http://en.wikipedia.org/wiki/NC_%28complexity%29

DLOGTIME seems to be the smallest that might work.

I've read in various places that $\, \operatorname{L} \subseteq \operatorname{NC}^2 \,$, $\,$ although every place I've

found that results which states a uniformity condition uses $\operatorname{L}$-uniformity.

Is there any deterministic class $X$ such that $\, \operatorname{L} \subseteq \operatorname{NC} \,$ is known with $X$-uniform $\operatorname{NC}$, and

1. $\;$ ... $\; X\subset \operatorname{L} \;$ is known to hold?

2. $\;$ ... $\; X\subseteq \operatorname{L} \;$ is known to hold and $\, X = \operatorname{L} \,$ is not known to hold?

(1, or to a much lesser extent 2, would seem to imply that $\operatorname{L}$-uniformity is the correct condition)


texts: Which is the limit of lossless compression data? (if there exists such a limit)

texts:
Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression.

So far, the only source I could find on this topic was the Wikipedia:

  Lossless compression of digitized data
  such as video, digitized film, and
  audio preserves all the information,
  but can rarely do much better than 1:2
  compression because of the intrinsic
  entropy of the data.

Unfortunately, Wikipedia's article doesn't contain a reference or citation to support this claim. I'm not a data-compression expert, so I'd appreciate any information you can provide on this subject, or if you could point me to a more reliable source than Wikipedia.


texts:
Given a graph $G$, and a vertex-induced subgraph $H$ of $G$, there are two superficially-similar definitions ways to define the density of $H$:

(1) Average degree of vertices in $H$

(2) What I will refer to as the "edge density" of $H$, defined as $\frac{ E(H) }{ \binom{V(H)}{2}}$.

I'm interested in understanding the complexity of finding dense subgraphs, subject to constraints on the number of nodes, using the second definition of density. Unfortunately, most of the relevant work I can find, most notably on variants of the $k$-densest subgraph problem, uses the first definition. I'm looking for pointers to work on the second definition. First, I will elaborate on the similarities and differences between the two definitions before asking two specific questions.

If one is interested in finding the  densest subgraph with a given number of nodes $k$, it doesn't matter which definition you use. The two definitions coincide when comparing subgraphs with the same number of nodes. The result is the NP-hard $k$-densest subgraph problem, which is well studied, but who's complexity of approximation remains poorly understood. However,when looking for the "densest at-most-k subgraph"  or "densest at-least-k" subgraph, the two definitions of density appear importantly different.

Densest at-most-k subgraph: Using the average-degree definition, this problem is NP-hard, and its approximability is essentially equivalent to that of the classic "k-densest subgraph" problem [Anderson and Chellapilla '09]. Using the edge density definition, however, this problem is trivial: any two nodes connected by an edge are an optimal choice of $H$.

Densest at-least-k subgraph: Using the average-degree definition, this problem has been studied before, and admits a constant factor approximation [Anderson and Chellapilla '09]. However, using the edge density definition, I can't seem to find any related work.

This get more dicey when one considers both upper and lower bounds on $k$, the number of nodes in the sought induced subgraph.

My questions:

(a) Can anyone point me to work on approximation algorithms for densest at-least-k subgraph using the edge-density definition of density?

(b) What is the proper name of what I'm calling "edge density"? Why does this definition appear more esoteric, as far as the approximation algorithms community is concerned, than the average degree definition? (Or is it?)


texts: Time complexity of Held-Karp algorithm for TSP

texts:
When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, I came up with the following question:
why the complexity of their algorithm for TSP is $(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$ (p. 199), I mean where do they take the factor $k$? If I understood correctly $k-1$ means the number of additions for each subset of cities. Then why each addition operation is coupled with unknown to me $k$ operations? I suppose it is connected somehow to taking minimum, but computing minimum doesn't seem to require such many operations.

Dynamic programming algorithm by Held and Karp and independently Bellman runs as follows:
for each pair $(S,c_i)$, meaning a path going through $c_1$, all the elements of $S$ and terminating at $c_i$ compute

$OPT[S,c_i]=min\{OPT[S\setminus\{c_i\},c_j]+d(c_j,c_i):c_j\in S\setminus\{c_i\}\},$

where $d(c_j,c_i)$ means the distance between cities $c_j$ and $c_i$. Then in the formula from the paper $k$ means the size of $S$.


texts:
Is there any abstract definition for 'shapes' of a cluster?

I am currently working on providing for a set of axioms to study clustering. In my work, I have found a need for an abstract definition for 'shape'. I wish to know if indeed there is such a definition.

I have searched for the existence of said definition and have found this:

I wish to know if there are other definitions.


texts: How to solve an unification problem on $\mathbb{N}$?

texts:
Usually, the unification problem for two given terms $t$ and $s$ is to find a substitution $\theta$ such that $\theta t = \theta s$,
which is equal to finding the certain $\langle x_1 , \cdots , x_n \rangle$ such that $t = s$ holds.
But in the $\lambda$Prolog programming language, by the existence of the logical operator $\mathtt{pi}$ whose semantics resembles $\forall$, an unification problem is of the form
$$ \mathcal{Q}_1 x_1 \cdots \mathcal{Q}_n x_n \left[ t_1 = s_1 \land \cdots \land t_m = s_m \right] , $$
where $\mathcal{Q}_i$ is an universal or existential quantifier.
See Miller's paper for more details.
I made my own $\lambda$Prolog interpreter without the operator of $+$ and $\times$, in which the currently implemented are numerals and successor.
Now, what I want to do is to add both $+$ and $\times$ with their arithmetic semantics, i.e., I want to solve the decision problem:
$$ \mathbb{N} \models \mathcal{Q}_1 x_1 \cdots \mathcal{Q}_n x_n \left[ t_1 = s_1 \land \cdots \land t_m = s_m \right] , $$
where $\mathcal{Q}_i$ is a quantifier, $x_i$ is a variable, $t_j$ and $s_j$ are terms; and terms are $\lambda$-terms extended with the constants $0$, $S$, $+$ and $\times$.


texts: Prefix Dictionary Problem in External Memory

texts:
I'm interested in an external memory data structure able to support the following operations on variable length binary sequences: (1) Insert such a sequence. (2) Given a query sequence, find the longest sequence previously inserted which is a prefix of the query sequence, provided one exists.

In particular, do we need $O(n)$ I/O's for an operation with a sequence of length $n$? (Say, by directly implementing a radix tree in external memory.) Or is there something nice, where we can get $O(n/B)$ I/O's?


texts: What is the meaning Partitioned Signatures?

texts:
Context: Boneh & Boyen devised a transformation for these class of signatures which increases the security to stronger notion of unforgeability.

It would be nice if it is an example. Thanks!

Reference Paper:  Strongly Unforgeable Signature based on CDH assumption


texts: Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?

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

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

More details about this construction are on Mathoverlfow


texts: Chromatic number of planar graph with girth at least k

texts:
The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones.

Girth is the length of the smallest cycle in a graph. Planar graph with girth at least 4, i.e., triangle-free, is 3-colorable, shown in paper.

Question:
Is it NP-Complete to find a 3-coloring of a planar graph with girth at least $k$, where $k$ is a fixed integer?  Is there any result about this topic?

I find another post "graph families which have polynomial algorithms for chromatic number" might be related.


texts: Representing bound variables with a function from uses to binders

texts:
The problem of representing bound variables in syntax, and in particular that of capture-avoiding substitution, is well-known and has a number of solutions: named variables with alpha-equivalence, de Bruijn indices, locally namelessness, nominal sets, etc.

But there seems to be another fairly obvious approach, which I have nevertheless not seen used anywhere.  Namely, in the basic syntax we have only one "variable" term, written say $\bullet$, and then separately we give a function that maps each variable to a binder in whose scope it lies.  So a $\lambda$-term like

$$ \lambda x. (\lambda y. x y)$$

would be written $\lambda. (\lambda. \bullet\bullet)$, and the function would map the first $\bullet$ to the first $\lambda$ and the second $\bullet$ to the second $\lambda$.  So it's kind of like de Bruijn indices, only instead of having to "count $\lambda$s" as you back out of the term to find the corresponding binder, you just evaluate a function.  (If representing this as a data structure in an implementation, I would think of equipping each variable-term object with a simple pointer/reference to the corresponding binder-term object.)

Obviously this is not sensible for writing syntax on a page for humans to read, but then neither are de Bruijn indices.  It seems to me that it makes perfect sense mathematically, and in particular it makes capture-avoiding substitution very easy: just drop in the term you are substituting and take the union of the binding functions.  It's true that it doesn't have a notion of "free variable", but then (again) neither do de Bruijn indices really; in either case a term containing free variables is represented a term with a list of "context" binders in front.

Am I missing something and there is some reason this representation doesn't work?  Are there problems that make it so much worse than the others that it's not worth considering?  (The only problem I can think of right now is that the set of terms (together with their binding functions) is not inductively defined, but that doesn't seem insurmountable.)  Or are there actually places where it has been used?


texts: Information Theory used to prove neat combinatorial statements?

texts:
What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?

Some examples I can think of are related to lower bounds for locally decodable codes, e.g., in this paper: suppose that for a bunch of binary strings $x_1,...,x_m$ of length $n$ it holds that for every $i$, for $k_i$ different pairs {$j_1,j_2$}, $$e_i = x_{j_1} \oplus x_{j_2}.$$ Then m is at least exponential in n, where the exponent depends linearly on the average ratio of $k_i/m$.

Another (related) example is some isoperimetric inequalities on the Boolean cube (feel free to elaborate on this in your answers).

Do you have more nice examples? Preferably, short and easy to explain.


texts:
I have just started (independent) learning about quantum computation in general from Nielsen-Chuang book.

I wanted to ask if anyone could try finding time to help me with whats going on with the measurement postulate of quantum mechanics. I mean, I am not trying to question the postulate; its just that I do not get how the value of the state  of the system after measurement comes out to $M_m/\sqrt{ <\psi|M_m^+ M_m|\psi> }$.

Even though its just what the postulate seems to say, I find it really awkward that why is it this expression. I do not know if what I ask here makes sense, but this is proving to be something which for some reason seems to block me from reading any further,


texts: Security of message authentication codes and tag size

texts:
The obvious way to attack a MAC is to try every key; therefore, if we use an n-bit key we need $2^n$ steps to break it.

But we can also try every tag in order to find the correct one, and in some concrete scenarios (e.g. CBC-MAC with AES-256) the tag is smaller than the key.

Does this mean that a MAC with n-bit keys and t-bit tags will offer $\min(n,t)$ bits of security, or is there something wrong with this reasoning?


texts: Sublinear finite-precision sampling in a stream

texts:
I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem.

On a stream of length $n$, I would like to make $o(n)$ calls to my random number generator (henceforth "RNG"). Additionally, I would like to work in finite precision. Is there a data structure that supports this?

As usual with reservoir sampling, I want to preserve that:

Each item is selected with equal probability
The total time used is $O(n)$ with high probability. A Las Vegas algorithm would be just fine
No more than $O(1)$ machine words and $O(1)$ stream items are stored between stream items arriving
Only one pass is made over the stream

Results that I know about that do not meet my requirements include:

The standard reservoir sampling data structure makes $\Omega(n)$ calls to the RNG.
"Random sampling with a reservoir" by Jeffrey S. Vitter and "Reservoir-sampling algorithms of time complexity $O(n(1 + \log(N/n)))$" by Kim-Hung Li need only $o(n)$ calls to the RNG but use arbitrary precision arithmetic.
"Sampling in Space Restricted Settings" by Bhattacharya et al. describes a data structure that meets the above criteria but can fail to sample an item with non-zero probability.
Exact minwise hashing (in which each index in the stream is hashed and the reservoir holds the item at the index with the lowest hash value seen so far) would suffice, but exact minwise hashing families have size at least $e^{n - o(n)}$ according to Theorem 1 of "Min-Wise Independent Permutations" by Broder et al.. Storing a member of the family would require using at least $(\lg e)(n - o(n))$ bits of space between the arrival of stream items.


texts: Has a proof checker bug ever invalidated a major proof?

texts:
Most (all?) proof assistants have soundness bugs fixed on occasion.  However, from those I've seen these bugs are usually difficult to come across unintentionally, and results proved before the bug is fixed generally hold up after the fix.

Three questions, in order of strength:

Has such a soundness bug fix ever caused a major proof to fail, without modifying the proof?
If (1) is true, were major modifications ever required to fix the proof?
If (2) is true, has anyone proved a wrong major theorem due to a soundness bug?

I'll leave the definition of "major" up to others.


texts: Constructing integer sets in which a certain equation has no solution

texts:
Given some linear equation, e.g., $$x+2y=3z+4u+5w,$$ I would like to construct a set $S$ of $n$ positive integers so that equation has no solution in $S$.

Two questions:

1) How big must the integers in $S$ be? That is, how large is $\max_{a \in S} a$? Can $S$ be chosen in such a way that this latter quantity is  $O(n \log^k n)$ for some $k$?

2) How long does it take to construct (either deterministically or with randomization) a set $S$ of $n$ positive integers where a fixed linear equation has no solution, and such that the largest number $\max_{a \in S} a$ has (approximately) minimal size?


texts:
We can consider a datalog program as a set of clauses. Some of them allow to derive others. For instance from:

A(x) :- B(x), C(x).
B(x) :- D(x).
C(x) :- D(x).

We can derive:

A(x) :- D(x).

Given a datalog program, a minimal equivalent datalog program is a subset of the given program with the smallest number of clauses that allows to derive the full datalog program. Minimal equivalent datalog program is not unique at least in the presence of cycles. Finding any of them is enough; I don't need to find them all.

The clauses contain no disjunctions, only an implication and an atom in the head. Alternate definition: clauses are composed by disjunctions (no conjunctions) and there is only one non-negated predicate. All predicates are unary or binary, and contain variables or constants. There may be recursion, and it may be limited to unary predicates.

I'm searching for an algorithm that allows to find this minimal datalog program for a given program, but I could not find it. It may just be a matter of not using the correct terms, or maybe my confusion is deeper. In any case this seems a fundamental problem when working with datalog and my guess is that it was solved decades ago.

Do you know any algorithm for this? Should I use a different terminology?

Thank you.

PD: a more enticing example that allows greater optimization:

A(x):- I(x).        B(x):- P(x,y).      P(x,y):- T(x,y).
A(x):- C(x).        G(x):- L(x).        P(x,z):- T(y,x).
A(x):- R(x,y).      H(x):- P(x,y).      P(x,z):- U(y,x).
A(x):- R(y,x).      H(x):- T(x,y).      P(y,x):- T(x,y).
D(x):- A(x).        I(x):- J(x).        P(z,x):- R(y,x).
D(x):- T(y,x).      I(x):- T(x,y).      R(x,y):- T(x,y).
E(x):- I(x).        C(x):- K(x).        R(y,x):- T(x,y).
E(x):- R(x,y).      C(x):- R(x,y).      S(x,z):- T(x,y).
F(x):- A(x).        C(x):- T(y,x).      S(x,z):- R(x,y).
F(x):- H(x).        C(x):- U(x,y).      S(y,x):- T(x,y).
F(x):- R(y,x).      J(x):- K(x).        S(y,x):- U(x,y).
B(x):- D(x).        J(x):- R(x,y).      T(y,x):- U(x,y).
B(x):- C(x).        K(x):- U(x,y).      U(x,z):- R(x,y).
B(x):- J(x).        L(x):- R(y,x).      U(x,z):- P(x,y).
B(x):- L(x).

I was calculating the result manually, but I think I can do it with an algorithm, it's going to take a while.

PD: I found this: A. Pettorossi and M. Proietti, “Transformation of logic programs: Foundations and techniques,” The Journal of Logic Programming, vol. 19–20, Supplement 1, pp. 261–320, May 1994.


texts: Power of randomness vs. power of indefinite computation

texts:
I am writing a paragraph on the power of randomness, part of which I am trying to ground in theory of computation (I am no expert/researcher in this field).

First off, I am aware that for traditional complexity classes such as ZPP and BPP, it is open question whether they equal P. In context of this question, I am interested in a particular subset of ZPP.

Let ZPP be the set of decision problems for which there exists a Probabilistic Turing Machine (PTM) which solves it in a time that is polynomial in expectation.

Note that this definition allows indefinite computation (albeit with an infinitesimal likelihood). In fact, most membership proofs by example (I am aware of) use PTMs which exploit this fact.

Let bounded-ZPP (my own term) be the subclass of ZPP which (in addition) requires a PTM to have a bounded execution, i.e. it to halt after a finite (possibly super-polynomial) # steps.

I was wondering about the following:

Is there a more conventional name for bounded-ZPP?
Is bounded-ZPP = ZPP?
Is P = bounded-ZPP?
If (3) holds, wouldn't this suggest that a hypothetical P $\subset$ ZPP, would be more correctly attributed to allowing indefinite execution in ZPP, rather than the "power of random choice"?


texts: On the faces of the multicommodity flow polytope

texts:
Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows $(R_1,R_2,...,R_k)$ forms a polytope. We know that for $k=1$ (Ford-Fulkerson theorem) and $k=2$ (T.C. Hu's theorem), the cutset outer bound on the flow region is tight, so the polytope is completely specified by the cutset bound inequalities.

We also know that for $k=3$, the cutset outer bound is not tight in general. I am interested in what is known about the faces of this polytope for $k=3$.

Is there a universal bound on the number of faces of the polytope (for all graphs where $k=3$)? Or is it the case that given any $N>0$, one can construct a graph with 3 source-destination pairs whose flow polytope has more than $N$ faces?
Is it possible to express the equations for the new faces, namely the faces that don't correspond to the cutset bound, in terms of some combinatorial quantities associated with the graph?

Thanks.


texts:
Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know).

The general notion of algorithm is model of computation with finite number of steps which my be performed on device from "set of computational devices". Up to now "Set of Computational devices" consists of quantum and classical computers which both may be simulated on Universal Turing Machine. It means that Turing machine remains the most general model for computations ( which is in harmony with other notions of effective computable functions like lambda-calculus or recursive functions).

So let me explain motivation to as question at the end:

Turing Machine is in some way connected with notion of time (it is idealisation of computation by performing "one operation" at a time). As we discover new interesting phenomena ( famous discovery: http://arxiv.org/abs/1101.2565 mentioned also here http://www.technologyreview.com/blog/arxiv/26270/ ) probably it is time to ask what is the role of time in Turing Computation model and if it has rigorous enough definition.

Let's imagine a simple Gedankenexperiment: Imagine a class of TM for which initial Data and Result has to be at least 4 ( in general n - natural number) cells one after other - it looks like artificial idea, but when we refer to separation in time - it sound very natural. We use "separation in time" as very natural notion: in fact we require it - answer has to be obtained after question - right?. So, in a light of existence of phenomenon like time-entanglement - mentioned in references above - it is probably time for review... It is not clear for me if this phenomenon point on something new but it may...

Of course "notion of time" is not so important here at all, probably the notion of order is sufficient enough ( although I do not know how such change would result in quantum computations where time is important parameter I suppose, but we may say - in mathematical idelisation/model probably it may be not important).

The questions:

(1) Order dependency of TM - is it new idea?

(2) Is it interesting?

(3) Even for finite sets we still may use abstract concept of lattice to model order of algorithm steps. Is it useful for example for parallel computation model?

(4) It looks like Universal Turing Machine definition use strict order of algorithm steps. Why? If ten we change notion of time order in UTM to notion of abstract order, will that change notion of algorithm/Turing Machine definition? Was that analysed by someone?

(5) When we go to hypercomputational models: may we use continuous index as "time order" replacement? Are there any important consequences of such change?

(6) Was there any influence of time-entitlement on our computational model discussed?


texts: Is it possible to make trapdoor board games?

texts:
Motivated partly by this MO question, I am wondering if it's possible to design a board game where there is a simple winning strategy but it's hard to find. For example, the game of picking a random number, applying your public crypto key to it and asking what the original number was, would be a trapdoor game, but I am looking for something more like a board game. For example, chess with different rules about how the pieces can move, or some Nim like game.

To make the question more clear - what I am looking for is a simple recipe using which I can generate myself a board game in which I can beat everyone and playing many times won't reveal my strategy. (Yes, I've recently been beaten too many times by my wife in memory...)


texts: "finally" for algebraic effects and handlers

texts: In Java in addition to catch there is also finally, this is very important to make sure resources get cleaned up. I believe dynamic-wind for call-cc is similar to this. According to this dynamic-wind can be written using delimited continuations. Because algebraic effects can can express delimited continuations, does that mean that we can write a finally like construct using algebraic effects and handlers, that allows us to safely handle resources?


texts: Which formal language class are XML and JSON with unique keys?

texts:
I moved this question from stackoverflow where id got no answers. We had a similar question whether JSON is regular:

JSON and XML are both frequently called to be context-free languages - they are both specified mainly by a formal grammar in EBNF. However this is only true for JSON as defined in RFC 4329, section 2.2 which does not require uniqueness of object keys (many may not know but {"a":1,"a":2} is valid JSON!). But if you require unique keys in JSON or unique attribute names in XML this cannot be expressed by a context-free grammars. But which is the language class of JSON with unique keys and for well-formed XML (which implies unique attribute names?).

One of the best paper I found on this subject (Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory) explicitly excludes integrity constraints such as keys/keyrefs and uniqueness to be checked on an additional layer. Beside this the subset of XML defined by an XML Schema or by a DTD is context-free. But not the full set of all well-formed XML documents.

I think a nested stack automaton (=indexed language) should be able to parse JSON with unique key constraint. For XML can simlify the question to the language S of all comma-separated lists of unique integers. Does anyone know more, preferably with citations?

P.S: A simple algorithm to decide the languages (beside the context-free part) is based on a good sorting algorithm. Therefore it should be decidable in "linearithmic time" with O(n log n) worst case. I have not found out yet, whether the complexity class is for instance "mildly context-sensitive", or "indexed" but probably something between context-free and context-sensitive (?).

EDIT: Maybe I better reformulate the question for the more theoretical computer scientists. Given the class CFL of all languages that can be expressed by Backus-Naur-Form with repetition (x := a+ $\Leftrightarrow$ x := a | x a). Now what do I gain in computational power if I introduce a "repetition with unique instances" operator ^, so a^ is a sequence of a where each element results in a different sequence of terminals?


texts: Matrix multiplication algorithms for research

texts:
I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for matrix multiplication.

I am extremely curious to know what kind of algorithms my peers use?
The following are the possible choices:

Naive $O(n^3)$
Strassens Algorithm $O(n^{2.807})$
Coppersmith Winograd Algorithm $O(n^{2.375})$

Obviously (3) is quite complicated and may take quite a few tries to get right. Is it worth the effort ? I must mention here that speed is paramount for my usage as I will have a number of multiplication calls.


texts:
Martin-Löf type theory uses W-types to define inductive structures like integers, lists, etc. However, calculus of inductive constructions doesn't use them in the same way, inductive types there seems to be more like axiom schemas.

Are these two approaches equivalent (they seem to be)? Are there any philosophical reasons why one is better than the other (for me, W-types feel like more intuitive, because the are just trees of special structure)? Which is easier from implementation point of view (inductive types seems to be better for me, since for W-types to be useful we need at least finite types and products to be available in a system's core)


texts: The Drawing Challenge - a problem I made up and can't solve!

texts:
I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be $\sf{NP}$-Complete.

I created a programming challenge type description to encourage my CS friends to have a go at it.

Charlie likes to draw.

He’s given a piece of paper of width $W$ and height $H$ and a list of $N$ numbers $a_1, a_2, a_3, ... a_N$

For each number, he wants to draw a rectangle on the piece of paper. If the rectangle has width $w$ and height $h$ then  $w > 0, h > 0, w \geq h$ and $w \leq W$ and $h \leq H$. Both w and h must be positive integers.

If a number $a_x > a_y$, then $a_x$’s rectangle must have area bigger or equal to $a_y$’s rectangle, where area is $w*h$. If $a_x = a_y$, then they can have different areas.

Charlie doesn’t like to waste ink. For a rectangle of width $w$ and height $h$, he must draw a line of length $2w + 2h$, using $2w + 2h$ units of ink. Clarification: even if two rectangles are adjacent, the adjacent side must be drawn twice.

What is the least units of ink that Charlie can use, drawing one rectangle for each number on the piece of paper, such that no rectangles overlap and the whole paper is covered by rectangles?

Input File:
Line 1       : The width W and height H of the piece of paper, separated by spaces
Line 2       : N, the number of numbers to draw
Lines 3..N+2 : One number on each line.

Constraints:
W and H are positive integers <= 1000
N is a positive integer <= W * H
ax, where 1  <= x <= N, is a positive integer <= 1000

Output file:
A single line containing the least units of ink Charlie can use.

Bonus:

Output, for each number ax, the position and size of its rectangle on the piece of paper for a solution that uses the least amount of ink (there can be more than one).

Sample input file:

2 2
4
1
1
1
1

Sample output file:

16

Sample bonus:

-----
| | |
-----
| | |
-----

As pointed out by Marzio, here's the decision problem version:

Given a $W × H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn, filling the entire paper, as described above?


texts: "A simple linear time algorithm" by Klawe

texts:
I try to implement the algorithm described in "A simple linear time algorithm for concave one-dimensional dynamic programming" by Maria M. Klawe, 1989.

However, right at the beginning there is possibly a typo:

i ← 0; r ← 0;
While i < 2^⎡log(n + 1)⎤ and r < i do;
    If i = 2^⎡log i⎤ - 1 then do;
...

because of the "r < i" the while loop immediately terminates. Also, the "if" condition should be taken right in the first loop (from what I understood).

Please, does anyone know if there is a typo indeed and eventually what should the initialization look like?

Edit

I hope it's ok if I post here the whole algorithm. I honestly don't know what the practice on posting such things online is - if it's not ok, I apologize and I (or the moderator) will delete it.

i ← 0; r ← 0;
While i < 2^⎡log(n + 1)⎤ and r < i do;
    If i = 2^⎡log i⎤ - 1 then do;
        SMAWK M(0 : i, i + 1 : min(2(i + 1) - 1, n));
        * a square has been treated *
        i ← i + 1;
        end;
    else if M(r, 2^(⎣log(i + 1)⎦ + 1) - 1) < M(i, 2^(⎣log(i + 1)⎦ + 1) - 1)
        then i ← i + 1;
        * a slice has been treated *
        else r ← r + 1;
        * the region M(r, 2^(⎣log(i + 1)⎦ + 1) - 1 : n) has been treated *
end;
* The algorithm has now treated rows 0, ..., i - 1. *

It works like this: there is a triangular matrix, which the algorithm extracts larger and larger squares from (that's the first branch). The algorithm then breaks the remaining lines under the square into "slices".

PS: The initialization is just one problem. The another is that for some input the second branch M(r, ...) < M(i, ...) starts to increase only r which causes the while loop to exit prematurely because of r < i


texts: Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?

texts:
There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an optimum value. And another theory, that of differential approximation where the approximation ratio is $\inf\frac{\Omega-A}{\Omega-OPT}$, $\Omega$ - the worst value of a feasible solution for the given instance. The authors of this theory claim that it has some definite advantages over classical one. For example:

it gives the same approximation ratio for such problems as Minimum vertex cover and Maximum independent set which are known to be just different realizations of the same problem;
it gives the same ratio for max and min versions of the same problem. At the same time we know in standard theory MIN TSP and MAX TSP have very different ratios.
It measures distance not only to the optimum but also to the pessimum $\Omega$. So in the case of Vertex Cover standard approximation theory says that $2$ is the best upper bound. But essentialy $2$ is the maximum ratio between the pessimum and the optimum. Thus such algorithm is guaranteed to output the solution with the worst value.

My argument pro is: in asymptotic analysis we don't take into consideration constants and low-order terms (here I recalled the quote by Avi Widgerson: "We are successful because we use the right level of abstraction.") and this is the level of abstraction for comparing algorithm's usage of resources. But when we study approximation we by some reason introduce the difference in those places where we can avoid it.

My question is

  why the differential approximation theory so poorly studied. Or the arguments involved are not strong enough?


texts: For which families of graphs is Generalized Geography in $P$?

texts:
As @Marzio mentioned, the following game is known as Generalized Geography.

Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows:

At each turn (two players alternating), a player chooses $u\in N(v)$, and then the following happens:

$v$, as well as all of its edges, is removed from $G$.
$u\to v$ (i.e. $v$ is updated to be the vertex $u$).

The player who is forced to select a "dead end" (i.e. a vertex with no outgoing edges) loses.

In which graph families is the optimal strategy computable in polynomial time?

For example, it's easy to see that if $G$ is a DAG, then we can easily compute the optimal strategy for the players.


texts: "long code test" and "dictatorship test"

texts:
Why is "long code test" also called "dictatorship test"?

I got really confused when I read about it in Arora's survey.


texts: Complexity of linearized Ising model at 0

texts:
Suppose $Z_G(J,h)$ is a partition function of Ising model with coupling $J$ and magnetic field $h$ on graph $G$. What is the complexity of finding the gradient of Z at $\mathbf{0}$?

Specifically, if $n$ is the number of vertices, $E$ is a set of edges, $\mathcal{X}=\{1,-1\}^n$, the gradient is of the following function
$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$$


texts: It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with high probability rather than just in expectation?


texts:
To celebrate Alan Turing 100th birthday, I want to watch a documentary about his life.  However, there are several documentaries to choose from.
Which documentary about Alan Turing is your favorite?
Please include only one documentary per answer.


texts: What are the historical roots of Milner's bigraphs?

texts:
Robin Milner defined bigraphs as a type of graphical structure with graph-like structure but where the nodes can be nested.  They generalise process calculi like CCS and the $\pi$-calculus, but Milner seems to have intended for them to be used much more generally: the seminar notes from shortly before his death detail recent developments.

Looking back instead of forward, the prologue of Milner's 2009 textbook The Space and Motion of Communicating Agents, does not provide much of a historical background.  Milner explicitly acknowledged its roots in Mobile Ambients and the Pi calculus.  Yet the model is so general that there are bound to be strong links to older models.

  Are there historical predecessors of bigraphs?

Focusing on the syntactic elements rather than the way they are used to capture evolving systems, an obvious precedent is A. B. Kempe, A Memoir on the Theory of Mathematical Form, Philosophical Transactions of the Royal Society of London 177, 1–70, 1886.  Kempe's paper may have introduced vertex and edge coloured graphs (I am ignorant of earlier usage but would welcome pointers).  Kempe also appears to have had some of the same kinds of general applications in mind that Milner envisaged.  Are there other predecessors that should be mentioned?

(Edit: now marking this a community wiki, in the hope of attracting further answers.)


texts: How fast can we perform DFT on a Log-RAM computer?

texts:
The question is how fast we can perform an $n$ coefficient discrete Fourier transform on the log-RAM model of computation.  If we assume that we can do arithmetic operations on registers of size $\log{(n)}$ in constant time, we essentially have the log-RAM model explained in Martin Fürer's preprint "How Fast Can We Multiply Large Integers on an Actual Computer?".

So how fast can we perform the DFT in this model?  Fürer's paper also notes that Schönhage and Strassen's first algorithm in their seminal paper on integer multiplication runs in time $O(n)$ in this model.  Could it be that we can perform the DFT in linear time in this model?

For instance, Bluestein's "A linear filtering approach to the computation of discrete Fourier transform" can help to reduce DFTs to integer multiplication.  One can see "Even faster integer multiplication" by Harvey and van der Hoeven for more ideas on this.  Again, since integer multiplication can be done in linear time in this model, the DFT may be faster, too.

Is there any advantage to performing a number theoretic transform in this model?  This is when all coefficients are nonnegative integers and the transform is done over some finite field $\mathbb{F}_p$, $p$ prime.


texts:
Let's define the integer ADT.

It has, as generators, the constant 0 (a generator) and the succ operation.
Moreover, it also contains the add operation defined by the (usual) axioms

  add (0, x) = x (where x is a variable of type integer)
  add (succ(x), y) = succ(add(x,y)).

Let's assume that I have two terms: add(x, succ(succ(succ(succ(0))))) and succ(succ(succ(succ(succ(succ(0)))))).

Is there an algorithm that finds all the substitutions allowing the first term to be rewritten to the second term?

Thanks in advance,
Ayroles


texts: Multiple independent random number streams

texts:
Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel.

In other words, one thread will have a full-period independent and uniformly distributed stream of pseudo-random numbers. Each thread will consume these numbers in four different functions (a,b,c,d).

My concern is about the distribution across threads for each function. Thread.1 func_a.1, thread.2 func_a.2... and so on. Do I still need to make sure this distribution is indeed uniform across func_a1, func_a2, etc? Failing to do so can make my simulation have flaws?

In summary,if I start using the pseudo-random numbers in a "random" fashion, rejection sampling. Can I still be sure of the normal distribution among the different parts?


texts:
A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the resulting reductions grew out of control.  Eventually this led me to think that there should be some theory that could get a handle on the size introduced by reductions.

For example, what prevents us from taking a source NP-Complete problem (3-SAT, say) and adding a particular type of structure in the resulting NP-Complete problem (HAMILTONIAN CYCLE, say) such that reducing back to the original (3-SAT) would notice the structure and get back the original instance?  Maybe the original problem would need to be 'pre-structured' so that this type of 'ping-ponging' between NP-Complete problems could occur.

In other words, what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size?  The algorithms for reductions would need to notice the structure embedded in the instance and add their own if need.  I could imagine the features to be indicators for the reduction algorithm so that subsequent reductions would be able to avoid instance inflation.

What do these reductions look like?  What's our current best 'inflation factor'?

Surely I'm not the first to think of this.  Does anyone have references that discuss this type of reduction?  Barring that, does anyone have any ideas on what type of structure needs to be added to achieve this result?  I would be surprised if such a method wasn't possible but I would happily hear about any references about impossibility of such a method.


texts:
Recall the hypercontractive inequality:

Let $\rho = \sqrt{\frac{p-1}{q-1}}$, then $||T_\rho(f)||_q \leq ||f||_p$

In https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf it is stated that the dual of the hypercontractive inequality is equivalent to the following:

If $f$ has degree at most $d$, then

$||f||_q \leq \rho ^ d ||f||_p$

I am unable to show this (Specifically, the direction that the original version implies the dual version), and would like to help.

Attempt-

We know for every $g$, $||T_\rho(g)||_q \leq ||g||_p$

Plugging $g = T_{\frac{1}{\rho}}(f)$,

$||f||_q \leq ||T_{\frac{1}{\rho}}(f)||_p$

Now if $p=2$ it's clear how to finish since it's clear how $T_{\frac{1}{\rho}}$(f) affect the fourier coefficients, and it's clear how the fourier coefficients relate to the $l_2$ norm. However for $p\neq 2$, it's not clear to me how to show $||T_{\frac{1}{\rho}}(f)||_p \leq \frac{1}{\rho ^d} ||f||_p$, or even relate the norms.

I will note the proof that the dual implies us works well here (I can provide more detalis if needed, but I don't think it will help).


texts:
This question comes from what I asked in a comment here, although I realized that
I don't actually care about which input is less than the other, if they're different.

Alice and Bob have n-bit strings, and want to figure out if they're equal
while doing little communication. $\:$ They can use a randomized solution,
but there must be zero chance of getting the wrong answer.

Parametrized by $n$, how much communication is needed to for a protocol that:

outputs one of {NO,MAYBE,YES}
for all input pairs, the probability of the protocol outputting MAYBE on that pair is at most 1/2
the protocol never outputs YES on unequal inputs, and never outputs NO on equal inputs
?

Since this falls between the deterministic and the standard randomized cases,
the bounds for those are upper and lower bounds, respectively, for this question.


texts:
The following problem recently appeared in my research. Being no expert on algorithmic questions I have Googled extensively in the search for suitable problems to reduce from. I don't see how 3SAT would work, and even though ZOE is similar in spirit a reduction is not obvious. Another possibility would be the existential theory of the reals. That doesn't seem to be quite the match either but I might be wrong about that.

Problem:
$A$ and $B$ are both $n\times n$-matrices over your favorite field. We assume that an arbitrary set of indices of $A$ are set to 0. Likewise, an arbitrary set of indices of $B$ are set to 0. Question: can we fill in the remaining indices of $A$ and $B$ such that $AB = I_n$?

Example: $A = \begin{bmatrix} 0 & a_1 \\ a_2 & 0 \end{bmatrix}$, $B = \begin{bmatrix} b_1 & 0 \\ 0 & b_2 \end{bmatrix}$. Not possible.

What is the computational complexity of this (in $n$)?

Any hints or ideas to where to look for similar results in the literature will be greatly appreciated.

EDIT (completely forgot about this post): In recent work which is available on the arXiv (if anyone is interested in the preprint let me know) we have shown that the problem is NP-hard over any finite field.


texts: Oncina-Garcia RPNI algorithm for learning DFAs

texts:
The question refers to this paper:
ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf

Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+n)p^2)$. Nothing is claimed about the size of this DFA; if its size were $o((p+n)/\log(p+n)))$, that would imply a compression-based generalization bound. Of course, if they were able to always compress to size poly(opt) -- where opt is the size of the minimal consistent DFA --- that would imply P=NP, via a result of Pitt and Warmuth.

Questions: (1) Is anything at all known about the size of RNPI's resulting DFA? (2) In the linked paper, they claim that RNPI "can identify any regular language in the limit". Has that claim been rigorously proved anywhere? I couldn't find such a proof in the paper.


texts: Tight examples for approximating the feedback vertex set problem

texts:
There are several 2-approximation algorithms for the UNWEIGHTED feedback vertex set problem (FVS), which are summarized in [4]. Note that the reduction from vertex cover to FVS is approximation-preserving. Assuming Unique Game Conjecture, we cannot expect better algorithms. The question is:

Is there an unweighted graph on which some of the algorithm really reaches ratio 2?

[1] contains such a tight instance for weighted FVS.

Vineet Bafna and Piotr Berman and Toshihiro Fujito,
http://doi.org/10.1137/S0895480196305124;
Ann Becker and Dan
Geiger, http://doi.org/10.1016/0004-3702(95)00004-6;
Toshihiro
Fujito, http://doi.org/10.1016/0020-0190(96)00094-4;
Fabián A.
Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson,
http://doi.org/10.1016/S0167-6377(98)00021-2.


texts: Illustrative Examples of Tarski's Fixed Point Theorems

texts:
I have come across many informal examples that provide a physical illustration for Brouwer's fixed point theorem (some due to Brouwer himself).

A person walks from the bottom of a hill to the top. The next day the person walks from the top of the hill to the bottom. If both journeys start and stop at the same time, there exists a place where the person is at the same time on both days.
If a paper is crumpled and dropped onto another identical, flat sheet, then flattened, there exists a point that is directly above itself.
If a floor plan of a building is taken into the building, there is always a point that can be marked "You are here".
Etc, etc etc.

I have seen similar illustrations for the hairy-ball theorem, and the ham-sandwich theorem. I am interested in Tarski's Fixed Point Theorem.

  Theorem. A monotone function on a complete lattice has a fixed point.

Are there intuitive, physical-world examples that illustrate this theorem?


texts:
We know that using FFT we can compute multiplication of an $a$ bit number with a $b$ bit number in $(a+b)^{1+\epsilon}$ time.

My question is supposing we want to compute $A\bmod B$ where $A$ is an $a=f(b)$ bit number for some linear function of $b$ with $B$ a $b$ bit number, what is the time and space complexity of such an operation? Could it be done in fully linear ($O(a+b)$) time and space complexity (at least assuming $B$ is fixed per $b$ bits and $A$ is input)? I have been unable to find such a reference or procedure for this operation even when $B$ is fixed (which is the case useful in operations such as Diffie Hellman key exchange).


texts: I wonder whether there is any relationship between lambda calculus and phonology (study of phonemes). Specifically, how one would use the concepts of lambda calculus (typed or untyped) in the study of phonology of a particular natural language, like English, German, or Finnish? It would be much appreciated, if you could mention some introductory texts, papers, books, etc. about this.


texts: Are there integer programs with small coefficients that only have large solutions?

texts:
It is well-known that if an integer linear program has a feasible solution, then it has a feasible solution whose bit size is polynomially bounded. For example, here is Theorem 13.4 from Papadimitriou and Steiglitz' Combinatorial Optimization book (paraphrased):

  Consider the ILP $$Ax \le b, \quad x \ge 0, \quad x \in \mathbb Z^n,$$ where $A$ is an $m\times n$ matrix. Let $r = \max |a_{ij}|$ be the largest value appearing in $A$, and let $s = \max |b_j|$. Then if the ILP has a feasible solution, then it has a feasible solution $x$ with $x_i \le (n+m)(mr)^{2m+3}(1+s)$ for each $i \in [n]$.

Via binary encoding, this implies that integer programming is contained in NP. (The intuition is that large coefficients are required to induce sharp angles in the polyhedron. Results like above can be found in many textbooks, but the following question never seems to be addressed.)

I wonder whether the upper bound given is actually attained. Are there examples of feasible integer programs where all coefficients are small (maybe even $|a_{ij}|, |b_j| \le 1$) and yet all feasible solutions contain exponentially large numbers?

Equivalently, I wonder whether feasible integer programs encoded in unary have a solution whose unary size is polynomially bounded in the input size.


texts: Counterintuitive results for undergraduates

texts:
I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get it wrong. Results' statement should be easily explainable to undergraduates in cs/math. I am mainly looking for results in computer science.

What are the most counterintuitive/unexpected results (of general interest) in your area?


texts: Computing the Löwner-John ellipsoid of a polyhedron

texts:
The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations available if $C$ is (the convex hull of) a set of points.

Are there fast (i.e non-ellipsoid-method based) approximations to the MVE of a bounded polyhedron presented only in terms of the halfplanes whose intersections define it ? In particular, I'd be interested in methods that run in time polynomial in the dimension and the inverse error $1/\varepsilon$.


texts: What is the logarithm or root operation in type-space?

texts:
I was recently reading The Two Dualities of Computation: Negative and Fractional Types.  The paper expands on sum-types and product-types, giving semantics to the types a - b and a/b.

Unlike addition and multiplication, there are not one but two inverses of
exponentiation, logarithms and rooting.  If function types (a → b) are
type-theoretic exponentiation, given the type a → b (or b^a) what does it mean to have
the type logb(c) or the type a√c?

Does it make sense to extend logarithms and roots to types at all?

If so, has there been any work in this area, and what are some good directions on how to comprehend the repercussions?

I tried looking up information on this via logic, hoping the Curry-Howard correspondence could help me, but to no avail.


texts: Order-invariant conjunctive queries are FO-definable without the order

texts:
I'm looking for a reference for Exercise 6.11 from Libkin's FMT book:

Prove that an order-invariant conjunctive query is FO-definable without the order relation.

All help is appreciated.


texts:
Consider the following two system of linear (in)eqaulities:

$S = Ax \leq b;\; Cx = e$

$T = Dx \leq d;\; Gx = g$

How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the linear system $T$.


texts: Examples of $\Sigma_2^p$ complete problems?

texts:
I need a list of $\Sigma_2^p$ complete languages. There are two such problems listed in the Complexity Zoo, namely:

Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of literals?
Shortest implicant. Given a formula F and integer k, is there a conjunction of k or fewer literals that implies F?

Another basic $\Sigma_2^p$ complete problem:

$\Sigma_i \text{SAT}$. Given a quantified boolean formula $\varphi$ of the form $\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$, is $\varphi$ valid?

However, I am hopefully looking for a problem which makes use of graphs (e.g. a clique related problem).


texts:
Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.

If God had a similar book for algorithms, what algorithm(s) do you think would be a candidate(s)?

If possible, please also supply a clickable reference and the key insight(s) which make it work.

Only one algorithm per answer, please.


texts: Split find-min data structure that finds several small elements?

texts:
The split find-min data structure is initialized with a sequence of elements $e_1,\ldots,e_n$, each associated with a key. The data structure supports three operations:

(1) $Split(e_i)$ that splits the sequence at position $e_i$.

(2) $FindMin(e_i)$ that returns the minimum in the interval that contains $e_i$.

(3) $DecreaseKey(e_i,k)$ that decreases the key of $e_i$ by $k$.

For instance, you may have started with $[5,2,1,4]$, where the min is $1$, then split at $2$ to get $[5][2,1,4]$, so the min of the first interval is $5$ and the min of the second interval is $1$.

Seth Pettie gave an implementation of this data structure that makes at most $O(m\log\alpha(m,n))$ comparisons when $m$ is the number of $DecreaseKey$ operations and $n$ is the number of elements ($\alpha$ is the inverse Ackermann function).
For more details see the paper:

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
http://arxiv.org/abs/1407.1910

My question is: Suppose that you want to support queries not about which is the min element in each interval, but about which are the $l$ smallest elements in each interval, for a parameter $l\gg 1$ (note that you don't need to know the order among the $l$ smallest elements, only what they are). How many comparisons do you need for that?


texts: Graph partitioning, balancing on within subset edge weights

texts:
I'm interested in pointers to algorithms (approximation algorithms are fine) that attempt to partition a graph into two subsets such that the sum of the edge weights within each subset is (approximately) equal, and the sum of the edge weights between the two subsets is (approximately) minimal.

Any pointers are much appreciated.


texts: Complexity class when reducing decision problem to function problem

texts:
Given a decision problem DEC which is PSPACE-Hard and a function problem FUN.  If there is a polytime reduction from DEC to FUN, does this mean that FUN is FPSPACE-Hard?

In my case, the answer of the function problem is the one of the decision problem plus additional information.  So it seems natural to assume that it is at least as hard.  The question is whether this means that a lower bound for its complexity is the "function class" corresponding to the complexity class of the decision problem.


texts: Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$

texts:
Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence Number of such a $G$.

Question
Which is the best known upper bound on the Indipendence Number $\alpha(G)$ of such a so dense $G$?

The closest references I've found are:

The Independence Ratio of Regular Graphs by Béla Bolobás, October 1981. Here there is no random restriction, and the degree is considered to be a constant. But at top of page $4$ it is written that for a general $\Delta$ relation the Independence Number is asymptotically upper bounded by $\frac{2 \log \Delta}{\Delta}|V|$. This alone should nail down the question. But see below.
This presentation where, at slide 16, it is said that $\alpha(G) = \frac{2 \log \Delta}{\Delta}|V|(1+O(\xi))$ is asymptotically almost surely satisfied, where $\xi \to 0$ as $\Delta \to \infty$. To be noted that such slide says "Fix $\Delta \geq 3$...", the verb "to fix" seems to suggest that $\Delta$ is a constant. Such slide cites the result here below.
On the Independence and Chromatic Numbers of Random Regular Graphs by A. M. Frieze and T. Łuczak, May 1988. From the very abstract, it is already clear that they allow $\Delta$ to grow with $|V|$. However: for their result to hold, they require that $\Delta \in o(|V|^\theta)$ where $\theta < \frac{1}{3}$. Such requirement is clearly false in my case. Does it mean that the general $\Delta$ mentioned by Bolobás is not as general as to encompass the $\Theta(\sqrt{|V|} \log^2 |V|)$ case...? For if it encompasses it (as I hope), then why Frieze and Łuczak would have proven a result less powerful than the result already proven $7$ years before by Bolobás? This confusion makes me asymptotically almost sure that I'm missing something here.


texts:
I am writing a computer science textbook and want to use an illustration showing a Turing machine.  Images are all over web, but almost always without authorship/illustratorship credited. I need to attribute authorship (and perhaps also clear rights).
Does anybody know where the image reproduced below first appeared?
Alternative: Can anybody point me to a similar illustration of a Turing machine where authorship is known?


texts: Example of scalable non-Hamiltonian cubic planar graph

texts: Suppose I have a non-Hamiltonian non-bipartite cubic planar graph $G_1$ = ($V_1$, $E_1$) where no face has fewer than five sides, and that I can partition $V_1$ into two Hamiltonian subgraphs.  Suppose further that $G_1$ has a set of faces that satisfies the Grinberg equation (remember that satisfaction of the Grinberg equation is a necessary but  not sufficient condition for a graph to be Hamiltonian), and is minimally two-connected, i.e., it contains exactly two edges, $v_1$ and $w_1$, whose removal disconnects $G_1$. Finally, assume that $G_1$ contains no separating triangles. Is there an example of such a $G_1$ that I can augment (judiciously) without limit by successively adding sets of vertices and edges to it in such a way that I create the series ($G_1$, $G_2$,...,$G_n$),  |$V_i$| < |$V_j$|, n $\in$  $\mathbb{Z^+}$, where $G_i$ retains the given properties (including $v_1$and $w_1$) of $G_1$?


texts: Survey on algorithms/complexity of linear algebra

texts:
I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with emphasis on parallel ($NC$ hierarchy) and polytime algorithms. I could not find a recent one.

Do you know a good recent survey or book on complexity of linear algebra?


texts: Document references describing weaknesses for cutting planes and algebraic proof system?

texts:
Here, Fortnow says (section 4.3):

  Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on polynomials and (...)

I am trying to find references to documents describing weaknesses for cutting planes and algebraic proof system regarding the P vs NP question. Unfortunately, Fortnow's document does not provide any.


texts:
In Descriptive Complexity, Immerman has

  Corollary 7.23. The following conditions are equivalent:
  1. P = NP.
  2. Over finite, ordered structures, FO(LFP) = SO.

This can be thought of as "amplifying" P=NP to an equivalent statement over (presumably) larger complexity classes.  Note that SO captures the polynomial-time hierarchy PH, and that FO(LFP) captures P, so this can be thought of as P=NP iff P=PH.

(The interesting part of this is the statement that P=NP implies P=PH; it is trivial that P=CC implies P=NP for any class CC that contains NP.  Immerman simply remarks "if P=NP then PH=NP", presumably because P=NP can be used with the oracle definition of PH to show inductively that the whole hierarchy collapses.)

My question is:

  How much further can P=NP be amplified in this way?

In particular, what is the largest known class CC' such that P=NP implies P=CC', and the smallest class CC such that P=NP implies CC=NP?  This would allow P=NP to be replaced by the equivalent question CC=CC'.  P appears to be a rather powerful class, which seems to provide little "wiggle room" for arguments trying to separate it from NP: how far can the wiggle room be amplified?

I would of course also be interested in an argument that shows that P=PH is the limit of this approach.

Edit: note the closely related question Why doesn't P=NP imply P=AP (i.e. P=PSPACE)? which focuses on the other direction, why we don't have proofs that P=PSPACE.  Answers there by Kaveh and Peter Shor argue that the number of alternations being fixed is key.  Another related question is A decision problem which is not known to be in PH but will be in P if P=NP which asks for a candidate problem; the answers there also can be used to construct answers for this question, although these classes are somewhat artificial (thanks to Tsuyoshi Ito for pointing this out).  In a more general setting, Collapsing of exptime and alternation bounded turing machine asks whether a local collapse at any level in an alternation hierarchy induces an upward collapse, as happens with the polynomial-time hierarchy.


texts: Assigning probability to membership in an NP-complete language

texts:
Motivation

Assuming $\mathsf{P}\ne\mathsf{NP}$, it is impossible to efficiently decide membership in an NP-complete language. I would like to assign probability to such membership, in some sense.

Definitions

The following definitions use the approach to average-case complexity given in e.g. O. Goldreich "Computational Complexity" chapter 10.

Consider $(L, X_n)$ an average-case decision problem where $L$ is a language and $X_n$ is a family of random variables which can be sampled by an algorithm with polynomial running time.

Consider $A$ an algorithm computing for each input string $x$ an infinite binary fraction in $[0, 1]$ (informally regarded as a probability). We call such algorithms "estimators". $A$ is called efficient when the time of computing $k$ digits of $A(x)$ is bounded by $p(|x|, 2^k)$ with $p$ polynomial.

Define the error function to be

$$\epsilon_n(A; L):=-E_{X_n}[\chi_L(x)\ln A(x) + (1-\chi_L(x))\ln(1-A(x))]$$

where $\chi_L(x)$ is the characteristic function of $L$. It is easy to see that assuming $\mathsf{sampP}\ne\mathsf{sampNP}$, for $(L, X_n)$ which is $\mathsf{sampNP}$-complete there is a polynomial $q$ s.t.

$$\forall n \exists m > n:\epsilon_m(A; L) > \frac{1}{|q(m)|}$$

Define $A$ to be optimal for $(L, X_n)$ when it is efficient and for any efficient $B$ and polynomial $r$:

$$\forall n >> 0:\epsilon_n(A; L) - \epsilon_n(B; L) < \frac{1}{|r(n)|}$$

Question

  Assuming $\mathsf{sampP}\ne\mathsf{sampNP}$ (and other conjectures if necessary), does $A$ exist which is optimal for an $\mathsf{sampNP}$-complete problem?

Observations

Reductions

Let's call a Karp-reduction $f$ of $(L, X_n)$ to $(M, Y_n)$ semi-invertible when there exists $g: \lbrace 0, 1 \rbrace^* \rightarrow \lbrace 0, 1 \rbrace^* \cup \lbrace \bot \rbrace$ computable in polynomial time s.t.

$$\forall x: g(f(x))=x$$

$$\forall y: g(y) \ne \bot \rightarrow f(g(y))=y$$

Given $A$ optimal for $(M, Y_n)$ and $f$ a semi-invertible reduction of $(L, X_n)$ to $(M, Y_n)$, $A \circ f$ is optimal for $(L, X_n)$. In particular, if $(M, Y_n)$ is $\mathsf{sampNP}$-complete s.t. the reductions can be chosen semi-invertible (such $(M, Y_n)$ exists since examining the construction of a complete problem in Ben-David et al we see the reductions are semi-invertible), we get optimal algorithms for all problems in $\mathsf{sampNP}$. In particular, $A$ yields an average-case polynomial time solution for any problem formulated as a problem in $\mathsf{sampNP}$ which is "secretly" in $\mathsf{sampP}$. This is similar to the properties of Levin search, but Levin search only solves instances with a positive answer.

Uniqueness

Consider $A$, $B$ estimators for $(L, X_n)$. Define the "metric"

$$\delta_n(A, B; L) := E_{X_n}[\chi_L |\ln{A} - \ln{B}| + (1-\chi_L) |\ln{(1-A)} - \ln{(1-B)}|]$$

If $\delta_n(A, B; L)$ vanishes for large $n$ with superpolynomial speed, then $\epsilon_n(A; L) - \epsilon_n(B; L)$ also vanished for large $n$ with superpolynomial speed.

Suppose $A$ and $B$ are both optimal. Then it can be seen that $\delta_n(A, B; L)$ vanishes for large $n$ with superpolynomial speed (via considering $\frac{A+B}{2}$ and using the convexity of the logarithm). So optimal estimators are unique up to "small" deviations.


texts: Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

texts:
In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-Shapiro's theorem, etc. These techniques work thanks to, or are directly based on, the existence of some diagonal argument (i.e. some program $M$ behaves in the opposite way as its input program $M'$, so $M = M'$ is contradictory). In Complexity, if we want to prove that some problem cannot be computed in some time (regardless of any unproved claims such as e.g. $P \neq NP$), we use arguments which are, ultimately, based on some diagonal argument (e.g. the Time Hierarchy theorem proves $EXPTIME$-complete problems are not in $P$, but that theorem is also proved by using a diagonal argument).

So my question is the following. Are all important impossibility results in Computability and Complexity (actual impossibility, not impossibility up to some unproved result) ultimately due to some diagonal argument? That is, does all our important "impossibility knowledge" in Computability and Complexity come from the fact that programs are powerful enough to execute programs?

The only important impossibility result coming to my mind which is not ultimately due to a diagonal argument is that the Ackermann function is not primitive recursive. Am I missing other important counterexamples of this apparent "rule"?

EDIT (Nov 18): Sorry for implying that my question was particularly focusing on the diagonal argument itself, but I'm more interested on all arguments that rely on the self reference of programs (including the diagonal argument, Berry paradox, etc). For simpler languages (e.g. regular or context-free), we have "structural" impossibility arguments based on how these languages are constructed (e.g. pumping lemmas). However, for recursive or r.e. languages, most of impossibility results strongly rely on the self reference of programs. This is what I meant.


texts: How to prove integrality of LP with not totally unimodular matrix

texts:
I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU).  However, even though constraint matrix is small (14x20), extensive generation of random coefficients for objective function did not allow me to find the problem formulation for which optimal solution value changes if I add integrality constraints.

I believe that the reason might be that I also have some constraints on the objective function coefficients - I know that some coefficients are 0'os, and some coefficients are equal.

Given that, I wanted to know if it is possible to prove that given my specific subset of objective functions the objective will always be integral, and what should be the way to do that.

Provided that my hypothesis is true, I also wanted to ask if it is easy to find an integer solution, given the solution of an LP, if I know that the objective function value will be the same. (Some kind of movement on the hyperplane of active constraints?)

Any relevant literature links are appreciated.

Thank you!


texts: Recursive parallel topological sorting in linear time

texts:
While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer algorithm that

  requires $O(n+m)$ processors and $O(\log^2m)$ time on a CREW-PRAM model

Unfortunately the paper is not only behind pay wall but is also in Japanese except for the abstract. I was able to obtain a copy, however only from the abstract and some contained (English) pseudocode I did not fully understand the details of the algorithm/analysis.

I found few references in English papers (such as this), but none does more then mention in.

Does anybody know of an English (or perhaps German?) description of the details of this algorithm?


texts: Complexity of universal computation on random input

texts:
This post is a refinement of a previous question which turned out to be trivial
It is also related to another previous question
Motivation: A property commonly ascribed to artificial intelligence is the ability to solve generic problems. In my opinion, this must be supplemented by a requirement of efficiency, otherwise any solvable problem can be solved by brute force which would hardly count for intelligence. Therefore it seems natural to explore the complexity bounds of universal problem solvers. Also, rather than treating all problems "equally", it makes sense to focus on problems with low Kolmogorov complexity which is elegantly achieved by generating random programs for a prefix-free universal Turing machine. The significance of these random programs in the context of artificial intelligence was acknowledged in the context of Solomonoff induction, the intelligence measure introduced by Legg and Hutter and other works on universal intelligence
Formal statement of question: Consider an input-less algorithm $A$ generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Suppose further we have an infinite sequence $A_1, A_2, A_3...$ of such algorithms, each generated randomly and independently of the others. Denote $t_1, t_2, t_3...$ the execution times of these algorithms. We can then define
$$\nu(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t_i}<t}\right\})$$
Here $E_{halt}$ is conditional expectation value, the condition being that all algorithms halt. In other words, $\nu(t)$ is the average number of algorithms that can be executed during time $t$, assuming the algorithms are sampled randomly from our ensemble, but avoiding algorithms which don't halt. If the conditional expectation value of the execution time of $A$ had a finite value $\tau$, $\nu(t)$ would behave asymptotically as $t / \tau$. However $\tau$ is infinite since the busy beaver function grows (much) faster than exponentially, as pointed out by Artem Kaznatcheev in response to my previous question. Hence $\nu(t)$ grows much slower than linearly.
Now consider $U$ a universal computer i.e. an algorithm taking an input-less algorithm $B$ for input and producing $B$'s output for output. My point of view is that $B$ is a "problem" and $U$ is a "universal problem solver". It seems reasonable to assume that if $U$ represents an intelligent agent it should in some sense perform better than simple execution of $B$. One is reminded of the anecdote about Gauss when his school teacher gave the class an assignment to sum all numbers from 1 to 100. Instead of doing it head-on, like the teacher intended, Gauss discovered the formula
$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$
Denote $t^U_1, t^U_2, t^U_3...$ the execution times of $U$ given the input $A_1, A_2, A_3...$. Define
$$\nu_U(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t^U_i}<t}\right\})$$
$$T:=\inf_U \limsup_{t \to \infty} \frac{\nu(t)}{\nu_U(t)}$$
Obviously $T < \infty$. Finally, the questions:

Is T > 0?
Is T achieved for a specific $U$ i.e. is it a minimum?


texts: $\mathbb{N}$ in intensional MLTT with judgmentally commutative $+$ and $\times$

texts: Is there a way to implement natural numbers in intensional Martin-Löf type theory so that addition and multiplication is judgmentally commutative?


texts: Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words

texts:
Consider a deterministic transition structure having states in set $X$ and transition function $\rightarrow$, and an initial state $x \in X$. This structure is intended to be part of an automaton accepting streams, such as a Buchi or Muller automaton.

Given a regular language of non-empty finite words $L$, and a word $v \in L$, define $I(v)$ to be the inf-set of $v^\omega$, that is, the set of states that is traversed infinitely often by the unique run of $v^\omega$ starting from $x$.

One can define the following notion:

$(X,\rightarrow)$ is separated by $L$ if and only if the sets $\{ I(v) | v \in L \}$ and $\{ I(v) | v \notin L\}$ have empty intersection. In words, the set of inf-sets of words in $L$ and of words not in $L$ are disjoint.

A counterexample is the single-state deterministic structure against the regular language $a^+ \cup b^+$; we have $I(ab) = I(a)$ with $a \in L$ and $ab \notin L$.

The question is: is this notion known? In particular, I would like to prove that all non-empty regular languages separate some finite deterministic structure. I wonder if that is known already.

Note: one can assume that $L$ is invariant under the equivalence $u = v \iff u^\omega = v^\omega$, making it a "looping" language.


texts: Inferring Cartesian position from a set of nodes where only distance is known

texts:
I am attempting to resolve a problem of inferring Cartesian position from distance. I have a set of nodes arbitrarily but statically positioned on a 2-D plane. Every node is aware of its position relative to the other $n-1$ nodes. From this set of $n$ nodes, is it possible to infer each node's position ($x$,$y$) by choosing any node and using it as a basis?

For example, with two nodes, this is not possible, as the distance alone leaves open the possibility of the node not chosen as the basis for being located anywhere in the radial distance from the basis node.

With three nodes, it also seems impossible because the orientation can be flipped and is thus ambiguous based solely on distance. How many nodes are needed to unambiguously infer the position of the elements on a Cartesian plane?


texts: Holographic Algorithms - Equivalence of Bases

texts:
I was going through Les Valiant's seminal paper and I had a tough time with Proposition 4.3 on page 10 of the paper.

I cannot see why is it the case that if there is a generator with certain values for $valG$ with a basis $\{(a_1,b_1) \ldots (a_r,b_r)\}$, then there exists some generator with same $valG$ values for any basis $\{(xa_1,yb_1) \ldots (xa_r,yb_r)\}$ ($1^{st} kind$) or $\{(xb_1,ya_1) \ldots (xb_r,ya_r) \}$ ($2^{nd} kind$) for any $x,y \in F$.

Valiant points out the reason in preceding paragraph  - namely the $1^{st}$ kind of transformation can be achieved by appending to every input or output node an edge of weight $1$. The $2^{nd}$ kind of transformation, Valiant says, can be achieved by appending to input or output nodes chains of length $2$ weighted by $x$ and $y$ respectively.

I have not been really able to understand these statements. Maybe they are already clear, but still I cannot really see why the above construct helps achieve any realizable $valG$ values with one basis with the new basis which is one of the above types.

Please help illuminate them to me. On a different note, are there some tensor free surveys for hologaphic algorithms available online. Most of them use tensors which, sadly, scare me :-(

Best
-Akash


texts: Commitment schemes with verification in NC0

texts:
Is there any secure cryptographic commitment scheme, where the verification routine can be implemented in $NC^0$?  If so, what is the minimum possible depth of the circuit for verification?

Applebaum et al prove the existence of a commitment scheme where commitment can be done in $NC^0$ and where verification can be done with a $NC^0$ circuit plus a single AND gate of unbounded fan-in.  See

Cryptography in NC0.  Benny Applebaum, Yuval Ishai, Eyal Kushilevitz.  Section 7.

However, this does not show how to do the verification in $NC^0$, i.e., in constant depth.  Is there a plausible construction to achieve that goal?

For a result of a similar flavor, see also

Cryptography with Constant Input Locality.   Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.  Journal of Cryptology, 2009, 22:429-469.

which gives a plausible construction of a commitment scheme with similar properties; but again their verification scheme involves a $NC^0$ circuit plus a single AND gate of unbounded fan-in.

Motivation. I came across this problem when thinking about how to obfuscate a particular function that uses the verification component of a commitment scheme, but I realized this might be of broader interest.


texts: Succinct graphs with ability to perform random walk

texts:
Suppose I have an exponentially large graph $G$ ($|G|=2^n$) supplied with an efficient (of size $poly(n)$) randomized circuit $C_G$ implementing the random walk on $G$ - that is, $C_G$ takes a vertex index $i$ and outputs a random neighbor of $i$.

Has this type of graph specification been studied and is it more powerful that the standard succinct representation, where $G$ is given as an efficient circuit that given $i,j$ outputs whether $(i,j)$ is an edge in $G$? I could imagine that being able to perform a random walk could help e.g. in detecting triangles in a dense graph (e.g. by choosing a random starting vertex and performing a random walk of length $3$; on the other hand, deciding triangle-freeness in the usual succinct model in NP-hard)


texts: Perfect Matching with ``set-over-like" constraints?

texts:
Problem Description:

Let k and n be some natural numbers. We are given a complete bipartite graph G where each side of G has n vertices. G is edge-labeled with labels being subsets of {1,...,k}. We are looking for a perfect matching G' such that the union of sets labeling edges of G' equals {1,...,k}.

The problem is clearly NP-hard in k, but is it also NP-hard in n? I.e. can one achieve an algorithm that is polynomial in n while possibly being exponential in k (maybe via adaptation of the Dynamic Programming algorithm for set cover..)?

Many thanks,
Amir


texts: Finding the shortest path in the presence of negative cycles

texts:
Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the Bellman-Ford algorithm.

However, I'm interested in finding the shortest-path between two vertices that doesn't involve cycling (ie. under the constraint that you may not visit the same vertex twice). Is this problem well studied? Can a variant of the Bellman-Ford algorithm be employed, and if not is there another solution?

I'm also interested in the equivalent all-pairs problem, for which I might otherwise apply Floyd–Warshall.


texts:
The question is: what are examples of clique problem applications? I mean, what problems can be solved by reducing to clique problem (sorry for tautology)?

All I came with is finding social cliques: groups of people who know each other personally.

I understand, that similar ideas may arise in electronics, CS (i.e., compiler design?) and probably other fields, but can't think of other interesting problems.

Would be glad to see some of them.


texts: understanding generalized coupon collector for distributions or learning mixture of distribution

texts: Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from the distribution $P$, can we learn $T_1$ and $T_2$? Clearly, using a coupon collector argument, we can learn $T_1\cup T_2$ using $O(n \log n)$ samples from $P$ and suppose $T_2$ was empty, we can learn $T_1$ completely. But is there a way where we can learn both $T_1$ and $T_2$ individually? I don't mind even allowing $poly(n)$ many samples from the distribution $P$.


texts: Approximation of covering number in metric space

texts:
Consider the following setting:

Let $(X,d)$ be a metric space and let $S$ be a finite subset of $X$. An $\epsilon$-cover of $S$ is any subset $C\subset S$ such that
$$
\max_{x\in S} d(x,C)\leq \epsilon,
$$
where $d(x,C)=\min_{y\in C} d(x,y)$. Let's call the $\epsilon$-covering number of $S$, denoted by $N(S,\epsilon)$, the size of its minimal $\epsilon$-cover:
$$
N(S,\epsilon)=\min\{ |C| \mid C \text{is an $\epsilon$-covering of } S\}.
$$

My question is the following: Are there any good approximation algorithms for computing the covering number? I am aware of an algorithm based on farthest-first traversal that outputs a number $N$ such that $N(S,\epsilon)\leq N \leq N(S,\epsilon/2)$. Is there anything out there which does better?


texts: What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

texts:
What is the complexity of the following problem? (e.g. best-known running time, space, best upper bound in terms of complexity classes, etc.)

Input: A multivariate polynomial $f$ with coefficients over $\mathbb{Z}$
Decide: Is there a rational zero of $f$?

What about the complexity where $f$ is the translation of a Boolean formula under the standard translation? (viz. $t(x) = x$, $t(f \vee g) =  1-(1-t(f))(1-t(g))$ and $t(f \wedge g) = t(f) t(g)$; thus, a $\{0,1\}$ assignment satisfies $f$ iff it satisfies the polynomial equation $t(f)=1$.)


texts: Distributions which are intractable to sample from?

texts:
I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from.

I'm not sure what the right notion of intractable is, though I know the notion of efficiently samplable: the existence of a polynomial-time randomized Turing machine that can simulate samples from $P$.

  Q1: Is a reasonable notion of intractable that if there exists such a randomized Turing machine, it can be derandomized to solve an NP-complete problem? If not, what is the right notion? Is there a good reference for this? (Or just some good search terms.)

There are a lot of tautological examples along the following lines: there is no algorithm to sample from [set of solutions to NP-complete problem union a symbol for no solution], because there is an obvious reduction to [that NP-complete problem] by taking the output of the sampler.

  Q2: What are some more interesting examples of intractable sampling problems than these?

There are also examples perhaps like this: Given a set $X$, the goal is to sample uniformly from $P(P(X))$ (powerset). If you could do so with a polynomial time turing machine, you could produce exponentially many bits of entropy in only polynomially many coin flips, which is impossible (because $H(f(Y)) \leq H(Y)$ for any random variable $Y$ and deterministic function $f$).

In order to avoid this kind of example, I want the underlying set of the distribution to grow at most like $2^{p(|x|)}$, where $p$ is a polynomial in the size of the input.


texts: What is the minimal known space for polytime algorithms

texts:
Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured bounds?

Are the bounds different if we require the new algorithm to also take $O(n^k)$?


texts: Upper bound to number of closed itemsets

texts:
Given a set $I$ of $n$ items, and a collection $D$ of $m<2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper supersets. Closed itemsets are important in data mining because they provide a compact representation of the dataset.

I'm trying to find some non-trivial upper bound to the number of closed itemsets. It seems a natural combinatorial question and I'm surprised I can't find anything non-trivial.

Any suggestion/reference? Thank you.


texts: Complexity of acyclicity of a "nondeterministic" graph

texts:
By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible to pick one edge from each candidate set, so that the picked edges form an acyclic graph.
When the candidate sets are all singletons, the graph is then deterministic and the problem is of course linear. The general case seems sufficiently complicated to be NP hard, but I couldn't prove it, nor did I find any related literature.
Does anyone know whether this problem has already been investigated? Is it NP hard?
Thanks!


texts:
Consider the following maximisation problem.

Given a path $P=\{1,2,\dots,n\}$ over $n$ vertices, a set $D\subseteq P\times P$ of "edges" and a set of positive integers capacities $\mathcal{C}=\{c_{i,j} \mid 1\le i<j \le n\}$ for each subpath, we define the cut of the subpath $\{i,\dots,j\}$ by $H\subseteq D$, written $d_{i,j}(H)$ as the number of edges in $H$ with exactly one endpoint between $i$ and $j$:
$$
d_{i,j}(H):=\vert\{(x,y)\in H \mid x<i\le y \le j \text{ or } i\le x \le j < y\}\vert
$$

The goal of $\Pi$ is to find a maximum cardinality subset $H\subseteq D$ such that for all $1\le i<j\le n: d_{i,j}(H)\le c_{i,j}$, which means that any cut must not exceed the given capacity.

This problem is a special case of Set-packing by considering $D$ as the ground set and subpaths as sets. I would be interested in any thought that could suggest that this problem admit a strictly better approximation that classic Set-packing.

Further, another version that is of interest is the one where the additional "non-crossing" property is requiered: a solution $H\subseteq D$ is feasible if the capacities are respected and for any two edges $(i,j)$ and $(i',j')$ in $H$, either $j<i'$ or $j'<i$ or $i<i'<j'<j$ or $i'<i<j<j'$. Can this additional constraint allows us to find a constant approximation ? For this particular case, one can find a $O(\log n)$-approximation with dynamic programming.


texts: What is the difference between a model of computation and a programming language?

texts:
https://en.wikipedia.org/wiki/Model_of_computation includes sequential models, functional models and concurrency models.

Sequential models include finite state machine, Turing machines, random access machine.

Functional models include lambda calculus.

Concurrency models include pi calculus, the actor model.

I have seen lambda calculus, pi calculus, and the actor model are formulated as languages with syntax and semantics.

Some books (such as Varela's Programming Distributed Computing
Systems) present models of computations and then programming
languages which "follow" the models.

What is the difference between a model of computation and a programming language, if both can be formulated as languages with
syntax and semantics meaning computation? (For example, I didn't realize to make any distinction, and called lambda calculus as a programming language, but was corrected.)

What is the definition of the "follow" relationship between models of computation and programming languages?

I haven't found out whether finite state machine, Turing machines,
and random access machine are formulated as languages with syntax
and semantics. I wonder if they can be and why they aren't or are
not often formulated as such?

Thanks.


texts:
I am about to begin a verification project (for MIPS)  with my professor (I am a senior undergraduate) and have been told that the soundness proof for the program logic we need will probably involve step-indexing. I have read the Very Modal Model paper by Appel et al. and after a short tutorial by my prof, I think I have a basic understanding of step-indexing. However it has been kind of slow going. Especially when the $\mu$ operator and contravariance come up.

I would like to ask for either the original papers where step-indexing was introduced (from what I understand it traces back to the 50-60s? but am having trouble finding them) or if someone can point out a tutorial, that would also be great.


texts: Is there any good and free Introduction to topological graph theory

texts:
My knowledge in topological graph theory is in low, I need some good reference which has two simple thing, Definition of new concepts (like genus,graph embedding in surface, ...) also contains related theorem on this topic, It's not essential to prove theorem, I think there should be something like wiki or good survey.

I found some books, but first of all I need some overview on it, maybe it's not necessary to have book to come up with my problems, I found something in wolfram but it's not integrated, and It's not easy to find all related things (because I don't know them) and print them all to have in hand. So first I need good bible (specially free).

In fact I'm working in some aspects of planar graphs and some other types of graph which are near to them (like graphs with small genus), everyone know about filed has any suggestion (book, book chapter, Advise, ... ) I'll be happy to know it.

Also If you know any theorem or definition, I'll be happy to know it, and sure upvote it, because if there isn't good reference is good create one here.


texts: Algorithm/Complexity for the following SAT Version

texts:
Given   : A 3 SAT problem.

Known 1 : The SAT problem is satisfiable.

Known 2 : We have a solution that satisfies the given 3 SAT.

Problem Statement: Maximize the solution, i.e. find a solution such that it contains the maximum number of 1's amongst all possible valid solutions to the given problem.


texts: What relations are there between a problem hardness and the hardness of verifying a witness?

texts:
I had some hard times trying to formulate the question, so I'll start with some examples:

Suppose you are given a Dominating Set instance, $<G,k>$.

Now suppose I give you a set of vertices $D$ of size $k$. Deciding whether $D$ is a dominating set of $G$ requires linear time in the size of $G$, and doesn't seem to be possible only by looking at the vertices of $D$.

In contrast, if we have a $k-path$ instance $<G,k>$ (asking whether a simple path of length $k$ exists in $G$), and I give you a tuple $P$ of $k$ vertices, you can verify that $P$ is a k-path by reading merely $k$ bits of the adjacency table.

In general, assume you have some graph problem that includes a parameter$L\subset \mathcal{G}\times \mathbb{N}$, whose witness is a set of $k$ vertices/edges ($k$ is the parameter of the problem).

Now we can define the set of problems which are "easy" to verify as:

$EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in $poly(k)$ time$\}$, i.e. independent of $|V|,|E|$.

It seems, for example, that $EasyVer \not\subset FPT$ and $FPT \not\subset EasyVer$, as

$VC\in FPT, VC \notin EasyVer$.
$Clique\in EasyVer$, while Clique is $W[1]-hard$.

Does my definition even make sense?
Are there known complexity classes with similar meaning?
Any other complexity relations to known classes?
Does it makes more sense to define $EasyVer$ in terms of the number of bits a verification algorithm needs to read from the adjacency matrix?
Does generalizing the definition to $Ver_{f(n,k)}=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in time $O(f(|G|,k))$ $\}$ makes sense?


texts: Complexity of computing logarithm of a prime power

texts:
Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important to note that the prime is unknown. The input is just a number $n$.

It seems that there exists [1] an algorithm for computing $k$ when $n$ is a power of an arbitrary integer (not necessarily a prime) that runs in $O(\log n \log^c \log n)$ time for some $c$. Is there a better algorithm for prime powers?

[1]: Bernstein, Lenstra, and Pila. Detecting Perfect powers by factoring into coprimes, 2006.


texts: Can complexities differ w.r.t. different computational models?

texts:
I understand that a decision problem can be decidable with respect to certain computational models. For instance, the question whether an arbitrary sequence of parenthesis is balanced is undecidable for finite state automata and decidable for pushdown automata.

Does something similar hold for the complexity of problems? For instance, are there problems that are in $\mathbf{P}$ with respect to one computational model, but are in $\mathbf{EXPTIME} \setminus \mathbf{P}$ with respect to a strictly weaker one?


texts: Classes containing boolean closure of CFLs

texts:
So I asked a similar question on MathOverflow, but I now realize I asked the wrong question and asked it in the wrong place.

Anyway, I'm searching for a class of languages containing the boolean closure of CFLs that has a 'pumping-type' condition on it. What I've found so far are:

MCFGs (multiple context-free languages), which have a nice pumping lemma and contain CFLs (though it's not obvious if they contain the boolean closure of CFLs, since they're not boolean-closed themselves),
ET0L languages (which contain CFLs, have a 'pumping-type' lemma, and are (full) AFLs themselves--but I don't think they necessarily contain the boolean closure of CFLs),
Mildly CSLs (which apparently have pumping-type lemmas?),
Indexed languages (which have a 'shrinking' lemma), etc.

Now, I'm certainly no specialist in formal language theory, so I don't know too much about these classes. Anyway, does such a class exist, and, if so, where can I find papers/etc. on it?


texts: How to deal with concept classes with exponential value of VC dimension

texts:
Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how computational learning community handle the learnability of $C$.

One thing I am thinking about is investigating the learnability of $C$ in active learning. Hoping that I will end up with less number of examples required.

However, I prefer to stick with the passive learning for now and wondered what else I can do for this poor $C$? As I am new to the field, I also wish to have some examples of concept classes with exponential VC dimension.