texts: Universal Approximation - Are ReLUs discriminatory?

texts:
In Cybenko's elegant proof of the Universal Approximation Theorem (UAT) he proves that single hidden layer neural networks (with linear output layer) are universal approximators whenever their activation functions are (what he calls) discriminatory. He then shows that bounded measureable sigmoidal functions are discriminatory, completing the proof. In particular, continuous sigmoidal functions work as well.

Later Leshno et al. proves that locally bounded piecewise continuous (l.b.p.c.) activation functions yield the UAT if and only if they are nonpolynomial.

My Question(s):

What kinds of functions are discriminatory? Polynomials certainly aren't (Leshno et al.) and continuous sigmoids are (Cybenko).  Are ReLUs discriminatory?

Together, the above results imply that for l.b.p.c. functions, that discriminatory implies non-polynomial. Is the converse true?


texts: Merging Graph Edges to form a 2 color-able Graph (with weight constraints)?

texts:
Given an undirected graph $G$. Each vertex has a weight 1.

We define shrinking an edge as merging and replacing 2 adjacent vertices $(A, B)$ with a new vertex $C$ such that all the vertices that were connected to $A$ or $B$ are now connected to $C$. Moreover the weight of the new vertex $C$ is sum of weight of $A$ and $B$.

Question: Determine if for a given graph $G$, we can merge vertices such that in the new Graph:

Each vertex has a weight 2.
The new graph is 2 color-able.

How do we approach this problem?


texts: Back-propagation for computing derivative of certain line integral

texts:
Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following path integral:

$$C_i({\bf x}, {\bf w}) = {\bf x}_i \int_0^1\frac{\partial F}{\partial {\bf x}_i}(\alpha {\bf x})d\alpha $$

Basically, one can think of $C_i({\bf x}, {\bf w})$ as the "contribution" of the $i$-th dimension to the final output --  by integrating along a line from $\bf 0$ to $\bf x$.

My question is whether there are known methods (references, etc.) that give "backpropagation-like" algorithms for computing:

$$\frac{\partial C_i({\bf x}, {\bf w})}{\partial {\bf w}_i}$$

That is, basically I want to understand the first order information of the contribution of the $i$-th dimension w.r.t. ${\bf w}_i$.

Thanks in advance for any insight.


texts: Approximate counting problem capturing BQP

texts:
In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say).

Is there a similar problem for BQP? This comment by Ken Regan suggests such a problem

You can reduce a BPP question to approximating a single #P function, but with BQP what you get is the difference of two #P functions, call them $f$ and $g$. Approximating $f$ and $g$ separately does not help you approximate $f - g$ when $f - g$ is near zero!

BQP does give you a little help: When the answer to the BQP question on an input $x$ is yes, you get that $f(x) - g(x)$ is close to the square root of $2^m$, where the counting predicates defining $f$ and $g$ have m binary variables after you substitute for $x$. (There are no absolute-value bars; “magically” you always get $f(x) > g(x)$. Under common representations of quantum circuits for BQP, $m$ becomes the number of Hadamard gates.) When the answer is no, the difference is close to 0.

Can you precisely formulate such a problem as close as possible to BQP? I am hoping for something like: given black-box access to functions $f,g$ mapping $X$ to $Y$, with the promise that ..., estimate $f-g$ to within $\varepsilon$.


texts:
I have a problem with the following statement :

Every combinatorial embedding is equivalent to one with $\lambda(T) = 1$ on a spanning tree of G

What does this mean ?

OK in a spanning tree there isn't a cycle, so the signature of every edge is equal to $1$ but what is the sense of this statement?


texts: Is there a useful notion of being “approximately computable”

texts:
It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f_n(x)$ such that $$\lim_{n\to\infty} f_n(x)=\chi_S(x)$$ Under this definition, I believe that the halting set is approximately computable and that a set is computable if and only if it is uniformly approximately computable.

I haven’t been able to find anything online about this notion, or any other notion, of approximately computable. This doesn’t seem particularly novel, and I’m surprised I can’t find any resources on it. Has an idea of “approximately computable sets” been studied? Do they all collapse to merely computable for a reason I haven’t seen?

By diagonalization, there are set that aren’t approximately computable under my definition. It seems likely that any reasonable definition of “approximately computable” would similarly only apply to $\aleph_0$-many sunsets of $P(\mathbb N)$. Assuming that there is a reasonable definition, is there a criteria (perhaps a level of the arithmetic hierarchy) where all sets above that level are not approximately computable?

I am thinking about this because I’ve been reading about combinatorial game theory recently, and about games with only uncomputable winning strategies. It seems plausible that a computer might be able to play a game extremely close to optimally in some sense, perhaps that they play the closest to optimally of all programs of size $\leq n$. Sets that don’t have a computable approximation seem like candidates for building games where computers can only play the game poorly. If anyone has references for investigations of this idea, I would be very interested in that as well.


texts: Practical algorithm for testing whether an edge is Delaunay

texts:
I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$.

My assumed definition of a Delaunay edge is: An edge is Delaunay, iff there exists a circumsphere of its endpoints not containing any other vertex inside it.

I would like to know practical approaches/algorithms for such Delaunay-edge test.

UPDATE: Answer to a question here models Delaunay-edge criteria as a linear programming feasibility problem. Concisely, it searches for a vector, scalar tuple $(v,c)$ such that for a set of vertices $P$(formed by transforming original points $(x,y,z)$ in 3D space to $(x,y,z,x^2+y^2+z^2)$ in 4D space) and endpoints of a  Delaunay edge candidate $(p_i,p_j)\in P$,

$v.p_a \geq c$

$v.p_b=c$

where $p_a\in P-\{p_i,p_j\}$ and $p_b\in\{p_i,p_j\}$

and it recommends using ellipsoid method, but Wiki section on this method describes it as numerically unstable beyond 2 dimensions. Is there any other practical yet numerically stable(in three dimensions) linear programming approach for performing Delaunay edge test?

P.S.: I have already asked this question on ComputerScience SE but did not receive any relevant response.


texts: Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

texts:
Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes.

  Which $NP$-hard graph problems are $W[1]$-Hard on directed graphs, but fixed parameter tractable on undirected graphs?

  Which $NP$-hard graph problems are $W[1]$-Hard on weighted graphs, but fixed parameter tractable on unweighted graphs?

OK, so we have problems which becomes harder on the directed version. What about weights? Can they make parameterized problem harder?


texts:
Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that increase the hardness of problems in $NPI$ from an intermediate complexity to full $NP$-completeness. I'm interested in other $NP$-complete variants of $NPI$ problems. Ideally, a recent survey paper of $NP$-complete variants of $NPI$ problems would be the best answer?

EDIT July 1st, 2012 The bounty will be awarded to the person that lists the maximum number of such problems.


texts: Solving semidefinite programs in polynomial time

texts:
We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (exponential) number of variables/constraints can also be solved in polynomial time, provided we can design a polynomial time separation oracle for them.

What about semidefinite programs (SDP)? What classes of SDPs can be solved exactly in polynomial time? When an SDP can't be solved exactly, can we always design an FPTAS/PTAS for solving it? What are the technical conditions under which this can be done? Can we solve an SDP with exponential number of variables/constraints in polynomial time, if we can design a polynomial time separation oracle for it?

Can we solve the SDPs that occur in combinatorial optimization problems (MAX-CUT, graph coloring) efficiently? If we can solve only within a $1+\epsilon$ factor, will it not have an effect on constant factor approximation algorithms (like 0.878 for Goemans-Williamson MAX-CUT algorithm)?

Any good reference on this will be highly appreciated.


texts:
Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to" like phrases to jump back or forward to another step, thus avoiding explicit loops). I mean something like this:

  Step: Do ...
  Step: If ..., go back to step 1. Else, do ...
  Do ...

This is in contrast to pseudocode that is written more in the style of source code of some structured programming language, like this. With this approach, one tends to avoid "go to" statements, which are considered harmful in programming. I wonder to what extent the criticism of go to statements applies also to the presentation of algorithms in theoretical computer science (outside of programming). I think if one uses something like Hoare logic to prove the correctness of some algorithm, it seems avoiding go to statements is the thing to do.

On the other side, I feel that the enumerative way of describing an algorithm has the advantage that whole algorithm is neatly split into a few chunks, which makes it often conceptually easier for me to read the algorithm, whereas the source code approach often contains many nested loops with many indentations making the algorithm hard to read.

Now I wonder, and this is my big question: Which of the two approaches (enumerative vs source code approach) do you think is more appropriate and suitable in research of theoretical computer science? Which style should be used in research articles? What are the advantages and disadvantages of the two approaches?


texts: Connecting cells by line and column permutations in a finite grid

texts:
I'd like to know whether the following simple problem has been studied before and if any solution is known.

Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said to be (locally) connected if their coordinates differ by at most one (i.e., if drawn as squares, they share at least one corner point).

Now, one can try to connect the crumbs (their set as a whole) by permutating the lines and the columns of the grid. In other words, the goal is to come up with a permutation of the lines and a permutation of the columns so that any two crumbs in the resulting grid are connected by a chain of (locally) connected crumbs.

Question: is there always a solution?

I don't quite know how to attack it. For lack of a better idea, I have written a raw program that looks for solutions by brute force (it generates the permutations at random and checks whether the resulting grid has its crumbs connected). The program has so far always found solutions on smallish (10x10 or 7x14) grids, and larger grids are clearly out of reach of its simplistic strategy (it would take too long to stumble at random across a solution).

Here is an example of a grid solved by the program:

Initial grid (crumbs are denoted by X's, empty cells by dots):

   0 1 2 3 4 5 6 7 8 9
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Solution:

   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Naturally, the problem can readily be generalized to any dimension d > 2. I suppose other generalizations could be considered.

Thanks in advance,

Yann David


texts: Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs

texts:
Orlin's algorithm is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and the node sets of the graph $G(V, E)$ in question.

If the graph $G(V = V_1 \cup V_2, E)$ is known to be bipartite (with $V_1$ and $V_2$ denoting the "left" and "right" node sets), can one compute the minimum cost maximum flow any faster? Here the flow is between an additional source that is connected to the nodes in $V_1$ and an additional sink that is connected to the nodes in $V_2$.

I'm also interested to hear about algorithms that do not have better time complexity, but perform well in practice.

You can assume that all capacities and costs are non-negative integers. There can be both limited-capacity and unlimited-capacity edges in the graph. Also, assume that both the maximum non-infinite capacity $c$, and the maximum edge cost $w$ is small; i.e. one can consider both as $O(1)$ terms for complexity purposes.

Thanks!

Edit: My current-best solution is to use a minimum cost augmentation algorithm, which solves the problem in $O(|E| \; F \log |V|)$ time, where $F$ is the value of the maximum flow. Since $F$ is bounded by $c \;|V|$ (which is $O(|V|)$ under our assumptions), this approach results in an overall time complexity of $O(|E| \; |V| \; \log |V|)$. Is it possible to beat this?


texts: Expected travel time for regularly departing trains

texts:
First a simple mathematical question: Suppose $n$ train lines service a train station. Each of the $i \in \{1, 2, ... n\}$ lines has trains departing every $x_{i}$ minutes and takes $y_{i}$ minutes to arrive at the destination. If the rider takes the first train on any line, what is the expected journey time (waiting + travel)?

Secondly: it may be the case that taking the first train on any line is not optimal. (For example, if one of the train lines takes $y_{j} = 30$ minutes to arrive at the next stop while others take 20 minutes, and the waiting times are such that it doesn't make sense to take the slower train anyway.) Unfortunately I'm at a total loss for how to compute this algorithmically. Mathematically it's minimizing the expectation over all subsets of $\{1, 2, ... n\}$, but I need to actually compute it so any tips would be helpful.


texts: Approximation algorithms for the maximum $2$-independence set problem

texts:
I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct vertices in $I$ is more than $2$. In other words $I$ is $2$-independent in $G$ if and only if $I$ is independent in $G^2$, the square of $G$. $2$-independent sets are also sometimes called $2$-packings, packings or closed neighborhood packings.

The maximum $2$-independent set problems ask for the $2$-independence set with maximum cardinality in a given graphs $G$. In [1] it is proved that for any $\epsilon > 0$ it can't be approximated with a better than $O(n^{1/2-\epsilon})$ multiplicative factor (this problem is called maximum distance-$3$ independent set in this paper). However, I did not find any positive results about its approximation. Is there any $O(\sqrt{n})$-approximation (or worse) algorithm? Or, maybe, there are better inapproximability results?

Also, any results about characterization of the squares of all graphs may help (let us denote the class of squares of all graphs as $\mathcal{G}^{(2)}$). For example, it may occur that $\mathcal{G}^{(2)}$ is a subclass of some class where maximum independent set problem admits some approximation. Or, conversely, it may be a superclass of some class with no approximation better than $n^{1-\epsilon}$. Unfortunately, I am not aware of any such results.

[1] Eto, Hiroshi and Guo, Fengrui and Miyano, Eiji. Distance-$d$ Independent Set Problems for Bipartite and Chordal Graphs // Combinatorial Optimization and Applications, Vol. 7402 (2012), pages 234-244.


texts: Computational Complexity of Computer Vision Problems

texts:
What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard?

In most cases this will boil down to determining the computational complexity of the corresponding machine learning problem. Although generally the machine learning problem is approached statistically rather than combinatorially, I guess this is still pertinent.

Could you also point me to some literature which answers (or tries to answer) this question?


texts: Assistance in showing computational equivalence between software and hardware computing systems

texts:
I'm in the middle of a discussion regarding the equivalence of software and hardware computing systems, and I would like some comment. Any arguments and/or documentation (supporting or dissenting) would be appreciated.

My position is that the implementation of a computational processing system can be separated from the act of logical computation, i.e. the agent performing logical processing (i.e., computation) can be distinctly separated from the process.  My line of reasoning is more observational at the moment. For example,

A PID controller may be implementing in pure (analog or digital) hardware or software.
It is now routine to compile a C program into VHDL, then write the resulting "hardware" configuration into an FPGA.
Computational systems have been constructed from fluidics and other mechanical systems.
Computations systems have been constructed from molecular biology (i.e., DNA computing.)

From these observations, one might conclude that hardware computational systems, from simple collections of basic gates to FPGAs, are functionally equivalent to software programs.

The question is not entirely academic: the US FDA places dramatically different validation and verification (V&V) requirements on a medical device depending upon its use of hardware or software for logical operations.  Software systems are subject to a number of standards and regulations, and the resulting testing procedure and documentation burden is heavy.  On the other hand, simple hardware-only implementations, such as a PID controller, are subject to much less federal regulation.

As a result, a bias is introduced into the design process.  A system designer is inherently pushed toward a hardware solution - simply due to the regulatory burden. The assertion that "computational hardware and software do the fundamental same things" is rendered heretical.  It implies that hardware solutions are challenged with the issues of software development, and that hardware solutions should be subject to the same V&V processes applied to software.  (Note that the US FDA is slowly coming around to this viewpoint - some of their more recent guidelines sound like early software guidelines.)

Can someone suggest a theoretical strategy for establishing this equivalence or a logical argument for divorcing the process of computation from the agent of computation?


texts:
What should I read to understand this problem?

  The power of small-depth quantum
  circuits. Is $BQP = BPP^{BQNC}$? In other
  words, can the "quantum" part of any
  quantum algorithm be compressed to
  polylog(n) depth, provided we're
  willing to do polynomial-time
  classical postprocessing? (This is
  known to be true for Shor's
  algorithm.) If so, building a
  general-purpose quantum computer would
  be much easier than is generally
  believed! Incidentally, it's not hard
  to give an oracle separation between
  $BQP$ and $BPP^{BQNC}$, but the question is
  whether there's any concrete function
  "instantiating" such an oracle. --Scott Aaronson
  http://www.scottaaronson.com/writings/qchallenge.html


texts: Are there hypothesis classes that are hard to learn but easy to test?

texts:
Let $H$ be a binary hypothesis class, it is easy to see that if $H$ is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or $\epsilon$-far testable).

My question is:

  Fixed a distribution, is there any known hypothesis class that is hard (say NP-hard) to properly learn (to avoid the problem to be trivial, we assume the class is statistically  PAC-learnable) under this specific distribution, but easy (say within polynomial time) to test under the same distribution?

As far as I know most of the results for proving hardness of learning are reduced to the hardness of testing (i.e. decide a gap version of the risk minimization is hard).


texts: Can the Lasserre relaxation be defined over the reals?

texts:
If one wants to say minimize a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ on its domain  then a degree$-d$ Lasserre relaxation of it would be to solve the problem of $\min \mathbb{E}_\mu [f(x)]$ over degree$-d$ pseudo-distributions $\mu$.

Can this relaxed problem be now completely defined over the reals with no need to anymore look at the Boolean hypercube?

It seems to me that there are a few choices here about how to define this relaxation.

(A)

Is the relaxation now well defined if $f$ is lifted in anyway to a function $f : \mathbb{R}^n \rightarrow \mathbb{R}$ such that on the Boolean hypercube it matches the original value?

Next we have in principle $2$ options about how to define $\mu$,

(B1)

$\mu$ can be defined as any function from $\mathbb{R}^n \rightarrow \mathbb{R}$ such (a) $ \sum_{x \in \{-1,1\}^n} \mu(x) =1$ and (b) when any function $g$ is taken from the real $SOS_d$ cone we would have $ \sum_{x \in \{-1,1\}^n} \mu(x)g(x) \geq 0$.

(B2)

Or is it necessary that $\mu$ and $g$ be satisfying the above properties but $\mu$ maps from $ \{-1,1\}^n \rightarrow \mathbb{R}$ and $g$ be a member of the $SOS_d$ cone of polynomials each of which is also a map, $ \{-1,1\}^n \rightarrow \mathbb{R}$?

(..the "degree" of a polynomial as in the real $SOS_d$ cone may not match the degree of its representative in the $SOS_d$ cone of functions on the Boolean hypercube and there is no unique way to go the otherway..)

I think the $\mu$s defined by conditions B1 will automatically satisfy the conditions in B2 and vice-verse.  But there could be an effect of this choice depending on how one resolved the options in A.
Also I think the option B1 makes most sense since otherwise the relaxed problem is probably isnt a standard SDP that can be run in polynomial time.


texts: How to write a negative review for a conference paper?

texts:
This is related to the general question of "How do I referee a paper?". I am reviewing a paper for a conference, and this paper should be rejected, because it is not significant enough for publication and has flaws in some of its technical details. The paper is not wrong, but the ways in which it is right are not very interesting. How do I write a negative review in such a settings? More importantly, how do I do this as a non-senior researcher?

As an example, they make part of their argument through numerics, but I can prove the same result analytically. The analytic treatment is longer than what I can include in a review. I know the author's emails (the review process is not blind both ways), should I email them? This is a conference, so there is no time for revisions, will they be mad at me for rejecting their paper? Should I email them before or after they receive the reviews?

The paper is also sparsely cited, and does not connect strongly to existing literature. I am familiar with many aspects of the relevant literature, how detailed should I make my recommendations on further reading/references?

To extract the general questions:

How does a junior researcher write a negative review?
What should you do if you have specific technical comments/improvements that are too long for a standard review?


texts: VC dimension for balanced binary decision trees

texts:
What is the VC dimension of all balanced binary decision tree of
depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?


texts: Communication complexity of random functions with limited independence

texts:
Let $X_0, \ldots, X_{2^n-1}$ be $k$-wise independent random $0/1$ variables over a sample space $\Omega$ and $Prob \left[ X_i = 1 \right] = p$ for every $i$ and some $0 < p < 1$. Let assume $n$ is dividable by 2 and $f(x,y): \lbrace 0,1 \rbrace^{n/2} \times \lbrace 0,1 \rbrace^{n/2} \rightarrow \lbrace 0,1 \rbrace$ is defined by $f(x,y) = X_{\vert xy \vert}$ where $xy$ is the concatenation of $x$ and $y$ and $\vert z \vert := \sum 2^i \cdot z_i$. I'm interested in the 1-way 2-party (deterministic) communication complexity of $f$ such that both players know the random sample (out of $\Omega$) which is chosen at the beginning of the protocol, i.e. both players know the current value of every $X_i$. Of course, it is also ok to know something about the expected number of communicated bits.

Motivation: At first I think this is an interesting problem :) However, I'm currently dealing with such random functions and want to show some lower bounds for my computational model using communication complexity.


