texts: Extracting randomness from Santha-Vazirani sources using a seed of constant length

texts:
This question is actually an exercise problem from Salil Vadhan's draft survey "Pseudorandomness" marked with a star (*) (see Chapter 6, Problem 6.6). I do not know other references.

We say a random variable $X=(X_1,X_2,\cdots,X_n)\in\{0,1\}^n$ comes from a Santha-Vazirani source if for any $0\leq i< n$ and $x_1,x_2,\cdots,x_i\in \{0,1\}$, it holds that:
$$
\delta \leq  \Pr[X_{i+1}=0\mid X_1=x_1,X_2=x_2,\cdots,X_i=x_i] \leq 1-\delta
$$
where $\delta$ is some positive constant.

It is not hard to show that any fixed deterministic extractor (an extractor without a seed) cannot extract even one bit well from some SV-source (the output may be biased with the probability distribution $(\delta, 1-\delta)$ or worse).

It is also known that a seeded extractor $\mathrm{Ext}: \{0,1\}^n\times \{0,1\}^d\to\{0,1\}^m$ exists for SV-sources such that the output is $\epsilon$-close to the uniform distribution (measured by the statistical difference) with the output length $m=\Omega(\delta n)$ and the seed length $d=O(\log(n/\epsilon))$. Actually we have explicit constructions for extracting a constant fraction of min-entropy from any source. In this question the min-entropy is $\Omega(\delta n)$.

The question is: how to extract $\Omega(\delta n)$ bits from SV-sources with a seed of length $d=d(\delta,\epsilon)$ that is independent of $n$?


texts: What is the current status of Acta Informatica?

texts:
Almost everybody knows the journal Acta Informatica. Some really important publications appeared there over the years.

Upon looking on the website of the journal I noticed the following:

  Number of days from submission of a manuscript to first decision: 15

Does this mean that this is not a peer-review journal anymore? What is the current status of the journal? Do people submit (good) work there?

I find it very hard to believe that they provide feedback after 15 days.

I understand that this is a soft question, so feel free to comment for deletion if you think it does not comply with the guidelines.

  Update: to somewhat confirm my initial and slight "suspicion", here are the average times from submission to "Final Acceptance" of a paper. According to this (American Mathematical Society) link, this average time for up to 2015, is 3.8 months for Acta Informatica, time that surely is very low for such a TCS journal and somewhat consistent with the 2016 statistics of 15 days from submission to first decision.


texts:
In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to each entry of the board, in such a way that the rules of the games are satisfied.

For instance, slitherlink,numberlink, sudoku, filomino, kakuro etc, are the types of puzzles I'm looking for.

Preferentially, the puzzles should satisfy the following conditions:

Scalability: The puzzle can be defined for $n\times n$ boards for each
$n$. Or if this is not possible, for each $f(n)$ where $f:{\bf N}\rightarrow {\bf N}$ is some
easy looking function.
An online library of instances for the puzzle should be available.

What would be online databases for such puzzles? For instance, the section Games and Puzzles of this wikipedia page has many square games satisfying condition 1. So what I'm really looking for is a of puzzles that also satisfy condition 2.

Please feel free to suggest more than one puzzle in one answer.


texts: Abstract algebra for Theoretical Computer Scientists

texts:
I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ).  I think this was partly as I needed to see applications and any that I could find were in physics, not CS.  As my interest is really CS, are there any materials available now (online drafts, lecture notes, videos, books) that cover abstract algebra from the point of view of applications in CS and in particularly algorithms/theory?  I am happy for these applications to be entirely theoretical but they shouldn't assume any pre-existing abstract algebra knowledge.

I am pretty sure that were these resources to exist, they would be appreciated by  a large number of CS researchers.


texts: Complexity of permutation related problems

texts:
Given a group $G$ of permutations on $[n]=\{1, \cdots, n\}$, and two vectors $u,v\in \Gamma^n$ where $\Gamma$ is a finite alphabet which is not quite relevant here, the question is whether there exists some $\pi\in G$ such that $\pi(u)=v$ where $\pi(u)$ means applying the permutation $\pi$ on $u$ in an expected way.

Suppose further that $G$ is given, as the input, by a finite set $S$ of generators. What's the complexity of the problem? In particular, is it in NP?


texts: dependent types and higher-order logic applied in the realm of DSLs

texts:
(this is a beginner question and English is not my first language)

I am searching for references on using theorem proves based on dependent type theory (or Martin Löf type-theory) and higher-order logic in the development of domain specific languages (DSLs).

Dependent types, i.e., Coq and Agda
Higher-Order logic, i.e., Isabelle/HOL

Currently, I am attending an course on higher-order logic for PhD students, and it seems to me there are possible applications to DSLs. As I am not so familiar with Coq so I may have overlooked some references.

I found only two references:

Oury, Nicolas, and Wouter Swierstra. "The power of Pi." ACM Sigplan Notices. Vol. 43. No. 9. ACM, 2008.

Chlipala, Adam. "Ur: statically-typed metaprogramming with type-level record computation." ACM Sigplan Notices. Vol. 45. No. 6. ACM, 2010.

Any suggestions on papers that I missed?


texts:
It is now a well known observation that many graphical structures that arise in natural settings tend to obey scale-free properties, such as the power law of degree distribution.

Are there any good example of natural graphs that are fairly random and not do not necessarily obey scale-free properties?


texts: How to find interesting research problems

texts:
Despite several years of classes,
I'm still at a loss when it comes to choosing a research topic.
I've been looking over papers from different areas and
spoken with professors, and
I'm beginning to think this is the wrong approach.

I've read that it helps to find an interesting problem (nevermind the area) and
to then work on that.
Textbooks mention famous unsolved ones but
I wouldn't want to tackle them directly.
Research papers only mentioned positive results,
not failed attempts.

How can I find interesting research problems?
How do you find interesting research problems?
Is there a list somewhere?

How do you decide if it is worth to work on a particular problem?


texts:
I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted.

My questions are: what are the definitions that best match the primary sources and the current use? Does what follows sound right?

(1) The Cheeger constant of a graph, denoted $h$ is

$h(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ |S|, |V-S| \}}$

where $\textrm{Edges}(S,V-S)$ denotes the number of (or the total weight of) edges with one endpoint in $S$ and one endpoint not in $S$.

(2) The uniform sparsest cut of a graph, denoted $\phi$ is

$\phi(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{|S| \cdot |V-S|}$

Notes:

 $h$ is also called the edge expansion of $G$
 $h$ and $|V|\cdot \phi$ are within a factor of 2, so approximating one problem is equivalent to approximating the other, up to a constant loss in the approximation ratio

(3) The conductance of a graph, unfortunately also usually denoted $\phi$. Maybe we should use $\sigma$ for the sparsest cut parameter?

$\textrm{conductance}(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ \textrm{vol}(S), \textrm{vol}(V-S) \}}$

where $\textrm{vol}(S)$ is the sum of the degrees of the vertices of $S$

Note:

 If $G$ is $d$-regular, then $\textrm{conductance}(G) = h(G)/d$. In the irregular case, the conductance is incomparable with $h$ and $\phi$

(4) Finally, as an intermediate problem to use to give relaxations of the conductance problem, I have seen the following problem, that does not seem to have a name ("volume-weighted sparsest cut"? what letter should be used to denote it?)

$\min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\textrm{vol}(S) \cdot \textrm{vol}(V-S)}$

which is $\phi/d^2$ in regular graphs, and that scaled by $\textrm{vol}(V)$ is within a factor of 2 from the conductance.


texts: Finding maximum weight arborescence in an edge-weighted DAG

texts:
Let $G$ be an edge-weighted DAG with a unique source $s$. The question is how to find out a maximum weight arborescence in $G$ rooted at $s$.

