texts: Proving skip-lists strongly weight-balanced in expectation

texts:
Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor?

In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as:

  For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.

They claim:

  Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees,
  deterministic skip lists, and skip lists in the expected sense.

I asked already about the claim for deterministic skip lists. This question is about the claim for skip lists.

I believe that skip lists have this property in expectation, but I can't find a rigorous reason. The probability the other way around (what is the height, given the length) can be calculated directly to within a constant factor. A sophisticated analysis is given in The binomial transform and the analysis of skip lists.

Edit:

There are several different notions for defining "descendants" in skip lists; this term is not used in Pugh's original paper. Some possible interpretations of "descendants" come from viewing skip lists as trees. Different ways of doing this are included in

A limit theory for random skip lists
Deterministic skip lists
Skip trees, an alternative data structure to skip lists in a concurrent approach
Exploring the Duality Between Skip Lists and Binary Search Trees

Using the notion from "Deterministic skip lists", I think this is another way of asking the same question:

If I take a fair coin, then flip it some number of times such that my last result is tails, and the longest continuous sequence of heads was of length $n$, what is the expected value of the number of times I saw tails?

I'd also be interested in non-constructive proofs of strong weight-balance in expectation, even without a closed form solution for $d$.


texts: Approximation algorithm for graph problem

texts:
In the process of trying to create an approximation algorithm for the following problem.

Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a finite set of integers.  Each vertex $v$ in the graph is to be assigned an element $i$ from the list $L$ at cost $c_{iv}$.  Cost $c_e$ is incurred for an edge iff its vertices are in different lists.  The objective is to find the minimum cost assignment to vertices.

IP: Minimize $\sum_{e \in E} c_e x_e + \sum_{i \in L \\ v \in V} c_{iv}y_{iv}$
subject to

$\sum_{i \in L} y_{iv} = 1$ for all $v \in V$,

$y_{iv} + y_{ju} \le 1 + x_{(u,v)}$,
for all $(u,v) \in E$, $i \neq j \in L$.

$x_e, y_{iv} \in \{0,1\}$ for all $e \in E$, $i \in L$, $v \in V$.

Somehow (through rounding), I am supposed to use the linear relaxation to create a 2-factor approximation for the optimal solution to this integer program.  Does anyone have a hint for how to proceed?


texts: Computational depth and p-time hard instances

texts:
After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic computational depth and hard/easy instances of NP-complete problems.

I mean, if a NP-complete has an exponential number of p-hard instances for any polynomial p for an algorithm A (instances that cannot be recognized in p-time) for sizes n sufficiently big, then it seems that the computational depth of such instancexs x is:
 BCD_p(x) =   K^p(x) - K(X) should be O(1)  (they are like random strings)

(Although this last observation is something I only have an informal explanation of why it should be)

So, looking at the results of Antunes and Fortnow, it seems that for any
polynomial p there would exist instances x such that the running time  with A:
  T_A(x) > p(|x|) >=  2^(BCD_p(X)+log(x)) (for instances with sufficiently big size n)

I would like to know if there are formal results related to this possible
connection between p-hard instances and low basic computational depth.
And there could be also connections with computational cores (sets of instances hard for any algorithm solving a problem).


texts: Finding the sparsest solution to a system of linear equations

texts:
How hard is it to find the sparsest solution to a system of linear equations?

More formally, consider the following decision problem:

Instance: A system of linear equations with integer coefficients and a number $c$.

Question: Does there exist a solution to the system with at least $c$ variables assigned to zero?

I'm also trying to determine what the dependence is on $c$.  That is, maybe the problem is FPT with parameter $c$.

Any ideas or references are really appreciated.


texts: Degree reduction step in Dinur's proof of the PCP theorem

texts: In the degree reduction step of Dinur's proof, the input graph $G$ is transformed into a graph $G'$ by replacing each vertex $v \in V(G)$ by a set of vertices, $cloud(v)$, such that $|cloud(v)| = degree_G(v)$, and imposing a degree d expander graph on $cloud(v)$ for all $v \in V(G)$. This makes $G'$ a d+1 regular graph, and the construction ensures that the gap reduces only by a constant factor. I was wondering what would happen if we impose a cycle on each cloud instead? I tried bounding the drop in the gap, but was not able to do so. So, does the proof break down at this step?


texts: To which complexity class does this language belong?

texts:
I was thinking about which class this language belongs:
$L =\{ \langle G,k \rangle \mid G $ is a graph, $k$ is a natural number and $k$ is the chromatic number of $G\}$

I thought of $L$ as (1) " there is no coloring of k-1 colors" and (2) "there is coloring of $k$ colors". Now, (1) is coNP and (2) is NP-complete so I assume that this language is neither in NP nor in coNP, but I didn't find to which class it belongs.
Any help will be welcomed.

Thanks


texts: Lower bounds on monotone space complexity

texts:
The monotone space complexity of a language $L \subseteq \Sigma^*$ can be defined in terms of monotone switching networks (see e.g. "Average Case Lower Bounds for Monotone Switching Networks" by Filmus et al.). This notion is linked to the monotone $NC$ hierarchy and may have applications to the non-monotone setting for which most questions are open.

Here is an equivalent definition in term of circuits. Let $K$ be a circuit (or dag) whose arcs are labelled by elements of $[n] \times \Sigma$, and which has a single root node $r$. We say that $K$ accepts a word $w \in \Sigma^n$ iff there is a root-leaf path $P$ in $K$ whose sequence of labels matches $w$, i.e. for each label $(i,a)$ in $P$ we have $w[i] = a$. Now, given a language $L$, for each integer $n$ we define its $n$-slice complexity $C_L(n)$ as the minimum size of a circuit accepting exactly the words in $L \cap \Sigma^n$. We can put some restrictions on this notion, for instance by requiring that the circuits are read-once, meaning that each accepting path makes a single access to a given position. This leads to a second complexity measure $C'_L(n)$ which seems easier to analyze, as illustrated below.

An example is the Perfect Matching problem ($PM$), which can be shown to have monotone complexity $C'_{PM}(n) = 2^{\Omega(n)}$ as follows. Let $PM_n$ denote the slice of the language corresponding to bipartite graphs $G$ with $n$ vertices on each side of the bipartition (denoted by $A,B$). Consider a circuit $K$ accepting it. Given an integer $k$, let $\mathcal{P}_k$ denote the set of paths of length $k$ in $K$ starting from the root, and let $\mathcal{T}_k$ denote the pair of sets $(S,T)$ with $S \subseteq A, T \subseteq B$ and $|S| = |T| = k$. By monotonicity, we can make the following assumption:

(*) for each node $u$ of depth $k$, there is a tuple $t = (S,T) \in \mathcal{T}_k$ such that each path $P \in \mathcal{P}_k$ leading to $u$ is labeled by a permutation $\sigma_P : S \rightarrow T$.

Indeed, if there were two different paths leading to $u$ corresponding to different tuples, one of them could be extended to a function that is not a permutation (and thus would recognize an $n$-edges graph that is not a matching).

Now observe that we must have the following "coverage" property: for each permutation $\sigma : A \rightarrow B$, there should exist some path $P \in \mathcal{P}_k$ such that $\sigma$ extends $\sigma_P$. Observe that a given permutation $\sigma_P$ can be extended to at most $(n-k)!$ different permutations, and that a given tuple in $\mathcal{T}_k$ can induce at most $k!$ different permutations. This implies that the number of nodes at depth $k$ is at least $\frac{n!}{k! (n-k)!}$. In particular, the number of nodes at level $\frac{n}{2}$ is at least $\frac{n!}{(\frac{n}{2})!^2} = 2^{\Omega(n)}$.

There are two things I would like to understand: (i) why does this reasoning break down for read-many / nonmonotone space complexity, (ii) how does it relate to known lower bounds for the monotone space complexity of $PM$.


texts:
We are considering length n strings over the alphabet S.

The goal is to compute a set of string, M, such that for any string, x, in S^n there exists a string, y, in M such that the hamming distance between x and y is at least r.

A way of thinking of this is that we want to guarantee that for any string, we have a string in our solution M which is far away from the given string.

For a given S (with size at least 3), n and r (which may be a funciton of n, for example n/2) for many strings a needed to include in M to guarantee that for any string in S^n, we have a string in M which has a hamming distance to it of at least r.

I have a feeling this is well studied and might be related to covering designs. Can someone give me a good reference (or insight)? I would be very grateful.


texts: Is optimally solving the n×n×n Rubik's Cube NP-hard?

texts:
Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube.  Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time algorithm?

[Some related results are described in my recent blog post.]


texts: Complexity of DBA-recognizable Omega-Languages

texts: Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular expression to a Muller automaton. However, I would asumme that this problem lies in NP but I could not find any proofs of this.


texts: Define the properties of a grammar that is the fastest to parse

texts:
It's possible to define the properties of a grammar that is fast to parse as it is indeed possible to classify algorithm based on their complexity ?

In other words it's possible to evaluate and define grammars based on their "computational" properties/behaviour ?


texts: Stochastic multi-armed bandit problem with transition costs

