texts: Random sampling data structure with removal

texts:
I'd like a data structure with the following operations:

create a new instances from an array of floating point weights.
randomly sample, returning an item with probability proportionate to its weight.
set the weight of a specific item to 0.

Without the third option this is pretty standard: Just implement an alias method sampler using Vose's algorithm, but the ability to do a dynamic update makes it harder.

The first operation is intrinsically O(n) (or at least it is if you don't make the second operation O(n)), but it would be nice to be able to do the other two in amortized O(1), or at least O(log(n)). Sampling will be significantly the more common operation, so ideally I would like to have it not be much slower (either in complexity or constant factors) than using the alias method.

One option is to just rebuild the sampler every time you do a remove, but that's O(n) which is less than ideal.

The following is currently my best bet, which builds on that to amortise it a bit:

We keep a copy of the set of weights, and build an alias method sampler initially. When we set the weight of an item to zero we update our weights table appropriately. Then when we sample from our alias table, we check the weight. If it's zero then we rebuild the alias table with the updated weights and draw again.

This should work OK for amortising some of the cost, but unfortunately the workload I'm likely to want to put it through is probably pessimal for it: Items that are going to be removed will have been drawn from the sampler, so will tend to be of high weight. This means that it will end up hitting the rebuild case fairly commonly.

So I'm hoping for something better. Any suggestions?


texts: Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?

texts: So far, I've only encountered the VC-dim for binary classifiers. I'm interested to learn how this notion can be extended to the multi-class case. Are there expressions that provide bounds on the out-of-sample error based on the VC-dim for multi-category classifiers? The learning machines I am interested in are: SVMs, Neural Networks, AdaBoost and k-Nearest neighbors. Thanks.


texts: Complexity of the homomorphism problem parameterized by treewidth

texts:
The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two
classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows:

  Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $\mathcal{H}$

  Output: decide if there is a homomorphism from $G$ to $H$, i.e.,
    a mapping $h$ from the vertices of $G$ to those of $H$ such that,
    for any edge $\{x, y\}$ of $G$, $\{h(x), h(y)\}$ is an edge of $H$.

For each $k \in \mathbb{N}$, I will call $\mathcal{T}_k$ the class of the
graphs of treewidth at most
$k$. I'm interested in the problem $\text{Hom}(\mathcal{T}_k, \mathcal{T}_k)$,
which I see as a parameterized problem (by the treewidth bound $k$). My
question is: what is the complexity of this parameterized problem?
Is it known to be FPT? or is it W[1]-hard?

Here are some things that I found about the $\text{Hom}$ problem, but which do
not help me answer the question. (I write $-$ for the class of all graphs.)

http://www.sciencedirect.com/science/article/pii/009589569090132J:
If $\mathcal{H}$ is bipartite then $\text{Hom}(-, \mathcal{H})$ is in PTIME,
otherwise it is NP-complete, but of course the NP-hardness relies on
allowing arbitrary $G$.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9013&rep=rep1&type=pdf: If the treewidth of $\mathcal{G}$ (modulo homomorphic equivalence)
is bounded by a constant then $\text{Hom}(\mathcal{G}, -)$ is in PTIME (and
otherwise it isn't, assuming FPT != W[1]). Hence, in particular my
problem $\text{Hom}(\mathcal{T}_k, \mathcal{T}_k)$ is in PTIME for fixed $k$,
but this doesn't tell me what is the dependency on the parameter.
From Flum and Grohe's book Parameterized Complexity Theory, Corollary
13.17: The problem $\text{Hom}(\mathcal{T}_k, -)$ is FPT when parameterized
by the size of $G$ (but I am parameterizing by the treewidth)
http://users.uoa.gr/~sedthilk/papers/homo.pdf, Corollary 3.2: When
fixing a specific graph $H$, the problem $\text{Hom}(\mathcal{T}_k, \{H\})$,
parameterized by k, is FPT (this even holds for more complicated
counting variants), but I do not want to restrict to fixed $H$.


texts:
Exact cover by 3-sets problem is defined as:

Instance: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}  $ of 3-elements subsets of $X$ (triples);
Question: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.

It is known that Exact cover by 3-sets problem is NP-complete even if input is restricted such that each element of $X$ appears exactly in three triples.

  Is still NP-complete if the input is restricted further such that no pair of input triples share more than one element of $X$?


texts: Generating all instances of a regular language up to a certain length

texts:
Given a fixed regular language R, what is the complexity of generating all members of R with length at most $n$?  Suppose some reasonable model (RAM with $n$-bit words?) and a write-only output tape.  The list should be in length-lexicographical order.

I'm interested in the answer in terms of the output as well as the input.  (If R = Σ* then you can't improve on $O(|\Sigma|^n)$ but it only takes time linear in the output.)


texts: Proof that the theory of rationals is convex

texts:
In Example 10.12 of the book The calculus of computation by Bradley and Manna, it is said

The theory of rationals is convex, as it is convex in a geometric sense.

How does the geometric sense of convex relate to theories being convex?
It further gives a proof by contradiction but I am unclear on what the assumptions are, what is being contradicted and how.

The theory of rationals TQ is convex, as it is convex in a geometric sense ... Each equality ui = vi of the disjunction G of is geometrically convex, but G itself is not. Consider, for example, H : x=y ∨ x=z. Let SH be the set of points satisfying H. The point (x,y,z) = (0,0,1) is included in SH , as is the point (1,0,1). However, the average of the two points, (12, 0,1) (choosing λ = 1/2), is not in SH. Indeed, choose any two points (u, u,v1) and (w,v2,w) from Sx=y and Sx=z, respectively, such that neither is in their intersection Sx=y=z (i.e., v1= u and v2= w). Then for any λ ∈ (0,1), the point
(λu +(1−λ)w, λu+(1−λ)v2, λv1 +(1−λ)w)
is neither in Sx=y nor in Sx=z. Suppose, then, that F ⇒ G : ni=1 ui = vi, but for no i ∈ {1,...,n} does F ⇒ui=vi. Then it must be the case that there are two points s1 and s2 of SF in separate subsets Sui=vi, Suj=vj, i= j, of SG. By the argument above, the points on the line segment between s1 and s2 are not in SG and thus not in SF. Then F is not geometrically convex, a contradiction. Thus, TQ is convex.

UPDATE:
Context from the same book:

If a conjunctive formula in a convex theory implies a disjunction of equalities between variables, then it actually implies a single equality. Formally, consider a quantifier-free conjunctive Σ-formula F and a disjunction n
G: conjunction_over_i_to_n ( ui = vi ),
for variables ui and vi.
Theory T is convex if for every such F and G, if n
F ⇒ disjunction_over_i_to_n (ui = vi)
then,
F ⇒ ui=vi for some i∈{1,...,n} .
If F implies G, then F actually implies one of the disjuncts of G.

Cross-posted from SO: https://stackoverflow.com/q/38814285/1494559 (as it lies in the intersection of the fields)


texts: Techniques introduced to log-rank conjecture

texts: What have been some of techniques (like discrepancy, arithmetic combinatorics) that have been introduced to shed light on Log-rank conjecture which roughly states that deterministic communication complexity of a communication problem roughly depends on some fixed power of rank of communication matrix of problem under study?


texts:
Context: Aaronson raised the following question:

  Let f be a black-box function, which is promised either to satisfy the
  Simon promise or to be one-to-one.  Can a prover with the power of BQP
  convince a BPP verifier that f is one-to-one?

Speculation: Let's take Arthur-Merlin protocols (I actually don't know in much depth about these protocols so please pardon any inconsistencies that may arise) where one can restrict Merlin's power to BQP instead of unbounded resources and Arthur has BPP resources. Now I realize that there are probabilities to:

  A problem is considered to be solvable by this protocol if whenever
  the answer is "yes", Merlin has some series of responses which will
  cause Arthur to accept at least 2/3 of the time, and if whenever the
  answer is "no", Arthur will never accept more than 1/3 of the time.

source: Wikipedia.

Now consider the following, this paper gives an algorithm where one can check in quantum polynomial time whether a function satisfies Simon's promise. Merlin can therefore check this, for Arthur we don't know, let's assume it can't.

Question: Given the above mentioned conjecture, if Arthur sends (through a message) Merlin the function to be computed/checked in the first pass, Merlin can check whether the function satisfies Simon's promise or not, if yes, then we know the answer, if no, then is checking whether a function one-to-one in polynomial time? Also if Arthur can't check whether the function satisfies Simon's promise can the probabilities above mentioned change, since Merlin knows the answer already?

I also think this question might remain open until we know whether BPP != BQP, are there any indirect techniques that can let one evade having to rely on conjectural support in my argument? Thanks!


texts: Is there a universal gate set for classical probabilistic computing?

texts:
We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum circuits. However, what about classical probabilistic circuits?

It seems like if you had a "coin-flip" gate (takes no input/any input and produces 0 or 1, each with probability 1/2) and NAND, you could build any probabilistic circuit you want (up to some level of precision) with a rejection sampling procedure. The desired probabilistic circuit can be seen as a set of deterministic circuits, chosen according to some distribution; use rejection sampling to simulate that distribution and then apply the required deterministic circuit.

(by the same argument, any gate that produces a fixed, non-trivial probability distribution, plus NAND, would be universal).

Is this a question that has been looked into? Any results that I can cite?


texts: What is the complexity of computing a compatible 3-coloring of a complete graph?

texts:
Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points.

The best algorithm I know is quasi-polynomial time. The problem is not known to be NP-complete. What is known about the status of this problem ?


texts: Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?

texts:
The paper https://cs.brown.edu/people/seny/pubs/vbponline.pdf discusses $\{0,1\}$-Vector Bin packing in the online setting and give lower bounds. However, they do not mention anything about the complexity of the problem in the offline setting. I could not find any other papers mentioning this either.

Formally, the problem is as follows: Given a set of vectors $V=\{x_1,x_2,\ldots,x_n\}$, where each $x_i\in\{0,1\}^d$, and a vector $\textbf{b}=(b_1,b_2,\ldots,b_d)\in \mathbb{Z}_+^d$, partition $V$ into $V_1,V_2,\ldots,V_l$ such that $\forall~j,\sum_{x_i\in V_j} x_i \leq \textbf{b}$. Then the objective is to minimize the number of partitions, $l$.