When all edge weights are positive then the required arborescence is also spanning and so we can use the directed minimum spanning tree algorithm (http://www.ce.rit.edu/~sjyeec/dmst.html)

What if negative weights are allowed?


texts:
I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem.

I have some finite set $ U $ of some distinct elements $ e_i \in U $.

I have some subsets $ A_i \subset U $, where $ i \in \{1, 2, \cdots, N\} $.

I have an array of integers $ <k_1, k_2, \cdots, k_N > $. Each integer $ k_i \leq |A_i| $ and $$ \sum_{i \in \{1, 2, \cdots, N\}} k_i \leq | \cup_{i \in \{1, 2, \cdots, N\}} A_i | $$.

I want to find sets $ B_i $, where $ i \in \{1, 2, \cdots, N\} $, such that $ |B_i| = k_i $ and $$ \forall i \in \{1, 2, \cdots, N\} .  B_i \subset A_i $$ and $$ \forall i, j \in \{1, 2, \cdots, N\} . B_i \cap B_j = \emptyset $$

The choice of actual $ B_i $ doesn't matter at all.

I'd like to find is it possible at all. It seems to me that it is, since it's obviously possible for not intersecting $ A_i $, and if they intersects we can reduce the problem to not intersecting $ A'_i $
I'd like to find fast algorithm that will not-deterministically choose any $ B_i $. I'd like to find the complexity of the problem. It seems that there should be some fast algorithm and problem doesn't seem similar to NP-hard problems, but I somehow feel that it can be NP-hard.

The actual environment is that there are around 50 000 000 elements in $ U $ and N is around 100.

Is it some known problem? Where can I read on the matter? Is there any fast algorithm? What is the best way to perform such partitioning in given environment.


texts: Can the "mutual independence" condition in the Lovász local lemma be weakened?

texts:
The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows.

  Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is mutually independent of all but at most $d$ of the $A_j$'s. Then if $ep(d+1) \leq 1$, the probability that none of the $A_i$'s occur is positive.

I have a few questions about the assumptions needed for the above lemma. Looking at the proof given in the Wikipedia article here, it appears that one does not require each $A_i$ to be mutually independent of all but at most $d$ of the $A_j$'s. Instead, all one requires is that$$\text{Prob}\left(A_i \mid \bigwedge_{j \in S} \overline{B_j} \right) = \text{Prob}(A_i),$$where $S = \{1, \ldots, k\} - \Gamma(A_i)$, where $\Gamma(A_i)$ is the dependency locus of $A_i$. I think that the above condition appears to be considerably weaker than mutual independence; indeed, mutual independence means that
$$\text{Prob}\left(A_i \wedge \bigwedge_{j \in S} \overline{B_j}\right) = \text{Prob}(A_i) \cdot \prod_{j \in S} \text{Prob}(\overline{B_j}).$$

Am I right to say that mutual independence is not required?

Also, is there a reason why the constant $e$ in the statement of the Lovász local lemma is optimal? Several sources seem to agree on this. It seems somewhat arbitrary to me, and I feel like a smaller constant can be achieved by being more careful in the proof.

Thanks in advance!


texts: Notation for drawing rooted trees with isomorphic subtrees and recursive parts

texts:
I need to specify small rooted trees with a lot of repeated parts and some recursive definitions.

To illustrate the need, let's use $s(T_1, T_2, ..., T_k)$ to denote a tree that consists of a degree-$k$ root node and $k$ subtrees: the $i$th subtree is a copy of $T_i$. Then I might want to define something like this:

$T = s(X_d, X_d, X_d, B)$

$X_{i+1} = s(X_i, X_i, X_i, X_i)$
$X_0 = s(A, B, B)$
$A = s(C, D, D)$
$B = s(D, D, D)$
$C = s(L, L, L)$
$D = s(L, L)$
$L =$ a leaf node

Well, certainly I can define it, but I would prefer to draw an illustration that defines the structure of $T$. I would prefer to keep the illustration as compact as possible, yet unambiguous (that is, the illustration alone is enough to define $T$). I would rather not name the subtrees $X_i$, $A$, $B$, ...; they could be just some anonymous nodes (?) in the illustration.

Sure, I could come up with my own notation for such illustrations, but when I tried to depict recursion I realised that using a well-known standard notation might be a better idea. Hence the question:

  What is the standard notation for drawing trees that contain recursive parts and isomorphic subtrees?

I explored ideas ranging from the Unified Modeling Language to tree grammars, but did not find anything that really answers my needs. Any ideas? Preferably something that might be already familiar to a computer scientist.


texts: Quantum annealing vs adiabatic quantum computation

texts:
I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions when it gives a solution. But this D-Wave report says as follows:

  D-Wave processors compute by piggybacking on quantum annealing. A
  quantum annealing processor can be operated as a universal quantum
  computer. In this regime of operation, the computational model is
  referred to as adiabatic quantum computation (AQC), which can be
  thought of as the long-time limit of quantum annealing.

Should I think that adiabatic quantum computation is an application of quantum annealing?


texts: It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model?  Do we have any intuition that we can beat the complexity of the Coppersmith-Winograd algorithm using quantum computers?


texts: Generating $k$ random bits from a pdf with entropy $H(p) = k$

texts:
All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it.
So can we formalize this as follows? Suppose I can only sample from my distribution, is there an algorithm or procedure to generate a uniform $k$ bit binary string?
Thanks for your help.


texts: Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?

texts: There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's simple enough to use in a first course in algorithm analysis and design. The same “level of difficulty” as the lower bound for sorting would be fine. Also, any approach (e.g., combinatorial or based on information theory) would be OK. Any suggestions?


texts: Can abstract syntax trees be unparsed in subexponential time?

texts:
Abstract problem description

The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. parse(unparse(AST)) = AST should hold.

This is the equal to finding a valid parse tree which would produce the same AST.

The language is described by a context free S-attributed grammar using a eBNF variant.

So the unparser has to find a valid 'path' through the traversed nodes in which all grammar constraints hold. This bascially means to find a valid allocation of AST nodes to grammar production rules. This is a constraint satisfaction problem (CSP) in general and could be solved, like parsing, by backtracking in $O(e^n)$.

Fortunately for parsing, this can be done in $O(n^3)$ using GLR (or better restricting the grammar). Because the AST structure is so close to the grammar production rule structure, I was really surprised seeing an implementation where the runtime is worse than parsing: XText uses ANTLR for parsing and backtracking for unparsing.

Questions

Is a context free S-attribute grammar everything a parser and unparser need to share or are there further constraints, e.g. on the parsing technique / parser implementation?
I've got the feeling this problem isn't $O(e^n)$ in general -- could some genius help me with this?

The question has been posted on StackOverflow and Computer Science without any answers.


texts:
In this article on extension complexity of regular polygons https://arxiv.org/pdf/1505.08031.pdf it is mentioned that extension complexity of $n$ regular polygons should be $\theta(\log n)$. This is an exponential gap.

Can the gap be more than exponential for some non-trivial classes of polytopes such as $n$ inequalities being replaced by projection of $o(\log n)$ inequalities? What are the best known examples?

If the lower bound is $\alpha\log_2 n-\beta$ what are the sharpest tradeoffs and bounds on $\alpha$ and $\beta$?


texts:
What is the best upper and lower bound known for convolution without FFT?

Is FFT proven to be essential for time complexity reduction?
Is cancellation essential as well?


texts: Limited number of variable occurrences in 1-in-3 SAT

texts:
Is there a known result on complexity class of 1-in-3-SAT with restricted number of variable occurrences?

I've come up with the following parsimonious reduction with Peter Nightingale,  but I want to cite something if this is known.

Here is the trick we came up with. This shows that 1-in-3-SAT limited to 3 occurrences per variable is NP complete and #P complete (since 1-in-3-SAT is), while 3-SAT limited to 3 occurrences is in P

Let’s say we have more than three occurrences of x.  Say we need 6. Then we will introduce 5 new variables x2 to x6 equivalent to x and two new variables d1 and d2 guaranteed to be false with the following 6 new clauses:

x  -x2 d1
x2 -x3 d1
x3 -x4 d1
x4 -x5 d2
x5 -x6 d2
x6 -x  d2

Obviously we replace each occurrence of x after the first one by xi for some i. That gives three occurrences of each xi and d.

The above sets each di to false and all the xi to the same value. To see this, x has to be true or false. If it's true then the first clause sets x2 true and d1 false, and then this propagates down the clasues. If x is false then the last clause sets x6 false and d2 false and it propagates up the clauses. It's obviously strongly parsimonious so preserves counting.


texts: To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient?

texts:
I recently watched  this video on youtube. It featured someone explaining how he used genetic algorithms to improve the efficiency of wind mill turbines by finding the optimal shape for the blades. Eventually, the narrator found a non-trivial shape for the blades that seemed to be more efficient than windmills that have blades with a "standard" shape.

He did, however, use the wrong viscosity for the substance in which the wind mills are situated. Therefore the preliminary questions are:

Would the shape of the new blades be the same if the same procedure would be carried out in a substance with the correct viscosity? Would the blades still be more efficient than the "standard" blades?

Now to the real question(s). The narrator in the video carries out this genetic algorithm procedure with two-dimensional wind turbine blades.

I was wondering, though, if a similar procedure could also be carried out in a tree-dimensional environment? I guess it would be more complicated, and perhaps would require more computing power/time, but if it can be used to enhance the efficiency of wind turbine blades, it would be a good idea to do so, right? Has this already been done? Why or why not?

Last question:

if the genetic algorithm would indeed create novel, more efficient wind turbine blades, would that mean that some company would actually pick up on the idea and start producing them? Or would the novel shape be too complicated and therefore too expensive to produce, rendering the design useless from a financial perspective?

Thanks a lot in advance!


texts:
The off-policy Monte Carlo control algorithm to learn the optimal state-value function $V^*$ is given as follows, which is obtained from Sutton's book.

I have three questions concerning this algorithm:

Why does the algorithm going backward, that is, it iterates from $t = T-1$ downwards to zero in each episode.
The algorithm ensures that $A_t = \pi(S_t)$ for each $t$ otherwise it jumps out of the loop. Are there any additional assumptions to guarantee this algorithm works? How can it ensure $A_t = \pi(S_t)$ as $\{ S_t, A_t, R_t\}$ is generated by policy $\mu$, which is different from $\pi$.
It seems weight $W$ is the importance sampling ratio. But here the target policy $\pi$ changes over time. I think the reason that $W$ is updated by
$$
W \leftarrow W \cdot \frac{1}{ \mu(A_t | S_t)}
$$
is because the target policy is always greedy with respect to $Q(s,a)$, which makes $\pi(A_t | S_t) = 1$. Is this correct?


texts: Linear programming with superpolynomially many constraints?

texts:
(The specific problem I have is stated as precisely as I could in the very last paragraph which starts with a boldface "Question:", up until then the question provides context for it.)

Say we have an undirected vertex-weighted graph $G=(V,E,w)$ on $n$ vertices and want to find an optimal fractional vertex cover. You could use the following linear program (see these lecture notes) to do this:

\begin{align}
\text{minimize} &\sum_{v \in V} w(v)\cdot x_v \\
x_v &\leq 1 \qquad \forall v \in V \\
x_v &\geq 0 \qquad \forall v \in V \\
x_u + x_v &\geq 1 \qquad \forall \{u,v\} \in E
\end{align}

That gives you a polynomial time algorithm since there are polynomially many constraints, and there are polynomial time algorithms for linear programming.

However: what if there are superpolynomially many constraints? I have come across claims that you can still solve linear programs of that kind if you only have polynomially many explicit constraints (i.e. a constraint matrix of polynomial size) and for the remaining constraints, you get an implicit specification called a "separation oracle" (see e.g. these notes): such an oracle is a p-time algorithm that can check whether a constraint was violated and if so, produce a violated constraint. This works for the ellipsoid algorithm since the violated constraint defines a separating hyperplane (if I understood that correctly). An example for such a linear program is the one Even et al. used as part of an approximation algorithm for the minimum linear arrangement problem, where given an edge-weighted, connected, undirected graph $G=(V,E,w)$, we want to find a bijection $\pi: V \to [|V|]$ that minimizes $\sum_{\{u,v\}=e \in E} w(e)\cdot |\pi(u) - \pi(v)|$. The LP is this:

\begin{align}
\text{minimize} &\sum_{e \in E} w(e)\cdot l(e) \\
&\forall U \subseteq V:\, \forall v\in U: \sum_{u \in U} \text{dist}_l(u,v)\geq \frac{1}{4}(|U|^2-1) \\
&\forall e\in E:\,l(e) \geq 0
\end{align}

Here, $\text{dist}_l(u,v)$ is the shortest-path distance between $u$ and $v$ according to $l$. The second line specifies exponentially many constraints, however a separation oracle exists: first, run all-pairs-shortest-paths with respect to $l$, then for each vertex, sort the distances to all other vertices in ascending order. A constraint belonging to the second line is violated iff for some vertex $v$, the first $1\leq k \leq n-1$ distances sum to less than $\frac{(k+1)^2-1}{4}$, and in this case a witness for the violation consists of the endpoints of those shortest paths.

I've also seen claims that instead of the ellipsoid algorithm, one can use interior point methods. From what I've read, "interior point" doesn't refer to a single algorithm (or set of close variants of one algorithm) that solves the linear programming problem, but a number of different algorithms for different classes of problems. The paper where Ye's algorithm was introduced has extensive references on the development of interior point methods. I was also unable to find references that outline how to use interior point methods to solve implicitly specified linear programs that would have superpolynomial size if specified explicitly.

Question: Which interior point methods can be used to solve implicitly defined linear programs (which would have superpolynomial size if defined explicitly) in polynomial time, and how does the implicit definition have to be specified?


texts: Algorithm to find all intersections in set of simplices

texts:
What is the fastest known algorithm to report all intersecting pairs amongst a collection of $n$ simplices, each with dimension at most $r \leq d$ embedded in $\mathbb{R}^d$ (for small $d$)?

In the case where $d=2$ and all simplices are line segments, this problem can be solved in $O((n+k) \log(n))$ time using the standard sweep line algorithm, where $k$ is the number of intersections.

Are there generalizations of this technique to higher dimensions and with higher dimensional simplices (for example, find all intersections of a set of triangles in 3D)?

For clarification, I am most interested in the case where the dimension, $d$, is small, so it would be reasonable to assume that the cost of testing intersection between two simplices is $O(1)$.  Under this assumption, there is a trivial $O(n^2)$ algorithm (just test all pairs), but it would be nice to be able to do better.

The motivation for this would be to generalize sweep line intersection to 3D or higher dimensions.  This would be useful for computing overlay operations (especially CSG) in 3D, or snap-rounding.  Conventional approaches to this problem rely on spatial partitioning trees, though the performance and analysis of these techniques is somewhat sketchy (ie purely empirical, and not always great in the worst case even in practice).  It would be nice to know a solution to this problem which is supported by rigorous analysis.


texts: Are there connections between Turing machines and symbolic dynamic systems?

texts:
On a course, when shift systems were being introduced, the lector said that "if the shift of symbols sequence reminds you Turing machine, then it is a very correct association":

$\sigma(\ldots, x_{-1}, x_0, x_1, \ldots) = (\ldots, x_0, x_1, x_2, \ldots)$

I asked him about concretes but he gave me vague answers that seem to only refer to the general notion of universality that can be proved by reducing a system to Turing machine.

So he did not confirm his suggestion, that shifting sequence of symbols is analogous to moving the tape in Turing machine. But I am confused. Can this be clarified?


texts:
This is a vague question. I will do my best, I think it has definite answers. I am hoping for answers of the form "Read book x, learn this specific topic, read this paper/s".

What is bothering me is that every AI system I have read about seems to have an internal model which is set up to operate in a specific way. The task of the learning algorithm is to then optimise the parameters of this model to solve the problem.

I am thinking that this is akin to setting up a custom description language which preserves or translates some structure of the thing to be modelled in such a way that it becomes amenable to solution through some understood algorithmic technique; iterative gradient descent, analytic, whatever.

The Question: Is there any framework in which the optimum model/description language can be discovered? For instance in a GA the mapping from the genome to the phenotype is critical to the effective operation of the algorithm. This mapping is manually defined and, I would posit, is the most critical component of the GA. Specifically how would one search through the space of mappings? Or going meta how would one search through the space of algorithms for finding that best mapping? It feels like you could disappear up that ladder forever. In order to solve the problem you must first solve the problem.

Neural networks seem to represent an effective model for solving real world problems, why? How would one generate another model for a different set of problems? Cellular Automata seem good for modelling traffic flows or disease transmission, why? How would I automatically generate alternative systems which also model the set of problems effectively? etc.

Is this something that is thought about and discussed? Where would I find it? This is my first question, please be gentle! :)