texts:
The stochastic multi-armed bandit problem ($k$ arms, the $i$'th of which gives you a reward of $1$ with unknown probability $p_i$, and $0$ with probability $1-p_i$, and you must decide at each stage which arm to pull based on the past reward history) is well-studied. For example, there is the UCB1 algorithm of Auer, Cesa-Bianchi, and Fisher which achieves expected regret of $O(\log n)$ in $n$ iterations, treating the other parameters ($k$ and the probabilities $p_i$) as fixed.

My question is: is there any literature out there on this problem with transition costs?  Namely, suppose you pay a cost of $P(i,j)$ whenever you pull arm $j$ immediately after pulling arm $i$?

Thank you!


texts: What are good conferences for algorithms about finite automata?

texts:
I am writing a research paper, which describes some properties about finite automata. It also provides a couple of algorithms that can measure some aspects of the properties.

Could you point out some related conferences that this topic can well fit? And how good they are?


texts: Algorithms for printing the digits of pi, minimizing the time spent between digits

texts:
What is the smallest function $t(n)$ such that there exists an algorithm which prints the binary digits of $\pi$, with the time spent between printing digit $n - 1$ and digit $n$ being $O(t(n))$?

Since the $n$th bit of $\pi$ can be computed in $O(n \log^3 n)$ time by itself, we can trivially take $t(n)$ to be $n \log^3 n$. But we can hope that $t(n)$ can be much smaller, since we get to "reuse" all of the computations which gave us the previous bits. In fact, I don't see how to rule out $t(n) = 1$.

Also, what is the name of this "mode" of computation, where we are listing out the terms of an infinite sequence? It's a little like streaming, but backward...


texts:
Is anything known about doing cryptography with very small keys?  In particular, is there any theory involving cryptosystems (based on whatever assumption you want) that can encrypt messages of length $n$ with key sizes $s = o(n^{\epsilon})$ for all $\epsilon>0$? (Assume $s$ is still large
enough that one cannot brute-force search through the space of keys.)

If there is no theory, are there real-world cryptosystems that would still "behave" with such small keys and for which much better than brute-force attacks are not known?


texts: Hardness of finding a graph coloring given the optimal number of colors

texts: We know that graph coloring is NP-complete even in some special graph classes. On the other hand if someone tells you the exact value of the chromatic number of the input graph, is this problem remains NP-complete. In other words I am wondering if there are any result for the search version of the coloring problem (possibly on different graph classes).


texts:
Are there any interesting proofs on unconventional computing? When reading on the topic I most often see soft analysis – like following paragraph from Wikipedia (Natural computing):

  Swarm intelligence,[12] sometimes referred to as collective
  intelligence, is defined as the problem solving behavior that emerges
  from the interaction of individual agents (e.g., bacteria, ants,
  termites, bees, spiders, fish, birds) which communicate with other
  agents by acting on their local environments.

Instead of soft analysis – are there any formal (and important) results in the topic?


texts: Smallest Nonuniform Complexity Classes including uniform-P

texts:
As we know, studiyng differences between uniform complexity and nonuniform complexity class is crucial.

For example, P/poly is defined as challenges to derive a separation between P and NP, because P/poly and superpoly-circuit lower bounds gives us the separation.

However, it is possible that P/poly is NOT appropriate to measure the computational ability of uniform P which is defined by usual Turing Machine.

Circuits, branching programs, protocol trees are considerd as physical devices rather than computer programs. Physical devices force to increase the number of "input wires" and can we produce infinitely  many devices (and these devices are  able to be very very different as the nubmer of input wires increases ) by constant length bit-strings ? It seems that both questions have the answer "NO".

Thus my question is :

(1)Is there any nonuniform (relating with circuits or branching programs) complexity classe C that contains P but P/poly contains the class C.

(2)What is the complexity class which satisfies (1) and is colosest to P as far we know ?


texts: Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

texts:
I am wondering if this is a topic that has had research done...

If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring that hamiltonicity wouldn't be lost - that would be very useful for me.

Anyone know anything about this?  Thank you.


texts: Best lower bound for proof complexity of graph non-automorphism problem

texts:
Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in NP-intermediate. I'm looking for references that study the certificate complexity of graph non-automorphism (GNA= {G| G is rigid or asymmetric graph}).

What is the best known lower bound on the length of certificates that proves a graph is rigid ($G \in GNA$)? Also, Is there a plausible conjecture that prohibits sub-exponential certificates for Co-NP-complete problems (analogues to ETH)?


texts:
I am looking for a simple example of a charging scheme. That is, one that will take 1-2 minutes to explain in a talk. I know of one such example, though it concerns a geometric question, while I hope to find something more graph-theoretic.

My geometric example is about upper bounding the complexity of an envelope of squares,  (that is, how many vertices can appear in the union of $n$ squares, counting only vertices that are on the border / not contained in the interior of another square). We allow the squares to have different sizes. A vertex on the envelope is either a vertex of a square or an intersection point of two squares, and thus, we immediately obtain a quadratic upper bound. A very simple charging scheme yields a linear bound.

We wish to charge every vertex of the envelope to a vertex of a square, such that every square vertex will be charged at most twice. This will immediately imply that there are at most $8n$ vertices on the envelope. A vertex of the envelope that is also a vertex of a square will charge itself. Let $p$ be a vertex of the envelope that is formed by the intersection of the squares $A,B$ such that $A$ is larger or equal to $B$. We travel from $p$ along the edge of $B$ in the direction that enters the interior of $A$, and charge the vertex of $B$ that is at the end of this edge. By drawing this, it is easy to verify that every vertex is indeed charged at most twice.

I hope that you will agree that this charging scheme can be explained in a talk in 1-2 minutes. Are there any such simple graph-theoretic examples?

Many thanks,
Adam


texts: Counting the number of distinct s-t cuts in a oriented graph

texts:
I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article Enumeration in Graphs p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a faster or simpler algorithm I can use if I am interested only in the number of such cuts and I do not actually need to enumerate it?

The definition of a s-t cut I am using is following. We have a directed graph where two vertices are labelled S and T. Cut is a minimal set of edges of a graph such that by removing those edges there will no longer exist a path from vertex S to vertex T.

I tried to ask this at Stack Overflow and I have been pointed here.


texts: Sensitivity-Block sensitivity conjecture - Implications

texts:
Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$.

The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c>0$ such that $\forall f,\mbox{ }bs(f)\leq s(f)^c$.

What are the implications of the truth and falsehood of this conjecture?

Please quote references as well.


texts:
I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.

Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $n$ order statistic of $F$. That is, $X_{k:n}$ is a random variable distributed according to the $k$th highest of $n$ IID draws from $F$. Let $\mu_{k:n}=E[X_{k:n}]$ denote the mean of $X_{k:n}$.

For an arbitrary $k$ and $n$, I am interested in the number of samples required to estimate $\mu_{k:n}$. In other words, I'm interested in estimators that take $m$ (distinct from $k$ and $n$, probably much larger) IID samples from $F$ and output an estimator $\hat \mu_{k:n}$ that is as close to $\mu_{k:n}$ as possible. I would be happy with either a guarantee in terms of mean absolute deviation (i.e. minimizing $E[|\hat \mu_{k:n}-\mu_{k:n}|]$) or a PAC-style guarantee that $\text{Pr}[|\hat \mu_{k:n}-\mu_{k:n}|\geq \epsilon]\leq \delta$.

One naïve approach would be to divide your $m$ samples into $m/n$ blocks of $n$ samples, and average the $k$th sample from each block. The performance of this estimator could be analyzed fairly easily using Chernoff bounds. I'm wondering if there's something smarter one can do. Lower bounds would also be of interest.


texts:
The following decision problem is called k-True-Monotone-2SAT:

  Given a 2-CNF boolean formula $F$ that does not contain any negated variables
  and given a positive integer $k$, can $F$ be satisfied by setting $k$ or fewer
  variables to true?

It is NP-complete: it's easy to see a straightforward reduction from Vertex Cover to it (i.e. can we cover all the edges with $k$ or fewer nodes?).

The following decision problem is called Monotone-2SAT:

  Given a 2-CNF boolean formula $F$ that does not contain any negated variables, is it satisfiable?

As a decision problem, Monotone-2SAT is trivial. The answer is always YES: just set every variable to true.

But consider its counting version, called #Monotone-2SAT:

  Given a 2-CNF boolean formula $F$ that does not contain any negated variables, how many satisfying assignments $F$ has?

Surprisingly, #Monotone-2SAT is #P-complete.

Now here is the question. Suppose we have an oracle for #Monotone-2SAT, which returns the exact solution count of a Monotone-2SAT formula: how such solution count can be used to solve k-True-Monotone-2SAT?

I'm asking this because I do not immediately see how the solution count may give information on how many solutions have k or less literals set to true and how many don't.


texts: Explicit combinatorial construction minimizing intersection of sets

texts:
I'd like to know if anything is known about the following problem:

Suppose we choose positive integer $t$ to be constant. Let $S = \{1,2,\dots,n\}$, where $n$ is sufficiently large. Consider a partition $A_j$ of $S$ of the form $S = A_{j,1} \cup S_{j,2} \cup \dots \cup S_{j,\sqrt{n}}$, where each $S_{j,i}$ is roughly of size $\sqrt{n}$. Is it possible to find an explicit construction of $k = O(1)$ such partitions ($k$ not depending on $n$ or $t$), say $A_1, A_2, \dots, A_k$, such that for any choice of $i_1, i_2, \dots, i_{t/10}$ (for each $i \leq k$), we have
$|\bigcap_{i=1}^k (A_{i,i_1} \cup A_{i,i_2} \cup \cdots \cup A_{i,i_{t/10}})| = O(t)$?

Thanks!


texts:
I'm looking to adapt the PageRank algorithm as a centrality measure in a network. This network however, unlike the "random surfer" of the original paper on PageRank, or the random library browser for Eigenfactor.org, doesn't have a random browser who can leave and jump off to some other network. The theoretical reader is reading only this literature, and reading it completely.

As I understand it, the damping factor in the usual implementation of PageRank is 1 - probability of the random surfer jumping to a different site, and is usually set at 0.85. Is it reasonable then, in an entirely closed network, to set this value = 1.0, or is there something I'm not seeing?

Some details of the network, which would probably be helpful:

All the networks I will be looking at are fairly small, less than 1000 nodes, and directed. They're citation networks - with papers as nodes and edges as citations between papers, so inherently there are no isolated nodes not connected to any other nodes, as their inclusion in the network is conditional on there being a link to or from the network. There's no reason to believe the network is strongly connected - indeed, I'm pretty sure they're inherently not.


texts: #P-complete problems are at least as hard as NP-complete problems

texts:
I just read

J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)

and one of the first sentences is

  Valiant defines the notion of the #P-complete class (...) and shows that problems in this class are at least as hard as NP-complete problems.

My first problem is that is seems weird to directly compare the complexity of counting and decision problems. But more importantly: There are quite easy decision problems, whose counting variant is #P-complete, for example satisfiability of boolean formulas in DNF. This can also be read on Wikipedia:

http://en.wikipedia.org/wiki/Sharp-P-complete

So is the statement, that a #P-complete problem is at least as hard as a NP-complete problem simply wrong or am I getting something wrong?


texts:
In the paper “Consequences of Faster Alignment of Sequences” by
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of the integer 3-SUM conjecture is stated.
Conjecture 1 (3-SUM Conjecture) In the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $n^{2−o(1)}$ time in expectation to determine whether three sets
$A,B,C \subset \{−n^3,\ldots,n^3\}$ with $|A| = |B| = |C| = n$
integers contain three elements $a∈A,b∈B,c∈C$ with $a+b+c=0.$
Not being an expert I have the following question.
How is this restriction to the set of integers with absolute value $\leq n^3$ justified? Is this in some sense hardest and other cases can be solved if this case is solved?
Remark: I suppose a ground set of size $O(n^3)$ is dense in the sense that a lot of triple candidates cannot be ruled out, but I imagine there are more spread out sets which may have similar properties.
Edit 2: Changed the focus of the question.