While the problem in general can easily be seen to be NP-Hard from Independent set or, as Yonatan pointed out, $k$-colouring, I'm interested in the case when the vectors are from $\{0,1\}^d$, where $d=O(1)$. It is known that $[0,1]$-vector packing is NP-Hard even under this restriction, because it is a generalization of bin packing. However, I did not find anything for the $\{0,1\}$ case. Is this problem NP-Hard?

Neal Young has given an excellent answer for the case when the vector $\textbf{b}$ has $\forall ~i,b_i=O(1)$. This leaves the case where $b_i$ is not constant. In particular, $b_i=\Omega(n)$ seems to remain hard.

Edit: It seems that the problem has been considered, at least in the knapsack context, here. Their algorithm for the $d=2$ case seems very non-trivial. This seems to suggest that the ILP approach suggested by Gamow wouldn't work.


texts: Is there a name for this property of a binary relation?

texts:
Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case.

(EDIT: note that this may be formalized as $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z)))$

Is there a well-known name for the property enjoyed by this relation?  And are there natural examples in mathematics (or in ARS) of relations characterized by this property?

In normal modal logic, the above property characterizes frames axiomatized by the schema $\lozenge\square\alpha\to\lozenge\alpha$ (or, dually, by $\square\alpha\to\square\lozenge\alpha$).  It amounts to a stronger version of the Church-Rosser property, according to which $x\mathsf{R}y$ and $y\mathsf{R}x$ are simultaneously the case only if there is a $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case.  I have however been unable to determine so far whether there is an established name for the above mentioned property in the literature.

(I am now cross-posting this with Math.SE, to see if anyone there has an aswer to offer.)


texts: Quality measure for clusters of a metric space embedding of a graph?

texts:
When evaluating clustering algorithms for networks, we have well-established metrics like Modularity and Surprise for evaluating the quality of the resulting partition.

If we then embed our graph (well) in a metric space, it becomes much easier to compute distances and communities using geometric algorithms on the points, at the cost of losing our link structure.  Therefore, given a partitioning of the points in the metric space (into, say, k clusters) are there any well-established metrics for computing the quality of the clusters?

And if such metrics exist, can we say anything about what embedding/clustering methods are likely to yield clusters that yield similar results when moving from a graph to its embedding?


texts: Complexity of two perfect matchings with minimum shared edges?

texts:
Perfect Matching problem is polynomial time solvable in general graphs.
Given undirected simple graph,

  Is the problem of finding two perfect matching with minimum shared edges between them efficiently solvable?

Shared edge is an edge that occurs in both perfect matchings.


texts: Representing data with Shannon entropy predicted bits

texts:
Let us assume a file based on a character set where each character has equal probability of occurance. This will result in the maximum entropy for that character set. On calculating the entropy, let us say that the entropy is just above an integral value. Usually, in such cases, the number is rounded up(which makes sense when it comes to storage).

Using standard techniques, when a single character in the string changes, the entire binary representation changes along with it. So is there any efficient coding technique where the representation doesn't change much with small changes in the original string?


texts: I recently started to read a lot about proof complexity and have been really enjoying what I have been reading. I would really like to learn more about this, but I am having difficulty finding some good beginner material to start with. Would anyone be able to recommend some basics?


texts: Find all pairs of values that are close under Hamming distance

texts:
I have a few million 32-bit values. For each value, I want to find all other values within a hamming distance of 5. In the naive approach, this requires $O(N^2)$ comparisons, which I want to avoid.

I realized that if I just treated these 32-bit values as integers and sorted the list once, then values which differed only in the least significant bits ended up very close together. This allows me to have a shorter "window" or range of numbers within which I can perform actual pair-wise comparisons for the exact hamming distance. However, when 2 values vary only in the higher order bits, then they end up outside this "window" and appear in opposite ends of the sorted list. E.g.

11010010101001110001111001010110

01010010101001110001111001010110

would be very far apart, even though their hamming distance is 1. Since, the hamming distance between 2 values are preserved when both are rotated, I figured that by doing 32 left rotations and then sorting the list every time, it's likely that 2 values will end up close enough in the sorted list in at least one of them.

Although this approach is giving me good results, I'm struggling to formally establish the correctness of this approach.
Given that I'm looking for matching values having hamming distance $k$ or less, do I really need to do all 32 bit rotations? For e.g. if $k=1$ and my window size is 1000, I need to do at max 24 bit rotations because even if the stray bit appeared in any of the 8 lower order bits, the resulting numbers won't differ by more than 1000.


texts: Proof that the graph optimization problem is NP-hard

texts:
I'm trying to prove that the following optimization problem is NP-hard:

Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)$, find a subset of vertices $S \in V$ that minimizes the function $C$:

$$C = \sum_{v \notin S}{w(v)} + \sum_{v \in S}{s(v)} + \sum_{(u,v) \in E:u \in S, v \notin S}{t(u,v)} $$

$$w(v) \geq 0, s(v) \geq 0, t(u, v) \geq 0$$

In other words, I'm trying to bipartition the graph and minimize the sum of vertex weights and edge weights across the cut, but the vertex weights are different depending on which "side" of the partition they are.

I've tried to reduce the max-cut problem to this by somehow minimizing the complement graph, also tried the sparsest cut, but the second weight function always seems to be problematic. Obviously, assuming that $s(v) = 0$ or $s(v) = w(v)$ makes the problem trivial, so there must be some solution that I'm missing. Or maybe the problem isn't NP-hard at all?

Any help is appreciated :)

Edit: restrict to non-negative weights


texts: Space complexity of Coppersmith–Winograd algorithm

texts: Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$  which is the best known so far. What is the space complexity of this algorithm ? Is it in $\Theta(n^2)$ ?


texts: How can I find the second cheapest spanning tree?

texts:
The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead.

Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly more costly than an MST, but is the second cheapest? For example, if you switch one of the edges in this spanning tree, you end up with an MST and vice versa.

My question, though, is simply: How can I find the second cheapest spanning tree, given a graph $G$ with an MST?


texts: Probability for an element to appear in at least one set

texts:
Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct.

What is the probability that $j$ ($j=1,...,M$) elements appear at least once in the (union of the) sets?

We know that for $j = N$ the probability is $1$. For $j > N$ I wanted to use the binomial distribution, but the parameter $p$ should be conditioned somehow on the number of elements that already appear in the sets. Should I use some recursive formula for this?

Edit:

(1) This maybe also be formulated as the famous balls in bins problem, with the twist that the balls are thrown $N$ at a time to $M$ bins, where it is known that each group of $N$ balls falls into distinct $N$ bins.

(2) Another option to see this is as the (extended) Coupon Collector's Problem, who acquires $N$ (instead of $1$) distinct coupons at a time, from a set of $M$ distinct coupons. Denoting by $W_t(j)$ the probability that he acquired $j$ distinct coupons at time $t$, my questions is what is the probability distribution of $W_t(j)$, for $j=N,N+1,...,M$, for each time (or set in the original formulation) $t=1,2,...,k$. I saw something relevant here:
https://math.stackexchange.com/questions/100175/probability-of-non-empty-bins-after-randomly-inserting-balls-by-pairs


texts: Generate random permutation via iid uniforms --- is inverse transformation possible?

texts:
A very common technique in the analysis of algorithms involving random permutations is to have each element $x$ select a rank $\rho(x)$ uniformly at random from the real interval $[0,1]$. The permutation $\pi$ is then formed by sorting on ranks.

Is it possible to invert this transformation? That is, given a permutation $\pi$ generated randomly in $S_n$, choose ranks $\rho(x)$ (with some additional randomness) such that

Over all possible $\pi$, each $\rho(x)$ is uniformly distributed in $[0,1]$
$\rho(\pi(1)) < \rho(\pi(2)) < \dots < \rho(\pi(n))$
(Optional) $\rho(\pi(i))$ depends only only $\pi(1), \dots, \pi(i)$

Seemingly, giving $\rho(\pi(1))$ the distribution on the minimum of  $n$ uniform variables, and so on, would work. Is there are any reference?


texts: What tools do you use to give presentations?

texts:
I was wondering what tools that people in this field (theoretical computer science) use to create presentations. Since a great deal of computer science is not just writing papers but also giving presentations I thought that this would be an important soft question. This is inspired by the previous question what tools do you use to write papers.  The most common that I have seen are as follows.

Beamer
Microsoft PowerPoint
LaTeX
GraphViz

I was wondering if there are any other tricks that I am missing?


texts: Bloom filter variant for constant-time subset/superset queries

texts:
Bloom filters make it easy to determine if an element is in a set, within some acceptable margin of error. I'm looking to solve a related problem for which Bloom filters are inadequate, but for which I'm hoping some "Bloom-like" solution will hold:

Suppose I have some universe set $U$, and the things I care about are subsets of $U$. In other words, they are elements of the power set $2^U$. I want to add elements to the Bloom-like filter one at a time. Each time I add, I want to check the following things:

Is this element already in the list?
2a. Is this element a proper superset of something already in the list?
2b. OR, is this element a proper subset of something already in the list?

I only need to implement one of the superset/subset queries for my application - doesn't matter which one. If I can handle one case, I'm good.

Standard Bloom filters can only handle the first case, so I'm looking for a way to handle the last two as well.

The literature is full of ways to extend Bloom filters: for pattern matching, set queries, small subset queries, etc.

I've been digging but the literature is fairly convoluted and I lack a good starting point here: the set query ones don't appear to be constant time, and nothing seems to be quite what I'm looking for. If anyone is familiar with the literature and knows a solution to the exact problem specified above, I would appreciate a good reference.

To be specific, I am looking for a data structure which has the following characteristics:

It admits sublinear-time additions and queries. (Ideally constant time)
There exists some probability of error (usually false positive).
The error rate decreases with the size of the filter.

FWIW, the compact approximator approach looked interesting, and possibly something you could tweak to get what I'm after, but I wasn't sure how to do it.


texts: What functions can System F not compute?

texts:
In this wikipedia article on Turing Completeness it states that:

  The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.

What is an example of a total computable function that is uncomputable by system F?

In addition, since hindley-milner is:

  A restriction of System F

because of the fact that:

  type checking is undecidable for a Curry-style variant of System F, that is, one that lacks explicit typing annotations.

Does this mean that the lambda calculus underlying hindley-milner type systems is not turing complete as well?

If this is true, since haskell is clearly turing complete and we know that it's basis is the lambda calculus and the hindley-milner type system, what features that are not present in the lambda calculus are added in order to make haskell turing complete?


