texts: Deciding the Most Significant Bit of Binary Multiplication

texts:
I am interested in determining the complexity of the following decision problem: Given two integers $l_1$ and $l_2$ (each with at most m bits), decide whether the most significant bit of the multiplication $l_1 \cdot l_2$ is 1 (where the result is printed in 2m bits with possibly leading 0's)?

Some background on the problem: Obviously, this problem is a special case of binary multiplication that asks whether the $i$-th bit of the multiplication $l_1 \cdot l_2$ is 1.  In their paper, Uniform constant-depth threshold circuits for division and iterated multiplication, Hesse, Allender and Barrington prove that iterated (and thus binary) multiplication is in $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$. Moreover, it seems to be well-known that binary multiplication is already $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard. However, I was not able to find a particular source proving this hardness result. As a non-expert in circuit complexity, I would also appreciate a pointer to this general hardness result. Finally, assuming that binary multiplication is $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard, my question can also be read as: Does it remain $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard if we want to decide only the most significant bit of binary multiplication?

UPDATE: Kaveh's answer clarifies why binary multiplication is $\mathsf{TC}^0$-hard (reduction from COUNT). The precise complexity of deciding the most significant bit of binary multiplication remains open (and the bounty is for this question).


texts: Oracle-Decidability of Algebraic Independence

texts:
Consider numbers $x_1,...,x_n\in \mathbb{R}$ given by TMs $M_1,...,M_n$ such that $M_i$ approximates $x_i$ to an arbitrary precision (by allowing it to run longer and longer).

I am interested in the following problem:

  Decide whether $x_1,...,x_n$ are algebraically independent.

Clearly this is undecidable, since even deciding whether $x_i=0$ is undecidable. However, if we are given an oracle to the problem of deciding whether $x_i=0$, then the above problem becomes recognizable: enumerate all polynomials with integer coefficients (e.g. in minlex order), and for each polynomial $p$ compute a TM $M_p$ that approximates $p(x_1,...,x_n)$ arbitrarily. Then, use the oracle to check if this number is $0$.

So the question is:

  Is the problem also decidable under a zero-test oracle? i.e. is it co-recognizable?

Remarks:

This question relates (but is not directly connected/reducible to) my question here.
I see that a lot of questions regarding real-numbers encounter issues with encoding. I think the encoding here is well defined (comment if I'm wrong, and I'll revise). Note that not all numbers are of course representable in this model.


texts: Extreme rays of the cone of submodular functions

texts:
Consider a ground set $U=\{1,2,...,n\}$ and the set $\mathcal{F}$ of all non-negative submodular functions $f: 2^U \mapsto \mathbb{R}_{\geq 0}$. The set $\mathcal{F}$ is closed under taking linear combinations of elements but with non-negative coefficients, and hence it forms a cone.
Question: does this cone have $O(2^{poly(n)})$ number of extreme rays?

In other words, does there exist a set $\mathcal{B} \subseteq \mathcal{F}$ of non-negative submodular functions over $U$ such that any non-negative submodular function $f$ over $U$ can be represented as $f = \sum_{b\in \mathcal{B}}  \gamma_b \cdot b$ for $\gamma_b \in \mathbb{R}_{\geq 0}$, and such that the size of $\mathcal{B}$ is exponential in $n$?
I don't need a characterization of set $\mathcal{B}$, just quantify its size.

I came across this paper https://www.jstor.org/stable/1997813?seq=21#page_scan_tab_contents which in Section 2.1 states that such a cone has just $O(2^n\cdot n^2)$ facets, because we can define such a cone as an intersection of $O(2^n\cdot n^2)$ halfspaces each defined for a different triple $(X ,x,y) \subseteq 2^U \cdot U \cdot U$ by $f(X+x)+f(X+y)-f(X + x + y) -f(X) \geq 0$. I have a hard time reading the paper, so can someone tell me if this argument is already answering my question?

I will greatly appreciate any help.

EDIT: Would it change a lot, if we would be considering only monotone submodular functions?


texts: Complexity of a specific class of definite integrals

texts:
INTRODUCTION: From the answer to this question I learned that deciding whether a definite integral is $0$ or not can be NP-complete, as the following integral representation of the Number Partition Problem shows.

Given $n$ numbers $(a_0,a_1,...,a_{n-1})$ in the range of $1$ to $M$, find whether the following integral is $0$ or not:
$$
\frac{1}{2\pi}\int_{-\pi}^{\pi} \prod_{k=1}^{n-1} (e^{ia_k \theta} + e^{-ia_k \theta}) d\theta.
$$

To see the reduction, notice that the only terms that survive the integration would be the ones where the exponent sum up to $0$ and this happens exactly when there is a bipartition of $(a_0,a_1,...,a_{n-1})$ where elements of the two parts sum up to the same number. The integral is therefore different from $0$ iff such partition exists; this implies that computing a definite integral is at least as hard as Partition, which is known to be NP-complete.

QUESTION: Assuming our machine is able to handle reals, I am now interested in proving (or disproving) the NP-hardness of the following problem

Let $p(x)$ be a polynomial on $\mathbb{R}$ of degree $n$. Decide whether the following integral is $0$ or not:
$$
\int_0^1 \cos(p(x)) dx.
$$

More in general, what are the techniques one usually uses in order to do reduction for the problem of finding whether a definite integral is $0$ or not on a specific class of functions?

NOTE: This question was also posted on Mathematics Stack Exchange but I guess that attempt was too optimistic.


texts: Strongly NP-complete variants of subset sum or partition problem

texts:
Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA problem is NP-complete.

Also, Factoring decision problem has sub-exponential time algorithm and it is not believed to be NP-complete. Meanwhile, a variant of factoring problem is NP-complete.

Subset-sum and partition problems are weakly NP-complete problems since they have pseudo-polynomial time algorithms. I am interested in their variants that are strongly NP-complete.

  Are there known variants of subset-sum or partition problem that are strongly NP-complete?

P.S. I am not interested in 3-partition problem.


texts: Abduction in a Herbrand Constraint System

texts:
I have a simple constraint system with a finite set $C$ of constant symbols, an infinite set $V$ of variables, and two relation symbols - $R_1$, a preorder, and $R_2$, an equivalence relation. Furthermore, $R_1$ and $R_2$ are related in the following way:

$\forall x,y. R_1(x,y) \wedge R_1(y,x) \Rightarrow R_2(x,y)$

The language of constraints ($\phi$) is as following:

$x,y \in C \cup V$
$\phi \in R_1(x,y) ~|~ R_2(x,y) ~|~ \phi \wedge \phi ~|~ true $

I need to perform abduction in this constraint system. Specifically, for any given mutually consistent pair of constraints $\phi_{cx}$ and $\phi_{cs}$, I need to find a maximally weak (in an intuitive sense) constraint $\varphi$ such that

$\phi_{cx} \wedge \varphi \Rightarrow \phi_{cs}$.

I have following questions:

Is my constraint system a Herbrand constraint system?
Are the results on Simple Constraint Abduction problem described in [M. Maher, Herbrand Constraint Abduction, LICS'05] applicable to my case?


texts: How to apply Statistical Query Algorithm for class of decision list

texts: There were some people discussing how to apply SQ algorithm on learning monotone conjunction, but I wonder if anyone knows how to apply SQ algorithm on decision list?


texts: sophistication or logical depth to detect intelligent extra-terrestrial species

texts:
From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can be used to characterize strings that are complex not because of some trivial randomness, but rather because they are generated by complex programs (plus some possible additional randomness but the non-random part is important).
I’m wondering if it would be possible to use those concepts to detect an intelligent species in space, and if so, has it been done? (For instance in initiatives like Breakthrough Listen [3]?)
I’m aware some researchers like Laurance R. Doyle are applying information theory to detect, for instance, Zipf’s law patterns in signals (which humans as well as animals like dolphins are shown to exhibit when communicating) [2], but I’m wondering if there were areas of research looking at the AIT side. For example, we would look at a radio signal (but also possibly a Hubble image, etc...) and compute (an approximation of) its sophistication or logical depth: if it is high then there are a lot of chances that an intelligent specie was involved in its generation process.
But first of all, as a sanity check, on human data vs natural data, would it work? Is there any experiment about this? For instance, is an image of a rock or a cloud less sophisticated than say an image of a motorcycle?
Or is there something more that is needed to make it work?
I’m not familiar yet with the theory of sophistication and logical depth because they are quite hard for me to grasp, (although I'm eager to learn), but I was curious about a general high-level idea of what could be possible.
PS: apologies if my question is not precise enough, I'll refine it as needed, but I think as of now it gathers all of the important parts of the question
[1] Relativity of Depth and Sophistication https://arxiv.org/pdf/2002.06709.pdf
[2] http://cosmos.nautil.us/feature/54/listening-for-extraterrestrial-blah-blah
[3] https://en.wikipedia.org/wiki/Breakthrough_Listen


texts: Automata : Language Containment, Minimality & Graph Homomorphism

texts:
Given two DFAs $A$ and $B$ defined on the same alphabet, a (graph) homomorphism $h:A \rightarrow B$ from $A$ to $B$ is a mapping of the states of $A$ into the states of $B$ such that :

if the state $x$ is initial (resp. final) in $A$ then $h(x)$ is initial (resp. final) in $B$
if there is a $\lambda$-transition from the state $x$ to the state $y$ in $A$ then it is also the case from $h(x)$ to $h(y)$ in $B$

Let $A$ and $B$ be two DFAs and $L_A$ and $L_B$ their respective languages,
if there exists a (graph) homomorphism from $A$ to $B$ then $L_A \subseteq L_B$. But the converse does not necessarily hold.

My question : What are the requirements on $A$ and $B$ to get the equivalence between (graph) homomorphism and language containment ? And if the equivalence is possible, what are the properties of such (graph) homomorphism ?

I conjecture that we get the equivalence with the minimality of both automata : if $A$ and $B$ are minimal then there exists a (graph) homomorphism from $A$ to $B$ iff $L_A \subseteq L_B$.

I also suspect this (graph) homomorphism $h:A \rightarrow B$ to be unique. Indeed, because of the determinism, any path in $A$ can be found only once in $B$.

I found very few informations (papers, lecture notes, books, tutorials) about this relationship between (graph) homomorphism and language containment and I would really appreciate any references or any answers regarding this problem.

Thank you very much, Luz :-)


texts: What are some examples of sequential-decision tasks?

texts:
I ask this because I'm currently learning about Neural Networks as a subset of the machine learning algorithms

Just trying to get some intuition on what sort of problems out there are categorized as "sequential" while others "non-sequential"

Thanks :)


texts: Dynamic Data structure for All nearest smaller values

texts:
I need a data structure that stores a sequence of numbers and supports the following operations.  The input to each operation includes the position of an item in the current sequence (not the value or the memory address of that item).

$\mathtt{NearestSmaller}(i)$: Return the value of the last item in the sequence that occurs before position $i$ and whose value is less than the value at position $i$.
$\mathtt{InsertBefore}(x, i)$: Insert a new item with value $x$ into the sequence just before the item with position $i$.
$\mathtt{Delete}(i)$: Delete item at position $i$ from the sequence.

In short, my question is whether there is a dynamic version of the all nearest smaller neighbors algorithm.

For example, if the current sequence is $X = [9,7,3,1,8,12,10,20,15,5]$, then

$\mathtt{NearestSmaller}(6)$ should return $8 = X[5]$, and
$\mathtt{NearestSmaller}(10)$ should return $1 = X[4]$.


texts:
Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here.

Let's equip a normal Turing machine with a "black box oracle" that contains a boolean circuit of unknown size, and call this Turing machine a "black box machine". The black box oracle pretty much works the same way as an ordinary oracle machine, whose input and output (which are just the input/output of the circuit) are both polynomially bounded by the input size of our black box machine. As in the usual oracle machine's case, the evaluation of the black box circuit takes $O(1)$ time.

Now we define the boolean black box (BBB) problem:

(BBB) Given a circuit $C$ which size is polynomially bounded by $n$ and a black box $B$ which input and output are both polynomially bounded by $n$, determine whether $C$ will always behave identically as $B$ (in other words, for any possible input, whether $C$ and $B$ always produce the same result).

And the corresponding function problem:

(BBB-F) Given a black box $B$ which input and output are both polynomially bounded by $n$, compute a circuit $C$ that always behaves identically as $B$.

It seems to me that BBB is unlikely to be in $P$, or even $NP$, because generally one needs to check all $2^n$ possible input/output pairs, which would take more than polynomial time. However, what happens if we restrict the size of the black-box circuit to be polynomially bounded by $n$? (Notice that this does change something: if we restrict the size to be some constant $c$, then the problem can be solved in linear time. But what happens when the bound is polynomial?) Of course, we would also like to know if BBB-F will fall into $FP/FNP$ with this restriction.

A variant of this problem is that we only require the machine to be correct with a probability that is significantly higher than $1/2$. In other words, does $BBB \in PP$?

Third question: $PSPACE$. Can this possibly be solved in polynomial space?

Also, I can see some vague connections between this problem and some craptographic problems. For instance, I would guess that a CCA2-secure cryptosystem exists if and only if BBB-F is not in FP. To see the left-to-right part, simply put the decrypting procedure along with the secret key into a black box. An attacker with access to this black box has essentially the power to perform CCA2 attack. Now if BBB-F is indeed in FP, then we can construct a valid circuit $C$ within polynomial time that behaves the same as the black box circuit, which is the decryptor, and that would break the security of the system.
As for the other way around, I don't have a good idea yet.

I googled quite a bit but couldn't find useful info about work done along this direction, so I would really appreciate it if someone can point me to some relevant literature. Any further thoughts on this problem would also be much appreciated. Thanks for your time!


texts: How to start studying topics Hardness of approximation and PCP's

texts: Recently I have done an introductory course on complexity theory ( which covered 90% of sipser text book). Now I would like to study the topics Hardness of approximation and PCP's. Can you please suggest me the best available sources (lecture notes or video lectures) to study these topics from the basics.


texts: Places where the order of points along a simple polygon passing through them is useful

texts:
We know that finding the convex hull of $n$ points on a plane has a lower bound of $\Omega(n\log n)$ on its running time. However, if the points are given in the order in which they occur along some simple polygon that has those points as its vertices, then their convex hull can be found in linear time.

I find this intriguing because there are probably too many simple polygons that have the given points as their vertices and therefore, intuitively, the order along one of them sounds like a very useless piece of information. And yet, it helps.

So my question is, are there other places where the same information helps in bringing down the running time of an algorithm?

As a side, I also want to know bounds on the number of permutations of a given set of points on a plane for which there is a simple polygon with those points as its vertices so that the order in which the points occur along the polygon is the same as the order in the permutation. What's known about this?


texts: Is higher-order unification decidable for terms without abstractions within applications?

texts:
Consider the problem of higher order unification - that is, finding a substitution for the equation a = b, where a and b are open terms on the lambda calculus, such that a and b have the same alpha-beta normal form. That problem is undecidable in general. Now, consider the case where:

b is a closed term on the shape (λ t . (t Y0 Y1 Y2 ...)).
a is on the shape (λ t . (t (F X0) (F X1) (F X2) ... )), where F is the only variable.
Xn and Yn have no lambdas within applications.

For example, a valid instance of this problem is:

a = (λ t .
    (F (λ a b c d . (a (c d) (a (c (c d)) (a (c (c (c d))) b)))))
    (F (λ a b c d . (a (c (c d)) (a (c d) (a (c (c (c (c d)))) b)))))
    (F (λ a b c d . (a (c (c d)) (a (c (c d)) b)))))

b = (λ t .
    (λ a b . (a (a (a (a (a (a b)))))))
    (λ a b . (a (a (a (a (a (a (a b))))))))
    (λ a b . (a (a (a (a b))))))

The solution is the substitution:

F = (λ l f . (l (λ h t e . (h (t e))) (λ n . n) (λ p e . (f (p e))) (λ z . z)))

Is this problem decidable?


texts: Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

texts:
In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time
$$O(n \sqrt{\log n}),
$$
and linear space. The paper seems reasonable, though I am not an expert in sorting algorithms.

If correct, this would be a significant, I believe, at least theoretically.

The presentation of the main argument is somewhat informal and nontraditional, however.

Has anyone noticed/commented on this paper? It seems that the same author, Yijie Han, has published a related result on integer sorting, as discussed in Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm


texts: Intuition on context free and other kinds of a forests? Data structures perspective

texts:
I am trying to gain intuition on formal forests, also called tree languages, i.e., sets of trees.
There are regular tree languages, and there are context free tree languages. They both come in a deterministic and non-deterministic variants. The definitions are clear, but I am in search of examples that are less technical and more intuitive. Consider data structures:
Is the language of all AVL trees context free? Replace AVL by leftist, red-black, some other useful data structure, e.g., binomial heap with appropriate adjustment for unbounded rank)
Replace "context free tree language" by some other class of tree languages.