texts:
What is known about complexity of NP-hard problems on Cayley graphs?

Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input length is the size of the graph. Can we solve NP-complete problems on such graphs (maximum clique/max-cut) in polynomial time?

What about some special cases of groups? For example, $\mathbb{Z}_n$ (a.k.a. circulant graphs) or $\mathbb{Z}_2^{\log(n)}$. That is, the input to the problem is the set of generators (and $1^n$ to represent the size of the graph).


texts: On derandomizing polynomial identity testing

texts: In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x_1,\dots,x_n]$. Derandomizing known efficient randomized algorithms and producing an efficient deterministic algorithm is an important open problem. Is there a complete problem for PIT so that derandomizing identity testing for this one class of polynomials solves this open problem? If not, are there classes of polynomials where this problem is solved and classes where they are open?


texts:
Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.

I would like to know if anything is known on the time and space complexity with respect to $n$ to check for membership in $L$ for a sliding window of size $n$ over an infinite stream. Here I mean the incremental complexity by moving the window along the stream and computing on the fly the membership of the window seen as a word to the language $L$.

Exemple:  It is simple to check with space complexity $\mathcal{O}(\log(n))$ and time complexity $\mathcal{O}(1)$ for the language $\Sigma^* ab \Sigma^*$ with $\Sigma=\{a,b\}$. You simply need to remember the last $ab$ factor seen in a register and to increment it by $1$ at every new symbol, which is constant in the appropriate RAM model.

Case of interest (at least for me) includes:

$L$ is the Parity language over $\{0, 1\}$, the number of $1$ is even, or in regexp: $(0^* + 10^*1)^*$
$L$ is the Majority language over $\{0,1\}$, there are more $1$ than $0$.
$L$ is the language over $\{0,1,e\}$ such that there exists a $0$ before a $1$.
$L$ is an arbitary regular language.

In particular, is it needed to store all the window for those languages?
It seems so but I fail to see a proof. Even if we allow a space $\mathcal{O}(n)$, can we reply in time $\mathcal{O}(1)$?


texts: How to find the shattering set size without visualising the target function behaviour?

texts:
My aim is to prove a vc-dimension $d$ for different problems. All the problems I have do not have visualised target function (or concept) . I know this is unnecessarily. But this unlike most of the examples I came through. For example in the interval problem, the target function $h^*$ is: if point $x\in [a,b]$ then $x=+$ and $-$ otherwise. I do not know where $[a,b]$ resides in $R$ but at least I know its an interval. Therefore, three points of $(+,-,+)$ cannot be shattered by any concept.

I am given an infinite input space $X$ and $H$ is the class of all finite languages over $X$ and asked to find and prove the vc-dimension for this problem. Since I do not know what the target function looks like, I can't test the sample points. All what I know is that if $|x|$ is finite then $h^*(x)=+$ otherwise $-$.

Assume I got two points $x_1,x_2\in X$, there are $2^2$ possibilities $(-,-),(-,+),(+,-),(+,+)$. I am stucking here since I don't know how to test for example $(-,+)$ against my function behaviour. Any hints on how to shatter without visualising the target behaviour?


texts: Why can't codes be defined over infinite fields?

texts: In Coding Theory, people use $q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as $\mathbb{R}$ or $\mathbb{C}$?


texts: $\mathsf{P}^\mathsf{BPP}$ vs $\mathsf{BPP}$ (Are they known to be equal)

texts:
Is it known if $\mathsf{P}^\mathsf{BPP}= \mathsf{BPP}$ ?

It's clear that $\mathsf{BPP} \subseteq \mathsf{P}^\mathsf{BPP}$. Now, since $\mathsf{BPP}$ is closed under complementation, union, and intersection, it seems to provide evidence that $\mathsf{BPP} = \mathsf{P}^\mathsf{BPP}$. However, I can't prove this.


texts: Problems and theories in CS that uses Fibonacci numbers

texts:
I want to know problems and theories where Fibonacci sequence is used and where we have some possibility to use Fibonacci numbers. I have found that-

In counting number of steps for Euclidean algorithm, 2. Fibonacci heap, 3. Fibonacci search, 4. Fibonacci numbers are complete; means we can write any number as sum of Fibonacci numbers(Fibonacci basis) etc.

Is there any other applications of this sequence in CS. Please share if you know any other.


texts: What would be the consequences of factoring being NP-complete?


texts: Number of subsets on a set with partial order

texts:
Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a<b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-closed?

Are there algorithms that can solve the problem in time polynomial in $|S|$?


texts: What's new in compiler optimization techniques over last few years?

texts:
I'm interested in optimization of data flow and control flow graphs and in particular more computationally complex.
But it will also be interesting to know about the latest inventions in the field of peephole optimizations.


texts: Circuit Complexity Charaterization for DLogTime and NLogTime

texts:
$\mathsf{DLogTime}$ and $\mathsf{NLogTime}$ are two of the smallest complexity classes we have. (Note that logarithmic time hierarchy $\mathsf{LH}$ is equal to $\mathsf{AC}^0$ and these are the first two level of $\mathsf{LH}$).

After reading this question, I become interested to see if the separation between these two classes is known, and in fact it is easy to separate them since $OR(x_1,...,x_n) \in \mathsf{NLogTime}-\mathsf{DLogTime}$ (thanks to Robin Kothari. See also known). Now I am interested to know their corresponding circuit complexity characterization. I have searched a little bit and have asked a few people but was not able to find the answer.

  Do we have nice circuit complexity characterizations for complexity classes $\mathsf{DLogTime}$ and $\mathsf{NLogTime}$?

Note: $\mathsf{DLogTime}$ shows up a lot in defining uniformity for small complexity classes. Note that the small time bound does not allow these machines to read the whole input, they can only read $\lg n$ bits from the input, and the classes are defined using machines that can write the address of a bit and then read that bit directly (i.e. don't need to go over all previous bits to reach there).


texts: Can real-time deterministic multicounter automata recognize the marked palindrome language?

texts:
Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$.

It is easy to recognize MPAL using only a single stack.

My question is whether MPAL can be recognized by a real-time deterministic multicounter automaton.


texts: Interval partitioning with restrictions: NP-complete or efficiently solvable?

texts:
The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. Here's my problem formulation:

There are $n$ rooms. We want to hold $m$ events in these rooms. These events have fixed (given as input) starting times $s_1,\dots,s_m$ and finishing times $f_1,\dots,f_m$.
Each event must be held in exactly one room, and two events cannot be held in the same room at the same time.
Certain events can be held in only certain rooms. This is given as an input as an $n$ by $m$ matrix of booleans.
We want to figure out whether all events can be held in these rooms.

It seems to me that a greedy algorithm can't solve this. Additionally, since bipartite matching is a special case of this problem (when all events are held at the same time), I have attempted to transform this "interval partitioning with restrictions" problem into a maximum flow problem, with no success. I have also considered trying to prove that this problem is NP-complete, but I don't know where to start.

Could anybody help me either find an efficient algorithm for this or prove that it is NP-complete?


texts: Is there fast algorithm for finding min vertex-disjoint path cover of DAG graph of poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v

texts:
Let P is a poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v. Let G is a DAG corresponding to poset P. Suppose I want to find some minimum vertex-disjoint path cover of G.

It is known that there is a general algorithm by reduction of this problem to maximal matching. But in this case P may have some specific properties, so may be there is some algorithm for doing this faster than matching.

Thanks in advance.


texts: How quickly can we decompose a number into a set of residues?

texts:
Basically, if we are given a natural $x$, in binary, with $x < m_0 \cdot m_1 \cdot m_2 \cdot \dots \cdot m_n$, how quickly can we find $x \bmod m_0$, $x \bmod m_1$,..., and $x \bmod m_n$?  In other words, how quickly can we find $n$ residues in modular arithmetic?  Note that the residues needn't be primes.

I suppose that this is a fairly broad question, and I'm curious if there are special cases where we can find these residues much faster (in other words, if there are special values for the modulus that allow faster calculations).  My motivation is that I'm entertaining some ideas concerning integer multiplication.  Along these lines, I'd like to break apart numbers into smaller residues.  I'm interested in any results besides the trivial situation when some of the moduli are powers of 2.


texts: Is there any place, where description of formalized image processing algorithms can be found? Like creating hdr images, bluring images, etc.


texts:
Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-complete by Schaefer. It remains NP-complete even for planar cubic graphs.

I am interested in a variant where we want to decide whether input graph has coloring with two colors such each node has exactly one neighbor colored differently from itself. I call this Red-Blue perfect matching problem. I don't know whether this is a known problem.

  How hard is deciding the existence of Red-Blue perfect matching?


texts: Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

texts:
Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable).

Assume you are given a set of $k$ constraints of the form "$v_i \text{ is colored by }f(v_i)$".

Our goal is to determine whether this precoloring could be extended into a valid 4-coloring of $G$.

  Can the 4-colors precoloring extension of $G$ be solved in FPT time (with respect to $k$)?

Notice that the problem is NP-hard by a reduction from 3-coloring of planar graphs - Given a planar instance $G$ which we want to check for 3-colorability, create a vertex $v'$ for each vertex $v$, connect $v'$ with $v$, and force all of the new vertices to be colored in the 4th color.


texts: Selection algorithm on depth-$\text{O}(\log n)$ sorting network

texts:
Is there a sorting network of depth $\text{O}(\log n)$ for selecting the $i$th order statistic?

Remark: I've already asked a related question in a different context.  Although the two questions are related, this is not a duplicate of the other one.


texts:
I want to learn about nested stack automata. However my efforts to find a suitable learning resource have so far been abortive:

The Wikipedia article on nested stack automata is a stub.
Alfred Aho's original paper on nested stack automata is available on ACM. However it's not free and I don't have the means to pay for it.
I've read the paper on nested stack automata written by Robert Gilman and Michael Shapiro several times but the concept, to me, is still abstruse.

I really want to learn about nested stack automata. Hence it would be nice if somebody could explain, in a rigorous manner, how a nested stack automaton works.

In addition if you could link me to some good articles which explain nested stack automata then that would be great. Perhaps you have a soft copy of Alfred Aho's original paper on nested stack automata and are willing to share it?


texts: Triangular range counting query in poly-logarithmic time

texts:
What is the minimal space requirement for
triangular range counting queries in plane
if one wants to process each query in poly-logarithmic time?

In [Goswami et al, 2004]
they preprocess the points to create a data structure in $O(n^2)$ time and space
achieving $O(\log n)$ query time for triangular range counting.