texts: I'm working on a Haskell library for approximation algorithms.  In particular, I'm working on Partition, Knapsack, Vertex Cover, and possibly a few others.  Of course, I'd like to benchmark my library against other libraries in terms of both speed and the goodness of the solution.  So, are there any good benchmarks for these problems out there?  I'm looking for something like the UCI machine learning repository, but for approximation algorithms.


texts: Common insights into hypothetical complexity of graph problems

texts:
I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. For instance, Barnette's conjecture states that every 3-connected cubic planar bipartite graph is Hamiltonian. Feder and Subi proved that refuting the conjecture would imply the NP-completeness of the Hamiltonian cycle problem on graphs in the class of the conjecture.

Tutte's 5-flow Conjecture states that every bridgeless graph has a nowhere-zero 5-flow. Kochol showed that if the conjecture is false, then the problem of determining whether a cubic graph admits a nowhere-zero 5-flow is NP-complete.

  Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems? Are there other examples of hypothetical complexity in the above sense?

P.S. This was posted on MathoverFlow without getting an answer.


texts: Lower Bound for Nonzero Terms of a Polynomial Fully Sensitive at 0

texts:
Every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be uniquely represented as a multilinear polynomial $p=\sum_{S\subseteq [n]}c_S \chi_s$ where $\chi_s=\prod_{i\in S}x_i$.

A boolean function is fully-sensitive at $\vec{0}$ if $f(\vec{0})=0$ (wlog) and takes value $1$ on any input with hamming weight $1$.

Question: Is there any lower bound on the number of nonzero terms for such a polynomial(originated from a boolean function and fully-sensitive at $\vec{0}$?)

To the best of my knowledge, Noam Nisan and Avi Wigderson studied this type of function and proposed an example with degree $O(n^{log_3 2})$, which also suggested an upper bound of $2^{O(n^{\log_3 2})}$ on the number of nonzero terms, but what about the lower bounds? Besides, the character of "fully sensitive at $\vec{0}$" is indeed an embedding of Unique Disjoint Function, which also has results on lower bound on nonnegative ranks, etc. However, those results and ideas seem not directly applicable here.

Any previous results or ideas would help. Thanks!


texts: Approximating a max-cut's intersection with other cuts

texts:
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any other cut. Finding a max cut is NP-hard, but a greedy algorithm (e.g.) can approximate a max cut, finding a cut with at least half as many edges as possible.

Equivalently, a cut $\delta (S)\subseteq E(G)$ is a max cut if and only if
$$| \delta (S)\cap \delta (T) |\geq \frac{1}{2}|\delta (T)|  \qquad \forall\text{ cuts } \delta (T)\subseteq E(G).$$
(Sidenote: It should be clear that the standard definition implies this one. To show that these inequalities imply $\delta (S)$ is at least as big as any other cut $\delta (S')$, observe that $$|\delta (S)| - |\delta (S')| = |\delta (S) \cap \delta (S\Delta S')| - |\delta (S') \cap \delta (S\Delta S')|.$$ Because the two edge-sets appearing in the right-hand side partition the edges of the cut $\delta (S\Delta S')$, applying the above inequality with $S\Delta S'$ in the role of $T$ gives $|\delta (S)|-|\delta (S')|\geq 0$.)

I'd like to know whether max cuts can be easily approximated in the sense of my second definition. Specifically:

  Question: Is there a polynomial-time algorithm to find a cut $\delta (S)\subseteq E(G)$ with $$| \delta (S)\cap \delta (T) |\geq \epsilon |\delta (T)| \qquad \forall\text{ cuts } \delta (T)\subseteq E(G)$$ for some $\epsilon > 0$?


texts:
I'm trying to understand the connections between a few different concepts fundamental to dependent type theory.

Dependent functions ($\Pi$-types)

Including non-dependent functions ($A \rightarrow B$)

Dependent pairs ($\Sigma$-types)

Including non-dependent products ($A \times B$)

Coproducts ($A + B$)

Homotopy Type Theory says the following about $\Sigma$s and $\Pi$s:

[ $\Sigma$ ] is called a dependent pair type, or $\Sigma$-type, because in set theory it corresponds to an indexed sum (in the sense of a coproduct or disjoint union) over a given type.
The name "$\Pi$-type" is used because this type can also be regarded as the cartesian product over a given type

(I don't think I fully understand this point)
In a non-dependent setting I'm accustomed to calling coproducts "sums" because the number of inhabitants of a coproduct is the sum of its constituent types' inhabitants - $|A+B| = |A| + |B|$. Likewise I call dependent pairs "products" because $|(A,B)| = |A| \cdot |B|$. Also functions can be called exponentials - $|A \rightarrow B| = |B|^{|A|}$!
Now for the question.
Why does it make sense in Type Theory to use $\Sigma$ for products and $\Pi$ for exponentials? It seems like everything is shifted between non-dependent and dependent types.

sums approximately correspond to dependent coproducts
products approximately correspond to dependent sums
exponentials approximately correspond to dependent products
what about dependent exponentials?

What's the deeper connection?


texts:
Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7.pdf introduces monotone complexity classes in monotone Turing models.

Does Positive Linear Programming have a monotone polynomial complexity?
Can PLP approximation be parallelizable in $mNC$?


texts: What's the complexity of counting odd nodes in graph?

texts:
According to Handshaking Lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem).

PPA ( Christos Papadimitriou in 1994 [1]) is defined as follows. Suppose we have a graph on whose vertices are n-bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently perform local exploration.) Suppose furthermore that a specific vertex (say the all-zeroes vector) has an odd number of neighbors. We are required to find another odd-degree vertex. The corresponding class of parity arguments for directed graphs is belong to PPAD.

My question: What is the complexity of counting odd nodes in directed and undirected graph?

[1] Papadimitriou, Christos H. "On the complexity of the parity argument and other inefficient proofs of existence." Journal of Computer and system Sciences 48.3 (1994): 498-532.


texts: Simple spatial ordering or TSP algorithms?

texts:
I'm not sure if this is the right place to ask, but I suppose you'll tell me.

I'm writing a program that produces a series of points on a map, and I need to put the points in some linear order so that adjacent points in the list are usually near each other. I just want to tack this on as a minor feature, so I need a simple algorithm that won't be hard to implement, and won't take more than O(N2) time.

I don't need much accuracy so maybe Z-order or Hilbert order would suffice, but the points are floating-point, and I only know how to implement Z-order for integer coordinates.

So, what algorithm would you suggest?


texts: Why is Bayesian filtering better than Neural Networks when classifying spam?

texts:
According to several people on StackOverflow Bayesian filtering is better than Neural Networks for detecting spam.

According to the literature I've read that shouldn't be the case. Please explain!


texts: Is there any known CCC closed under a probabilistic powerdomain operation?

texts:
Equivalently, is there a known denotational semantics for probabilistic higher-order functional programming languages? Specifically, is there a domain model of pure untyped $\lambda$-calculus extended by a symmetric random binary choice operation.

Motivation

Cartesian closed categories provide a semantics to higher-order $\lambda$-calculi. Probabilistic powerdomains provide semantics to stochastic programs. A CCC closed under a probabilistic powerdomain operation would provide a semantics to a stochastic higher-order functional programming language.

Related Work

Tix, Keimel, and Plotkin (2004) [1] give modern constructions of the lower-, upper-, and convex- powerdomain operations, but remark that

  It still is an open problem whether there is a cartesian closed category of continuous domains which is closed under the construction of probabilistic powerdomains.

Mislove (2013) [2,3] gives semantics for continuous random variables in a first-order language, but remarks that

  Even though the probabilistic power domain leaves the CCC of directed complete posets (dcpos, for short) and Scott-continuous maps invariant, there is no Cartesian closed category of domains – dcpos that satisfy the usual approximation assumption – that is known to be invariant under this construct. The best that is known is that the category of coherent domains is invariant under the probabilistic choice monad [4], but this category is not Cartesian closed.

References

Regina Tix, Klaus Keimel, and Gordon Plotkin (2004)
"Semantic domains for combining probability and non-determinism".
Michael Mislove (2013)
"Anatomy of a domain of continuous random variables I"
Michael Mislove (2013)
"Anatomy of a domain of continuous random variables II"
Jung, A. and R. Tix (1998)
"The troublesome probabilistic powerdomain"


texts: Typing of substitution in a bidirectional type system

texts:
In most typed lambda calculi, we have the following lemma:

If $\Gamma \vdash t_1 : \tau_1$ and $\Gamma, x : \tau_1, \Delta \vdash t_2 : \tau_2$ then $\Gamma,\Delta[t_1/x] \vdash t_2[t_1/x] : \tau_2[t_1/x]$

However, I'm wondering how we'd phrase such a lemma in a bidirectional typing system, with synthesis $\Rightarrow$ and checking $\Leftarrow$ judgements.

The main problem is that substitution does not preserve synthesis. For example, in most systems, $\Gamma \vdash x \Rightarrow T$ if $x : T \in \Gamma$, but  $[(\lambda y \ldotp t)/x]x$ won't synthesize any type if there are only checking rules for $\lambda$.

Potential solutions I can think of:

Restrict to substituting with synthesizing expressions. This seems like it would give us the induction hypothesis we need (since, in most systems, all synthesizing expressions also check), but is very restrictive.
Only show that substitution preserves checking. This is a weaker result, and I'm unsure of whether it gives us a strong enough inductive hypothesis, since it would be difficult to rebuild typing derivations with synthesis judgements in the premises.

This seems like a pretty basic metatheoretic property, so I'm sure I'm not the first one to have encountered this. Does anyone have a reference to a bidirectional system that cleanly solves these issues? Is there an obvious solution I am missing?


texts:
I'm looking for a formal proof that a problem (say, dominating set) is bidimensional/contraction-bidimensional. Either a reference or a proof sketch is fine.

There are two elements in the definition of (contraction-)bidimensionality (1) taking minor/contraction does not increase the parameter (2) on r*r-grid/triangulated grid, the solution value is at least theta(r*r).
In particular, I'd like to know how the proof goes regarding (2).


texts: Computing weighted sums of binomial coefficients

texts:
This question is a reformulation of
Complexity for computing weighted number of paths on integer lattice

Is there any way to compute in $o(n^2)$ all $n$ sums
$\sum_{0\leq i \leq j} a_i\binom{j}{i}$ for $j\in\{1,\dots,n\}$?