texts: My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes.  If you have a proof that the theorem does indeed relativize, please supply an explanation of how relativization impacts the proposition, i.e., what does the relativized version of the statement look like when an oracle A is added?  Also, please explain what happens to the proposition when a TQBF oracle is added to the computation model.


texts:
Does anyone recognise the following problems? Do they have names? Are they hard?
If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard algorithms for rooted tree isomorphism). But what about the inexact case?
Variant 1
Input:

A rooted perfect full binary tree $T$ with $2^k-1$ nodes; let $V$ be the set of nodes.
Functions $x\colon V\to \{0,1\}$ and $y\colon V\to \{0,1\}$.

Output:

Automorphism $f\colon V \to V$ of tree $T$ that minimises the number of nodes $v \in V$ with $x(v) \ne y(f(v))$ — these are called mismatches.

Put otherwise, the task is to find a labelling $x'$ such that $x'$ is as close to $x$ as possible (minimise the number of elements that differ) and the labelled trees $(T,x')$ and $(T,y)$ are isomorphic.
Variant 2
The same as above, but only leaf nodes can have non-zero labels.


texts:
In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT?
, Nati Linial posed the following open problem:

  Which $NP$-hard computational problem on graph remain hard when restricted to expander graphs?

Since then, Has any progress been made to prove such result for an $NP$-hard problem?


texts: Number of strings with unique substrings

texts:
I have a question about binary strings with a certain property:

Given an integer $n$-bit integer $p$, that is not a perfect power of $2$. Count the number of $(p+n-2)$-bit strings that have the property that they start with $\underbrace{00...01}_{n-bit}$
and end with $\underbrace{100...0}_{n-\mathrm{bit}}$ and each $n$-bit substring occurs exactly once.

E.g., for $n=3$, $p=7$ there are $001 01 100$ and $001 10 100$, which are the only ones for the pair $(n,p)$.

Further examples are: $n=5$ and $p=29$: $00001 0001101001111011100101 10000$

and $n=5$ and $p=19$: $00001 101011110010 10000$.

I searched for related work and found papers about incompressible strings and Kolmogorov complexity. However, they did not helped me out.

Does there exists a combinatorial approach to count the number of solutions? Or is there an heuristic argument that gives a good approximation?


texts: Shortest number of editing move between two words

texts:
I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes are

add a letter at one of the extremities (for example, AB -> ABC),
duplicate and concatenate the whole word (for example, ABC -> ABCABC),
cut a word in two (the dual of the duplication move, ABCABC -> ABC + ABC),
delete one of the letters (for example, ABC -> AC), and
repeat one of the letters (for example, ABC -> ABBC).

For example, a minimal sequence of moves from ABC to BCBC is ABC -> BC (delete A) -> BCBC (duplication).

I don't have a background in computer science. Perhaps this is a well-known problem, but my Google search gave me nothing.

Do you know some related, well-defined problem?

Edit: As suggested in the answer by Anthony Labarre, I read some papers about the poset permutation/arrangement problem which is similar to the problem described above. Does anyone know more about this problem? Is this relevant?


texts: Maintaining the value of a polynomial over a dynamically updated input

texts:
Let $P(x_1, x_2, \ldots, x_n)$ be a polynomial over a fixed finite field. Suppose we are given the value of $P$ on some vector $y \in \{0,1\}^n$ and the vector $y$.

We now want to compute the value of $P$ on a vector $y' \in \{0,1\}^n$ such that $y$ and $y'$ differ on exactly one position (in other words, we flip exactly one bit in $y$). What are the space and the time trade-offs for this problem?

For example, if $r$ is the number of monomials in $P$, we can store the coefficients and the values of all monomials in $P$. If $y_i$ is flipped, we fix the value of each monomial containing $y_i$ and then the value of $P(y)$ using the stored information. Overall, we need $O(r)$ time and space.

(I do not say anything about how we identify the monomials containing $y_i$ for purpose. You can choose any reasonable representation of $P$, in the example I assume that we store a list of monomials containing $y_i$ for each $i$.)

Is there anything better?


texts:
Are there standard techniques to show that no algorithms exist for given complexity constraints?

For example, consider the following problem. The input is a list of items with exactly one duplicate, and you wish to find the duplicate item.

How do you formally prove that there cannot be an algorithm that does this in constant space and linear time?


texts: Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?

texts:
I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question are:

applying it to exact and approximate inference in Boltzmann machines, and
using it to determine for which hypergraphs it is tractable to count the number of colorings approximately.


texts: Applications of Spectral Graph Theory in Information and Coding Theory

texts:
I wanted to find out what are some application of SGT in the area of information and coding theory and maybe communications. The most related that comes to mind is the work on Expander Codes

Michael Sipser and Daniel Spielman, "Expander Codes", IEEE Transactions on Information Theory, Vol 42, No 6, pp. 1710-1722. 1996

Other examples?


texts: Notable examples of the square root idea in complexity analysis

texts:
There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include

baby-step giant-step algorithm for computing discrete logarithm in $O(\sqrt n)$,
static 2D orthogonal range counting in $O(\sqrt n)$ time and $O(n)$ memory,
priority queue with EXTRACT-MIN in $O(\sqrt[k] n)$ and DECREASE-KEY in $O(1)$,
colouring a 3-colourable graph with $O(\sqrt n)$ colours in polynomial time,

just to name a few.

While such algorithms often are suboptimal, they are easy to understand by students and good to quickly show that naive bounds aren't optimal. Also, square-root-idea data structures are sometimes more practical than their binary tree based counterparts because of cache friendliness (not considering cache-oblivious techniques). That's why I give a nice bit of attention to this topic while teaching.

I'm interested in more distinctive examples of this kind. So I'm looking for any (preferably elegant) algorithms, data structures, communication protocols etc which analysis relies on the square root idea. Their asymptotics do not need to be optimal.


texts: Minimize the time when guard observes more than one event (for fixed number of guards)

texts:
Consider the following optimization problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which are contained in two or more intervals coloured with the same colour, is minimal for given $k$. By colouring a set $S$ in $k$ colours I mean a map from $S$ to $\{1,2,\ldots,k\}$.

Example: for three intervals $[0,3]$, $[1,4]$, $[2,5]$ and $k = 2$ we need to colour first and third interval in first colour and second interval in second colour, so the measure of the set of points, which are contained in two or more intervals coloured with the same colour, is $1$.

Motivation for this problem can be the following: we have $k$ guards and $S$ is a set of events to be observed. We need to partition these events into $k$ sets (one for every guard), minimizing the time when some guard observes more than one event.

I wonder if there are any papers on this problem or related problems.

Note: I have asked this question on mathoverflow, but didn't get a response. As this problem can be considered as scheduling optimization problem, I think it is closely related to computer science.


texts: Are there languages require many variables to achieve $\Sigma_n^0$ completeness?

texts:
The proof of Post's Theorem that I am familiar with assumes you have access to as many variables as you wish in your language.  Matiyasevich's Theorem by contrast gives a $\Sigma_n^0$-complete formula of the form $\exists y_1 \forall y_2 \cdots Q y_n Q^* y_{n+1} \phi(x, y_1, \ldots, y_{n+1})$ where $Q$ and $Q*$ are the appropriate ending quantifiers. This requires only $n+1$ variables.

The number of variables required to actually demonstrate $\Sigma_n^0$-completeness of particular language is a function of the particular language being used that we might denote $f_\mathcal{L}(n)$. Note that by "language" here I mean a formal language in first order logic that is interpretable as expressing statements of arithmetic.

Can we construct languages for which $f_\mathcal{L}(n) = n^2$? $n^k$? $2^n$? An Ackermann function? Are any upper bounds known?

Edit: Josh Grochow asked about distinguishing between variables and quantifiers. After some thought, I think that the number of variables can always be made to be one more than the number of unbounded quantifiers so the distinction isn't particularly important.


texts: An algorithm for calculating the probability of a disease spreading through a graph

texts:
The following problem came up in my undergrad research project: You have some undirected graph. Some nodes are "sick" and some are not. The probability that a neighbour of a sick node becomes sick is (1 - q_i), where q is a number specific to the node under attack, ranging from 0 to 1. If a node succesfully resists an attack from a sick neighbor, it becomes immune and cannot get sick from any other node. What is the probability that any given node will become sick, given a graph A, some initial sick nodes, and a vector of q's characterizing the nodes?

I feel like this problem has been solved, but I'm having trouble finding sources. Any help or references to papers/books will be greatly appreciated.


texts: Optimal Self Balancing Trees with Canonical Form?

texts: Are any efficient [O(log n)] self balancing trees that are canonical? By canonical I mean that for any set of data inserted into the tree, inserting it after any permutation results in the same tree. I'm particularly interested in trees where data is stored in the leaves.


texts: Interesting algorithms in the formalization of the Feit-Thompson theorem?

texts:
It looks like George Gonthier and his collaborators have finished formalizing the Odd Order Theorem.

In his earlier work on the Four Color Theorem, Gonthier invented a bunch of new algorithms (mostly variants of BDDs and graph algorithms) which were especially amenable to formal verification. Since he has said that he was  continuing to use this small-scale reflection style of verification in the work on finite group theory, I wonder what new algorithmic tricks were developed during this development?


texts: How to efficiently generate a random 0-1 matrix of a given rank

texts: How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?


texts: What does "number of inputs to each neuron" mean in Neural Network terms?

texts:
I am reading about a Neural Networks project that has some data like this

I am new to this, and though I think I understand what a 3:1 network mean, I do not understand what number of inputs (to each neuron) means.

I think this is what a 3:1 network would look like (please correct me if I am wrong). Does 3 inputs per neuron mean that we will have 3 inputs to each of nodes A, B and C? In that case, what would the line connecting A to Z indicate? As in out of three inputs, how is a resultant chosen?


texts: Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al

texts:
This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say that $\mathbb{E}[g] = 0$, $\operatorname{Inf}_{i}(g) \leq \operatorname{Inf}_{i}(f)$ for all $i$, and $S_{\rho}(f) \geq S_{\rho}(g) = -S_{-\rho}(g)$.

So, applying MIS on $g$, we get

$S_{\rho}(g) \leq 1 - \frac{2}{\pi}\arccos(\rho) + \epsilon$ for $\rho$ from 0 to 1.

which implies

$-S_{-\rho}(g) \geq -\left(1 - \frac{2}{\pi}\arccos(-\rho) + \epsilon\right)$ for $\rho$ from -1 to 0.

Therefore,

$$S_{\rho}(f) \geq -1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$$

But in the statement of the proposition, authors have written $S_{\rho}(f) \geq 1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$. Is it really an error? Or I am missing something?


texts: A bijection between ordered lambda terms and rooted planar maps?

texts:
Consider the following recurrence in two parameters $n$ and $k$:

\begin{aligned}
NF(0,k) &= 0 \\
NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\
Neu(n,k) &= [n=1 \wedge k=1] + \sum_{l=1}^{n-1}\sum_{i=0}^k Neu(l,i) \cdot NF(n-l,k-i)
\end{aligned}
The expression $NF(n,k)$ counts the number of (untyped) ordered lambda terms in normal form of length $n$ with $k$ free variables. Recall that lambda terms are either variables, lambda abstractions or applications
\begin{aligned}
t &::= x \mid \lambda x.t \mid t\ u
\end{aligned}
that a term is ordered if every free or bound variable occurs exactly once and in the order it was introduced, and that a term is normal if it contains no subterms of the form $(\lambda x.t)\ u$. I take the length of a lambda term to be defined by
\begin{aligned}
|x| &= 1 \\
|\lambda x.t| &= 1 + |t| \\
|t\ u| &= |t| + |u|
\end{aligned}
The recurrence for $NF(n,k)$ is derived from a standard inductive characterization of normal lambda terms (in a mutual induction with "neutral" terms -- for background see these notes, or slide 9 of this talk).

$NF(n,0)$ thus counts the number of closed normal ordered lambda terms of length $n$.

I computed $NF(n,0)$ for $n=0..14$, and derived this sequence:
$$
0,0,1,0,2,0,9,0,54,0,378,0,2916,0,24057
$$
Now, dropping all of the 0s and plugging the result into the OEIS, I landed on A000168, whose first few terms are
$$
1, 2, 9, 54, 378, 2916, 24057, 208494
$$
and which user Don Knuth says corresponds to the
$$\text{Number of rooted planar maps with }n\text{ edges.}$$
A nice explanation (with illustrative pictures) of planar maps is given in these slides (and also this paper); in particular, a planar map is defined as a proper embedding of a connected graph in the plane (considered up to homeomorphisms of the plane), and it is rooted if one root edge is marked on the infinite face and oriented in counterclockwise direction.

Conjecture: for all $n$, we have
\begin{aligned}
NF(2n,0) &= \#\text{ of rooted planar maps with }n\text{ edges} \\
NF(2n+1,0) &= 0
\end{aligned}

Questions: Is the conjecture true? Can you prove it by exhibiting a simple bijection between ordered lambda terms and rooted planar maps?

Update (12 May 2014): I realized that the way I originally explained the conjecture was not strictly speaking correct, since the recurrence for $NF$ actually counts lambda terms which are ordered and not merely linear.  (For example, both $\lambda x.\lambda y.x\ y$ and $\lambda x.\lambda y.y\ x$ are linear lambda terms in normal form, but only $\lambda x.\lambda y.x\ y$ is ordered.  Up to normalization, the two ordered linear lambda terms of length 4 are $\lambda x.\lambda y.x\ y$ and $\lambda x.x\ (\lambda y.y)$.) I am still looking for a proof of this conjecture.


texts: Number of distinct nodes in a random walk

texts:
Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically the sum of the two hitting times $H(i,j)$ and $H(j,i)$.

Is there anything similar to the commute time (not exactly the same) but defined in terms of nodes? In other words, what is the expected number of distinct nodes a random walk starting at $i$ and returning at $i$ will visit?

Update (Sept 30, 2012): There is a number of related work on the number of distinct sites visited by a random walker on a lattice (i.e., $\mathbb{Z}^n$). For instance, see: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=no

Anybody has ever read something on this?


texts: Heuristics for exact #3COLORING close to the 3-colorability threshold

texts: What are some fast heuristics for exactly counting 3-colorings of graphs close to or at the 3-colorability threshold? Is there literature on the average-case performance for any of these methods?


texts: PhD Development; Literature Review Tactics

texts:
Not sure if correct area, but here goes.

Starting a PhD in Trust and Reputation Management in Communications networks (lots of graph theory, probabilistic analysis, etc), and have lots of reading ahead of me.

Can anyone advise the best ways to manage academic reading and what I should be noting for literature review/progress reports, etc?


texts: Is there a typed lambda calculus which is consistent and Turing complete?

texts:
Is there a typed lambda calculus where the corresponding logic under the Curry-Howard correspondence is consistent, and where there are typeable lambda expressions for every computable function?

This is admittedly an imprecise question, lacking a precise definition of "typed lambda calculus." I'm basically wondering whether there are either (a) known examples of this, or (b) known impossibility proofs for something in this area.

Edit: @cody gives a precise version of this question in his answer below: is there a logical pure type system (LPTS) which is consistent and Turing complete (in a sense defined below)?


texts: Small number of inequalities defining integer hull of integer programming problem

texts: In integer programming problem, we often want to relax the integer programming problem to linear programming problem. So we want to find the integer hull of the problem. The number of inequalities to define this integer hull is exponential in general, but are there some conditions in which the number of inequalities to define the integer hull is relative small, say, polynomial to the number of constraints? Are there any research about this?


texts: Random forests have a reputation among practitioners of being among the most effective classification techniques. Yet we don't encounter them much in the learning-theoretic literature, from which I surmise an absence of deep theoretical results. If one wanted to delve into this theory, where would one start?


texts: TCS conferences for undergraduate students?

texts:
I have noticed that ICFP has a student volunteer program and research program that accepts undergraduate students and POPL have the Programming Language Mentoring Workshop, so I was wondering if there are any other conferences with similar programs within TCS?

Also, would it be very likely that an undergraduate student would get any funding for these programs, as I am assuming the organisers would prefer postgraduate students? I would be very interested in attending the PLMW at POPL but as it's in India next year, it would be hard to self fund...

Edit: Thanks for the suggestions, I have checked some of them out, but I should have probably added that I am in the UK, so some of them would be quite far, but I know of a couple of similar undergraduate conferences to the ones mentioned by vzn so I will consider that route too...


texts:
Motivation. When I use a hash function, I would like my pre-images (original values) to a given output (hash) to be evenly distributed as it could be that an uneven distribution could make guessing / checking for original values easier.
Mathematical formulation. We can regard a hash function as a surjective map $h:\mathbb{N}\to F$ where $F\subseteq \mathbb{N}$ is a finite set. We say that $h$ is fair if $$\lim_{n\to\infty} \frac{|h^{-1}(b)\cap\{1,\ldots,n\}|}{n} = \frac{1}{|F|}$$ for all $b\in F$.
Another natural notion of "fairness" is the following: a hash function is weakly fair if $f^{-1}(\{f(x)\})$ is infinite for all $x\in \mathbb{N}$, that is for every hash there are infinitely many possible inputs (original values).
Question. Is it known for any of the currently used cryptological hash functions whether it is (weakly) fair?


texts: Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?

texts:
Let $\underline{x}\triangleq x_1,\dots,x_n$.
Given a Boolean function
$f:\{0,1\}^n\to\{0,1\}$,
we say that $p(\underline{x})\in\Bbb{R}[\underline{x}]$ is an $\epsilon$-approximation to $f$
if  for all $\underline{x}$, $|p(\underline{x})-f(\underline{x})|\leq\epsilon$.
$\newcommand{\apxdeg}[0]{{{\mathsf{deg}}}}$
Let $\mathsf{deg}_\epsilon(f)$ be the minimum degree of
multilinear real polynomial that $\epsilon$-approximates $f$.

  Supposing that $\mathsf{deg}_{1/3}(f)\geq(\mathsf{deg}_0(f))^b$ with some $b\in(0.00001,1]$, are there constants $a_f\in(0,0.00001]$ such that,
  $\mathsf{deg}_\epsilon(f) \geq(\mathsf{deg}_0(f))^{a_f}$ at every $\epsilon\in(0,1)$?

  Or is there an $f$ such that
  $\apxdeg_\epsilon(f) \leq \mathsf{polylog}(\apxdeg_0(f))$ at some $\epsilon\in(0,1)$?

  Note that $a_f$ is unlikely to be independent of $f$. A closely related question corresponds to what is the highest error $\eta_f<1/2$ as it approaches $1/2$ beyond which no further decrease happens in degree except at exactly $\epsilon=\frac{1}2$.

  Nisan-Szegedy result implies only a trivial lower bound of
  $$\lim_{\epsilon\rightarrow\frac{1}2^-}\mathsf{deg}_\epsilon(f)\geq 1.$$

For symmetric $f$ we can have $a_f$ close to $0.5$.

Is there a class of functions where a non-trivial lower-bound is not known?

Is there a class of functions it is conjectured approximate degree $\mathsf{deg}_{ \epsilon}(f)$ at some $\epsilon\in(0,\frac{1}2)$ can be polylogarithmically smaller than the exact degree given that $\mathsf{deg}_{1/3}(f)\geq(\mathsf{deg}_0(f))^b$ with some $b\in(0.00001,1]$?

When error approaches $1/2$. The bound is $\deg_{0}(f)\leq C_\epsilon(\deg_{\epsilon}(f))^8$ where $C_\epsilon$ depends on $\epsilon$. As $\epsilon$ approaches $0$, $C_\epsilon\rightarrow\infty$. So it is possible the upper bound is because  $C_\epsilon\rightarrow\infty$ and $\deg_{\epsilon}(f)\rightarrow1$. This corresponds to $a_f=0$ in the question. Can this degenerate situation actually happen in a boolean function $f$?


texts: Curry-Howard and programs from non-constructive proofs

texts:
This is a follow up question to

What is the difference between proofs and programs (or between propositions and types)?

What program would correspond to a non-constructive (classical) proof of the form $\forall k \ T(e,k) \lor \lnot \forall k \ T(e,k)$? (Assume that $T$ is some interesting decidable relation e.g. $e$-th TM does not halt in $k$ steps.)

(ps: I am posting this question partly because I am interested in learning more about what Neel means by "the Godel-Gentzen translation is a continuation-passing transformation" in his comment.)


texts: What language feature allows programs to manipulate themselves?

texts: I am busy researching different languages just for some theoretical knowledge and came across programs that manipulate themselves. What language feature is used for this?


texts: Weird claim of graphclasses about complexity of domination

texts:
EDIT this got 'fixed' on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - http://sagemath.org.

Likely this is technical error in graphclasses or in me.

Appears to me graphclasses claims P=NP.

In Domination perfect
we have $\gamma(G)=i(G)$ which implies the complexity of Dominating Set
 (DS) and Independent Dominating Set (IDS) is the same in subclasses of
domination perfect.

In line graphs
we have DS NP-complete and IDS Polynomial.

According to the java application of graphclasses, line graphs
are domination perfect, one of the reasons is they are claw-free.

Appears to me this implies P=NP.

  What is wrong?

Screenshot:

Answering vb le question about polynomial IDS on line.

Clicking details recursively, we get: Polynomial on claw-free
and the claim without reference on claw-free:

  Polynomial On domination perfect graphs, the Independent set and Independent domininating set problems are equivalent.


texts: Is 0-1 programming with constant number of constraints polynomially solvable?

texts:
It was shown in the paper "Integer Programming with a Fixed Number of Variables" that integer programmings with constant number of constraints (or variables) are polynomially solvable.

Does this hold for 0-1 programming?


texts: Are highly symmetric inequalities solvable over integers?

texts:
Suppose I have $n$ variables $x_1,\ldots,x_n$ that satisfy some inequalities that are highly symmetric, e.g., for all $S\subset [n], |S|=k$ we have $\sum_{i\in S} f(x_i,k)\le \sum_{i\in [n]} g(x_i,k)$, where $f$ and $g$ are some simple functions, e.g., composed of addition, minimum etc.
Is there a polynomial algorithm to decide whether this system has an integer solution?
What if the situation is a bit more complex, like we have several inequalities of the above form and/or additional individual inequalities, e.g., $x_i\le b_i$?

Motivation:
Many classic problems can be brought to the above form, e.g., http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem and http://en.wikipedia.org/wiki/Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem.
For example in Erdos-Gallai we have $f=x_i+\min(x_i,k)-(k-1)$ and $g=\min(x_i,k)$.

Seems related but I don't see a direct connection:
http://arxiv.org/abs/1012.4941.


texts: Computing the $n$-th bit of the binary representation of $\pi$

texts:
I (only) learned today about the following fact:

The $n$-th binary digit of $\pi$ is computable without calculating all the previous digits.

This apparently has been discovered in 1995, and follows from the Bailey—Borwein—Plouffe formula:
$$
\pi = \sum_{n=0}^\infty \frac{1}{16^n}\left(\frac{4}{8n+1}-\frac{2}{8n+4}-\frac{1}{8n+5}-\frac{1}{8n+6}\right)
$$
This in turn leads to an $O(n\log n)$-time algorithm to compute the $n$-th digit of the hexadecimal expansion of $\pi$ (and so also of the binary one), interestingly without computing the intermediate ones. (Interestingly too, it's apparently unknown how to do that for the base-10 expansion.)
My question, out of sheer curiosity, is whether anything better is known? Either deterministically or in a randomized fashion, what is the fastest algorithm known for the task "given $n$ as input, compute the $n$-th digit of the binary expansion of $\pi$"? (Also, is there any lower bound?)
Also, is there any interesting application/implication?


texts: If $P=BPP$, then Is it correct that $IP=NP$?

texts:
This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, this is not a repeated question, my question is the following:

I'm now studying Interactive Proof System in Goldreich's textbook and here. I have the following question:

Suppose P=BPP, then this show that randomness doesn't give us power over deterministic model (moreover, this would show that we can derandomize every randomness algorithm into deterministic model). Now, In interactive proof system, we know that if Verifier is deterministic, then Prover can guess all questions that Verifier would ask. So, interactive proof system is useless without randomness (see Claim 1 in the above lecture note). Moreover, interactive proof system such that Verifier is not using randomness would be equivalent to class NP. Now, does this mean if P=BPP, then IP=NP? Why I say something like that? Well, since Prover has unbounded computation power, then Prover can simulate randomness by derandomness.

Thank you!


texts:
The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be efficiently solved without randomness. This result was achieved by showing one could start from the assumption that there are problems in E that do not have small circuits, and obtain a universal pseudorandom generator to fool BPP algorithms. I say "universal", because from one hard function (family) you obtain a single PRG that fools all time-limited distinguishers.

What if we reverse the quantifiers? Would it be any easier to show that for every BPP algorithm, there exists some efficient PRG to derandomize it? The above result of course implies it (the universal PRG is such a PRG), but it relies on the hard-to-prove assumption that E does not have small circuits. Would it be possible to have weaker assumptions to get BPP derandomization, through "problem-dependent" PRGs?

This is somewhat like a uniform version of Adleman's BPP in P/poly theorem: assuming X, for every problem L in BPP, we can use X and L to construct a PRG that generates the "superwitnesses" for L.


texts: A combinatorial version for the polynomial Hirsch conjecture

texts:
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .

Suppose that

(*)

For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$,
there is $S \in {\cal F}_j$ which contains $R \cap T$.

The basic question is:

How large can t  be???

What is known

The best known upper bound is quasi polynomial $t \le n^{\log n+1}$.

The best known lower bound is (up to a logarithmic factor) quadratic.

This abstract setting is taken from the paper Diameter of Polyhedra: The Limits of Abstraction by Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov, and Thomas Rothvoss. The quadratic lower bound as well as a proof of the upper bound can be found in their paper.

Motivation

Every upper bound will apply to the diameter of graphs of d-dimensional polytopes with n facets. To see this associate to every vertex $v$ the set $S_v$ of facets containing it. Then starting from a vertex $w$ let ${\cal F}_r$ be the sets corresponding to vertices of the polytope of distance $r+1$ from $w$.

More

This problem is the subject matter of polymath3. But I thought it can be useful to present it here and on MO in spite it being an open problem. If the project will lead to specific subproblems I (or others) may try asking them as well.

(Update; Oct 5:) One specific problem that is of special interest is to restrict attention to sets of size d. Let f(d,n) be the maximum value of t when all sets in all families have size d. Let f*(d,n) be the maximim value of t when we allow multisets of size d.
Understanding f*(3,n) may be crucial.

Problem: Does f*(3,n) behaves like 3n or like 4n?

The known lower and upper bounds are 3n-2 and 4n-1 respectively. and since the 3 is the beggining of the sequence 'd'  while the 4 is the beginning of the sequence $2^{d-1}$ deciding if the truth is 3 or 4 nay be of importance.
See the second thread.


texts: Transposition of any characters in Damerau–Levenshtein edit distance computation

texts:
Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters?

Maybe some heuristic would help?

update

I will identify the application.

I have two sequences of characters. An "Old" one and a "New" one. I need to compute editorial prescription (is it a correct English term?) as a series of actions that could be applied to an "Old" sequence to make it equal to a "New" one.

There are not more than 10-20 characters in a sequence in most cases, thus O(n) is not so important.

The important part is... characters in that "Old" sequence have some metadata assigned to each other. That's why transposition is more welcome than remove/insert when it's possible.

My goal is to make an "Old" sequence equal to a "New" one preserving that metadata as much as possible.


texts:
The book "Proofs from The Book", referencing Erdős' notion of God's book, which contains the most beautiful proofs, was published in 1998.

  Are there any new proofs that should be considered for "The Book"?

While this is somewhat opinion-based, I think the voting platform in our community is an excellent way to rank the beauty of proofs.


texts: When will an NP-complete language remain hard if half of a witness is revealed with the instance?

texts:
Let $L$ be an NP-complete language.  Let $W(x)$ denote the set of (polynomially length bounded) witnesses that certify $x\in L$. That is, $x\in L$ if and only if there exists a $w$, such that $w\in W(x)$. For example, if $x$ encodes a SAT instance, then $W(x)$ contains all satisfying truth assignments of the formula $x$.

Let us assume that every witness has even length, and define the following new language:
$$L'=\{x\#u\:|\: \exists v \; \mbox{such that}\; |u|=|v|\; \mbox{and}\; uv\in W(x)\}$$
where $\#$ is a symbol that is only used for separation, it does not occur in $x$ and $u$.

The meaning of this construction is that with every input $x$, the new language $L'$ reveals the first half of a witness. In this sense, $L'$ is "easier" than $L$, because we only need to find the second half of the witness, its first half is already given. On the other hand, finding the second half still appears hard. For example, if for a SAT instance half of a satisfying truth assignment is given, it is still hard to find the other half, since after substituting the given truth values, in general we are still left with a polynomial sized formula to satisfy.

  Question: Is there any condition which guarantees that  $L'$ remains NP-complete?

Note: In general, $L'$ does not have to remain NP-complete. For example, if each witness is constructed such that its second half is only a dummy filler (such as all 0), then $L'\in {\bf P}.$


texts:
I'm learning to use the LEAN theorem prover and I got stuck in a proof of a simple fact in first-order logic:
$$ p(x) \rightarrow \forall x p(x) $$
My code is the following:

variables (A : Type) (p q : A → Prop)
example (x : A) : p x → (∀ x, p x) :=
assume H : p x,
take x : A,
show p x, from H

but it keeps saying that H has type p x_1, instead of what I expected, which is type p x.


texts: Extension of Cheeger's inequality with distinguished vertices

texts:
The standard Cheeger's inequality for graph $G$ states that

$\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$

where $\lambda$ is the second smallest eigenvalue of the normalized Laplacian of G, and $\phi(G)$ is the conductance of G.

Now suppose we are also given two special vertices $s$ and $t$, and would like to consider only cuts that separate $s$ and $t$.
Can we have a similar result relating the conductance in this special case, an some Rayleigh coefficient of the normalized Laplacian of the graph?


texts: Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

texts:
There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for example, in Paz and Moran, Non Deterministic Polynomial Optimization Problems and Their Approximations, 1981).

I've seen several claims (for example, Lund and Yannakakis, On the Hardness of Approximating Minimization Problems, 1994) that this reduction means the approximation factor bound of $c \log m$ for some $c > 0$ (proven in Raz and Safra, A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP, 1997 and cited in the mentioned Wikipedia article) gives a similar bound of $c \log n$ for MINIMUM DOMINATING SET.

But $m$ in the MINIMUM SET COVER bound is the cardinality of the universe of the sets, while the size $n = |V|$ of the graph obtained by the reduction is bigger by the number of the subsets provided for covering. When the number of subsets gets as large as $2^m$, $\log n = \log (m + 2^m)$ becomes $\Theta(m)$. How do we prove the $c \log m$ approximation factor for SET COVER when the DOMINATING SET approximation differs from the optimum only by a factor of $c m$ in the worst case?

One might argue that subsets contained in other subsets are redundant - but this still leaves $m \choose {\lfloor m/2\rfloor}$ subsets due to the Sperner's theorem, which is yet of the order of $2^m$.

Note: this page in A compendium of NP optimization problems also cites Raz and Safra's result on SET COVER inapproximability as sufficient for ($c \log |V|$)-inapproximability for DOMINATING SET.


texts: The complexity of decomposing a bi-stochastic matrix

texts:
A bistochastic matrix $A$ is a matrix with positive entries in which
each row/column sums to $1$.
By the Birkhoff von-Neumann theorem $A$ is a convex combination of
permutation matrices.
Further, by the Caratheodory theorem, $A$ can be written as a convex combination of at most $n^2 +1$ such matrices.

What is known about the complexity of finding any such permutation-matrix decomposition of A?
Is this problem known to be NP-hard ?
Furthermore, suppose we are provided with such a succinct description of $A$, i.e.
$$
A = \sum_{i=1}^{n^2+1} c_i P_i, \ \ \sum_i c_i = 1, c_i \geq 0,
$$
where each $P_i$ is a permutation matrix.
Are there problems related to bi-stochastic matrices that become easier,
say computing the permanent of $A$ ?


texts: Under what models do we know linear time sorting?

texts:
The best we know for general case sorting is $O(n\log n)$ (which is also $\theta(n\log n)$ is decision tree model) and the problem of $O(n)$ sorting is open for turing machine models.

Under what models do we know $O(n)$ algorithms and how far they are deemed away from general models?


texts: Decide the existence of a string homomorphism

texts:
Consider the following problem:

  Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y.

It is easy to show that this problem is in $NP$. Are there other things we can say about this problem? e.g. Is it in $coNP$, or even $P$?

This problem seems very natural, so I am not surprised if it has been studied thoroughly. However I could not find this problem in literature.


texts:
Finding the longest path in a graph is intractable problem. The decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path in a graph?

The algorithm should output YES if the length of the longest path is even otherwise the output is NO. Also, What is the complexity if we restrict the input to cubic graphs?

EDIT 1: I moved some of my comments here as requested by a friend.

My problem is LPEP={graph G: the longest path in G has even length }. The answer of Gadi A proves intractability and I accepted it. I was waiting for Karp reduction.

Cross posted on Math StackExchange


texts: One Generalization of Graph Isomorphism Problem

texts:
Say I generalize the language which consists of pairs of isomorphic graphs to take the following form:

$GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \geq f\}$

