texts: Maintaining multiple field dynamic values

texts:
This question is posted on behalf of my friend, who is a networks engineer handling massive data (so not a toy problem). He needs to maintain a lookup/insertion/deletion structure storing nodes with multiple attributes. That is, there is a set of $k$ global properties, or key/value fields, where each node may maintain only a subset of them. E.g, $A$ is ($x=1$), $B$ is ($x=1$,$y=4$), $C$ is ($x=1$,$z=5$), where $x$, $y$, and $z$ are attributes. There should be no repetition of nodes, although one may be a subset of another in it's filled values. For example, here node $A$ is a subset of $B$.

The structure would initially be constructed from a large amount of nodes "on disk" (let us call this parameter $n$) in preprocessing and then would go in live query mode. Whenever a new query $Q$ comes in, the query $Q$ will also have between 1 to $k$ of the key/value pairs filled. The structure has to specify ALL matching nodes of the structure (e.g, $A(x=1)$, $B(y=4)$, $C(x=1,y=4)$ all would match $Q(x=1,y=4)$) and if $Q$ does not already exist in the structure, it has to be inserted. Given a query node, $Q$, a matching node $M$ is defined to be such that it's filled key-value pairs are a superset of those of $Q$

Which data structure would produce such a result in optimal insertion/lookup/deletion time, and of course, linear storage? Both amortized and worst case guarantees would be interesting, since this structure will handle a large number of queries. A link to relevant papers or literature would also help.

I thought about posting this on stackoverflow, but in this case the engineer is looking for a sound algorithm, not code, and preferably with theoretical performance guarantees. Apologies if it is fairly trivial for someone well-versed in data structures.


texts: Simulating quantum measurements by unitaries

texts:
I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [KW00] for instance:

  Often we will describe quantum circuits in a high-level manner that suggests that measurements are performed at various times as the circuits are applied to some collection of qubits. In fact, as all of our circuits are assumed to be unitary, such measurements do not occur, but rather are assumed to be simulated by unitary gates as described in [AKN98].

I have read [AKN98] but it points to other papers (lemmas 1 and 4). It seems to be a standard result in quantum computing that just requires to add ancilla qubits. Could someone explain how it's done?


texts: Reference for the fact that (0=1) implies false requires a universe in MLTT

texts:
It's a fairly well-known fact that deriving a contradiction from a disequality (for example, $(0=1) \to \bot$) in Martin-Loef type theory requires a universe.

The proof is also fairly straightforward -- in the absence of universes, we can erase the dependencies from any dependent type to get a simple type as its shape, and so proving that $(0=1) \to \bot$ implies we can prove $p \to \bot$ for an arbitrary atom $p$, which is of course not possible.

However, I can't find who proved this first! Does anyone have a reference?


texts: Formula size lower bounds for AC0 functions

texts:
Question:

  What is the best known formula size lower bound for an explicit function in AC0? Is there an explicit function with an $\Omega(n^2)$ lower bound?

Background:

Like most lower bounds, formula size lower bounds are hard to come by. I am interested in formula size lower bounds over the standard universal gate set {AND, OR, NOT}.

The best known formula size lower bound for an explicit function over this gate set is $\Omega(n^{3-o(1)})$ for a function defined by Andreev. This bound was shown by Håstad, improving Andreev's lower bound of $\Omega(n^{2.5-o(1)})$.
Another explicit lower bound is Khrapchenko's $\Omega(n^2)$ lower bound for the parity function.

However, these two functions are not in AC0. I'm wondering if we know an explicit function in AC0 with a quadratic (or better) lower bound. The best bound I am aware of is the $\Omega(n^2/\log n)$ lower bound for the Element Distinctness function, as shown by Nechiporuk. Note that the element distinctness function is in AC0, so I'm looking for a lower bound for an explicit AC0 function that is better than $\Omega(n^2/\log n)$, preferably $\Omega(n^2)$.

Further reading:

An excellent resource on the topic is "Boolean Function Complexity: Advances and Frontiers" by Stasys Jukna. A draft of the book is available for free on his website.


texts: Can we efficiently convert from NFA to smallest equivalent DFA?

texts:
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.

Conversion Problem: NFA to smallest equivalent DFA
Input: A nondeterministic finite automaton $A$.
Output: A smallest possible deterministic finite automaton $B$ such that $L(A) = L(B)$.

We can solve this problem by converting from NFA to DFA using the powerset construction and then minimizing the resulting DFA.  However, this seems inefficient.
In particular, it seems that this could run for $O(2^{sc(L)})$ time where $L = L(A)$ if the powerset construction gives us a suboptimal DFA.

Question: Is there an algorithm for this problem that runs in linear time in terms of the state complexity?  By this, I mean that it runs in $O(n + sc(L))$ time where $n$ is the size of $A$ and $L = L(A)$?  What about $poly(n + sc(L))$ time?


texts: What are some "must-read" papers for someone getting into Quantum Cryptography?

texts:
I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography.
I'm interested in Quantum Cryptography and would like to know what people would consider the most important papers for me to read if I want to get an intro to QC, for someone of my background. Any help would be much appreciated.


texts: What's a good advanced textbook/resource for studying the complexity of counting and combinatorics?

texts: I'm taking a class in enumerative combinatorics. The professor focusses on the complexity of solving combinatorics problems like partitions etc. I'm using Enumerative Combinatorics but it does not talk about complexity. What's a good book/website/resource that touches on enumerative (or even extremal) combinatorics and complexity of counting?


texts: Bounding the gap between quantum and deterministic query complexity

texts:
Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, they only apply to certain partial functions. If the partial functions have some special structures then they are also polynomially related with $D(f) = O(Q(f)^9))$. However, I am mostly concerned about total functions.

In a classic paper it was shown that $D(f)$ is bounded by $O(Q(f)^6)$ for total functions, $O(Q(f)^4)$ for monotone total functions, and $O(Q(f)^2)$ for symmetric total functions. However, no greater than quadratic separations are known for these sort of functions (this separation is achieved by $OR$ for example). As far as I understand, most people conjecture that for total functions we have $D(f) = O(Q(f)^2)$. Under what conditions has this conjecture been proven (apart from symmetric functions)? What is the best current bounds on decision-tree complexity in terms of quantum query complexity for total functions?


texts: Dimentionality Reduction for Lp-Normed Spaces

texts:
Are there any dimensionality reduction techniques known for the general $\ell_{p}$-normed spaces for $\ell \geq 1$?
In the Euclidean space, there is a classical result: Johnson-Lindenstrass lemma that can map any $n$ points to $O(\log n)$ dimensional space while preserving the pairwise distances up to a factor of  $(1+\epsilon)$ factor. From the lower bound perspective, the $\log n$ bound on the dimension is also tight (see this).
Are there similar upper or lower bound results known for the general $\ell_{p}$-normed spaces? Thanks.


texts: Automatic theorem prover for first-order logic versus model checker

texts: What's the formal difference between a model checker, and an automated theorem prover for first-order logic, i.e. something like Meson/Metis/Sledgehammer/Vampire/E? Link to a clear discussion of the difference is preferred.


texts: What games best represent well-known computer science problems?

texts: I heard that Clue is a board game that is related to the NP-complete traveling salesman problem.   What are other games that relate to important computational problems?


texts: Neural Networks: what's the point of learning features that don't linearly separate?

texts:
Unless I'm mistaken, deep neural networks are good for learning functions that are nonlinear in the input.

In such cases, the input set is linearly inseparable, so the optimisation problem that results from the approximation problem is not convex, so it cannot be globally optimised with local optimization. Support Vector Machines (try to) get around this by choosing features such that the projection of the input space into the feature space is linearly separable, and we have a convex optimisation problem once again.

I don't suppose that a deep neural network always learns features that make the input set linearly separable in feature space. So what's the point in it learning features?


texts: Knowing if there are two solutions to the subset sum problem

texts:
I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are at least two or more solutions.
My thought is that potentially it is FNP, because the Another Solution Problem (ASP) for Subset Sum appears to be FNP (by reduction from 3SAT), but ASP assumes that at least one solution was already found. Is there a way to say something about the hardness of finding two solutions without prefacing that one was already found?


texts: Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?

texts:
At http://www.dharwadker.org/tevet/isomorphism/, there is a presentation of an algorithm for determining if two graphs are isomorphic. Given a number of shall we say, "interesting" claims by A Dharwadker, I am not inclined to believe it.

In my investigation, I find that the algorithm will definitely produce the correct answer and tell you that two graphs are not isomorphic when in fact that is correct. However, it is not clear that the algorithm will consistently tell you if two graphs are isomorphic when they actually are. The "proof" of their result leaves something to be desired.

However, I am not aware of a counter-example. Before I start writing software to test out the algorithm, I thought I would see if anyone was already aware of a counter-example.

Someone requested a synopsis of the algorithm. I will do what I can here, but to really understand it, you should visit http://www.dharwadker.org/tevet/isomorphism/.

There are two phases to the algorithm: A "signature" phase and a sorting phase. The first "signature" phase (this is my term for their process; they call it generating the "sign matrix") effectively sorts vertices into different equivalence classes. The second phase first orders vertices according to their equivalence class, and then applies a sort procedure within equivalence classes to establish an isomorphism between the two graphs. Interestingly, they do not claim to establish a canonical form for the graphs - instead, one graph is used as a kind of template for the second.

The signature phase is actually quite interesting, and I would not do it justice here by attempting to paraphrase it. If you want further details, I recommend following the link to examine his signature phase. The generated "sign matrix" certainly retains all information about the original graph and then establishes a bit more information. After collecting the signatures, they ignore the original matrix since the signatures contain the entire information about the original matrix. Suffice to say that the signature performs some operation that applies to each edge related to the vertex and then they collects the multiset of elements for a vertex to establish an equivalence class for the vertex.