texts: Algorithms with finite expected running time and infinite variance

texts:
I am working on an algorithm for which the running time is a random variable $X$ that has finite expected value, but infinite variance. Are there examples of other algorithms for which this is the case?

Are any such algorithm used in practice, or does the infinite variance make the running time too unpredictable?


texts: Approximation algorithms for problems in P

texts:
One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for several reasons. Off the top of my head, an approximation algorithm may run with a much lower complexity (or even a much smaller constant), might use less space or might be much better parallelizable.

Also, schemes that provide time/accuracy tradeoffs (FPTAS's and PTAS's) might be very attractive for problems in P with lower bounds that are unacceptable on large inputs.

Three questions: is there anything that I'm missing that makes this obviously a bad idea? Is there research going on in developing a theory of these algorithms? If not, at least, is anyone familiar with individual examples of such algorithms?


texts: Tree decompositions of optimal width where every vertex is in a bounded number of bags?

texts:
Let $G$ be a graph on $n$ vertices whose maximum degree is at most $\Delta$ and whose treewidth is at most $k$.
Does there exist a function $f(k, \Delta)$, independent of $n$, such that it is possible to find a tree decomposition of $G$ of width $k$ (i.e. with bags of size $k+1$) with the additional property that every vertex of $G$ is in at most $f(k, \Delta)$ of the bags?