texts: Reconstructing a colored grid with vertical and horizontal shifts

texts:
Consider the following simple problem (puzzle): given

a $N \times N$ $c$-colored grid $G$
a $N \times N$ $c$-colored target grid $G_T$
a number $m$ represented in unary

Can we transform $G$ into $G_T$ using at most $m$ horizontal or vertical shifts.. In a shift an entire column or row is shifted by one cell (columns vertically; rows horizontally) and every shift is circular: the cell that exits from a border  re-enters the grid on the opposite side.

  Q1. Has this game/problem a name?
  Q2. Is it NP-complete?
  Q3. What about the variants in which $c$ is fixed (e.g. $c=2$) or the grids are $N \times k$ with $k$-fixed?

Update:

We can also consider the simpler variant (I called it "Block Shift Puzzle") in which:

$c = 2$, i.e. the empty grid (color 1) contains some colored boxes (color 2);
the target configuration is simply a square area in the upper-left part of the grid, i.e. the boxes must be "packed" in the upper-left part of the grid;
and the columns/rows can only be shifted in one direction (upward/leftward).

  Q4. Is this simpler variant polynomial-time solvable?

I implemented this variant in Javascript and it can be played online here (even small grids seem not so easy to solve).


texts: Is the finite inverse semigroup isomorphism problem GI-complete? Here the finite inverse semigroups are assumed to be given by their multiplication tables.


texts: Why are NPI problems not all of the same complexity?

texts: How does one look at a problem and reason that it is likely NP-Intermediate as opposed to NP-Complete?  It is often pretty simple to look at a problem and tell whether it is likely NP-Complete or not but it appears to me to be much harder to tell whether a problem is NP-Intermediate as the line seems to be quite thin between the two classes.  Basically what I am asking is why would a problem that can be verified in polynomial time (if at all) but not solved in polynomial time (as long as P dosn't equal NP) not be polynomial time reducible to each other.  Also, is there some way to show a problem is NP-Intermediate similar to how a problem is shown to be NP-Hard, such as reduction or some other technique?  Any links or textbooks that would help me understand the class of NP-Intermediate would be appreciated as well.


texts:
There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.

A priori, we expect the minimizing face should be high dimensional for various reasons, including that the objective function being minimized is the maximum of many of the constraints :

Minimize $\epsilon$ subject to $f_i(\bar x) \leq \epsilon < 0$ with $f_i$ linear and $x_i > 0$ for all $i$ and $\sum_i x_i = 1$.

We'd never obtain any centrality-like property form the simplex algorithm of course.  Do any of the usual interior point algorithms exhibit such properties though?  Do any even guarantee they'll avoid vertices or lower dimensional faces whenever possible?

In fact, I'm probably content with a easy quadratic program that finds the midpoint of the entire polytope since centrality matters more than minimality, just vaguely curious if other linear programming algorithms offer relevant properties.

Update : I've reduced the underlying problem to a simple constrained minimization problem solvable with Lagrange multipliers, but the question above remains interesting anyways.


texts: Are aspects of the 20 questions game ambitious enough for graduate research?

texts:
I am finishing a masters program this year and I'm interested in doing a Ph.D. in the field of Artificial Intelligence.

I have an idea I've been tinkering with for a while, but some people have told me that it is not ambitious enough for Ph.D.-level research. I'm not sure if this is because the TCS community already knows all there is to know about it or because I have failed to express myself adequately (bad sales pitch). Based on what I could find online, not all that much has been done.

So, I am going to describe what I thought about doing and I would like to ask if you think this is a promising start idea and if it has the potential to lead to something graduate-level worthy.

I want to research efficient and reliable ways to implement a distributed system that can identify entities based on data collected from its users. To give a concrete example of this, I am going to use the 20 questions game.

Existing implementations of this can be found at http://www.20q.net/ and http://www.akinator.com/ however these are closed: no official details whatsoever on how they do it exist anywhere that I can find (subquestion: in general, if someone does something but does not publish how it's done, how worthy is (much) later research that explains how it can be done?).

There are also no details on the required processing power (performance can easily be seen to be very good, although also hard to quantify exactly - is this because they're smart about whatever it is they do or because they run the site on supercomputers?) and the reliability (how often they guess right, under what circumstances etc.) of these systems.

Of course, one can say "use neural networks", "use bayesian classifiers", "use KNN", "use this special form of decision trees: ____", but how well will these work (is it that obvious that they even will?), how exactly they need to be implemented to work efficiently and reliably, how they can be implemented in a distributed manner that is accesible and cheap (for example, if they could be implemented efficiently using widely-used relational databases such as MySQL, that would be great), how they can be tailored to learn from user inputs and probably other factors seem to be up for research.

The problem is more complicated than it seems I feel, because players can also lie, and you'll notice akinator will guess right in many of those cases as well - so it's not so easy as using a decision tree. As for the other approaches, many questions arise as well, such as scalability, reliability and exact mechanics that are provably best (or at least better than most others) for this specific problem.

At first, based on what I read online, the problem did not seem too complicated, but when I thought and learned more about what people were suggesting, I quickly started to find various flaws. Then I started to write code and noticed even more potential shortcomings, so now I feel that the problem has a lot more that can be learned from it than trivial implementations of various existing concepts.

Does this have any potential or should I start looking someplace else entirely?


texts:
This is about how effectively we can express an algorithm at hand. I need this for my undergraduate teaching.

I understand there is no such thing as standard way of writing a pseudo code. Different authors follow different conventions.

It would be helpful if people here point out, the way they follow and think the best one.

Is there any book that deals with this in a good detail?


texts: Practical applications of the Theory of Equality with Uninterpreted Functions (EUF)

texts:
In these days I'm reading the book Decision Procedures - An Algorithmic Point of View. Chapters 3 and 4 deal with the Theory of Equality with Uninterpreted Functions (EUF). The authors give 3 toy examples on using EUF to solve real-world problems: proving equivalence of programs, proving equivalence of circuits, validating the translation performed by a compiler. I'm looking for further practical applications of EUF, possibly non-toy examples.

  Question(s)

  Did anyone use EUF to successfully solve real-world problems different than those indicated above?
  Did anyone use EUF to successfully solve the above problems, but in a real world setting rather than a toy setting?
  Did anyone use EUF to model (parts of) big, complex systems? What did you model? What did you manage to prove about such systems? Do you have any success story to tell?

Pointers to papers are greatly appreciated. I've already posted this question on ai.stackexchange.com, without receiving any answer (moreover, unfortunately that site was closed during its beta for insufficient activity).


texts: Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs

texts:
Nisan's answer to this question shows the Impossiblity of efficient sampling from random non-Hamiltonian graphs (unless $NP=coNP$). I am interested in the implications of this conjecture.

  Does the Impossibility of efficient sampling from random non-Hamiltonian graphs imply that $NP \ne coNP$?

I am also interested in other complexity implications.

EDIT July 4: My intuition is that efficient sampling from random non-Hamiltonian graphs is possible if and only if $NP=coNP$. It hints a probabilistic characterization of class $NP$ (possibly connected to PCP theorem).

I would be very interested in published works about (preferably efficient) sampling from random non-Hamiltonian graphs (and any possible connection to PCP theorem).


texts: What can you do with a moving knife besides cutting a cake?

texts:
In the fair cake-cutting, two different computational models are used:

A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies;
A continuous model, in which one or more "knives" move continuously over the cake under certain restrictions, until a player shouts "stop".

The continuous model is strictly stronger: there are problems that can be solved easily in the continuous model, but cannot be solved in finite time in the discrete model, e.g, envy-free cake-cutting with connected pieces.

So I wonder what other problems, besides cake-cutting, can benefit from a "moving knife" or a similar continuous model?

For example, is there a continuous variant of a Turing machine, that can easily solve problems that are unsolvable for a discrete Turing machine?


texts: The decision procedure of theory of closed real field is in NP-hard?

texts: The decision procedure of theory of closed real field  refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers


texts: Do natural generalizations of P versus NP exist?

texts:
Accepted Answer

Scott Aaronson's answer has been "accepted" (mainly because it's the only answer!)

One-sentence summary of answer  Plausibly natural generalizations of the P versus NP question are not obviously easier to resolve than P versus NP itself.

One obstruction to a general answer  The original question assumed that every complexity class A associates "naturally" to a nondeterministic generalization NA — however a general complexity class A can be defined in so many ways, that the class-map N$\colon\,$A$\,\to\,$NA cannot (apparently) be readily given a completely general and manifestly natural specification.

However …  dkuper's comment (below) provides a link to a talk by by Christos Kapoutsis (LIAFA), titled Minicomplexity, that describes a research strategy along the lines indicated.

For further discussion, a recommended resource is the Dick Lipton/Ken Regan Gödel's Lost Letter and P=NP essay titled We Believe A Lot, But Can Prove Little.

The question finally asked

  The question  What trait shared by every complexity class A ⊂ P that is richer than NTIME(n ln n), acts to obstruct proofs of A ⊂ NA?

This question was motivated by Scott Aaronson's recent weblog comments (see below), and the complexity-theoretic richness of this question has subsequently been illuminated by comments/answers/essays by Robin Kathari, Scott Aaronson, Ryan Williams, Dick Lipton and Ken Regan, and previous TCS StackExchange questions.

  Observations  (1) For all known complexity classes A ⊂ P that are sufficiently large as to include NTIME(n ln n) ⊂ A, the problem A $\overset{?}{\subset}$ NA is open, and (2) the reason(s) for this near-universal complexity-theoretic obstruction are not presently well-understood.

Like many folks, I had long appreciated the immense difficulty of proving P ⊂ NP, but had not previously appreciated that proving A ⊂ NA is an open problem for (essentially) all computational complexity classes.

The question originally asked

On his weblog Shtetl Optimized, Scott Aaronson issued the following TCS challenge:

  The Shtetl Optimized TCS Challenge   If you believe P vs. NP is undecidable, then you need to answer:

  The Shtetl Optimized TCS Question   Why does whatever intuition tells you that [P vs NP is undecidable] not also tell you that the P versus EXP, NL versus PSPACE, MAEXP versus P/poly, TC0 versus AC0, and NEXP versus ACC questions are similarly undecidable?

  (In case you don’t know, those are five pairs of complexity classes that have been proved different from each other, sometimes using very sophisticated ideas.)

Answers to the following specific question will be accepted:

  Q1 (TCS literature question)   Do any known complexity classes A and B provably satisfy A ⊂ B and NA ⊇ B, for NA the natural non-deterministic extension of A?

Supposing that the answer to Q1 is "yes", an explanation is desired of how it happens that the strict inclusion A ⊂ B has been proved, while the (superficially similar) strict inclusion P ⊂ NP is hard to prove.

Alternatively, if the answer to Q1 is "no", one further question is asked:

  Q2 (The Extended Shtetl Optimized TCS Question)   Are complexity-class inclusions of the general form A ⊂ B and NA ⊇ B provable — in ZFC or any finite extension of ZFC — for any "natural" complexity classes whatsoever? (if "yes" construct examples; if "no" prove the obstruction).

PostScript   Appreciation and thanks are extended to TCS StackExchange for sustaining this wonderfully inspiring and helpful mathematical community, and to Scott Aaronson for sustaining his admirable weblog Shtetl Optimized!


texts: Cover set of Boolean formulas with conjunctions

texts:
I want to cover a set of Boolean formulas (over the same variables) with disjunctive conjunctions. Here's an example with two formulas $p_1$ and $p_2$ over the set of variables $\{A, B, X, Y\}$:

I want to partition the solution space into conjunctions and represent all formulas as disjunctions of such conjunctions:

In the left example, the solution space is partitioned into five conjunctions. Both $p_1$ and $p_2$ can be represented as disjunctions of these conjunctions, as shown. Note that not every conjunction appears in a disjunction. However, it is still needed to partition the solution space.

I am looking for such a partition with the minimal number of conjunctions. So although the partition on the right also admits a representation as disjunctions, it consists of six conjunctions and is therefore not minimal.

Is this a solved problem? I am interested in both structural and algorithmic results.


texts: Is there any parallel algorithms or approximation algorithms for 3SAT?


texts: Correspondence between Computability & Learnability Theory

texts: Could someone give a brief explanation of the computability & learnability theory & the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are welcome) Thank You.


