texts: Metric graph theory database search algorithms

texts:
I am (slowly) writing a review of the Handbook of Chemoinformatics Algorithms for SIGACT News.  One chapter discusses current software implementations, and the database searches (and other applications) don't seem to take advantage of as much information about the graphs as they could.  On the other hand, perhaps more theoretical algorithms would be too hard to implement.  It seems like a potential open area, though.

So here's my question:

Is there an overview (or a small handful of references) that discusses theory and implementation (hopefully) of algorithms of databases of graphs with metric information?  (Each edge is a distance, and each vertex has a volume.)  A chemistry-free description of an example problem would be: given a database of graphs, find all of them that contain a particular subgraph.


texts: Counting complexity of a scheduling problem.

texts:
Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements $\pi$, such that $\sum_{i=1}^k p_{\pi(i)} \le d_{\pi(i)}$ for all $k=1,\ldots,n$.

Does there exist a pseudo-polynomial time algorithm for computing the total number of feasible schedules?

A pseudo-polynomial time algorithm is an algorithm whose running time is bounded by a polynomial on the size of the input, given that the input is written in unary notation (2 = II, 3 = III). (e.g., the size of a number n in unary notation is $O(n)$, and not $O(\log(n)))$.


texts:
Let $F$ be an integer valued function such that $2F$ is in $\#P$.  Does it follow that $F$ is in $\#P$?  Are there reasons to believe this is unlikely to always hold?  Any references I should know about?

Somewhat surprisingly, this situation came up (with a much larger constant), for a function $F$ for which $F \in? \#P$ is an old open problem.

Note: I am aware of the paper M. Ogiwara, L. Hemachandra, A complexity theory for feasible closure properties where a related division-by-2 problem has been studied (see Thm 3.13).  Their problem is different however, as they define the division for all functions via the floor operator.  That allowed them to make some quick reductions to parity problems.


texts: Gradient descent on k nearest neighbor graph

texts:
I wanted to know how gradient descent can be used to minimize the distance function in approximate k nearest neighbor algorithm as mentioned in paper "Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures" by Dong et al. where the author says "The approximate K-NNG can be viewed as K × N functions, each being the distance between one of the N objects and its k-th NN. The algorithm is simply to simultaneously minimize these K × N functions with the gradient descent method, hence the name “NN-descent”. https://www.cs.princeton.edu/cass/papers/www11.pdf
Like is there some regression formula or thing based on weights associated with neighbors closer to query that can be used to describe gradient descent in this case


texts: What's the upper bounds for #3-SAT circuits?

texts:
We have, from this thread on 3-SAT upper bounds, and this answer on #P that the current best upper bounds for 3-SAT is faster than $O(1.31)^n$, and approximately $O(1.64^n)$ for #3-SAT.

Can we do better for 3-SAT and #3-SAT circuits?

The reason I ask is that I've been fiddling with a circuit that achieves a modest improvement over the #3-SAT upper bounds mentioned above.  But since it's a circuit, I have my doubts that it's even worthwhile.  So I'm wondering:  what kind of circuit upper bounds can we get?


texts: Has the compactness theorem for FOL been formalized in Coq/Isabelle/etc?

texts: I've been searching for a formalization of the compactness theorem for FOL, but haven't found any. Is anyone aware of such a development or related work?


texts:
When we look at the book, Homotopy Type Theory - we see the following topics:

Homotopy type theory
2.1 Types are higher groupoids
2.2 Functions are functors
2.3 Type families are ﬁbrations
2.4 Homotopies and equivalences
2.5 The higher groupoid structure of type formers
2.6 Cartesian product types
2.7 S-types
2.8 The unit type
2.9 P-types and the function extensionality axiom
2.10 Universes and the univalence axiom
2.11 Identity type
2.12 Coproducts
2.13 Natural numbers
2.14 Example: equality of structures
2.15 Universal properties

Now we know that not all of homotopy type theory is possible is Agda and Coq.

My question is: What parts of homotopy type theory are not possible in Agda or Coq?


texts: Has Khachiyan/Porkolob's convex integer optimization been implemented?

texts: Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ over integer points in a convex set in $\Bbb R^k$. Has this ever been implemented in any package?


texts: Entropy criterion of efficiency for (comparison using hashing)

texts:
I understand that hash is effective iff the "domain" size is smaller than the size of the "general set" - set of all possible objects.

E.g., "domain" is the set of valid english phrases with length 1000, and "general set" is the set of all possible strings with length 1000.

Roughly speaking, hashes just project our objects from giant and almost-empty "abacus" desk to much more smaller one.

Question: Is there a smart criterion (expressed in therms of Kolmogorov complexity theory, Shannon entropy), which we could use to be sure that comparison operation will be more effective using hashes?


texts: VNP is closed under taking coefficients using Valiant's criterion

texts:
We consider the family of polynomials

$$\{f_n(x_1,\dots,x_n,y_1,\dots,y_n)\}\in\mathsf{VNP}$$

We want to show that the family

$$\{h_n(x_1,\dots,x_n)\}$$

is in $\mathsf{VNP}$. Where $h_n(x_1,\dots,x_n)=[\text{coefficient of } y_1\cdots y_n \text{ in } f_n]$.

From Valiant's criterion it is enough to show that given any vector of exponents
$$e=(e_1,\cdots,e_n)$$
we can efficiently (in $\mathsf{\# P/Poly}$) compute the coefficient of the monomial $x_1^{e_1}\cdots x_n^{e_n}$ in $h_n$. But this is exactly the coefficient of the monomial $x_1^{e_1}\cdots x_n^{e_n}y_1\cdots y_n$ in $f_n$.

I now want to say that it can be efficiently computed since $\{f_n\}\in\mathsf{VNP}$, but I feel it is the other direction of Valiant's criterion which we cannot use.


texts: Why would a TCS researcher need funding?

texts:
I was reading this. It says

  ... You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)...

Why do pure mathematicians need funding?(Ooops its mathoverflow  question)

Why would someone doing theoretical research need funding?

I think tools of trade are papers, pencils, a laptop with good internet connection and a printer(?).

Please enlighten me! :-)


texts: Edges in a graph with girth greater than 4

texts:
According to the following paper by Füredi, the maximum number of edges for a graph with $n$ vertices is upper bounded by $O(n^{\frac{3}{2}})$, where the leading co-efficient of the term $n^{\frac{3}{2}}$ is $\frac{1}{2}$. The paper also provides examples of graphs, for certain special values of $n$, where the number of edges exactly equal to the upper bound.

I wanted to know there exists graphs G(V,E) ($|V| = n $) for all values of $n$ such that

$$\Big|E - \small{\frac{1}{2}}n^{\frac{3}{2}}\Big| = o\big(n^\frac{3}{2}\big)$$


texts: Lower Bound Methods in NonDet Communication Complexity

texts:
rank+($M$) is the minimum $r$ such that the following statement holds.

The statement : there exists matrices $U,V$ such that $M = UV$ and $U$ has $r$ columns and $V$ has $r$ rows.

Is rank+($M$) bounded from below by the rectangle covering bound for $M$ ?


texts: Why isn't the Charikar algorithm for finding the densest subgraph optimal?

texts:
I read about the algorithm in
Greedy Approximation Algorithms for Finding
Dense Components in a Graph by
Moses Charikar,
and I tried to find an instance/graph where the algorithm returns a different solution from the optimal one but I didn't succeed.
Can anyone provide me an example where the algorithm 'fails' and proves that the approximation is no less than 2?


texts: List of (unsolved) complexity problems arising from PL

texts: What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time complexity of Hindley-Milner type inference" or "the time complexity of 0CFA" (though both are solved problems).


texts: Reference Request: Surveys on attacks on security schemes

texts:
I am new to provable security and am working on cryptanalysis of a certificate free signature scheme.

Unfortunately, I don't have much knowledge about finding attacks on schemes. It would be very helpful if someone can point me to a survey or other reference to study about cryptanalysis and basically develop some intuition to attack an scheme.


texts: Is it #P-hard to compute the number of antichains of a distributive lattice?

texts:
An antichain of a poset $(P, <)$ is a subset of pairwise incomparable elements, namely, a subset $A \subseteq P$ such that there are no $x, y \in A$ with $x < y$. By a result of Provan and Ball, it is known that it is #P-hard, given a poset, to compute its number of antichains.

My question is whether this hardness result is known to extend to restricted classes of posets. More specifically, I am interested in posets which are distributive lattices. Is it #P-hard to count antichains in distributive lattices?

Of course, one could also ask for which classes of posets is hardness, or tractability, known to hold. Has there been any work on this since Provan and Ball?


texts: Coupon collector - the effect of randomization

texts:
Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x _i$ is the element drawn at the $i^{th}$ draw. In here, $k = n H_n$ following the standard solution of the coupon collector problem.