The second phase - the sort phase - is the part that is dubious. In particular, I would expect that if their process worked, then the algorithm developed by Anna Lubiw for providing a "Doubly Lexical Ordering of Matrices" (See: http://dl.acm.org/citation.cfm?id=22189) would also work to define a canonical form for a graph.

To be fair, I do not entirely understand their sort process, though I think they do a reasonable job of describing it. (I just have not worked through all the details). In other words, I may be missing something. However, it is unclear how this process can do much more than accidentally find an isomorphism. Sure, they will probably find it with high probability, but not with a guarantee. If the two graphs are non-isomorphic, the sort process will never find it, and the process correctly rejects the graphs.


texts:
What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem?

I asked a similar question four years ago, but I expect the answer to be different.

To give a concrete example, consider End-Of-The-Line in a grid (known to be PPAD-complete); here a digraph $G_n$ on $2^n\times 2^n$, with arcs going only between some neighboring grid-points, is encoded by a machine, such that $(0,0)$ has no in-neighbor and only one out-neighbor, and our goal is to find another vertex of odd degree. We make a CFLPAD problem from it as follows. Fix a PDA. On any input $(x,y)$ of length $n$, the PDA should return the in- and out-neighbors of the grid-vertex $(x,y)$ of $G_n$. So how hard is it to find another odd vertex (with the PDA and $n$ as input)?


texts: I would like to find a free software (running under Windows 8) which could simulate every single step of Process Algebras of the most general form as given in the Handbook of Process Algebras and some of decidable questions about decidable problems about them. I.e. esp. I do not want that it would be limited to linear time, colored,finite-state or otherwise restricted class of them from the very beginning. I understand that many questions will be undecidable, but I still want to design my own model in this generality and simulate it step by step.


texts:
I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them  give an $\epsilon$-approximation sketch of the input data. However, for the later case we know a characterization i.e. if a range space has finite VC dimension, then it can be approximated by a small (constant) size sample. On the other hand, for the case of $\epsilon$-coreset (similar to the concept of VC dimension)  is there any characterization known over the problems which can or cannot be sketched by a small size sample?

Thanks,


texts: Soft decoding of linear block (20,10) codes - what methods are used ?

texts:
What  algorithms are advised for soft-decoding of linear block codes (20,10) ?
What are advised references ?

Sincerely Yours Alex

PS

By soft-decoding - I mean that   input  - is set of 20 real numbers (r_1, ... r_20)
and I want to find the codeword which is most close in the Eucledian metric
to this vector. I can do brute force full search of all 2^10 codewords and find the nearest one - to get the answer. But I am interested in some speeding up the process.
I've heard several methods, but advises are highly welcome.

PSPS
My code is over F_2, e.g.  0,1, not the other Galois field


texts: Descriptive complexity of communication complexity classes

texts:
It is well known that some major complexity classes, like P or NP, admit a full logical characterization (e.g NP = existential 2nd order logic by Fagin's theorem). On the other hand, one can also define complexity classes in communication complexity (where P = problems solvable with poly(logN) communication etc. - see Complexity classes in communication complexity theory for more).

My question is - are any descriptive complexity characterizations known for communication complexity classes (or do any such results from standard complexity classes transfer to communication setting easily)?


texts: What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?

texts:
Let $L$ be a language and $f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\star$ a function on two parameters with the property that for all $x$ and $y$, $f$ returns an element of $L$ if and only if both $x$ and $y$ are elements of $L$:

$$f(x,y)\in L \iff x\in L\wedge y\in L .$$

Question Do such functions have a name in the literature?

Following are some amusing observations. These functions, which I will call "conjunctive reductions", can be constructed for the complete problems of a variety of complexity classes. For example, for $L=SAT$, take the function $f(\psi, \phi)=\psi\wedge\phi$. Analogously, we may consider "disjunctive reductions", so that $g(\psi,\phi)=\psi\vee\phi$ is a disjunctive reduction over $SAT$. These two reductions work fine over quantified boolean formulas too, so they also work for all levels of the polynomial hierarchy and for PSPACE.

It is easy to construct both conjunctive and disjunctive reductions for the L and NL-Complete languages DSTCON and USTCON: Given two graphs, $G, H$ and two pairs of vertices, $(u,v), (x,y)$, construct a new graph by taking the disjoint union $G\cup H$, add two nodes $s,t$ and add edges $(s,u),(v,x),(y,t)$. A disjunctive reduction puts these two graphs in parallel, rather than in series.

A conjunctive reduction exists for Graph Isomorphism, but no disjunctive reduction obviously exists. Conversely, a disjunctive reduction exists for the Nontrivial Graph Automorphism problem, but I could not find a conjunctive reduction. This surprised me, because I thought these problems were on some level the same, and then I had learned something new about graph isomorphism!

As an obvious last step, one may consider "conjugate reductions", functions such that $f(x)\in L \iff x \not\in L$. Finding such a reduction for Graph Isomorphism would show that it is in coNP. I could find neither a conjunctive, nor a disjunctive, nor a conjugate reduction for the decision version of Factoring.


texts: NP-Completeness of the decision problem for the generalized 15-puzzle

texts:
I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block).

Now the generalization would be to extend the size of the puzzle from 15 to $p \times q$, where one field is free. I have created a small illustration (the dashed arrows show permitted moves and the lower configuration shows the solved puzzle):

Given an initial configuration of a puzzle, I ask myself the following question:

  Decision question: Given a puzzle of size $p \times q$, and a number $k \in \mathbb{N}$. Is there a sequence of $k$ or less allowed moves
  that transform the puzzle into the solved configuration?

I already did some investigation and found the article "The $(n^2−1)$-puzzle and related relocation problems" from 1990, which shows that deciding my question for $p=q$ is NP-Complete and therefore that deciding my question is NP-Complete (as the general algorithm could also decide the question for symmetric fields).

The question that remains open is if the decision problem is also NP-Complete for fixed $q>1$. I am particularily interested in the special cases $q=2,3$. It also remains open if allowing more free spaces than one field makes the decision problem harder or easier.

All the articles I could find sadly omit the asymmetric case, thus I think there might be no known results about this. As the proof in the article is quite complicated and doesn't translate at all for fixed height, I rather hope that someone might come up with a different reduction/article that answers some of the questions.

Other related articles (to be extended):

http://larc.unt.edu/ian/pubs/saml.pdf
http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf
http://erikdemaine.org/papers/AlgGameTheory_GONC3/


texts:
When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used?

My understanding is that most problems use unit-cost RAM, but some (such as integer multiplication) use log-cost RAM, and for some others it depends on the author.

Unit-cost appears simpler to map to commonly used algorithms (hence its popularity), while log-cost RAM appears more accurate as a true measure of compute.

For log-cost RAM, it appears there is a standard up to linear time equivalence.

For unit-cost RAM, there are different possibilities (in order of decreasing model power):
a. (naive) unlimited word size with multiplication
b. unlimited word size (with addition but not multiplication)
c. log-limited word size (with different conventions)
d. pointer machines (also called storage modification machines; this is a natural model but appears more restrictive than unit-cost RAM).

I think the convention is (c), but even here we have different choices.  A sensible choice for $\mathrm{TimeSpace}(t, s \, \mathrm{cells})$ with $s≤t$ is to have cells $0..O(s)$ each storing a number $0..(s+\mathrm{inputlength})^{O(1)}$, with $\mathrm{Time}(O(t)) = \mathrm{TimeSpace}(O(t), O(t) \, \mathrm{cells})$ (assuming $t$ is above the input length; I am not sure if using $t^{O(1)}$ cells gives an equivalent model).  However, I do not know whether this is the standard, whether there are other subtleties, or if the unit-cost RAM is undefined for algorithms using more than polynomial space.


texts: 1-way Quantum Finite Automata Example Question

texts:
I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be useful). This example provides a very stripped down example of a 1-QFA with the following transition rules:

$V_a|q_0\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle$,

$V_a|q_1\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle$,

$V_{\$}|q_0\rangle = |q_{rej}\rangle$,

$V_{\$}|q_1\rangle = |q_{acc}\rangle$

For instance, if I'm in $q_0$ and I process an $a$ as input, I apply the first rule. My understanding is that I would have a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of staying in state $|q_0\rangle$, a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of progressing to state $|q_1\rangle$ and a $||\frac{1}{\sqrt 2}||^2 = \frac{1}{2}$ chance of ending the computation and rejecting the string.

I would imagine the automata for this to look like the following image

I'm not entirely sure if that is correct however. The probabilities mentioned in the paper for acceptance of the string $aa$ is $\frac{1}{4}$ while the probability of rejection is $\frac{3}{4}$. Just wondering if someone could either point out a flaw or validate what I have conceptually in mind for the example.

Thanks.

Reworked automata model to more accurately reflect the probabilities:


texts:
Suppose X_1, ..., X_k are iid standard Gaussian variables, for some k > 1.

Then, what is the distribution of X := X_1 * ... * X_k ? Can it be approximated by a Gaussian, maybe for large k ?


texts: a polynomial representation of boolean functions

texts:
I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) mappings and their application.

For three variables, the transformation matrix is given below:

I have posted this with some details and a description for reducing 3-SAT to checking the existence of specific term in an ordinary polynomial product on math.stackexchange (here). I have not got much feedback there. I was wondering if someone here could help.

If this is not the right forum to ask this sort of questions, or more details are needed, please let me know in comments.

EDIT: I found similarities to Zhegalkin polynomials and the $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ -1,1 \right \}$ representation described here with the difference that this is a $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ 0,1 \right \}$ representation.


texts: Size of Formulas with no negative sign for Matrix Permanent

texts: What is the best lower bound for algebraic formulas for Permanent of a matrix given that the formulas have no negative sign? Is there an exponential lower bound known for such formulas and what would be a good reference on the topic?


texts: $\ell_1$ norm of Fourier coefficients vector for the hypercube

texts:
Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$.

Given a function $f:[-1,1] \rightarrow[0,1]$, we can define for every $a \in \{0,1\}^d$ the Fourier coefficient
$$\hat{h}_a = \sum_{r \in \{0,1\}^d}f\left(1-2\frac{|r|}{d}\right)(-1)^{\left<r,a\right>}$$
Now, let $v$ be the vector of size $2^d$ so that $v_i = \hat{h}_i$ for $i \in \{0,1\}^d$.

I am looking for an upper-bound on $\frac{1}{2^{d}}\|v\|_1$ in terms of $f$.

Thank you very much for your help.


texts: Length of a minimal DNF Boolean expression