Is it the best known result till date?

References:
Partha P. Goswamia, Sandip Dasb, Subhas C. Nandy,
"Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment", 2004


texts: Efficient algorithm for near-optimal edge-colourings of hypergraphs

texts:
Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.
Question.
What efficient algorithms are there for finding an approximately-optimal edge-colouring  for k-uniform hypergraphs?
Details ---

A k-uniform hypergraph is one in which each edge contains precisely k vertices; the usual case of a simple graph is k=2. More precisely, I'm interested in labelled k-uniform hypergraphs, in which two edges may actually have the same vertex-set; but I'll settle for something on k-regular hypergraphs with edges intersecting at no more than k−1 vertices.

An edge-colouring of hypergraphs is one in which edges of the same colour do not intersect, as with the case of graphs. The chromatic index χ'(H) is the minumum number of colours required, as usual.

I would like results on deterministic or randomized polynomial time algorithms.

I'm looking for the best known approximation-factor/additive-gap between what can be efficiently found, and the actual chromatic index χ'(H) --- or for that matter, the best efficiently-attainable result in terms of parameters such as the maximum vertex degree Δ(H), the size of the hypergraph, etc.

Edit: prompted by Suresh's remarks about hypergraph duals below, I should note that this problem is equivalent to the problem of finding a strong vertex colouring of a k-regular hypergraph: that is, where each vertex belongs to k distinct edges [but the edges may now contain differing numbers of vertices], and we want a vertex colouring such that any two adjacent vertices have different colours. This reformulation also does not seem to have an obvious solution.

Remarks
In the case of graphs, Vizing's Theorem not only guarantees that the edge-chromatic number for a graph G is either Δ(G) or Δ(G)+1, standard proofs of it also give an efficient algorithm for finding a Δ(G)+1-edge-colouring. This result would be good enough for me if I were interested in the case k=2; however, I'm specifically interested in k>2 arbitrary.
There doesn't seem to be any well-known results about bounds on hypergraph-edge-colouring, unless you add restrictions such as every edge intersecting in at most t vertices. But I don't need bounds on χ'(H) itself; just an algorithm which will find a "good enough" edge-colouring. [I also don't want to place any restrictions on my hypergraphs, except for being k-uniform, and perhaps bounds on the maximum vertex-degree, e.g. Δ(H) ≤ f(k) for some f ∈ ω(1).]
[Addendum. I have now asked a related question on MathOverlow about bounds on the chromatic number, constructive or otherwise.]


texts: Definition and Computational Model of EnumP

texts:
Valiant [1] defined the $P$-enumerable problem in which he used the Counting Turing Machine Model: A counting Turing machine is a standard nondeterministic TM with an auxiliary output device that (magically) prints in binary notation on a special tape the number of accepting computations induced by the input. It has (worst-case) time complexity $f(n)$ if the longest accepting computation induced by the set of all inputs of size n takes $f(n)$ steps (when the TM is regarded as a standard nondeterministic machine with no auxiliary device).

A relation $R$ is $P$-enumerable iff there is a polynomial $p$ such that for all $x$ the set $\{y|R(x, y)\}$ can be enumerated in time $|\{y|R(x, y)\}|\cdot p(|x|)$.

However, in [2], they used the Random Access Machine (RAM) model to give the definition of $EnumP:$ Let $C$ be a set of binary predicates, $Enum · C$ is the set of problems $A$ such that $A \in C$.

It seems that $EnumP$ is more general than the definition of $P$-enumerable. Only the notations are easily confusing.

Why do they use different models for the enumerating problem? What is the connection between the Counting Turing Machine and RAM model when deal with the enumeration problem?

For the difference of TM and RAM can be referred to [3].

[1] Valiant, Leslie G. "The complexity of enumeration and reliability problems." SIAM Journal on Computing 8.3 (1979): 410-421.

[2] Capelli, Florent, and Yann Strozecki. "On The Complexity of Enumeration." arXiv preprint arXiv:1703.01928 (2017).

[3] https://cs.stackexchange.com/questions/22418/what-is-the-difference-between-ram-and-tm


texts:
There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "surprising" consequences (like the collapse of the polynomial hierarchy).

My question is, what is the basis for belief that the class PPAD is intractable? If there was a polynomial time algorithm for finding Nash equilibria, would this imply anything about other complexity classes? Is there a heuristic argument for why it should be hard?


texts: Are arithmetic circuits weaker than boolean?

texts:
Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit
computing a given multilinear  polynomial
$$
 f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,
$$
 and $B(f)$ denote the minimum size of a (non-monotone) boolean $(\lor,\land,\neg)$ circuit
computing the boolean version $f_b$ of $f$ defined by:
$$
 f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,.
$$

Are polynomials $f$ known for which $B(f)$ is smaller than $A(f)$?

If we consider monotone versions of circuits -- no Minus $(-)$ and no Not $(\neg)$ gates -- then $B(f)$ can be even exponentially smaller than $A(f)$: take, for example, the shortest s-t path polynomial $f$ on $K_n$;
then $B(f)=O(n^3)$ and $A(f)=2^{\Omega(n)}$. But what happens in the "non-monotone world"? Of course, big gaps cannot be known just because we do not have large lower bounds on $A(f)$. But perhaps there are at least some small gaps known?

NOTE (15.03.2016) In my question, I do not specified how large coefficients $c_e$ are allowed. Igor Sergeev remembered me that, for example, the following (univariate) polynomial $f(z)=\sum_{j=1}^m 2^{2^{jm}} z^j$ has $A(f)=\Omega(m^{1/2})$ (Strassen and people of his group). But $B(f)=0$ for this polynomial, since $f_b(z)=z$. We can obtain fron $f$ a multivariate polynomial $f'(x_1,\ldots,x_n)$
of $n=\log m$ variables using using Kronecker substitution. Associate with every exponent $j$ a monomial $X_j=\prod_{i:a_i=1}x_i$, where $(a_1,\ldots,a_n)$ are the 0-1 coefficients of the binary representation of $j$. Then the desired polynomial
is $f'=\sum_{j=1}^m c_j X_j$, and we have that
$$
A(f')+n\geq  A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.
$$
But the boolean version of $f'$ is just an OR of variables, so $B(f')\leq n-1$, and we have an even exponential gap. Thus, if magnitude of coefficients can be triple-exponential in the number $n$ of variables then the gap $A(f)/B(f)$ can be shown to be even exponential. (Actually, not the magnitude itself -- more the algebraic dependence of the coefficients.)
This is why the real problem with $A(f)$ is the case of small coefficients (ideally, only 0-1). But in this case, as Joshua recalled, the lower bound $A(f)=\Omega(n\log n)$ of Strassen and Baur (with 0-1 coefficients) remains the best what we have today.


texts: Is counting simple cycles in $P$ for graphs of bounded tree width?

texts:
Motivation:
Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either via some algorithm involving separators + dynamic programming, or by expressing the existence of a Hamiltonian cycle in a form that fits into Courcelle's theorem.

Counting the number of Eulerian circuits on undirected graphs is $\# P $ complete, but according to this paper it is in $P$ on graphs with bounded tree width.

Counting the number of Hamiltonian cycles is $\#P$ complete, but according to theorem 4.3 of this paper, counting Hamiltonian cycles is in $P$ for graphs of bounded tree width.

Counting simple cycles is $\# P$ hard in general...

Question: Is counting the number of simple cycles in $P$ on graphs of bounded tree width?

Notes:

My inclination is to look at the separators + dynamic programming algorithms to see if one of them can be modified, but I'm pretty sure that if one can be straightforwardly modified to count simple cycles, then someone has done that already.
I do not see a way to express 'simple cycle' in $MSOL_2$ (the best I can do is express disjoint unions of simple cycles). I'm not sure if there is a version of Courcelle's theorem for counting the set of solutions to a monadic second order logic formula -- I just got a surface level understanding of this theorem from wikipedia.
I found a simple dynamic programming style algorithm to count simple cycles on series parallel graph, but it does not generalize to bounded tree width graphs. I assume that this is well known and in the literature somewhere.
(Here is the algorithm: Initialize all edge weights $w_a$ to be $1$. Initialize $S = 0$. Every time you replace 2 parallel edges with weights $w_e$ and $w_f$, with a new edge called $ef$, set $w_{ef} := w_e + w_f$ and $S := S + w_e w_f$. Every time you replace to series edges $e$ and $f$ with a new edge called $ef$, set $w_{ef} := w_e w_f$. Apply replacements until you have $K_2$. The value of $S$ at the end is the number of simple cycles, and the weight of the edge at the end is the number of simple $s$-$t$ paths.)


texts:
In Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?, authors defined a new type of generic oracles named Kolmogorov generic oracles.

They proved following results relative to $G\oplus H$ where $G$ is Kolmogorov generic and $H$ is $PSPACE$-complete:

$TFNP=FP$,
$PH$ does not collapse,
$P\not=UP$.