texts: Forbidden minors for bounded treewidth graphs

texts:
This question is similar to one of my previous questions. It is known that $K_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$.

  Is there a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs and grid graphs) that are minimal forbidden minors for graphs of every treewidth. In other words, is there an explicit graph $G_r$ on $r$ vertices (which is not a complete graph) such that $G_r$ is a forbidden minor for graphs of treewidth at most $r$, where $r$ is a function of $t$ ?

The complete sets of forbidden minors are known for graphs of treewidth at most three. See this Wikipedia article for more details.

  Is the complete set of forbidden minors of graphs of treewidth at most four known ?


texts: What's the relationship between "free theorems" and "free objects"

texts: What's the relationship between free theorems and free objects from algebra. They seem quite similar. I'm wondering if there's an underlying principle here.


texts: Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

texts:
Is anyone familiar with Yijie Han's $O(n \log\log n)$, linear space, integer sorting algorithm?  This result appears in a fairly short paper (Deterministic sorting in $O(n \log\log n)$ time and linear space. J. Alg. 50:96–105, 2004) which basically glues together a lot of earlier results, with suitable adaptations.  My problem is that it's written in a rather hand-wavingly manner without going very deep into any specifics.  It relies heavily on previous papers, prominent among them  another paper by Han (Improved fast integer sorting in linear space. Information and Computation 170(1):81–94) written in much the same style.  I am having significant difficulties in understanding these two papers, particularly the way in which they adapt and use previous results.  I would appreciate any help.

This is of course too broad and vague to be considered a proper question, but I am hoping to develop a discussion across several focused well defined questions and answers.

To lead off, here is my first specific question.  In Lemma 2 of the Info. Comp. paper there is a recursive $O(n/k \log k)$ time algorithm for finding the mth smallest integer in a set of $n$ small integers packed $k$ each into RAM words.  The description of the algorithm fails to mention how the base case $k=O(n)$ is handled.  In this case it is required to do the selection in $O(\log k)$ time.  How can this be done?


texts:
Fix $n\in\mathbb{N}$. Consider a rooted binary tree $T$ in which every non-leaf node contains either AND-gate or OR-gate. Let me say that $T$ is an universal formula if for every $f\colon\{0,1\}^n\to\{0, 1\}$ we can assign literals to the leafs of $T$ in such a way that the resulting formula computes $f$.

  What is the minimal size of universal formula?

There is an obvious lower bound $\Omega\left(\frac{2^n}{\log(n)}\right)$ as a tree of size $L$ can compute at most $(2n)^L = 2^{L \cdot \log_2(2n)}$ different Boolean functions. On the other hand, as far as I can see, there is an upper bound $O(2^n)$. Namely, one can take $(n+2)$-bit communication protocol for the universal relation from [1] and transform it into an universal formula via Karchmer-Wigderson correspondence [2].

One more related work is [3], where a different notion of universality is considered. Instead of fixing gates we fix literals and we want that for any $f$ it is possible to assign gates to non-leaf nodes in such a way that the resulting formula computes $f$. There is an obvious lower bound $\Omega(2^n)$ (as there are now 2 choices for every node) and [3] constructs a matching $O(2^n)$ upper bound.

In [1] it is also stated that their protocol improves and simplifies the result of [3]. I don't see why. An explanation would be greatly appreciated.

References

[1] G. Tardos, U. Zwick. The communication complexity of universal relation. Proc. 12th Computational Complexity Conference, pp. 247-259 (1997).

[2] M. Karchmer, A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2), pp. 255-265 (1990).

[3] W.F. McColl, M.S. Paterson. The depth of all Boolean functions. SIAM Journal on Computing, 6(2), pp. 373-380 (1977).

Update

Some clarifications: actually in [3] all possible bivariate gates are allowed, not only AND, OR gates. Then it becomes clear why [1] implies [3]. Moreover, it seems that [1] gives a stronger object. Namely, one can get from it a DeMorgan formula $F$ of size $O(2^n)$ such that for any $f\colon\{0, 1\}^n \to \{0, 1\}$ we can change in some leafs of $F$ the corresonding literals to opposite ones so that the resulting $F^\prime$ computes $f$.


texts: Tableau method for two-variable first-order logic