texts: Consider an disjunctive normal form boolean expression on $n$ variables. What is the upper bound on the number of terms in a minimal equivalent DNF expression? That is, given an arbitrary DNF expression on $n$ variables, after eliminating redundant terms, what length is it guaranteed to be under (how many $\vee$'s)?


texts: Is $\mathsf{NP^{PP}} = \mathsf{P^{PP}}$? Or, more generally, Is $\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}$?


texts: Emptiness of PDA without constructing the corresponding CFG

texts:
The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs.

Therefore, given a PDA, the straightforward way to decide whether the language it accepts is empty is to convert the PDA into a CFG and then use the known algorithm to decide emptiness of the corresponding CFG.

I am wondering whether there exists some algorithm to directly check emptiness of the language of the PDA without going through the conversion to a context free grammar.


texts:
I am reading about the Bloom filter, and I must say I am fascinated by the idea. I would like to know if it is possible to use it for storage.

The problem with the Bloom filter is that, even if we accept that there will be false positives, the set of elements that we need to scan to see which ones are present may be very large (assuming that such set is finite). I would like to know if there is a smart way to reduce the complexity of such problems, namely, the complexity associated to the task of finding which elements are currently stored in the Bloom filter (of course with error due to false positives, if any).

Is there any techniques in the literature that I can look at to reduce the complexity of such task?


texts: What are the obstructions to extending $L=SL$ to $L=NL$?

texts:
Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an expander graph from the original graph, and then do the walk in the expander graph. The expander graph is made by squaring the original graph logarithmically many times. In the expander graph, the diameter is only logarithmic, so a DFS search of logarithmic depth suffices.

Extending the result to $L=NL$ would imply the existence of a logspace algorithm for DSTCON -- the same, but for Directed graphs. (Sometimes just STCON.) My question, maybe slightly soft, is what are the primary obstructions to extending Reingold's proof to that?

It feels slightly like there should be a sort of "directed expander" graph. A similar sort of construction, where you add in edges corresponding to medium-length directed paths, and then some corresponding to long ones; and then you can traverse the graph with logarithmic depth by moving across short paths to get to a long one; then back to short paths at the end.

Is there a major flaw in this concept? Or is it that there aren't any good constructions of such expanders? Or does it somehow require more memory than the undirected version?

I unfortunately cannot find much at all on directed expander graphs. In fact essentially all I could find was https://math.stackexchange.com/questions/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (which is unanswered) and https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . Is there a different term I should be searching under?


texts: Optimal polynomial time algorithm to determine if a random graph is $k$-colorable

texts:
Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $k$-colorable. That is, $G(n, d/n)$ is $k$-colorable with high probability if $d  < d_{k-col}$ and not $k$-colorable with high probability if $d  > d_{k-col}$.

However, if $G(n, d/n)$ is indeed $k$-colorable, it is not clear if it can be colored in polynomial time. I was wondering what is the best known polynomial algorithm to color a random graph.

In addition, are their any hardness result about determining whether $G(n, d/n)$ is $k$-colorable in polynomial time? Will the threshold be different from $d_{k-col}$?


texts: The average number of annual publications for CS postdocs

texts: What is the average number of publications (including conference proceedings), per year, for CS postdoctoral researchers in the US? What are the ways to find out or estimate this number?


texts: PTAS for a variant of multiple knapsack?

texts:
I am interested in the following variant of multiple knapsack. There are $n$ items with values $v_1,\ldots,v_n$. We want to partition the items into $m$ subsets $S_1,\ldots,S_m$ to maximize $\min_{j\in\{1,\ldots,m\}}\sum_{i\in S_j} v_i$. In words, we want to assign the items to $m$ bins to maximize the minimum total value in any bin.