The following questions are about the Kolmogorov generic oracle $G$ and its definition:

  Q1. The consistency of two conditions $p$ and $q$ means $p|_{D(p)\cap D(q)}= q|_{D(p)\cap D(q)}$ where $D(\alpha)$ means domain of $\alpha$. My question is about the meaning of consistency in the definition of an interval $U_p$. What is the meaning of the consistency of a condition $p$ with some subset of $U$ like $A$?

  Q2. Theorem 5 says that relative to a Kolmogorov-generic oracle $G$, $P\not = UP$. In the proof of this theorem the language $L=\{\left<i,0^n\right>:\exists z(|z|=n \land\left<i,0^n\right>\in G\}$ is defined and it says that $L\not\in P^G$ without proof. What is the argument to prove $L\not\in P^G$?


texts:
Here is the problem as posed by Jerrum:

"The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target permutation which is a member
of the group, what is the shortest expression for the target permutation in terms of the generators?"

Jerrum, Mark R. "The complexity of finding minimum-length generator sequences." Theoretical Computer Science 36 (1985): 265-289.

What is the current state of the art algorithm for finding min-length generator sequences over small ( n<13 ) permutations?

The simple approach seems to be caching prefixes and growing them when a length $i+1$ word (composed into a permutation) is not contained in any of the length $1..i$ words. You either reach the target permutation, or at some length your words no longer compose into new permutations so you know the target is unreachable.


texts: An easy case of SAT that is not easy for tree resolution

texts:
Is there a natural class $C$ of CNF formulas - preferably one that has previously been studied in the literature - with the following properties:

$C$ is an easy case of SAT, like e.g. Horn or 2-CNF, i.e., membership in $C$ can be tested in polynomial time, and formulas $F\in C$ can be tested for satisfiability in polynomial time.
Unsatisfiable formulas $F\in C$ are not known to have short (polynomial size) tree-like resolution refutations. Even better would be: there are unsatisfiable formulas in $C$ for which a super-polynomial lower bound for tree-like resolution is known.
On the other hand, unsatisfiable formulas in $C$ are known to have short proofs in some stronger proof system, e.g. in dag-like resolution or some even stronger system.

$C$ should not be too sparse, i.e., contain many formulas with $n$ variables, for every (or at least for most values of) $n\in \mathbb{N}$. It should also be non-trivial, in the sense of containing satisfiable as well as unsatisfiable formulas.

The following approach to solving an arbitrary CNF formula $F$ should be meaningful: find a partial assignment $\alpha$ s.t. the residual formula $F\alpha$ is in $C$, and then apply the polynomial time algorithm for formulas in $C$ to $F\alpha$. Therefore I would like other answers besides the all-different constraints from the currently accepted answer, as I think it is rare that an arbitrary formula will become an all-different constraint after applying a restriction.


texts:
If LR(0) condition for a grammar G is formulated as follows:

Every state is either reduction or a shift state and it can't be both at the same time
if it is a reduction state, it contains exactly one item

and LALR :

Every reduction candidate has a look-ahead set disjoint from the set of the terminal labels of the arcs leaving the state
in case of multiple reduction candidates, their look-ahead sets are disjoint

I'm looking for the name (if any) of the LALR subset corresponding to the following conditions:

Every reduction candidate has a look-ahead set disjoint from the set of the terminal labels of the arcs leaving the state
Each reduction state contains exactly one reduction candidate

which is a hybrid between LR(0) and LALR itself.

Thank you.


texts:
I'm trying to figure out some consequences of the fact that Toda's Theorem relativizes. The (un-relativized) Toda's theorem states that $PH \subset P^{\#P}$ so that for any constant $k$ and any polynomial-time computable function $g: \{0,1\}^{n \times 2k} \to \{0,1\}$ we have that the problem of computing
$$\min_{x_1} \max_{y_1} ... \min_{x_k} \max_{y_k} g(x_1,y_1,...,x_k,y_k)$$

can be reduced to the problem of computing
$$h(\#\phi)$$
for some polynomial time function $h: \mathbb{N} \to \{0,1\}$ and some polynomial time boolean formula $\phi: \{0,1\}^{poly(n)} \to \{0,1\}$

My question is, do I need to assume that $\phi$ and $g$ can be computed in polynomial time? My conjecture is that since Toda's theorem relativizes, I can assume that they are arbitrary black-box functions and the theorem will still hold.


texts:
Apologies in advance for this a soft question which has no closed, correct answer. This is probably the best forum to ask my question.

I am a third year graduate student in theory group of a top-15 school in US. So far, I've been doing decently well. I have a first author theory paper and a first author practical paper so far. My advisor has been superb in helping me honing my skills but I feel stuck (and helpless).

So far, my advisor has been a helping hand and a guiding force to always point me right directions and pose the right questions (not too abstract, not too concrete) which have been instrumental in me finding the answers to research problem. As I try to be more "independent", i.e, ask the right questions and prove results, I feel I have failed miserably and quickly feel overwhelmed. I feel that I don't have the maturity of a theory PhD student yet where I can ask myself the right questions and come with answers. In other words, given the right definitions and some hand holding, I am able to do things but otherwise, it becomes very hard. My sloppiness when it comes to writing proofs doesn't help either.

I am looking for advice on how can I sharpen my skills and be more "theory-minded" where I can grasp things quicker and require less hand holding. While one answer is simply to keep working and hope that experience makes me wiser, I am not sure how this will work out. The only solution I have is to actually go through come recent papers in my area and write down proofs by hand in as much detail as possible to help me nail proof writing skills and build intuition.

Any advice would be extremely helpful. Please let me know if question is unclear or needs more detail.


texts: When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?

texts:
I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of Papadimitriou's textbook.

We are in the function-problem world. The problem CLIQUE-SIZE "given a graph, find the size of its maximum clique" is not thought to be $FP^{NP}$-complete since it can be solved by logarithmically many calls to an NP-oracle through binary search. This puts CLIQUE-SIZE in $FP^{NP[\log(n)]}$, and the problem is known to be complete for this class.

On the other hand, MAX-WEIGHTED-SAT is known to be $FP^{NP}$-complete. This is the problem "given a CNF-formula with binary clause weights, find an assignment maximising the weight of satisfied clauses". Now we seem to be able to solve this question in $O(n^2)$ calls to an NP-oracle, where $n$ is the input size. (See below for why I think this). Hence this problem is in $FP^{NP[n^2]}$, which suggests that $FP^{NP[n^2]} = FP^{NP}$. Is that right? If so, for which (nice) functions $f(n)$ do we have $FP^{NP[f(n)]} = FP^{NP}$?

Krentel (1988, Thm 4.2) shows that (unless $P=NP$) we have $FP^{NP[f(n)]} \subsetneq FP^{NP[g(n)]}$ when $f$ and $g$ are smooth with $f(n) < g(n)$ and $f(n) \le \frac12 \log n$.

(To find a max-assignment in $O(n^2)$ queries: the maximum possible objective value is the sum of all weights. The logarithm of this value is $O(n)$, since all the digits of the individual weights are part of the input. Hence by binary search we can in $O(n)$ calls to an NP "MAX-WEIGHTED-SAT $\ge k$"-oracle find the maximum possible weight. Now go through the $O(n)$ variables in the formula one-by-one, set them false, and check whether this decreased the possible objective value. If so, set it true, otherwise leave it false. Go to the next variable. This takes $O(n^2)$ calls.)


texts: Find the right/best track combination for a given distance, using a genetic algorithm or ?.

texts:
I have a list of tracks (model railroad tracks) with different length, example: TrackA on 3.0cm, TrackB on 5.0cm, TrackC on 6.5cm, TrackD on 10.5cm

Then I want to find out of what kind of track I should put together to get from point A to point B with a given distance and a margin. And I should also be able to a prioritizes the use of track type.

Example; Distance from point A to B is 1.7m, and I have lot of TrackC and few of TrackB. And I will allow a margin on +/- 0.5cm to the distance.

What kind of tracks should I use, and how many of each track, and how many combination do I have, sorted after the track where I have most of.

I have Google after some C# help using genetic algorithm, but I am lost in, how I can implement this in a good method.

Or just a mathematical method, that can solve my problem..

Please help..


texts: What are the consequences of solving XOR 3-SAT in Logspace?

texts:
XOR Formulas

Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR).  Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses.  An $\oplus$-clause contains literals that are connected with $\oplus$.

Example Formula:

$(v_1 \oplus \bar{v_2} \oplus v_3 \oplus v_4) \wedge (\bar{v_1} \oplus v_2) \wedge (\bar{v_2} \oplus v_3 \oplus \bar{v_4})$

Decision Problem

  Name: XOR 3-SAT

  Input: A boolean formula that is a conjunction of $\oplus$-clauses where each clause contains three literals.

  Question: Does there exist an assignment to the variables that satisfies the formulas?

More Background

XOR SAT can be reduced to solving a system of equations over $\mathbb{Z}_2$.  This is because every $\oplus$-clause can be thought of as an equation.  As a result, XOR SAT is solvable in polynomial time using gaussian elimination.

Further, XOR 2-SAT can be reduced to solving reachability in an undirected graph.  This is because every $\oplus$-clause with two literals defines an edge in an undirected graph.  As a result, XOR 2-SAT is solvable in logspace because reachability in an undirected graph is solvable in logspace (because SL = L).

Question

  (1) Is XOR 3-SAT solvable in logspace?

  (2) Are there any known consequences of solving XOR 3-SAT in logspace?

  (3) For example, would this imply that XOR $k$-SAT is solvable in
  logspace?


texts:
Restricted $k$-set cover:

Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$.

Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\},
i_1=min(S_1),i_2=min(S_1\cap S_{i_1}), \cdots, i_k=min(S_1\cap S_{i_2}\cap\cdots\cap S_{i_{k-1}})$

This problem is Restricted $k$-set cover
I want to know the above problem is in L or NL?

I trying to show this problem is in NL-complete. But I did not get  any problem which is NL-complete connects to this problem.


texts: The role of symmetry in geometric complexity theory?

texts:
I'm not well versed in geometric complexity theory so my question could be trivial. I understand that GCT program  studies the symmetries of determinant and permanent to prove Valiant's Hypothesis: $VP\ne VNP$

  In simple terms, What is the invariant property? Which mapping (transformation) is applied to the determinant and permanent? How is the symmetry of permanent used to explain the difficulty of computing the permanent?


texts: Concurrent algorithm for strongly connected components (SCCs)

texts: Is anybody aware of a concurrent version of Tarjan's SCCs algorithm, Kosaraju's algorithm or any other fast, O(|V| + |E|) algorithm for finding SCCs? Neither of those algorithms seem to be very hard to multithread, but I'd be happy for somebody else to have done this job. What I'm trying to handle here is an 8 GB directed graph, which I keep in RAM using a big AWS instance, and I'd like to make a good use of all 16 cores.


texts:
I am interested in the volume of the intersection of two Hamming balls of radius say m/6 in m-dimensional space, the distance between whose centers is about \sqrt{m}. I would ideally like this to be a constant or 1/poly(m) fraction of the volume of the Ball itself and wondering if this is true.

This should be an elementary question and I imagine the answer must be well-known, but I am not able to find this on the interweb. Thanks!


texts:
A differentially private algorithm takes datasets containing inputs and produces randomized outputs, such that no small change in the dataset can shift the distribution of outputs by too much.  This is normally discussed in the context of privacy - when you observe the output, you cannot infer anything about a given input.  But it also implies that an attacker with control over just a single input cannot effectively poison the data to change outcomes.

One might say this is useful only in a very weak threat model, compared to, say, a model in which a constant fraction of (or even most) inputs can be poisoned.  The main assumption would be that it's costly to create new inputs.  But a typical case to want a differential privacy guarantee for is when the unit that the datasets are being measured with respect to is a user of a service, e.g. collaborative filtering settings.

Consider the Netflix dataset, with ~100M ratings from ~500K users, to ~20K movies.  In this case, the average movie has only 5K ratings.  Thus 1% of users being adversarial would negate any real signals - i.e. many malicious users rating a single movie well to boost it may be indistinguishable from normal behavior. A realistic threat model for Netflix might reasonably assume costly account creation.  So the number of poisoned ratings for a given movie is at least proportional to the cost to the attacker.