Is there any work on this language? The obvious question is whether there exists $f$ such that $GI(f) \in P$. The funny counterpart to this language is

$IG(f) = \{ (G, H) \mid \forall \psi : V_G \rightarrow V_H, Pr_{a, b \in V_g}((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \leq f \}$

Just wanted to hear the thoughts of anyone who wanted to have a go at constructing algorithms for different constant values of $f$ or perhaps for $f$ as a function of the size of the vertex sets or something.


texts: Hardness of vertex colouring on hypergraphs with $O(\log n)$ edges

texts:
I'm interested to know whether there has been any work done on the problem in the title. For the problem to be meaningful, we would naturally need that the hyperedges must have large ($\omega(1)$) size, otherwise there would be zero-degree vertices.

Any references to algorithmic results that would be helpful in such a scenario would also be appreciated, as are results to other generalizations of colouring such as rainbow colouring and list colouring.


texts: Generating quadratic optimization problems amenable to quantum annealing

texts:
Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a comparison between quantum Monte Carlo simulation and D-Wave machines were conducted, showing that the scaling behavior of the D-Wave chip did not indicate anything special. Around the same time, Katzgraber and coauthors argue that random instances are not too useful for testing quantum speedup. They go on to propose some things specifically for Chimera spin-glasses (the Chimera graph is the name of the hardware graph used in the D-Wave chips).

What Katzgraber says makes a lot of sense--we should focus on the hard problems and see if there's anything interesting. But how to come up with these instances? There is an isomorphism between the Ising spin-glass model and quadratic unconstrained binary optimization problems (QUBOs), so you could ask the question both ways.

I am open to: any (possibly small) insights, corrections of my misconceptions, keywords, ideas, or anything else you can contribute. Also I wonder if there are ideas in the AQC context for this that I've just simply missed or haven't understood.

[*] As a matter of courtesy, I thought I should include a brief description of the quantum annealing problem that I used in my other question:

In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily coolable initial (ground) state with Hamiltonian $H_i$ and "anneal" (adiabatically perturb) towards $H_p$, i.e.

$$
H(s) = s H_i + (1-s) H_p
$$

where $s \in [0,1]$. Details about AQC: http://arxiv.org/abs/quant-ph/0001106v1


texts: LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free language. See this wikipedia article for some natural LogCFL-complete problems. There are several other interesting LogCFL-complete problems. I could not find any natural LogDCFL-complete problems. Name any natural LogDCFL-complete problem.


texts:
In the simply-typed lambda calculus, do we ever need alpha-conversion in a small-step call-by-value reduction of a term that is closed?

The evaluation rule that uses substitution is:
$(\lambda x.t_1)~v_2 \to [x\mapsto v_2]t_1$

But if $(\lambda x.t_1)~v_2$ is closed, then $v_2$ is closed and $t_1$ only has $x$ has a free variable. Since $v_2$ has no free variables, substitution won't need alpha-conversion. $[x\mapsto v_2]t_1$ is also closed because the only free variable, $x$, has been substituted by a close term. So the result of the reduction is also closed.

It's also easy to show that for the other rules, if $t$ is closed and $t \to t'$, then $t'$ is closed.

Therefore, since we only substitute closed terms, $\alpha$-conversion is not needed.

Do you agree?

Edit: Actually, what needs to be shown is that if $t$ is closed and $t \to t'$ then in any immediate reduction $t_1 \to t_1'$ used to derive $t \to t'$, $t_1$ is closed. This is not true when reducing under binders.


texts:
Let $s$ be a graph parameter (ex. diameter, domination number, etc)

A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph
$G\in \mathcal{F}$, the treewidth of $G$ is at most $f(s)$.

For instance, let $s = \mathit{diameter}$, and $\mathcal{F}$ be the family of planar graphs. Then it is known that any planar graph of diameter at most $s$ has treewidth at most $O(s)$.
More generally, Eppstein showed that a family of graphs has the diameter-treewidth property if and only if it excludes some apex graph as a minor.
Examples of such families are graphs of constant genus, etc.

As another example, let $s = \mathit{domination{-}number}$. Fomin and Thilikos have proved an analog result to Eppstein's by showing that a family of graphs has the domination-number-treewidth property
if and only if $\mathcal{F}$ has local-treewidth. Note that this happens if and only if $\mathcal{F}$ has the diameter-treewidth property.

Questions:

For which graph parameters $s$ is the $s$-treewidth property known to hold on planar graphs?
For which graph parameters $s$ is the $s$-treewidth property known to hold on graphs of bounded local-treewidth?
Are there any other families of graphs, not comparable to graphs of bounded local-treewidth for which the $s$-treewidth property holds for some suitable parameter $s$?

I have a feeling that these questions have some relation with the theory of bidimensionality. Within this theory,
there are several important parameters. For instance, the sizes of feedback vertex set, vertex cover,
minimum maximal matching, face cover, dominating set, edge dominating set,
R-dominating set, connected dominating set, connected edge dominating set,
connected R-dominating set, etc.

Does any parameter $s$ encountered in bidimensionality theory have the $s$-treewidth property for some suitable family of graphs?


texts: Intuition behind the Charikar's LP formulation for densest subgraph problem

texts:
I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper.
Just mentioning the LP for maximum density of a subgraph of G(V,E)

$$ \max{\sum_{(i,j) \in E} {x_{ij}}}$$
$$\text{s.t.}$$
$$\forall (i,j)\in E \quad x_{ij} \leq y_i$$
$$\forall (i,j)\in E \quad x_{ij} \leq y_j$$
$$\sum_{i \in V}y_i \leq 1$$
$$\forall (i,j)\in E, i \in V \quad x_{ij}, y_i \geq 0$$


texts: Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

texts:
Suppose $L$ is a computably enumerable language, can it be decompose into  infinite CFLs with infinite words ?
$$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$

Second question: if it is possible that every $L$ , computably enumerable language with infinity words be decompose into  finite/infinite CFLs with infinite words, can it be be decompose into  finite/infinite unabiguous CFLs with infinite words?

UpDate: Third question, is it possible that every $L$ , computably enumerable language with infinity words be formed by union,complement,intersection,product  (finite/infinite) of unabiguous CFLs with infinite words?


texts: Best SAT upper bounds based on number of clauses

texts:
What's the best upper bounds based on number of clauses? In this question shown fastest algorithms for SAT, but there bounds depends from number of variables ( $O(const^n)$ where n is number of variables).

I know that variables bounds can be converted to clauses bounds. If k-SAT formula contains $m$ clauses then $n \leq \frac{k * m}{2}$, consequently if algorithm bounded by $O(const^n)$, it also bounded by $O(const^ \frac{k * m}{2}) = O((const^ \frac{k}{2})^m)$. In that way PPSZ for 3-SAT can be bounded by $O(1.496^m)$. But I'm interested in algorithms which bounds "natively" depends from number of clauses.


texts:
Let $P(x)$ be a univariate polynomial with integer coefficients where both coefficients and degrees are in binary and let $q(x)$ be another polynomial also with integer coefficients where the degrees are given in unary and the coefficients in binary. What is the complexity of determining $P(x) \bmod{q(x)}$?

I am specifically interested in the case when $P(x) = x^N$ for a binary integer $N$ and $q(x)$ is a constant degree polynomial. Any upper bound on this problem will imply the same bound on the matrix powering problem (see comment there) for constant size matrices (the degree of $q(x)$ figures as the dimension of the matrix).

The problem can be reduced to $\mathsf{BitSLP}$ (see this for definition) e.g. by reducing the problem to computing (large) powers of a matrix (Healy-Viola show how to do the reduction over finite fields in Lemma 21 - the algorithm being essentially the Kung-Sieveking algorithm - but the basic ideas are the same over $\mathbb{Z}$ also. The challenge is to improve the bound from the one for $\mathsf{BitSLP}$ proved in Allender et al viz. $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^\mathsf{PP}}} \subseteq \mathsf{CH}$


texts:
I had hard time finding algorithm or published papers on Self intersecting polygon(also polygon with hole structure) triangulation.

Can any one guide me to find published paper/algorithm, please?

PS: someone tag this question appropriately please, I do not have enough reputation points to do it.


texts: Max-cut equivalence with most likely assignment to an Ising model

texts:
Ising Model

$$
Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum_{ij \in E} \lambda_{ij} x_{ij} \right)
$$