The problem is clearly NP-hard even for the case of two bins; it is essentially the PARTITION problem. However, SUBSET-SUM has an FPTAS and many generalizations of SUBSET-SUM and KNAPSACK have a PTAS; there are so many of them, though... Is there a generalization of these problems that is known to have a PTAS and captures my problem? (On the other hand, the problem is a special case of the Santa Claus problem [Bansal and Sviridenko, STOC'06], which seems to be quite hard to approximate.)


texts: Hyperplanes not intersecting points on a cube

texts:
Consider the set of points in $\mathbb{R}^n$ with coordinates in $\{-1, 0, 1\}$. Find a hyperplane passing through the origin that contains no points in the set besides the origin.

This is simple if we don't give any constraints on the hyperplane. Even if define the hyperplane by a normal vector in $\mathbb{Z}^n$, it is simple. However, what if we require every coordinate of the normal vector to be an integer bounded in absolute value by some polynomial in $n$? Does such a hyperplane exist?


texts: Computational complexity of some recursive property

texts:
I am currently working on a property of graphs defined as follows. A graph $G$ is said to be OL-AP iff one of the following two conditions holds:

$G$ is an isolated vertex.
$G$ is connected and for every $x \in [1,|V(G)|-1]$ there exists a subset $V_x$ of $V(G)$ with size $x$ such that $G[V_x]$ is connected and $G-V_x$ is OL-AP.

Basically, we would like to take some connected parts off a graph whatever their sizes are without disconnecting it. The recursive aspect of this definition should be obvious. One can refer to this article for some more details.

I have been trying to characterize the complexity of computing this property, but I could not get anything because of the recursivity arising from the definition.

On the one hand, to show that computing this property is in $NP$, I would naively give, as a certificate showing that a graph is OL-AP, a connected part for every possible size of each level. I mean that if my graph has order $n$, I would give the first parts of size $1, ..., n-1$ as well as those of the induced subgraphs, and so on. But I do not think that such a certificate as a polynomial size.

On the other hand, a witness to show that the property is in $co-NP$ would be to give a size $x$ such that we cannot take a connected part with this size off the graph in such a way that the remaining graph is OL-AP. But how the algorithm could check whether a subgraph is OL-AP since this is the property I am dealing with? If such an algorith exists, then dealing with my property would be pointless.

I think that such a problem is in a higher level of the polynomial hierarchy, but I cannot find where because of its recursive aspect. So, any idea or comment is welcomed :) .

Thanks in advance!


texts: Set Cover with bounded intersection size

texts:
So, the set cover problem is trivial if none of the candidate sets intersect eachother.

However, what if the size of the intersection for any pair of candidate sets was at most 1? Is this problem NP-hard?

I would appreciate any insight.

Thanks,
Garrett


texts: Terminology for languages of pairs of words

texts:
I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this?
I wrote "double language" first (but that doesn't sound right to me), then "square language" (but languages can be squared in various ways), then "pair language" (maybe ok?), or just "language". The issue with just "language" is that it doesn't convey that there's a sort of "type hierarchy" of languages, which would be useful for me (just informally that is, don't read too much into the word "type", I barely know what it means). Eventually I figured maybe someone has already called this something and I should use the same.
My paper is in symbolic dynamics (or something like that), where I think no term is fixed for this. I am sure I have seen such "languages" in the theory of formal languages, in automata theory, and in combinatorics on words, but I can't really put my finger on any specific reference where they play a prominent role.
You can also just give your expert (or other) suggestion.


texts: Is there a fast algorithm for computing the Schmidt decomposition

texts:
I have a huge covariance matrix, , with the dimension, e.g., $10^8 \times 10^8$. Luckily enough, the number of nonzero eigenpairs, $n$, is very small, i.e., $n<5$. From the computational prospective, I would like to represent, $M$, in Schmidt decompsition as
$$
= \sum_{i=1}^n \lambda_i {\bf e}_i^T \otimes {\bf e}_i,
$$
where $\lambda_i$ and ${\bf e}_i$ are the nonzero eigenvalues and eigenvectors of $M$. This equation can be further written as
$$
= \sum_{i=1}^n {\bf g}_i^T \otimes {\bf g}_i,
$$
where the vectors ${\bf g}_i=\sqrt{\lambda_i}{\bf e}_i$. Using this relation, the matrix, $M$, can be stored in terms of nonzero ${\bf g}_i$ in computer.
My problem is that the matrix, , is changing at every time snapshot. The update of the matrix, , is given by the following formular,
$$
′= \sum_{i=1}^n {\bf g}_i^T \otimes ({\bf g}_i+ \delta {\bf g}_i)+({\bf g}_i+ \delta {\bf g}_i)^T \otimes {\bf g}_i
$$
where $\delta {\bf g}_i$ is the update of the $i$th vector and is small comparing with ${\bf g}_i$. Due to some dynamical properties/constraints, the updated covariance matrix, $M'$, contains the same number of nonzero eigenpairs, $n$.
I wonder whether there is a fast algorithm for computing the new nonzero eigenpairs?
Many thanks in advance!


texts: What are the differences between logical relations and simulations?

texts:
I'm a beginner working on methods proving program equivalence. I've read a few papers about defining logical relations or simulations to prove two programs are equivalent. But I am quite confused about these two techniques.

I only know logical relations are inductively defined while simulations are based on coinduction. Why are they defined in such ways? What are their pros and cons respectively? Which one should I choose in different situations?


texts:
[Note 2020-02-08: I updated the definition of nihilistic types so that it relies less on the type Empty.]

A discussion on Twitter prompted the following question, which I have never seen considered before.

Definition: Say that a type T is inhabited if there exists a closed term of type T, and  empty otherwise.

We assume that there is an empty type, or else the rest of the question is not very interesting. For instance, we might have the type Empty which is in fact empty.

Definition: Say that a type T is nihilistic if every closed term t of type T contains a subexpression of an empty type.

I think (but have not thought carefully) that a type is nihilistic if and only if every normalized closed terms contains a subexpression of an empty type.

Clearly, every empty type is nihilistic.

  Question: Which inhabited types are nihilistic, if any?

For example Empty → Empty seems like a good candidate for a nihilistic type.


texts: Minimizing SubModular Function: Cardinality

texts:
Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and  such that f(S) is minimized.

When the size constraint is |S| >=k, the problem is NP-hard.  What is known about when the constraint is |S| <= k?


texts: Variant of set cover problem with symmetric difference instead of union?

texts:
I am wondering if this problem has been studied, and in particular if there is an algorithm for it.

Consider a universe $\mathcal U$ and a set $A \subseteq U$, and a family of sets $\mathcal F \subset 2^{\mathcal U}$. We know that
$$\mathcal U = \bigcup_{F \in \mathcal F} F.$$

I want to find a minimal set $\mathcal E \subseteq \mathcal F$ such that
$$A = \triangle_{E \in \mathcal E} E$$
where $\triangle_{E \in \mathcal E} E$ means the symmetric difference of all the sets in $\mathcal E$.

The set family $\mathcal F$ is not closed under symmetric difference, but we know that for any $B \subseteq \mathcal U$, there exists a $\mathcal F' \subseteq \mathcal F$ such that
$$B = \triangle_{F \in \mathcal F'} F,$$
so the problem is solvable.

I think the decision problem should be NP-hard.

Edit: The links in Kristoffer Arnsfelt Hansen's comments show that the problem of finding the smallest subset expressible as a symmetric difference of the subsets in $\mathbb F$ is NP-complete. This problem is somewhat different, and I am still looking for an algorithm.


texts: Is equivalence of uniform AC0 decidable?

texts:
Is there a representation of the functions from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ for which equivalence is decidable?

Since the languages defined by nondeterministic pushdown automata belong to $\mathsf{LogCFL}$, and we know that their equivalence is not decidable, we know that there can be no representation of the functions from $\mathsf{LogCFL}$ for which equivalence would be decidable. Since $\mathsf{AC}^0$ is nearly the most powerful class which we still can separate from $\mathsf{LogCFL}$, learning that equivalence of $\mathsf{AC}^0$ is decidable should have no surprising consequences (at least I expect that if equivalence of $\mathsf{TC}^0$ were known to be decidable, then we could separate $\mathsf{TC}^0$ from $\mathsf{LogCFL}$).

Edit: Emil's comment hints that the answer is "no", but that this question did not define what it means by "representation" rigorously enough to allow any definite answer at all. Let me first try to guess why the answer is "no": Since length is $\mathsf{DLogTime}$ computable, it is probably possible to pad the input at will, by writting the padded length in binary at the beginning, and hence reducing the equivalence problem for  $\mathsf{CFL}$ to the equivalence problem for  $\mathsf{DLogTime}$.

Given the paragraph about $\mathsf{LogCFL}$ above, one should expect that this question interprets "representation" in a way that is compatible with that conclusion. But that is not the case. (But making my guess about padding the input rigorous would nevertheless answer this question.) It assumes that "representation" simply has its intuitive meaning. So we have strings over some alphabet, we can computationally decide whether a string is "valid", every language from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ is represented by some "valid" string, and given a "valid" string, it is possible to computationally enumerate the language represented by that string.


texts:
Could anybody suggest practically important distances that are significantly non-metric and are not Bregman divergences? For instance, they are non-symmetric and not equivalent to the Euclidean distance.

Thanks!


texts:
To prove a protocol secure in the computational model, one can use game-based approach or the simulation approach (I just assume these two models for simplicity).

In the game based approach, the security of the mentioned protocol is verified through some games between parties or between parties and algorithms (oracles). This approach usually gives us a lower bound on the communication effort for the protocol.
The second approach is through an ideal functionality or a trusted third party which acts as a paradigm for what we seek from meaning of security when running that protocol. This is usually called 'the Ideal/Real Paradigm'. In this approach a $\mathcal{PPT}$ (probabilistic polynomial time) machine which we call it 'the simulator' is responsible for generating the interaction between parties while running the protocol such that no other $\mathcal{PPT}$ machine (called distinguisher) can have any advantage greater than 0.5 to distinguish between the real interaction and the simulator made interaction. In this way we have proven the protocol secure by just comparing it to what is ideal when defining security of that protocol.

In the Ideal/Real paradigm, when proving a protocol secure some times the simulator must use some special  types of primitives. For example, when facing an adaptive adversary (fully capable adversary), we may use non-committing encryption or trapdoor permutation or some other forms of equivocal primitives to provide the same view as the real world.

  Question: What does it mean to use a equivocal primitive? What is the practical point of that? Do we use these primitives in practice?  can you name some?

As a side note, I found some good issues on this in the response of Damgard to Koblitz Controversy. [I just noticed that this forum is Theoretical Computer Science, but I have asked something practical]

Edit: I may explain more on the non-committing encryption here to clarify my question. Let start an example; In a secure multi-party computation, the best way of communication is through secure channels. A secure channel by definition is the one in which the full-fledged adversary which controls the whole communications cannot see the messages. What does is it mean not to see the communication where all communications are visible to adversary and actually if she decides to put an end to a conversation, she can do it easily by dropping messages. The point is, informally when a non-committing encryption is used over a channel it makes the channel a secure channel because every permutation of an encrypted message is possible now. Remember that a non-committing encryption is the one in which a receiver can open a ciphertext bit to "0" or "1" as he wishes. As a naive example, consider one-time-pad and suppose your ciphertext is, say, 111; One can open it to every permutation of 3 bits length. So when this kind of ciphertext is at hand, the adversary can infer nothing out of it and it is equivalent to not receiving such a ciphertext at all.


texts:
(I was redirected from mathoverflow in asking this)

Hello,
I'm trying to determine if the following problem is solvable in polynomial time:  given a collection of $n$ half-open intervals $[s_i, t_i)$ having integer endpoints, is it possible, for given integers $k$ and $L$, to find a subset $S$ of these intervals that are "exactly" covered with $k$ half-open intervals of length $L$, with each of these $k$ "covering intervals" only covering one of the given intervals at any particular instant?  Put another way, by William Thurston, "given a finite set of half-open intervals, is there a subset of them so the sum of their characteristic functions can be expressed as a sum of characteristic functions of intervals of length $L$"?

For example, given the four intervals $[0,3), [2,4), [3, 6), [3, 8)$ with $k=2$ and $L=4$, we find that $[0,3)$, $[2,4)$, and $[3,6)$ can be exactly covered by the two intervals $[0,4)$ and $[2,6)$.  I hope I've stated this clearly.  One thing I've tried is a reduction via the subset-sum problem, but the fact that I'm dealing with intervals complicates it in a way I'm not comfortable with.  Thanks!

A clarification about "only covering one of the given intervals at any particular instant":  what I mean is that, for example, the interval $[0,5]$ could be said to cover either $(0,3)$ or $(0,4)$, but not both simultaneously.


texts: Major mistakes in accepted FOCS/STOC papers

texts: Have you come across an occasion like that in the past? Well, there is a possibility for everything but I would like to know how realistic this incidence can be. I am referring to serious mistakes altering the target of the paper and not minor mistakes, of course. Thanks


texts: What is known about learning a maximal independent set in a (very) sparse graph?

texts:
Maximal independent set is known to be hard in many meanings (hard to approximate, $W[1]$-hard, etc.). But if the number of edges is very small, then the problem becomes simpler. Here, I'm interested in learning an independent set from an unknown graph.
Assume that we have an unknown sparse graph $G=(V,E)$ with at most $k\ll |V|$ edges ($k$ is given).
We want to find a maximal independent set for the graph using as few queries as possible, where Query$(S)$, for some $S\subseteq V$ returns 1 if $S$ is an independent set and $0$ otherwise.
For example, if $k=1$, we can find an independent set of size $n-1$ using $\Theta(\log n)$ queries.

What is the query complexity for general $k$?
If I want to learn the exact graph (rather than just a maximal independent set), is the query complexity similar?

For $k=1$ we can also find the edge using $\Theta(\log n)$ queries.
The run time of the algorithm here can be arbitrary, all I care about is the query complexity.


texts:
Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges.  Choose some subset of $n\leq V$  "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we can get $O(1)$ reachability queries between any two special nodes $v_i$ and $v_j$?

For $n = V$, this is just the usual reachability problem. I want to focus on the case where $n \ll V$. Using $n$ depth-first searches starting at the special vertices, it is straightforward to obtain an $O(nE)$-time algorithm. Can this be beaten? What if we relax to $O(\log n)$, $O(n)$, or $O(\log V)$ query time?

EDIT (May 3, 2011). One comment points out that bounds like $O(nE/V^\alpha)$, $\alpha > 0$ imply sub-cubic matrix multiplication bounds. On the other hand, a bound like $O(\max(n^2 V, E))$ for the restricted reachability problem would not imply a sub-cubic method, yet would still be quite useful for $n \ll E / V$.


texts: Kolmogorov Complexity vs Running Time (Edited)

texts:
Let $U$ be a universal Turing Machine. Suppose I have a Kolmogorov incompressible string $s$ of length $n$. Let $A:\{1,...,n\} \to \{0,1\}$ be an algorithm such that $A(i) = s_i$.

I believe that the time it takes for the universal Turing machine to evaluate $A$ on input $i$ should be $\Theta(n)$. I'm not familiar with Kolmogorov complexity, and I wanted to ask if the following intuition is correct

An upper bound on the running time of $A$ is $O(n)$, since the description of $A$ can just list the whole string $s$ and return $s_i$ on input $i$. The universal Turing machine on inputs $(A,i)$ simply reads the description of $A$ (Which is $O(n)$ in length) and outputs the $i^{th}$ coordinate (which takes time $\log n$)
A lower bound on the running time of $A$ can be proved as follows.

a. The description length of $A$ must be at least $n - log n - c$ for a constant $c > 0$. This is because the program $B$: "Run $A$ on every input from $1$ to $n$" has description length $DL(B) = DL(A) + log(n) + c$ and generates the string $s$. Thus $DL(B) \geq n$ and $DL(A) \geq n- \log(n) - c$.

b. The universal Turing machine $U$ on input $(A,i)$ needs to read both $A$ and $i$, which requires at least $DL(A) + \log n \geq n-c$ operations.

Is this intuition correct? Or am I missing something big about Kolmogorov complexity?


texts:
I wanted to know as to how often are the submissions for ECCC cleared? Or do we know when is the next set of uploads going to be made on that site? Unlike arxiv where I know when my paper will go online, on ECCC there seems to be no way to know what is the timeline of my article. Last time I had submitted something on ECCC it took about 3 days for it go online. This time I am wondering as to why its taking longer. (..I had gone by this previous experience of 3 days to plan that I would refer to this online index number as reference for an upcoming talk of mine but now it seems I can't do that because the timeline looks indeterminate..)

If this is off-topic I will remove this. I guess people can just comment here rather than write "answers" so that I can eventually remove this question.


texts:
This question considers a special class of problems in (NP,P-samplable). The question is:

Do there exists a problem $(L,\mu) \in \mbox{(NP,P-samplable)}$ such that:

$L$ is $\rm{NP}$-complete, and
$L$ is hard on instances sampled by $\mu$; That is, for any $\rm{BPP}$ algorithm $A$, any polynomial $p(\cdot)$, and any all sufficiently large $n$:
$\Pr_{x \leftarrow \mu(1^n)}[A(1^n,x) = \chi_L(x)] < 1/p(n)$. (Here, $\chi_L(\cdot)$ denotes the characteristic function of $L$.)

Your answer can be based on any reasonable assumption, like:

$\rm{P} \ne \rm{NP}$;
one-way functions (or permutations) exist;
factoring is hard;
etc.

Another question is based on the following quote from On Basing One-Way Functions on NP-Hardness:
More than two decades ago, Brassard ("Relativized Cryptography") observed that the inverting task associated with a one-way permutation cannot be NP-hard, unless NP = coNP.

Is my understanding correct: It is saying that, there does not exist polynomial-time-computable permutations whose inverting is worst-case NP-hard and hard-on-average (unless NP = coNP)?


texts:
Can someone recommend a reference on graph minors structure theorem and sublinear treewidth?  Doesn't have to be the newest/strongest results as long as it's easier than tracking down all the papers written about these results.
Mostly I'm interested in finding the details about the existence of large grid minors in large treewidth planar and minor free graphs and sublinear treewidth of planar and minor free graphs from basic graph theory.


texts: Optimal sort algorithm in number of swaps

texts: Given a sequence of $n$ numbers, can it be sorted with $O(n \ln n)$ comparisons and $O(n)$ swaps/moves? Any pointer to publications on that matter or counterarguments showing a $\Omega(n \ln n)$ lower bound would help.


texts: How hard is the Circuit Isomorphism problem?

texts: Given two circuits, how hard is it to tell if they represent the same function? Clearly, this must be at least as easy as Graph Isomorphism since you can represent any circuit as a graph.


texts: What's the strict definition of random coins in streaming algorithm?

texts:
I have a very basic question about random bits in streaming. How could a streaming algorithm use them? Can the algorithm use the same random bit at the start of the execution and look at it again later? Or it serves a random source that once you look at it, you will get a random bit?

Sometimes it makes difference on the space when the algorithm have to store the random bits in memory and look at it later. Or, are they just equivalent?


texts: What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

texts:
JBV suggested I turn some comments into a question, so here goes.

Another question [1] asks about applications of QM computing. One answer [2] was "efficiently simulating quantum mechanics". Apparently this idea dates all the way back to Feynman's early writing on subject; although I dont have a reference. So:

  Question. What is the proof that a quantum computer can efficiently simulate an arbitrary quantum mechanical system?

On one level this seems basic. However, this does not seem to be trivial for following reason: most quantum computing literature seems to reduce to operations on gates acting on two particles or other small subsystems. (Yes, Toffoli gates act on 3 inputs, but anyway are often reduced to two-qubit CNOT gates.)

There is surely no question, due to Turing completeness, that a quantum computer can simulate arbitrary classical or even quantum physics (although maybe there are some naysayers there due to the uncertainty principle etcetera — I  would be curious to hear about that too). But it seems to me that to simulate arbitary quantum physics efficiently one at least needs a way to simulate arbitrary n-way interactions in mostly/nearly 2-way gates.

One could argue that we can build arbitary n-way gates, but the clear evidence after many years of experimental research is that even just 2-way gates are extremely hard to build, and that n-way gates would surely be much harder. (There are some 3-way quantum experiments, e.g. 3 particle bell inequalities, but they are difficult to build.)

[1]
Real world applications of quantum computing (except for security)

[2] https://cstheory.stackexchange.com/a/10241/248


texts: Hardness result or reference for a set partition problem

texts:
I'm wondering if the following problem is (or has been proven to be) NP-Complete.

  Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.

  Accept iff: there exists $\{a_i,b_i\},i=1,2,\ldots,n$ such that $\{a_1,\ldots,a_n,b_1,\ldots,b_n\}=\{1,2,\ldots,2n\}$ and $S_{a_i}\cup S_{b_i}=T_i,S_{a_i}\cap S_{b_i}=\emptyset$.

That is, we want to partition $\{S_i\}$ as $n$ group of two sets, and the $i$-th group exactly covers $T_i$.

Towards algorithm, we can construct a colored graph with vertex set $\{v_1,\ldots,v_{2n}\}$ and $v_i,v_j$ is connected with color $k$ iff $S_i\cup S_j=T_k,S_i\cap S_j=\emptyset$. Then the problem asks for a perfect matching of distinct color.

I suspect the problem was considered before; or there is some other problem closely related. But all I can find is the comment in this problem.


texts: Partitioning graphs while minimizing inter-partition edges

texts:
I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been partitioned into 4 "clusters":

What I wanted originally was an algorithm that could create partitions of approximately k triangles (there could be some error as long it wasn't too large), and I managed to figure out a $O(k^2p^2(v+e))$ algorithm (where p is the total number of partitions) that could find such a partitioning. I then realized that having large numbers of inter-partition edges were detrimental for the application I needed this algorithm for.

Ideally, I'd like an algorithm that can keep each partition within some range of $k$, ideally have it be a constant factor like 2. Also, I'd like to be able to make the number of inter-edges have an upper bound that is "low".

Additionally, another problem I have is if I have a partition that has these properties, and I modify the graph by doing one of the following:

Adding a set of edges connecting to existing vertices
Adding a vertex and a set of edges connecting to the added vertex
Removing a set of edges
Removing a vertex and all edges that connect to this vertex

I want to be able to repartition the graph and still have each partition with size $k$ and number of cut edges minimized. (This is the solution I'm putting up a bounty for). This means that using this algorithm, we can construct any partition by starting with an empty graph and adding vertices and edges one by one and repartitioning.

Here's some additional constraints to the problem:

The graph is planar
Each "triangle" is a vertex that has undirected edges to triangles it shares an edge with
From the above statement, it is obvious that each vertex in this graph has degree at most 3
The graph is connected
Each subgraph from the partition is connected
Each subgraph has approximately k vertices
There are at most $\sqrt n$ inter-partition edges (edges that contain a vertices from different partitions). If you can find a similar bound for inter-partition edges like $2\sqrt n$ or $O(\log n)$ then that could work too. I'm not entirely sure the upper bound for inter-partition edges can be less than $O(n)$ so if you can prove that its impossible to do better, that is satisfying as well.

I'm at a point where I'm stuck, so any help with this problem would be lovely. If you can flat out solve this problem, you're the bees knees. Otherwise, if you know of any papers or textbooks or algorithms you could point me to, I'd appreciate it very much.

Let me know if I need to clarify anything!

EDIT: Here are some additional constraints if it makes the problem easier.

We are dealing with constrained delaunay triangulations
Constraints will NEVER be a single vertex
The graph created from the triangulation is constructed as follows: each triangle is represented as a vertex. Each edge in the graph corresponds to an unconstrained edge in the triangulation. This means that a constrained edge between two triangles will not show up in the graph representation of the triangulation.

Another thing I realized is that we may need to modify $k$ to grow as $n$ grows, otherwise there can be no sub $O(n)$ guarantees on the number of inter-partition edges.


texts: Scoring set of points based on clustering

texts:
I have a sparse set of points with unpredictable locations. I need a way of "scoring" each set of points such that clustering is rewarded. My working case is actually one dimensional, but a two dimensional use case may come up later.

Here's an example:
Data A contains points at -2, 1, 5, 7. Data B has points at -10, 0, 20, 6. A and B are independent of each other and have not had clustering applied. Ideally, after clustering, A would have clusters (-2, 1) and (5, 7). There is more clustering in A so I would like it scored higher. Bonus points if the algorithm allows the points to have variable values so that in some cases, if points are 100 units apart but each of the points has a high value, that set of points will rate higher than a set of points 10 units apart with much lower values.

EDIT: My current idea is to use a clustering algorithm to figure out the center of each cluster and it figure out which points occupy the cluster. I would then score each cluster finding the mean of the distances squared (EDIT: Apparently this is called "variance.").


texts: Assessing complexity of a language using subset relations

texts:
What makes a language hard in a computational sense is neither simply that it contains very few words(e.g. is finite) or that it contains a lot of words(e.g. is infinte) but rather an intricate selection of a subset of $\Sigma^*$.

I would try to formalize this intuition as the following statement:

Let $A,B$ be two languages which are complete w.r.t to some class $\mathcal{C}$. Then for every language $C$ it holds that
$$ A \subseteq C \subseteq B \implies C \text{ is complete w.r.t $\mathcal{C}$} $$

What can we say about the truth value of this statement or interesting special cases such as NP. Maybe it implies only lower bounds(hardness)?
I would be rather suprised if even the lower bounds of $A$ and $B$ don't apply to $C$.

One natural example to explore might be HAMCIRC and HAMPATH. If the hypotheses holds then we could state that any set of graphs $G$ for which every element has a hampath and every graph with a hamcirc is contained in it, it follows that $G$ is NP-complete.


texts: Algorithm to find a polyhedral embedding

texts:
A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge, or do not intersect at all.

I need an algorithm that, given a graph, finds a polyhedral embedding if the graph admits it. I have been looking around but haven't found it. I also need to know the time order of the algorithm.

Deciding whether a graph admits a polyhedral embedding is NP-complete (proved here: B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf). I don't expect an efficient algorithm, just something that works.

Note: I should mention that I am only interested in the combinatorial aspect of this problem. An embedding of a graph can be described by specifying the cyclic orderings of the edges incident on any vertex, and a signature for each edge, which is +1 or -1 according to whether the cyclic orderings of the two vertices on this edge are consistent along this edge. A face-walk is a walk in the graph where at all vertices the next edge is the leftmost edge according to the cyclic ordering on the vertex. A polyhedral embedding is an embedding where all the face-walks are simple cycles. The problem is then to find a circular ordering of edges around each edge and a signature for each edge such that all face-walks are simple cycles.


texts: If the set of factors of an infinite word $\xi$ is regular, is this property stable under "shift's" of $\xi$?

texts:
Let $\xi$ be an infinite binary sequence, and denote by $T(\xi)$ the set of all factors (infixes) of $\xi$. Also if $w$ is some finite prefix of $\xi$, denote by $\xi/w$ the unique $\eta$ such that $w \cdot \eta = \xi$, i.e. the tail of $\xi$ after deleting the prefix $w$. Is it possible that for $\xi$ we have two prefixes $u,v$ of $\xi$ such that
$T(\xi/u)$ is regular, but $T(\xi/v)$ is not regular?

Closely related to this question is, if $w \in X^*$ and $\xi$ is an infinite sequence, is $T(w\cdot \xi)$ regular if $T(\xi)$ is regular, and if $w$ is a prefix, does $T(\xi)$ regular imply that $T(\xi/w)$ is regular?

EDIT: I guess I have a proof that if $T(\xi)$ is regular, then $T(\xi/w)$ is regular too, but this is somewhat contrary to what Yuval Filmus wrote, so I would be grateful if someone would point out to me what might be wrong with my proof??

Okay, we introduce the notation $L / v := \{ u : vu \in L \}$ for $L \subseteq X^*$, the so called (right) quotient or derivative of $L$. First note that if $v$ is a prefix of $\xi$ then
$$
 T(\xi/v) = T(T(\xi)/v).
$$

  Proof: If $w \in T(\xi/v)$ then we have $vxw\eta = \xi$ for some $x \in X^*$. So $vxw \in T(\xi)$ or $xw \in T(\xi) / v$, which shows $w \in T(T(\xi)/v)$. For the other inclusion let $w \in T(T(\xi)/v))$, then $xwy \in T(\xi)/v$ for some $x,y \in X^*$, and by definition $vxwy \in T(\xi)$. If $vxwy$ is a prefix of $\xi$, then $xwy$ is a prefix of $\xi/v$ and we have $xwy \in T(\xi)/v$ and hence $w \in T(\xi)/v$. If $vxwy$
  is not a prefix of $\xi$, then the part $xwy$ must occur in $\xi/v$, as it begins behind the $|v|$-th position in $\xi$, hence $xwy \in T(\xi)/v$ and so $w \in T(\xi)/v$.

Okay, now the proof that $T(\xi)$ regular implies $T(\xi/w)$ is regular.

  Proof: I use that if $L$ is regular, then its set of factors $T(L)$ is also regular (I guess this is true). Then if $T(\xi)$ is regular, then $T(\xi)/w$ is regular if $w$ is a prefix of $\xi$ as regular languages are closed under quotients (this could be found in many textbooks). Taken together
  $$
 T(\xi/w) = T(T(\xi)/w)
$$
  is regular, as it is the set of factors of the regular language $T(\xi)/w$. QED


texts: Complexity of finding the leading eigenvector of a graph Laplacian

texts:
Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$?

Are there any families of Laplacians for which it takes almost linear time?


texts: Are there more polynomial time problems with complexity lower bounds?

texts:
I'm looking for more problems in $P$ with classical time complexity lower bounds.  Some people might wonder how you could prove such a lower bound.  See below.

Exponential Lower Bounds:

Claim: If you have a problem $X$ that is $EXPTIME$-complete under polynomial reductions, then there is a constant $\alpha \in \mathbb{R}$ such that $X$ is not solvable in $O(2^{n^{\alpha}})$ time.

Proof Idea: By the time hierarchy theorem, there is a problem $Y$ in $O(2^n)$ time that is not in $o(\frac{2^n}{n})$ time.  Further, there must be a polynomial reduction from $Y$ to $X$.  Therefore, there is a constant $c$ such that this reduction takes an instance of size $n$ for $Y$ to an instance of size $n^c$ for $X$.  The lower bound for $Y$ of $O(2^{n^{1-\epsilon}})$ time shifts to a lower bound for $X$ of $O(2^{n^{\frac{1-\epsilon}{c}}})$ time.

Polynomial Lower Bounds:

Some $EXPTIME$-complete problems have nice parameterizations into polynomial time problems.  Consider the problem $X$ from before.  Suppose we have a parameterization $k$-$X$ for $X$ such that:

For each fixed $k$, $k$-$X$ is in polynomial time.

There are of course exceptions to this, but intuitively, as $k$ grows the $k$-$X$ problems should get harder because $X$ has an exponential time complexity lower bound.

An Example:

One example problem that has come up is intersection non-emptiness for tree automata.  That is, given a finite list of tree automata, does there exist a tree that simultaneously satisfies all of the automata?

This problem was shown to be $EXPTIME$-complete here.  Further, we can parameterize the intersection problem by the number of automata $k$.  It can be shown that for fixed $k$, the intersection problem has time complexity $n^{\Theta(k)}$.

Question:

Are there any other $EXPTIME$-complete problems that have natural parameterizations into polynomial time problems with nice lower bounds?


texts: Minimal number of hyperplanes needed to separate sets of points from one other set

texts:
Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$.

We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. This means that there exist a hyperplane separating $g$ and $b$ (which we can find  in poly time with linear programming). We could repeatedly cut our space, eliminating one $b$ at a time, and be left with a subspace that only contains $g$ from our initial sets - this is what we want.

But we can do (a lot) better - we could separate multiple $b \in B$ from $g$ simultaneously with a single hyperplane. Is there an efficient algorithm that finds the minimal number of hyperplanes needed (and the partition of $B$ into groups you eliminate simultaneously)?


texts: Hardness of approximating chromatic number of triangle-free graphs

texts:
The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs.

Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?


texts: A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching

texts:
The question is asked first at here. It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness.

Problem: Given a graph $G(V,E)$, Find a subset of edges $M \subseteq E$. For each edge $(u,v) \in M$ , $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$ holds, where $c=3$. $d(u)$ means degree in $M$, i.e., $d(u)=|(u,v) \in M|$. We call this constraint a degree-constraint.
Output: The maximum sized (cardinality of edges) $M$.

The problem on $c=2$ is already $NP-complete$ as shown by Jukka Suomela. There is a $2-approximation$ algorithm for a general graph already.  Jukka devised a $O(|V|c)$ DP for this problem when $G$ is restricted on trees.


texts:
I'm trying to classify the following problem:

  I have $N$ empty boxes ($n_i$ is the volume of the $i$-th box, $1 \leq i \leq N$) and $M$ divisible items ($m_j$ is the volume of $j$-th item, $1 \leq j \leq M$). The total volume of all boxes is exactly equal to the total volume of all items. I need to find a distribution of items among boxes which minimizes the number of item divisions.

I suppose this problem is NP-complete, and is some kind of set coverage problem, but I can't find appropriate variation of it.


texts: Approximating and bounding Ramsey numbers

texts:
Calculating the diagonal Ramsey numbers R(s,s) is hard. There is a famous quote from Joel Spencer:

  Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.

However, calculating some bounds on Ramsey numbers is not as difficult:

$$
 (1 + o(1)) \frac{\sqrt{2} s}{e} 2^{s/2} \leq R(s,s) \leq s^{-c \log s/\log \log s} 4^{s}
$$

My question is:

  What are the best possible lower and upper bounds on the diagonal Ramsey numbers that can be calculated in polynomial time (where $s$ is given in unary)?

Or more generally, are there any inapproximation results on Ramsey numbers?


texts: Are space and time hierarchies even comparable?

texts:
I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such that $L_1 \in \DeclareMathOperator{TIME}{TIME} \TIME(f(n))\setminus SPACE(g(n)),L_2\in \DeclareMathOperator{SPACE}{SPACE} \SPACE(g(n)) \setminus \TIME(f(n))$? How often does this occur?

P.S.- The question Function with space-depending computation time seems to ask something similar but was worded confusingly and none of the answers seem to be what I'm looking for.


texts: "Almost all objects have property P" vs. "It is easy to test whether an object has property P"

texts:
I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable".

My guess is that they are completely separate (that is, one doesn't imply the other). Am I missing something?

(Note: Almost all in the sense of probability)

PS: I am not sure whether the tag probability is appropriate here, sorry.


texts: State of the art algorithms for community detection in graphs

texts: Is anyone aware of the must read papers to get knowledge of the most recent algorithms and method for community detection in graphs, especially those that represent social networks?


texts: Partitioning a connected polygon into connected pieces of equal area

texts:
Armaselu and Daescu (TCS, 2015) present algorithms that, given a convex polygon $P$ and an integer $m$ (which  must be a power of $2$), return a partition of $P$ into $m$ convex polygons with the same area and same perimeter.
If we only want the area to be equal (and do not care about perimeter), then the problem becomes easy for any $m$: move a "knife" (a straight line) over $P$ from left to right, and make a cut whenever the area covered by the knife is $1/m$. Since $P$ is convex, the resulting pieces are convex too.
But what if $P$ is not convex? Then, cutting $P$ by a knife might generate pieces that are not convex and even not connected.
What is an algorithm for partitioning a polygon (that is connected but not necessarily convex) into $m$ connected polygons?
My guess is that the problem should be much easier for hole-free polygons. But even for this case, I could not find an algorithm.


texts:
I want to run $k$ programs distributed on $N$ machines. Because of resource constraints, a machine can have at most $p$ of the $k$ programs installed. To have a balanced system, I can install each of the $k$ programs on the same number of machines, that part is easy.

My problem is how can I do that while minimizing the number of machines having any 2 programs installed. In other words, if I run 2 of those programs, I want to avoid having them run on the same set of machines while some other machines in the cluster are doing nothing.

In terms of sets, the questions becomes how to find $k$ subsets of a set of $N$ elements such that

any element is in $p$ subsets and
the maximum size of the intersection of any 2 subsets is minimized.

Any pointers / heuristic approach is appreciated.


texts:
Manuel Blum is a well-known theoretical computer scientist and a Turing award winner. But more interestingly, he has the highest number of students who have gone on to win a Turing award (Leonard Adleman, Shafi Goldwasser, Silvio Micali) in the whole computer science. The list of his students is amazing and even more so if we include the students of his students.

Can anyone comment on Manuel's supervisory style? What makes him so successful in training exceptional researchers? Anything that can help other supervisors be more successful in training exceptional researchers?


texts: What are the most known database disk storage layout algorithms?

texts:
I can list for example algorithms used in databases:

append only b-trees (MVCC like used in CouchDB)
merged logs (like used in Big Table, Hbase, Cassandra)
paged storages grouped in extents (like in InnoDB engine of MySQL)
fractal trees (like used in TokuDB engine of MySQL)

Are there any others? similar or totaly different?


texts: find the most similar topological ordering of a dag

texts:
Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$.
Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $L$?
(The most similar is that the least number of elements' positions are changed.)
Note: the topological order means the $n$ elements should be placed according to the constraints in $G$.


texts: Trees: complexity of counting the number of vertex covers

texts: Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?


texts: What is the relationship between intuitionistic logic, combinatory logic and lambda calculus?

texts:
I've been reading Lectures on the Curry-Howard Isomorphism and it talks about intuitionistic/constructive logic (IL) , combinatory logic (CL) and lambda calculus ($\lambda$c) before moving on to the Curry-Howard correspondence.

In fact, almost every text I've come across when trying to understand the "history and theory of functional programming", I've almost found these 3 topics interlinked. However, I'm unable to grasp how exactly are they connected?

From what I understand, IL predates CL which predates $\lambda$c.I believe $\lambda$c incorporates the principles of IL and CL in some form but I can't seem to put a finger on it. It seems this some form has something to do with Curry-Howard Isomorphism (CHI), but I'm unable to find a "non-abstract" example that relates everything together. Most texts have proofs with letters A, B, C and the like and it takes a while to figure out exactly what's going on.

So, how are they related? If its CHI, then what's a good example to hit the point home, intuitively speaking? Perhaps a constructive example for the proof of CHI could be helpful.


texts: What is the counting complexity of random 2-SAT?

texts:
Has any work been done on how the complexity of random instances of #2-SAT varies with the clause density? That is: how does the difficulty of counting satisfying solutions to a randomly generated instance of 2-SAT vary, as the clause density varies? In particular, are there any rigorous results known involving critical thresholds?

Of course, because  2-SAT ∈ P, the typical counting complexity depends partly on the probability with which an instance is satisfiable; instances whose clause density is above the critical threshold for SAT/UNSAT will typically have an easy counting complexity, as the answer is "zero" almost surely, in the limit n $\to \infty$. However, the counting complexity may still be easy for instances of 2-SAT having a density near to or just above the critical threshold for finite n: one might expect that a satisfiable instance will have only a small number of solutions, which might be easy to enumerate due to the tightness of the constraints.

For k-SAT with k ≥ 3, the difficulty of determining whether an instance is satisfiable or unsatisfiable  seems to be highest near the critical thresholds separating the SAT phase from the UNSAT phase, in part as one tries to determine whether there exists at least one satisfying solution. For #2-SAT, the difficulty cannot lie in determining whether at least one solution exists; so one should expect that the difficulty is likely to be in determining the number of solutions for satisfiable formulae of a significant but not large number of constraints — that is, where there are enough constraints to induce non-trivial dependencies between variables, but not so many as to over-determine the possible assignments.


texts: Which algorithms can be used to measure similarity for two very different languages?

texts:
recently I have read this paper, A Survey of text similarity approaches, and I discovered that there are a lot of algorithms that can be used to measure similarity.

At present I am applying the method of soft similarity (link to the paper: Soft similarity and soft cosine):

  "Our idea is more general: we propose to modify the
  manner of calculation of similarity in Vector Space Model
  taking into account similarity of features. If we apply
  this idea to the cosine measure, then the “soft cosine
  measure” is introduced, as opposed to traditional “hard
  cosine”, which ignores similarity of features. Note that
  when we consider similarity of each pair of features, it
  is equivalent to introducing new features in the VSM.
  Essentially, we have a matrix of similarity between pairs
  of features and all these features represent new dimensions in the VSM. [...] The next question is how to measure similarity between features. In general, the measuring of similarity
  depends on the nature of the features. In our case,
  we compare features using the Levenshtein distance [6],
  taking advantage of the fact that they are usually strings
  in case of natural language processing"

I am working on vectors trying to align Language1 and the same language in leet form. My question here is: are there any other distance measures that I can test a part from the here mentioned Levenshtein distance and the cosine distance? and why should I prefer one from another?


texts: Layman Interpretation: Quantum Factoring Algorithm

texts:
I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media.

So, I'm hoping that somebody will be able to help me to correct my understanding of quantum computing.

My understanding is as follows:

a qubit acts as though it is in both states at once (1 and 0)
a register of n qubits can act as though it is in any of $2^n$ states.
this has obvious benefits in terms of a factoring algorithm: we can identify whether any of these states is a 'correct' solution to a problem.
however, I understand that although we can identify whether or not there is a correct state, we can not necessarily observe the state which is correct

So, my assumption up to now has been that we can 'pin' one or more of the qubits by replacing with a classical bit, and observe whether or not the remaining set of states still contain a correct solution. (Simple!)

My problem is that this would seem to lead to a solution to the factoring problem in $O(log n)$ time, by passing down and pinning each of the bits. I haven't proved that out but it feels right, based on my assumptions.

However, Shor's algorithm takes $O((logn)^3)$ and doesn't seem that simple. I'd like to know which of my assumptions are wrong, but Wikipedia's description of Shor's algorithm seems intractable to me.

Can you help identify my misconception? Which of my points of understanding are correct/incorrect?
Thanks!


texts:
Why are the candidates for one-way functions so few?

Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!).

Why one can not generate several candidates by using advanced mathematics, for example using complex structures of combinatorics?


texts: Is generalized pigeonhole search known to be no harder than PPP?

texts:
Consider the TFNP search problem

  Given a positive integer $t$ in unary, positive integers $M$ and $N$ (in binary), and a

  function from $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}M\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}M\hspace{-0.04 in}-\hspace{-0.05 in}1\hspace{-0.02 in}\}$ to $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}N\hspace{-0.05 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}N\hspace{-0.05 in}-\hspace{-0.05 in}1\hspace{-0.02 in}\}$ (as a circuit),

  find $\: \operatorname{min}(t,\hspace{-0.04 in}\lceil M/N\hspace{.02 in}\rceil) \:$ distinct inputs that map to the same output.