A more practical attack would be a single user giving bad ratings to all but one movie.  This sort of attack would be mitigated by differential privacy.  Differential privacy has the property of group privacy, which says a group of size $g$ can blow up outcome probabilities by $e^{g\epsilon}$ instead of $e^\epsilon$.  Since cost is assumed to be linear in group size, this would be reasonable for small $g\epsilon$.

Googling for keywords "differential privacy" + "data poisoning" (and variants), I couldn't find a discussion about this, despite many parties being interested in the intersection of privacy and security.  For example, see here, and here.  In the second pdf, there's even a table with differential privacy in the remedy column for the attack on confidentiality, but not in the column for attack on model integrity.  So is there something wrong with my reasoning?

Is my reasoning sound?  Are there any works which discuss a threat model similar to what I'm describing (or is it too silly for serious researchers to consider)?


texts:
In packing problems, we need to select a set of sets of items, such that no item is chosen twice (in $Set-Packing$, the actual items must not be packed twice, in $Graph-Packing$ the copies of the graph has to be vertex disjoint, in multidimensional matching every item has to appear once, etc.).

Are there any studied problems that ask for packing such that every item is packed at most $p$ times?

For example, is there any known reference for (perhaps under a different name?)-

$repetition-Set-Packing$:

given a universe $\mathcal{U}=\{e_1,..,e_n\}$, two numbers $k,r\in \mathbb{N}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that every item in $\mathcal{U}$ appears in at most $r$ sets in $S'$?

Are there any other works on packing with limitied repetitions?


texts:
One of the few things that I dislike about Okasaki's book on purely functional data structures is that his code is littered with inexhaustive pattern matching. As an example, I'll give his implementation of real-time queues (refactored to eliminate unnecessary suspensions):

infixr 5 :::

datatype 'a stream = Nil | ::: of 'a * 'a stream lazy

structure RealTimeQueue :> QUEUE =
struct
  (* front stream, rear list, schedule stream *)
  type 'a queue = 'a stream * 'a list * 'a stream

  (* the front stream is one element shorter than the rear list *)
  fun rotate (x ::: $xs, y :: ys, zs) = x ::: $rotate (xs, ys, y ::: $zs)
    | rotate (Nil, y :: nil, zs) = y ::: $zs

  fun exec (xs, ys, _ ::: $zs) = (xs, ys, zs)
    | exec args = let val xs = rotate args in (xs, nil, xs) end

  (* public operations *)
  val empty = (Nil, nil, Nil)
  fun snoc ((xs, ys, zs), y) = exec (xs, y :: ys, zs)
  fun uncons (x ::: $xs, ys, zs) = SOME (x, exec (xs, ys, zs))
    | uncons _ = NONE
end

As can be seen rotate isn't exhaustive, because it doesn't cover the case where the rear list is empty. Most Standard ML implementations will generate a warning about it. We know that the rear list can't possibly be empty, because rotate's precondition is that the rear list one element longer than the front stream. But the type checker doesn't know - and it can't possibly know, because this fact is inexpressible in ML's type system.

Right now, my solution to suppress this warning is the following inelegant hack:

  fun rotate (x ::: $xs, y :: ys, zs) = x ::: $rotate (xs, ys, y ::: $zs)
    | rotate (_, ys, zs) = foldl (fn (x, xs) => x ::: $xs) zs ys

But what I really want is a type system that can understand that not every triplet is a valid argument to rotate. I'd like the type system to let me define types like:

type 'a triplet = 'a stream * 'a list * 'a stream

subtype 'a queue of 'a triplet
  = (Nil, nil, Nil)
  | (xs, ys, zs) : 'a queue => (_ ::: $xs, _ :: ys, zs)
  | (xs, ys, zs) : 'a queue => (_ ::: $xs, ys, _ ::: $zs)

And then infer:

subtype 'a rotatable of 'a triplet
  = (xs, ys, _) : 'a rotatable => (_ ::: $xs, _ :: ys, _)
  | (Nil, y :: nil, _)

subtype 'a executable of 'a triplet
  = (xs, ys, zs) : 'a queue => (xs, ys, _ ::: $zs)
  | (xs, ys, Nil) : 'a rotatable => (xs, ys, Nil)

val rotate : 'a rotatable -> 'a stream
val exec : 'a executable -> 'a queue

However, I don't want full-blown dependent types, or even GADTs, or any of the other crazy things certain programmers use. I just want to define subtypes by “carving out” inductively defined subsets of existing ML types. Is this feasible?


texts: Hard instances in Impagliazzo's Heuristica

texts:
In Impagliazzo's imaginary world Heuristica, P ≠ NP but all NP problems are easy on average for any samplable probability distribution.

In Impagliazzo's paper, he implies that if you do manage to find a hard instance in Heuristica, it won't take much more effort to solve the instance than it took to find the instance in the first place.

  In
  this
  world,
  Grouse
  might
  be
  able
  to
  find
  problems
  that
  Gauss
  cannot
  answer
  in  class,
  but
  it
  might
  take
  Grouse
  a
  week
  to
  find
  a  problem
  that
  Gauss
  could
  not
  solve
  in
  a
  day,
  and
  a
  year
  to
  find
  one
  that
  Gauss
  could
  not
  solve
  in
  a
  month.
  (Here,
  I
  am
  assuming
  that
  Gauss
  has
  some polynomial
  advantage
  over
  Grouse,
  since
  Gauss
  is
  after
  all
  a
  genius!)
  Presumably,  “real-life”
  is
  not
  so
  adversarial
  that
  it
  would
  solve
  intractable
  problems
  just
  to
  give  us
  a
  hard
  time,
  so
  for  all
  practical
  purposes
  this
  world
  is  indistinguishable  from
  Algorithmica.

However, what I'm not clear on is whether the following scenario is possible: It takes time 1.001n to find a 3-SAT instance that takes time 1.3n to solve.  In other words, Grouse can still maintain an exponential advantage over Gauss provided that Grouse is prepared to invest an exponential amount of work.

Is there a simple argument (or if not, is there a standard complexity hypothesis) that implies that this can't happen in Heuristica?


texts:
You are given a graph $G = (V,E)$ with $n$ vertices. It might be bipartite if you  want. There are $m$ sets of edges $E_1,\ldots, E_m \subseteq E$ (say disjoint). I am interested in the problem of finding a subset $S \subseteq V$, as small as possible (or even smaller), such that the induced graph $G_S$ has at least one edge from each class $E_i$, for $i=1,\ldots, m$.

Currently, I know that this problem is set cover hard. I also have a not completely obvious (roughly) $O(\sqrt{n})$ approximation.

This seems like a natural problem - is anyone aware of any relevant references, or any better algorithms?


texts: What is the time complexity of base conversion on a multi-tape Turing machine?

texts:
Base conversion is the problem of converting an integer between representations in two fixed bases. Without loss of generality consider the case of relatively prime bases. I think it's easier to imagine a single type of machine that can handle all cases even though the bases are fixed, so consider a base-$b$ number as being represented by a concatenation of $\lceil \log_2{(b)} \rceil$-bit words, and let our multi-tape Turing machines have a binary input and output alphabet. But equivalently we can build a machine whose input and output tape alphabet sizes match the source and target bases.

Is base conversion known to be computable in better than essentially quadratic time?

This question has been asked many times but every reference I can find is in a practical context. I have seen claims that it can be accomplished in quasilinear time, but I can't understand how this is supposed to work, in part because assumptions about the model are often unstated in such discussions.


texts: Finding similar vectors in subquadratic time

texts:
Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the similarity function.
Examples of similarity function are
cosine distance, $l_2$ norm, Hamming distance, Jaccard similarity, etc.

Consider $n$ binary vectors of length $k$: $\vec{v} \in (\{0,1\}^k)^n$.

Our goal is to group vectors which are similar.
More formally,
we want to compute a similarity graph where
nodes are the vectors and
edges represent vectors which are similar ($d(v,u) \leq \epsilon$).

$n$ and $k$ are very large numbers, and
comparing two length $k$ vectors is expensive,
we cannot do all brute-force $O(n^2)$ operations.
We want to compute the similarity graph with significantly less operations.

Is this possible?
If not can we compute an approximation to the graph
which contains all edges in the similarity graph
plus possibly at most $O(1)$ other edges?


texts: What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

texts: Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (exponential time hypothesis). I cannot find this talk and am interested in said problems, for I want to look into quantum algorithms for this group of problems during the semester I'm beginning right now.


texts:
The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, the positive rank $rank_{\Bbb R}^+(A)$ is the smallest $m$ such that $A=LR$ for a non-negative $n\times m$ matrix $L$, and non-negative $m\times n$ matrix $R$.

This concept is valuable in communication complexity, since it was shown that if $rank_{\Bbb R}^+(A)$ and $rank_{\Bbb R}(A)$ could be quasi-polynomially related for a $0/1$ matrix $A$, then the log-rank conjecture holds.

Is there an example of a $0/1$ matrix $A$ whose positive rank is strictly smaller than the dimension $m$ of any positive decomposition of $A$ into $0/1$ matrices $L,R$?

I think Theorem 1.1 in http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf answers this.

  Do we know that if non-negative rank and real rank are not quasipolynomially related then the log-rank conjecture fails?

The converse is direct.


texts:
Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$?

If $c=1/2$, this is the famous partition problem which is NP-complete. What is known about the complexity for other values of $c$?


texts: Efficient update of reachable set of a node in a digraph

texts:
Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , $R_{ret}$, from which I can return to $S$.

The issue I have now, is that I need to add and remove edges. I can keep track of the changes in the graph. Note that these changes to the graph only happen locally, i.e. within a given range/distance around a vertex I know.

I have successfully been localizing the update of $R_{reach}$ and $R_{ret}$ for the edges I add to the graph. However, when I remove an edge from the graph one issue arises, that this edge might cut off a subgraph in term of reachability/returnability. I am not sure if it is possible to keep the update of $R_{reach}$ and $R_{ret}$ still local around the known vertex and the given update distance or if it is faster to simply recompute $R_{reach}$ and $R_{ret}$ for the whole graph again using BFS.


texts: Algorithm for finding heavy hitters in a weighted stream

texts:
The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times appear in $\mathcal D$, and no element with frequency lower than $N(\theta-\epsilon)$ belongs to $\mathcal D$. $\epsilon$ and $\theta$ are constant thresholds given as input.