A related concept which is perhaps relevant is that of domino treewidth.
We say a tree decomposition is domino if every vertex is in at most $2$ of the bags.
Bodlaender and Engelfriet [ https://link.springer.com/chapter/10.1007/3-540-59071-4_33 ] show that there exists $c(k, \Delta)$ such that every graph with maximum degree at most $\Delta$ and treewidth at most $k$ has a domino tree decomposition of width $c(k, \Delta)$.

Thus, by increasing the size of the bags from $k$ to $c(k, \Delta)$, they can find a new tree decomposition where each vertex is in at most $2$ bags (and clearly the $2$ cannot be lowered).
It seems to me that there is a trade-off between "size of the bags" and "number of bags per vertex" for the class of graphs with bounded degree and treewidth, and my question is if it possible to control the number of "bags per vertex" if we insist on not increasing the bag size.


texts:
CFG here stands for context-free grammar. I understand that:

Deciding whether a CFG $G$ is ambiguous is undecidable.
Deciding whether a CFL $L$ is inherently ambiguous is undecidable.

My question is:

  Is there an algorithm $A$ to remove ambiguity from an ambiguous grammar $G$ of a NOT inherently ambiguous language $L(G)$?

To specify the behavior of $A$ more precisely, $A$ operates on $G$ and:

If $L(G)$ is not inherently ambiguous, $A$ outputs a CFG $G'$ so that $G'$ is not ambiguous and $L(G') = L(G)$.
If $L(G)$ is inherently ambiguous, $A$ outputs something arbitrarily.

Is this problem known to be undecidable, or still open? Any comments and links are welcome. Thanks.


texts: Persistant bag/set with direct access to known elements

texts:
I'm looking for a bag or set data structure that will allow for the following operations:

Add an element to the set, and get a "pointer" to that element.
Add :: mystructure a -> a -> (mystructure a, myptr a)

Remove an element for which I have a "pointer".
Remove :: mystructure a -> myptr a -> mystructure a

Enumerate all the elements in the set.
Enumerate :: mystructure a -> [a]

Note that I don't really care about duplicate values (the values I enter are already unique), nor the order of elements.
A very simple implementation for this structure would be to use a doubly-linked list, with the standard Add returning a pointer to the newly created list node, the standard Remove removing such a node from the list, and Enumerate simply traversing the list.
However, I need the structure to be immutable/persistant (i.e. the Add and Remove operations don't modify the original data structure). Ideally, the operations would still be O(1), like with a doubly-linked list. I think finger trees could be used for this, but I don't know them well.


texts: How exactly does lambda calculus capture the intuitive notion of computability?

texts:
I've been trying to wrap my head around the what, why and how of $\lambda$-calculus but I'm unable to come to grips with "why does it work"?

"Intuitively" I get the computability model of Turing Machines (TM). But this $\lambda$-abstraction just leaves me confounded.

Let's assume, TMs don't exist - then how can one be "intuitively" convinced about $\lambda$-calculus's ability to capture this notion of computability. How does having a bunch of functions for everything and their composobility imply computability? What am I missing here? I read Alonzo Church's paper on that but I'm still confused and looking for a more "dummed down" understanding of the same.


texts: Does Pattern Calculus represent a step forward in languages or are we just going back to LISP?

texts:
Barry Jay in his book makes some bold claims - basically by saying that, at the core of a program, everything is either atomic or composed. Then things can be easily iterated, filtered, updated, just by
navigating this composition relationship.

Is this a new frontier in Computer Science for computer languages - or are we just going back to LISP?


texts: How to simulate sequential registers from causal ones?

texts:
Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For example, we can construct the strongest multi-writer multi-reader atomic $\texttt{read/write}$ registers from the weakest single-writer multi-reader safe ones [1].

Question:

  Is it possible to simulate sequential registers from causal ones in DSM model? And how to, if possible?

I guess the answer is negative. However, I have no idea how to prove/disprove it (Googling does not help on this).

[1] The Art of Multiprocessor Programming. By Maurice Herlihy and Nir Shavit (Chapter 4)


texts: Dynamic and/or practical succinct data structures for triangulations

texts:
Does anybody know of any results on succinct data structures for triangulations that can be constructed efficiently, and preferably also updated efficiently?

Does anybody know of practical implementations of succinct data structures for triangulations?

Is there a good and up-to-date survey that discusses this topic?


texts: Is there a complexity theory analogue of Rice's theorem in computability theory?

texts:
Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable.

I am looking for complexity-theoretic Rice-type theorem that tells us which nontrivial properties of NP sets are intractable.


texts: Shuffling of tokens on a graph using local swaps

texts:
Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.

I want to uniformly shuffle the tokens amongst the graph using only local swaps (i.e. exchange of the tokens between two adjacent nodes) ? Is there a lower bound known for this problem ?

The only idea I had is to use a random walk result, then to see how much swaps I need to "simulate" the effect of random walks transporting tokens on the graph.


texts:
This question did not originate in my research, but I think it's interesting. It is somewhat underspecified. I'd be interested in an example in any particular case.

We have $n$ parties that between them must choose a value $x \in \mathbb{R}$. Each party has a preferred value $p_i$ for $x$, but we must find a compromise. Let's say we want the mean of the preferences.

Now, anybody who has been involved in politics will know that taking the middle way between stated preferences can be gamed by stating a more extreme position than the actual preference, so that the mean lands closer to it. Is there a protocol that lets us find (an approximation to) the mean of the true preferences?

As an analogy, one can take the second-price auction, where everybody is best served by bidding their true valuation.


texts: Is the church-style affine calculus of constructions with unrestricted recursion consistent?

texts:
Suppose we take the church-style calculus of constructions, except with affine functions (variables must occur at most once) and mutual recursive definitions. For example:

Nat =
  ∀ P : *
  ∀ S : Nat -> P
  ∀ Z : P
  P

Zer =
  λ P : *
  λ S : Nat -> P
  λ Z : Nat
  Z

Suc =
  λ x : Nat
  λ P : *
  λ S : Nat -> P
  λ Z : Nat
  S x

two =
  Suc (Suc Zer)

If we built an eager type-checker and asked it to infer Zer, it'd not halt, as Zer's type is infinite:

two : ∀ (P : *) -> ∀ S : (∀ (P : *) -> ∀ S : (∀ (P : *) -> ∀ S : ...

But if we do it lazily, then it'd output:

Zer :
  ∀ P : *
  ∀ S : Nat -> P
  ∀ Z : Nat
  Z

Which is the same as Nat and correct, since Zer is indeed a proof of Nat. One could wonder if it could accept "wrong" proofs such as false : ∀ (P : *) -> P, for some construction of false. The obvious approach, though, seems not to work:

false = (λ (x : ∀ (P : *) -> P) -> x) false

If we had top-level type-annotations (such as false : ∀ (P : *) -> P), the checker would indeed accept this term. But, because of curry-style, the only way to infer the type of false is by inferring the type of false: it'll be stuck in an infinite loop and never output anything.

In other words, it seems that, for the subset of terms that this type-inferencer halts, it behaves as a consistent proof assistant. Of course, it works a bit differently from usual as it has infinite types and whatnot, but, intuitively, it seems to be a functional system for mathematical proofs, since it seems to be unable to accept false or other incorrect proofs. If one is able to prove that this type-checker could never accept false, would it indeed be well suited for mathematical proofs?


texts: Finding the closest subspace to a collection of subspaces

texts:
Suppose we have a collection of linear subspaces $\mathbb{C}$ lying in $\mathbb{R}^d$, such that each $c \in \mathbb{C}$ is of dimension at most $k \leq d$ for a given fixed $k$ and $|\mathbb{C}| = n$. Now we want to find the subspace of dimension at most $k$ closest to each $c \in \mathbb{C}$ under the sin-theta distance. (Note we do not restrict this optimal subspace to be chosen from $\mathbb{C}$).

How can compute this and how much time would this take? This seems simple enough that it might be standard and well-known, perhaps under the right geometric transformation? Even an exponential time algorithm would be very useful - I am more interested in computability rather than optimal efficiency.

To be more precise, define the sin-theta distance for two linear subspaces $L$ and $M$ as follows:
$\sin \theta(L,M) = \max_{x \in L, ||x|| = 1} \min_{y \in M, ||y|| = 1} || x - y||_2$. (This is symmetric if and only if $L$ and $M$ are of equal dimensionality.)

Now if we let $S$ be the space of all subspaces of $\mathbb{R}^d$ of rank at most $k$ our problem reduces to finding $\text{argmin}_{s \in S} \sin \theta (\mathbb{C}, s)$.

Note: Having though about this where all the subspaces are of dimension exactly $k$, the problem simply maps to having a collection $\bar{\mathbb{C}}$ of $n$ points on the surface of the sphere $\mathbb{S}^{d-1}$ and finding the point closest to them. It becomes more tricky where the subspaces in $\mathbb{C}$ are of varying dimensions, as you introduce more degrees of freedom.


texts:
There seems to be much work, for some NP-Hard problems, on developing fast exponential time exact algorithms (i.e., results of the form: Algorithm A solves problem $x$ in O(c^n) time, with c small). There seems to be a fair amount of work along these lines for some NP-hard problems (e.g., Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06) but I haven't been able to find similar work for the set packing problem. There seems to be similar work on some restrictions of the set packing problem (e.g., An $O^{*}(3.523^{k})$ Parameterized Algorithm for 3-Set Packing) but I haven't found any for the general set packing problem.

So my question is: What is the best time complexity for exactly solving the weighted set packing problem where there are $m$ sets drawn from a universe of $n$ elements?

I am also interested in the relationship between the number of sets and the size of the universe. For example, has there been algorithmic work on situations where $m$ is relatively large compared to $n$ (i.e., close to $2^n$)?


texts: Parallel programming languages which look deterministic?

texts:
Are there any programming languages where the system parallelizes the program without any noticeable differences for the programmer?

That is, the programmer writes a linear, deterministic program, without any additional tags or meta-data, and the underlying system parallelizes all of the work.


texts: When was co-NP introduced for the first time?

texts: My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?


texts: quasiP-Natural Property again SIZE($n^e$) for fixed e.

texts:
The Natural Proof theorem says :

If for a fixed $c>1$ $G_k \in SIZE(k^c)$ is $2^{k^\epsilon}$-hard then not exists a $quasiP$-Natural Property that for all $e$ sufficently large is usefull against $SIZE(n^e)$.

The idea in the proof is that if you can distinguish a random function from a function in $SIZE(n^e)$ you can invert a pseudorandom generator. $SIZE(n^e)$ is big enough to compute pseudorandom function generator (based on the pseudorandom string generator $G_k$)

can we say that?

If for any k,n (where if we fix n then we can choose any $k=n^{O(1)}$) $G:\{0,1\}^k\times \{0,1\}^n \rightarrow \{0,1\}$ is a pseudorandom functions genereator (for a sub-exponential adversaries) computable in $SIZE(n^e)$ then not exists a $quasiP$-Natural Property usefull against $SIZE(n^e)$.

I think that it's wrong, because for any fixed $e$ you can find a $quasiP$-Natural Property against $SIZE(n^e)$. But I can't see why


texts: Simple proof that splay trees have the dynamic finger property?

texts:
Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in a splay tree is logarithmic in the magnitude of the rank difference between the queried key and the most-recently-queried key.

It seems like the first proof that splay trees have the dynamic finger property comes from a two-paper series by Cole et al ("On the Dynamic Finger Conjecture for Splay Trees I: Splay Sorting $\log n$-Block Sequences" and "On the Dynamic Finger Conjecture for Splay Trees II: The Proof.") These papers collectively are over eighty pages long and involve fairly complicated, technical proofs. They also seem to be the papers cited by future work in splay trees and related structures when referring to the dynamic finger property.

Has there been any follow-up work in this area that provides a simpler proof of the dynamic finger conjecture?


texts: Expected vs worst-case communication complexity

texts:
In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an $n$-bit string as input; denoted by $X$ for Alice's input, and $Y$ for Bob's input. They need to output "no" if and only if there exists an index $i$ such that $X[i]=Y[i]=1$, otherwise they should output "yes".

The seminal paper An information statistics approach to data stream and communication complexity shows a lower bound of $\Omega(n)$ bits for this problem on the worst case length of the transcript $\Pi$ sent between Alice and Bob. At the end of their argument, the authors show this by using that $|\Pi| \ge H[\Pi]$, where $|\Pi|$ is the transcript length and $H[\Pi]$ is the entropy of the transcript.

I was wondering why the authors didn't show the significantly stronger statement that the expected communication complexity is at least $\Omega(n)$. This holds because even the expected length of the transcript is at least as long as $H[\Pi]$ (by the converse of Shannon's coding theorem, right?).

Actually, all lower bounds that I've seen in communication complexity seem to be shown only for the worst case length.

Is there some reason why the expected communication complexity isn't considered that I'm missing?


texts: Strongly edge-guarding a 3d triangulation

texts:
Let $T$ be a planar triangulation.  It is known that one can guard the faces of $T$ using at most $\lfloor n/3 \rfloor$ edge-guards (Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces). I am trying to obtain a similar upper bound for an extension of this problem, as follows.

Now, let $T$ be a three-dimensional triangulation (a tetrahedralization), and let $S$ be a subset of its edges.  We say that $S$ strongly guards $T$ if, for every tetrahedron in $T$, one of the six edges of that tetrahedron lies in $S$.  Is there a known nontrivial upper bound for the number of edges required to strongly guard all tetrahedra of a tetrahedralization?

Obviously, this problem can be solved via edge-coloring with no monochromatic tetrahedra. Is there any upper bound on the edge chromatic number for three-dimensional triangulations better than $\Delta + 1$? Maybe the assumption that $T$ is a Delaunay triangulation can conduct to a probabilistic bound.


texts: How do you go from insights to formal solutions?

texts:
My question pertains to the problem of translating ideas and insights to the solution (of some problem) into formal notations, thus expressing the answer formally.
In other words, having a bunch of ideas (pertaining to the solution) and transforming them into a well composed, formal solution is a process which I often find difficult.

It might be because (at times) I am not aware of enough literature in the problem domain and so have the problem of not knowing how to express my ideas. However, I would like to know if this is something that can be improved upon and if so, how?


texts:
I have a question, but I don't seem to know enough computer science terminology in order to look up an answer. So I wonder if you guys could help a poor physicist like me.

I would like to know if Boolean circuits are what I would call universal. By this I mean that, given an infinite number of NAND gates and wires, could I solve any problem on any input?

Equivalently (I think) could I simulate any given instance of a universal Turing machine using some particular Boolean circuit? By 'a given instance' I mean that the action table and input tape are set in stone, so we know exactly what process that our Boolean circuit is to simulate before we start wiring all the NAND's together.


texts: Combinatorial discrepancy of the system of all cuts

texts:
This is a variant of this previous question. In the meantime I have learned that what I am really interested in is the discrepancy of the system of all cuts of the complete graph on $n$ vertices. More precisely, my ground set $X$ is the set of all 2-element subsets of $[n]=\{1,\ldots,n\}$, and I am looking at the set system which consists of the sets $S_U=\{\{i,j\}\in X\ :\ i\in U\text{ and }j\not\in U\}$ for all $U\subseteq[n]$. Is there a function $f:X\to\{1,-1\}$ such that

$$\forall U\subseteq[n]\ \left\lvert\sum_{\{i,j\}\in S_U}f(\{i,j\})\right\rvert=O(n)\,?$$

Choosing $f$ at random gives $O(n^{3/2})$ and I think that is also what follows from Spencer's 6 standard deviations theorem. But maybe one can do better by exploiting the cut structure.


texts: Temporal Logic and Access Control Models

texts: What is the best way to describe the semantics of a new access control model?. I heard the temporal logic is the way to go. Is it true?


texts: Is the current best approximation ratio for Vertex Cover problem also a lower bound?

texts:
In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we cannot improve better than 2. However, there is an old paper by Johan Hastad here he shows that by using PCP technique we cannot do better than 7/6=1.16 which is an NP-complete. So, we have a gap between 2 and 7/6 which tells us that whether we have a better approximation algorithm is still open problem. Is that right?! or suppose that Hastad is wrong, then there must be a new analysis about the hardness of vector cover in terms of approximation algorithm.

*As I understand who argues that we cannot do better than the approximation ratio which is 2, the reason is that to give tight example (nontrivial example) which is a complete bipartite graph (K_{n,n}) and since the algorithm choose n number of edges, therefore we have 2n number of vertices, and the vertex cover is only n in this case. Their claim is that if you find 2(n-1) edges, then you have n-1 vertices, and there is a contradiction since we are not covering all vertices which is n. (this is how I understand it so it could be wrong) (Of course there is no polynomial algorithm to find n vertices, and the best approximation algorithm is to find 2n in polynomial time, and they say that it is tight bound) I also read this lecture notes

Also, Is there any new results about the hardness of vertex cover in terms of approximation.


texts: Consequences of faster parameterized integer programming

texts:
Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space.

Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)$ under the assumption the integer programming problem we have had at most $1$ solution?


texts: I recently read Landin's paper "The Next 700 Programming Languages".  But I was a bit confused by ISWIM.  In particular, are functions first-class objects in ISWIM?  It seems not because every function must occur under some name and there is no $\lambda$-like construct in the language to construct an anonymous function.  Landin even explicitly claimed in the first footnote that "a not inappropriate title would have been Church without lambda".  Anybody knows the reason behind this choice?  Is ISWIM less expressive than a language with $\lambda$?


texts: The exponential function over algebraic numbers

texts:
Given an algebraic number $\alpha$,
I am interested in finding an approximation of $\Re(e^\alpha)$
up to a given precision,
where $\Re()$ refers to the real part of the complex number.

Formally, I want to compute a rational number $r$ such that
$$|\Re(e^\alpha)-r|\leq 2^{-n}$$

$\alpha$ is given by a (standard) minimal polynomial.

How fast can we solve this problem?

When $\alpha$ is given as a floating point,
the following reference

R. Brent. Fast multiple-precision evaluation of elementary functions. JACM, 1976.

seems to give an answer.

However,
I am not sure it can be used for the algebraic number $\alpha$.


texts: Exponential time hypothesis for random algorithms

texts:
The exponential time hypothesis asserts that an algorithm for SAT must take time $2^{\Omega(n)}$. If I am reading this right, this refers only to deterministic algorithms.

Is it possible that ETH holds, yet their is a random algorithm in time $2^{o(n)}$? If so, is there any name for the hypothesis that any randomized (say BPP-type) algorithm takes time $2^{\Omega(n)}$ as well?


texts: Closure Properties of Locally Testable Language

texts:
Are locally testable languages closed under complementation? I guess yes, because when I can decide membership by sliding a window of size $k$ over the word and looking if the $k$-length words appearing under the window are in a specified set, then deciding the complement is simply looking if some string under the window is not in the set.

The Wikipedia article states that these languages are not closed under complementation. Contrarily, in the paper Local languages and the Berry-Sethi algorithm by J. Berstel & Jean Eric Pin the authors prove that these languages are closed under union, concatenation and Kleene-Star, as opposed to the Wikipedia article. so the Wikipedia information does not seem very trustworthy. Following the proofs in the paper, if I have a local automaton, then the automaton in which the final- and ordinary states are exchanged is still local I think and accepts the complement of the original language. So I think these languages should be closed under complement. Am I right?


texts: Maximal correlation vs correlation coefficient when one RV is Gaussian

texts:
Last week I asked a question on MOF (see here), but I got no reply. So I am asking my question here.

Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have density with respect to Lebesgue measure)  with joint distribution $P_{XY}$. The maximal correlation $\rho_m(X;Y)$ between $X$ and $Y$ is defined as
$$\rho_m(X;Y):=\sup_{f,g} \rho(f(X); g(Y)),$$ where $\rho(\cdot; \cdot)$ denotes the correlation coefficient (aka Pearson correlation coefficient). Rényi suggested the following simpler representation for maximal correlation:
$$\rho_m(X;Y):=\sup_{f,g}\mathbb{E}[f(X)g(Y)],$$ where the maximization is taken over real-valued functions $f$ and $g$ such that $\mathbb{E}[f(X)]=\mathbb{E}[g(Y)]=0$ and $\mathbb{E}[f^2(X)]=\mathbb{E}[g^2(Y)]=1$. A single-function characterization of maximal correlation correlation was given by by Renyi as follows:
$$\rho^2_m(X;Y)=\max_{f}\mathbb{E}[(\mathbb{E}[f(X)|Y])^2],$$ where $f$ satisfies the above conditions as well. One can easily see that for any arbitrary random variables $X$ and $Y$, $0\leq\rho_m(X;Y)\leq 1$ where 0 is achieved iff $X$ and $Y$ are independent and 1 is achieved iff there exists a pair of functions $f$ and $g$ such that $f(X)=g(Y)$ almost surely.

It is a well-known fact that for jointly Gaussian $(X,Y)$, we have $\rho_m^2(X; Y)=\rho^2(X; Y)$.

Suppose now that only $Y$ is Gaussian. I would like to know a necessary and sufficient condition on $P_{XY}$ such that $\rho_m^2(X; Y)=\rho^2(X; Y)$. In particular, I am interested to see if this statement is correct: if $\rho_m^2(X;Y)$ is close to $\rho^2(X;Y)$, then $X$ is close to a Gaussian random variable.


texts: Potentially equal complexity classes without known contradictory relativizations

texts:
What are some examples of pairs of complexity classes $A$ and $B$ such that

we do not know whether $A=B$, and
we do not know contradictory relativizations either (i.e., we do not know oracles $P$ and $Q$ such that $A^P = B^P$ and $A^Q \ne B^Q$)?

To phrase the question another way, what are some exceptions to the heuristic that if can't figure out contradictory relativizations then it is easy to resolve the equality question outright?


texts: Algorithm Design for only Mutual Information Sharing

texts:
Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their exchange their actual bit strings... how can they do this? Keep in mind that even once they both hold the AND of their two bit strings, they should still not be able to calculate the other person's string exactly (unless of course one of their strings was all 1s).

I asked this on Stack Overflow and got yelled at to move it here. Not really sure how to tag it either if anyone knows what it would fit under better please feel free to edit. I know that I have seen something similar before in some sort of mutual key system/voting system but I couldn't remember where. It has to be something like make a private random key, xor it and use that somehow... but I couldn't work out the details. Any clever encryption design people out there?


texts: Is there a good notion of non-termination and halting proofs in type theory?

texts:
Constructive type theory with its basic interpretation under the curry howard correspondence consists only of total, computable functions. In the literature, some has been said on using "computational type theory" in order to represent non-termination in functional programs, yet in the papers I have come across, this does not seem to be the major motivation for the theory (For example Benton mentions non-determinism, continuations, and exceptions, without going into much detail on non-termination), so I have yet to find a paper giving a robust interpretation of non-termination using computational type theory.

Specifically, what I am looking for is a way that given a type representing a possibly non terminating computation of type $A$, $T(A)$, there should be some notion of proofs that $x : T(A)$ terminates of type $H(x)$, such that given $x:T(A)$ and $p:H(x)$, we can construct a term $\tilde x : A$.

My motivation for this is, I'd like to eventually be able to more formally relate notions in computational complexity theory to constructive type theory. Specifically, I am interested in what power as a formal theory constructive types gain with access to a halting oracle, and in order to do so, I of course need to actually have a formal notion of possible non-termination, and proofs of halting to go along with it inside a type-theoretic framework.


texts:
I am wondering if the following problem has a name, or any results related to it.

Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,v \in V$, $w(u,v) \in [-1,1]$. The problem is to find a subset of vertices that maximizes the sum of the weights of the edges adjacent to them:
$$\max_{S \subseteq V} \sum_{(u,v) : u \in S\ \textrm{or}\ v\in S} w(u,v)$$
 Note that I am counting edges both that are inside the subset and that are outside the subset, which is what distinguishes this problem from max-cut. However, even if both $u$ and $v$ are in $S$, I only want to count the edge $(u,v)$ once (rather than twice), which is what distinguishes the objective from merely being the sum of the degrees.

Note that the problem is trivial if all edge weights are non-negative -- simply take the whole graph!


texts:
This was an assignment problem in a course on analytics combinatorics that I had taken this semester. Here is the problem:

Let $\mathbf{F}$ be the set of boolean functions, $f: \{0,1\}^n \rightarrow \{0,1\}$, and let $U_k(f)$ denote the $k^{th}$ Gowers norm of $f$, which is defined as

$$U_k(f) = (\mathbb{E}_{x,y_1,y_2,\ldots,y_k \in \mathbb{F}_2^n} (-1)^{\Delta_{y_1,y_2 \ldots y_k} f(x)})^\frac{1}{2^k} \text.$$

Here $\Delta$ is the discrete derivative : $\Delta_{y} {f(x)} = f(x) + f(x+y)$.
Give an estimate of the quantity $\mathbb{E}_{f \in \mathbf{F}} U_k(f)$, for $1 \le k \le 3$.

Intuitively, to me, it seems that this quantity should be vanishingly small (not lower-bounded by a constant which is independent of $n$) since the above expression is the Gowers norm of a random function, which cannot have a good correlation with low-degree polynomials.
Is my line of thought is correct, and can someone can give a quantitative estimate of the above expression for $k = 1,2,3$.


texts: Finding an injective mapping between two sets that maximizes a similarity function

texts:
I have a practical application where I need to map elements from one set (A) to another (B).

Sets A and B can both have arbitrary numbers of elements
Elements from A and B need to be paired up so that every element can only be used once.
Elements can be left unpaired as well.
A similarity matrix can be calculated: how well any element from A maps to any element from B.
The goal is to find a mapping that maximizes the sum of these similarity scores.

Brute-forcing all the options gives factorial complexity which gets out of hand fast. However, for many examples a simple greedy approach seems to work fine - iteratively add the edge which has the maximum score in the similarity matrix, making sure that the restrictions still apply.

Is there any guarantee that this greedy approach will give me the maximized result? I haven't been able to come up with a good counter-example but that doesn't mean they don't exist.


texts: Is there a reduction from a 0-1 knapsack problem to the unbounded problem?

texts:
As we know, an unbounded knapsack problem could be described as:

$\max \sum_{i=1}^nc_1x_i$

s.t. $\sum_{i=1}^na_ix_i\le b$

$x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$

And for an 0-1 knapsack problem, we have an additional restriction:

$x_i\in\{0,1\},i=1,\cdots,n$

However, I would like to know whether there exists a reduction from the 0-1 knapsack problem to the unbounded knapsack problem?

I have thought over this problem, but I could not imagine whether something could be done in the unbounded problem in order to simulate the effect as the constraint $x_i\in\{0,1\}$ in a 0-1 knapsack problem.

Thanks!


texts: Run Dijkstra's algorithm twice to detect negative-weight cycles?

texts:
Dijkstra's algo (for finding single-source shortest path) assumes that once a vertex has been chosen for expansion (aka exploration), its shortest path has been found. This can only be true if there are no negative-weight cycles reachable from the source.

Therefore, I was thinking that in order to detect a negative-weight cycle, we could run Dijkstra's algorithm a 2nd time, but instead of initialising the vertex distances to -infinity, we use the ones found by the 1st iteration. If at any point during this 2nd iteration, there is a distance update, the assumption above is violated, therefore there is a negative weight cycle.

There must be a mistake in my reasoning, because if this works, it would have same time complexity as Dijkstra's algo, which would be better than the Bellman-Ford algorithm, which is the textbook algorithm for solving the single-source shortest-path in potential presence of negative weight cycles.

Is my mistake that a 2nd iteration may lead to no distance updates even in the presence of a negative weight cycle? If so, could someone provide such an example?


texts:
It's formulated by extending threshold graphs.  Given a threshold graph $(C,I)$ where $C$ is the clique and $I$ is the independent set, my extension is as follows: Each vertex $v\in I$ can be replaced by a new clique $K_v$ such that the vertices of $K_v$ have the same neighbors of $v$.

I guess this should have been studied, but it is hard to search such thing in graphclasses.org.


texts:
We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.

I'm interested in the approximability of two problems, or in general, what is known about them.

Given a number $k'\in[m]$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k'$ such that all of the sets in $\mathcal{S'}$ are disjoint.
Given a number $k''\in[n]$, is there a set $\mathcal{S''} \subseteq \mathcal{S}$ such that $|\cup_{s\in\mathcal{S''}}s|\geq k''$ (i.e. it covers at least $k$ elements) and the sets in $\mathcal{S''}$ are disjoint.

The problems are NP-complete:
The first has a straight forward reduction from 3-dimensional matching, and the second answers exact cover directly.

The first problem seems $APX-hard$ if we use the hardness results from k-dimensional matching.
Both problems can be viewed as a special case of Independent Set over the graph whose vertices are $\mathcal{S}$ and there's an edge $(s_i,s_j)$ iff $s_i\cap s_j$ isn't empty ( (2) has vertices weights $w(s_i)=|s_i|$), but I don't see any easy reduction from $IS$ to either that doesn't require exponential size blowup.

What can we say about the approximability of the two problems? maximal k-dimensional matching is known to be approximable within a factor of $\frac{k}{2}$, does it have an analogue for the first problem?

Both of these problems seems natural, so I'm tagging this question as a reference request, assuming they have been looked at under different name, rings a bell to anyone?


texts: Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

texts:
I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032

1) "A further problem that can be shown to be #P-hard is that of counting the number of Hamiltonian subgraphs of an arbitrary directed graph." (I think he means subgraphs as sets of edges, not induced by nodes.)

2) "Given a complete graph on n nodes and arbitrary
probabilities assigned to each edge, the probability that the graph has a Hamiltonian circuit (or some other NP-complete substructure) is easily seen to be #P-complete."

Given $1)$, it's easy to see that $2)$ problem is $\sharp P$ hard$^*$, but it's unclear to me why this problem is in $\sharp P$. Valiant mentions that $1)$ is likely not in $\sharp P$, so maybe this is a typo. $2)$ appears to perhaps even strictly harder than $1)$.