.

That problem is clearly hard for the class PPP. $\:$ Is that problem known to be in PPP?


texts: Regular language that discriminates between two deterministic CFGs

texts:
Suppose you are given two deterministic push down automata which recognize languages $A$ and $B$, and wish to determine whether there is a regular language $R$ such that $A \subseteq R$ and $R \cap B = \emptyset$. Basically, the challenge is to determine whether there is a DFA that can recognize which of the two languages any given string comes from, given that it comes from one of those languages.

Is this decideable? If so, what is the complexity? Can the DFA be constructed explicitly?


texts:
I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$.
In particular, I would like to be able to solve the problem of finding all the point within a ball of center p and radius n without exploring all the points of $E$.

First remark that it depends of the choice of the distance: it is much more easier for the Chebyshev distance since a simple b-tree over each coordinates would be sufficient.
Also remark that I would be happy if finding those points is FPT with the $d$ (dimension) as a parameter.

I guess it is well-known-well-studied problem, but I didn't find anything after a (rather short) bibliographical search?

Best,


texts: Complexity of finding the mean of the subset with smallest variance

texts:
Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer.
Let's consider the following problem
$\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\right) \|x_i - \mu \|_2^2$
where: $F:[0, 1] \rightarrow R$ is the $\alpha$-threshold, i.e. $F(z) = 1$ is $z \le \alpha$ and $F(z) = 0$ otherwise; and $\pi$ is the ascending permutation of the $i$s based on the values of $\|x_i-\mu\|_2^2$.
I guess one way to reformulate the problem is the following: find the mean of the size-$\alpha n$ subset of  elements with the smallest variance.
I'm not an expert and I'm wondering if this problem is $NP$-hard. For $d=1$ it admits a simple polinomial time algorithm, but in the general case, I suspect it doesn't.


