texts: Reference request: pi-calculus with simultaneous events

texts:
I am interested in using the $\pi$-calculus as a basis for modeling workflows, and came up with an extension that proved useful in my modeling, namely the ability to specify that two or more channel communications should take place simultaneously. I can only imagine that a similar extension has been treated before, but I just cannot find it mentioned anywhere, most likely because I don't know what to search for.
I will describe the basic idea with a simplified variant of the calculus with only signal/query events (i.e. no passing of names over channels) but extended with a simultaneous events:
\begin{align}
\mathsf{Action}\quad \alpha ::={}&
   a && \text{query}
   \\
   {}\mid{} & \overline{a} && \text{signal}
   \\
   {}\mid{} & \alpha_1\& \alpha_2 && \text{simultaneous composition}
   \\
   {}\mid{} & \tau && \text{silent}
   \\
   \\
\mathsf{Sum}\quad S ::={}&
   \alpha.P && \text{prefix}
   \\
   {}\mid{}& S_1 + S_2 && \text{choice}
   \\
   {}\mid{}& 0 && \text{inert process}
  \\\\
\mathsf{Process}\quad P ::={}&
  P_1 \mid P_2 && \text{composition} \\
  {}\mid{}& \nu a\ldotp P && \text{new channel} \\
  {}\mid{}& !P && \text{replication} \\
  {}\mid{}& S && \text{synchronization}
\end{align}
We define the usual congruence relation $\equiv$ with scope extrusion on processes, and such that processes with composition forms a commutative monoid with neutral element $0$, and such that sums with choice form a commutative monoid also with neutral element $0$. Furthermore, actions with simultaneous also form a commutative monoid with neutral element $\tau$, and furthermore the submonoid generated by channel names $a$ has a group structure with $a^{-1} = \overline{a}$. For example, $a \& b \& \overline{a} \equiv b$.
The operational semantics has communication rule
\begin{align}
\frac{P \stackrel{\alpha_1}{\to} P' \quad Q \stackrel{\alpha_2}{\to} Q'}{P \mid Q \stackrel{\alpha_1 \& \alpha_2}{\to} P' \mid Q'}
\end{align}
and scoping rule
\begin{align}
\frac{P \stackrel{\alpha}{\to} P'}{\nu a\ldotp P \stackrel{\alpha}{\to} \nu a\ldotp P'}(\text{$a \not\in \alpha$})
\end{align}
The group structure on actions ensure that matching queries and signals cancel each other out. For example:
\begin{align}
  a\&\overline{b}\ldotp P \mid b\ldotp Q \mid c\&\overline{a}\ldotp R \stackrel{c}{\to} P\mid Q \mid R
\end{align}
But also:
\begin{align}
  a\&\overline{b}\ldotp P \mid b\ldotp Q \mid c\&\overline{a}\ldotp R \stackrel{a}{\to} P\mid Q \mid c\&\overline{a}\ldotp R
\end{align}


texts: Computational cost of Optimal Morse-Like codes?

texts:
Did anyone considered formally the computational complexity of Morse-like codes from an information theory point of view?

Morse Code