Note that $x _k$ have been seen only once. We create the $S'$ = $\{S - x _k\}$ and $X' = \{X - x _k\}$. We shuffle $X'$ and get a shuffled series $\{p(x'_1), ..., p(x' _{k-1})\}$, where $p(x' _i)$ is the $i^{th}$ drawn element from the shuffled set $X'$. What is the smallest index $m$ such that the sequence $\{p(x' _1), ..., p(x' _m)\}$ contains all elements in $S'$ ?

Can we simply assume that $m = (n-1) H _{n-1}$ following the same logic of coupon collector ?  or is $k$ is too small to assume that the distribution of $X'$ is uniform ?

If not, then what is the expected value of $m$ ?


texts: Lattice generation inside d-dimensional unit ball

texts:
I am interested to know if there is a standard algorithm for generating all the lattice points inside the $d$-dimensional unit ball (with respect to the $\ell_2$-norm).

The brute force approach is to generate the lattice over the $\ell_\infty$ unit ball and then loop through each of the points and remove those with norm strictly greater than $1$. I was wondering if there is a more elegant approach to solving this problem. My initial thoughts are to attempt to cover the $d-1$ dimensional sphere with $n$ points and try and use those points to find out the "limits" that I can then use to generate the lattice coordinate vectors. Then I would define the lattice over the intervals defined by these limits $[a_1,b_1] \times [a_2,b_2] \times … \times [a_d,b_d]$. However, in my mind it is non-trivial to decide how many points to put on the sphere and the algorithm for actually determining the aforementioned limits.

Another approach would be to think of what are the coordinates of the maximum volume polyhedron that can be inscribed in the ball and then somehow constrain them to be on the lattice...Again, this seems to be non trivial. A similar line of thought would be to find the minimum volume polyhedron in which we can include the unit ball by enforcing the constraint that its vertices are lattice points. Then we can just subtract the distance between two lattice points and end up inside the sphere...

Are any of these problems with known solutions/non-trivial to solve?

Thank you in advance.


texts: Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

texts:
minimize/maximize $\displaystyle \sum_{i=0}^{f(n)} G(x,n)$
s.t. $n \ge 1$ and $x$ in some feasible region

The decision variables are $x$ (a vector) and $n$ (a scalar).
How is this type of optimization problem classified?
Has it been studied? Any references?

Here is an example of how an unconstrained version of the problem arises:

"Optimizing capacity of buses, K, on a bus route"

The bus route is a loop. One point on
the loop is designated the “bus
station,” the only place passengers
can get on the bus.
Passengers can get off the bus at any
point on the bus route (other than
the bus station).
By the time a bus returns to the bus
station, all of its passengers will
have gotten off.
Passengers arrive by a Poisson
process with rate lambda (per hour).
A bus cannot take off from the bus
station until it has K passengers on
board.
There are N buses that operate on the
one route. When a bus arrives at the
bus station, it waits in line behind
buses that are already there. It’s a
FIFO system where the first bus in
line gets first K arriving
passengers, and so on…
When a passenger arrives at the
station, s/he gets on the first bus
in line and waits until enough
passengers have gotten on the bus to
make a total of K passengers before
the bus takes off. Passengers get on
the bus in a FIFO manner as well.
The waiting time for a passenger is
the length of time from when that
passenger arrived at the bus station
until a bus with that passenger on
board takes off.
The waiting time for a bus is the
length of time from when the bus
arrives at the station until it has K
passengers on board, at which point
it takes off.
It is assumed that the “loading” of
passengers takes zero time.
Also, it takes C(K) time for buses to
travel the length of the bus route. This is a function of K because there is time lost for each passenger that is dropped off.

What is the expected waiting time for passengers? For buses?

The optimization aspect is as follows. Bus drivers want to make the most amount of money in an hour. The higher K is, the more money a bus driver makes per trip on the bus route, but the number of trips per hour goes down. There is a monetary cost (to bus drivers) for each minute that a passenger waits at the stop for a bus (as in loss of goodwill). So the objective function is dependent on both the expected waiting time of buses (which determines how much money buses make per hour) and the expected waiting time of passengers.

I was able to get an expression for the expected waiting time of buses and it is of the form:

E[Waiting time for a bus] = $\displaystyle\sum_{j=0}^{KN} \frac{KN-j}{\lambda}\frac{(\lambda C(K))^j}{j!}e^{-\lambda C(K)}$

E[Waiting time for a passenger] = ??

I have not been able to get an expression for the waiting time of passengers, but I suspect it will also have the upper bound of summation as some function of K.


texts: Reducing redundant edges from a dependency graph

texts:
I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal sub graph.

For example:

A -> B -> C
A -> C

in words A is prerequisite to B, and B is prerequisite to C, and also A is prerequisite to C. In this case A -> C is redundant (since B is already necessary to reach C, and A is necessary to reach B).

Its been a while since I studied algorithms, and I'm not sure where to start.

By the way, its not critical that the algorithm finds the global minimum, local minimum is fine (the edge reduction is only a runtime optimization for next stage of processing).

Also, I realize this is a CS QA and not programming, but my program is written in Python, so I would be extra happy to learn of a python module or open source for doing this reduction, just in case you know of it.

thanks in advance!


texts: Finding the number of independent rows of a matrix

texts:
There is a $n\times n$ matrix $A$, and we are asked to find the number $N(A)$ of independent rows in it, i.e. rows that are not a linear combination of the other rows. Clearly, if $rank(A)=n$, then $N(A)=n$, but for $rank(A)=n-1$  $N(A)$ can be anywhere between $0$ and $n-1$.

A straightforward way to check if a row is independent is to check if removing it from $A$ lowers the rank of $A$. Assuming calculating rank requires $O(n^\alpha)$ operations, calculating $N(A)$ this way would require $O(n^{\alpha+1})$. Are there more efficient ways to find $N(A)$?


texts: Pseudorandom generators indistinguishable by uniform deterministic adversaries

texts:
I've seen pseudorandom generators defined for nonuniform efficient adversaries, or uniform probabilistic efficient adversaries.  (For example, a monograph Pseudorandomness by Vadhan (here's its draft does that.)

I believe that it's natural to think about pseudorandom generators indistinguishable by uniform deterministic efficient adversaries.  Has that notion studied before?  Does it have any significance to some degree?

EDIT: I was mistaken in that Vadhan defined pseudorandomness against uniform probabilistic adversaries: he did define indistinguishability by uniform probabilistic algorithms, but he neither defined, nor stated facts about, the corresponding notion of pseudorandomness.  My interest mostly concerned with uniform adversaries and my original question was about deterministic vs. probabilistic.


texts: I understand that the purpose of the alphabet reduction step in Dinur's proof of the PCP theorem is to reduce the alphabet after the graph powering stage. However, I don't see why the alphabet needs to be reduced- it is still a constant (though larger), and it seems that the graph powering step can be reapplied even with a larger alphabet size. Since the process is repeated logarithmically many times, the ending alphabet size will be polynomial in the input size. Please let me know what I am missing.


texts: Why has hypercomputation research died down?

texts: I see a lot of research on hypercomputation in the 1990's, but in more recent years there seems to be little work on the topic. Is it true that research in this area has died down? If so, what could be the reasons for it? Was this area convincingly shown to be unpromising?


texts:
I am looking for a bound on the entropy $H(X+Y)$ of the sum of two independent discrete random variables $X$ and $Y$. Naturally, $$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$$ However, applied to the sum of $n$ independent Bernoulli random variables $Z_1, \ldots, Z_n$, this gives
$$ H(Z_1 + Z_2 + \cdots + Z_n) \leq n H(Z_1)  $$ In other words, the bound grows linearly with $n$ when applied repeatedly. However, $Z_1 + \cdots Z_n$ is supported on a set of size $n$, so its entropy is at most $\log n$. In fact, by the central limit theorem, I'm guessing that $H(Z_1 + \cdots + Z_n) \approx (1/2) \log n$ since it is essentially supported on a set of size $\sqrt{n}$.
In short, the bound $(*)$ overshoots by quite a bit in this situation. From perusing this blog post, I gather all sorts of bounds on $H(X+Y)$ are possible; is there a bound that gives the right asymptotics (or, at least, more reasonable asymptotics) when applied repeatedly to the sum of Bernoulli random variables?


texts: A proved computationally-irreductible function

texts: In arXiv:1111.4121 and arXiv:1304.5247, Hervé Zwirn and Jean-Paul Delahaye propose a formal definition of computational irreducibility. Is there a (possibly artificial) function that can be proved to be computationally irreducible? I would accept an answer based on an alternative formal definition.


texts:
Is there a standard macro package, or just standard set of macros, for
  formatting decision problems in LaTeX?

A decision problem is presented via the data "problem name", "instance", and "question", with the latter always having a yes or no answer.  For example FACTOR has, as an instance, a pair of positive integers (n,p) and has, as its question, "Does n have a factor less that q and greater than one?".  Here is an attempt to format FACTOR in HTML.

FACTOR
Instance: $(n,q) \in \mathbb N \times \mathbb N$
Question: Does $n$ have a factor bigger than one and less than $q$?

In the interest of not reinventing the wheel, I asked google, and found some homegrown macros, each with their own spacing, choice of fonts, and layout.  Has anyone implemented a standard?  Say, a standard journal in complexity theory?

For quite old examples of formatting choices see Karp's classic paper Reducibility among combinatorial problems, starting on page 89 (using the page numbers in the book, not in the pdf file).  The book Computers and intractability by Garey and Johnson also gives many decision problems - see page 25 of the linked text.  I've seen more recent texts where the problem name is in small caps, and the boiler-plate on the instance and question lines is in italics.

For a more recent example, I found a macro written for use by students in a cs class - see lines 95 to 116.

Finally - I tried asking over at the TeX Stack Exchange site, but didn't get any answers.  I've deleted the question there, and moved it over here.


texts:
Input: A single long string (<10MB) and a number k

Definition: A unique k-substring is a substring of length k, which occurs exactly once in the input document.

Output (Approach 1): Either print each unique k-substring OR

Output (Approach 2): Output a DFA which matches unique k-substrings in the given document in a streaming fashion (KNP-style search)

Given a large string, I'd like to preprocess it find a "fingerprint" of all fixed-length (say, length 20) unique substrings. These are typically phrases specific to the document.

Then, I want to use find approximate copies of the document inside other documents. I have this process working already, it's just too slow.

So far, I've been looking at suffix tries and KNP-style search. Aho-Corasick algorithm adapts KNP to recognize multiple strings, and Incremental String Match, further allows adding strings while running. If I add removing search strings while running I think I'll be at a solution, but this is quickly getting complicated for a problem with such simple structure.

Is there a simpler algorithm / data structure, or a known one?


texts: Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

texts: What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?


texts: Status of constant-depth isomorphism in $AC^0[\oplus]$

texts:
In [1], Agrawal proved the following:

  For any complexity class $\mathcal{C}$ closed under $NC^1$ reductions, problems complete for $\mathcal{C}$ under $FO$ reductions are isomorphic via an isomorphism computable in $FO$.

This is a derandomized construction of a non-uniform $AC^0$ isomorphism theorem due to Allender, Agrawal & Rudich [2].

I am curious if any work has been done regarding isomorphism with respect to $AC^0[\oplus]$ reductions.