texts: Current tightest bounds for critical 3-SAT density

texts:
I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or more, they are almost surely unsatisfiable.
(Here $\epsilon$ is any small constant and $n$ is the number of variables.)
If the number is $(\alpha - \epsilon) n$ or less, they are almost surely satisfiable.

The thesis Belief propagation algorithms for constraint satisfaction problems  by Elitza Nikolaeva Maneva challenges the problem from the angle of belief propagation known in information theory. On page 13, it says $3.52<\alpha<4.51$ if $\alpha$ exists.

What are the best known bounds for $\alpha$?


texts: Is finding whether k different perfect matchings exist in a bipartite graph co-NP?

texts:
Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is an edge in the graph) and where every node occurs in this set exactly once.

I am given an n x n bipartite graph, and I am trying to find out if the problem of finding whether k different perfect matchings exist in the graph, where k= polynomial(n), is a co-NP problem.

Work done so far

To initially simplify the problem, I believe that if k=2, then this is a co-NP problem. I think this is true, because the bipartite graph does not have 2 different perfect matchings, if there does not exist an exchange of neighbors between 2 nodes. I define the exchange of neighbors as the following. Let G1 be the first set in the graph, and G2 be the second set in the graph. The exchange occurs when we have a subset of G1, S1={A,B}, and a second subset of G2, S2={X,Y}, where {(A,X),(A,Y),(B,X),(B,Y)} belongs to the set of edges E. I call it exchange because if A was initially matched with X, and B with Y, then when A gets paired with Y, and B with X, A and B have exchanged their neighbors. I believe that the only way to have 2 different perfect matchings is to have at least one such exchange.

Now, we can verify that no such exchange exist, in polynomial time. This is true since getting all the possible subsets S1 and S2 has O(n^4) time complexity. This because we need (n choose 2) from G1 multiplied by (n choose 2) from G2, and this gives us an upper bound of n^4.


texts:
I am trying to understand better the proof that
the language $K=\{a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} is not context-free. (see It only looks like a homework problem…), and the use of Ogden's lemma as well.

I must say I have some difficulty reading @Frank Weinberg's proof as given, so I tried to write one myself. I feel it is more intuitive to follow, but is it correct ? One is easily mixed up in quantifiers with Ogden's lemma. I am not pretending my version is fundamentally different from the previous proof (assuming mine is correct). It may seem a bit longer, but I believe only because I am giving more details. My main problem with the previous proof is that I do not see why one has to define the infinite set of possible exponents.

The starting idea is the same. Given the marked-pumping length $p$. choose a word $a^i b^p c^k$ and mark all and only the $b$'s. Now, in the pumping triple $xyz$, $x$ and $z$ must contain each only one kind of symbol. Otherwise, pumping would immediately create alternation of symbols and get us out of the language, thus proving it is not CF. Condition 1 of the lemma says that at least one of them must contain $b$'s, since only $b$'s are marked. Thus $a$ or $c$ or both do not get pumped, and no more than $p$ $b$'s get pumped (condition 2 of the lemma).
We want to pump exactly enough $b$'s to match either the $a$'s or the $c$'s.

Let $h$ be the product of the first $p$ positive integer. We choose $i=p+h$ and $k=p+2h$.
The word $ a^{p+h} b^p c^{p+2h}$ is in $K$. We apply Ogden's lemma, marking the $b$'s as said above. Assume that for this word, it is the $a$'s that do not get pumped, and that the pumping length for $b$'s is $n$. Since $n\leq p$, $n$ divides $h$, and by applying the pump $h/n$ times we get a word of the form $a^{p+h} b^{p+h} c^k$ which is not in the language $K$. The reasonning is similar if it is the $c$'s that are not pumped. Hence the language K is not CF.

The question is : do I err, and why ?  Why does  Weinberg's proof require showing that there is an infinite set of exponents? Other comments are welcome too.


texts: About generalized planar graphs and generalized outerplanar graphs

texts:
Any planar, respectively, outerplanar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$,
respectively, $|E'|\le 2|V'|-3$, for every subgraph $G'=(V',E')$ of $G$.
Also, (outer-)planar graphs can be recognized in polynomial time.

What is known about graphs $G=(V,E)$ such that $|E'|\le 3|V'|-6$
(resp. $|E'|\le 2|V'|-3$) for every subgraph $G'=(V',E')$ of $G$? Is it possible to
recognize them in polynomial time?