was optimized but designed before the advent of information theory,
difers from traditional prefix free codes in that all character codes end by one space (it's one way to say it, the other would be that codes are not prefix free and that they are separated by spaces in the output), and in addition
has 3 output characters, of variable costs (lengths): short dots, long dashes and spaces.

Optimal Prefix Free Code(s)

are well understood in information theory for uniform weights of output characters, and
only approximated (PTAS) for non-uniform weights of output characters.

I am considering the following questions:

Ignoring the variable cost of output characters (i.e. assuming that dots, dashes and spaces cost the same), what is the computational cost of computing an "optimal" Morse-Type Code?
Taking into account the variable cost of output characters, can one approximate in good time an "optimal" Morse-Type Code as we do for Prefix Free Codes?

I thought that at least the first question would have been covered already (the worst case and adaptive optimal algorithms are similar to that for optimal prefix free codes), but could not find a reference for it (even just the worst case for $n$ fixed), other than the three following ones:

one reddit page    https://www.reddit.com/r/compsci/comments/1mkx3p/huffman_encoding_vs_morse_code;

one econometrics page http://deeconometrist.nl/optimizing-morse-code/ (which mentions scientists but does not give references) from 2019;

a more theoretical one from 2015 https://eclecticlight.co/2015/10/22/reinventing-morse-code-using-modern-theory/ (which proposes to integrate Lempel Ziv with Morse-like codes)


texts: Polynomial Quantum Algorithm for Graph Isomorphism?

texts:
Possible Duplicate:
  NP-intermediate problems with efficient quantum solutions

Many suspect that quantum computers will not be able to efficiently solve NP-complete problems and  thus focus on the class NPI. Among the problems regarded as likely canditates to be in NPI are factoring and graph isomorphism. Known yet Shor's algorithm for efficient factorization, what steps have been done towards the design of a polynomial algorithm for graph isomorphism?


texts:
Has there ever been a proof technique to show that a language isn't in $\mathrm{P}$, by showing inductively there isn't any $k$ for which the language is in $\mathrm{TIME}(n^k)$?

e.g.: $L\notin \mathrm{TIME}(n^0)$,

$L\notin \mathrm{TIME}(n^k)\rightarrow L\notin \mathrm{TIME}(n^{k+1})$,

$\therefore L\notin \mathrm{P}$.

Is something of the sort feasible? Has it been used?


texts:
We know that a CESK machine can be defined as:

  a state-machine in which each state has four components: a (C)ontrol component, an (E)nvironment, a (S)tore and a (K)ontinuation. One might imagine these respectively as the instruction pointer, the local variables, the heap and the stack.

Ed Kmett writes

  Video from my recent twitch stream on CEK machines is up!

Matt Might writes:

  Writing CEK-style interpreters (or semantics) in Haskell

To Matt's credit - he also writes about CESK machines in racket and Java.

But when we read the original paper ("A Calculus for Assignments in Higher Order Languages") by Matthias Felleisen and Dan Friedman - we find that the original paper describes a CESK machine.

The paper also describes a CS machine - but not a CEK machine. The point being the Continuation and the Store are essential, but the Environment and the Continuation are negotiable.

My question is: Is a CEK machine an implementation of a CESK machine? (ie isn't the Store Essential?)


texts: Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$

texts:
Consider a circuit that takes as inputs numbers in $[0,1]$, and has gates that consist of the functions $\max(x, y)$, $\min(x, y)$, $1 - x$, and $\frac{x+y}{2}$.
The output of the circuit is then also a number in $[0,1]$.

Does anyone know if this model, or a closely related model, has been studied?

Specifically, I'm trying to solve the satisfiability problem for this circuit, namely computing the maximum value that can be attained by this circuit (it indeed attains a maximum, as it represents a continuous function in a compact domain).

Remark: my study of this model is via weighted temporal logics, so any models that relate to the latter might also come in handy.


texts: Noether’s Normalization Lemma for finite fields

texts:
My question is about theorems 4.1 and 4.2 in "Geometric Complexity Theory V".

The first theorem states that there exists an EXPSPACE algorithm for constructing h.s.o.p. for $\Delta[\text{det},m]$ (see definitions in the paper) on $\mathbb{C}$ (in fact on an arbitrary algebraically closed  field of characteristic zero).

The second provides a probabilistic poly-time Monte-Carlo algorithm for the same problem.

Can theses results be extended to an algebraic closure of a finite field?

As I understand, it is possible because Hilbert’s Nullstellensatz problem belongs to PSPACE in this case too. Heintz and Schnorr theorem also holds for fields of arbitrary characteristic...


texts: Testing emptiness property complexity in Sum of Squares Proof systems

texts:
Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$$ are linear homogeneous polynomials with $a_1,\dots,a_t\in\mathbb Z$ and $$f_1(x_1,\dots,x_n),\dots,f_n(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$$ are degree $d$-homogeneous polynomials.
We can test if $\mathcal T=\emptyset$ by Sum Of Squares proof system.

What is the complexity if $d$ and $t$ are $O(1)$ and $m\geq n$ holds?

Note since $m\geq n$ holds $\mathcal T=\emptyset$ almost always.
I am looking for general upper bounds on:

Number of bits in certifying polynomials

Degree of certifying polynomias

Time to get the certificates in SDPs.

in terms of the degree $d$ of the polynomials $f_i(x_1,\dots,x_n)$, $t$ the number of polynomials $h_i(x_1,\dots,x_n)$, $m$ the number of polynomials $f_i(x_1,\dots,x_n)$ and $n$ the number of variables in the polynomials and also $L$ the total number of bits to represent the polynomial coefficients of $f_i(x_1,\dots,x_n)$, $h_i(x_1,\dots,x_n)$?

Is answer to 3. $O((dt)^npoly(dtnL))$ where $L$ is number of bits to encode polynomials $f_1,\dots,f_n,h_1,\dots,h_t$ or much higher?
Is answer to 2. $O(polylog(dtnL))$ and is answer to 1. $O(poly(dtnL))$?
Is there good reference on these topics?

Updates Note testing 'Is $\mathcal T\cap\mathbb Z^n=\emptyset$?' is in $coNP$ and perhaps it is in $NP$ as well.


texts:
I know this could be considered a pointless question. However despite I am quite convinced that any possible model (i.e. UML, SysML, natural language, math, etc.) can be defined by means of a graph I do not know if there is a way to formally prove there exist an isomorphism between the set of Models and the set of Graphs.

I guess one should first define what a model is and I guess a possible answer is that a model can be considered as a sentence of the language defined by its meta-model. Thus models are languages. The question is therefore if there is an isomorphism between the set of languages and the set of graphs or, less formally, if it is provable that any possible language can be represented by means of a graph. I guess that the Chomsky works on languages could help but I can not find a reference on the Internet of such demonstration.


texts: How to do organize papers, urls and other TCS related resources?

texts:
This question is a try of making
Do you use any article organizers? question suitable for TCS (as suggested in meta answer https://cstheory.meta.stackexchange.com/a/359/6133 )

Question similar -> about organizers, but ...

What organizer do you use, know that are possible to handle TCS related meta-information ?

We organize our knowledge in many ways.

Some of them are hierarchical, as complexity zoo.
Others more like graph -> let's take algorithms as vertices and how they are related with each other as edges
As another extreme, some knowledge we organize like sets and think about it in terms of sets intersections - to be more specific conjunction of criteria, just like flat tags.

I would love to see tool that combines many approaches and enables collaboration between researches, even better, if between strangers (possibly with crowdsourcing).

Above might relate to Academia in general.

What I mean is that TCS people have more CS skills, knowledge and are able to apply it in organizing their own information.

I believe our approach in organizing information is different, partially because we use concepts of graphs, sets, ontology in our job, so they are natural to us and we are able to handle complex models of organizing information, which might use or even might all of mentioned. On the other hand, people from non scientific fields (especially not math related), might have problems with using such models and I believe that's the reason why almost all tools have so much simplified models.

I use "hacks", "tips&tricks" to extend them, but it's not comfortable and not build-in. I even run sometimes analysis tools on my own collections of data - but again, in hacky, why. I would love to see really flexible tools, suitable for CS / TCS people.


texts: Is there any exsiting research on this kind of "sorting with constraint" problem?

texts:
I have been interested in this kind of "sorting with constraint" problem:

Given $n$ items $\{S_1 ,S_2 ,...S_n\}$ with corresponding weight $w_i ,i=1,2,...,n$, we want to sort these $n$ items (i.e. for $p_1 ,p_2 ,...,p_n$, we have a sequence that $S_i$ is at the $p_i$th position) with those constraints and goal below:

Constraint1: for some $<i,j>$, there must have $p_i<p_j$
Constraint2: for some $<i,k>$ that have constraint1, there could have some $j$ that cannot be $p_i<p_j<p_k$
Goal: maximize $\sum_{1}^{n}p_iw_i$ (or some other loss function that we can call it "sort")

We can assume that there are $O(n)$ constraint1 and constrain2.

Here is my curiosity about whether there has been any research on this kind of problem, especially about:

Obviously this problem is an $NP$ problem. Is it $NP-hard$ (which we can also be inferred that it is $NP-complete$)?
If this is an $NP-complete$ problem, is there any approximation algorithm? In what ratio will this approximation algorithm performs?
Consider a special condition: for $\{S_1 ,S_2 ,...S_n\}$, only O(1) items of them have non-zero weight. What will the complexity of this question--and the corresponding algorithm to solve it--be?


texts: Is there a succinct representation for all problems?

texts: Recently I saw an interesting question on succinct problems from here. I was wondering if all problems have a succinct representation(It would be great if you can provide me a reference/proof). When I read the paper linked in the post, I could find mostly only graph problems with succinct representation. Can a problem like testing for primality have a succinct representation? Is there a proof/reference for this anywhere?


texts: Sorting using comparisons that are not simple mappings of simple comparisons

texts:
The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x.  One can also provide a cmp argument (sort(x, cmp=f)), which is a two-parameter function that will be used to compare pairs of elements of x.  In general, the cmp function will be called $O(len(x) \log len(x))$ times.

More efficiently, one can provide a key argument (sort(x, key=f)), which will be called $O(len(x))$ times to transform each element of x into "key values" which will then be compared by the intrinsic comparison operator associated with the type of the key values.

A developer of the key feature has asserted that using key is always more efficient than using cmp.  This leads to a somewhat amorphous atheoretical question:

Does there exist a universe of values $U$ which can be compared by a "fast" algorithm but for which there is no "fast" algorithm which maps elements of $U$ in an order-preserving way into elements of a "simple" key set $K$ which can be compared by a "fast" algorithm?  I assume that all the orders are total orders.  The exact meaning of "simple" is unclear to me, but my intuition is that "finite sequences of integers under lexicographic ordering" is a superset of all totally-ordered sets that I would consider "simple".  The condition of "simplicity" is what excludes the trivial solution of setting $K = U$ and using the identity as the key mapping, and the simplicity of $K$'s comparison function is what excludes having the key mapping simply encode elements of $U$ into $K$ in some straightforward way.

In a sense, what I'm looking for is a total ordering which is not a "simple" transformation of "simple" totally-ordered set.


texts:
Its been a while since I took my theory course, but I recall that Hilberts Decision problem was shown to be false.

  By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

From Wikipedia.

But In my AI course, we learned of an algorithm to prove or disprove new statements using the axioms known as Resolution by refutation. Simply take the a negation of the statement you want to prove, and use the axioms to show it either leads to an empty clause (true) or non-empty clause (false).

So my question is: What am I missing from these two seemingly contradictory statements? On one hand the literature states there exists no algorithm to determine if a statement is provable from the axioms, and on the other hand, I am presented with an algorithm that proves (or disproves) a statement from the axioms. What am I confused or incorrect about here?


texts: Compute Nash Equilibrium for 2-player games

texts:
I want to compute a mixed strategy that will be the Nash Equilibrium of the game.
I have used my knowledge in order to create the system for the mixed strategy.
I concluded on a system with 3 variables and 5 constrains.I am not able to solve this system using the common Gaussian Elimination method.This system is a linear program from what I can imagine.I have searched google for similar examples but all the examples was on 2-player games with only 2 strategies per player.In those games was quite easy to compute the mixed strategy.I am thinking of using the simplex method for finding the NE but I am thinking that this is weird for such a small game...
Are there simpler method that can be used in computing a NE profile?
Thank you.


texts: partition to min the max number of intersections

texts:
Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any store is minimized.

Does anyone recognize this problem? I have the slight feeling that it is some standard set or cut problem in disguise, but I just cannot find the right one.


texts: Lower Bounds for Frege and Extended Frege

texts:
Wikipedia [1] states that the best known lower bound for size of Frege proofs is quadratic, and that there is no known superlinear lower bounds for the number of lines of Frege proofs.

Questions:

1) What is the best known lower bound for the number of lines of extended Frege proofs?

2) What is the best known lower bound for the size of extended Frege proofs? Is it still quadratic as in Frege?

3) Tree-like Extended Frege can simulate DAG-like Extended Frege in a polynomial number of steps. Are there any superlinear lower bounds for size/number of lines on tree-like extended Frege?

4) What are the tautologies that lead to the linear lower bound for number of lines and to the quadratic lower bound for the size in Frege proofs as stated at wikipedia?

Obs: I'm aware of the fact that for constant depth Frege we have size lower bounds of the order of $2^{\Omega(n^{6^{-d}})}$. But I'm really interested in full power Frege and Extended Frege.

[1] https://en.wikipedia.org/wiki/Frege_system


texts: Is the maximum independent set in cubic planar graphs NP-complete?

texts:
In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation from vertex cover and for vertex cover (I suppose in cubic planar graphs) they cite the paper of Garey, Johnson and Stockmeyer 1976.

When I looked at their DBLP entry, there is a single paper that matches the description of the mentioned paper:

Some Simplified NP-complete Graph Problems.

Having checked the paper, the reduction for vertex cover in graphs of maximum degree 3 is for general graphs, not planar graphs. For planar graphs, they only have a reduction that shows hardness on planar graphs of maximum degree 6, not 3 (already the gadget has vertices of degree 6).

I'm wondering if I'm missing something here since there are consequent papers building upon the aforementioned comment of the book.


texts: Separation between coarse correlated equilibria and correlated equilibria

texts:
I am looking for examples of techniques for proving price of anarchy bounds that have the power to separate the price of anarchy over coarse correlated equilibria (the limiting set of no-external-regret dynamics) from the price of anarchy over correlated equilibria (the limiting set of no-swap-regret dynamics). Are natural separations of this type known?

One obstruction towards separating these two classes is that the most natural (and common) way to prove price of anarchy bounds is to observe only that at equilibrium, no player has any incentive to deviate to playing his action at OPT, and to somehow use this to connect the social welfare at some configuration to the social welfare of OPT. Unfortunately, any proof that the price of anarchy over coarse correlated equilibria is small that only considers deviations of each player to a single alternative action (say the action from OPT) necessarily also holds for correlated equilibria, and so cannot provide a separation. This is because the only difference between a coarse correlated equilibrium and a correlated equilibrium is the ability of a player in a correlated equilibrium to simultaneously consider multiple deviations, conditioned on his signal of the play profile drawn from the equilibrium distribution.

Are such separations known?


texts: Enumeration of discrete objects for which recognition problem is coNP-complete

texts:
Is there any problem of enumeration of discrete objects for which problem of recognizing of these discrete objects is coNP-complete (or NP-complete), but it is possible to enumerate all these objects in output polynomial time?