In which $\lambda_{ij} \in \mathbb{R}$, and
$$
x_{ij} =
\begin{cases}
1 & x_i = x_j\\
-1 & x_i \neq x_j
\end{cases}
$$

and we are looking for

$$
x^* = \arg\max_x Pr(x; \lambda)
$$

This is proven to be NP-Complete.

Max Cut

Given the graph $G(V,E)$ and non-negative weights $w_{ij} \in E $ the goal is to find the set of vertices $S$ such that we maximize the the weight of edges in the cut $(S, V \setminus S)$ (the edges with the start-point in $S$ and end-point in $V\setminus S$).
More formally, by assuming $w_{ij} = 0, \forall e_{ij} \notin E $, we dote the weight of the cut by $w(S, V \setminus S) = \sum_{i \in S, j \in V \setminus S} w_{i,j}$

This is proven to be NP-Complete.

Min Cut

Exactly like Max-Cut, but the goal is to minimize the weight of the cut.

The problem could be solved in polynomial time using its max-flow formulation.

Problem Statement

In [1] (Page 16, last paragraph) it is mentioned that "finding the most likely assignment in an Ising model is equivalent to a cut problem. For example, if  $\mu \leq 0$, then the MAP assignment for graph $G = (V; E)$ corresponds to the maximum cut of $G$ with edge weights $\lambda$."