texts:
$FO^2$, i.e. two-variable first-order logic, has a NEXPTIME-complete satisfiability problem (see Grädel, Kolaitis and Vardi '97). However, the decidability and complexity of this fragment is proved by that paper in an indirect way, as far as I can tell.
What I need instead is an effective way to solve $FO^2$ satisfiability. What are the actual algorithms and methods available for this logic?
In particular, I would need a tableau-based method for $FO^2$ satisfiability. Is there any resource describing such a thing? Has it ever been developed?


texts: How can theoretical modelling be converted into viable product?

texts:
Many a times modelling is just for the sake of modelling like exploring some properties of materials which does not help in converting the theoretical modelling into a viable product that can serve humanity.

How one can become expert enough or which areas one should focus to model such problems and materials which can eventually result in some useful product.

Like we have solar cells but every other day we see a research article being published just by tweaking the parameters which does not result in better or greater product.

I want to see modelling and theory becoming useful sooner than we normally see.


texts: Uniqueness of the distribution maximizing the channel capacity

texts:
Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$.

To simplify notation, let the input symbols be labelled as $[1,2, ..., N]$ where $N = |\mathcal{X}|$ and the output symbols be labelled as $[1,2, ..., M]$ where $M = |\mathcal{Y}|$. The input probability vector of size $1\times N$ is denoted by $p$ and the output probability vector of size $1\times M$ is denoted by $q$. The stochastic matrix $Q$ of size $N\times M$ is the channel matrix i.e. $q = Qp$. The capacity of this channel is given by

$$C = \max_{p}\sum_{i=1}^N\sum_{j=1}^M p_iQ_{ij}\log\frac{Q_{ij}}{q_j}$$

Let the distribution that achieves $C$ be $p^*$.

Conjecture: If $p^*$ does not use the entire input alphabet in $X$ i.e. $p^*_i = 0$ for some component $i$, then it is guaranteed that there exists another distribution $\tilde{p}^* \neq p^*$ which also achieves the capacity of the channel.

Can anyone help prove this or show a counterexample?


texts: concurrent non-malleable *statistical* zero knowledge

texts:
According to Huijia Lin and
Rafael Pass's "Concurrent Non-Malleable Zero Knowledge with
Adaptive Inputs" paper:

  if collision-resistant hash functions exist, then
  "there exists a $\omega\left(\log^2(k)\right)$-round concurrent non-malleable zero-knowledge proof with adaptive input selection (and a with a black-box simulator) for all of NP",

where the "adaptive input selection" is in the strongest strongest sense that I know of.

As far as I can tell, their assumptions can be reduced to 2-round
statistically hiding commitment with publicly verifiable opening.
However, after searching online,
I do not see any results for concurrent non-malleable statistical zero knowledge.

  Is there any known construction for
  concurrent non-malleable statistical zero-knowledge arguments of knowledge
  (in the plain model)?


texts: Bounds on the construction of regular expressions' intersection operator

texts:
There are references on the exponential worst-case of the intersection operator for regular expressions (see [1]). However, I was wondering if there are similar results for the construction process itself?
Concretely, given two regular expressions $E_1$ and $E_2$ whose intersection can be represented by a regular expression of polynomial size, is the construction process itself bounded by exponential time or memory in the worst-case?
[1] Succinctness of the Complement and Intersection of Regular Expressions


texts: Can a fixed point combinator find the fixed point of a function that has no fixed point?

texts: A fixed point combinator is supposed to find the fixed point of any function. Yet I am wondering what if a function happens to have no fixed point, such as the add1 function over $\mathbb{Z}$, mapping -1 to 0, 0 to 1, etc. Does the fixed point combinator make sense any more?


texts: Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation

texts:
What is the complexity of deciding whether an $\mathsf{NC}^0$ circuit
with $n$ input bits and $n$ output bits computes  a permutation
of $\{0,1\}^n$? in the other words, whether every bit strings in
$\{0,1\}^n$ is an output of the circuit for some input?
It looks like a problem which has been studied,
but I cannot find any references.


texts: Fast algorithm to distribute points evenly in a 2D grid

texts:
In an NxN grid, I want to select M points ($1 \leq M \leq N^2$) so that they are distributed as evenly as possible, spread out everywhere, edge to edge. Can you suggest a fast algorithm for distributing points evenly over a grid?
I won't yet try to formally define "evenly", because it's not an exact requirement. Low runtime is the most important factor here, so algorithms like "do a random distribution and refine until it satisfies a criteria" are bad, I prefer doing it in a simple nested loop.

Examples
Let me illustrate with some examples.
When M is a square number, the solution is simple, let's say N=5 and M=9:
trivial
#.#.#
.....
#.#.#
.....
#.#.#

It can also work in some special cases when M can be written as a sum of squares, and there's no interference between the squares, for example N=5 and M=13=9+4:
two square patterns
#.#.#
.X.X.
#.#.#
.X.X.
#.#.#

But this wouldn't exactly work for M=10, because after you select 9 points in a square pattern, there's no good place to put the 10th one.
My first shot at this was an image dithering algorithm. It looked pretty good when M was big enough, but with small M's, the error distribution makes it biased towards the edges. For example with N=3 and M=1, dithering yields a bad result when a good result is pretty obvious:
bad  good
...  ...
...  .#.
..#  ...

Let me show another example of a bad and good distribution with N=5 and M=5:
bad    good   bad    good
#....  #...#  .....  .#...
.#...  .....  .#.#.  ....#
..#..  ..#..  ..#..  ..#..
...#.  .....  .#.#.  #....
....#  #...#  .....  ...#.

I'll tell you an idea for a formal definition of "evenly". But as I said, it doesn't have to be exactly like that, it's more of an intuitive thing. So how about this: let's take every 2x2, 3x3, ... N-1xN-1 subsquare and count the point density in each of them. The deviation of those numbers should be as small as possible. Let's see for N=4 and M=4:
one   two
#.#.  #..#
....  ....
#.#.  ....
....  #..#

One:

2x2 sums: 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4
3x3 sums: 4/9, 2/9, 2/9, 1/9
stddev: 0.06991

Two:

2x2 sums: 1/4, 0, 1/4, 0, 0, 0, 1/4, 0, 1/4
3x3 sums: 1/9, 1/9, 1/9, 1/9
stddev: 0.10758

(Even though number two has a higher deviation, it is spread edge to edge, so I prefer it a little, but number one works as well. Dealing with the edges is a not-so important edge-case.)


texts:
Let $F_1$ be a satisfiable CNF Formula with $n$ variables and $m$ clauses. Let $S_{F_1}$ be the solution space of $F_1$.

Consider the problem of determining, given $F_1$, another CNF Formula $F_2$ with the same set of variables as $F_1$, with $S_{F_2} = S_{F_1}$ (same solution space as $F_1$), but with as few clauses as possible (the only aim is to minimize the number of clauses, so how many literals each clause may have is not relevant).

  Question

  Did anyone already investigated this problem? Are there any results in the literature concerning it?

As an example, consider the following CNF Formula $F_1$ (each row is a clause):

$x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_2 \lor x_4$
$\lnot x_1 \lor x_2 \lor \lnot x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2 \lor \lnot x_5$

and the following formula $F_2$:

$x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

both have the same solution space, but while $F_1$ has $6$ clauses, $F_2$ only has $4$.

Finally, consider the following formula $F_3$:

$x_2 \lor x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

The solution space is again the same, but with only $3$ clauses.


texts: Formula in common: How to search for same/similar equations in other knowledge domains?

texts:
In a recent presentation by Sedgewick, he recounts in 1977 Flajolet noticed that they had a formula in common, both in different domains (see slide 4 in http://www.cs.princeton.edu/~rs/talks/AofA2AC.pdf )

I saw the same thing in an article on tantalizing links between matrix eigenvalues distributions, nuclear physics and Riemann's zeta zeros http://web.williams.edu/go/math/sjmiller/public_html/RH/Hayes_spectrum_riemannium.pdf

My question is: Say I have derived a formula/equation - how would I go about searching for an occurrence of the formula in other domains? Can I make Wolfram Alpha do that?

Thanks for any pointers

Daniel Bilar


texts: Generating points uniformly distributed over the SURFACE of a standard simplex

texts:
I would like to generate points that are uniformly distributed over the SURFACE of a standard $k$-simplex ($k$ dimensions, $k+1$ vertices).

One way to efficiently generate points that are uniformly distributed over the ENTIRETY of the $k$-simplex is to generate samples of $k$ iid exponential random variables, $E_i$, $i\in \left[1,k\right]$, then normalize, and $\vec{X}=\frac{\left\langle E_1,E_2,\dots,E_k\right\rangle}{\sum_{i=1}^k E_i}$, will be uniformly distributed over the entire $k$-simplex.

My problem is that the probability that one of these points lands on the surface (i.e. at a vertex, or along a hyper-edge, or on hyper-face, etc.) is nearly $0$, so that in practice all of the points end up being in the INTERIOR of the $k$-simplex.

In an attempt to sample the SURFACE of the $k$-simplex I have considered each hyper-edge, hyper-face, etc. separately and generated uniformly distributed samples on each (since they are themselves lower dimensional simplices). However, the problem becomes computationally unfeasible as $k$ increases because the number of hyper-edges, hyper-faces, etc. blows up.

Does anyone know of a method to explicitly generate samples that are uniformly distributed over the SURFACE (or BOUNDARY) of a standard $k$-simplex?


texts: Minimum Parity Weight Path - what is the complexity?

texts:
Consider an undirected graph, with non-negative  weights on the edges, and two distinguished  nodes $s\neq t$. If $P$ is a simple $s-t$ path in this graph, let $W_1(P)$ denote the sum of the weights on the path, but only adding up every other one, as we traverse the path from $s$ to $t$, starting the summation with the first edge. That is, we add up the first, third, fifth etc. weights on the path. Let us call it the parity weight of the path.

What is the complexity of finding the minimum parity weight $s-t$ path?


texts:
I have a question about counting problems on arbitrary (not necessarily polynomial time) functions.

Let $F_n = \{f : \{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions with $n$ inputs (again, not necessarily polynomial time).

Consider the operator $\#: F_n \to \mathbb{N}$ that maps $f \in F_n$ to $\#f = |\{x \in \{0,1\}^n : f(x) = 0\}|$

Consider a computational model where evaluating $f$ on an input $x$ can be done in time O(1). Clearly, the operator #f can be computed in time $O(2^n)$ by a brute force algorithm that evaluates $f$  on all inputs, and counts which of these inputs are zeros of $f$.

My question is, is there an exponential lower bound on the running time of #f?


texts: How can I use my computational theory and analysis powers for the greater good?

texts:
Outside of academia, what are the uses of my 'powers'? What can I do other than teaching and publishing papers? Where all can I apply my powers?

For the sake of argument: Please assume I have a PhD in algorithms/TCS and have learnt a great deal of 'stuff' and made have come up with breakthrough bounds on existing algorithms etc., And I also have a strong footing in algorithmic analysis, approximation/randomized algorithms, mathematical programming etc.,

Rationale behind question: Curious about non-academic career options for folks in this area and to possibly motivate some students that it's "just not theory" and there are potential uses in the outside world in essence.

PS: Please don't answer stating there is a lot to learn and you may want to try topic XXX. I am curious from a career/professional development point of view. Operations Research (OR) seems to be the only good fit, IMO. What other options exist?


texts: Membership testing in transformation monoids

texts:
"Given a finite set $A$, a set of functions $S=\left\{f_{1}, f_{2}, \ldots, f_{k}\right\}$, each $A \to A$, and a candidate function $g:A \to A$, is $g$ in the monoid generated by $S$ with respect to composition?"

Kozen's paper "Lower bounds for natural proof systems" shows that this problem is PSPACE-complete. The following question is about his argument that the problem is in PSPACE.

He argues that it is easy to compute function composition if we represent the functions as bipartite graphs. Now we just guess a sequence of $f_{i}$s, compose them, and check whether it equals $g$. Thus, it can be done in nondeterministic linear space, and by Savitch's theorem, the problem is in PSPACE.

But is this really sufficient to see that the problem is in nondeterministic linear space? The representation of $g$ using terms from $S$ might itself be exponentially long. The paper concedes this just before definition 3.2.2, and is an otherwise interesting little fact about permutations (which are a special case of the system being considered) -- the order of a permutation over $n$ elements may be exponentially large in $n$ (See this).


texts: Do many-one reductions and Turing reductions define the same class NPC

texts:
I wonder if NPC classes defined by many-one reductions and Turing reductions are equal.

Edit:
Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class $C$ such as there exists a problem not in $C \cup co-C$ under Karp reduction and which is in $C$ under Turing reduction ?


texts: Longest geometrically increasing subsequence

texts:
Given a sorted array of $n$ positive integers, the problem is to find the longest subsequence so that the progression of differences between consecutive elements of the subsequence is geometrically increasing.

Is there any complexity theoretic reason to believe this simple looking problem cannot be solved in $O(n^2)$ time?

added How fast can this problem be solved? Dynamic programming seems to give $O(n^3)$ time.


texts: How should one simulate self-avoiding random walks?

texts:
There is a trivial method for simulating a random walk through a graph by exponentiating a stochastic adjacency matrix, but the problem becomes harder if you ask that the random walk be self-avoiding.  In other words, the process must traverse the graph using paths, like an infection or something.

If the edge probabilities are large, there is a simple Monte Carlo algorithm :  In each trial, you simply delete each edge $e$ with probability $1-p_e$, compute the new graph's connected components, and increment a counting matrix by matrices of 1s for each contacted component.  You divide by the number of trials at the end.

Does anyone know any algorithm for doing this computation when the probabilities are quite small?

If the graph isn't too highly connected, you can find some minimum cut sets, and do inclusion-exclusion counting on them, but such an approach is doubly exponential in the size of the cut sets.  There are various optimizations for specific cases of high connectivity too, like treating all the clique subgraphs separately via the obvious computation.  Any more general ideas?


texts: Membership problem for certain class of unrestricted grammars

texts:
Consider an arbitrary context-free grammar $G$ over the alphabet $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$. To the productions of this grammar,  add two fixed non-context-free productions $P$: $\overline{0} 0 \rightarrow  \epsilon$  and $\overline{1} 1 \rightarrow  \epsilon$. Call the resulting grammar $G^P$ standing for "$G$ augmented with the productions $P$".

Is it possible to give an algorithm which takes a grammar $G^P$ and a  string $s$ over $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$ and decides whether $s \in \mathcal{L}(G^ P)$?


texts: NP-completeness of a problem using a "T-gadget"

texts:
Working on a problem I came up with the following "T-gadget":

It has 3 connectors (A, B, C); each connector has two wires (A1,A2; B1,B2; C1,C2);
it can be rotated (0, 90, 180, 270 degrees);
two gadgets X and Y, can be linked together (one connector of X is joined with one connector of Y);
the wires used to link the T-gadgets cannot overlap.

A signal is propagated on the wires; and it can use 1 or 2 connectors to traverse a T-gadget. Suppose that it enters through wire A1, then it can:

go back through wire A2, OR
choose among connector B or C - suppose that it chooses connector B; then it can exit the gadget through wire B1, re-enter through B2 and exit again through A2

When a signal enters a gadget and exits from the same connector, the gadget is "activated".

Possible traversals of a T-gadget:
(OUT) - A1 - A2 (OUT)
(OUT) - A1 - B1 - (OUT) - B2 - A2 - (OUT)
(OUT) - A1 - C1 - (OUT) - C2 - A2 - (OUT)
(OUT) - B1 - B2 (OUT)
(OUT) - B1 - A1 - (OUT) - A2 - B2 - (OUT)
(OUT) - B1 - C1 - (OUT) - C2 - B2 - (OUT)
(OUT) - C1 - C2 (OUT)
(OUT) - C1 - B1 - (OUT) - B2 - C2 - (OUT)
(OUT) - C1 - A1 - (OUT) - A2 - C2 - (OUT)

The signal starts on wire A1 of a gadget (with connector A unlinked) and must return to A2.

Question: is the problem: "Given a set of T-gadgets linked together, does exist a path that activates all of them?" $NP$-complete?

If we omit option 1 (go back through wire A2) I think that the problem is $NP$-complete (through reduction from Hamiltonian path problem on cubic planar graphs).


texts:
The wise other editors at Wikipedia have declined my request to move the Wikipedia article on the Rabin–Karp algorithm to what I think it should be called, the Karp–Rabin algorithm, on the basis that the Rabin–Karp name is used more often (false, if one goes by Google scholar's numbers), or that it sounds better out loud (really?). The original publication name order was Karp and Rabin, alphabetically as it usually is for theory papers, which is why I requested the move.

One major proponent of the Rabin–Karp name ordering is the Cormen–Leiserson–Rivest–Stein Introduction to Algorithms textbook. The Wikipedia outcome is unlikely to change barring significant new evidence one way or another, and it seems unlikely that either Rabin or Karp cares about $\epsilon$ more credit, but now I'm curious: Do any readers remember the history of this and have any explanation why CLRS (or anyone else) chose the Rabin–Karp name order?


texts: Resolution vs Nondeterministic Search Problems

texts:
It is well known that each resolution refutation $\Pi$ for an unsatisfiable CNF formula $F = C_1\wedge C_2 \wedge ... \wedge C_m$ over variables $X$ can  be translated in polynomial time (in the size of $\Pi$) into a deterministic branching program $P$ solving the following search problem:

1) $P$ has one source node and one sink node for each clause $C_i$.

2) For each assingment $\alpha:X\rightarrow  \{0,1\}$ there is a consistent path in $P$ from the
source node to some sink node associated with a clause that is falsified  by $\alpha$.

Question:
Is there a proof system strictly stronger than resolution where each proof $\Pi$ can be translated in polynomial time (in the size of $\Pi$) into a not necessarily deterministic branching program $P$ solving the search problem above?


texts: Power of Hyperedge Replacement Grammars (HRGs)

texts:
Can HRGs generate languages which equal or include the following graph languages:

All (bipartite) graphs of bounded degree
All (bipartite) planar graphs of bounded degree
All (bipartite) planar graphs in a square grid (so that every vertex has 4 neighbors)
A good language of expander graphs

The HRGs can potentially generate additional graphs outside of those languages or generate predictable additional vertices and edges that can be removed through post-processing. It would also be of interest whether node replacement (C-edNCE specifically) languages can generate these languages.


texts: Is there some research about infinitely many-armed bandit with non-stationary assumption? I have found the paper about infinitely many-armed bandit under stationary (or stochastic) assumption. And I also found the solution for non-stationary multi-armed bandit problem, like discounted UCB. Are there some attempts to this mixed problems?


texts:
Is there anything known about the problem of incremental emptiness testing for a pushdown automata?

Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the transition table up front, you are given transition edges one at a time and asked whether their insertion would cause the PDA to accept a nonempty language. Also suppose that each transition can either push a single symbol, pop a single symbol, or leave the stack unchanged, and that the PDA has a designated start and end state, and is defined to accept a word if it results in reaching the end state with an empty stack.

So far, the best algorithm I've been able to come up with is $O(n^3)$, based on reducing this to the incremental directed reachability problem, and then applying the classic $O(n^3)$ algorithm. The basic idea is to maintain a directed graph with a vertex for each PDA state, with the invariant that b is reachable from a in that graph if and only if you can go from a to b in the PDA starting and ending with an empty stack. The $n^3$ reachability algorithm maintains a bit matrix (well actually a table of pointers) for the reachability of each node pair, and hence can determine when b becomes reachable from a for the first time. Whenever the source of a pop edge becomes reachable from the sink of a corresponding push edge, insert an edge into the directed graph from the source of the push edge to the sink of the pop edge (the push and pop edges themselves are obviously not included in the directed graph).

Note that incremental reachability can be done in $O(nm)$ time, where $m$ is the number of edges. In the case of the PDA, I specified a linear number of edges $n$ in the input. However, the extra edges added to level the stack transitions can result in up to $m = O(n^2)$ edges in the directed graph, and thus overall $O(n^3)$ time.

I've spent quite a bit of time thinking about this problem, but I haven't been able to improve on the $O(n^3)$ algorithm at all and am beginning to suspect that it is impossible. Does anyone know of any way to improve this or show that it can't be done?


texts: Graphs-like data structure with weighted vertices

texts:
I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges.
Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of vertices $V$ and edges $E$ and a weights function $w: E \to \mathbb{R}$.

Now, I want to define a new data structure say a weighted-vertex graph as a tuple $(V,E,w(\cdot))$ of vertices $V$, edges $E$ and a weights function $w: V \to \mathbb{R}$

This seems related to graph coloring. Indeed, if we restrict to integer weights, then we can define vertex-colored graphs exactly this way.
My questions are as follows:

Is the formulation of weighted-vertex graph somehow equivalent to the standard formulation of an undirected weighted-(edge)-graph? (The answer to this is most likely no)
What are some problems/algorithms studied for weighted-vertex-graphs? As mentioned before, graph coloring is one major class of problems if we restrict to integer weights. Are there any other problems with integer weights or can every problem be formulated as a coloring problem? What about for real weights?

For example, one possible problem comes to mind. (I don't know if this has been studied)

Suppose $G_0 = (V,E,w_0)$ and $G_1 = (V,E, w_1)$ are weighted-vertex-graph that share the same vertices and edges (but different weights). An "action" for a vertex $v$ consists of distributing $w(v)$ equally to its neighbors and then setting $w(v) = 0$. Graphs $G_0$ and $G_1$ are called vertex-weight-isomorphic if you can convert from $G_0$ to $G_1$ using a finite sequence of actions. Find an algorithm that outputs whether two graphs are vertex-weight-isomorphic.

I haven't given this specific problem much thought so it's possible it can be converted to a problem in standard graphs but it seems like these types of problems might be interesting.


texts: NPI-candidate hereditary graph property?

texts:
A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover,  a number of nontrivial general facts are also known about hereditary classes of graphs, see "Global properties of hereditary classes?"

Considering complexity, hereditary graph properties include both polynomial-time decidable and NP-complete ones. We know, however, that there are  a number of natural problems in NP that are candidates for NP-intermediate status, see a nice collection in Problems Between P and NPC. Among the numerous answers there, however, none of them looks like a hereditary graph property (unless I overlooked something).

  Question: Do you know a hereditary graph property that is a candidate for NP-intermediate status? Or else, is there a dichotomy theorem for hereditary graph properties?


texts: Formal notion for energy complexity of computational problems

texts:
Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms. Also, Are there established energy-complexity classes for computational problems?

References are appreciated.


texts: How many induced subgraphs does $G$ have of specific size

texts:
Let $G$ be a connected graph with $n$ vertices and $O(nk)$ edges, ($k$ is parameter).
Then how many connected induced subgraphs of size $l$  does $G$ have?

The simple case when $l=2$, The number of subgraphs is number of edges which is $O(nk)$. How can we generalize this one.


texts: Hessian of non differentiable convex function

texts:
The motivation of the question is the following:
Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\infty)$.

$f(c) = \sum_{p\in P}\Vert p-c\Vert^2$.

It is well known that the mean $\mu(P)=\frac{1}{n}\sum_{p\in P}p$ minimizes the function over $\mathbb{R}^d$. More generally, for any $c\in \mathbb{R}^d$ the following is true

$f(c) = f(\mu(P)) + n\Vert c-\mu(P)\Vert^2$.

There are various ways to prove this. For example we can compute the gradient

$\nabla f(c) = \sum_{p\in P}2(c-p)$

Since $f$ is convex, for $c^\star = \mu(P)$, we have $\nabla f(c^\star) = 0$. The Hessian is $\nabla^2 f(c)=2nI$, $I$ being the Identity matrix. Now consider the second order approximation

$f(c) = f(c^\star) + \langle \nabla f(c^\star), c-c^\star\rangle + \frac{1}{2}(c-c^\star)^T\nabla^2f(\theta)(c-c^\star) = f(c^\star) + n\Vert c-c^\star\Vert^2$, for some $\theta\in [c,c^\star]$.

Coming to the main question
Let $\mathcal{P} = \left\{P_1,\cdots,P_n \right\}$ be a family of $n$ finite sets in $\mathbb{R}^d$. Consider the following (convex) function

$F(c) = \sum_{j\in[n]}\max_{p\in P_j}\Vert p-c\Vert^2$

Given $c\in\mathbb{R}^d$, let $p_j\in P_j$ such that $\Vert p_j-c\Vert^2=\max_{p\in P_j}\Vert p-c\Vert^2$. Then one can show that $G(c) = \sum_{j\in[n]}2(c-p_j)$ is a valid "sub gradient" of $F$ at $c$ ($\in \partial F(c)$). It is well known that $c^\star$ minimizes $F$ iff $0\in \partial F(c^\star)$. Therefore, $c^\star = \frac{1}{n} \sum_{j\in[n]} p_j$ is a minimizer of $F$. Now I want find out how changing the point effects the function(similar to the above). For that one needs an analogue of Hessian for non differentiable functions, where the "sub gradient" exists.
So is there a way to compute something similar to the Hessian, when the function is non-differentiable?
PS. After Googling, I found the paper GENERALIZED HESSIAN PROPERTIES
OF REGULARIZED NONSMOOTH FUNCTIONS, it may be of importance.
UPDATE: 29/01/2020
It seems to me that $c^\star = \frac{1}{n} \sum_{j\in[n]} p_j$ may not be a minimizer of $F$, because $G(c)$ may not be zero for any $c\in \mathbb{R}^d$ (there may not be any point which is the "mean" of the points farthest in the sets). This is interesting.


texts: Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?

texts:
It has been claimed that if $P = NP$, then every problem in $P$ (equivalently $NP$) is NP-complete.

As a blanket statement, I find this wrong because, well, there's the trivial problem or constant time problems, but more interestingly, I expect that there are classes that are very small that are provably not NP-complete but aren't entirely trivial. This is in analogy to the fact that it is known that $P != EXP$, there must be a $C \subsetneq NP$, presumably $C= NTIME(\log(n))$. But I have never heard discussed such a small class.

The smallest well-known class I can think of is $AC^0$, but I don't know whether it is known that it is not $NPC$. And there's Ryan's recent result that $NEXP \not\subset ACC^0$, which leads me to believe that it would have to be a much smaller class than $AC^0$ that would be known to be disctinct from $NP$.

I think the first statement might be considered to be true if all one has are deterministic polytime reductions (which would imply that -all- problems in $P$ are $P$-complete), but that seems to be too simplistic. A particular proof might use a particular reduction, but the distinctness of complexity classes is not parameterized by those reductions (or is it?).

So, thoughts/suggestions? Should I just accept the first statement since $NPC$ is defined with respect to deterministic polytime reductions? And even so, is there a well-known non-trivial class that is provably a proper subset of $NP$?


texts: Is the knapsack variant with small profit and unlimited repetition of items NP-hard?

texts:
Consider the unbounded Knapsack problem where we are given $n$ items of integral weights $w_i$, integral profits $p_i$, and a max weight $W$. The goal is to maximize the total profit $\sum_i x_ip_i$ subject to the total weight $\sum_i w_i x_i$ being at most $W$.  Here (in the unbounded variant) each item $i$ can be taken any number of times, so each $x_i$ can take any value in $\mathbb N_0$.
In general, this problem is NP-hard, but I am wondering about the restriction to instances with small profits --- where every item profit $p_i$ is $O(n)$.  With this restriction, is the unbounded Knapsack problem NP-hard, or is there a poly-time algorithm for it?
For comparison, consider the standard Knapsack problem, where each item can be taken at most once, so each $x_i$ is either 0 or 1.  This version is NP-hard by reduction from Subset Sum. (That reduction creates profits that are the same as the weights, and both are exponential.)  But for instances where each item profit is $O(n)$, the maximum achievable profit $P$ is $O(n^2)$, and there is a standard dynamic-programming algorithm that runs in time polynomial in $n$ and $P$, so the run-time in the case of small profits is polynomial in $n$. In contrast, for the unbounded problem, even with small profits, the maximum achievable profit is not in general polynomial in $n$, so the same approach does not yield a polynomial-time algorithm.


texts:
Most of us are familiar with — or at least have heard of — the Shannon entropy of a random variable, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$, and all the related information-theoretic measures such as relative entropy, mutual information, and so on. There are a few other measures of entropy that are commonly used in theoretical computer science and information theory, such as the min-entropy of a random variable.

I've started seeing these so-called Renyi entropies more often as I browse the literature. They generalize the Shannon entropy and the min-entropy, and in fact provide a whole spectrum of entropic measures of a random variable.
I work mostly in the area of quantum information, where the quantum version of Renyi entropy is also considered quite often.

What I don't really understand is why they are useful. I've heard that oftentimes they're easier to work with analytically than say Shannon/von Neumann entropy or min-entropy. But they also can be related back to Shannon entropy/min-entropy, as well.

Can anyone provide examples (classical or quantum) of when using Renyi entropies is "the right thing to do"? What I'm looking for is some "mental hook" or "template" for knowing when I might want to use Renyi entropies.

Thanks!


texts: Dynamic programming algorithm to find a colorful subset of disjoint sets

texts:
Suppose there is a set $F=\{X_1 ,...,X_m\}$, such that $\forall 1\leq
  i\leq m: |X_i|=3.$ Suppose we color the elements of $\bigcup F$ in
$3k$ colors. We wish to know if there is a subset $F'\subseteq F$ such
that all sets in $F'$ are pairwise disjoint, and $F'$ is colorful,
i.e. $\bigcup F'$ uses all $3k$ colors.

I'm trying to come up with a parameterized fixed tractable dynamic programming algorithm for the task, but I had a couple of issues.
First I thought of defining $M[C,i]$ to be $true$ iff there is a solution subset of $F$ with respect to $C$ and $i$, that is, it only uses $\{X_1,...,X_i\}$ and all the colors in $C$.
But when trying to define the recursive relation, if we set $I=\{j < i: X_j \cap X_i = \emptyset  \} $, then $M[C,i]= M[C\setminus col(X_i), I]\vee M[C,i-1]$ which doesn't make much sense since $i$ is a number and $I$ is a set, but still I cannot allow selection of a colorful set using $\{X_1 ,... , X_{i-1}\}$ since it might not be disjoint of $X_i$ even though it is pairwise disjoint within itself.
Any ideas on a better definition or a fix for this definition?
(Using subsets of $1,...m$ is not an option since that would mean $\Omega(2^m)$ entries which is not FPT)


texts:
This could be a downvoted question but I am asking because I am not able to get usable info via Google.

Are there any interesting combinatorial problems in the field of electronics circuits design? I am interested in solved problems and not in the high science.

I am asking this because we are looking for a diploma themas on Electrical Engineering faculty. We will try to guide and help our students (I am a part of staff) to solve these problems using a BDD package in a similar way as BDDs are used to solve 8-Queens problem and other combinatorial problems found in Knuth's book and various research papers.

We have Quine-McCluskey minimization, but are there also some more hardware-related problems?


texts: Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics?

texts:
This guy asserts:

  I’ll say it — the computer was invented in order to help to clarify … a philosophical question about the foundations of mathematics.
  (This problem being Entscheidungsproblem - The Decision Problem)

The reference here states that the Church-Turing thesis was attempting to answer this question.

My question is - is it true that modern computers are a byproduct of trying to solve 'The Decision Problem'?

(My intuition told me that modern computers were more a byproduct of trying to break Nazi encryption codes). (perhaps with some pre-war German influence).


texts: Is perfect matching for bipartite graph with no cycles unique?

texts:
Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.

My question is if the balanced bipartite graph is also acyclic then is the perfect matching unique?

If so (I am almost certain it is), can you point me to a cite-able source? I was not able to such a document.


texts: Non-objected oriented type theories that can express the $\nu Obj$ calculus

texts:
Odersky et al.'s $\nu Obj$ calculus [1] adds just enough dependent typeness on top of object oriented programming to express interfaces that define types (and consequently module systems and other fanciness).  Although still undecidable, it seems to have proven itself practical as the base of a language without the need for interactive theorem proving.

I am curious about non-objected oriented type systems which are (1) at least as expressive as $\nu Obj$, in the sense that $\nu Obj$ can be embedded within them and (2) not "too much" more expressive (left intentionally vague), and therefore hopefully more tractable from a type inference / checking perspective.

For example, a sufficiently powerful non-objected system should be able to type the vtable concept, and then express "objects" as tuples the first element of which is a vtable.  Unfortunately, the obvious way to do this requires existential types, which I (perhaps naively) think of as more complicated than $\nu Obj$.  So, I suppose my question splits into three parts:

Are existential types on top of basic Hindley-Milner sufficient to express $\nu Obj$?
Am I correct that existentials are harder to deal with than $\nu Obj$ ("too much more expessive")?
Is there something weaker than existentials that still captures $\nu Obj$, without an object oriented focus?

[1] Odersky et al. 2003, A nominal theory of objects with dependent types.


texts: Can the distribution over the squared moduli of the 'probabilities' defined by an RBM with complex weights be written as an RBM with real weights?

texts:
I posted this question originally on the math boards, but figured it would be better suited here.

https://math.stackexchange.com/questions/2203967/can-the-distribution-over-the-squared-moduli-of-the-probabilities-defined-by-a


texts: The structure of pathological instances for simplex algorithms

texts:
As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum. Let us call these instances 'pathological' since usually (i.e. on most inputs) the simplex algorithm terminates quickly. I remember from my mathematical programming course that the standard examples of pathological instances for specific rules were highly structured. My general question is if this is an artifact of the specific examples, or a feature of pathological instances in general?

Results like smoothed analysis and the polynomial time algorithm extending it rely on perturbing the input --- suggesting that the pathological examples are very special. Hence the intuition that the pathological instances are highly-structured does not seem that far fetched.

Does anybody have any specific insights on this? Or some references to existing work? I have been specifically vague about what I mean by 'structured' to try to be as encompassing as possible, but suggestions on how to better pin down 'structured' would also be useful. Any advice or references are greatly appreciated!


texts: Is sliding blocks linear space complete?

texts:
Sliding blocks is PSPACE complete even in its simplest form involving 1x2 and 2x1 blocks (without rotation or fractional positions) in a rectangular area, with goal being to move a designated block to the designated space.  See "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation" by Robert Hearn and Erik Demaine. However, that paper does not give a more precise characterization than PSPACE.

Is existence of a solution in sliding blocks (deterministic) linear space complete?

One choice of completeness is to use polynomial time linear space reductions with at most linear increase in instance size, but gadget based reductions also work in LOGSPACE and might even work in uniform linear size AC$^0$.

Offered using Q/A format.


texts: Small universal monotone Turing machines

texts:
This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) simulators of Turing machines?

  Monotone machines are Turing machines with a one-way read-only input tape, some work tapes, and a one-way write-only output tape. The input tape contains a one-way infinite sequence of 0's and 1's and initially the input head scans the leftmost bit. The output tape is written one symbol at a time, and the output is defined as the finite binary sequence on the output tape if the machine halts, and the possibly infinite sequence appearing on the output tape in a never-ending process if the machine does not halt at all.

From page 276 of An introduction to Kolmogorov complexity and its applications by Li and Vitanyi.


texts: Is it possible to find a non-cut vertex in O(|V|) time?

texts:
Let $G = (V, E)$ be an undirected connected graph, which is represented by an adjacency list. A vertex is called a cut vertex if removing this vertex with its incident edges from $G$ makes the graph disconnected. Finding a cut-vertex can be done in linear time.

My question is as follows: is it possible to find a non-cut vertex in $O(|V|)$ time?

My idea is to find a spanning tree of $G$, since all leaves of the spanning tree are non-cut vertices. However, I cannot find a spanning tree in $O(|V|)$ time.

Although I can find a cycle in $O(V)$ time, finding a non-cut vertex in a cycle seems not obvious to me.

I am wondering whether this problem has been solved, and I would appreciate any pointers provided by anyone.


texts: Is there a fine grained relation between LH and AC0?

texts: The wikipedia article states that the Logarithmic time hierarchy (LH) is equal to FO-uniform AC0. But since the natural way to think about LH is in terms of its levels (with DLogTime at the zeroth level, NLogTime and coNLogTime at the first level, and the log-time machines with (k-1)-alternations at the k-th level), it is natural to wonder whether there is a fine grained relation between the classes from the individual levels like (coNLogTime) with specific subclasses of AC0.


texts:
In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions.  Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as linear combinations thereof.

My question is: what, really, is the difference between two hash functions and one with twice the entropy?

This comes from looking at what you actually do with the output of your hash functions: you're going to take your (say) 64-bit hash value and scale it to the size of your bit vector, which is probably significantly smaller than 264.  This is clearly an entropy-losing transformation (except in the rare case your hash size and filter capacity exactly coincide).  Assuming my filter has less than 232 entries, what's to stop me from splitting my 64-bit hash value into two 32-bit hashes and taking linear combinations of those?  Or using it to seed a PRNG?

In other words, how much information do I actually need to know about each element I insert into a Bloom filter to ensure the standard false positive rate holds?  Or more generally, what is the relationship between how well I can distinguish elements (how many bits I use to describe them) and how my Bloom filter performs?

It sure seems like I can get away with $2\lg(m)$ bits for a filter size of $m$, or equivalently $2(\lg(-n\ln{p}) - 2\lg(\ln2))$ bits to store $n$ elements with false positive probability $p$....


texts: Papers every complexity theorist should read

texts:
I am starting my PhD this autumn and I am planning to work in complexity theory for my thesis.

I am compiling a list of important papers that every complexity theorist should know.

What papers would you suggest to a person like me? And please briefly explain why you think the paper is important.


texts: Is the Mendler-encoding in System-F adequate?

texts:
In the paper "Efficiency of Lambda-Encodings in Total Type Theory" it is mentioned that the Church-encoding is adequate and the Parigot encoding is not adequate. This means that any inhabitant of an encoded datatype actually represents an element of the datatype.
My question is if the Mendler-style encoding is adequate. I think I found a counter example (in System F):
-- Mendler-style encoding
Alg f t = forall r. (r -> t) -> f r -> t
Fix f = forall t. Alg f t -> t

-- Natural numbers
NatF r = forall t. t -> (r -> t) -> t
Nat = Fix Nat

-- the valid constructors for natural numbers
Z : Nat = /\t. \alg. alg [Nat] (\y. y [t] alg) (/\t. \z s. z)
S : Nat -> Nat = \n. /\t. \alg. alg [Nat] (\y. y [t] alg) (/\t. \z s. s n)

-- An inhabitant of Nat that is not a valid natural number
wrong : Nat =
  /\t. \alg.
    alg [forall t. t -> t]
    (\x. alg [t] (\y. y) (/\t. \z s. z))
    (/\t. \z s. s (/\t. \x. x))


texts: Impartial Combinatorial Games as a core of the final undergraduate project

texts:
Solving several problems of Impartial Combinatorial Games in Game Theory has drawn my attention. So that, I'd like to ask if it's possible to use this topic (e.g. Sprague Grundy theorem) as a core or the main idea of my final year project in computer science.

P.S. I will do this project individually, and I may make any decision depending on your advice and suggestions.

Edit: Any additional information needed?


texts: Monomial decomposition as product of smaller monomials

texts:
Is there an algorithm to get all possible decompositions of a monomial as the product of smaller monomials ?

For example $x^2y^3$ is $x∗xy^3$, $x^2∗y^3$, $xy∗xy^2$, and so on.

For a monomial in one inderminate, I know I can use an integer partitions of the monomial degree.

But this does not apply when there are at least two indeterminates.

(Sorry for misuse of vocabulary and may be uncomplete tags : I am french).

Note : this is a step in construction of an invariant polynomial as described in DOI : 10.1016/j.ijsolstr.2005.05.021.


texts: Minimum path edge-cover or minimum flow with unit capacities and DAGs

texts:
I have a directed acyclic graph (DAG) such that there can only be at most one edge between any two nodes (ie, only one (i,j) can exist between i and j). I need to find the the smallest set of paths from sources si to sinks ti that cover all the edges (ie, any edge is in at least one path).

The problem should be equivalent to a minimum flow problem, after having introduced a virtual source and a virtual sink and having set l(i,j)=1 for i,j not in {s,t} and l(s,si) = l(ti,t)=0 and c(i,j)=infinite.

There is some literature about that (eg, http://basilo.kaist.ac.kr/mathnet/kms_tex/981523.pdf). However, I'd like to know if there is an algorithm that works better in the specific case. The best I can think of is the blocking flow method (see the paper above), which should be O(|V|*|E|) in my case.

Thanks in advance for any help!

Marco


texts: NP-hardness of a Set Cover specialization

texts:
Is the following problem NP-hard?

Given a set of $N$ real numbers (targets) $x_1,\dotsc,x_N$ and a "trident" defined by two distances $a$, $b$ from the center of the trident, what is the minimum number $K$ of positions $p_1,\dotsc,p_K$ of the trident to cover all targets, i.e.
$$ \bigcup_{k=1}^K \{p_k-a,p_k,p_k+b\} \supseteq \{x_1,\dotsc,x_N\}.$$

Obviously, this is a special case of the set cover problem: Considering all sets $\{p_k-a,p_k,p_k+b\}$, with $p_k\in\{x_n+t\mid n\in\{1,\dotsc,N\}, t\in\{a,0,-b\}\}$ representing all "relevant" potential positions, we look for the minimum number of sets covering the universe $\{x_1,\dotsc,x_N\}$. Equivalently, we can represent the problem as a bipartite graph of position and target nodes and consider the hitting set problem.

Note that the problem is not NP-hard if the trident loses one of its "jags": Then each target can be covered from 2 positions and each position covers at most 2 targets, so the corresponding bipartite graph of potential positions and targets is a union of paths. In each path it is easy to determine a minimal hitting set (namely, the inner position nodes).

But is the trident case NP-hard?


texts: Transitivity check vs. Transitive Closure

texts: Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to determine if a digraph is transitive or not?


texts: Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

texts:
A walk in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. Note that a trial may visit a vertex multiple times as long as no edge is revisited.

Given a directed graph $G=(V,E)$ where the weight of each edge may be negative. Let $s,t \in V$ be our source and destination vertices, respectively. We are asked to find the shortest $s-t$ trail in $G$.

This problem seems harder than the elementary shortest path problem. But I failed to reduce it to this problem. I've also tried to do reductions from Hamiltonian cycle or feedback arc set, however I failed again. Could you please shed some light upon it?


texts: Does a decision oracle imply an algorithm for $\mathbb{NP}$ - hard problems with several parameters?

texts:
If we consider the decision version of the classical graph coloring problem, then we have some graph $G$ and some integer $k$ and we want to color $G$ with at most $k$ colors. It is well known that, given an oracle which tells us True or False for a tuple $(G,k)$, we can find the minimal $\hat{k}$ for which $G$ is $\hat{k}$ colorable using something like binary search in polynomial time.
Assume now that we consider an (abstract) slightly different problem, where we do not just have one parameter $k$, but rather two parameters $k_1$ and $k_2$ (these could be for example a bound on the number of colors and a bound of the number of different colors contained in some induced subgraph or something along these lines). Now consider some objective like $\min \{k_1,k_2\}$ or $k_1+k_2$ or something similar.
Note that we only use coloring as an example here, the question is more concerned with the general case of $\mathbb{NP}$ hard problems with several parameters.
Given an oracle for $(G,k_1,k_2)$ is it possible to solve this extended problem in polynomial time? Or is there some constraint on the objective function which has to be fulfilled in order to guarantee existance? Or what about the more general case where there are parameters $k_1,...,k_n$, with $n$ depending on the input size?


texts: Can Quarter-Subset Membership be decided space-efficiently?

texts:
Consider the following decision problem.
Let $q = \sum_{i=0}^{n/4} \binom{n}{i}$ and let $(C_0^n, C_1^n,\dots,C_{q-1}^n)$ be a suitable enumeration of those subsets of $\{0,1,\dots,n-1\}$ that have at most $n/4$ elements.

  Quarter-Subset Membership
  Input: tuple of non-negative integers $(i,j,n)$ represented in binary
  Question: is $i \in C_j^n$?

By picking a "nice" enumeration $(C_i^n)$, can Quarter-Subset Membership be decided by a deterministic Turing machine using no more than $(0.99)n$ bits of workspace, for all large enough $n$?

Discussion

Let $\log x = \log_2 x$.
It is easy to enumerate all subsets of at most $k$ elements chosen out of $n$ by keeping track of $k$ indices of size $\lceil \log n \rceil$ bits each.
(See also the discussion in Knuth's TAOCP section 7.2.1.3.)
When $k$ is constant this is just $O(\log n)$ bits.
However, if we let $k = cn$ for some constant $c \le 1/4$, then such enumeration schemes use $\Omega(n\log n)$ space.
One can also use an $n$-bit characteristic vector together with a check for the number of bits set.
I'm interested in schemes that beat $n$ bits.

A closely related question is then:

  For positive $c$ satisfying the inequality $c\log(e(1+c)/c) < 1$, is there a code representing subsets of at most $cn$ elements chosen from $n$ that uses $dn$ bits for some constant $d < 1$, and can be decoded efficiently?

Note that for large enough $n$,
$$\sum_{i=0}^k\binom{n}{i} \le \left(\binom{n}{k}\right) = \binom{n+k-1}{k},$$
and since
$$\log\binom{n+k-1}{k} \le \log[(e(n+k-1)/k)^k],$$
when $k = cn$ then information-theoretically it follows that $d \le c\log(e(1+c)/c)$ would be achieved with a perfect code.
(This is less than $1$ if $0 < c \le 0.2728$.)
I am therefore looking for a reasonably clean code that can be manipulated without using lots of space.

To obtain a perfect code, one could pick some enumeration of the subsets, run an index through the enumeration in increasing order, and then obtain each combination by decoding the index.
However, decoding such a code when $k \ge \Omega(n/\log n)$ seems to require using at least $n$ bits of space for the enumerations I have looked at, such as via characteristic vectors ordered by increasing Hamming weight and then lexicographically, or via Gray codes.

There might be a way to do this with $o(n)$ space, but I think $(1-\varepsilon)n$ is more likely to be feasible.
Note that since $\log \binom{n}{cn} \ge cn\log(1/c)$, the information-theoretic lower bound is already $\Omega(n)$ bits, so this really is about whether $(1-\varepsilon)n$ can be achieved for some $\varepsilon > 0$.
A code that is nice enough (but not necessarily perfect) would seem to be enough to answer my question in the affirmative.
It might also be the case that Quarter-Subset Membership can be decided efficiently without explicitly constructing a code.
On the other hand, such an enumeration may not exist: for instance, every sequence of enumerations for values of $n$ might be inherently non-uniform, or it might be the case that any $(1-\varepsilon)n$-bit bound must be breached infinitely often.


texts: Minimum relevant variables in linear system - additive approximation

texts:
In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.:

$$ A x = b $$

and the goal is to find a solution $x$ with as few nonzero variables as possible.

The problem is known to be NP-hard and hard to approximate to within a constant multiplicative factor (see the wikipedia page for details).

My question is: is anything known about additive approximations? In particular: what is the complexity of finding a solution that has at most $\text{OPT}+d$ nonzero variables, where $\text{OPT}$ is the smallest number of nonzero variables in a solution, and $d$ is some constant?


texts: mixed vs behavior strategies for zero-sum game with infinite extensive form

texts:
This is a crosspost of this post on math.stackexchange, which didn't get any responses.

For two-player games given in extensive ("game tree") form, there are several natural ways to define randomized strategies for the players.  A mixed strategy is a probability distribution over pure strategies.  A behavior strategy specifies, for each node in the game tree at which the player must play, a probability distribution on the possible moves.

Kuhn's theorem gives conditions under which these two notions are "equivalent".  Equivalence here means, for example, that for any mixed strategy there is a behavior strategy that (for any fixed play of the opponent) gives the same distribution on outcomes.

I'm looking for theorems that extend Kuhn's theorem to games with infinite game trees.  In particular, when one player has finitely many pure strategies, but the other player has uncountably many.

For the game I have in mind, I can make an educated guess at reasonable ways to formally define what a mixed strategy is for the player with uncountably many pure strategies, and I'm sure I can prove the results I want.  I'm sure this must be a special case of known results, but I haven't been able to find a good, accessible reference to cite.  Can anyone suggest a good reference?  Thanks.

p.s. In case you're curious, here is the game I am studying:

An instance of the game is specified by a positive integer $n$, a distribution $P$ on $n$ arbitrary items, and a cost function $c$, where $c(i)\ge 0$ is the cost of slot $i\in[n]$.  Both players know $P$ and $c$.
Player 1 plays first by choosing any permutation $P'$ of the distribution $P$.  We then generate an infinite random sequence $x_1,x_2,\ldots$ of items by repeatedly and independently sampling from $P'$.  The permutation $P'$ is not revealed to Player 2.
At each time $t=1,2,\ldots$, the item $x_t$ is revealed to Player 2.  If the item has not been seen before time $t$, Player 2 (without knowing $P'$ or future requests) must assign some slot $j$ to the item, where slot $j$ has not yet been assigned to any item.
Once Player 2 has seen all $n$ items, he has assigned a unique slot $j(i)$ to each item $i$, and the game ends. Player 2 pays Player 1 the payout $\sum_{i=1}^n P'_i c({j(i)})$.

Each pure strategy of Player 1 is one of the $n!$ permutations of $P$.  Each pure strategy of Player 2 is a function specifying, given any sequence $x_1,x_2,\ldots,x_t$ of items, where $x_t$ is the first occurrence of that item, which slot $j$ to assign to item $x_t$.  (Note that a-priori Player 2 has uncountably many such pure strategies.)  A behavior strategy for Player 2 is a function mapping each such sequence to a distribution on the unassigned slots.

It is a technical exercise to show that the (pure) greedy strategy for Player 2 (assign the slots in order of increasing cost) minimizes the maximum expected payoff.  Also, playing uniformly at random is optimal for Player 1.


texts: What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

texts:
We have some quantum circuit $C$ with $k$ ancillae and $n$ input bits of depth $d$ and size $s$, and we can define a function $f$ which, for any $x \in \{0, 1\}^n$, is the random variable which is the first bit of output from $C|x, 0^k\rangle$, i.e. $Pr(f(x) = 1) = |(C|x, 0^k\rangle)_0|^2$. We define the sensitivity of this function at $x$ as $s(f, x) = \sum_{y : ham(x, y) = 1} |Pr(f(x) = 1) - Pr(f(y) = 1)|$ and the average sensitivity $S(f) = \mathbb{E_x[s(f, x)]}$. We know by an extension of Boppana's 97 paper on the average sensitivity of circuits to probabilistic classical circuits (those which we can compare these to), that these have average sensitivity $O(log(s))^{d-1}$. I think exploring the average sensitivity of these quantum circuits would be a nice way to resolve some of the open problems stated here.

My intuition is that the average sensitivity will be higher than in the classical case, but still lower than the maximal average sensitivity which one gets for parity, showing that $QAC_{wf}^k \neq QAC^k$.

I'd be quite satisfied with approaches to use or just interesting discussions of this as answers, as I don't expect for someone to actually resolve this here.


texts: Complexity of applying a permutation in-place

texts:
To my surprise, I was not able to find papers about this - probably searched the wrong keywords.

So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.

How do we reorder the array according to $f$ with memory and runtime as close to $O(1)$ and $O(n)$ as possible?

Are there any additional conditions when this task becomes easier? E.g. when we explicitly know a function $g$ is the inverse of $f$?

I know of an algorithm that follows cycles and traverses a cycle for each index to check if it's the least in its cycle, but again, it has worst-case $O(n^2)$ run time, though on average it seems to behave better...


texts: Dependent types over Church-encoded type in PTS/CoC

texts:
I'm experimenting with pure type systems in Barendregt's lambda cube, specifically with the most powerfull one, the Calculus of Constructions. This system has sorts * and BOX. Just for the record, below I'm using the concrete syntax of the Morte tool https://github.com/Gabriel439/Haskell-Morte-Library which is close to the classical lambda calculus.

I see we can emulate inductive types by some kind of Church-like encoding (a.k.a. Boehm-Berarducci isomorphism for algebraic data types).
For a simple example I use type Bool = ∀(t : *) -> t -> t -> t with the constructors True = λ(t : *) -> λ(x : t) -> λ(y : t) -> x and False = λ(t : *) -> λ(x : t) -> λ(y : t) -> y.

I see that the type of term-level functions Bool -> T is isomorphic to pairs of type Product T T with classical Product = λ(A : *) -> λ(B : *) -> ∀(t : *) -> (A -> B -> t) -> t modulo parametricity by means of function if : Bool -> λ(t : *) -> t -> t -> t which is in fact identity.

All questions below will be about representations of dependent types Bool -> *.

I can split D : Bool -> * into pair of D True and D False. Are there the canonical way to create D again? I want to reproduce isomosphism Bool -> T = Product T T by an analogue of function if at type level but I cannot write this function as simple as original if because we cannot pass kinds in arguments like types.
I use a kind of an inductive type with two constuctors to solve question(1). The high level description (Agda-style) is the following type (used instead of type-level if)

data BoolDep (T : *) (F : *) : Bool -> * where
  DepTrue : T -> BoolDep T F True
  DepFalse : F -> BoolDep T F False

with the following encoding in PTS/CoC:

λ(T : *) -> λ(F : *) -> λ(bool : Bool ) ->
∀(P : Bool -> *) ->
∀(DepTrue : T -> P True ) ->
∀(DepFalse : F -> P False ) ->
P bool

Is my encoding above correct?
I can write down the constructors for BoolDep like this code for DepTrue : ∀(T : *) -> ∀(F : *) -> T -> BoolDep T F True:

λ(T : *) ->  λ(F : *) ->  λ(arg : T ) ->
λ(P : Bool -> *) ->
λ(DepTrue : T -> P True ) ->
λ(DepFalse : F -> P False ) ->
DepTrue arg

but I cannot write down the inverse function (or any function in the inverse direction). Is it possible? Or should I use another representation for BoolDep to produce an isomorphism BoolDep T F True = T?


texts: What is the benefit of Krivine's notation?

texts: I saw some people uses Krivine's notation for function application when presenting the syntax for the $\lambda$-calculus.  For example, the $\lambda$-term $\lambda f . \lambda x . \lambda y . f\ x\ y$ (with the normal convention that function application associates to the left, so it actually means $\lambda f . \lambda x . \lambda y . ((f\ x)\ y)$) is written $\lambda f . \lambda x . \lambda y . (f)\ x\ y$ (with a similar convention that it actually means $\lambda f . \lambda x . \lambda y . ((f)\ x)\ y$).  I do not see the point of having another pair of parentheses around the innermost $f$.  Why do people use Krivine's notation instead of the usual one?


texts: Difference between Primal Dual Algorithm for Proper and Uncrossable Functions

texts:
Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions:

(1) super-modular functions

(2) proper functions

(3) uncrossable function

All of which is covered in his PhD thesis titled: "On the design of approximation algorithms for a class of graph problems.", 1993.

My question is that where is the difficulty coming when we move from 0-1 proper to uncrossable functions?? May be some example would also help. Is there some variant of uncrossable function which is superset of proper functions in general?? Also, why do we not consider sub-modular functions?? Why types of problems would have sub-modular functions. (i know about the trivial example of modular function i.e. cut $\delta(S)$ but nothing much). So where is difficulty coming when we consider sub-modular functions or are they too easy?? This would probably let me know the inspiration to consider the super-modular functions. Also a related question is that sometimes we replace two crossable sets by uncrossing sets, like when we construct the tree corresponding to laminarity concept. Is this always possible?? (in case of every supermodular function?? or only in uncrossable functions??) Interesting references would also help.


texts: Partitioning a square for optimal queries

texts:
I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles:

$f(x, y, r)$ tells me how many skittles are in the circle of radius $r$ centered about the point $(x,y)$ on my plate

$q(x, y, r)$ gives me all of the skittles that are in the circle of radius $r$ centered about the point $(x,y)$ on my plate

However, my plate is very big, and my oracles are very small. So the $r$ given to $f$ and $q$ must be less than or equal to a given value $R$.

Oracles don't come free these days: I have to pay a cost of 1 each time I call $f$. Each time I call $q(x, y, r)$, I must pay a cost of $f(x, y, r)/P$: 1 for each $P$ skittles that my oracle brings to me (rounded up). The $P$ is an input to this problem. Then those skittles are eaten.

There are $N$ skittles on my plate. What is a strategy that doesn't cost very much to eat all of my skittles, in terms of $N, R$, and $P$?

I'm curious about two cases:

If an adversary is placing skittles, what is the most they can make me pay?
If all the skittles are each independently placed according to a uniform distribution over the entire plate, what is a strategy that does "sorta well", and what is the expected amount I would need to pay?


texts: What does it take to be accepted to FUN?

texts: I've just understood that FUN's deadline is slowly approaching. The conference page is very vague about what kind of fun they are looking for. So the question is: what the FUN committee is looking for?


texts: Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

texts:
I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology.

Are there any applications for these subjects in computer science?
I have looked a bit, and found a lot of applications (of course) for finite graph theory, finite topology, low dimensional topology, geometric topology etc.

However, I am looking for applications of the infinite objects of these subjects, i.e. infinite trees (Aronszajn trees for example), infinite topology etc.

Any ideas?

Thank you!!


texts: What are multiple rounds of SOS/Lasserre hierarchy?

texts:
Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things?

Or to take a different view,

We needed to show that the projector to low-degree polynomials has bounded hypercontractive norm. We start off defining the projector $\mathcal{P}_d$ as the map,
$$\mathcal{P}_d : ( \{ \pm \}^n \rightarrow \mathbb{R}   )  \rightarrow  ( \{ \pm \}^n \rightarrow \mathbb{R}  )$$
$$ f = \sum_{\alpha \subseteq [n] }\hat {f}_\alpha \chi_\alpha  \rightarrow f' = \sum_{\vert \alpha\vert \leq d } \hat{f}_\alpha \chi_\alpha$$

Where $\chi_\alpha = \prod_{i \in \alpha} x_i$

Then we show that the over the space of such ''$n-$variate Fourier polynomials" $f'$ with degree at most $d$, $\mathbb{E} [f'^4 ] \leq 9^d ( \mathbb{E} [ f'^2 ] )^2  $ (which is equivalent to showing that  $\Vert \cal{P} \Vert_{2 \rightarrow 4 } \leq 9^d$ )

So in the above context is the choice of ``4" what quantifies the number of "rounds" of Lasserre hierarchy used? (the above is called a degree-4 SOS proof!) (as in you can run the SOS-program trying to optimize the hypercontractive norm of an operator only for as large a value of $x$(here $4$) as for which above kind of hypercontractive bounds can be established?)
Since this hypercontractive bound on such projection operators is already proven as a theorem then what does the so-called "Tensor-SDP" algorithm achieve in terms of giving an "efficient certificate"?


texts: Dependent corrections in measurement-based Universal Blind Quantum Computation

texts:
In Universal Blind Quantum Computation the autors describe a measurement-based protocol which allows an almost classical user to perform arbitrary computations on a quantum server without revealing almost anything about the content of the computation.

In the protocol description, the authors mention "dependency sets" associated to each qubit, which are supposed to be calculated by some method described in Determinism in the one-way model

However, it's not clear to me from reading the paper how these set are computed.

Can somebody help to clarify this issue?


texts: Approximating Max-Coverage when the elements need to be covered multiple times

texts:
In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. The question is to cover N with the minimum number of subsets from S. I'm aware of the approximation algorithms for this problem (Rajagopalan & Vazirani).

I'm interested in a different version of the problem (max multi-coverage). We are given K and we ask for the maximal number of the elements from N we can cover with K subsets from S. We count an element as covered if it is covered at least the required number of times. Are there any approximation algorithms for this case? Are there any lower bounds for this case (or even for the standard set multicover problem)?

Thanks in advance!


texts: Transitive reduction not provably minimal

texts:
Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be created, you can simply replace any SCC with a simple Hamiltonian cycle.

This excerpt from The Algorithm Design Manual has me confused however:

  "A linear-time, quick-and-dirty transitive reduction algorithm
  identifies the strongly connected components of G, replaces each by a
  simple directed cycle, and adds these edges to those bridging the
  different components. Although this reduction is not provably minimal,
  it is likely to be pretty close on typical graphs."

Can anyone explain when this would not be minimal? How is it ever possible to construct a smaller equivalent component than a simple directed cycle?


texts: How to show that a type in a system with dependent types is not inhabited (i.e. formula not provable)?

texts:
For systems without dependent types, like Hindley-Milner type system, the types correspond to formulas of intuitionistic logic. There we know that its models are Heyting algebras, and in particular, to disprove a formula, we can restrict to one Heyting algebra where each formula is represented by an open subset of $\mathbb{R}$.

For example, if we want to show that $\forall\alpha.\alpha\lor(\alpha\rightarrow\bot)$ is not inhabited, we construct a mapping $\phi$ from formulas to open subsets of $\mathbb{R}$ by defining:
\begin{align}
\phi(\alpha) &= (-\infty, 0)
\end{align}
Then
\begin{align}
\phi(\alpha\rightarrow\bot) &= \mbox{int}( [0, \infty) ) \\ & = (0,\infty) \\
\phi(\alpha\lor(\alpha\rightarrow\bot)) &= (-\infty, 0) \cup (0,\infty) \\
  &= \mathbb{R} \setminus {0}.
\end{align}
This shows that the original formula cannot be provable, since we have a model where it's not true, or equivalently (by Curry-Howard isomorphism) the type cannot be inhabited.

Another possibility would be to use Kriepke frames.

Are there any similar methods for systems with dependent types? Like some generalization of Heyting algebras or Kripke frames?

Note: I'm not asking for a decision procedure, I know there cannot be any. I'm asking just for a mechanism that allows to witness unprovability of a formula - to convince someone that it's unprovable.


texts: Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)

texts:
Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^{\mathsf{poly}(n)};\; S(r))$. Let's call such an $S$ a sampler for $D$.

Question

Is it possible to pseduodeterministically (in the sense of e.g., this paper) choose an element from the support of $D_n$ in sub-exponential time? I.e., is there a probabilistic sub-exponential time algorithm $C$ ($C$ for choice) with the following properties:

For any two samplers $S_1, S_2$ of $D$ we have $C(S_1, 1^n) = C(S_2, 1^n)$ with noticeable probability.
For any sampler $S$ for $D$, $C(S, 1^n)$ is in the support of $D_n$ for all $n$.

It would still be interesting if property 1 were weakened to "with non-negligible probability" and 2 were weakened to "for infinitely many $n$".

Please feel free to make any plausible complexity-theoretic assumptions.

Some motivation

You can think of $C$ as a kind of canonical-choice algorithm. Note that constructing the above is at least as hard as giving a sub-exponential time algorithm for graph isomorphism, since given a graph $G$ we can easily construct a sampler for a distribution supported on the isomorphism class of $G$ that does not depend on the choice of $G$. To test if two graphs are isomorphic we feed these two distributions into our chooser $C$ and check to see if the canonical representatives output by $C$ are equal.


texts: Relation between tree-width and clique number

texts:
Are there any nice graph classes for which the tree-width $tw(G)$ is upper-bounded by a function of the clique number $\omega(G)$, i.e. $tw(G)\leq f(\omega(G))$?

For example, it is a classic fact that for any chordal graph $G$, we have $tw(G)=\omega(G)-1$. So, classes related to chordal graphs could be good candidates.