The problem is well studied, with many algorithms developed for it, such as Sticky Sampling, Lossy counting, Batch decrement, and Space Saving. The last two are optimal, in the sense that they require $O(\frac{1}{\epsilon})$ counters and have constant runtime.

I'm looking for an algorithm for a weighted variant of the problem:

Every item in the stream is of a tuple $(id, weight)$, and the goal is the return the elements with the highest weight. All weights are in $(0,1]$.

Formally, a weighted heavy hitters algorithm is required to return all elements whose sum of weights is at least $W\theta$, and no element with weight lower than $W(\theta-\epsilon)$, where $W$ is the sum of weights of the stream elements.

  Are there known (preferably deterministic) algorithms for this problem that use $O(\frac{1}{\epsilon})$ counters and have $O(1)$ runtime?

Batch Decrement and Space Saving does not seem to have a simple generalization to the weighted case, as both maintain a data structure that allows finding the minimum counter in constant time, which might not be doable in the weighted setting.


texts: Where does the modern canonical version of the Turing machine come from?

texts:
Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions:

The Turing machine I learned about was essentially a recognizer: it would either accept or reject input having specified characteristics.  It has an accept or halt final state.  By contrast, Turing describes a computing machine proper--his model computations involve producing and outputting numbers--without any particular halt state--although, for the proof that the Entscheidungsproblem has no solution, he does propose a machine D that would mark as "s" or "u" some other machine based on whether it is circular ("u").  Where does the recognizer view of the Turing machine come from?  Is it the result of later theorists focusing in on the imaginary machine D in Section 8 of Turing's paper?
The version of the Turing machine I got--e.g., from Sipser--required a definition of language as a "set of strings," where a Turing machine would recognize a given input string as belonging or not to some language L.  Where does this idea come from?  Turing's model of computation makes no reference to this concept of "language."  Is it due to Sipser?  Or Penrose?
Turing defines "circular" in a way that seems surprising and counterintuitive today:  "If a computing machine never writes down more than a finite number of symbols of the first kind [i.e., symbols from {0, 1}], it will be called circular."  Suppose you want the machine to compute a + b, where a and b are integers.  This sounds as if a machine that halts when finished computing a number with a finite representation is circular.  Moreover, Turing never explains what is circular in the common sense of the word about such a machine.  Is he just leaving out an argument that the reader is supposed to infer?  Presumably, the argument would go thus:  if we assume (but why?) that the machine should compute a number whose representation is infinite, then, if the machine halts, this can only result from a circularity in the state diagram--either one state leads to itself, without any motion or change of written symbol, or the states follow in a circular sequence with an equivalent result.  That seems to me to presuppose a lot--for instance, that the circularity does not result in any motion beyond the squares already written and that the written symbols remain the same as before.

Was there published work leading up to Turing's 1936 paper already introducing the concept of circularity, so that he could merely allude to it?

Thanks!


texts: Quickly finding empty-string producing nonterminals in a CFG

texts:
For a given context free language G, we call a nonterminal $A_i$ nullable if $A_i \rightarrow^* \epsilon$, ie we can derive the empty string from $A_i$ after applying a finite number of productions.

There is a simple algorithm for determining which nonterminals of a grammar are nullable as can be found here:

We start by considering all nonterminals as not nullable. We mark all $A_i$ as nullable if there is a production $A_i \rightarrow \epsilon$. We then loop over all other productions $A_i \rightarrow B_1 B_2 \dots B_k$ excluding productions with a terminal in them, and mark $A_i$ as nullable if all $B_i$ are nullable. We keep doing this loop until we finish a loop without marking any nonterminals as nullable.

My problem with this algorithm is that it has a $O(n^2)$ running time: a worst case is for instance $A_1 \rightarrow A_2$, $A_2 \rightarrow A_3$, $A_3 \rightarrow A_4$, ..., $A_{n-1} \rightarrow A_n$, $A_n \rightarrow \epsilon$.

  Is there an algorithm for this problem
  with a better running time than
  $O(n^2)$?


texts: Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem

texts:
In [1], Feige proves that if there is a polynomial algorithm with approximation ratio in $o(\log n)$ for any $\mathsf{log\textit{-}APX}$ hard problem (say Minimum Dominating Set), then $\mathsf{NP}\subseteq\mathsf{DTIME}\left(n^{O(\log \log n)}\right)$ .

The paper dates back to 1998. Has any progress been made since this result, i.e., stronger consequences, for example under $ETH$ or $SETH$, or any other plausible conjecture?

[1] Feige, U. (1998). A threshold of $\ln n$ for approximating set cover. Journal of the ACM (JACM), 45(4), 634-652.


texts: Complexity of Uniform Generation of Perfect Matchings

texts:
Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to relations in a "Existence, Construction, Uniform Generation and Counting" hierarchy.

In the case of the of M being a perfect matching in a bipartite graph G, we know that the problems of existence and construction are easy, and the counting problem is #P-Complete. The uniform generation problem is to generate a perfect matching in such a way that all perfect matching have the same probability

¿Is anything know about the problem of uniform generation of perfect matchings?


texts: What is contextual equivalence ignoring non-termination called?

texts:
Contextual equivalence ($M_1 \cong_{ctx} M_2$) is often defined as:
$C[M_1] \Downarrow V \iff C[M_2] \Downarrow V$

Which is to say for any context $C$, $C[M_1]$ terminates with value $V$ iff $C[M_2]$ terminates with value $V$.

Is there a name for the weaker equivalence: $C[M_1] \Downarrow V_1 \wedge C[M_2] \Downarrow V_2 \Rightarrow V_1 = V_2$?

Which is to say $C[M_1]$ and $C[M_2]$ reduce to equal values iff they both terminate.


texts: The complexity of a multi-objective shortest path problem

texts:
I have the following shortest path problem.

Consider a directed graph with $n$ levels.  Each level has $m$ nodes.  Each node at level $i$ is connected to all nodes at level $i+1$.  Let us also make a starting node that is connected to all nodes at level $1$ (the first level).

Each edge is labelled by a pair of non-negative integer weights.  Each level $i$ has a single non-negative integer label which we call $L_i$.

The goal is to minimize the shortest path with respect to the first weight in each edge weight pair from the starting node to the last level while ensuring that the weight of the path from the starting node with respect to the second weight in each edge weight pair is no more than $L_i$ at each level $i$.

Has this problem been studied? Is it known to be NP-hard?


texts: How to model degree variable in logic (new type of modal logic?)?

texts:
I am trying to model domain in logic (first order logic or some of modal logics) and I have variable which is degree and not true-false variable. There can be different conclusions depending on the degree of this variable. How to model such variable? If v ir degree variable and n degrees are possible, then v can be modelled by introduction of n propositional variables v1=true <= v=1, v2=true <= v=2 and so on. Additional constraints (axioms) should be introducted - e.g. only one variable from v1, ..., vn can be true.

Introduction of additional variables is not good, because: 1) it increases complexity; 2) it is not extendable in simple manner.

The question is - maybe there is some syntactic sugar available for degrees, or maybe special logics are already available for handing degrees of even variables whose domain is set of natural numbers?

Prolog and other logical programming environments has this feature, maybe this can be brought back to the theory as well.


texts: Understanding proof of Theorem 3.3 in Karp's "Probabilistic Recurrence Relations"

texts:
Background: In Karp's paper on Probabilistic Recurrence Relations, he develops tail-bounds for random variables satisfying the following recurrence:

$$ T(x) = a(x) + T(h(x)) $$

where $T(x)$ is a random-variable that can be thought of as the cost or run-time of some randomized algorithm when run on an instance of size $x$. Here, $a$ is some deterministic "toll" cost involved in processing the instance prior to a recursive call, and $h(x)$ is a real-valued random-variable in the range [0, x], which gives the size of the instance in the recursive call of $T$.

Assuming the expectation of $h(x)$ is bounded by some function $m(x)$, Karp then considers the deterministic recurrence relation:

$$ u(x) = a(x) + u(m(x)) $$

He then derives various tail-bounds on $T$ in terms of $m$, $a$, and $u$.

Question: My question is about one of the steps in the proof of Theorem 3.3 of the paper. The exact statement of the result is not needed to understand the step I'm stuck on. In this theorem, $a$ and $m$ are assumed to be continuous, there is some $d$ such that $a(x) = 0$ on the interval $[0, d]$, $a$ is strictly increasing on $[d, \infty)$, and $m(x)/x$ is assumed to be non-decreasing.

Karp then defines $K_r(x) = \mathrm{Prob}[T(x) > r]$. He notes that $K_r(x) = E[K_{r - a(x)}(h(x))]$. His goal is to bound $K_r(x)$ by some quantity. To do so, he starts by defining a sequence of functions $K_r^i$ indexed by natural number $i$ as: $K_r^0(x) = 1$ for $r \leq 0$ and $K_r^0(x) = 0$ for $r > 0$; and inductively, $K_r^{i+1}(x) = E[K_{r-a(x)}^i(h(x))]$. He then says that $K_r(x) \leq \sup_{i} K_r^i(x)$, and proceeds to bound each of the $K_r^i$, thus deriving a bound on the supremum and in turn $K_r$.

However, I do not understand why $K_r(x) \leq \sup_{i} K_r^i(x)$. This step is stated without elaboration, so I'm guessing I'm missing something obvious. I see that the $K_r^i$ are defined recursively in terms of the same recurrence about expectation that $K_r$ satisfies, and the supremum of the $K_r^i$ should be a fixed-point of this recurrence, sort of like the construction in Kleene's fixed-point theorem. But that would seem to give a least fixed point, which would justify the opposite inequality: $\sup K_r^i(x) \leq K_r(x)$. I think I see a way to make the argument go through if $\{a(x) | a(x) > 0\}$ is bounded below by some $\epsilon > 0$, but that contradicts the continuity assumption on $a$. Banach's fixed-point theorem would give a unique fixed point, which would do, but I do not see a sense in which this is a contraction.

Other references: this result is mentioned in Chapter 4 of Dubhashi and Panconesi's textbook on Concentration of Measure, but the proof is not included. Chaudhuri and Dubhashi's paper "Probabilistic Recurrence Relations Revisited" proves a similar result but the proof technique is different, so it does not help me understand this argument.


texts: Estimating the number of operations required to factorize a $b$-bit integer using GNFS

texts:
You may skip to question

According to Wikipedia, the complexity of factorizing a number n using the general number field sieve is ("heuristically"):

$ \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\log n)^{\frac{1}{3}}(\log \log n)^{\frac{2}{3}}\right)  $.

Probably big O notation. How could I use that to estimate the number of operations to factorize the number?