I am looking for the direct conversion between the two problems. The 2nd sentences (Started by "For example") also doesn't make sense to me.

On the other hand in Page 20 of [1] (Second paragraph), it is mentioned that:

"In the positive side, MAP inference in Ising models with ferromagnetic potentials, or
positive edge weights, is equivalent to the minimum cut problem, which can be solved in
nearly linear time (Karger, 2000)"

I'd interpret this as, Min Cut (which is Poly-time) is special case of MAP inference. Again, this is a little vague.

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf


texts: Optimal upper bound on the number of non-isomorphic graphs with certain parameter

texts:
What are the optimal (or best known) bounds (preferably exact or else asymptotic but not expectation on random graphs) on the number of  non-isomorphic (unlabelled) simple (no self-loop), undirected graphs with the following parameters/conditions:

a) connected, $|V| = m, \ |E| = n$,
b) (a) AND spectrum of adjacency matrices is same,
c) (a) AND same degree distribution
d) (c) and (b) (i.e. all of the above)

My interest is in finding lower bounds on the resource (time steps, variables required etc, enegy.) for solving graph isomorphism problem. I am aware of one such work by Cai, Furer and Immerman. Any other references aiming at or helpful in understanding the optimal resources (in any form) required for solving graph isomorphism problem will be greatly appreciated.