texts: Restoring symmetry in certain combinatorial bijections?

texts:
I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an $n$-vertex forest, and $f$ is a labeling of its nodes from $1$ to $n$. We say that:

$\cal{F}$ is standard if $f$ is bijective,
$\cal{F}$ is sorted if the numbering is increasing along each root-to-leaf path,
$\cal{F}$ is subexcedant if for each node $u$, $f(u)$ is at most the number of nodes of the subtree rooted at $u$.

Let $T_n,O_n,U_n$ denote the sets arising from these three cases, for a fixed size $n$. It is not too difficult to show the existence of a bijection $Sort_n : T_n \rightarrow O_n \times U_n$, which implies a well-known 'hook length' formula due to Knuth. One unpleasant aspect of this bijection lies in its assymetry: we would like to get a pair of similar objects in order to get extra symmetry properties (e.g. what would happen if we switch the two objects and then apply the reverse bijection?)

Therefore, I'm asking naively if you think that the symmetry could be restored by considering more general structures. I'm not optimistic on this question though: there might be a positive but difficult answer that so far eludes me. A side remark: this bijection $Sort_n$ already enjoys some interesting symmetry properties in connection with the Schützenberger involution, but we would need something stronger to get an interesting algebraic object (possibly a Hopf algebra?)


texts: Schaefer's theorem and CSPs of unbounded width