Edit (after Eppstein's nice answer): Any planar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$ for every subgraph $G'=(V',E')$ of $G$ with at least three vertices $|V'|\ge 3$. So, "generalized planar graphs" would be those satisfying this property, and recognizing them in polynomial time seems to be an (interesting) open question.


texts: parameterized algorithms for geometric set cover

texts:
Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover?

It is known that set cover problem is $W[2]$ hard when parametrized by the solution size? There might be some advantages when the sets are defined by geometric objects.


texts: Critical Assignments vs Read-Once Branching Programs - Reference Request

texts:
Straight to the point:
I'm looking for a reference for the fact that the complexity of a read-once branching program solving the search problem for an unsatisfiable formula $F$ is at least the complexity of a read-once branching program solving the search problem restricted to critical assignments for $F$.

Definitions and formal statement are below.

Search problem:
Let $F=C_1\,\wedge\, C_2\, \wedge\, ... \,\wedge\, C_m$ be an unsatisfiable formula. The search problem for $F$ is defined as follows: Given an assingment $\sigma:X\rightarrow \{0,1\}$, return a clause that is falsified by $\sigma$.

So, formally, the search problem can be described by a relation
$R_F \subseteq \{0,1\}^n \times \{C_1,..,C_m\}$, such that
$(\sigma,C_i)\in R_F$ if and only if $\sigma$ falsifies $C_i$.

Critical Assignments:
Now a critical assignment is an assignment $\sigma$ that satisfies all clauses but one. Therefore, given such an assignment $\sigma$, there is
a unique $C_i$ such that $(\sigma,C_i)\in R_F$. As a consequence, if
$S$ is the set of critical assignments, then $Q_F = R_F \cap S\times \{C_1,...,C_m\}$ is a function.

Read Once Branching Program associated with $F$: A read-once branching program is a directed acyclic multigraph with a distinguished source vertex, of in-degree $0$ and distinguished sink vertices of out-degree $0$. Each non-sink vertex is labeled with a variable, and each sink-vertex is labeled with a clause.
Each non-sink vertex labeled with a variable $x$ has two out-edges, one labeled with assignment $x=0$ and the other with assignment $x=1$.
Such branching program is read-once if for each path $p$, each variable labels at most one vertex of $p$.

Each assignment $\sigma$ naturally defines a path from the source of the branching program to the a sink vertex. This is the path whose edge assignments are consistent with $\sigma$. The clause associated with $\sigma$ is the clause $C(\sigma)$ labeling the sink-vertex corresponding to $\sigma$.

Let $R\subseteq R_F$. We say that such a branching programs solves
$R$ if for each assignment $\sigma$, the pair $(\sigma,C(\sigma))\in R$.

Wanted Reference:

Statement: The minimum size of a branching program solving $R_F$ is at least the minimum size of a branching program solving $Q_F$.

In other words the complexity of a read-once branching program solving the search problem for $F$ is at least the complexity of a read-once branching program solving he search problem restricted to critical assignments.

I would like to have a reference for the statement above. I have seen similar statements mentioned in several places. But I can't remember of a concrete reference clearly stating the fact above.

Question: Which article / book has a proof for the statement above? Or at least a proof for a similar statement?


texts: Can choice or sequential execution be expressed with other basic operators of the pi calculus?

texts:
There are several definitions of what basic operators constitute the pi calculus  (see papers from R. Milner, B.Pierce, J.Wing).

The common basic operators ($C$) are:

the parallel composition
reading from a named channel
writing to a named channel
restriction to get a new named channel
replication to get an infinite number of parallel copies of a process
the inert process that does nothing.

Sometimes, there is additionally one of the following two operator mentioned as basic operator:

the sequential operator for sequential execution;
the summation operator to choose between processes.

Is $C$ together with the sequential operator equivalent to $C$ with the summation operator? Are they even equivalent to $C$ without any further operator? Why (not)?


texts: Can Merlin convince Arthur about a certain sum?

texts:
Merlin, who has unbounded computational resources, wants to convince Arthur that
$$m|\sum_{p\le N,\ p\text{ prime}}p^k$$
for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$  Computing this sum in the straightforward way (modular exponentiation and addition) takes time $N(\log\log N)^{2+o(1)}$ with FFT-based multiplication.*  But Arthur can only perform $O(N)$ operations.

(Notation, for compatibility with earlier versions of this question: Let the sum equal $m\alpha$; then the question is whether $\alpha$ is an integer.)

Can Merlin convince Arthur with a string of length $O(N)$?  If not, can he convince Arthur with an interactive proof (total communication, of course, must be $O(N)$)?  If so, could Merlin use a string of length $o(N)$? Could Arthur use $o(N)$ time?

Arthur has no access to nondeterminism or other special tools (quantum methods, oracles other than Merlin, etc.) but has $O(N)$ space if needed.  Of course Arthur need not compute the sum directly, he merely needs to be convinced that a given triple (N, m, k) makes the equation true or false.

Note that with $k=0$ it is possible to compute the sum in time $O(N^{1/2+\varepsilon})$ using the Lagarias-Odlyzko method.  For $k>0$ the sum is superlinear and so cannot be stored directly (without, e.g., modular reduction) but it's not clear whether a fast algorithm exists.

I would also be interested in any algorithm to calculate the sum (modular or otherwise) other than by direct powering and addition.

* $N/\log N$ numbers to calculate, time $\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$ for each calculation.


texts: What are the best current lower bounds on 3SAT?

texts: What are the best current lower bounds for time and circuit depth for 3SAT?


texts: Finding mapping between two spatial representations of the same objects

texts:
I have two matrices $U$ and $V$.  $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that $VA = \hat{U}$, where $\hat{U} = \underset{X}{\arg \min}$ $m(X, U)$ for some metric $m$.

Is there a closed form or iterative solution to this problem?


texts: What graph properties only consider neighbours of a node in their calculations?

texts: I'm looking for graph properties which only consider neighbours of a node and do not go beyond that. For example, nodes degree only considers neighbours or clustering coefficient also consider only neighbours, but shortest path considers all nodes in the graph. Are there any other property (except node degree and node coefficient clustering) which only considers neighbours of a node in its calculation?


texts: Pathfinding search over a space with known changing costs

texts:
I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time.

More specifically, the danger values represent bad weather, and the program uses ten days of weather predictions to find the best route across a section of the earth.

Formalized:
We're given a graph where, for each edge $e$, the cost on that edge when starting at time t is $c_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$.

Up until now we've been using a modified A* search, however it is extremely inefficient and has become almost exhaustive.

Is there a better algorithm already out there for such a problem?

I've started to take a look at D* lite, but I don't believe it's the best solution, because we already know what the cost at time t.

Any advice is much appreciated.

Cheers,

Arek Sredzki


texts: Cartesian factorization of a finite set of n-tuples

texts:
(NB: I asked this question in Math Overflow, and based on the one reply [a comment, actually] that it received so far, I realized that this may be a more appropriate forum for it.  I've added a few comments to this post, connecting the problem to the theory of databases.)

I'm interested in factoring a finite set of $n$-tuples as the Cartesian product of two "factor sets", of which the first factor is itself the Cartesian product of some of the set's projection images, and the second factor is an unfactorizable "remainder".

To describe the problem more precisely, let $X$ be a non-empty, finite set of $n$-tuples, and let $A_1,...,A_n$ be the images of $X$ upon projection onto its various coordinates.  Hence, $X \subset \prod_{i=1}^{n} A_i $.  Furthermore, assume that this inclusion is strict; that is, $X \neq \prod_{i=1}^{n} A_i $.  (From this it follows that $n > 1$.)  If $\sigma$ is some permutation of $\{1,...,n\}$, let $X_\sigma$ denote the set of $n$-tuples derived from $X$ by permuting the coordinates of its elements according to $\sigma$: $X_\sigma = \{(x_{\sigma(1)},...,x_{\sigma(n)})|(x_1,...,x_n)\in X \}$.  (See the end of this post for a restatement of the problem using OLAP terminology.)

For any $n$-permutation $\sigma$, I'm interested in factorizations of $X_\sigma$ having the form $X_\sigma = (\prod_{i=1}^{k} A_{\sigma(i)}) \times Z$, where $0 \leq k \lt n$ and $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$.  This factorization means that every $n$-tuple in $X_\sigma$ can be written (obviously uniquely) as the concatenation of one $k$-tuple from $\prod_{i=1}^{k} A_{\sigma(i)}$ and one $(n-k)$-tuple from $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$, and, conversely, every concatenation of such tuples represents some element of $X_\sigma$.  (If $k = 0$, then $Z = X_\sigma$; i.e. the factorization is a trivial one.)

I am primarily interested in factorizations for which the factor $\prod_{i=1}^{k} A_{\sigma(i)}$ has maximal cardinality, over all possible choices of $\sigma$ and $k$.  I am also interested in factorizations for which $k$ is maximal, over all possible choices of $\sigma$.  [Edit: both criteria actually lead to the same result; see Tsuyoshi Ito's answer.]

[(This bracketed paragraph is intended by way of background; it is tangential to the questions of this post.  Please disregard it if it is not useful or clear.)  One area where this problem arises is in the theory of databases and OLAP: given a facts table $X$ with $n$ dimension (aka "metadata") columns, how can it be "most efficiently" converted to a collection of perfectly dense (i.e. no empty cells) multidimensional data "(hyper)cubes" having identical domains.  (These domains correspond to the sets $A_{\sigma(1)},...,A_{\sigma(k)}$ above.)  This formulation leaves the optimization criterion fuzzy.  I use the term "efficient" here to describe solutions that pack "as much information as possible" in the regular hypercubes, but even with this clarification the criterion is ill-defined, because "most information" could be defined as "the greatest number of cells" or "the greatest number of dimensions" (i.e. potential explanatory factors) for the regular hypercubes.  These correspond to the two classes of factorizations I described in the previous paragraph.]

I'm looking for keywords I may use to search for algorithms to compute such maximal factorizations, given some concrete set of $n$-tuples $X$.  Do such factorizations, or the problem of computing them, have a name?  Are their complexity classes known?  Any pointers to the relevant literature would be appreciated!

~kj


texts: Applications of sunflower lemma in theoretical computer science

texts:
In one lecture by Kewen Wu who is one of the authors of paper

  Improved bounds for the sunflower lemma,

it is said that the sunflower lemma can be applied to many fields like

circuit lower bounds
data structure lower bounds
matrix multiplication
pseudorandomness
cryptography
property testing
fixed parameter complexity

What I can know about the sunflower lemma comes from the books

  Parameterized Complexity Theory

  Extremal Combinatorics

  The Mathematics of Paul Erdős II     2013

and papers

  Improved Bound On Sets Including No Sunflower
  With Three Petals Junichiro Fukuyama 2018

  Improved bounds for the sunflower lemma Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang 2019

How is it applied to the field of computer science?


texts: Number of words of length n in a context-free language

texts:
Denote by $w_n$ the number of words of length $n$ in a (possibly ambiguous) context-free language.

  What is known about $w_n$?

I'm sure this has been studied a lot, but I couldn't find anything at all on it.


texts: Strong normalization property of CoC inside CoC

texts:
Wikipedia says that

  The CoC is strongly normalizing, although, by Gödel's incompleteness
  theorem, it is impossible to prove this property within the CoC since
  it implies inconsistency.

Why is it impossible to prove within CoC that it is strongly normalizing?

Probably strong normalization property within CoC implies proof of consistency within CoC.  Then we can use the second Gödel's incompleteness theorem.  If so,

How does strong normalization property within CoC imply proof of consistency within Coc?

UPDATE:

In other words, why there can not exist a term of CoC that is a proof of CoC's proposition that CoC has normalization property. My guess is that such a term could be used to construct a term that proves a proposition of CoC that expresses consistency of CoC which is impossible by the second Gödel's incompleteness theorem.  How to construct a proof of consistency within CoC given a proof of normalization property?


texts:
While the rule of thumb is that in TCS papers the authors are ordered alphabetically, there are some notable counterexamples that comes to mind, wherein the authors are ordered in a different way, e.g.,

Algebraic Methods for Interactive Proof Systems [Lund, Fortnow, Karloff, Nisan]
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems [Rivest, Shamir, Adleman]
Word Problems Requiring Exponential Time [Stockmeyer, Meyer]

What is the story behind the unusual author ordering in these papers?

Are there any other examples of major TCS papers in which the order of the authors is not alphabetical?


texts: What advantages does having a null-able string type confer to a programming language?

texts: I've been trying to understand the rationale behind the design of the C# language. Are there any specific advantages that can be gleaned from allowing string type variables to contain null?


texts: Probability of random (in)finite graphs being isomorphic

texts:
I once skimmed a paper which examined the probability of two (infinite) graphs picked at random being isomorph. The surprising result was that for two random infinite graphs this probability is quite high as opposed to the finite case. I remember it being referenced in the context of why so many graph invariants  - often claimed to be complete - work correct on most inputs.

I think the paper was published before the nineties.


texts: NP-hardness of tasks graph assignment to two heterogenous servers

texts:
I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated.

Problem definition

Given is a directed acyclic graph $G=(V,E)$ representing a set of computation tasks which need to be performed. Each vertex $v$ represents a single, non-divisible computation task. Each edge $e$ denotes communication between two tasks, i.e. transmission of output data from one task to another.

Each computation task can be executed on one of two servers: $S_A$ or $S_B$. The servers have differing architectures, so $S_A$ is able to perform some computations more efficiently than $S_B$, and vice versa. Therefore, each computation task has two values associated with it: $c_A(v)$ and $c_B(v)$, which denote the cost of executing the task on server $S_A$ and $S_B$, respectively.

Consequently, each edge $e$ has two associated values representing the data transmission cost: $t_{internal}(e)$ (both tasks executed on the same server) and $t_{external}(e)$ (the task are executed on different servers). We assume $t_{internal}(e) = 0$ (i.e. internal server communication has no significant cost). $t_{external}(e) > 0$ and is proportional to the amount of data which needs to be transmitted between the tasks. The transmission cost is symmetrical, i.e. it does not matter if we transmit the data from $S_A$ to $S_B$ or from $S_B$ to $S_A$.

The total cost of computation $C$ is the sum of costs of individual task executions and the costs of communication between tasks, i.e.:

$C = \sum\limits_{v \in V}c(v) + \sum\limits_{e \in E}t(e) $

Question

Is determining the lowest-cost assignment of tasks $v$ to servers ($S_A$ and $S_B$) NP-hard?

Attempted approach

I have tried transforming the graph $G$ to a new graph $G^Z$ with doubled vertices, as shown in the picture below.

In the new graph, the problem is to choose one vertex from each pair ($v^A$, $v^B$) so that the total weight of edges remaining in the resulting graph would be minimal.

I have tried to find possible analogies to well-known graph theory problems (e.g. maximum independent set, vertex cover, graph partitioning, etc.). Alas, to no avail.


texts:
By the Curry-Howard Isomorphism we view propositions (or theorems if true/inhabited) as types.

But take the type $\mathbb{N} \implies \mathbb{N} \implies \mathbb{N} $.

We have as witnesses to this type (i.e., proofs of this theorem) both

f x y = x + y
f x y = x * y

Yet they "attest to the validity" of two very different programs. Is this the motivation for increasing the expressivity of a type system, as we see with dependent types? How would the type signature above be spoken in English - "for all naturals, x and y, it is true for all naturals"...?


texts: Is there a list of canonical problems in distributed systems?

texts:
Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about Solved Problems, Unsolved Problems and Non-Problems in Concurrency. The paper is easily readable, but one of the things that got me thinking is the following assertion:

  Can any problem be regarded as a mutual exclusion problem or a
  producer- consumer problem, or a combination of the two?

I would like to know if this question has been answered for the distributed systems case.

Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to? What is this canonical list?

If there is not a canonical list what is the current list of problems and what reductions exist?

For example, I would say very naively that the leader election and mutual exclusion problems can be reduced to the consensus problem. I would also say that a distributed snapshot can be reduced to a distributed clock. It it true or plain wrong?

If possible, I would prefer that the answers provide a reference to a published paper/book supporting its claims :)


texts: Is $\mathrm{co}(\mathrm{NP}^A) = (\mathrm{coNP})^A$?

texts:
I believe $\mathrm{co}(\mathrm{NP}^A) = (\mathrm{coNP})^A$:

By definition, $L \in (\mathrm{coNP})^A$ means there is a PTIME Turing machine $M$, allowed to make oracle calls to $A$, such that for any word $w$, all computations of $M$ when started with $w$ on its input tape end in "reject" iff $w \in L$.

In other words, for any word $w$, there is some computation of $M$ (with oracle calls to $A$) that ends in "accept" iff $w \notin L$, i.e., iff $\overline{L} \in
\mathrm{NP}^A$ iff $L \in \mathrm{co}(\mathrm{NP}^A)$.

Is this right?


texts: Computing specific information of a signal propagation instead of entire signal

texts:
Disclaimer: This may be considered off-topic. I apologise if this is the case, but I really could not find a better place to post this.
In general, a signal can be built from a combination of parameters. A simple example is a Gaussian distribution of the form-
$f(x) = \frac{1}{\sigma \sqrt{2\pi}}e^{(\frac{x - \mu}{\sigma})^2}$
which can be always represented by $\mu$ and $\sigma$.
In the specific problem I am working on, I have a differential equation that describes the propagation of a signal starting from a Gaussian pulse. But I don't really care about the signal itself, but care only about the pulse width.
The pulse width of a signal carries "less" information about the signal than the signal itself. By this, I mean the value of the pulse width is hidden within the signal, but the signal cannot be described from the knowledge of the pulse width alone.
This makes me think that it would be justified if an algorithm could be developed that can track the propagation of the pulse width alone which is computationally inexpensive as compared to track the propagation of the pulse itself and then calculate the pulse width from it.
Am I right in saying this? My initial guess is no. But I do not know why it is wrong to say so.
As for tags, I am not sure what this question could be tagged under. Going with a generic "information" tag for now. Please let me know if I have to add any others.
Edit:
My input is a Gaussian signal. I would like to see how the pulse width of the signal changes when it propagates through a system described by a partial differential equation. My current method is to see how the signal itself propagates and then calculate the pulse width from the signal. I would rather like to see how only the pulse width propagates without actually seeing how the signal propagates. Intuitively, I feel that it should be easier to compute the pulse width as a function instead of the entire signal as the pulse width alone has lesser information than the entire signal.
The differential equation I had in mind is the Nonlinear Schrodinger Equation (NLSE).
Although an algorithm would be great, that is not what I am asking. I am asking if it is possible to prove that such an algorithm exists or doesn't exist in the general case where the propagation of a single parameter of a signal can be tracked with lesser computation than the computation required for propagating the entire signal.


texts: Chomsky normal form method: CYK parser performance implications?

texts:
Chart parsers can be implemented based on Chomsky normal form or
directly based on production rules. Lets for the moment assume
we have a CYK chart parser that uses Chomsky normal form. The
binarization is not uniquely defined. Does this impact the
performance of the CYK chart parse. Can this be exploited to
improve the performance of a CYK chart parser?


texts: Is there a generalization of information theory to polynomially knowable information?

texts:
I apologize, this is a bit of a "soft" question.

Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating satisfiability carry the same amount of information.

Is there a way to formalize the concept of "polynomially knowable"?

Such a framework could define for example the notion of polynomial-KL divergence between a random variable X relative Y as the number of bits needed to compute X in polynomial time given Y.

Likewise, the entropy of a random variable X could be defined as the number of bits needed to encode X in a way that can be decoded in polynomial time.

Has such a generalization been studied? Can it be made consistent?


texts: Are there efficient black-box constructions of sigma-protocols for SAT?

texts:
Is there a known black-box construction for the following implication?

  non-interactive string commitment that stretches additively by an

  amount which does not depend on the string being committed to
  $\implies$
  sigma-protocol for, equivalently, circuit-SAT or 3-SAT, whose communication

  complexity scales subquadratically with the size of the SAT instance

The only methods I know either

use circuit-SAT, commit to the values of enough gates, and then use the code of the commitment scheme to prove that the values committed to are correct and cause

the circuit to output TRUE $\:$ (using the code makes the construction not black box)

or

use a graph with a number of edges that scales linearly with the number of variables

(as the case may be) and commit to each entry in the adjacency matrix, for a

communication complexity that scales quadratically with the size of the SAT instance

or

reduce to 3-coloring and, although the communication for each instance of the "core"

only scales linearly, need a number of parallel executions of the "core" that scales linearly,

for a communication complexity that scales quadratically with the size of the SAT instance

.


texts: Estimating the rank of a large sparse matrix

texts: Consider a large sparse n by n matrix.  Are there any methods to estimate its rank in time roughly proportional the number of elements in the matrix?


texts: What is the connection between moments of Gaussians and perfect matchings of graphs?

texts:
Today, I heard the following statement in a talk:

  The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a complete graph of $4$ vertices, which is $3$.

Unfortunately, the speaker did not have enough time to go into the details of this.

Firstly, it is very astonishing to me that something continuous can be related to something discrete as precisely as this, that is, beyond the limits of things like approximating a discrete sum with an integral. Secondly, what is the intuition behind this? Any pointers? Are there other examples like this where discrete quantities can be related to continuous quantities?


texts: bounded language complete for NSPACE(log n)?

texts:
What are the consequences of a sparse language being complete for $\mathsf{NSPACE(\log n)}$ under deterministic $O(\log n)$-space many-one reductions? Is there an analog of Mahaney's Theorem for $\mathsf{NL}$ (if there is a sparse $\mathsf{NL}$-complete language then $\mathsf{L} = \mathsf{NL}$)?

Bounded here was meant to indicate that if the input alphabet is $\{a_1, ..., a_k\}$, the language is a subset of $a_1^* a_2^* ... a_k^*$. Any such language clearly has number of strings of length $n$ that is bounded by $n^k$ so bounded => sparse.


texts: Aryeh Kontorovich wrote a technical report on 'Rademacher complexity of k-fold maxima of hyperplanes.' But its link (https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf) is not accessible anymore from US. I know there is another paper which generalizes this result: https://arxiv.org/pdf/1911.06468.pdf but I am trying to see what were the bounds Aryeh Kontorovich got for max function specifically.


texts: Approximate c-chromatic number, each color class is P4-free (cograph)

texts:
The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of them is c-chromatic number, $c(G)$, defined in the paper Partitions of graphs into cographs. It asks that each color class is a cograph. Cograph is a P4-free graph, i.e., there is no induced path of length 3.

"G-free-complexity" implies that it is NP-Complete decide $c(G)=k$ for any $k\ge 2$. I have thought following questions about (in-)approximating $c(G)$ for a while. Any suggestion is appreciated. Intuitively, I think these graph coloring are really hard to approximate.

This post is related to a previous one about greedy coloring using a list.

Question 1. Given a graph $G$ of $c(G)=2$, is it hard (e.g., unless P=NP. or any other hardness assumption) to partition $G$ into three cographs? How hard is it to approximate $c(G)$ for general graphs.

Related results of the classic $\chi(G)$. It is hard to 4-color a 3-colorable graph. There are many inapproximateness results from the well-known PCP theorem. I tried to learn this theorem myself but it is hard for me to apply it to get inapproximate result of $c(G)$. I also tried gap amplification technique used to show it is hard to 2-approximate $\chi(G)$ by Garey & Johnsn.

Question 2. How good can we approximate $c(G)$ in polynomial time?

Related results. "Approximate Hypergraph Coloring" shows that, for any 4-uniform 2-colorable hypergraph $H$, there is a randomized algorithm to color $H$ using $O(n^{2/9}\log n)$ colors.
For any graph, Remark 12 shows that we can partition $G$ into at most $\lceil \frac{\Delta + 1}{2} \rceil $ cographs.

Any suggestion is welcome. A good tutorial or note of PCP Theorem (including application) is great. Thank you very much.


texts: Existence of complete "asymptotic" optimization problems

texts:
Define a function $u:\lbrace 0,1 \rbrace^* \rightarrow \mathbb{R}$ to be an asymptotic optimization problem when the following conditions hold:

There is an algorithm $U$ which computes the first $n$ digits of $u(x)$ in time at most $p(2^n, |x|)$ where $p$ is a polynomial
There are $a$, $c > 0$ s.t. given $x$ a prefix of $y$ we have $|u(x)-u(y)|<2^{-c|x|}a$

It is possible to restrict attention to functions $u:\lbrace 0,1 \rbrace^* \rightarrow [0,1]$ since any function satisfying the 2nd condition can be brought to this form by a linear redefinition

Consider $u$, $v$ asymptotic optimization problems. $f: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^*$ is a called a reduction of $u$ to $v$ when the following conditions hold:

Given $x$ a prefix of $y$, $f(x)$ is a prefix of $f(y)$
For any $u_0 < \sup u$ exists $w(u_0) < \sup v$ s.t. given $s \in \lbrace 0,1 \rbrace^\omega$, if $\lim_{n \rightarrow \infty}v(s_{<n}) > w(u_0)$ then $\lim_{n \rightarrow \infty}u(f(s_{<n})) > u_0$

The reduction is called polynomial-time when $f$ is computable in polynomial time

  Is there $u^*$ an asymptotic optimization problem s.t. any asymptotic optimization problem $u$ is reducible to $u^*$ in polynomial time?


texts: Suggested approach to cover data structure literature

texts:
I am not sure if this question is odd topic or too broad, but I have been wondering about this for a long time, and I would very much appreciate any valuable inputs.

As a new grad student working on data structures (in this case, related to pattern matching literature), how would someone get through the huge amount of literature that needs to be covered? I have a reasonable understanding of basic data structures, but each time I open a research paper, there are heaps of new terms that I haven't heard before. In an effort to broaden my knowledge, I have been reading a few textbooks. For instance:

Advanced data structures by Peter Brass
Compact Data Structures A Practical Approach by Gonzalo Navarro (which is quite hard to get through)

Still, getting through the research papers seems like a never ending battle. What is a really good approach to get an overview of such huge volume of works done in the area?


texts:
Is anything known about ExpSpace problems whose configuration reachability problems are in P/poly?

  Let $M$ be an ExpSpace machine.
  Given two configurations $a$ and $b$ of $M$ (of max length), and an integer $t$,
  can $M$ reach $b$ from $a$ in $t$ steps?

Note that the length of $a$, $b$ and $t$ are exponentially large in terms of the length of the input to $M$.

So the P/poly machine runs exponential time with an exponentially-long advice string. But it should not be something like $\mathsf{EXPSPACE} \cap \mathsf{EXP/exp}$ (and thus simply EXPSPACE) for obvious reasons.


texts: An algorithm to compute sine and cosine within $n$-digit precision

texts: I know CORDIC, but is there a better algorithm to compute $\sin x$ and $\cos x$ within specified $n$-digit accuracy?


texts: Complexity of marriage matching problem?

texts:
Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair binds one male to one female. The satisfaction of a matching is number of attributes satisfied for the least lucky person.

  Is finding a matching with maximum satisfaction efficiently solvable or is it $NP$-hard?


texts: Semiring examples from formal language theory

texts:
I'm learning algebraic theory of parsing. My first problem is identifying semiring examples which are specific to formal language theory. Here is an attempt to construct two examples.

1 Given CNF grammar, the elements of semiring are sets of terminal and nonterminal symbols with the operations:

i) Multiplication, joining the two sets pair-wise according to CYK rule. For example given CNF grammar

s: p p | q r
t: p q
u: q q

then

$ \{p,q,r\}\otimes \{p,r\} = \{s,t\} $

ii) Addition is set union, e.g.