As I was taught, exponents and logs in complexity are usually base 2. But for this case Wikipedia shows its "L-notation" too, which uses base $e$, so I don't know if it applies.

My attempt was to compare to msieve's (software) expected time to factor a 512-bit number, 6 weeks (got by scaling a 2009 79 day to break a 512-bit RSA key by Benjamin Moody), and assume an average computer for 5 Giga operations per second and work backwards, all in base 2. I got a correction factor of $1/2^{12.5}$, being the estimation of the number of operations to break a $b$-bit modulus:

$f(b) = 2^{ (7.11b(\log b)^2 )^{1/3}-12.5  }$.

For the said computer ($5\times10^9 \frac{operations}{second}$) it takes aobut 6 weeks to break a 512 bit modulus and for a 768 bit it would take 968 years, which is close of what is claimed about the RSA-768 after scaling (2000 years with a pc at roughly 2.5 GHz)

Question

I estimated the number of operations to factorize a b bit integer using GNFS(by its expected complexity) in:

$f(b) = 2^{ (7.11b(\log b)^2 )^{1/3}-12.5  }$

I'd like to know what is wrong with this estimation or if there is a better equation for that.


texts: Fast weighted intersection algorithm for CFG and FSA with self loops but no other circles?

texts: We all know that arbitrary CFG and FSA can be intersected using the Bar-Hillel Construction, whose time complexity is unfortunately too expensive. On the other hand, there are efficient algorithms that intersects intersect CFGs with lattices (i.e. acyclic FSAs). If an FSA is much like a lattice, except that all circles it can possibly have are self loops, is there any efficient algorithm for intersecting such an FSA with a CFG?


texts: Two valued variant of subset sum problem

texts:
I'm interested in the complexity of the following problem: Given a multiset $S$ containing only two positive integers $a$ and $b$, find a $k$-partition of $S$ that maximizes the sum of part with smallest sum. This a restricted case of the $k$-way number partitioning problem, which is NP-hard. When $k=2$, one can view this as a variant of the Subset-Sum problem, which is also NP-hard in general.
I'm wondering if the additional restriction of there being only two values in the multiset can be leveraged to design an efficient algorithm, or the problem remains NP-hard even with this restriction. For instance, minimizing the makespan (distribute jobs to machines in order to minimize the largest completion time) is polynomial-time solvable when all jobs are of length 1 or 2.
I am interested in the case where $k$ is not constant. When $k$ is fixed, the problem can be solved using linear programming. Concretely, the problem is:
Given a multiset $S = \{a_1,\dots,a_m\}$, where $a_i\in\{a,b\}$ for $a,b\in\mathbb{Z}^{+}$, and $k\in\mathbb{N}$, compute a $k$-partition $S_1,\dots,S_k$ of $S$ which maximizes $\min_i \sum_{a_j\in S_i} a_j$. I am looking either for an algorithm that runs in time polynomial in $m,k,\log a,\log b$, or a proof of NP-hardness.
Any leads would be appreciated!


texts: Near-Sort quicksort algorithm faster than O(nlgn)

texts:
Here, we define a nearly-sorted array with k-sized error, as this:
Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices.
For example:

1, 2, 3, 6, 5, 4, 7, 8, 9

The 6 and the 4 are in the wrong order, and they are 2 indices apart from one another.
The rest of the elements are in order, or of less than 2 indices apart.
So the above array is nearly-sorted with an error size 2.

The question is, how to "tweak" the simple and basic version of the QuickSort algorithm, to have it produce a nearly-sorted array instead of a fully-sorted array, given a certain k, and thereby making it faster than O(nlgn)?

I've been thinking about this for days now, and I can't seem to understand how "ignoring" some of the elements while sorting, in any way, can ever change the run-time complexity of the algorithm, where k is constant?

I could easily just stop the recursion if size < k instead of size < 2, which would indeed make it faster by a tiny bit, and will indeed have possible errors, but wouldn't it still be O(nlgn)?

Any help or direction will be appreciated!


texts: SMT solving with less-than theory and monotonic functions

texts:
I am attempting to solve a less-than theory within an SMT paradigm that involves variables assigned to reals and assumes that all the functions used in the theory are monotonic. The theory's signature has the terms denoted as T and the formulas are denoted as φ. The syntax is given as follows:

$$T = x \mid f(T) \tag{1}$$
$$φ = T < T \mid ¬φ \mid φ ∧ φ \mid φ ∨ φ \tag{2}$$

An example formula in this domain is:

$$(x < y) ∧ (y < z) ∧ ((f(z) < f(y)) ∨ (f(x) < f(z)))$$

How would I begin thinking about how to encode a general formula within the less-than theory as a SAT problem? What is the decision process and encoding algorithm?


texts: IP, MIP and MIP* with super-polynomial verifier

texts:
Regarding each of the above classes, what are the currently known upper bounds when the verifier is given more than polynomial power?
Specifically, when do we reach ALL in each of the above classes with respect to (as a function of) the power of the verifier?


texts: Relative consistency of PA and some type theories

texts:
For a type theory, by consistency, I mean that it has a type which is not inhabited. From the strong normalization of the lambda cube, it follows that system $F$ and system $F_\omega$ are consistent. MLTT + inductive types also has a normalization proof. However, these should all be powerful enough to construct a model of PA, which proves that PA is consistent from these theories. System $F$ is quite powerful, so I expect it to be able to prove the consistency of PA by constructing a model using Church numerals. MLTT + IT has a natural numbers inductive type and should prove consistency as well.

This all implies that the normalization proofs for these theories can't be internalized in PA. So:

Can system $F$, system $F_\omega$, and MLTT + IT actually prove the consistency of PA?
If they can, then what metatheory is needed to prove normalization for system $F$, $F_\omega$, and MLTT+IT?
Is there a good reference for the proof theory of type theories in general, or for some of these type theories in particular?


texts: Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

texts:
This is a specialized version of a previous question:
    Complexity of Finding the Eigendecomposition of a Matrix .

For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the eigen decomposition.  The question is: can we achieve sub-cubic complexity?  Thanks.


texts: Justifying the state of virtual memory as a vector space

texts:
First, I'm mostly experienced with Math, which I hope won't be too inconvenient.

I saw Operational Calculus on Programming Spaces by Sajovic and Vuk, which seemed very interesting to me (for a "short summary" of the paper, the Wikipedia article on Automatic Differentiation may be helpful).  I had a few questions about how they defined their "memory space of the program".  The relevant section is below:

  We will model computer programs as maps on a vector space. If we only focus on the real
  valued variables (of type float or double), the state of the virtual memory can be seen as a
  high dimensional vector. A set of all the possible states of the program’s memory, can be
  modeled by a finite dimensional real vector space $\mathcal{V} \equiv \mathbb{R}^n$. We will call $\mathcal{V}$ the memory space
  of the program.
  The effect of a computer program on its memory space $\mathcal{V}$, can be described
  by a map
  $$P : \mathcal{V} \to \mathcal{V}$$
  A programming space is a space of maps $\mathcal{V} \to \mathcal{V}$ that can be implemented as a program in
  specific programming language.

I understand how $\mathcal{V}$ should be some finite object - I don't understand why this should specifically be a vector space.
One analogy that may be useful for this is the following.  $C(\mathbb{R})$ denotes the set of all continuous functions $f:\mathbb{R}\to\mathbb{R}$. While continuous functions themselves aren't linear, we can define addition of continuous functions and scalar multiplication of continuous functions in a linear way by defining:
$$(f+g)(x) \stackrel{def}{=} f(x) + g(x)$$
$$k\cdot f(x) \stackrel{def}{=} (kf(x))$$
Something similar to this undoubtedly works for programs on $\mathcal{V}$ - for a given state $s$, define $p_1 + p_2$ evaluated on $s$ as $p_1(s) + p_2(s)$.  While this (likely) leaves us with a Banach space, I'm unsure if it's the correct interpretation.

This would give us that the sum of two programs $p_1,p_2$ applied to some state $s$ is just $p_1(s) + p_2(s)$.
So, looking at a single component of $p_1(s) + p_2(s)$, we have that the action of $p_1 + p_2$, as a program, is just the sum of the individual actions of $p_1$ and $p_2$ on the initial state.  This seems like an odd interpretation for me - for whatever reason it'd seem much more natural to have the way to combine programs to be function composition, but this would lead to problems like $+$ not being commutative, and scalar multiplication being harder to define.

In this paper, what's the correct interpretation of addition here?  The "usual" addition seems to lead to the correct mathematical construct, but I'm having a hard time understanding what the "program sum" is supposed to model in real life.

Edit: This Reddit Post seems to have some commentary on it which may help others.


texts: Is anything known about NC$^1$ with NP oracle

texts:
A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the other hand, I can't find much about the class $\textsf{NC}^1$ with access to an $\textsf{NP}$ oracle. Is it because the use of an oracle doesn't play well with the definition of $\textsf{NC}^1$? Which I doubt. Most likely, it's because I haven't looked properly.
Except for the direct $\textsf{NP} \cup \textsf{coNP} \subseteq {\textsf{NC}^1}^{\textsf{NP}} \subseteq \Theta_2^{\textsf{P}}$, What is known about ${\textsf{NC}^1}^{\textsf{NP}}$?
[1] Wagner, K. W. (1988, July). On restricting the access to an NP-oracle. In International Colloquium on Automata, Languages, and Programming (pp. 682-696). Springer, Berlin, Heidelberg.


texts:
I'm looking for an implementation of Boltzmann sampling for combinatorial structures.

Recent paper in the area for context:

http://hal.inria.fr/docs/00/74/77/09/PDF/NonRedundantGeneration-TCS-2010.pdf

Any good packages out there that don't rely on Maple?


texts: UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?

texts:
Background:

In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary alphabet admits an assignment satisfying 1-$\epsilon$ of the constraints or whether there exist no assignments satisying $\frac{8}{9}+\epsilon$ of the constraints, for arbitrarily small $\epsilon > 0$.

I'm curious whether this result has been generalized for any combination of $\ell$-ary constraints for $\ell \ge 3$ and variable domains of size $k \ge 3$ where $\ell \ne k \ne 3$. That is,

Question:

Are there any known hardness of approximation results for the predicate $NAE(x_1, \dots, x_\ell)$ for $x_i \in GF(k)$ for $\ell, k \ge 3$ and $\ell \ne k \ne 3$?

I'm especially interested in the combination of values $\ell = k$; e.g., the predicate Not-all-equal($x_1, \dots, x_k$) for $x_1 \dots, x_k \in GF(k)$.