Can anyone give me a hint on how to think about $1)$?

(*In the following way: For any given graph $G$, embed $G$ into a complete graph. On that complete graph, set the probabilities for edges not in the embedding to zero, and for edges in the embedding to $1/2$. Then each subgraph of $G$ has probability $(1/2)^{E(G)}$ of appearing, so the probability that the random subgraph has a HC can be used to easily determine the number of subgraphs with Hamiltonian cycles. This shows that (given 1) ) it is $\sharp P$ hard to compute those probabilities.)


texts: NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

texts:
Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the size of every part is the same, i.e., $k$. The goal is to maxmize the sum of the shared neighbors of every part, which can be difined as:
\begin{gather}
    \sum_{i=1}^m SN_{i}\\
    s.t. \quad\qquad SN_{i} = \cap_{v_i \in P_i} Nei(v_i)\\
    |P_i| = k\\
    \qquad \sum_{i=1}^m |P_i| = nk
\end{gather}

where $SN_{i}$ is the shared neighbours of the nodes in part $P_i$. For convenience, we regard that the node is the neighbour of itself.

I think the problem is np-hard. In my view, we can construct a specific graph which contains n k-clique. We then think about it as a clique-cover problem. However, I think the solution is a little strange... How should we prove it?

Thanks in advance!!!