For example (but I don't know about the complexity of enumeration) the problem of enumeration (generation) all Hamiltonian graphs with no more than n vertices.


texts:
XORification is the technique to make a Boolean function or formula harder by replacing every variable $x$ by the XOR of $k\geq 2$ distinct variables $x_1 \oplus \ldots \oplus x_k$.

I am aware of uses of this technique in proof complexity, mainly to obtain space lower bounds for resolution-based proof systems, e.g., in the papers:

Eli Ben-Sasson. Size space tradeoffs for resolution. STOC 2002, 457-464.
Eli Ben-Sasson and Jakob Nordström. Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. ICS 2011, 401-416.

Are there other uses of this technique in other areas?


texts: How hard is deciding the existence of a polygonization with prescribed perimeter?

texts:
Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or maximum) enclosed area is NP-complete. The answer to this post shows that it is NP-complete to decide the existence of a polygonization with some prescribed area.
Meanwhile, Minimum perimeter polygonization of 2D lattice points is a variant of the NP-complete Euclidean TSP. However, complexity of the maximization version of planar Euclidean TSP is an open problem. The authors conjecture that the Maximum TSP for Euclidean distances in the plane is an NP-hard problem.
I am interested in the complexity of deciding the existence of a polygonization of a set of 2D lattice points (in Euclidian plane) with prescribed perimeter. I suspect that it is NP-complete. What is known about its complexity?


texts: Approximating Front Size of Asymmetric Matrices

texts:
The front size of a matrix $A$ is the largest number of non-zeros below the diagonal in any column of its Cholesky factor. If $A$ is symmetric then the minimum front size of $A$ is equal to the treewidth of $G(A)$. Here $G(A)$ is an undirected graph with $A$ as its adjacency matrix. Hence, front size of symmetric matrix can be approximated by using the approximation algorithms of treewidth. The best known factor is $O(\sqrt{\log{n}})$.

I noticed that an approximation algorithm (to approximate Kelly-Width) in one of my recent papers, implies $O({\log}^{3/2}{n})$ approximation for front size of asymmetric matrices.

Minimizing front size is a fundamental problem and is very crucial in multi-frontal algorithms. I am wondering if there is an earlier approximation algorithm for front size of asymmetric matrices.

I will be surprised (and simultaneously excited) if the algorithm mentioned in my paper is the first approximation algorithm with non-trivial approximation factor.

  Is there an approximation algorithm for the front size of asymmetric matrices, prior to our work ?


texts: Where is the counting hierarchy if polynomial hierarchy collapses?