$ \{p,q\}\oplus \{q,r\} = \{p,q,r\} $

Unfortunately, multiplication is not associative.

2 The elements of second semiring are sets of not symbols but grammar rules [not necessarily in CNF] amended with position. The operations are

i) Multiplication, joining all matching pairs of elements according to Earley complete rule. For example given CNF grammar

s: p q r
r: s t | u

then

$ \{s: p \bullet q r,s: p q \bullet r\}\otimes \{r: u \bullet \} = \{s: p q r \bullet \} $

ii) Addition is again the set union, e.g.

$ \{s: p \bullet q r, r: \bullet s t\}\oplus \{r: u \bullet \} = \{s: p \bullet q r, r: \bullet s t, r: u \bullet\} $

This example is also deficient.

Semiring with elements being sets of grammar rules and multiplication being rule substitution seems to work fine. Yet, this is just relation algebra in disguise. Indeed, let view each grammar rule as an equivalence class -- a set of pairs of words consisting terminal and nonterminal letters related by rule's application, e.g.

$ [t : s a] = \{ (t,sa),(ta,saa),(bt,bsa),(abt,absa),... \} $

Then, recognition of a word in a grammar is a chain of relational compositions, e.g.

$ [t:sa] \otimes [s:aa] \otimes \{(aaa,aaa)\} =  \{(t,aaa)\} $