texts:
There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.

However, all algorithms for parsing arbitrary CFGs I know have a worst-case space usage of $\Omega(n^2)$ (although, admittedly, I have no idea what the space usage of that matrix multiplication algorithm is). I was wondering whether there are any algorithms that improve upon this space usage (so disregarding the time bound).

The question popped up into my mind after mentally linking $CSG = NDSPACE(n) \subseteq DSPACE(n^2)$ with the $\Omega(n^2)$ space bound on all the CFG parsing algorithms I knew. It's probably of no practical interest, but merely something I'd be interested in knowing.


texts: Given a type system T, and a type $A$ in that type system, is there an (effective) surjection from $\mathbb{N}$ onto the set of terms of that type?

texts:
I assume that in hoping for an effective bijection, we run into undecidability issues, but intuitively, it seems like there should at least be a surjection from $\mathbb{N}$ to the terms of any type, since well-typed terms of type theories are essentially finite trees, the set of which has cardinality $\aleph_0$. So, given a type theory* $T$ and a (non-empty) type $A$ in that type theory, can we always construct such a surjection? If possible, I would like to get a reference describing such an algorithm, if anyone has explicitly described it.

* I suppose I should specify formally what I mean by type theory, but I am not aware of any name for "type theories in general," so what I mean is a system consisting of a finite number of axioms (or axiom schemas), and rules, where we say $t : T$ if any only if there is a deduction (which is a finite tree whose leaves are axioms, and whose edges are rules) with conclusion $t:T$. So, examples would be simple type theory, homotopy type theory, one of the various forms of Martin-Lof type theory, etc...

This question is related to mine, but what I am asking is more general.


texts: Checking if a polynomial factors into linear factors

texts:
Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given
by an arithmetic circuit $C$ of size $s$. Given $C$ as the input,
is there a deterministic algorithm to check whether all the irreducible
factors of $f$ in $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ are linear
forms? On a related note, given a linear form $l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$,
can we check deterministically whether $l$ is factor of $f$. Of
course, we want running time to be polynomial in both the cases.
By size, we mean the total bit size. Also, it can be assumed that degree of $f$ is polynomial in $n$.


texts: Hungarian Search and min net-cost-length paths

texts:
Consider the Hungarian Search algorithm for max/min weighted bipartite matching. Let G be a bipartite graph weighted by $w:E\rightarrow\mathbb{R}$ and let $M$ be a matching in $G$, let $S$ be a subset of edges of $G$. The net-cost of $S$ w.r.t. $M$ is defined as

$w_M(S):=\sum_{e\in S\setminus M} w(e) -\sum_{e\in S\cap M} w(e)$.

How would you prove or justify the claim that the Hungarian Search, with classical $\pm \delta$ dual-adjustments, augments $M$ by growing augmenting paths of minimum net-cost? Maybe we can think about the problem of finding an augmenting path as a max-flow augmenting step, with matched edges in one direction and unmatched undges the other way... ?


texts: Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

texts:
The $q$-Dimensional $p$-Matching is defined as follows:

Given disjoint universes $U_1,\ldots,U_q$, think
of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element
from each universe $U_i$.

Now, given a family ${\cal S}\subseteq U_1\times \ldots\times U_q$ and a parameter $k\in\mathbb{N}$,
determine if there exists a subfamily of $k$ pairwise-disjoint sets in ${\cal S}$.

We abbreviate by $\#q$-Dimensional $p$-Matching (or $\#(q,p)$-matching in short) the counting version of the problem, asking how many matchings exist in $\cal S$.

In their famous paper from 2004, Flum and Grohe have developed the $\#W$ hierarchy, the counting equivalent of the $W$ hierarchy for parameterized problem.

Among their results in the paper, they have shown that counting the number of $k$-paths is $\#W[1]$-complete, and conjectured that counting the number of matchings of size $k$ in a bipartite graph is hard as well.

I'm unaware of any results addressing this conjecture, but was wondering about even a weaker result:

  Is #$q$-Dimensional $p$-Matching (counting the number of instances in a $(q,p)$-matching instace) $\#W[1]$-complete, where the parameter is $p+q$?

Such result would be weaker than the FG's conjuncture, as counting bipartite matchings is the same as $\#(2,p)$-matching.

Related result:

Recent result by Bläser and Curticapean shows that weighted counting of $k$-matching in bipartite graphs is $\#W[1]$-complete.


texts: Maximum Crossing number of topological graph

texts:
The crossing number of a graph $G$ is defined as the least number of crossings introduced when $G$ is drawn as a topological graph in the plane.

Is there anything known about the maximum number of crossings which can be introduced by drawing $G$ as a topological graph in the plane?


texts:
Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding until reaching a Manhattan distance $L/2$ from it, according to the following rules:

At each step $n=0,\dots,L/2-1$, visit all the vertices at Manhattan distance $n$ from the origin. If the current vertex is connected to the tree, then with probability $p$ connect to it its two neighboring vertices at Manhattan distance $n+1$ from the origin, and with probability $1-p$ connect only one of the two. Skip adding edges that create a cycle (i.e., an edge to a neighbor that has already been added to the tree).

Question: how does the order of the tree grown by this process scale with $L$ depending on the choice of $p$?

It is clear that limiting cases are $O(L)$ and $O(L^2)$, but I am wondering whether there is also some sort of intermediate "fractal" dimension.


texts: SAT variant with almost disjoint clauses

texts:
I'm wondering whether the following SAT variant is NP-complete or polynomial.
The formula given in input has n*m variables, and it has two parts.

A part with the n positive clauses:
$$(x_{1,1} \lor \dots \lor x_{1,m}) \land \\\dots\\(x_{n,1} \lor \dots \lor x_{n,m})$$

And a part with negative clauses with two variables:
$$ \neg x_{i,j} \lor \neg x_{k,l} $$ where $x_{i,j}$ and $x_{k,l}$ are part of the n*m variables mentioned above.

Thank you for the help


texts: An alternative proof of hypercontractivity of the Becker-Bonami operator

texts:
The Becker-Bonami operator $T_p$ on a function $f(x) : \{0,1\}^d \to \mathbb{R}$ is defined as follows. Let $\nu(x)$ be a perturbation of $x$ so that every bit remains the same with probability $p$ or is chosen uniformly at random from $\{0,1 \}$ with probability $1-p$. Then $T_p(f(x)) = E_{y =\nu(x)} f(y)$ . It is well known, by a famous inductive proof:

\begin{equation}||T_{\sqrt{p-1}} f ||_2 \leq ||f||_p \end{equation}

I am curious first, as to what other proofs are known besides the traditional inductive one I see in most lecture notes on  boolean functions?

(Note: It would be especially nice if there was a proof that leverages the fact that $T_p$ attenuates the coefficients of the parity basis functions. i.e, if $\chi_S: \{0,1\}^d \to \{-1,1\}$ is the function such that $\chi_S(x) = -1^{|x \cap S|}$, it is known that $T_p(\chi_S(x)) = p^{|S|} \chi_S(x)$.)


texts: Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

texts:
I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ .

Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph of $P$?
(Polynomial in the dimension, the number of equations, and the representation of $b$. I can assume that the number of equations is polynomial in the dimension.)

Update: I think I was able to show that this is NP-hard, see my answer that explains the argument. (And by $NP$-hard, I mean that an polynomial time algorithm would prove $RP = NP$... not sure what the correct terminology is here.)

Update 2: There is a 2 line proof of $NP$-hardness (given the right combinatorial polytope) and I was able to find it an article by Khachiyan. See answer for description and link. :-D

An equivalent problem:

In the comments Peter Shor pointed out that that this question is equivalent to the question of whether we can uniformly sample from the vertices of a given polytope. (I think the equivalence goes like this: In one direction, we can go from a polytope $P$ with a vertex $v$ to the vertex figure at $v$, $P/v$, and sampling the vertices of $P/v$ is equivalent to sampling the neighbors of $v$ on $P$. In the other direction, we can go from a polytope $P$ to a polytope $Q$ of one higher dimension by adding a cone with apex $v$ and base $P$. Then sampling the neighbors of $v$ in $Q$ is equivalent to sampling the vertices of $P$.)

This formulation of the question has been asked before: https://mathoverflow.net/questions/319930/sampling-uniformly-from-the-vertices-of-a-polytope


texts: Do any quantum algorithms improve on classical SAT?

texts:
Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT )

For comparison, using Grover's algorithm on a quantum computer would look for and provide a solution in $1.414^n$, randomized. (This may still require some knowledge of how many solutions there may or may not be, I'm not sure how necessary those bounds still are.) This is clearly significantly worse. Are there are any quantum algorithms that do better than the best classical algorithms (or at least -- almost as good?)