The only strategy we have to construct an isomorphism (that I've seen) essentially employs a resource-bounded Schroder-Bernstein argument, which requires that completeness of a problem $A$ for $\mathcal{C}$ under, say, $r$ reductions (where $r$ is a complexity measure) implies completeness of $A$ for $\mathcal{C}$ under 1-1, length-increasing, invertible $r$ reductions. So I'd be specifically interested in results of the following form:

  $A$ is $\leq_m^{AC^0[\oplus]}$-complete for $\mathcal{C}$ $\implies$ $A$ is $\leq_{P}^{AC^0[\oplus]}$-complete for $\mathcal{C}$ where property $P$ is some combination of $\{$1-1, invertible, length-increasing$\}$

Sources:

Manindra Agrawal, The First-Order Isomorphism Theorem. FSTTCS 2001, LNCS 2245: 70-82.
Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. JCSS 57: 127-143, 1999.


texts: Is there is an intuitive explanation why call-by-name PCF is less expressive than both call-by-value PCF and lazy PCF?

texts:
J.C. Mitchell cites in his "Expressive power of programming languages" the result in Riecke's "Fully abstract translations between functional languages" about the call-by-value, call-by-name and lazy versions of the language PCF.

He mentions: In lazy PCF, call-by-name evaluation order is used, but additionally termination is observed using some convergence-testing language primitive.

In general terms, he says, the main results are that call-by-value and lazy PCF are equally expressive (apparently shown in Riecke by means of an abstraction-preserving reduction), and both are more expressive than call-by-name PCF.

The first part, of this previous statement is intuitive. The second is not yet to me.

EDIT: Removed some nonsense I had written earlier.


texts: Is there an accepted name for Ross Quinlan's adaptation of the ID3 decision algorithm to use a Pearson's chi-squared test for independence?

texts:
In Ross Quinlan's seminal paper Induction of Decision Trees, Quinlan summarizes the current state of machine learning in 1985 and loudly introduces the ID3 decision algorithm in the context of its peers in the field. However, he also states this halfway into the paper:

  An alternative method based on the chi-square test for stochastic independence has been found to be more useful.

And further in:

  Hart notes, however, that the chi-square test is valid only when the expected values of $p' i$ and $n'i$ are uniformly larger than four. This condition could be violated by a set C of objects either when C is small or when few objects in C have a particular value of some attribute, and it is not clear how such sets would be handled. No empirical results with this approach are yet available.

The name for this modification of the algorithm is not given, though. Is there an accepted name for this modification of ID3 (which is usually dependent on Shannon entropy to perform branching)? It seems like something that should be obvious (eg, ID3.1.x), but I cannot find a formal source.

I've also taken the liberty of perusing and studying the meta links within the FAQ of this fine site, and this didn't seem to fall into any of the bins for obviousness or non-research level, nor did it appear to be a good fit for other StackExchange sites. It is, however, a simple question that I could not find the answer to in any of the common sources.

This is directly pertinent to my research: I'm compiling another optimization that bridges the gap between generalized Shannon mutual information and Pearson's chi-squared test for independence in the context of TDIDT, then applying it to multivariate characteristics in cancer data as an alternative to random forests. As such, working definitions for my terms are greatly useful, insofar as they might lead to further papers I am not familiar with.


texts:
Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$.
Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on the number of simple $st$-path using those edges.

If I see  the grid as a box in the plane, I can visualize an $st$-path as a rectilinear curve cutting this box. In this way I can associate each cell of the grid to either one or the other partition, getting as a trivial upper bound the value of $2^{n^2}$.
Is there any better?

I also thought that, if I am considering only the paths using the $k$ given edges on the upper line, then I can map each of these paths to a cut of the grid graph into $k+1$ partitions.
Do you know whether any non-trivial upper bound on this number is known?

Thanks for the help!


texts: Boolean formula balancing in $\mathsf{AC^0}$

texts:
I am looking for references about the complexity of Boolean formula balancing problem. In particular,

Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$?
Is there a simple proof of Boolean formula balancing being in $\mathsf{AC^0}$?

By "simple" I mean a proof simpler than the one I mention below, in particular I am looking for a proof which doesn't depend on Boolean formula evaluation being in $\mathsf{NC^1}$.

Background
Here all mentioned complexity classes are the uniform ones.

BFB (Boolean formula balancing):
Given a Boolean formula $\varphi$,
Find an equivalent balanced Boolean formula.

I am interested in the complexity of this problem, in particular simple proofs showing the problem is in $\mathsf{AC^0}$ (or even $\mathsf{TC^0}$ or $\mathsf{NC^1}$). The common balancing arguments like those based on Spira's lemma apply repeated structural modifications to the formula tree which seem to only give $BFB \in \mathsf{NC^2}$.
I have a proof for $BFB \in \mathsf{AC^0}$, however the proof is not simple and depends on the proof of $BFE \in \mathsf{NC^1}$.

BFE (Boolean formula evaluation)
Given a Boolean formula $\varphi$ and a truth assignment $\tau$ for variables in $\varphi$,
Does $\tau$ satisfy $\varphi$ ($\tau \vDash \varphi$)?

It is known from Sam Buss's celebrated result that Boolean formula evaluation ($BFE$) can be computed in $\mathsf{NC^1} = \mathsf{ALogTime}$ (see [Buss87] and  [BCGR92]).
It follows (quite surprisingly, at least to me) that Boolean formulas balancing ($BFB$) is also in $\mathsf{NC^1}$:
The idea is that we can hardcode $\varphi$ in the input gates of $BFE$ to obtain a formula equivalent to $\varphi$ and this is a completely syntactic operation computable in $\mathsf{AC^0}$. Since $BFE$ has balanced formulas we obtain a equivalent balanced formula for $\varphi$. In other words, the algorithm is:
$$\ulcorner \varphi \urcorner \mapsto \ulcorner \lambda \vec{p}. Eval(\ulcorner \varphi \urcorner, \vec{p} )\urcorner$$
Motivation
A simpler argument for $BFB$ being in $\mathsf{AC^0}$ (or $\mathsf{TC^0}$ or even $\mathsf{NC^1}$) would give a new simpler proof of $BFE \in \mathsf{NC^1}$ since it is easy to see that the balanced version of BFE can be solved in $\mathsf{NC^1}$ and we can compose it with $BFB$ and the result will be in $\mathsf{NC^1}$.

Questions

Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$ ($BFB\in \mathsf{AC^1}$)?
Is there a simpler argument (e.g. not relying on $BFE\in \mathsf{NC^1}$) for $BFB\in\mathsf{AC^0}$?


texts:
I'm confused about the example given in Wikipedia article about Context-sensitive grammar:

https://en.wikipedia.org/wiki/Context-sensitive_grammar

Disclamer: I've already changed discussed section in wikipedia article, so current state of article will differ from what I'm discussing in this question. Original version is here: https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=747616366

  The following grammar, with start symbol S, generates the canonical
  non-context-free language { anbncn : n ≥ 1 } :

  S       →       a   b   c
  S   →   a   S   B   c
  c   B   →   W   B
  W   B   →   W   X
  W   X   →   B   X
  B   X   →   B   c
  b   B   →   b   b

They do not claim directly that this grammar is context-sensitive, but next sentence implies that that they consider it as context-sensitive:

  rules 3 to 6 allow for successively exchanging each cB to Bc (four
  rules are needed for that since a rule cB → Bc wouldn't fit into the
  scheme αAβ → αγβ)

So they appeal to the canonical form of context-sensitive grammar rules: αAβ → αγβ, implying that whole grammar is context-sensitive.

What I'm confused about is rule #3, which seems to be not fitting scheme αAβ → αγβ. I consider terminal $c$ here as part of $\alpha$, variable $B$ as $A$ in scheme, $\beta$ is empty. This implies that $cB$ can not produce $WB$, as $c$ should be saved on same place ($cB\rightarrow c\dots$).

Did I missed something or this grammar was really placed here mistakenly (as it is not real context-sensitive)?


texts: KRW Conjecture: separation of NC^1 and P

texts:
More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more than welcome. I am trying to get a grip on the KRW Conjecture, which is aimed at proving $NC^1 \neq P$.
What I figured out is that the main goal of the whole question is:

Find a boolean function $f$ such that $D(f) = \omega(\log(n))$, where $D(f)$ is the depth complexity of $f$ – the depth of the shallowest circuit computing $f$.

This would imply  $NC^1 \neq P$ since it would prove the existence of a function $f$ which can be computed with a circuit of polynomial size but cannot be computed with a circuit of polylogarithmic depth:

$\exists\ f:\{0,1\}^n \rightarrow \{0,1\}\ |\quad f \in P/\mathrm{poly}$ and $f \notin NC^1$.

So we need tools to prove super-logarithmic lower bounds for boolean functions.
To do so we can relate Circuit Complexity to Communication Complexity via the KW relations. Indeed it has been proved that every boolean function yields a KW relation defined as follows:

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a boolean non-constant function.
Alice receives $x \in f^{-1}(0)$.
Bob receives $y \in f^{-1}(1)$.
Their aim is to find $i$ such that $x_i \neq y_i$.

The reason why we want (and why it is possible) to relate circuits to KW relations is that it was proved what follows:

$D(f) = CC(KW_f)$, where $CC(KW_f)$ is the amount of bits communicated over a protocol solving $KW_f$.

Being communication problems, it is possible to prove lower bounds for KW relations using the Communication Complexity framework.
The aim of Communication Complexity is to study the amount of communication, in terms of bits transmitted, required to solve a communication problem using a communication protocol, which is basically an algorithm stating the rules of the conversation.
For what it has been said until now we can establish a deep connection between circuits and protocols: Communication Complexity supplies a different point of view on the $NC^1 \neq P$ problem.
The first and most basic tool that comes from Communication Complexity are combinatorial rectangles:

A set $R \subseteq X \times Y$ is a (combinatorial) rectangle if $R = A \times B$ for $A \subseteq X$ and $B \subseteq Y$.
Furthermore, given a function $f: X \times Y\rightarrow Z$ and a rectangle $R \subseteq X \times Y$, $R$ is monochromatic in relation to $f$ if $f$ is constant over $R$.

Using rectangles it is possible to partition the space of input of any given function. Given a function $f$, the (base 2) logarithm of the amount of rectangles needed to cover the input space of $f$ gives a lower bound on the communication complexity of any protocol computing such $f$.
Here comes my first real question: given a function $f:X \times Y \rightarrow Z$, does proving that it is not possible to cover $X \times Y$ using at most n rectangles imply that $CC(f) = \omega(\log(n))$?
Now let’s talk about a practical example. The Equality Function is defined as follows:
$$EQ(X,Y) =\begin{cases}
1&\text{if $X = Y$,}\\
0&\text{otherwise.}
\end{cases}$$
Since it can be proved using rectangles that $CC(EQ) = n + 1$, wouldn’t that mean that $D(EQ) = \omega(\log(n))$?
There’s something slipping my grasp, thanks in advance to everyone who will spend some of their time to reply.


texts: Complexity classes not closed under intersection and union

texts: Some of the better known complexity classes: PP, NP, P... are closed under intersection and union. What are some counter-examples? Is there a natural reason for the common complexity classes to be closed under these operations?


texts: Can a flow be decomposed in a given number of paths?

texts:
If we have a digraph $G=(V,A)$ with capacity $u_a\in \mathbb{N}$ for $a\in A$ and a source $s$ and sink $t$. I know the following theorem:

  Let $f$ be a flow in the network above. Then there is a collection of feasible flows $f_1,\dots,f_k$ and $s$-$t$ paths $p_1,\dots,p_k$ such that

  $k\le |A|$
  the flow value of $f$ is equal the sum of the flow values of the $f_i$'s
  the flow $f_i$ sends only positive flow on the edges of $p_i$

I am wondering if for a given flow $f$ and integer $n$ under additional assumption there is such a decomposition in exactly $n$ such paths?

Motivation: In our lecture notes there use two iteration of the Ford–Fulkerson algorithm and claim: the resulting flow can be decomposed in 3 paths and a circulation. Clearly, from the algorithm I get two path, but how can I decompose the flow in three path and a circulation? The only decomposition theorem we had, is the one I stated above. I guess it uses some other approach.
However the question of decomposing in exactly $n$ paths is also of particular interest for me. Thanks in advance.

math


texts: Representation as sum of unit fractions: primitive recursive?

texts:
Consider the following ternary relation $R\subseteq\mathbb{N}^3$:

  $(p,q,m)\in R$ iff $p,q>0$ and there is a set $S\subseteq \{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $|S|=m$ and $\frac{p}{q}=\sum_{s\in S} s$.

Is $R$ primitive recursive, recursive, or recursively enumerable?


texts: What is the theoretical basis of imperative programming?

texts:
Functional programming has a theoretical basis in lambda calculus and combinatory logic.  As someone involved with statistical computing, I find these concepts to be very useful for modeling.

Is there an equivalent mathematical basis of imperative programming, or did it simply grow out of practical hardware application in machine language and the subsequent development of FORTRAN?


texts: Smallest representatives of a quotient by an equivalence relation

texts:
Background

Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for a regular language $L$ such that $|Q|=n$, and let $\equiv_L$ be the relation given by $$x\equiv_Ly\text{ iff for all $u$: }xu\in L\Leftrightarrow yu\in L.$$ It is known we can identify the states of $\mathcal{A}$ with the elements of the quotient $\Sigma^*/\equiv_L$. Moreover, since $\equiv_L$ can be characterized by $$x\equiv_Ly\text{ iff }\hat\delta(q_0,x)=\hat\delta(q_0,y),$$ we know we can choose elements $w_1,\ldots,w_n\in\Sigma^*$ such that $$Q=\big\{[w_i]_{\equiv_L}: i\in\{1,\ldots,n\}\big\},$$ and $|w_i|\leq n$ for all $i$, that is, we can choose representatives for $\Sigma^*/\equiv_L$ of length at most $n$.

This is useful because, given the minimal DFA $\mathcal{A}$ (whose states might be given in an abstract way, not necessarily with elements of $\Sigma^*/\equiv_L$), we can obtain a set of representatives of $\Sigma^*/\equiv_L$ by running $\mathcal{A}$ with all inputs of length at most $n$ and marking the states that have already been reached with a flag. Whenever an unmarked state is reached with a string $w$, we flag the state and add $w$ to the list of representatives. This might not be the most elegant or efficient algorithm, but thanks to the upper bound we can be sure it finished and it computes what we want.

Question

Is there a general method of estimating a minimal length of representatives of an equivalence relation? I'm assuming, of course, that the universe consists of elements of finite length (e.g. $\Sigma^*$).

In particular, I'm looking for a similar upper bound for the relation $\sim_L$ given by $$x\sim_Ly\text{ iff for all $u,v$: }uxv\in L\Leftrightarrow uyv\in L,$$ which can be characterized by $$x\sim_Ly\text{ iff for all $q\in Q$: }\hat\delta(q,x)=\hat\delta(q,y),$$ where the automaton is minimal.

Thanks in advance for your guidance.

Update: to be a bit more precise, what I want is an upper bound $M$ for the smallest representative of a class, so I can do an algorithm of the form: ``check all the words of length at most $M$...'' and be sure that all classes are covered by some representative at least once.


texts:
Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that

(i) $0 \le p_1, \ldots, p_n \le 1$

(ii) For $1\le j \le k$, $|(\sum_{i=1}^n p_i^j) - \alpha_j|\le \epsilon$.

Here $k \ll n$. I am interested in the time complexity of this problem: In particular, based on some symmetry considerations, one can show that it suffices to restrict one's search to the case where $p_1, \ldots, p_n$ all come from a set of size at most k. Based on this observation, one can consider all possible ways of partitioning $p_1, \ldots, p_n$ into k sets (which takes time $n^k$) and subsequently solve a problem which requires one to solve polynomial equations over the reals (in k variables and of degree bounded by k). This takes time $k^k$. The dependence of n^k is prohibitive for me and I was wondering if there is a way to solve this in time $O(n^{O(1)} \cdot k^{k})$ or at least better than $n^k$.


texts: Given a sequence $a_1,\ldots,a_n$, find a $k$ and numbers $1\leq i_1< \dots< i_{2k}\leq n$ that maximizes $(\sum_{j=1}^{k}(a_{i_{2j}}-a_{i_{2j-1}}))-2k$. I can get an $n^3$ algorithm using dynamic programming. Is there a better algorithm?


texts: A practical multi-word compare-and-swap operation

texts:
In the paper with the same title as that of this question, the authors describe how to build a nonblocking linearizable multi-word CAS operation using only a single-word CAS. They first introduce the double-compare-single-swap operation - RDCSS, as follows:

word_t RDCSS(RDCSSDescriptor_t *d) {
  do {
    r = CAS1(d->a2, d->o2, d);
    if (IsDescriptor(r)) Complete(r);
  } while (IsDescriptor(r));
  if (r == d->o2) Complete(d); // !!
  return r;
}

void Complete(RDCSSDescriptor_t *d) {
  v = *(d->a1);
  if (v == d->o1) CAS1(d->a2, d, d->n2);
  else CAS1(d->a2, d, d->o2);
}

where the RDCSSDescriptor_t is a structure with the following fields:

a1 - address of the first condition
o1 - value expected at the first address
a2 - address of the second condition
o2 - value expected at the second address
n2 - the new value to be written at the second address

This descriptor is created and initialized once in a thread which initiates the RDCSS operation - no other thread has a reference to it until the first CAS1 in the function RDCSS succeeds, making the descriptor reachable (or active in the terminology of the paper).

The idea behind the algorithm is the following - replace the second memory location with a descriptor saying what you want to do. Then, given that the descriptor is present, check the first memory location to see if its value changed. If it hasn't, replace the descriptor at the second memory location with the new value. Otherwise, set the second memory location back to the old value.

The authors do not explain why the line with the !! comment is necessary within the paper. It seems to me that the CAS1 instructions in the Complete function will always fail after this check, provided that there is no concurrent modification. And if there was a concurrent modification between the check and the CAS in Complete, then the thread doing the check should still fail with its CAS in Complete, since the concurrent modification should not use the same descriptor d.

My question is: Can the check in the function RDCSSS, if (r == d->o2)... be omitted, with RDCSS still maintaining the semantics of a double compare, single swap instruction which is linearizable and lock-free?  (line with !! comment)

If not, can you describe the scenario where this line is actually necessary to ensure correctness?

Thank you.


texts: Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

texts:
Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $n \in \mathbb{N}$ (written in unary) as input, I want to enumerate all words of the language of $A$ of length $n$, by increasing weight (i.e., first all words of the smallest possible weight, enumerated in some arbitrary order; then all words of the second smallest possible weight, in some arbitrary order; etc., until all words of length $n$ in the language of $A$ have been produced). I'm interested in this in the context of enumeration algorithms, so let's say I want polynomial delay, i.e., the time to produce the next word is always bounded by some polynomial function of $n$. Of course, finding some word achieving the smallest possible weight is easy (make $n$ copies of the automaton and do a shortest path algorithm); the difficulty is in finding the next words, keeping in mind that you are not allowed to enumerate the same word multiple times. And of course, enumerating all words with polynomial delay is not complicated if you do not care about ordering them by weight: make $n$ copies, prune the useless states, and simply enumerate all paths exhaustively with a DFS.

Is anything known about the complexity of this problem? Can the enumeration be performed in PTIME (maybe only for some DFAs?), or can it be shown to be intractable?

I'm also interested in:

A weighted variant, where instead of $n \in \mathbb{N}$ written in unary, I get as input an $n$-tuple of integers $w_1, \ldots, w_n$, and the weight of a word $u_1, \ldots, u_n$ is then $\sum_i u_i w_i$, i.e., I want to enumerate all words by increasing weight of their dot product with the input vector $w$. (The unweighted version above is the case where all values of the $n$-tuple are 1.) In this problem variant, if the numbers in the vector components are written in binary, it becomes NP-hard to decide if a certain weight can be achieved (this is the subset sum problem, already for the trivial automaton $A$ accepting $\Sigma^*$). But this does not imply that enumerating is hard.
A combined complexity variant where the automaton is also given as input and not fixed. In this case, you might as well do directly the product of the automaton with $n$, so you can simply assume that the input is an acyclic DFA, or equivalently an OBDD. But I'm not aware either of algorithms to enumerate OBDD valuations in order of increasing weight.


texts: Find worst case input for a program solving an NP-hard problem

texts:
I am trying to find a way to find a worst-case input for a black-box implementation of an algorithm with worst-case exponential runtime.

The problem that the program solves (integer linear programming) is NP-hard, but since the proof is by reduction from vertex cover, there is no construction of a hard subset or such. Also vertex cover is in NP due to a reduction from 3SAT. Now for 3SAT it is in no way certain that a hard case for a given 3sat solver would translate to a hard problem for one of my black-box ILP implementations.

Is there a systematic way to find a worst-case runtime example for a given problem of size n?


texts: Is this optimum travelling problem under deadlines NP-hard on trees?

texts:
One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it?

Problem:
There is a tree $T(V,E)$, each edge has symmetric traveling cost of 1. For each vertex $v_i$, there is a task which needs to be done before its deadline $d_i$. The task is also denoted as $v_i$. Each task has the uniform value 1. The processing time is 0 for each task, i.e., visiting a task before its deadline equals finishing it. Without loss of generality, let $v_0$ denote the root and assuming there is no task located at $v_0$. There is a vehicle at $v_0$ at time 0. Besides, we assume that $d_i \ge dep_i$ for every vertex, $dep_i$ stands for the depth of $v_i$. This is self-evident, the vertex with deadline less than its depth should be taken as outlier. The problem asks to find a scheduling which finishes as many tasks as possible.

Progress:

If the tree is restricted to a path, then it is in $\mathsf{P}$ via dynamic programming.
If the tree is generalized to a graph, then it is in $\mathsf{NP}$-complete.
I have a very simple greedy algorithm which is believed 3-factor apporoximation. I have not proved it completely. Rightnow, I am more interested about the NP-hard results. :-)

Thanks for your advice.


texts:
I'm exploring some graph algorithms, and would like to animate the graph change over time (e.g. when adding a heap node or balancing a tree).

Is there a nice way to animate a sequence of graphviz graphs?


texts: Is a monotone boolean function monotone as a multilinear polynomial?

texts: Let $f:\{-1,1\}^n \rightarrow \{0,1\}$ be a monotonically increasing boolean function. That is, $f(x) \leq f(y)$, if coordinate-wise $x \leq y$. Now, let $F: [-1,1]^n \rightarrow \mathbb{R}$ be $f$ expressed as a multilinear polynomial (i.e. $F$'s Fourier transform). Is $F$ still a monotonically increasing function?


texts: Complexity of the inverse modulo a composite number

texts:
Supposing $M$ is a composite number and supposing $a$ is an integer such that $a^{-1}\mod M$ exists,  can we compute $a^{-1} \bmod M$ by using $O(\log^{b}(M))$ ring operations in the RAM model, where $b>0$ and is some fixed number?

I'm interested in the case where $a$ and $M$ are of similar sizes.

When we apply the Euclidean algorithm, we compute the remainder of an integer divided by another. It is not clear to me if this can be done in unit time in the RAM model using only ring operations.


texts: Complexity of Parallelogram Range Minimum Query

texts:
Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs?

More formally, answering the query

$$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$$

In terms of preprocessing, and answering the query where the array is static


texts:
TL;DR:

I am looking for theoretical sources about the different manners to implement user access control.

Long version

I have almost finished all the stand-alone tools needed in my CMS.

I am not at the moment where I need to bring all these pieces together.
Now what I would like to is to create a CMS (and an API) that is completely user-centric.
This means a very strong, yet easy to use, rights management framework at the base of everything. A bit like unix/linux filesystems work (not the actual implementation, but in the sense that they are at the very core of the system).

This framework would need to account for special cases ("user can access this data until date x"), and implement per-action, or per-item rights ("user can edit articles, but not article233"), be completely abstract (not tied to any particular database), and not tied to any authentication system. Also, since any request would go through it, it needs to be quite optimized. Lastly, I want to keep it open for modularity.

This is quite a large project, and before getting into it, I'd like to gather as much theory about used rights management. I know about ACL (and have already implemented a few custom systems myself), but I am looking for a more abstract, high-level document, ideally, not tied to a particular language. In the article/book I envision, code samples would be rare, a few lines only, and coded in pseudo-code just to illustrate a point.

I've been looking on the net but can only find tutorials about how to implement ACL, or discussions about role-based access control, but nothing about, say, research in the field, innovative/alternative solutions, etc.

Anyone can advise a good book/webpage/resource about that?


texts: Are there known to exist functions with the following direct-sum property?

texts:
This question can be asked either in the framework of circuit complexity of Boolean circuits, or in the framework of algebraic complexity theory, or probably in lots of other settings.  It is easy to show, by counting arguments, that there exist Boolean functions on N inputs that require exponentially many gates (though of course we don't have any explicit examples).  Suppose I wish to evaluate the same function M times, for some integer M, on M distinct sets of inputs, so that the total number of inputs is MN.  That is, we just want to evaluate $f(x_{1,1},...,x_{1,N}), f(x_{2,1},...,x_{2,N}),...,f(x_{M,1},...,x_{M,N})$ for the same function $f$ at each time.

The question is: is it known that there exists a sequence of functions $f$ (one function for each N) such that, for any N, for any M, the total number of gates required is at least equal to M times an exponential function of N?  The simple counting argument does not seem to work since we want this result to hold for all M.  One can come up with simple analogues of this question in algebraic complexity theory and other areas.


texts: Testing low degree bivariate polynomials

texts:
Let $d,q \in \mathbb{N}$, and let $f:\mathrm{GF}(q) \to \mathrm{GF}(q)$ be a univariate polynomial. In this case, it is possible to test whether $f$ is of degree at most $d$ (or whether $f$ is at least $\epsilon$ from it) using the algorithm of (RS96). The testing algorithm works by simply trying to interpolate the function $f$ on $\Theta(1/\epsilon)$ collections of $d + 2$ uniformly selected points, and checking whether the resulting functions are all polynomial of degree at most $d$.

Is there an extension of this result that allows to test whether a bivariate polynomial $g:\mathrm{GF}(q)^2 \to \mathrm{GF}(q)$ is of degree at most $d$ in the first variable, using $O(\epsilon^{-1} \cdot d)$ queries?


texts:
I have the following problem:

We are given an instance of the 3-SAT problem.
Is there a satisfying assignment s.t. at least two literals are satisfied in each clause?

The question is:

Is the problem NP-complete?

The question might sound stupid, but I couldn't figure it out by myself.

I searched the web and in books but didn't find anything.

I also tried to reduce 3-SAT to it, but without success.

(I have to admit that I didn't spent much time to do it since it is not my main research focus; this is just a question that came to my mind while working on another problem. I am interested in the answer because if it turns out to be NP-complete it could help me in a future problem.)

Thanks in advance for your answers! Every answer or comment is welcome.


texts: Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

texts:
I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER to SAT.

Given a cubic graph $G$, the reduction outputs a CNF formula $F$ having both the following properties:

$F$ has at most $1$ satisfying assignment.
$F$ is satisfiable if and only if the number of vertex covers of $G$ is odd.

  Questions

  Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? A consequence which I'm already aware of is the following: $\mathbf{PH}$ would be reducible to $\mathbf{NP}$ via two-sided randomized reduction. In other words we would have $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ (using Toda's Theorem, which states that $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$, by merely replacing $\oplus\mathbf{P}$ with $\mathbf{NP}$). I do not know if $\mathbf{BPP}^{\mathbf{NP}}$ has been shown to be contained in some level $i$ of the Polynomial Hierarchy: if yes, a further consequence would be that $\mathbf{PH}$ collapses to such level $i$. Moreover, under widely accepted derandomization assumptions ($\mathbf{BPP} = \mathbf{P}$), the Polynomial Hierarchy would collapse between the first and the second level, as we would have $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$ (I'm told this is not true, however I will not erase this line until I fully understand why).
  If I'm not mistaken, the aforementioned reduction would actually prove more than $\oplus \mathbf{P} \subseteq \mathbf{NP}$. It would prove $\oplus \mathbf{P} \subseteq \mathbf{UP}$. Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{UP}$, in addition to those already implied by $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? I do not know exactly whether $\oplus \mathbf{P} \subseteq \mathbf{UP}$ would add more surprise to the already surprising consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$, nor to what extent. Intuitively I presume it would, and to a pretty wide extent.


texts:
What algorithms/mathematical techniques are available to exactly/approximately count number of independent sets?

Is/Are there a good reference/good references on this topic?

I am interested in regular graphs.


texts: Trying to find Warren D. Smith's Matrix Multiplication article

texts:
One of my favorite articles on the complexity of matrix multiplication has gone dark.

Warren Smith, Fast Matrix Algorithms And Multiplication Formulae,  https://math.cst.temple.edu/~wds/matgrant.ps

I especially liked the explanation of Brent equations.

Does anyone have a copy?


texts:
We think the log rank conjecture is true over $\{0,1\}$ real matrices and over any fixed alphabet matrix.

What is the fastest function $f(r)$ of rank $r$ such that the log rank conjecture over $\{0,1\}$ real matrices holds iff there is an $f(r)$-log rank conjecture that holds over $\{0,1,\dots,f(r)-1,f(r)\}$ real matrices?


texts:
In Savitch's 1969 paper, "Relationships Between Nondeterministic and Deterministic Tape Complexities", he states that "all common storage functions L(n) >= lg n are measurable. In particular, any polynomial in n and lg n is measurable."  His definition of measurable is:  "A function L(n) is said to be measurable if there is some Turing machine with just one storage tape such that, given any input of length n, the machine will halt after a computation in which the storage tape head scans exactly L(n) squares."

So, my problem is, based on his definition, I don't understand why storage functions L(n) >= lg n would be measurable, while functions L(n) < lg n would not be.  Is this somehow implicit in his definition?  Or are there some publications that I should read?


texts: Generalizing the "median trick" to higher dimensions?

texts:
For randomized algorithms $\mathcal{A}$ taking real values, the "median trick" is a simple way to reduce the probability of failure to any threshold $\delta > 0$, at the cost of only a multiplicative $t=O(\log\frac{1}{\delta})$ overhead.
Namely, if the $\mathcal{A}$'s output falls into a "good range" $I=[a,b]$ with probability (at least) $2/3$, then running independent copies $\mathcal{A}_1,\dots,\mathcal{A}_t$ and taking the median of their outputs $a_1,\dots,a_t$ will result in a value falling in $I$ with probability at least $1-\delta$ by Chernoff/Hoeffding bounds.

Is there any generalization of this "trick" to higher dimensions, say $\mathbb{R}^d$, where the good range is now a convex set (or a ball, or any sufficiently nice and structured set)? That is, given a randomized algorithm $\mathcal{A}$ outputting values in $\mathbb{R}^d$, and a "good set" $S\subseteq \mathbb{R}^d$ such that $\mathbb{P}_r\{ \mathcal{A}(x,r) \in S \} \geq 2/3$ for all $x$, how can one boost the probability of success to $1-\delta$ with only a logarithmic cost in $1/\delta$?

(Phrased differently: given fixed, arbirary $a_1,\dots, a_t\in \mathbb{R}^d$ with the guarantee that at least $\frac{2t}{3}$ of the $a_i$'s belong to $S$, is there a procedure outputting a value from $S$? If so, is there an efficient one?)

And what is the minimum set of assumptions one needs on $S$ for the above to be achievable?

Sorry if this turns out to be trivial -- I couldn't find a reference on this question...


texts: The worst-case scenario(s) for MAX3E SAT

texts:
MAX3E SAT is defined as SAT with all clauses consisting of 3 literals and their possible negations.  We define clause counting, for this question, as the ability to count the total number of satisfied clauses for all remaining possible truth assignments.  Let's say that we are allowed to pick a single variable and assign it a value, and then perform clause counting to get a total for all remaining possible truth assignments.  Further, we can do this for all variables and their negations.

Let's consider this clause counting ability for MAX3E SAT with an equation that is garaunteed to be satisfiable by at least one possible truth assignment.  Now, the clause counting from above can be used to help predict part of a satisfying truth assignment.  The variable we pick with the highest clause count should (probably) be part of a satisfying truth assignment.  I'd like to construct the smallest example (in terms of clauses) where this notion of clause counting fails.  Can someone please help?


texts:
Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the degree of each vertex is at most $k$. Now consider the problem of coloring $G$'s edges with $k$ colors, such that no adjacent edges have the same color. This problem can be solved efficiently by noting that $G$ is a subgraph of a $k$-regular bipartite graph and thus one can compute a perfect matchings to color $G$.

The problem I'm trying to solve is as follows. Assume that we have colored $G_1$ and now we're given a new graph $G_2$ with the same properties and vertices of $G_1$ but with possibly different edges. We want to color $G_2$ while trying to save as many colors from $G_1$ as possible. That is, if there is an edge $e_1$ of $G_1$ that is also present in $G_2$, then we prefer to keep its color from the previous coloring of $G_1$.

Formally, suppose $c_1$ is a coloring of $G_1$ and $c_2$ is a coloring of $G_2$. Define a function $f_{c_2}$ from the edges of $G_2$ to $\{0, 1\}$ as follows: $f_{c_2}(e) = 1$ iff $e$ is present in both $G_1$ and $G_2$ and $c_1(e_1) = c_2(e_2)$. Now the problem can be stated as follows. Given $G_1$, a coloring $c_1$ of $G_1$ and given $G_2 = \langle V_2, E_2\rangle $, we're asked to compute a coloring $c_2$ of $G_2$ such that $\sum_{e \in E_2}f_{c_2}(e)$ is maximized.

My approaches:

I tried to use the Hungarian algorithm $k$ times to find $k$ perfect matchings. Lets say i want to save as many blue colored edges as possible, so i give those edges in $G_2$ a high weight, i find a perfect matching to color it with blue and then i proceed to the next color. The problem with this solution is that the order of the colors that we choose may affect the outcome.
I thought that maybe one can state the problem as an instance of LP (linear programming).

A help would be appreciated,


texts:
Which would be the consequences of #P = FP?

I'm interested in both practical and theoretical consequences.

From a practical point of view, I'm particularly interested in consequences on Artificial Intelligence.

Pointers to papers or books are more than welcome.

Please do not say that #P = FP implies P = NP, I already know that. Also, please do not say "there will be no practical consequences if the algorithm runs in time $\Omega(n^{\alpha})$, where $\alpha$ is the number of electrons in the Universe": permit me to assume that, if a deterministic polynomial time algorithm for a #P-complete problem exists, its running time will be "clement" ($O(n^2)$, for example).


texts: Is the problem of finding the chromatic number of a modified interval graph NP-Complete

texts:
Few days ago I was working on interval graphs to solve the known problem of resource allocation, as we know there is a greedy approach that solves this problem (chromatic number) in polynomial time and gives us the colors of each vertex in the interval graph (the problem of finding the chromatic number in general graphs is NP-Complete (3-satisfiability reduction by Karp)).

  I was wondering: if had a graph that is not an interval graph but it is because it has one and only one chordless cycle of length > 3 (there is an edge that, when you remove it, the graph becomes an interval graph), does it makes the problem of finding the chromatic number on this kind of graph NP-Complete?


texts: The complexity of counting simple paths in a directed graph

texts:
Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$.

I would expect the problem to be #${\mathsf P}$-complete but have not been able to locate an exact reference.

Also notice that a number of similar questions have been answered correctly here
and elsewhere but not this precise question - to emphasise I am not interested in counting walks and/or undirected graphs (in the first case the variant is in ${\mathsf P}$ and in the other #${\mathsf P}$-hard).


texts:
My question is: given a maxcut instance, if it costs too much to solve it to optimal practically but we can get an optimal solution of SDP relaxation quickly, can we assess the quality of this SDP solution? (like estimate the OPT/SDP ratio for THIS INSTANCE). My preliminary thought is that if the rank of the SDP solution (matrix) is far bigger than 1, then SDP relaxation is probably not good for this instance. But can we say for sure? Is there some literature that can be pointed to?

In Goemans and Williamson 1995 paper "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", they asserted $\text{SDP} \ge \text{OPT} \ge \text{ALG} \ge 0.878 \text{ SDP}$. In Feige and Schechtman 2002 paper "On the optimality of the random hyperplane rounding technique for max cut", they constructed maxcut instances that $\text{OPT} \le (0.878 + \varepsilon) \text{ SDP}$. However, both of these are worst case analysis. My question is practically assessing the quality of SDP relaxation for a particular maxcut instance without knowing the optimum to the original problem.

In reading ""An Optimal SDP Algorithm for Max-Cut, and Equally Optimal Long Code Tests" by R.O'Donnell etc. from Stoc'08, the author gave a curve of $\text{OPT} vs. \text{SDP}$. So the worst-case analysis of $\frac{\text{OPT}}{\text{SDP}}$ is solved. However I have difficulty in understanding their proof so I don't know whether their work can be helpful to this problem.


texts: Is a PhD in TCS the best way towards achieving a career in industrial research?

texts:
My idea of a dream career is a career in industrial research, where one gets to tackle problems which are challenging, and also have a practical usage. To that end, is pursuing a PhD in TCS (I'm interested in topics such as distributed/parallel algorithms, online algorithms) a bad idea ? I've the notion that most, if not all, PhD applicants in TCS are expected to pursue a career in academia - is that a valid precept ?

I've noticed distinguished academics who are regular users of this site - I'm especially looking for guidance from any such person, as I don't want to apply for a doctoral program with the wrong goals in mind. To give a brief description of my profile, I've graduated with MTech in CS (from a fairly reputable institute in my country) about 2 years back, and been working in a MNC ever since on kernel level device drivers.

This question may not be the most ideal question for this site, but I couldn't find a better place to ask it. Requesting the moderators not to close this outright, as I'm really in need of some advice here.


texts: Time complexity analysis for Reingold's UST-CONN algorithm

texts: What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?


texts: the confusion about 'with high probability (w.h.p.)'

texts:
w.h.p. can often be seen in the analysis of randomized algorithms.  It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that:

Assuming we have 4 cases as bellow, and we can use $\delta$  to replace $1/n$, then $O(\log(n))=O(\log(1/\delta))$

case 1. ERROR is upper bounded by $O(n)$ with probability $1-\exp^{-n}$;

case 2. ERROR is upper bounded by $O(n)$ with probability $1-n^{-1}$;

case 3. ERROR is upper bounded by $O(n)$ with probability $1-n^{-1/3}$;

case 4. ERROR is upper bounded by $O(n)$ with probability $1-1/\log^{n}$.

In above cases, all the probabilities turns to be $1$ as $n$ increases, which are all  w.h.p.(based on the above definition wiki). But in practice, case 1 is the most efficient result, case 2 and 3 can be acceptable, while case 4 seems to has no practical meaning.

So, it seems we cannot use 'w.h.p.' to persuade other people to believe that the related (randomized) algorithms and theoretical guarantee can work well in practice?

OR, can we have a rigorous definition for 'w.h.p.'?


texts: Understanding the weak-OWF exists -> OWF exists proof

texts:
This is a proof that I've gone back to many times over the last few years and while I can read it and easily verify the steps, it seems like it's a proof, where I will always essentially forget the details, i.e. if I read it today, I would struggle to write down a full proof tomorrow without actually spending quite a bit of effort. I'm talking about the proof that's e.g. in Goldreich's Foundations of Crypto book, which I believe is standard (I've never seen a different proof).

As complexity theory is not my field, I would hope that people who are more experienced in the field could make sense of the proof by answering the following questions:

What part of the proof are completely standard techniques?
What part of the proof if any is a "trick".

The basic idea is easy: Given a weak one-way function, repeat it many times, so that any inverter of the repeated function needs to invert all the pieces. Dealing with the lack of independence in processing the components in the inversion is then the tricky part and I'm hoping that there's a way to split it up into standard arguments. At least understanding it in useful pieces that might be applicable elsewhere would be nice, if possible.


texts:
Wikipedia lists several exact algorithms for graph vertex coloring.

Are there any exact algorithms that are designed specifically for graph edge coloring?

edit:

Just came across my mind, i think it should be ok (pure bruteforce). I didnt try to implement this yet. Please comment if you see something wrong. Just to say again - algorithm should check whether graph is edge colorable with d or d+1 colors where d is max degree of all vertices in given simple graph, and to find one coloring...

colorEdge(edge, color, extra) {
    if (edge colored) return;  //if already colored, return
    if (can be colored in color) color it; //if color can be applied, apply it
    else {
        //else, 'd+1'-st color neded, so color it with that color, continue finding
        //coloring with d+1 colors
        extra = !extra;
        color it in color extra;
    }

    //recursivly try to color adjacent edges with available colors
    for each color c' from set of d colors {
        for each edge k adjacent to current {
            colorE(k, c', extra)
        }
    }
}

//main
bool extra = false;
for each color b from set of d colors {
    colorEdge(some starting edge, b, extra)
    if (!extra) break;
}


texts: Minimizing residual finite state automata

texts:
Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular language, and the language recognized by each state in the RFSA is a residual, just like in a DFA. However, whereas a minimum DFAs states form a bijection with all residuals, the canonical RFSAs states are in bijection with the prime residuals; there can be exponentially fewer of these, so RFSAs can be much more compact than DFAs for representing regular languages.
However, I can't tell if there is an efficient algorithm for minimizing RFSAs or if there is a hardness result. What is the complexity of minimizing RFSAs?
From browsing [BBCF10], it doesn't seem like this is common knowledge. On the one hand, I expect this to be difficult because a lot of simple questions about RFSAs like "is this NFA an RFSA?" are very hard, PSPACE-complete in this case. On the other hand, [BHKL09] shows that canonical RFSAs are efficiently learnable in Angluin's minimally-adequate teacher model [A87], and efficiently learning a minimum RFSA and minimizing RFSAs seems like it should be of equal difficulty. However, as far as I can tell [BHKL09]'s algorithm does not imply a minimization algorithm, since the size of counter-examples is not bounded and it is not clear how to efficiently test RFSAs for equality to simulate the counter-example oracle. Testing two NFAs for equality is PSPACE-complete, for example.
References
[A87] Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and Computation, 75: 87-106
[BBCF10] Berstel, J., Boasson, L., Carton, O., & Fagnot, I. (2010). Minimization of automata. arXiv:1010.5318.
[BHKL09] Bollig, B., Habermehl, P., Kern, C., & Leucker, M. (2009). Angluin-Style Learning of NFA. In IJCAI, 9: 1004-1009.
[DLT02] Denis, F., Lemay, A., & Terlutte, A. (2002). Residual finite state automata. Fundamenta Informaticae, 51(4): 339-368.


texts: What is the the optimal computational model for memristive style CMOS?

texts:
I'm a bit new to the practical use of memristors in general, but I'm starting to see it as a (3D stacked) grid of components that could be treated as transistors or flip-flops on demand (which may be completely wrong, I'm not sure). It seems like the usual Von Neumann architecture wouldn't be ideal at all (of course you could emulate it, but it doesn't seem like a good idea). Does anyone know of any models that are better suited? I'm trying to get my brain to move past a model that would create variable "cores" that scale with size as the program runs in the memristive space (I've been poisoned by the current models) and more of one where the "core" and memory is combined (no independent TLB/cache/RAM).

Edit: As to what I mean by memristive grid -- So, lets say you have a 3 dimensional hypercube with "nodes" at each discrete x,y,z coordinate. Each one of these nodes is addressable. When you address a node, you can tell it to become a bit of memory or a gate (just like an FPGA gate). After you tell all of the nodes what they are, you can then perform computation in the hypercube using the landscape of memory and gates that you designed. It's kinda like a processor with bits of memory sitting right next to the transistors, but you can reconfigure it as you go (under a nanosecond for each reconfiguration), possibly after each instruction that you execute in the landscape.

Edit: One of the things that got me interested in thinking about this problem is the idea that you can calculate Hilbert integers for a space filling curve and transpose the hypercube into a linear space using reflected binary codes -- it might lead into some interesting memory arrangements when you try to optimize the clustering of memristive memory and computation.


texts: Totally ordered multicast with Lamport timestamps

texts:
I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the application, but

"It is sufficient to multicast any other type of message, as long as that message has a timestamp larger than the received message. The condition for delivering a message m to the application, is that another message has been received from each other process with a large timestamp. This guarantees that there are no more messages underway with a lower timestamp."

This is a definition from a book. I tried to apply this definition to an example but I guess that something is wrong.
Example.

There are 4 processes and they multicast the following messages (the second number in parentheses is timestamp) :
P1 multi-casts (m11, 5);  (m12, 12); (m13, 14);
P2 multi-casts (m21, 6); (m22, 14);
P3 multi-casts (m31, 5); (m32, 7); (m33, 11);
P4 multi-casts (m41, 8); (m42, 15); (m43, 19).

Supposing that there are no acknoledgments, can I guess which messages can be delivered and which not? Based on definition, my guess is that only m11 and m31 can be delivered to the application, because all the other messages received will have a timestamp greater, but this seems very strange, and I think I didn't understand the delivery condition very well. I have an exam on Tuesday about this, but anyway I would understand this mechanism.


texts: Is the infinitely-often version of Ladner's theorem known?

texts:
We say two languages $\;\;\; L\hspace{.02 in},\hspace{-0.02 in}L' \: \subseteq \: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^* \;\;\;$ agree infinitely-often with each other

if and only if there are infinitely-many $n$ such that $\;\;\; L \cap \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^n \: = \: L' \cap \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^n \:\:\:\:$.

For a language $L$ let io-$L$ be
the set of languages which agree infinitely-often with $L$.

Let io-P be
the set of languages that agree infinitely-often with some language in P.

Let io-NPH be the infinitely-often version of NPH
(NP-hard w.r.t. Cook reductions):

$L \in$ io-NPH iff for all $L' \in$ NP, some language in io-$L'$ is polynomial-time Turing reducible to $L$.

  Is    io-P does not contain NP    known to imply that    io-P $\cup$ io-NPH  does not contain NP   ?


texts: Can one prove the discovery of a P versus NP solution without actually revealing it?

texts:
Suppose a person has proved that P≠NP. He wants to let the world know that he has solved the P versus NP problem but does not want to reveal that he has proved P≠NP as opposed to P=NP.

Is there any purely theoretical way to do so?

Also any practical evidence he can show to back his claim? (I'm not sure it this part is on-topic)


texts: What's the expressive power of Simply Typed Lambda calculus?

texts:
The standard approach to simply typed lambda calculus considers computations over Church numerals.
If input and outputs are Church numerals always typed as $Int$, where $Int = (\tau \rightarrow \tau) \rightarrow \tau \rightarrow \tau $, a result of Schwichtenberg showed that expressible functions are the extended polynomials.

If inputs are Church numerals given more complex types than $Int$, exponentiation and predecessor can be expressed (however Statman showed that equality, ordering and subtraction are not expressibile for any typing of church numerals.

However we should be more permissive and provide only an output restriction: a boolean type ( $Bool = \tau \rightarrow \tau \rightarrow \tau $).
Under this convention, Statman's theorem that "deciding equivalence of normal forms of two simply typed lambda-terms is not elementary recursive" can be seen as an expressibility result (right?): we can express nonelementary functions.

Pushing to the limit, where we can arrive?
Of course (by strong normalization) we can express only total functions. But I'm asking if there is a precise upper bound to simply typed lambda calculus expressive power.

I've found many articles, in particular "On the expressive power of simply typed and let-polymorphic lambda calculi" but I'm not able to understand if it is what I'm looking for.


texts: What is the most efficient algorithm to sample graphs with trivial automorphism groups ?

texts:
Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph

I'm looking for an efficient way to compute a random asymmetric graph on a given number of nodes.


texts: mean/integral, except where positive differences between values and "mean" are weighted differently from negative differences?

texts:
Given a curve $f(x)$ (for $x \in [0,1]$), and a line $y=a$, let $U$ be the total area below $f$ and above $a$, and let $L$ be the total area above $f$ and below $a$. If $L=U$, this means that $a =\int_0^1 f(x) dx$.

Or if $f(x)$ is a sequence of $n$ numbers, this means $a$ is their mean. Equivalently, $U = \sum \max(f(x)-a,0) \; dx$, $L = \sum \max(a-f(x),0) \; dx$.

What I want instead is the value $a$ for which $c \cdot L = U$, for some constant $c>0$.

This can be computed approximately by binary search or exactly with a more cumbersome algorithm, but: is there a closed-form expression for this value? And: has this value been studied?

(The motivation is a battery-charging problem, where $a$ is the constant level of energy available, and $f$ is the energy usage at each moment, so $L$ corresponds to charging into the battery, and $U$ corresponds to discharging from the battery. Because of charge/discharge inefficiencies, after charging 1 unit in, you'll only be able to discharge, say, .5 units out. (For this interpretation to make sense, you might assume f is monotonically increasing.))


texts: What is the smallest result you publish on ArXiv?

texts:
In essence, the question is:

What is the least publishable unit for the ArXiv?

Of particular interest are fields that use the ArXiv extensively such as quantum computing. But comments on other fields and preprint services (like, ECCC & ePrint) are also welcome.

Detailed question
This is based on the following two questions:

When should you say what you know?
How do you decide when you have enough research results to write a paper and to which journal you submit the paper

In particular, on Jukka Suomela's comment on this answer:

I think ArXiving your results ASAP is a good idea. Please keep in mind that an ArXiv manuscript does not need to constitute a minimum publishable unit. I think it is perfectly ok to submit a 2-page proof to ArXiv, even though it would be obviously too short as a conference or journal paper. Resolving an open problem that other people would like to solve is more than enough.

In my field (quantum computing) it seems that every preprint I see on the ArXiv is a publication-level paper, released early so that we don't have to wait for conference proceedings or journal turnaround. It is intimidating to submit something that is not at publication-level. Is it alright to put up results which are partial or only slight extensions of existing work? Is it alright to put up results that are potentially interesting (i.e. you've given some talks on them and not everybody fell asleep) but you doubt would get into a top-conference or journal? Do you have advice on when to share results on ArXiv or similar preprint-servers? Can sharing results early hurt you?

Some specific background
Just to make the question more personal, I'll include a further motivation. However, I am hoping to receive answers that give more general guidelines that I (and others) could follow in the future.
I did some work on unitary t-designs in which I extended an existing theorem (in a way that is kind of useful, but the proof of the original just needs to be modified slightly -- so no new idea; i.e. when I talked to the author of the earlier paper his comment was along the lines of "oh cool, didn't think about that", and for the proof I had to say about a sentence and then he was like "okay, I see how you would prove that"), proved some easy results, and provided an alternative proof of a lower bound.
I wrote up a pretty verbose paper that I keep on my website, but unfortunately I am not well read enough in the field to really understand how it fits in the bigger picture (and I think that is the biggest weak-point, that I doubt I could overcome easily). I keep the text around mostly as a sort of "I worked on this" note and since I give talks on the topic sometimes. It has also come in useful once to a friend since I make a pretty gentle intro and so he used it as a basic starting point to relate some of his work to designs (although he didn't use any of the results in the paper, just like a lecture note on definitions).
Would this be an example of something that I should put up on the ArXiv? or is the appropriate measure to keep it in on my website?


texts: Communication lower bounds for partial boolean functions

texts:
There are well known techniques for proving lower bounds on the communication complexity of boolean functions, like fooling sets, the rank of the communication matrix, and discepancy.

1) How do we use these techniques for lower bounding partial boolean functions? More specifically, how do you count the rectangles in the communication matrix? Do you also count the "undefined part" of the function? Or do you leave it out?

Another thing, what are the known relations between the communication complexity of total and partial functions? For example, is there a function $f$ with a promise version of it, call it $f'$, such that $C(f)\neq C(f')$? (here $C$ could be any communication complexity measure like deterministic, probabilistic with all its flavors, quantum). A concrete example is the equality function EQ, and its promise version defined in this paper denoted as EQ'. It is known that $C(EQ)=n$ and $C(EQ')=\Omega(n)$ where $C$ is the bounded error communication complexity (see the paper). There is no matching upper bound here, but they are asymptotically the same.

2) Is there a function defined in the same spirit of EQ and EQ', but with a different complexity?


texts: Dynamic k-shortest paths in a weighted transducer

texts:
I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly.

In this scenario there is a reference transducer 'B' which accepts input strings in language 'a', and outputs strings in language 'b'.   'B' is constructed prior to starting the search.  There is then an acceptor 'A' which constitutes a directed, weighted, acyclic automaton (a lattice) and which encodes strings in language 'a'.  'A' is constructed dynamically, arc-by-arc, and composed with 'B' on-the-fly.  The output side of A*B is then projected, resulting in 'C' - a directed, weighted, acyclic automaton that encodes strings in language 'b'.  In the static case this process can be summarized as,

  C = project_output( compose(A, B) )

where 'A' is constructed dynamically.

I am interested in computing the k-shortest paths through 'C' dynamically.  Because 'A' is a lattice, it is also possible that there will be multiple paths through 'C' that are equivalent, but arrived at via different paths through the input side of 'B'.  Thus the weight corresponding to any unique path through 'C' seems like it should correspond to the sum of the weights of all input paths that share the same output. Intuitively, if we have two distinct input paths in the lattice that result in the same output from 'C', their associated probabilities should be summed in some way.  Thus in fact we would like to compute 'D',

  D = k_shortest_unique( project_output( compose(A, B) ) )

In the static case I believe we could compute this by performing,

  D = k_shortest( minimize( determinize( rm_epsilon( project_o( compose(A, B) ) ) ) ) )

and running all of the operations except for the final k_shortest algorithm in the log semiring.  Assuming I've thought this out correctly ( a big assumption ) this should ensure that when identical paths through 'C' are merged, their weights are summed.  Computing the k-shortest paths through 'D' in the tropical semiring should then still produce the correct summed result.

This approach is fine for computing the result statically, and most of these operations admit a lazy implementation anyway, but I'm wondering if anyone knows some good references regarding this type of problem in a dynamic or on-the-fly context.  Note also that graph edges will only ever be added to the 'right-hand edge' of the graph, as we construct 'A' and compose it with 'B'.

Finally, in practice the idea is that each time we add an arc to 'A', this should result in an incremental update to the list of potential paths through 'C', and an update to the total weight associated with it.  The list will most likely never have more than 10 or 15 unique output candidate paths, but this might correspond to 10x or more input paths through 'A'.

That turned out really long.


texts:
Suppose we have a pseudorandom number generator PRNG with number of possible seed states K. Let us denote PRNG(k) the number yielded by the generator when the seed state is k. Here k is an integer between 1 and K.

Question A: Is it possible to adapt PRNG to yield pseudorandom integer numbers uniformly distributed between 1 and K?

Assuming that the answer to this question is yes, let's denote by PRNG(k; 1, K) the number between 1 and K yielded by the adapted PRNG when the seed state is k.

We can then build a new pseudorandom number generator by nesting PRNG, i.e.

newPRNG(k) = PRNG(PRNG(k; 1, K))

Question B: From a theoretical point of view, can we say something about the properties of the new PRNG? In particular, does this nesting trick increase or decrease the randomness of the generator, in some sense?
I think this question is a natural one but I didn't find any answer on the web.


texts: Log space algorithms for modular decomposition tree

texts:
Can we have log space algorithms for modular decomposition tree (see definition) for any graph?

If not, can we have log space algorithms for modular decomposition tree for any particular graph class?
If yes, then I would appreciate a pointer to the graph class or a reference.

Finally, can we have parallel algorithms for modular decomposition tree?


texts:
Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of integers to the other. We were able to reduce that problem to the following very natural problem that seems to have connections to edit distance, grouping by swapping, and minimum common string partition.

Problem: We are given a string, i.e., a sequence of letters, and our goal is to  homogenize it at minimum cost. That is, we want a rearranged sequence such that all letters that are alike are next to each other.

The only operation that is permitted is to pick up a subsequence of letters that are alike, and move that subsequence anywhere, and that costs me 1 unit.

Any help characterizing the complexity of this problem would be much appreciated!

Example:

a a b c d a b: Input
b c d a a a b: After moving the first a a to the position right after "d"
b b c d a a a: After moving the trailing b to the first position

Since the resulting string is homogeneous, we have a cost of 2.

Note that we are not constrained in any way with respect to the output: as long as it is homogeneous, we don't need to ensure any specific order.


texts:
Here : http://www.planarity.org/Klein_elementary_graph_theory.pdf (in chapter embeddings) is given definition of combinatorial embedding of a planar graph. (with definition of faces and so on) Though it could be easily used for any graph, they define planar graph as the graph, for which Euler formula holds (assuming that graph is connected). It pretty much understandable that for every plane graph the definition of faces in combinatorial embedding is similar to the definition of faces in topological embedding. (assuming that graph is connected. Otherwise in combinatorial embedding we'll have infinite face for every connected component)

The question is: if for some connected graph it's combinatorial embedding satisfies Euler formula, does this mean that this graph is planar in topological sense (it has plane embedding, i.e. it's plane graph)?


texts: Can factorial be encoded in the Kappa-calculus with fixed point operator?

texts:
Suppose we have a $\kappa$-calculus with operator $fix$, that could be used to transform function with type $(1 \rightarrow a) \rightarrow a$ to a value of type $1 \rightarrow a$. We use a normal reduction strategy.
We'd like to represent factorial function in such a system. The problem is that whatever function we're trying to find a fixed point of, when we apply the function to its fixpoint, there's no way to determine whether we need to use the value of argument $x$ or not. There's no "counter" to base our solution on.
$fix (\kappa{}x. \cdots) = (\kappa{}x. \cdots) (fix (\kappa{}x. \cdots))$
In $\lambda$-calculus we could run $fix (\lambda f. \lambda x.\cdots)$ and terminate depending on the value of $x$.

How to prove that $\kappa$-calculus with fixed point operator cannot really represent a factorial function?
How could we extend $\kappa$-calculus to make it Turing-complete, leaving space for its translation into generalized arrows?


texts: Have any generalizations of maximum weight matching been studied?

texts:
For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise.

accordingly, a maximum weight matching could then be viewed as  maximizing the objective $\sum_v f_v$.

Have any generalizations of maximum weight matching been studied that consider more general objective functions using  weighted, multivariate or nonlinear $f_v$ ?

Have other variants been studied that are generalizations in a different way?

pleas provide references if applicable!


texts: Prove np-hard with reduction from scheduling resources

texts:
We have a system in which we have n number of process and m number of resources.The resources are boolean valued that is they can either have value 0 or 1(in brief suppose the resources as single way roads of network in which vehicle can travel in one direction at a time).Now each process requires certain number  of resources in some particular order for some units of time.

For example process number 1 requires resource number 3 for 5 units of time and resource value should be 1 in that interval of time.In that particular time no other process can use that resource with the resource having value 0.This is analogous to a vehicle using a particular road for 5 units of time in a particular direction and no other vehicle can travel in that road for that 5 units of time in opposite to the direction the former vehicle is travelling.

Now each vehicle need to start from a source and reach its destination following the constraints.
1.No two vehicle can collide ,that is no two vehicles can use the same resource(road in this case) in the opposite direction at any instant of time.Either the vehicle need to wait till the road is completely clear or take some other path (use some other resource which is available to reach destination).

Now we can compute the shortest path of the all the source -destination pair and in ideal condition each car can travel via the respective shortest path to reach its destination.

The objective of the problem is that without having collsions all the cars should reach to their destinations in minimum time.This leads to the question of scheduling the n process such that they are completed with minimum lateness.

Any ideas of solving this problem


texts: Breaking cycles in network graph by adding nodes and rerouting edges

texts:
I have a quite "common" need : making a directed graph (with one or several cycles) a directed acyclic graph (DAG).

But the way I want to achieve it is, I guess, way more specific : I would like to break cycles by duplicating nodes, and rerouting edges.

For exemple, for a graph with such a loop (A > B > C > A) :

I would like to get a non-looping graph like this one :

So here :

A new node A' has been created (duplicated from A)
The edge C > A has been deleted, replaced by C > A'
Another edge A' > D is also created, to preserve "adjacency": it was possible to go from B to D in the first graph, so I want this to be possible in the transformed graph too.

The case above may appear quite simple, but I am tryig to build an automated method to do that. I also have some cases with interwined cycles, which are way more complex to deal with. Finally, I aim to minimise the number of duplicated nodes. I usually work with graphs having less than 100 nodes.

The aim of all this is to be able to order nodes (using Kahn or DFS).

In the exemple above, A > B > C > A' > D seems the most intuitive order.
A > D > B > C > A' would also be a valid order, but I think it is less intuitive.

This is also the reason for keeping the original A > D arc, forcing the resulting order to be the first one mentionned above.

Any leads about how to do that ? Any existing methods or scripts (preferably python) ?
During my research, I have never found any information about such a way to break cycles, maybe I have not searched enough, or maybe not in the good direction.

Note : this question has also been posted on StackOverflow [here]


texts: Applications of algebraic geometry in Boolean complexity

texts: Representing boolean functions by polynomials or rational functions either perfectly or approximately is an important topic while polynomials and rational functions is the body of algebraic geometry. Why is algebraic geometry not that applicable to this area of complexity theory? Or atleast what are some of the important papers in representing boolean functions that uses algebraic geometry?


texts: worst case external fragmentation in buddy memory systems

texts:
Unfortunately, I can't find any freely available text with an estimation of exact upper bound of (external) fragmentation overhead for (binary) buddy memory allocator. Estimation  $M(1+ \log 2 m)$ (where $M$ is total memory size need to allocate and $m$ is the longest allocated block) seems too pessimistic.  I'm almost sure that for $m=2$ the bound is about $M*(3/2)$.

I guess the answer is contained in the article:

Errol L. Lloyd and Michael C. Loui
On the worst case performance of buddy systems
Acta Informatica
Volume 22, Number 4, 451-473, DOI: 10.1007/BF00288778

but I wouldn't want to pay EUR 34.95 for my "general interest" :)

[this question is actually repost from stackoverflow.com
https://stackoverflow.com/questions/6295558/worst-case-external-fragmentation-in-buddy-memory-systems
where I got an answer about  $M(1+\log 2 m)$ formula;
but I still don't know the exact bound]


texts: What are some algorithms where space complexity tends to be the limiting factor in practice?

texts:
Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? It puts a hard upper bound on what you can do, whereas time is only a factor if you're 'impatient.'
Preferably something practical.