texts:
The Barabasi-Albert model describes a mechanism of generating random scale-free networks:

Growth: Starting with a small number ($m_0$) of connected nodes, at every time step, we add a new node with $m$ ($<m0$) edges that link the new node to $m$ different nodes already present in the network.
Preferential attachment: When choosing the nodes to which the new node connects, we assume that the probability $P$ that a new node will be connected to node $i$ depends on the degree $k_i$ of node $i$, such that

$$P\propto \frac{k_i}{\sum_i k_i}$$

Is there a similar model for scale-free bipartite networks? That is, is there a mechanism for generating random bipartite graphs that possess the usual properties of scale-free networks?


texts: A probabilistic set with no false positives?

texts:
So, Bloom filters are pretty cool -- they are sets that support membership checking with no false negatives, but a small chance of a false positive. Recently though, I've been wanting a "Bloom filter" that guarantees the opposite: no false positives, but potentially false negatives.

My motivation is simple: given a huge stream of items to process (with duplicates), we'd like to avoid processing items we've seen before. It doesn't hurt to process a duplicate, it is just a waste of time. Yet, if we neglected to process an element, it would be catastrophic. With a "reverse Bloom filter", one could store the items seen with little space overhead, and avoid processing duplicates with high probability by testing for membership in the set.

Yet I can't seem to find anything of the sort. The closest I've found are "retouched Bloom filters", which allow one to trade selected false positives for a higher false negative rate. I don't know how well their data structure performs when one wants to remove all false positives, however.

Anyone seen anything like this? :)


texts: Social choice, arrow's theorem and open problems ?

texts:
Last few months I started to lecture myself on social choice, arrow's theorem and related results.

After reading about the seminal results, I asked myself about what happens with partial order preferences, the answer is in the paper of Pini et al.: Aggregating partially ordered preferences: impossibility and possibility results. Then, I wondered if it is possible of finding a characterization of admissible social choice functions. And again someone did it (Complete Characterization of Functions Satisfying the Conditions of Arrow’s Theorem by Mossel and Tamuz). I won't give a full list, but any of the problems related to social choice I can think of where all solved in the last 5 years :(

So, do you know if there exists a survey on what was done recently in the field and what was not done?

Another question is: are you aware of complexity and social choice related problems (for instance the complexity of finding the largest subset of users that are compatible for at least one social choice function, or this kind of question).


texts:
A student of mine recently ask the following question:

Assume $$DTIME(f(n)) \subsetneq DTIME(g(n)).$$ Must there exist an $h(n)$ such that $$DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))?$$

This could probably be shown true by constructing an $h(n)$ if $f,g$ are time-constructible. But in general, I feel that this should be false similar to $DSPACE(o(\log(\log(n)))) = DSPACE(1)$.


texts: Is there any result showing that models (say SVM, Neural-Net, kNN, etc) will have difficulty in learning "rare" instances/tail phenomena?


texts: Pass ordering for greedy local search algorithms

texts:
Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for.

I have a problem with the following setup: I have a (finite) totally ordered set $(T, \leq)$ and a set of functions $f_i: T \to T$ that are non-increasing (i.e. $f_i(t) \leq t$). I know at least one point $t \in T$ but in general I only have access to $T$ via membership queries, that starting point, and the $f_i$.