Of course the classical algorithms could be used on a quantum computer assuming sufficient working space; I'm wondering about inherently quantum algorithms.


texts: The most applicable areas in Theoretical Computer Science

texts:
I just wanted to know areas in common to Theoretical Computer Science which have a lot of carrer prospects outside of academia. I specifically wanted to know because I am interested in almost all areas of TCS equally, so why not choose a field for PhD which is more vibrant in terms of carrer choice.
Inspired by this question  MathOverflow

My guesses are
1) Information Theory, all major communication companies and companies which need storage
2) Cryptography (Specifically protocols and construction of new/better codes)
3) Algorithmic Game Theory (Companies like Google are investing a lot in it)
4) Formal Verification(But i think it is a very niche area focussed in Europe)


texts: Resources on Cryptographic Applications of Expander Graphs

texts:
I want to read papers on cryptography like
How to Recycle Random Bits
or Security Preserving Ampliﬁcation of Hardness. They use random walks on expander graphs.

I need a short introduction to the subject of expander graphs and random walks on them. I prefer one that has cryptography in mind.

PS: In another post, Dai Le introduced the paper Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson as an excellent paper on expander graphs. Unfortunately, it is too long (123 pages) to be useful for me.


texts: Why is intuitionistic negation nonconstructive?

texts:
Can someone simply describe why intuitionistic negation is

not constructive and why intuitionistic proof is constructive?

    in intuitionistic logic the notion of falsity has a 'subordinate' status,

    i.e. intuitionistic logic essentially rests upon a certain disparity between verification

    and falsification in favor of verification. Unlike intuitionistic truth, intuitionistic

    falsity is a non-constructive notion representing simply a non-truth of a sentence"

That is a part of paper entitle "Dual Intuitionistic Logic and a Variety of Negations:

The Logic of Scientific Research" by Yaroslav Shramko.


texts: representing code path as graph walks.. a provable graph walk?

texts:
I am looking into some security analysis of arbitrary code which is represented as a graph

Are there any papers on whcih graphs walks are valid code paths ?
Or a provable graph walk which is shorter than a graph walk itself ?

Can anyone direct to any specific terms or papers i should be looking into ?


texts: graph isomorphism given a partial isomorphism

texts:
Is there an approach to graph isomorphism considering that we are already given a partial isomorphism ?
In particular, it would be interesting to have conditions on this partial isomorphism that makes the problem polynomial.

This question arises from automata theory, where one approach to testing equivalence of two NFAs on alphabet $A$ is to compute their syntactic semigroups $M_1,M_2$ (of exponential size) together with functions $h_1:A\to M_1$, $h_2: A\to M_2$. Testing semigroup isomorphism is hard in the general case, but here we can do it polynomially, because $h_1,h_2$ already give us a partial isomorphism for a set of generators, which is enough.

For graphs, an obvious sufficent condition for such a partial isomorphism to make the problem polynomial would be "containing a covering set" (in the sense each edge contains a vertex in it) . Maybe there are more subtle conditions that would still work ?


texts: Can we approximate the number of words accepted by an NFA?

texts:
Let $M$ be an acyclic NFA.
Since $M$ is acyclic, $L(M)$ is finite.
In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete.
The second answer for that question provides a counting algorithm, but only works for unambiguous NFAs (where every word is accepted by at most a single path).

Given an NFA $M$, can we approximate $|L(M)|$ in polynomial time?

As automata is a highly studied subject, I was surprised that I couldn't find anything about this, so if someone knows of a reference it'll be great :).


texts: Conditional Dependencies in Compiler Semantic Analysis Passes

texts:
Imagine that we have a been given an Excel spreadsheet with three columns, labeled COND, X and Y.

COND = TRUE or FALSE (user input)
X = if(COND == TRUE) then 0 else Y
Y = if(COND == TRUE) then X else 1;

These formulas evaluate perfectly fine in Excel, and Excel does not generate a Circular Dependency error.

I am writing a compiler that tries to convert these Excel formulas to C code. In my compiler, these formulas do generate a circular dependency error. The issue is that (naïvely) the expression of X depends on Y and the expression for Y depends on X and my compiler is unable to logically continue.

Excel is able to accomplish this feat because it is a lazy, interpreted language. Excel will just lazily evaluate the formulas at run-time (with user inputs), and since no circular dependency occurs at run-time Excel has no problem evaluating such logic.

Unfortunately, I need to convert these formulas to a compiled language (not an interpreted one). The actual formulas, in the actual spreadsheets, have more complicated dependencies between multiple cells/variables (involving up to over half a dozen different cells). This means that my compiler has to perform some kind of sophisticated static, semantic analysis of the formulas and be smart enough to detect that there are no circular references if we "look inside" the conditional branches. The compiler would then have to generate the following C code from the above Excel formulas:

bool COND;
int X, Y;
if(COND) { X = 0; Y = X; } else { Y = 1; X = Y; }

Notice that the order of the assignment instructions is different in each branch of the if-statement in C.

My question is, is there any established algorithm or literature on compilers that explains how to implement this type of analysis in a compiler? Do functional programming language compilers have to solve this problem?


texts: Hardness of 3-dimensional matching variant

texts:
I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose a matching $M \subseteq E$ of maximum size.

I would like to instead choose $M$ from the set $E \cup \{(x,w) \bigm| \exists z: (x,w,z) \in E \vee \exists y: (x,y,w) \in E\}$. So for each triple in $E$, assume that choosing a pair with the first and second elements or a pair with the first and third elements to be part of $M$ would also be acceptable. (Note that a pair with the second and third elements is not allowed.) The question is if there a matching $M$ that covers every element in $X \cup Y \cup Z$ exactly once.

I was wondering whether this problem is still hard. The Garey & Johnson proof of NP-hardness of 3d matching seems to break down; if $M$ is chosen as specified above, the gadget for the variable doesn't work anymore.


texts: Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

texts:
An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$-center instance) using at most $\alpha \cdot k$ centers.

My question is: Given that finding a $(1,1)$bi-criteria approximation (which is basically just the optimal solution to the $k$-center problem, known to be $NP$-hard) is $NP$-hard, is it also true that finding a $(c, 1)$ bi-criteria approximation is $NP$-hard, where $c$ is a positive constant?

I've found that it is possible to have a $(\log k, 1)$ approximation for $k$-center, but not seen any negative results for a $(c, 1)$ bi-criteria approximation. I would appreciate if I can get pointers to a reference that I may have missed, or an outline of the proof sketch if its something trivial.


texts: Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?

texts:
Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate nearest neighbor problem in $d$-dimensional Euclidean space in with query time $O(dn^{1/c^2 + o(1)})$ and space $O(dn + n^{1+ 1/c^2 + o(1)})$. The results are based on Locality Sensitive Hashing, i.e. all the points are hashed and a given query point $q$ will have a high probability of collision with a point $p$ if $p$ and $q$ are close to each other.

Is it possible to first preprocess with some dimension reduction technique and then apply the same Andoni / Indyk algorithm?

For example, we could apply a Johnson-Lindenstrauss Transform. Apparently the JL flattening theorem states that "any $n$ points
in Euclidean space can be embedded into $O(\epsilon^{−2} \log n)$ dimensions so that all pairwise Euclidean
distances are preserved up to $1± \epsilon$."

Thus, could we first preprocess by embedding the points into $O(\epsilon^{−2} \log n)$ dimensions and thus improve the space and query time bounds given by Andoni and Indyk?

I can't find any concrete technical reasons why this shouldn't work, but it also seems like if this does work, then I should be able to find a reference documenting it.

 More detail:

I see now that Andoni and Indyk are already performing a dimension reduction. From the paragraph above section 3.2:
"To reduce U, we project $ℜ^d$ to a lower-dimensional
space $ℜ^t$ via a random dimensionality reduction. The parameter
$t$ is $o(log n)$."

At first this made me think that another dimension reduction would be redundant.

However, there is still a factor of $d$ in the query time! This is because the LSH based query algorithm requires $O(n^\rho)$ hashing function evaluations, and each hash function (when hashing a $d$-dimensional point) requires $O(d)$ operations (according to IM98).

Therefore, if we want to reduce the dependence on $d$ in the query time while using a LSH based approach, we need to speed up the evaluation of the hash function. One way to do this would be to preprocess all the points, projecting them into $O(\epsilon^{−2} \log n)$ dimensions. The Andoni/Indyk algorithm will make another projection into $R^t$, where $t = o(\log n)$. However, when running the query algorithm, we make 1 projection of the query point into $e = \epsilon^{−2} \log n$ dimensions first, and so each of the $O(n^\rho)$ hash function evaluations is only evaluated on $e$-dimensional points instead of $d$ dimensional points. This should speed up the query time to $O(e\cdot n^\rho) = O(\epsilon^{−2} \log n \cdot n^\rho) < O(dn^\rho) $ when $d$ is large.


texts: How to play the following game? (placing balls into bins)

texts:
Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$.

The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\quad{} \Sigma_{i=1}^\ell y_i = \ell\cdot n.$$

Next, there are $\ell$ bins such that bin $i$ contains $x_i$ blue balls.
Given a random permutation $\sigma:[\ell]\to[\ell]$, $y_{i}$ is the number of red balls in bin $\sigma(i)$.

From every non-empty bin, a random ball is chosen uniformly, and we win the game if all sampled balls are red.

  How can we select $x,y$ to maximize our winning odds?

If we pick $x_1,\ldots,x_\ell=n/\ell$ and $y_1,\ldots,y_\ell=n$, we have that in each bin a red ball will be sampled with probability $1-1/(\ell+1)$ and the chance of getting only red balls would be $(1-1/(\ell+1))^{\ell}\approx 1/e$.

As GMB answered, it's possible to improve this by setting $x_1=\ldots=x_{\ell-1}=0$ and $x_\ell=y_1=\ldots=y_\ell=n$, and getting a success probablity of 1/2.

Is this optimal?

Formulated as a math expression:

  What is $\max_{x,y\mid \Sigma_{i=1}^\ell x_i = n, \Sigma_{i=1}^\ell y_i = \ell\cdot n} \quad{} \mathbb E_\sigma\; \left[\prod_{i=1}^\ell \frac{y_{\sigma^{-1}(i)}}{y_{\sigma^{-1}(i)}+x_i}\right]$?