texts:
Schaefer's dichotomy theorem shows that each CSP problem over $\{0,1\}$ is either solvable in polynomial time or is NP-complete. This applies only for CSP problems of bounded width, excluding SAT and Horn-SAT, for example. General CSP problems of unbounded width may be very difficult (even uncomputable), so let's restrict ourselves to problems which are "natural" and are in NP.

Given a CSP problem of unbounded width, for each $k$, we can look at the restriction of the problem to clauses of width up to $k$. Schaefer's theorem now applies, and the restricted problem is either in P or NP-complete. If for some $k$, the $k$-restricted problem is NP-complete, then so is the unrestricted problem. The situation is less clear when for all $k$, the $k$-restricted problem is in P.

Schaefer's dichotomy theorem relies on four (or so) different algorithms that solve all the easy cases. Suppose that for a given CSP problem, the $k$-restricted problem is always solvable by algorithm A. It might be the case that algorithm A can be used to solve the unrestricted problem as well. Or it might be that algorithm A isn't polynomial time in the unrestricted case, and then we're ignorant as to the hardness of the problem.

Has this kind of problem been considered? Are there examples in which we arrive at the "ignorant" spot?


texts:
I know that BPP is in P/poly.

I know that if NP is in P/poly then $PH = \Sigma^2_p$