(This monomial is reminiscent of semiring parser polynomial from Josh Goodman PhD thesis; however, let reiterate that constructing new semirings by taking polynomials and matrices is not of our interest here).

So, the question remains: is the semiring of formal languages over alphabet $\Sigma$ the only example?


texts: Can I represent a computer program on a Hilbert Curve?

texts:
I overheard in discussion tonight:

  You know - you can represent a computer program as points on a Hilbert Curve.

Is there a reference that explains this concept? I can't seem to Google for it.


texts: Best known results pairwise distance computation of high-dimensional points?

texts:
Suppose we are given a family $F$ of $n$ sets of total cardinality $N$ with elements of the sets drawn from a universe $U$ of size $|U| = d$.
Alternately, suppose we have $n$ points in $R^d$, or $n$ $d$-dimensional vectors.

Question:

We want to preprocess the sets/points such that we can efficiently report the approximate (Hamming/Minkowski) distance between any two sets/points within a factor of $1 + \epsilon$
What is the best known query time / preprocessing time for this problem?
(Note that we do not make any assumption on the relationship between $d$ and $n$. In particular $d$ is not necessarily sub-linear in $n$)

One approach would be to use a dimension reduction technique in the preprocessing phase, to speed up the query time. For example, we could use some algorithm based on the Johnson–Lindenstrauss lemma to project the points into a $k$ dimensional space first, and later when answering a query, we only spend $k$ time instead of $d$ time to compute the distance between any pair of points.

I think that Alon showed that $k = \Omega(\frac{\log n}{\epsilon^2 \log (1/\epsilon)})$ for the Johnson-Lindenstrauss lemma.

In their STOC'06 paper, Ailon and Chazelle give an algorithm which achieves a nearly matching upper bound of $k = O(\epsilon^{-2} \log n)$ using FJLT with a preprocessing time of $O(n\cdot(d \log d + \epsilon^{-3} \log^2 n))$ for the dimension reduction of all $n$ points under $\ell_1$ distance. Are there any similar approaches which achieve a better preprocessing time?

Are there any alternate approaches that beat the lower bound on $k$?
In A sparse Johnson-Lindenstrauss transform, under "Main Results", Dasgupta et al. appear to achieve $k = O(\epsilon^{-2}\log(\frac{1}{ \delta}))$, but I fear I may be misunderstanding that section of the paper.


texts: What is the computational complexity of the fastest algorithm to compute Jordan canonical form for a matrix

texts: Given a matrix, What is the  computational complexity of the fastest algorithm  to compute Jordan canonical form for the matrix? suppose the value of elements of the matrix and eigenvalue are complex number.


texts: What is some important work in fractals?

texts:
Relating to the discussion on whether fractals are part of TCS, my question is:

  What are some important work/results in fractals in TCS?

The work/results may be focusing on fractals or it may use fractal concepts as a secondary analysis of some primary topic.


texts: Regular safety properties and bad prefixes of $\omega$-regular properties

texts:
I have two questions:

By starting with a nondeterministic Büchi automaton (NBA) $\mathcal{A}^{\varphi} = (Q, \Sigma, \rightarrow, I, F )$ for an $\omega$-regular property $\varphi$, we can construct a NFA $\widehat{\mathcal{A}}^{\varphi} = (Q^{\prime}, \Sigma, \rightarrow^{\prime}, I^{\prime}, F^{\prime} )$ that recognizes the bad prefixes of $\varphi$ as the complement of NFA $\overline{\mathcal{A}}^{\varphi} = (Q, \Sigma, \rightarrow, I, F_1 )$:

For every state $q \in Q$, if there is a nontrivial strongly connected component (SCC) $C \subseteq Q$ such that  $C \cap F \neq \emptyset$ and $C$ is reachable from $q$, then $F_1 \leftarrow F_1 \cup \{q\}$. Basically, $q$ is in $F_1$ iff the language of $\mathcal{A}^{\varphi}$ starting from $q$ is nonempty.

N.B. A SCC consisting of a single state with a self-loop is considered nontrivial SCC.

  Does NFA $\widehat{\mathcal{A}}^{\varphi}$ recognize all bad prefixes of $\varphi$ and, hence, $\omega$-regular safety properties are regular safety properties, where a safety property is regular if its set of bad prefixes is a regular language?

By determinizing and complementing $\widehat{\mathcal{A}}^{\varphi}$, we can get a NBA $\mathcal{B}^{\psi}$.

  Is $\psi = Closure(\varphi)$?

According to PMC, $Closure(\varphi)$ of a linear-time property $\varphi \subseteq \Sigma^{\omega}$ is the set of all infinite words whose finite prefixes are also prefixes of $\varphi$. This coincides with the notion of closure from topology, and $Closure(\varphi)$ will always be a safety property.

Sorry for the elementary question.


texts: Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)

texts:
I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.

A very general question:
Most algorithms compromise of
finite input - finite computation steps - finite output

However, in mathematics most schemes which one could call algorithmic actually compromise infinitely many iterations. Just to name a few:

Iteration to construct fix-points of contractive maps
Iterative solvers in numerical analysis
Newtons method

I know the last one is treated in the classical book "Complexity and Real Computation" by Blum, Cucker, Shub & Smale, but there does not seem to exist a generalization which puts "iterative" algorithms onto solid foundations.

Edit:
Yes, the question:

  How can you deal with these iterative algorithms (which as such are not necessarily supposed to finish)?

Addendum:
I always wondered whether there might be something like a BSS-like model, which is tailored for numerical analysis - in that it does formalize errors, inexactness, approximate solutions, and does not allow for "unreasonable" computing power. And is easy to access.

The book mentioned above is concerned about this gap, too:
"There is not even a formal definition of algorithm in the subject [of numerical analysis]" (p. 23). However, it does not seem their approach suits this need. On the other hand, the monograph Andrej mentions does include a book which heads towards this direction.


texts:
Edited Version

What are the main characteristics and qualities that you would consider if you were going to choose a PhD program in theoretical computer science (or related areas) today (based on your experience) and why would you consider them important?
What are the credible sources that I can get information about those characteristics of PhD programs?

Especially I would like to hear your opinion about the following two issues:

If you had to choose between a program with a global and better brand name and another one with a strong research focus, which one would you choose? why?
Which of the following two is more important in your opinion: availability of specialization one wants vs general teaching/research quality of faculty?

Thanks.


texts: Fourier Analysis on checking whether there exists a vector in hypercube orthogonal to a set of vectors?

texts:
I know virtually noting about Fourier Analysis and I'd like to know whether it's worth to learn this topic for my problem.

My problem is: Given vectors $h_1,\cdots,h_k\in\{+1,-1\}^n$ where $k < n$, decide whether there exists another vector $x\in\{+1,-1\}^n$ that is orthogonal to all of $h_1,\cdots,h_k$.

I think I may formulate my problem with the help of a quadratic function $f(x) = x^T\left(\sum_{i=1}^k h_i h_i^T\right)x$ to have a condition that

  $f(x) = 0$ if and only if $x$ is orthogonal to $h_1,\cdots,h_k$.

As the desired function is a boolean function that $f:\{+1,-1\}^n\to\mathbb{R}$, it may be uniquely represented by a certain Fourier expansion . Then my job is to check whether this function has zero Fourier coefficients or not.

I know there can be $2^n$ Fourier coefficients. And it may be impossible to check whether a function has a Fourier expansion with zero coefficients. Does this approach make sense? Is there any reference / related work on this kind of problem?


texts:
Where can I find surveys in languages than English ?

If the question is found to be interesting (it could be usefull for graduated students who are not fluent in English for instance), it would be practical to propose one reference by answer, i.e. by subject and by language.


texts: Multiplicative-depth 1 composition of arithmetic circuits

texts:
I am trying to find information about the following problem. Let $C_1$ and $C_2$ be any two poly-size arithmetic circuits on input vectors x₁ and x₂ correspondingly. Assume that a third arithmetic circuit $C_3$ (also poly-size) combines their outputs. To make the problem non-trivial, $C_3$ can have multiplicative-depth $1$; however, the other two circuits have no such restrictions. What is known about the power of the resulting circuit class? Even some good keywords would help. Thanks in advance.

edit: forgot some details, please see my comments.


texts: How can one construct a densest graph with no k-clique?

texts:
Given integers $k$ and $n$ with $2 \le k < n$,
  how does one construct a graph on $n$ vertices
  that contains no $k$-clique and has the maximal
  number of edges?

This sounds like basic combinatorics, but I don't know where to find the result.  Pointers would be welcome if this is well-known.

Ideally I would like a deterministic procedure to construct such a maximal graph in $n^{O(1)}$ time.

One graph with $n$ vertices that is guaranteed not to contain $K_k$ is $\overline{K_{n-k+2} + \overline{K_{k-2}}}$, the complement of the graph formed by the disjoint union of $K_{n-k+2}$ and $k-2$ isolated vertices.  Whenever one picks $k$ vertices from it, at least two of these must be from the subset which is completely disconnected, so they cannot form a clique.  This can clearly be constructed in polynomial time, and is quite dense for $k$ close to $n$.  However, this construction yields rather sparse graphs when $k$ is small relative to $n$, so it seems unlikely to be the optimal construction.


texts:
I have heard it said that time is more precious than space because we can reuse space but not time.  What if we treat space with this much reverence?

What is generally known about models of computation in which space is immutable?

I would expect such models to initialize each memory cell to some "blank" state and then only allow the writing of some "non-blank" value to each cell at most once.

The study of persistent data structures seems to me like a possible way to answer this question.

I thought of this question while studying functional programming, which highly values immutability.


texts: What relations and differences are between formal semantics for linguistics and for programming languages?

texts:
I browsed the table of content of Cann's Formal Semantics, which   reminds me  of the things that I saw in programming language books.
Cann's book is for linguistics, and am I right that it is helpful for computational linguistics and natural language processing, another active research area of computer science? (Side note: it also seems to me that the approaches to NLP have been predominantly based on statistics and machine learning in applications (and maybe also research), which I think is completely unrelated to formal semantics?)
Do formal semantics of linguistics and semantics of programming languages (and the ways of study each of the two) have more common ground than differences?  What are their common ground and what are their differences?  Are books on one helpful to study in the other?
Thanks.


texts: Is it possible a recursive compression algorithm based on L-systems or a variant?

texts:
According to the Internet, there's a way to get an L-system's rules by it's string, unfortunately I can't read it because it's behind a paywall.

Question: If that paper is right, is it possible to make an algorithm, based on L-systems, to recursively reduce let's say a blob of 64MB of zeros and ones down to:

A "small" starting axiom.
A set of variables/constants/you-name-it.
A set of rules.
The number n of iterations required.

/Question End

Compression is all about entropy and something in my guts says this isn't possible, I'd like someone with more experience to confirm it.


texts: Different estimators for uniform convergence of means/averages to expectations

texts:
In uniform converge results of means or averages to their expectations (think of the typical results involving VC-dimension, covering numbers, Pseudo-dimension, fat shattering dimension, ...) , the estimator used on the sample is the sample average. Is it possible to use a different estimator? Is it required that the estimator has some specific properties (I assume at least unbiasedness) ?

Thanks


texts: Is there a way to solve or approximate the concave program with separable objective?

texts:
I would like to solve the following problem:
"minimize $\sum_{i=1}^k \sqrt{x_i}$ subject to some polytope constaints."
Is there a polynomial time algorithm to solve or approximate it?
Thanks.

Jian.


texts: Number of ordinal trees with n nodes, of depth d, with l leaves

texts:
What is the number of ordinal trees (aka rose trees) with $n$ nodes, of depth $d$, with $l$ leaves?

I thought that it was a known results but I could not find it, and neither did the various combinatorics whom I asked. It seems that it should be computed using generating functions, but beside the fact that such a generating function would have two variables, there is also the fact that the number of nodes and of leaves are additive between the various children of a tree, whereas the depth of a tree is one plus the max of the depth of each of its children: I don't know how to express those in a generating functions.

The reason I ask is that, when considering (some variant of) the cartesian tree of a multiset in order to support Range Minimum Queries on it, the number of runs in the multisets corresponds exactly to the number of leaves, and the number of distinct elements in the multiset gives a bound on the depth of the ordinal tree: the logarithm of the number of such trees will give a lower bound on the space usage of any compressed index supporting Range Minimum Queries, in the worst case over multisets of size $n$ with $l$ runs and $d$ distinct values. (And, with only a bit more work I believe, an asymptotically tight upper bound.)

Demaine et al define an ordinal tree as "a rooted tree of arbitrary degree in which the children are ordered" http://erikdemaine.org/papers/MaryTrees_Algorithmica/paper.ps. It seems that they are also called Rose trees in some communities. They should not be confused with cardinal trees, also called $k$-ary trees.


texts: Fourier spectrum of the parity of two monotone Boolean functions

texts:
This is a question that I've been pondering, on and off, for a while, and unsuccessfully. I'd be very interested in any insight regarding this conjecture. (Or rather, these conjectures.)

Recall that, given a Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, the Kahn—Kalai—Linial theorem states that
$$\max_{i\in[n]} \operatorname{Inf}_i f \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{1}
$$
from which we get that, for any monotone Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$,
$$\max_{i\in[n]} \widehat{f}(i) \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right)
= (1-\widehat{f}(0)^2)\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{2}
$$
(writing $\widehat{f}(i)$ for $\widehat{f}(\{i\})$, $i\in\{0,\dots,n\}$). Moreover, (2) is tight, as shown by considering the $\textsf{Tribes}_n$ function. In particular, this implies that
$$
W^{(0)}[f]+W^{(1)}[f] = \sum_{i=0}^n \widehat{f}(i)^2 = \Omega\!\left(\frac{\log^2 n}{n^2}\right) \tag{3}
$$
for any monotone Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, where $W^{(k)}[f] \stackrel{\rm def}{=} \sum_{S: \lvert S\rvert =k} \widehat{f}(S)^2$.

Now, consider two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, and let $h\stackrel{\rm def}{=}fg$ be their parity. It is easy to see that we could have $W^{(0)}[h]+W^{(1)}[h]=0$, e.g. by considering $f,g$ to be two different dictator functions (but in that very specific case, $W^{(2)}[h]=1$). But must there be some non-negligible Fourier mass on the first 3 Fourier levels, then?

  What can we say about $W^{(0)}[h]+W^{(1)}[h]+W^{(2)}[h] = \sum_{S: \lvert S\rvert \leq 2} \widehat{h}(S)^2$?

Conjecture 1. For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] > 0$.

Actually, I'd be actually inclined to believe the following stronger statement:

Conjecture 2. For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] \geq \frac{1}{\operatorname{poly}(n)}$.

Side note: this would have implications about weak learning of the class of "2-monotone" functions, which are exactly those functions obtained as parity or anti-parity of $2$ monotone functions. (See e.g. [BCOST15].) But more importantly, this is a very simple-looking question, that has been nagging at me for way too long.

[BCOST15] Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan. Learning Circuits with few Negations. APPROX-RANDOM 2015: 512-527