I am looking for any point $t_{min}$ which is a simultaneous fixed point of all of the $f_i$. Obviously I can find this by just calculating $(f_1 \ldots f_n)^k(t)$ for our starting point $t \in T$ (note: This wouldn't be true if the $f_i$ could increase their argument).

My question is this: Given some (in general non-uniform, but I'd be happy for an answer that assumes the same cost for each as a starting point) cost model for the $f_i$, how do I find such a $t_{\min}$ with a small cost of reaching it in terms of total cost of the $f_i$ invocations to get to that point?

There are lots of obvious heuristics one can apply, but it's not obvious which ones are good, and of the ones I've tried whether they work well or not seems to depend massively on the shape of the problem and the effectiveness of individual $f_i$.

Anecdotally, in my particular use case, the following seem to usually be true:

Especially after a few iterations, most points are likely to be fixed points of most of the $f_i$.
It is much more likely that $f_i^2(s) = f_i(s)$ than that $f_j(f_i(s)) = f_i(s)$ for $j \neq i$.

Other things that might be helpful:

In my concrete use case, $T$ is a set of strings over some ordered alphabet, with $\leq$ being the shortlex order (i.e. $s \leq t$ if $|s| < |t|$ or $|s| = |t|$ and $s$ is lexicographically before $t$).
I can sample uniformly at random from $T$, and my initial $t$ comes from that distribution, but sampling is typically much more expensive than individual $f_i$ invocations.

Are there any good heuristics/metaheuristics I should be looking at for this class of problem?


texts: What bound can we get using $k$-th moment inequality under 3-wise independence?

texts:
Let $X_1,\dots, X_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma_iX_i-\mu|\geq t)$. Can we get better bound than $\Theta\left(\frac{1}t\right)$ derived by Chebyshev's inequality?

If we get a little more information, say $4$-wise independence, then we can use the $4$-th moment to get a $\Theta\left(\frac{1}{t^2}\right)$ bound. Let $Y_i = X_i - \mu$ , $Y = \Sigma_iY_i$,
$$\Pr(|Y|\geq t) = \Pr(Y^4\geq t^4) \leq\frac{\mathbb{E}(Y^4)}{t^4}=\frac{t\mathbb{E}(Y_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y_1^2)}{t^4}=\Theta\left(\frac{1}{t^2}\right).$$

If we only have $3$-wise independence, the numerator in the RHS will be $$t\mathbb{E}(Y_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y_1^2)+24\cdot\sum_{i<j<k<l}\mathbb{E}(Y_iY_jY_kY_l).$$ I don't know how to deal with the summation.

I guess the answer may lie around $\Theta\left(\frac{1}{t^{1.5}}\right)$?


texts: Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?

texts:
Consider the problem of finding a maximum disjoint set - a maximum set of non-overlapping geometric shapes, from a given collection of candidates. This is an NP-complete problem, but in many cases, the following greedy algorithm yields a constant-factor approximation:

For every candidate shape x, calculate its disjoint intersection number $DIN(x)$ = the largest number of disjoint shapes that intersect x.
Select a candidate shape with a smallest DIN ($\arg \min_{x} DIN(x)$). Remove it and all the shapes it intersects.
Continue until no more candidates remain.

For example, consider the following figure from the Wikipedia page:

The green disk intersects 5 other disks, but its DIN is 3 (the 3 red disks are disjoint). The topmost and bottommost red disks intersect 2 other disks, but they themselves intersect, so their DIN is 1. The yellow disks have a DIN of 2.
The greedy algorithm thus selects the topmost or the bottommost red disk.

If the minimum DIN can be bounded by a constant, then the greedy algorithm is a polynomial constant-factor approximation.

For example, if all candidate shapes are unit disks, Marathe et al (1995) show that a disk with a DIN of at most 3 always exists: the leftmost disk (the disk with the smallest x coordinate) intersects at most 3 other disjoint disks. Therefore the greedy algorithm yields a 3-approximation because it obtains 1 disk for each (at most) 3 disks in the optimal solution.

Similarly, if all candidate shapes are disks of arbitrary size, the greedy algorithm yields a 5-approximation, because the smallest disk intersects at most 5 other disjoint disks, i.e. the minimum DIN is at most 5.

So far so good, but Are these factors of 3 and 5 tight? I am not sure.

Consider the figure above. Selecting the leftmost disk (green) will find a disjoint set of size 1, which is indeed a 3-approximation to the maximum disjoint set of size 3 (red), but, the greedy algorithm will not select the green disk - it will select the top/bottom red disk, whose DIN is 1. In this case the greedy algorithm will find the optimal solution.

I couldn't find a counter-example for general $n$, in which the greedy algorithm finds a disjoint set with $n$ unit disks while the maximum disjoint set has $3n$. Actually, I couldn't even construct a general counter-example in which the minimum DIN is indeed 3. The best I could come up with is the following, in which each unit disk intersects at most 2 other disjoint disks (i.e. the minimum DIN is 2). But even here, the greedy algorithm finds the optimal solution rather than a 2-approximation:

My questions are:

What is the actual max min DIN in collections of unit-disks? Arbitrary-sized disks?
What is the actual approximation factor of the greedy algorithm for collections of unit-disks? For arbitrary-sized disks? (this factor is at most as large as the max min DIN, but may be smaller).

UPDATE: For every k-tuple of shapes, $x_1,...,x_k$, define $DIN(x_1,...,x_k)$ = the largest number of disjoint shapes intersected by their union $x_1\cup...\cup x_k$. Define $minDIN_k$ as the minimum DIN of over all k-tuples of disjoint shapes.

For example, in Yury's answer below, $minDIN_1=3$, because every circle intersects 3 other circles. $minDIN_2=4$, because it is possible to select 2 disjoint circles, one from the outer circle and one from the inner circle, that together intersect only 4 other circles. For every $k$, $minDIN_k\leq k+2$.

I THINK that the approximation ratio of the greedy algorithm can be bounded by $\frac{minDIN_k}{k}$, because, for every $minDIN_k$ shapes in the optimal solution, we have at least $k$ shapes in the algorithm output. Is this correct?

EDIT: I am now reading the excellent book Research problems in discrete geometry. While I haven't found this exact problem, I found a problem that looks related. In section "2.5 Thin Packings with Many Neighbors", there are examples of circle packings in which each circle touchese 5 other circles. I wonder if such a packing can yield a configuration of circles with DIN = 5.


texts: Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

texts:
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.

I think this is a proof: if $EXP\neq BPP$ then from [IW98] we get that BPP has such a simulation. Otherwise we have that $EXP=BPP$, which implies $RP=NP$ (because $NP \subseteq BPP$) and $EXP \in PH$. Now if $NP=RP=ZPP$ we have that $PH$ collapses to $ZPP$ and as a result $EXP$, but this cannot happen because of the assumption, so $RP\neq ZPP$ and this by the Kabanets paper "Easiness assumptions and hardness tests: trading time for zero error" implies that RP has such a simulation and as a result also NP.

This sounds like it could be a useful gap theorem.  Does anyone know if it appears anywhere?


texts: Approximation for metric TSP: Worst case using nearest neighbor heuristic?

texts:
I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor heuristic to the optimal tour.

Apparently, the Minimum Spanning Tree heuristic is a 2-approximation for metric TSPs meaning that it will only find tours that - in the worst case - are twice as long as the optimal tour. Is there some factor like this for the nearest neighbor heuristic for metric TSPs?


texts: Does there exist an extension of regular expressions that captures the context free languages?

texts:
In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:

  $S \to a a S b$
  $S \to $

generates $\{ a^{2i} b^i | i \geq 0\}$,

  $S \to a S b$
  $S \to a a S b$
  $S \to $

generates $\{ a^i b^j \mid i \geq j \geq 0 \}$, and

  $S \to a S a$
  $S \to b S b$
  $S \to $

generates $\{ w w^R \mid w \in (a|b)^* \}$, or equivalently $\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$ (where $p_1$ refers to the part captured by $(...)_1$).

The above examples can all be generated by adding indices ($a^i$), simple constraints on these indices ($i > j$) and pattern matching to regular expressions. This makes me wonder whether all context-free languages can be generated by some extension of the regular expressions.

  Is there an extension of regular expressions that can generate all of or some significant subset of the context free languages?


texts: Name for the "stronger submodularity" property in cut function

texts:
Let $f:2^V \rightarrow \mathbb{R}$ be a set function over $V$ that satisfies the following:

$f(A \cap B) + f(A \cup B) \le f(A) + f(B)$
$f(A \backslash B) + f(B \backslash A) \le f(A) + f(B)$.

  Here are the questions:

  Cut function $c(\delta(\cdot))$ is known to satisfy both 1) and 2). Is there any other natural example of function satisfying both ?
  If $f$ satisfies 1), then we say $f$ is submodular. But is there a name for the property of function satisfying both 1) and 2) ? Or only 2) ?


texts: Set-theoretic encoding of functions in type theory

texts:
Functions usually get encoded in set theory as follows. A function $A\to B$ is a subset $f\subset A\times B$ such that $\pi_1:f\to A$ is a bijection.
In type theory to give a function $A\to B$ is to write a program computing a term of $B$ given a term of $A$.
But can we simulate the set-theoretic notion of function in type theory? Is this a useful notion? Are there references on this?


texts: Techniques for proving that a sentence relativizes

texts:
I am interested in how one proves that a sentence relativizes.  Of course, proving that a sentence does not relativize is simple, as seen in the Baker-Gill-Solovay result; but how does one prove that a sentence does relativize, i.e., that it is true relative to any oracle?  Are there known techniques for achieving this for arbitrary sentences?

If you know of any references that address this question, I would like to hear of them.  Thanks.


texts:
Informally, we say that a Turing machine $M(\cdot)$ approximates a function $f(\cdot)$ if their outputs on a series of inputs are indistinguishable.

More formally, let $L$ be a language, $M(\cdot)$ be a probabilistic polynomial-time (PPT) Turing machine, and $f(\cdot)$ be a polynomially bounded function: $f \colon \{0,1\}^n \to \{0,1\}^{\text{poly}(n)}$. We say that $M$ approximates $f$ on $L$ if for all families of polynomial-size binary circuits $D = \{D_k\}$, and for all large enough $x \in L$, it holds that the following quantity:

$|\Pr[D_n(M(x))=1] - \Pr[D_n(f(x))=1]|$

is negligible, i.e. a positive quantity smaller than the reciprocal of any positive polynomial (For instance, $2^{-n}$ and $n^{-\log n}$ are negligible, but $1 \over 2$ and $n^{-2}$ are not.) Here, $n=|x|$.

Since $D_n$ receives an advice, there are tests which $D_n$ can perform but $M(x)$ cannot.

  This question seeks the existence of functions which are not approximable in the above sense, but are approximable if $M$ has black-box or code access to $D$.

The formalization follows:

Assume the following:

$L$ is a decidable language;
$f$ is a polynomially bounded function;
$M$ is an oracle PPT Turing machine;
$D = \{D_k\}$ is a family of polynomial-size binary circuits.
$x \in L$

$L$, $f$, $M$, $D$, and $x$ are selected in the given order; so, for example, $D$ may depend on $M$ but not vice versa. Let $n$ denote the size of $x$.

If $M$ is not explicitly equipped with an oracle, we implicitly assume that there's an oracle which for all queries, returns a special $\perp$ symbol. (Meaning that "I don't know the answer to your query.")

The question is,

  Does there exist a decidable language $L$, and a poly-bounded function $f$, such that any PPT machine $M'$ fails to approximate $f$ on infinitely many $x\in L$,
  but there exists some PPT oracle machine $M$ such that for all poly-size circuit $D$, machine $M^{D_n}$ can approximate $f$ on $L$.
  That is, the following quantity is negligible:

  $|\Pr[D_n(M^{D_n}(x))=1] - \Pr[D_n(f(x))=1]|$

Moreover:

  What if $M$ was given an encoding of $D_n$ instead of oracle access to it? That is, what if we required that $M(\langle D_n \rangle, \cdot)$ should approximate $f(\cdot)$ on $L$? (here, $\langle D_n \rangle$ denotes the encoding of $D_n$ in some canonical way.) This means that the following quantity is negligible:

  $|\Pr[D_n(M(\langle D_n \rangle, x)=1] - \Pr[D_n(f(x))=1]|$