texts:
Supposing if $P^{\#P}\subseteq BPP$ then polynomial hierarchy collapses.

Does the counting hierarchy collapse as well?
Irrespective of $P^{\#P}\subseteq BPP$ are there any collapse results of counting hierarchy that imply collapse results of polynomial hierarchy and vice versa?


texts: Self-organizing maps algorithm(Kohonen networks)

texts: In self-organizing maps(SOM) algorithm described here it is said about the weights of nodes and data items. If using this algorithm for sine function approximation given a few points are the nodes - points and weights - coordinates?


texts: Are there Similar Distance Binary Error Correcting Codes?

texts:
I'm trying to find a low distortion embedding of the trivial metric space into hamming space.

It seems this should be doable by using a large set of low dimensional vectors, with approximately equal pairwise distance.

My question is if it makes sense to expect error correcting codes to have this property?

Usually when designing error correcting codes, we are interested in finding the highest achievable rate, given a minimum distance between points. A similar question is to consider, instead of the minimum distance, the ratio between the maximum and minimum distance, $\rho=max/min$. Given $\rho$, what codes should one consider for maximizing the rate?

I tried to count the distances in some of the codes from this list of optimal binary codes:

The $(7,2^3,4)$ code has all distances equal to four, so $\rho=1$.
The $(8,2^4,4)$ code has $112$ pairs of distance $4$ and $8$ of distance $8$, so it has $\rho=2$.
The $(9,40,3)$ code has maximum distance $8$, so $\rho=8/3$.
The $(24,2^{12},8)$ golay code has maximum distance $24$, so $\rho=3$.

The two later codes are nearly as bad as possible. Are there any codes for which I shouldn't expect this to be the case? If not, can I at least say something about the distribution of distances being fairly concentrated?


texts: Complexity of summing up integral powers

texts:
Let $x$ be a rational number, and $S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing $S_n(x)$ correct to $d$ decimal places? Is this a Hard problem?

It is clear from Faulhaber's formula that the problem takes $O(x)$ steps to solve for natural $x$. But I'm not very clear about rational $x$.


texts: Generalization of SAT, where we replace OR with another symmetric function

texts:
Let $\sigma(y_1,\dots,y_k)$ denote some boolean symmetric function on $k$ boolean inputs, $\sigma:\{0,1\}^k\to\{0,1\}$.  In $k$-SAT, an instance is a conjunction of clauses, where each clause is the logical-or of $k$ literals.  Consider replacing logical-or with $\sigma$, so that each clause contains $\sigma$ applies to $k$ literals.  In other words, $\varphi=\land_i \sigma(\ell_{i,1},\dots,\ell_{i,k})$ and each $\ell_{i,j}$ is a literal (some $x_i$ or $\neg x_i$).

For which functions $\sigma$ is this NP-complete, and for which functions is this solvable in polynomial time?  Can we classify the hardness of this problem for each possible value of $\sigma$?

Of course for $\sigma(y_1,\dots,y_k)=y_1\lor \dots \lor y_k$, we know this is hard: it is exactly $k$-SAT.  What about other functions $\sigma$?  For which $\sigma$ is it hard?  If it helps, we can characterize the function $\sigma$ by a set $S\subseteq\{0,1,2,\dots,k\}$, where $\sigma(y_1,\dots,y_k)$ is 1 if and only if $y_1+\dots+y_k\in S$; so we can ask, for which $S$ is this hard?

The variant that's probably more interesting to me: for which $\sigma$ is this hard, if we restrict all variables to appear in positive form (there are no negations in any of the literals)?  I recently learned that NAE-3SAT remains hard even with this positivity restriction, so for $S=\{1,2\}$ (i.e., $\sigma(y_1,\dots,y_k)=(\neg y_1 \land \dots \land \neg y_k)\lor (y_1\land \dots \land y_k)$) the problem is hard.  What about other choices of $\sigma$ (i.e., of $S$)?

My motivation: curiousity.  This was prompted by Complexity of a linear algebra problem.  There's some relationship to some variant of that problem, which arises if for some $k$, $f(x)=1$ for $x\in S$ and $f(x)=-1$ for $x\in\{0,1,2,\dots,k\}\setminus S$.  But mostly, I'm just curious.


texts: Does the 0-1 principle apply to merge networks?

texts:
For sorting networks, the 0-1 principle says that if it can sort any sequence of 0's and 1's, then it can sort any list.

What if I want to build a comparison-swap network for merging two pre-sorted lists.  Can I still rely on the 0-1 principle to determine if my network is correct?

Note: If so, this means it's possible to determine whether a network is a merging network in polynomial time (since there are only polynomially-many pairs of sorted lists of zeros and ones)


texts:
I have been reading a lot on the theory of Turan graphs, but I could not find anything on the graphs I am interested in. They are somewhat between complete $k$-partite graphs and Turan graphs.

Let $G=(V,E)$ a graph such that $V$ is partitioned into $r$ subsets $V_1, \dots, V_r$. Let $n<r$ be a positive integer such that for all $1\leq m \leq n$ and for all $(i,j)\in V_m^2$, the edge $(i,j)\in E$ exists in the graph $G$. For the remainings sets, the edges do not exist in $G$: for all $n<m\leq r$ and $(i,j)\in V_m^2$, $(i,j)\notin E.$

In others words, in contrast with the Turan graphs where $G$ would contain no $(r+1)$-clique, here I consider exactly $n$ such cliques. Note that if $n=r$, then $G$ is the complete $r$-partite graph.

My question then is: what can we say about the number of edges in $G$ ?

Does this graph has a name ?

Thanks a lot!


texts: Refinement of the hierarchy theorem of a complexity class

texts:
Say $\mathrm{CTIME}$ is some complexity measure, syntactic or semantic (e.g. $\mathrm{DTIME}$ or $\mathrm{BPTIME}$).
If we already know that for some $f(n) = \omega(n)$, $\mathrm{CTIME}(n) \subsetneq \mathrm{CTIME}(f(n))$, then, by a standard padding argument [KV87], for any $h(n)$ such that $h^c(n) = \Omega(f(n))$ with some constant $c$,

\begin{align*}
    \mathrm{CTIME}(n) \supseteq \mathrm{CTIME}(h(n)) &\implies \mathrm{CTIME}(h^i(n)) \supseteq \mathrm{CTIME}(h^{i+1}(n)) \\
& \implies \mathrm{CTIME}(n) \supseteq \mathrm{CTIME}(f(n)).
\end{align*}
Therefore $\mathrm{CTIME}(n) \subsetneq \mathrm{CTIME}(h(n))$. As an example, authors in [KV87] show that $\mathrm{BPTIME}(n^{\log n}) \subsetneq \mathrm{BPTIME}(2^{n^\epsilon})$ from $\mathrm{BPTIME}(n) \subsetneq \mathrm{BPTIME}(2^{O(n)})$.

Can we further improve this result as follows? (My intuition is NO but I don't know why. Maybe it has something to do with whether we can well order all probable "nice" functions, by defining $\textrm{"}f \leq g\textrm{"}\  :=\   \textrm{"}f=O(g)\textrm{"}$.)

  We only need $h$ to satisfy that the union of "intervals"
  $$
  [\Omega(t(n)), O(h(t(n))]
$$
  over all time-constructable $t(n)$ "covers" [$\Omega(n), O(f(n))$].

Suppose, throughout this process, we only consider "nice" function constructed by recursively applying arithmetic operation, $2^x$ or $\log x$ (e.g. $n^{\log n/\log \log n}$).


texts: Is "best-possible obfuscation" really what its name indicates?

texts:
The paper On Best-Possible Obfuscation defines what is calls "best-possible obfuscation",

and proves (propositions 3.4 and 3.5) that efficient best-possible

obfuscators are exactly efficient indistinguishability obfuscators.

However, it is not clear to me that their definition corresponds to their name.

Inspired by the paper On the (Im)possibility of Obfuscation (though obviously not

using that paper's definition), I define the "better obfuscator hypothesis" as follows:

  There exists a probabilistic polynomial-time algorithm $\operatorname{Obf}$ such that,

  with all probabilities involving $\operatorname{Obf}$ implicitly taken over $\operatorname{Obf}$'s randomness in

  addition to what is indicated explicitly in the subscript, one has the following:

  $\;$ for all circuits $C$, $\;\; \operatorname{Prob}\left(\operatorname{Obf}(C\hspace{.03 in}) \text{ is a circuit that computes the same function as } C\right) \: = \: 1$
  and
   $\;$ for all families of polynomial-size circuits $\mathcal{F}\hspace{-0.02 in}_0$ and $\mathcal{F}\hspace{-0.03 in}_1$, if

   $\;$ $\;$ for all adversaries $\mathcal{B}$ that are restricted to polynomially-many

   $\;$ $\;$ oracle queries but are (otherwise) computationally unbounded,

   $\;$ $\;$ $\left|\hspace{.02 in}\operatorname{Prob}_{C\leftarrow \mathcal{F}_0}\hspace{-0.05 in}\left(\mathcal{B}^C\hspace{-0.03 in}(\operatorname{size}(C\hspace{.03 in})) = 1\hspace{-0.02 in}\right)-\operatorname{Prob}_{C\leftarrow \mathcal{F}_1}\hspace{-0.05 in}\left(\mathcal{B}^C\hspace{-0.03 in}(\operatorname{size}(C\hspace{.03 in})) = 1\hspace{-0.02 in}\right)\right| \;$ is negligible
   $\;$ then
   $\;$ $\;$  for all feasible adversaries $\mathcal{A}$,

   $\;$ $\;$ $\left|\operatorname{Prob}_{C\leftarrow \mathcal{F}_0}\hspace{-0.05 in}(\mathcal{A}(\operatorname{Obf}(C\hspace{.03 in})) = 1)-\operatorname{Prob}_{C\leftarrow \mathcal{F}_1}\hspace{-0.05 in}(\mathcal{A}(\operatorname{Obf}(C\hspace{.03 in})) = 1)\right| \;$ is negligible

  .

(With respect to non-uniform adversaries, indistinguishability obfuscation

is equivalent to replacing "families" with "sequences" in that definition.)

Questions:
Is the "better obfuscator hypothesis" known to be false?

Is the "better obfuscator hypothesis" known to be equivalent to the existence

of an efficient best-possible obfuscator, as defined on page 7 of paper #1?


texts: What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?


texts: "The Solution Problem" - How to get credit for your work as an undergrad?

texts:
I have come to a rather startling discovery in regards to a question that has been posed to me a number of times through my now almost 1 year of CS studies.

Solving this problem is of great interest to many people, and if I have indeed done so... What do I do?

I see a few options, but none seem to ensure that my work gets recognized as my own: I could stash away the notes till the time comes for my masters thesis. This would force me to share both work and credit with my supervisor, though. I could attempt to publish it... But who would want to take work from a 9 months old computer scientist?

I am at a loss - in attempting to solve a difficult problem I have only given rise to an even more difficult one!


texts: What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$? In other words, are problems that admit a polynomial time local search approximable? Do approximable optimization problems imply a local search algorithm in general?


texts:
I am interesting in the sunflower system and its applications in computer science.

Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for all $i \neq j$. And $Y$ is called as the core and $A_i - Y$ is called petals.

A family of sets $F$ is called $s$-uniform is all the sets it contained possess $s$ elements.

Erdos and Rado proved that for a $s$ uniform family of sets $F$ , $F$ must contain a $k$-sunflower system  petals if $|F| > s!(k-1)^s $.

This result is called the sunflower lemma and has many important applications.

Erdos conjectured that for every $k$ there exist a constant $c_k$ such that the upper bound should be $c_k^s$ every $s$-uniform family $F$.
(The  sunflower conjecture)

Unfortunately, this conjecture is still open for $k=3$.

Here is what I want to know.

If we limit the number of elements in the universe $U$.Suppose $|U|$= $u$. Then the problem turns out be:

Given a universe with $u$ elements, and $s$-uniform family $F$ of sets containing the elements in $U$, we supposed can find sequence of constants $c_1$, $c_2$, $c_3$ ,... such that every $s$-uniform family $F$ contains a $3$-sunflower system if $|F|>$ $c_i^s$ and $|U|=i$.

Moreover, if we could prove that the sequence $c_i$ converges to a constant $c$, then it seems we can prove the sunflower conjecture.

But I cannot find such result.It might be that this approach is too stupid or too hard.

Could any one provide the state of art of sunflower lemma and the conjecture(finite version is also OK).

Here is some I can provide.
There is a chapter in Junka's book The Extremal Combinatorics.

The paper above is one of its application(finite version)

On Sunflowers and Matrix Multiplication N Alon et.al


texts:
In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat.

Cubic Planar Positive 1-in-3 Satisfiability
Instance: A boolean formula $B=(X,C)$ where $X$ is a set of variables, $C$ a set of 3-element subsets over $X$ (clauses), and graph of B is a cubic planar graph.
Question: Does there exist a truth assignment for $X$ such that each clause is $C$ has exactly one true variable?

(see the note of the https://cstheory.stackexchange.com/a/42605/47855 regarding terminology)

Then they prove that a particular tiling problem is NP-complete by a reduction from Cubic Planar Positive 1-in-3 Sat.
The following note is given after their reduction:

  While the reduction from this version of SAT to the tiling problem we gave in the previous section is parsimonious, this does not show that the counting problem is #P-complete, since we do not have such a result for Cubic Planar Positive 1-in-3 SAT. We leave this as an open problem for the reader.

This gave me the impression that the counting version of 1-in-3 Sat is indeed #P-complete, but I couldn't find any source claiming this. Is the counting version of 1-in-3 Sat #P-complete?


texts: References for the computational complexity of training neural networks

texts:
I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.

In particular, I'm trying to study questions like:

How is training complexity related to network topology ?
How is training complexity related to the complexity of the decision boundary?


texts:
Let

$L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \}$

(where $n$ is thought of as encoded in binary).  Then what can we say about the computational complexity of $L$?  It's clear that $L\in\mathsf{EXP}$.  And if I'm not mistaken, the amazing "BBP-type" algorithms for computing the $n^{th}$ bit of $\pi$ using quasilinear time and $(\log n)^{O(1)}$ memory, without needing to compute the previous bits, yield $L\in\mathsf{PSPACE}$.

Can we do even better, and place $L$ (say) in the counting hierarchy?  In the other direction, is there any hardness result whatsoever for $L$ (even an extremely weak one, like $\mathsf{TC}^0$-hardness)?

An interesting related language is

$L' = \{ \langle x,t\rangle : x\text{ occurs as a substring within the first }t\text{ digits of }\pi \}$

(where again, $t$ is written in binary).  We have

$L' \in \mathsf{NP}^L$

and hence $L' \in \mathsf{PSPACE}$; I'd be extremely interested if anything better is known.


texts: Is there a theory that combines category theory/abstract algebra and computational complexity?

texts:
Category theory and abstract algebra deal with the way functions can be combined with other functions.  Complexity theory deals with how hard a function is to compute.  It's weird to me that I haven't seen anyone combine these fields of study, since they seem like such natural pairs.  Has anyone done this before?

As a motivating example, let's take a look at monoids.  It's well known that if an operation is a monoid, then we can parallelize the operation.

For example in Haskell, we can trivially define that addition is a monoid over the integers like this:

instance Monoid Int where
    mempty = 0
    mappend = (+)

Now if we want to compute the sum of 0 to 999, we could do it sequentially like:

foldl1' (+) [0..999]

or we could do it in parallel

mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel

But parallelizing this monoid makes sense only because mappend runs in constant time.  What if this weren't the case?  Lists, for example, are monoids where mappend does not run inconstant time (or space!).  I'm guessing this is why there is no default parallel mconcat function in Haskell.  The best implementation depends on the complexity of the monoid.

It seems like there should be a convenient way to describe the differences between these two monoids.  We should then be able to annotate our code with these differences and have programs automatically choose the best algorithms to use depending on a monoid's complexity.


texts:
Definitions:
Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced subgraph (that is, the resulting graph is a disjoin union of cliques).

The class of $k$-trees is defined as follows: a complete graph with $k$ vertices is a $k$-tree; a $k$-trees with $n + 1$ vertices $(n > k)$ can be constructed from a $k$-tree $T$ with $n$ vertices by adding a vertex adjacent to all vertices of a $k$-clique of $T$, and only to these vertices.

Question:
Does exist a linear-time algorithm to solve Cluster Edge Deletion on 2-trees?


texts: Bounds on the size of smallest decision tree for a boolean function?

texts:
Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?

It seems to me that assuming $f$ has $n$ variables and $m$ true points then any minimal decision tree has at most $$ 2^{\lceil{\log_2 m}\rceil}−m+m⋅(n−\lceil{\log_2 m}\rceil) $$ 0-leaves (obviously, one can take the dual as well). I am wondering if whether this sort of thing has been covered before (I presume it has somewhere).


texts: Max-weight connected & co-connected subgraph problem

texts:
The max-weight connected subgraph problem (MWCS) may be described as follows:
given a simple graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, one
seeks for a subset $L\subseteq V$ for which the spanned subgraph $G[L]$ is
connected and $\sum_{v\in L}w(v)$ is maximal.

The MWCS problem is known to be NP-hard (see https://arxiv.org/abs/1409.5308).

Consider the following variation: in the same settings, one seeks for a vertex
set $L$ for which the spanned subgraphs $G[L]$ and $G[V\smallsetminus L]$ are
both connected, and $\sum_{v\in L}w(v)$ is maximal.

My question is the following: is it possible that this variation takes the
problem out from the NP class?  If not - is it easy to see that it is still
hard, given that the original problem is hard?

And does it make a difference if one asks
$\sum_{v\in L}w(v)-\sum_{u\in V\smallsetminus L}w(u)$ to be maximal?


texts: Reconstruction of sparse vectors from random matrices

texts:
In the paper [A], the following linear algebra result (Lemma 5 in [A])  is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries.

Lemma: Let $1 \le s \le n$. There is a choice $k = O(s)$ and a random linear function $L : \mathbb{R}^n \rightarrow \mathbb{R}^k$ (generated from $O(k\log n)$ random bits), and a recovery procedure that on input $L(x)$ outputs $x' \in \mathbb{R}^n$ or $DENSE$ such that, for any $s$-sparse vector $x$, the output is $x'=x$ with probability $1$ and, for any non-$s$-sparse vector $x$, the output is $DENSE$ with high probability.

Is there a reference for this result or an easy argument why this is true?

[A] Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems.
Hossein Jowhari, Mert Sağlam, Gábor Tardos
arXiv


texts: Are there problems whose average case complexity is the same as their worst case complexity? What are the underlying properties of these problems that makes reducing the worst case to the average case possible?


texts: Is the unbounded fan-in model realistic?

texts:
Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates?

As I understand, standard silicon ASICs are made of so-called cells where the number of input signals in the largest cells is small (e.g. never exceeds a fan-in of 100).


texts: Name of (and solution to) this generalization of linear assignment

texts:
I would like to know if the following problem is known and has any efficient solution.

Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no row or column is selected more than $b$ times.

This can be re-formulated as the following integer linear program:
\begin{align}
\mbox{maximize} &\sum_{1\le i,j\le n} s_{ij}x_{ij},\\
\mbox{subject to} & \sum_{1\le i,j\le n} x_{ij} = a,\\
& \sum_{1\le i\le n} x_{ij} \le b \quad\forall 1\le j\le n,\\
& \sum_{1\le j\le n} x_{ij} \le b \quad\forall 1\le i\le n,\\
& x_{ij}\in\{0,1\}\quad\forall 1\le i,j\le n.
\end{align}

Thank you very much in advance for your help!


texts: A graph parameter possibly related to treewidth

texts:
I am interested in graphs on $n$ vertices which can be produced via the following process.

Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as unused.
Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more  unused vertices in $G$, and is not connected to any used vertices in $G$. Label $v$ as unused.
Label one of the vertices in $G'$ to which $v$ is connected as used.
Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.

Call such graphs "graphs of complexity $k$" (apologies for the vague terminology). For example, if $G$ is a graph of complexity 1, $G$ is a path.

I would like to know if this process has been studied before. In particular, for arbitrary $k$, is it NP-complete to determine whether a graph has complexity $k$?

This problem appears somewhat similar to the question of whether $G$ is a partial $k$-tree, i.e. has treewidth $k$. It is known that determining whether $G$ has treewidth $k$ is NP-complete. However, some graphs (stars, for example) may have much smaller treewidth than the measure of complexity discussed here.

4th October 2012: Question cross-posted to MathOverflow after there was no conclusive answer after a week (though thanks for the info about causal flows).


texts:
On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$.
Below this there is a statement which says $XP\not = NP$ unless $P=NP$.

Is there a reference for proof for these two $XP$ statements?


texts: Literature for restrictions that make NPC-Problems to P

texts:
The boolean satisfiability problem is in $\mathcal{NPC}$. But if you only get Horn clauses, it is in $\mathcal{P}$.

I've already heard similar statements. Do you know a more general statement when problems in $\mathcal{NPC}$ get to problems in $\mathcal{P}$ because of restrictions?

If something like that does not exist, do you know literature where such restrictions are described?


texts: is "spaghetti sort" really O(n) (even as a thought experiment) ?

texts:
I`m referring to the notion described here: http://en.wikipedia.org/wiki/Spaghetti_sort

In the analysis section the author admits that considering it to be O(n) requires the assumption that the act of identifying and then removing the longest spaghetti rod which
has stopped your hand from descending further is an O(1)  rather than an O(n) or O(logn) operation - this seems to me a rather unreasonable assumption especially if many rodes of relatively simillar height exist.
Alternatively it seems equivalent to assuming that one can pick the longest rode from a heap of rodes arbitrarily spread on a table at O(1) without going through the "leveling" procedure at all.


texts: Initialization of errata evaluator polynomial for simultaneous computation in Berlekamp-Massey for Reed-Solomon

texts:
This is a continuation of this post on SO.

I am trying to implement an errata (errors-and-erasures) decoder for Reed-Solomon. My current approach is to use Berlekamp-Massey (because it's the most common algorithm and there are a lot of optimizations tricks that are known, but the Euclidian algorithm is very similar and should be pretty much the same for my case: same initialization variables and same output, only the calculation method is different).

What I know:

the common errors(-only) Berlekamp Massey to compute (only) the errors locator polynomial.
how to extend standard BM to simultaneously compute the errors evaluator polynomial.
how to extend standard BM to compute errata (errors-and-erasures) locator polynomial.

What I don't know: how to mix both extensions, to simultaneously compute the errata (errors-and-erasures) evaluator polynomial. In fact what I think I miss is the initialization value for the errata evaluator support polynomial A (see below).

To be clearer, here are some figures that describe the variations of BM that I cited above, from the book "Algebraic codes for data transmission", Blahut, Richard E., 2003, Cambridge university press. (readable here, chapters 7.4 and 7.5):

Standard (errors-only and locator polynomial Lambda only) BM:

BM extension to simultaneously compute the evaluator polynomial (named Gamma):

BM extension to decode errata (errors-and-erasures) but only locator polynomial:

As of now, I just compute the erasures evaluator polynomial from the erasures locator polynomial, and I initialize Gamma = A = erasures evaluator polynomial (just like Lambda = B = erasures locator polynomial, see post on SO), but at the end of BM, the errata evaluator polynomial contains terms of too high order that should have been cancelled, for example:

Gamma:  34x^11 + 187x^10 + 200x^9 + 43x^5 + 129x^4 + 5x^3 + 62x^2 + 8x + 1

Instead of the correct:

Gamma:  43x^5 + 129x^4 + 5x^3 + 62x^2 + 8x + 1

I guess my initialization of the errata evaluator support polynomial A is wrong (when there's no erasures, Gamma = 1 and A = 0, here with erasures they are both initialized with the erasures evaluator polynomial), but I could not find any academic paper describing the initialization values.

The only paper I have found describing an errata decoder computing simultaneously the locator and evaluator polynomials is using the Euclidian algorithm instead of BM (from "Efficient algorithms for decoding Reed-Solomon codes with erasures", Todd Mateer, Clemson University, Clemson, SC (2014)):

But here it seems they are just using the same approach I did: initializing Gamma and A (here Omega and little omega) with the erasures evaluator polynomial, and they just do some trimming inside the conditional branches and at the return of the algo by limiting the indices of Omega.

Do someone know what values should Gamma and A be initialized with to avoid playing with the "too high order terms trimming hack"?


texts: How to show that ECTL* is more expressive than CTL* $\cup$ Büchi (with an example)

texts:
I am looking for a preferably simple property that is expressible in ECTL* but not in CTL* and not in Büchi, with a citable reference to the proof.

Details of what I've tried:

I've tried a modification of Wolper's even-property: the property $Eeven$ that holds for every Kripke structure containing a path where p holds at least in every even state. The ECTL* formula $E (\mathcal{A}_{even}(p))$ specifies $Eeven$ (with $\mathcal{A}_{even}$ being the Büchi automaton that accepts words where p holds at least in every even state).

Because of the existential path quantifier, $E (\mathcal{A}_{even}(p))$ is trivially not expressible in Büchi.

But is there a short proof that $E (\mathcal{A}_{even}(p))$ is not in CTL*? Or a reference to a proof (of any length)?
After looking at Computation Tree Logic and Regular $\omega$-Languages, Wolfgang Thomas, 1989, I can think of a proof showing $Eeven$ is counting - but that would definitely not be a short proof :( Would using $Eeven$ is not star-free or $M(Eeven)$ is not group-free be any easier?


texts: Complexity of counterexample function and bounded arithmetic

texts:
Let $\{L^c_i\}_{i}$ be an efficient enumeration of languages in $DTime(2^{n^c})$,
e.g. clocked TMs.
Assume $EXP\not = NEXP$.
Let $L$ be an $NEXP$-complete language and therefore not in $EXP$.

There is a diagonal function $f$
such that for all $c$ and $i$:
$$f(i,c) \in L^c_i \leftrightarrow f(i,c) \not\in L$$

  Can such an $f$ be in $FPH$ or $FEXP$?

Also related to the above question,

  Is $S_2+EXP=NEXP$ consistant?


texts: Presenting work-in-progress (slides now available)

texts:
Presentation now given. Slides available below.

Presenting work-in-progress is something we all should do in order to obtain early feedback and to help crystallize our ideas. Unfortunately, many graduate students need help getting over this hurdle of presenting early research, even if it is only to their own research group. I will be giving a talk about presenting work-in-progress to our graduate students, and I'd like to get some input on what sort of advice I should give them to help them be more willing to share their work.

What tips can you offer on presenting work-in-progress?
How should the presented deal with the fact that the ideas are not entirely clear in his/her head?

I'm not so concerned about the work being stolen, as presentation will occur locally. I'd like to know how to get students to present such work and how they best can do it.

The students' work is generally of a formal nature, rather than describing systems, so I hope that this question is relevant here. If you feel that this is out of scope please do say so.

Resulting Presentation.

Here is the outcome. I am very grateful for your input, which you can see was useful.


texts: Relating classes of computational complexity to finding solution to classes of algebraic equations

texts: Having related classes of computational complexity to finding solution to classes of  algebraic equations, we may relate classes of computational complexity  to  algebraic geometry or complex geometry, is there any reference for the relationshi? like Schemes relating to classes of CC, or something else


texts: Reference for the shortcomings of Google's PageRank algorithm?

texts:
Sometimes, when using Google search, you don't immediately get quality results to your query. It is seems that PageRank algorithm gets distracted by widely used keywords that have different meanings and uses. Therefore, you need to spend extra time and possibly use different keywords to refine the search context.

  Is there a good reference that addresses the PageRank algorithm's shortcomings? Is there a contextual search algorithm?


texts:
Does it matter in the 3Sum problem if the numbers to be summed belong to the same set or to distinct sets?

Let's define

the problem "$k$-Sum" as follows: given a single finite set of integers $X\subset N$ of size $n$, decide if there exists $k$ integers $x_1,\ldots,x_k\in X$ such that their sum $\sum_{i=1}^k x_i$ is null; and
the problem "Separated $k$-Sum" as follows: given $k$ finite sets of integers $X_1,\ldots,X_k\subset N$ of respective sizes $n_1,\ldots,n_k\in[1..n]\subset N$, decide if there exist a vector $(x_1,\ldots,x_k)\in X_1\times\ldots\times X_k$ such that their sum $\sum_{i=1}^k x_i$ is null.

I was assuming that those two problems were equivalent, and I was using the second one as a pedagogical example for some parameterization technique (while there is an algorithm running in $O(n^2)$ for both, the second one can take advantage of variations in the size of the sets to solve the problem much faster, down to $O(n_1 n_3+\sum n_i\lg n_i)$ and $O(n_1 n_2 \lg \frac{n_3}{n_2}+\sum n_i\lg n_i)$).

But I realized today that I did not know how to prove this equivalence, and I might even start to think that they are not.


texts: Which randomized algorithms have exponentially small error probability?

texts:
Suppose that a randomized algorithm uses $r$ random bits. The lowest error probability one can expect (falling short of a deterministic algorithm with 0 error) is $2^{-\Omega(r)}$. Which randomized algorithms achieve such minimal error probability?

A couple of examples that come to mind are:

Sampling algorithms, e.g., where one wants to estimate the size of a
set for which one can check membership. If one samples uniformly at
random the elements to check, the Chernoff bound guarantees an
exponentially small error probability.
The Karger-Klein-Tarjan algorithm for computing minimum spanning tree. The algorithm picks each edge with probability 1/2, and recursively finds the MST in the sample. One can use Chernoff to argue that it's exponentially unlikely there'll be 2n+0.1m of the edges that are better than the tree (i.e., one would prefer to take them over one of the tree edges).

Can you think of other examples?

Following Andras' answer below: Indeed, every polynomial time algorithm can be converted to a slower polynomial time algorithm with exponentially small error probability. My focus is on algorithms that are as efficient as possible. In particular, for the two examples I gave there are deterministic polynomial time algorithms that solve the problems. The interest in the randomized algorithms is due to their efficiency.


texts: An extension to the student/college admissions Gale-Shapley algorithm

texts:
The Gale-Shapley algorithm is an established algorithm that finds an optimal one-to-one match between two groups, each individual of which has a preference for the individuals in the other group (the "stable marriage market problem"). The algorithm has been further extended for one-to-many matchings, often called the college admissions problem. In this example, applicants with preferences for certain colleges are optimally matched with colleges that have preferences over applicants and that also have a certain number of vacancies to fill that can be more than one.
Are there further extensions to this algorithm to optimally match many-to-many relationships?. For illustration, I would like to match projects to sources of funds, where a project might receive funding from multiple sources; and a source of funding may be able to fund more than one project. To use the college admissions analogy, this would be the same as specifying a student to attend one or more colleges whilst a college may accept one or more students.
A further extension of this concept would be to encode inclusivities (e.g., fund A must always be used with fund B), exclusivities (e.g., if project A is funded then project B must not be funded), but these added complexities first need the many-to-many algorithm described above.


texts: Best parameterized algorithm for maximum clique

texts:
I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "parameterized algorithm maximum clique" all failed.

What is the best known algorithm for maximum clique problem parameterized by the maximum degree. Or at least, how would you look for something like that?


texts: Using game-based proofs in simulation-based proofs

texts:
Simulation-based security provides more natural and more powerful definition of security than game-based security. I have seen the simulation based approaches use the game-based proofs in-part to prove security of some parts of the protocol. For example, to assess the security of a protocol for round complexity or total messages exchanged during execution of the protocol, a game-baed approach is taken, but the security of the protocol itself regarding the framework (in my study the UC framework) is proven by Ideal/Real paradigm (i.e., simulation based approach).

  Question: Under what circumstances can we use a game-based approach to prove security of a part of the protocol or the whole protocol when the protocol design must conform to a simulation approach? Can we use this approach at any point for any reason as long as it is not relevant to security of the whole protocol regarding the simulation-based framework?

Let me explain it through an example: I am studying a group key exchange protocol over UC framework (simulation-based), but the protocol uses encryption schemes which are CCA-Secure (proven by a game between adversary and some oracles) or CCA2-secure (proven by a game-based approach too), signatures must be existentially unforgeable (game-based approach too) and finally the communication cost of the protocol is calculated and analysis of the protocol security is done through 10 or 11 games between adversary and simulator. Finally proofs are made to show that the protocol conforms to UC regulations.


texts: Inductive types for large countable ordinal notations.

texts:
I'm looking to build notations for large countable ordinals in a "natural way".  By "natural way" I mean that given an inductive data type X, that equality should be the usual recursive equality (the same that deriving Eq in Haskell would produce) and the order should be the usual recursive lexicographical order (the same that deriving Ord in Haskell would produce), and there is a decidable predicate that determines if a member of X is a valid ordinal notation or not.

For example, ordinals less than ε0 can be represented by hereditarily finite sorted lists and satisfies these requirements. Define X to be μα. μβ. 1 + α×β, a.k.a. hereditarily finite lists.  Define isValid to check that X is sorted and all members of X are isValid.  The valid members of X are all ordinals less than ε0 under the usual lexicographical order.

I conjecture that μα0.… μαn. 1 + α0×…×αn can be used to define ordinals less than φn + 1(0), where φ is the Veblen function, in a similar way.

As you can see I run out of μ quantifiers at φω(0). Can I build larger ordinal notations satisfying my requirements?  I was hoping to get as far as Γ0.  Can I get larger ordinals if I drop my decidability requirement on my validity predicate?


texts: Differences between Quantum Computing and Parallelism

texts:
What are the differences between Quantum Computing and Parallelism?

thanks in advance


texts: Have fixed parameter integer program algorithms ever been implemented for research use?

texts: Have any fixed parameter integer programming algorithms described in  Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?


texts: Pairing algorithm for simple speed dating problem

texts:
I am asking myself whether there is an polynomial algorithm for the following problem:

Given:

- m persons (think of them as "men")
- w persons (think of them as "women")

- t-talking sessions
- a function
     f: (w, m) -> {-1,0,1,2}, which is preference of a specific woman to talk with a specific man: -1 means, that the woman does not want to talk to this man, if possible.
     g: (m, w) -> {-1,0,1,2}, which is preference of a specific man to talk with a specific woman: -1 means, that the man does not want to talk to this woman, if possible.

Target: Accomplish the "best" dating plan, meaning a pairing function for each talking session, which maximizes by summing over all dates using this function: m, w -> max(f(m,w),g(w,m)). During the talking sessions noone should date a person he has met before.

Is there a greedy algorithm for this problem, e.g. by matching the most loved-person with the most preferred person having the least number of talks?


texts: What logic correponds via Curry-Howard to a Monad?

texts:
According to Moggi's 1991 paper "Notions of computation and monads" one can represent monadic equational logic with the well known monad $(T, \eta, \mu)$ with T an functor and the two natural transformation
$\eta: Id \to T$ and $\mu: T^2 \to T$ that arise out of an adjunction.  Monadic Equational Logic limits one to a single formula on each side of the turnstile such as $x_1 : \tau_1 \vdash_{pl} e: \tau_2$.

In order to go beyond monadic equational logic to allow programs of the form
$x_1: \tau_1, \dots, x_n:\tau_n \vdash e: \tau$ one needs an extra strength natural transformation

$t_{A,B}: A \times TB \to T(A \times B)$

This allows one to take a context $\Gamma$ into account, represented by the $A$ in $t_{A,B}$ above.

This corresponds to the formula in modal logic

$A \land \diamond B \supset \diamond(A \land B)$

which is logically quite weird as it would allow one to have propositions $A$= "S can board the plane" and $B$="S cannot board the plane" and reason "S can board the plane and it could have been the S cannot board the plane" to "it is possible that S can board the plane and that S cannot board the plane".

Moggi writes in his conclusion:

  The semantics of computations corroborates the view that (constructive) proofs and programs are rather unrelated, although both of them can be understood in terms of functions. Indeed, monads (and comonads) used to model logical modalities, e.g. possibility and necessity in modal logic or why not and of course of linear logic, usually do not have a tensorial strength. In general, one should expect types suggested by logic to provide a more fine-grained type system without changing the nature of computations.

Have I understood this correctly? Is the Curry-Howard isomorphism for monads illogical?


texts: Explicit error bounds on the abelian hidden subgroup problem

texts:
What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries?

Ettinger, Hoyer, and Knill give a result that the success probability is $1-4r/2^{s/2}$, where $r$ is the number of subgroups of $G$ and $s$ is the query number.  However, this result seems to come from a specific set-up for the algorithm that departs from simply measuring a list of characters of $G$.  Does someone work out what the error probability in reconstructing the hidden subgroup would be just as a function of the number of characters measured?

Simplified cases where $G$ is cyclic or a product of $Z_2$ groups would also be of interest.


texts: Best algorithm for calculating lists of neighbours

texts:
Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted from nearest fo farthest.

Which is the fastest parallel algorithm for this purpose?

PS: I also crossposted this in math exchange and SO


texts: Graphs with precedence constraints on paths

texts:
Consider a directed graph where the edges are labelled with integer values.  In such a graph a path $a \rightarrow b \rightarrow c \rightarrow d$ is valid if the values of the labels of the edges followed strictly increase along the path.  I would like to be able to compute standard graph properties taking into account this extra restriction. Have such graphs been considered in the theory literature before?

EDIT: (This should be a comment but it is too long.) There is a simple reduction that follows by replacing each node $A$ by a bipartite graph with indegree($A$) incoming nodes and outdegree($A$) outgoing nodes. We can then connect the relevant incoming nodes to the outgoing nodes that respect the precedence constraints. This would increase the total number of edges by an additive term which is something like the sum of the square of the degrees of the nodes, where $n$ is the number of nodes in the original. Alternatively one can choose a more compact encoding where the nodes in the first half of the bipartite graph are connected in a line and so are the nodes in the second half and the nodes across from the first half to the second just point to the first node with a valid outgoing edge. This reduces the additive expansion factor to something like $n$ times the average degree of the nodes.

Unfortunately, neither reduction preserves crucial properties of the graph. As an example of the problem, if I want to find out if there is a simple path of length $k$ in the original graph, we can't simply look for simple paths in the transformed graphs. The reason is that a simple path in the transformed graph may correspond to a cycle in the original graph.  This means that any graph algorithm will have to be modified to take into account which nodes are in fact the same. In particular any algorithm that relies simply on a matrix representation of the graph (or its eigendecomposition) will not work any more.


texts: Subgraph of G whose maximum degree and minimum degree are of the same order

texts:
Consider a graph $G$ with max degree $\Delta_G$, min degree $\delta_G$ and average degree $d_G$.

Is it possible to obtain a subgraph of $G$, say $G'$, such that  $\Delta_{G'} = c_1d_{G}$, $\delta_{G'} = c_2d_{G}$ , where $c_1,c_2$ are constants

EDIT 1: Also the size of the resultant subgraph $G'$ must be constant times the size of original graph $G$.

My attempt :

Let $X$ be the random variable which denotes the degree of any randomly chosen vertex. Therefore, $d_G = E[X]$. Using markovs's inequality, we have

$$P(X > 3E[X]) < \frac{1}{3} $$
 and
$$P(X < \frac{E[X]}{3}) = P(\frac{1}{X} > \frac{3}{E[X]}) < \frac{E[\frac{1}{X}]*E[X]}{3} < \frac{1}{3}$$

Using union bound, we have

$$P(\frac{E[X]}{3} < X < 3E[X]) > 1/3$$.

Using the above equation, we can show that there exist $|V|/3$ vertices in $G$ whose degree is between $d_G/3$ and $3d_G$.

Does the graph obtained by the above $|V|/3$ vertices solve the problem? If not, can we modify the technique to obtain a solution?

Thanks in advance!


texts: How to find the set of edges for the directed graph associated with a partial order?

texts: I have a set $S$, and a partial order relation $\preceq$ defined on $S$. The way this partial order is given to me is through a function $f:S\times S \to \{true, false\}$,  where $f(a,b) = true$ if and only if $a\preceq b$. Given this setup, I can construct a directed graph $D = (S, E)$, where $E= \{(a,b) \in S\times S | f(a,b) = true\}$. I can find all the elements of $E$ in  time $|S|^2/2$ by examining all the possibilities. I am looking for an algorithm that can take advantage of the properties of partial order (in particular, transitivity), to reduce the expected time to find all the elements of $E$ to a linear order function of $|S|$.


texts: Do "outer-bounded-genus" graphs have constant treewidth?

texts:
Let $k\in\mathbb{N}$ and denote by $G_k$ the set of all graphs that can be embedded on a surface of genus $k$ such that all vertices are situated on the outer face. For instance, $G_0$ is the set of outerplanar graphs. Can the treewidth of graphs in $G_k$ be upper bounded by some function of $k$?

The other direction obviously does not hold, since constant treewidth does not even imply constant genus: Let $H_n$ be the union of $n$ disjoint copies of $K_{3,3}$. The treewidth of $H_n$ is constant, its genus however is $n$.


texts: Is Gödel's speed-up theorem an instance of Blum's speedup theorem?

texts:
Blum's speedup theorem is a statement about a certain class of computable functions for which it is always possible to find a faster algorithm.
Gödel's speed-up theorem is a statement about the possibility of drastically reducing the size of a theorem proof, by going to a more powerful axiomatic system.

Is Gödel's speed-up theorem an instance of Blum's speedup theorem, in which the computable function takes as input the axioms and outputs the theorem?
Such a function could concretely be built in theorem proving programming languages, say for instance with Coq.

Additional info:
I found this that looks related, but it doesn't clearly answer my question.


texts: PSPACE completeness, with different kinds of reductions

texts:
PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. This class is known as PSPACE-complete.

Similarly, we can define :

PSPACE-complete$_{FPSPACE}$ problems, the  PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial space reduction. This class is still PSPACE, minus trivial problems $\Sigma^*$ and $\emptyset$.

PSPACE-complete$_{FNP}$ problems, the  PSPACE problems such that every other PSPACE problem can be transformed to it with a FNP reduction (the function problem extension of the decision problem class NP).

PSPACE-complete$_{FPH}$ problems, the  PSPACE problems such that every other PSPACE problem can be transformed to it with a FPH reduction (the function problem extension of the decision problem class PH).

It seems to me that all these classes are well defined and that we have :

PSPACE-complete $\subset$ PSPACE-complete$_{FNP}$ $\subset$ PSPACE-complete$_{FPH}$ $\subset$ PSPACE

Additionally, if PSPACE-complete$_{FPH}$ $\neq$ PSPACE-complete then P $\neq$ NP.

Naturally, PSPACE-complete$_{FNP}$ $\neq$ PSPACE-complete works also but it's more difficult to prove.

What more can be found about the two last defined classes ?

(Initially asked on cs.stackexchange.com)


texts: Would a purely topological computational model be useful in decision problems in topology?

texts: If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the way that model would compute. Would such a model be useful in understanding computational problems in topology or would algebraic models suffice? If one already exists please provide a reference.


texts: Complexity of edge coloring graphs with $\Delta(G) \ge n/3$

texts:
Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices.

What is the complexity of edge coloring graphs in $C$?
Is there a reduction from SAT to edge coloring graphs in $C$?

Related to this question. A positive answer means a plausible graph theory conjecture implies $\sf NP=coNP$. A negative answer would greatly surprise me since all graphs of sufficiently large degree will be efficiently edge-colorable.

Possible approach is using some gadget like here

In addition this might help for counterexample for the conjecture (if false).


texts: Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

texts:
Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free monomials. (These $2^n$ monomials form a basis to the space of real functions on $\{-1,1\}^n$. The sum of the squares of the coefficients is simply $1$ so $f$ leads to a probability distribution on square free monomials. Let's call this distribution the F-distribution.

If f can be described by a bounded depth circuit of polynomial size then we know by a theorem of Linial, Mansour and Nisan that the F distribution is concentrated on monomials of $\text{polylog } n$ size up to almost-exponentially-small weight. This is derived from Hastad switching lemma. (A direct proof would be most desirable.)

What happens when we add mod 2 gates? One example to consider is the function $IP_{2n}$ on $2n$ variables which is described as the mod 2 inner product of the first n variables and the last n variables. Here the F-distribution is uniform.

  Question: Is the F-distribution of a Boolean function described by
  bounded depth polynomial size AND, OR,
  MOD$_2$ circuit concentrated (up to
  superpolynomially small error) on $o(n)$
  "levels"?

Remarks:

One possible path to a counterexample would be to "glue somehow" various IP$_2k$ on disjoint sets of variables but I don't see how to do it. Perhaps one should weaken the question and allow assigning some weights to the variables, but I don't see a clear way for doing it either. (So referring to these two matters is also part of what I am asking about.)
I would speculate that a positive answer to the question, (or to a successful variation) will apply also when you allow mod$_k$ gates. (So asking the question was motivated by Ryan Williams' recent impressive ACC result.)
For MAJORITY the F-distribution is large (1/poly) for every "level".

  As shown by Luca, the answer to the question I asked is "no". The question that is left is to propose ways to find properties of the F distributions of Boolean functions that can be described by AND OR and mod 2 gates not shared by MAJORITY.

An attempt to save the question by talking about MONOTONE functions:

  Question: Is the F-distribution of a MONOTONE Boolean function described by
  bounded depth polynomial size AND, OR,
  MOD$_2$ circuit concentrated (up to
  superpolynomially small error) on $o(n)$
  "levels"?

We may speculate that we can even replace $o(n)$ by $\text{polylog} (n)$ so a counterexample for this strong version can be interesting.


texts: Probability distributions and computational complexity

texts:
Some probability distributions are easier to work with than
others. Consider the following two problems.

Given a number $n$, return $i$ with $0 \leq i < n$ with uniform
probability, i.e. $\mathbb{P}(i = k) = \frac{1}{n}$ for all $0 \leq k
   < n$.
Given a number $n$, return $i$ such that $i$ is a (the Gödel
number of) a valid proof of length n in Peano arithmetic. Again $i$
should be chosen with uniform probability, i.e. if the number of such
proofs is $pr(n)$, then the probability to get any specific proof of
length $n$ should be $\frac{1}{pr(n)}$.

It seems inutitively clear that the latter problem is harder to solve
than the former, in a way that is reminiscent of computational
complexity.  If we had a program solving the first problem, and a
program for the second, what could we say about their time and space
consumption? Moreover, whatever the intrinsic complexity of the
distributions, there should be a connection with conventional
complexity theory, for the difficulty of the second problem is largely
a consequence of the fact that the set of valid proofs in Peano
arithmetic is a complicated subset of the set of all integers, and if
we had an oracle for it and / or the number of such proofs, we could
solve the second problem quite easily.

There is no reason to restrict one's attention to
uniform  or discrete distributions.

My question is this: where has the complexity of probability
distribution been investigated? What is a good overview article?

Please feel free to close or move this question if it's inappropriate for this forum. I asked
on cs.stackexchange but didn't get the kind of answers
I was looking for.


texts:
It is generally considered unlikely that quantum computers will be able to solve NP-complete problems efficiently. In the classical case one approach to tackle such problems is to use approximation algorithms. Has there been any research on approximation algorithms using quantum computing where quantumness gives significant speedup over classical approximation methods?

By "significant" I mean not necessarily exponential, but greater than for corresponding exact algorithms. In other words, I'm interested if relaxing the requirement that our algorithm yields the exact solution gives a significant advantage to quantum algorithms.


texts: Understanding a conference reviewer comment

texts:
I submitted my first paper to ICALP 2021 and just got the reviews back after receiving a rejection a couple of days ago. The reviews were overall positive with nearly all of the comments on presentation and typos.
Remarkably, two of the reviewers said -- "The ideas in this paper would make a nice chapter for a textbook". I have never seen this comment before and I am trying to understand if this is some sort of shade about the technical contribution or not. Does anyone have any input on what is this supposed to mean?


texts:
Consider $X = \sum_i \lambda_i Y_i^2$, where $\lambda_i$ > 0 and $Y_i$ is distributed as a standard normal. What kind of concentration bounds can one prove on $X$, as a function of the (fixed) coefficients $\lambda_i$?
If all the $\lambda_i$ are equal then this is a Chernoff bound. The only other result I am aware of is a lemma from a paper of Arora and Kannan ("Learning mixtures of arbitrary Gaussians", STOC'01, Lemma 13), which proves concentration of the form $\Pr[X < E[X] - t] < \exp(-t^2/(4 \sum_i \lambda_i^2)$, i.e., the bound depends on the sum of the squares of the coefficients.
The proof of their lemma is analogous to the usual proof of the Chernoff bound. Are there other "canonical" such bounds, or a general theory of which functions of the $\lambda_i$'s are such that their largeness ensures good exponential concentration (here, the function was simply the sum of the squares)? Maybe some general measure of entropy?
A more standard reference for the Arora-Kannan lemma would also be great, if it exists.


texts:
What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why?

Details:

http://en.wikipedia.org/wiki/Powerset_construction states that the worst-case runtime complexity is $\Theta(2^n)$, where $n$ is the number of states of the NFA.

I do not understand how $\Theta(2^n)$ is sufficient: You need up to $2^n$ steps to create the DFA, each creating a new state in the DFA. For each step, you need more time than $\Theta(1)$: you have to consider up to $n$ many states of the NFA (since the DFA-state is a set of up to $n$ states of the NFA) and for each such state up to $b$ (=maximal branching) many outgoing transitions. Thus I would have thought the worst-case time complexity would be $\Theta(2^n \times n \times b)$.

Is there some optimization possible to get to $\Theta(2^n)$? (Above, I have already used the optimization to look in each step at every state of the NFA at most once, instead of iterating through the set of NFA states and for each one doing an epsilon closure with worst case runtime complexity $O(n)$).


texts: My exact divide-conquer algorithm for counting antichain in a poset?

texts:
This post is a little lengthy, thank your for your patience for reading. ^_^

As known, counting antichains in a poset is #P-complete, so it is NP-hard to get the exact answer. Following is my simple divide-conquer algorithm for the antichain counting problem (#ANTICHAIN). I wonder if more helpful properties releavnt to my algorithm could be found? And whether the worst condition may happen?

We represent the poset as a DAG. Notice: We can assume that $G$'s underlying undirected graph is connected. Otherwise, we can calculate each connected component and just multiply the number of each component. Also, we assume that $G$ is transitive reduction of itself, i.e, $G$ is free of transitive edge.

Consider a vertex $u$ of $G$, let $R^+[u]=\{ v | u \leadsto v \}$ denote the set of vertices which are reachable from $u$, including $u$ itself. Similarly, let $R^-[u]=\{ v | v \leadsto u \}$.

When $u$ is selected as a member of an antichain, $R^+[u]$ is excluded from further selection, i.e., $G \leftarrow G-R^+[u]$. Just delete $R^+[u]$ and any edge which has an head (ending-point) in $R^+[u]$ from $G$.
When $u$ is not selected, $R^-[u]$ is excluded from further selection, i.e., $G \leftarrow G-R^-[u]$. Just delete $R^-[u]$ and any edge which has an tail (starting-point) in $R^-[u]$ from $G$.

Let $|R^+[u]|=a$ and $|R^-[u]|=b$, then the recurrence relation is at least as good as
$$T(n)=T(a)+T(n-a)+T(b)+T(n-b) \text.$$

Why at least? Because the underlying undirectd graph of $G-R^+[u]$ or $G-R^-[u]$ may be disconnected.

For a DAG, let ${\Delta^-}(G)$ and ${\Delta^+ }(G) $ represent the maximum indegree and outdegree of vertices of $G$.
If ${\Delta ^ - }(G) \le 1$ and ${\Delta ^ + }(G) \le 1$ , then #ANTICHAIN is in $\mathcal{O}(n)$. Otherwise, my algorithm satisfies the recursion

$$T(n)=T(n-1)+T(n-3) \text,$$

nearly $\mathcal{O}(1.45^n)$.
I wonder whether the recursion is tight? Does there exists a DAG when using my simple divide-conquer algorithm, the running time is $T(n)=T(n-1)+T(n-3)$?

This algorithm is really kind of stupid. Are there more elegant, effective algorithm exist already?  Has anyone thought about the possible FPRAS of it? Or has prove that #ANTICHAIN does not have a FPRAS?

Wow, closed. Sincerely thanks for your answer/comment in advance. ^_^