Question:

Is there a good survey on the power of non-uniformity? I'm basically looking for a list of known results about non-uniformity.

Thanks!


texts: Expected value in case of Langevin dynamics

texts:
Let $U(\beta) = \exp(-f(\beta))$ where $f$ is $m$ strongly convex and $L$ Lipschitz smooth. I am trying to find an upper bound on $E[\|\beta_t \|^2]$ where $\beta_t \in \mathcal{R}^p$ is defined below
\begin{align*}
d\beta_t = -\nabla U(\beta_t) dt + dW_t
\end{align*}
In the above equation, $W_t$ is a standard $p$ dimensional Brownian motion. We also know $\beta_0 \sim N(0,\lambda I)$, so $E[\|\beta_0 \|^2] = p\lambda$ and $\beta_{\infty} \sim N(\mu,\Sigma)$. I think we will have to use Gronwall's inequality to find an upper bound, but I am not sure.


texts:
I may have a very naive question on Constraint Based Analysis. (a technique of static program analysis).

I am reading an informal introduction from F. Nielson

He gives such an example,

let f = fn x => x 1;
    g = fn y => y + 2;
    h = fn z => z + 3
in (f g) + (f h)

The author explained that:

  ...the problem is that we cannot immediately point to the body of x:
  we need to know what parameters f will be called with. This is exactly
  the information that the Control Flow Analysis gives us:

  For each function application, which functions may be applied.

However, in my naive point of view, this information can be obtained statically and exactly, at least seen from this example. It suffices to check the "in-" part of the instruction "let...in..." to decide the functions that may be applied, doesn't it??
Although I do see in OO programming, it would not be evident to decide what the virtual calls really calls at run-time, I find from this above example that this piece of information can be obtained in a trivial way by looking at its syntax.

So where am I wrong? Thank you for your ideas.


texts:
What is the relationship between invertible primitive recursive functions (that is, a primitive recursive function that is an isomorphism) and all primitive recursive functions? Can every primitive recursive function be mimicked in some way (like Bennett’s result about reversible computation) by a reversible/invertible primitive recursive function?  Using pairing functions and Godel numbering can we look at all invertible primitive recursive functions from N to N?

Also, has anyone ever looked at the group of all invertible primitive recursive functions from N to N? Are there generators to this group? Can we talk about properties of this group? What is the relationship with its supergroup of all recursive isomorphisms? What about its relationship with the monoid of all primitive recursive functions from N to N? What about the monoid of all recursive functions from N to N?


texts: Finding min-max vertex-disjoint paths with a common source on planar graphs

texts:
Given a planar unweighted graph, and a collection of vertex pairs $(s,t_1),\dots,(s,t_k)$ ($k\ge2$ is a constant), find $k$ vertex-disjoint (except source) paths from $s$ to $t_i$ such that the length of the longest path is minimized.

Question: Is there a polynomial-time algorithm for the problem?

Some related results:

if $k$ is not fixed the problem is NP-hard even if $t_1=\dots=t_k$;
if the input graph is weighted and sources of paths do not coincide, i.e. paths are $(s_1,t_1),\dots,(s_k,t_k)$ the problem is NP-hard even for $k=2$;
a problem with different objective, namely minimizing the sum of path lengths, is

solvable with the minimum cost flow algorithm for coinciding sources;
NP-hard for non-coinciding sources and general $k$;
open for non-coinciding sources and constant $k$.


texts:
I'm looking for the complexity of satisfiability of a formula $\forall y_1, \dots,y_n, \exists x_1,\dots,x_m, \phi$ or of a formula $ \exists x_1,\dots,x_m \forall y_1, \dots,y_n,\phi$ where $\phi$ is formula of the form :
$$\phi:= \phi \wedge\phi ~| ~\neg \phi ~| ~ \phi\to \phi~| ~\psi$$
$$\psi := t>t~| ~t=t$$
$$ t:= t+t~| ~x_i~|~y_i ~| ~c$$
Where $c$ are the constant in $\mathbb{N}$, and the domain of variables $x_i,y_i$ is also $\mathbb{N}$.

In fact the $y_i$ are either $0$ or $1$. Does that simplify the complexity?

All answer with references would be gladly accepted.

Thanks


texts:
I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other subgraph of $G$.  I assume this problem is NP-hard but is there any work on it? For example, exact algorithms for sparse, planar etc. graphs or approximation algorithms or even heuristics.  Just to fix ideas, every node or edge connected pair of nodes will be isomorphic to some other subgraph so the minimum size this could ever be in a non-trivial graph would be of size $3$ nodes.

There is a very nice bibliography as of 1995 of the subgraph isomorphism problem linked from David Eppstein's publication page . Is there anything more relevant to my problem?


texts:
A set-function $f$ is monotone submodular if for all $A,B$,
$$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B). $$

A stronger property is
$$ \begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\f(A\cup B) + f(B\cup C) + f(A\cup C) + f(A \cap B \cap C). \end{multline*}$$
Taking $C = A\cup B$, this property implies monotone submodularity.

  Is this property known?

Background

This property came up while trying to characterize coverage functions. Given some weighted universe $U$ (all weights are non-negative) and a family $X$ of subsets of $U$, the coverage function $f(S)$ is defined for $S \subseteq X$ as the total weight of elements covered by sets in $S$. The function $f$ is always monotone and submodular. The converse isn't true.

The property in question implies that $f$ is a coverage function in the case $|X| = 3$. Similar, more complicated properties work for larger $X$. All these properties are satisfied by coverage functions, so this is a complete characterization.


texts: Problems with no known quantum advantage

texts:
I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer.

To start things off, I think computation of the edit distance is one for which the fastest known quantum algorithm seems to be the fastest known classical one. More tentatively, I would also suggest sorting as another problem for which there is no known quantum speedup (compared to the fastest known unit-cost word RAM algorithm).

Although I don't want to set a hard restriction, I am particularly interested in problems in NP and/or problems with no known efficient classical solution.

Following a suggestion of Juan Bermejo Vega  here is some further clarification.  I am interested in problems in NP for which there is currently no known big $O$ time complexity advantage at all if you use a quantum computer.

I am not focusing on cases where we can prove there can't be an advantage nor am I focusing on exponential speedups (i.e. polynomial would also be fine).  So far it seems the only two examples are the ones in my question which seems very surprising if it is really true.


texts: I have a set of nodes which can be connected together through arcs. Every node has an associated value, reflecting the "fitness" that this particular node has in the graph. I have to find the best graph connecting the vertices, defining best as the maximum value achievable by summing node fitness. I already have an algorithm for that, I'm only asking if this is a well-known problem or a more efficient algorithm than NP-hard does exist.


texts: Are non-deterministic tree-walking automata stronger than deterministic ones?

texts:
Update: It seems this problem has been studied and solved recently, see this wiki article: http://en.wikipedia.org/wiki/Tree_walking_automaton
And also this survey:
http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf

Suppose that instead of the usual set of words, {0,1}*, our words are not linear but rather given on some tree structure. To prevent our machines from "getting lost", define our words as the set of binary, embedded arborescences. (So every word is a tree, where every edge is directed away from a given a root that has degree two, every other non-leaf vertex has degree three, and every edge is labeled left or right such that any two edges starting from the same vertex have different labels.) A language is a set of such trees. (Note that there is no need to write zeros and ones on the vertices as they can be anyhow simulated by locally modifying the trees.) When a machine is "reading a tree", it starts from the root, it can sense if a given vertex is the root, a leaf or a degree three vertex and can decide if in the next step it wants to go to the parent of the vertex, or on the edge labeled left or right.

Is it true in this model that any language that can be recognized by a non-deterministic finite state automaton can also be recognized by a deterministic finite state automaton?

Note that when the tape is the usual linear tape, this is true, as any 2-NFA can be simulated with a 2-DFA (even with a DFA). I already asked a special instance of the problem here that was solved by Kristoffer. The motivation would be to solve this.


texts: Most important new papers in computational complexity

texts: We often hear about classic research and publications in the field of computational complexity (Turing, Cook, Karp, Hartmanis, Razborov etc). I was wondering if there are recently published papers considered seminal and a must read. By recent I mean in the last 5/10 years.


texts:
Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes.

(Note: Approximately means that each subgraph contains $\lceil \sqrt{n}\rceil$ or  $\lfloor \sqrt{n} \rfloor$ nodes and covers  $\lceil \sqrt{s}\rceil$ or
$\lfloor \sqrt{s} \rfloor$ sourses of the original graph. All sources of the original graph have to be covered by some subgraph, so there has to be $\lceil \sqrt{s}\rceil$ or                $\lfloor \sqrt{s} \rfloor$ subgraphs.)

Assume following about the graph G(V,E):

We try to solve the problem for
graphs in which such partition
exists - if the partition doesn't
exist it can be stated that it is
impossible to create partition
All the graph's node will have $\forall v \in V\ $ in_deg(v)=2 or in_deg(v)=1

Let's define the height of the DAG to be the maximum path length from some source to some sink.

The subgraphs have following requirements:

We require that all subgraphs
generated will have the same height(
max length of longest path)
Nodes of each subgraph should be
reachable from the sources within
that subgraph, using nodes of that
subgraph as intermediate nodes.
Moreover, the intersection of each
pair of node sets (of subgraphs)
must be empty.

In the following picture, you can see an example of a right partition (assume that each edge in the graph is directed upwards).

There are 36 nodes and 8 sources [#10,11,12,13,20,21,22,23] in the example. So each subgraph should have 6 nodes and 2 or 3 sources.

Do you have idea for algorithm?

Thank you very much