texts:
In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph  such that the number of edges between S and the complement of S is as large as possible.

Max-Cut is APX-complete on bounded-degree graphs [PY91], and in fact APX-complete on cubic graphs (i.e. graphs of degree 3) [AK00].

Max-Cut is NP-complete on triangle-free graphs of degree at most 3 [LY80] (triangle-free means that the input graph does not contain K_3, the complete graph on 3 vertices, as a subgraph).

Question: Is Max-Cut APX-complete on triangle-free graphs? (Note: arbitrary degrees allowed)

Thank you.

UPDATE: An answer has been found, but I would still be interested in a reference for this result, if there is any.

References:

[AK00] P. Alimonti and V. Kann: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1-2): 123-134, 2000. doi: 10.1016/S0304-3975(98)00158-3

[LY80] J.M. Lewis and M. Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230, 1980. doi: 10.1016/0022-0000(80)90060-4

[PY91] C.H Papadimitriou and M. Yannakakis: Optimization, Approximation, and Complexity Classes, J. Comput. System Sci., 43(3): 425-440, 1991. doi: 10.1016/0022-0000(91)90023-X


texts: Is there a sense in which we can say error returned from a function is the reverse of context?

texts:
This came up in a discussion about golang, but I think it applies more generally.

Context in which a function is executed (specially in when we have RPCs) and error returned from a function seem to be kind of special input and return values. Is that really the case? Are there any sense that they are related or say reverse or dual of each other?


texts: Must the cryptographic test for quantumness in [BCMVV18] use post-quantum Trapdoor Claw-Free Functions?

texts:
Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable computational quantumness based on a strengthening of trap-door claw-free functions (TCFs).

In the above scheme:

Vicky the classical verifier provides a description of a pair of functions $f_0$ and $f_1$ to Peggy the quantum prover, while saving the trapdoor to $f_0$ and $f_1$;
Peggy prepares, measures, and reports the results of a register in a quantum state to provide a $y$ such that $y=f_0(x_0)=f_1(x_1)$, keeping a superposition of $\vert b\rangle\vert x_b\rangle$;
Vicky asks Peggy to measure the superposition in either (a) the computational basis to provide a bit $b$ and an $x_b$ such that $f_b(x_b)=y$, or (b) in the Hadamard basis to provide a string $d$ orthogonal to $x_0\oplus x_1$; and
Based on Vicky's possession of the trapdoor, Vicky can validate results (she uses the trapdoor to deduce both $x_0$ and $x_1$ from $y$ and Peggy's response above).

The authors instantiate their TCF's with lattice-based learning-with-errors, which, in addition to satisfying hardcore bit requirements, is also a leading candidate for post-quantum cryptography - that is, a cryptographic protocol that is likely secure against a quantum computer.  They require post-quantum security for randomness generation, and Mahadev requires post-quantum security for her later breakthrough on classical verification of quantum computing.

  But does such a scheme to just prove quantumness also need to be based on post-quantum TCFs?

For example if the trapdoor claw-free function was based on a classically-secure, but quantum-broken, TCF, and if Peggy could be consistent in reporting correct answers to Vicky, then Peggy has shown that either:

She has prepared and maintained a quantum superposition of both preimages as intended; or
She has broken the TCF with quantum computer to invert $f_b$ to find at least one preimage along with the string $d$.

Either way, she has evidenced computational quantumness.


texts: Are Julia sets (theoretically) Turing-complete?

texts:
Could any (computational) function be expressed in terms of a Julia set?
Is the space of all possible computational functions (which I think is defined by Turing completeness) translatable to the space of all possible Julia sets?


texts: Dominations under oracles which is closed under complement?

texts:
Edited at 2010/11/29:

As John Watrous have mentioned, the class $\mathsf{C^O}$ may be not well-defined. After reading some early posts, I try to restate my question in an unambiguous way.

Let $\mathsf{O}$ be a complexity class that is closed under complement, i.e. $\mathsf{O} = \mathsf{coO}$. Also we assume that the logspace, $\mathsf{L}$, is a subset of $\mathsf{O}$.

  When does the equality $\mathsf{L^O} = \mathsf{O}$ hold?

We define $\mathsf{L^O}$ as languages accepted by logspace oracle machines with an $\mathsf{O}$ oracle, where queries are written on a separated oracle tape not restricted to the logspace bound, and after each query the tape is automatically erased.

We know that $\mathsf{NL} = \mathsf{coNL}$ by Immerman-Szelepcsényi Theorem, and we have $\mathsf{L^{NL}} = \mathsf{NL}$.
Before the era of Reingold, when nobody knows whether $\mathsf{SL} = \mathsf{L}$, Nisan and Ta-Shma have proved that $\mathsf{SL}$ is closed under complement. They also show that $\mathsf{L^{SL}} = \mathsf{SL}$ in the paper.

In the paper "Directed Planar Reachability Is in Unambiguous Log-Space" by Bourke, Tewari and Vinodchandran, they gave a claim in corollary 4.3 that $\mathsf{L^{UL \cap coUL}} = \mathsf{UL \cap coUL}$. Clearly $\mathsf{UL \cap coUL}$ is closed under complement, but is this equality holds so trivially?

Do we have any easy conditions to decide if $\mathsf{L^O}$ and $\mathsf{O}$ are in fact the same? For easy conditions it means we only have to check some properties about $\mathsf{O}$, then we can decide if they are equal, without using definitions of the classes to prove the inclusion $\mathsf{L^O} \subseteq \mathsf{O}$.

Another related question would be:

  Do we have any oracle $\mathsf{O}$ such that $\mathsf{L^O} \neq \mathsf{O}$?


texts: Complexity of factorial exponent over composite moduli

texts:
I know that computing factorial modulo a composite number has no fast algorithm and showing non-polylogarithmic lower bound in BSS model for factorial would separate P from NP in that model.

Given $a\in\Bbb Z/n\Bbb Z$, where $n$ is composite, what is the complexity of calculating $a^{m!}$ in $\Bbb Z/n\Bbb Z$ for any given integer $n>m>0$?


texts: determining if a matrix of linear forms represents a non-degenerate matrix

texts:
Let $k$ be a field with $p$ elements. Consider the following computational problem

  Input: a natural number $n$,  $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$.

  Problem: Is there an assignement of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?

${}$

  Question: What is known about algorithms for this problem?

As usually, let's assume the addition and multiplication in the field to have computational cost $1$.

The naive algorithm of checking each assignment of the variables $X_{ij}$ takes time bounded by a polynomial in $p^{n^2}$. I'd be interested to know if there is an improvement to polynomial in $p^n$ (or better).

The special case when each $M_{ij}$ is equal either to $0$ or to $X_{ij}$ is solved  by Emil Jeřábek on the mathoverflow thread linked to below.


texts: Number of subgraphs with given edge parity

texts: I would like to know whether counting number of induced (full) subgraphs (of an undirected graph) that have even number of edges is P or #P-complete. Additionally, is the problem easier if we assume that given undirected graph has constant degree (all vertices have up to k incident edges)?


texts: To find OR of $\sqrt{n}$ numbers each of $n$ bits?

texts:
Given $\sqrt{n}$ numbers of $n$ bits each. I need to find its OR and store it at another number RESULT of $n$ bits.
Trivially it can be done in $\mathcal{O}(n \sqrt{n})$ time, or $\mathcal{O}(n \sqrt{n} \,/ \log n)$ considering RAM model with word size $\log n$.

I am interested in some deterministic or randomized solution that takes $\mathcal{O}(n \text{ polyLog } n)$ time expected or exact to solve the problem. I need an exact solution but expected time will work.


texts:
Let us say that a graph class has the jump property, if it either contains all $n$-vertex graphs for every large enough $n$, or else the fraction of $n$-vertex graphs that belong to the class approaches 0, as $n\rightarrow\infty$.

The answers to an earlier question (see
here) show that every hereditary graph class has this jump property.

Question: What are some other (nontrivial) examples of graph classes with this  property?

Note: It would be good to see natural examples, that is, classes that arise from independent considerations, not created just for the sake of the jump property.


texts: Reference request: strong polynomial-time for LP

texts:
A follow-up of sorts on this question:
Complexity of finding a consistent hyperplane

What is a good survey of partial results on the strong poly-time status of the general LP problem?


texts: Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

texts:
This might be a subjective question rather than one with a concrete answer, but anyway.

In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands for polynomial time, and $\mathsf{L}$ stands for log space. Both of them are considered to be represented as a kind of "efficiency", and they capture the difficulties of some problems pretty well.

But there is a difference between $\mathsf{P}$ and $\mathsf{L}$: while the polynomial time, $\mathsf{P}$, is defined as the union of problems which runs in $O(n^k)$ time for any constant $k$, that is,

$\mathsf{P} = \bigcup_{k \geq 0} \mathsf{TIME[n^k]}$,

the log space, $\mathsf{L}$, is defined as $\mathsf{SPACE[\log n]}$. If we mimics the definition of $\mathsf{P}$, it becomes

$\mathsf{PolyL} = \bigcup_{k \geq 0} \mathsf{SPACE[\log^k n]}$,

where $\mathsf{PolyL}$ is called the class of polylog space.
My question is:

  Why do we use log space as the notion of efficient computation, instead of polylog space?

One main issue may be about the complete problem sets. Under logspace many-one reductions, both $\mathsf{P}$ and $\mathsf{L}$ have complete problems. In contrast, if $\mathsf{PolyL}$ has complete problems under such reductions, then we would have contradict to the space hierarchy theorem. But what if we moved to the polylog reductions?
Can we avoid such problems? In general, if we try our best to fit $\mathsf{PolyL}$ into the notion of efficiency, and (if needed) modify some of the definitions to get every good properties a "nice" class should have, how far can we go?

  Is there any theoretical and/or practical reasons for using log space instead of polylog space?


texts:
Is it possible that $\overline{SAT} \in NTIME(\exp(n^{0.9}))$ ?
Are there interesting consequences of such containment?
Would it contradict the Exponential Time Hypothesis?


texts:
Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed throughout the years.

But I have not encountered a comprehensive, systematic list of pivot rules in literature. Though comprehensiveness might be infeasible, one could hope for a list that at least contains rules that have been researched attention and discussion in the scientific community.

Do you know about such a list? Conversely, what prevents people from assembling such a list or survey?


texts: Shortest path in a DAG consisting of multiple copies of a smaller DAG

texts:
Let's say we have $k$ weighted DAGs (directed acyclic graphs)
$$H_1 = (V_1, A_1), \dots, H_k = (V_k, A_k)$$
that are copies of one another. Now consider another weighted DAG $G$ that is built by combining $H_1, \dots, H_k$ and adding some additional arcs that can only go from one vertex to vertices in the following copies, i.e., consider a weighted DAG $G = (V, A)$ such that:

$V = \bigcup_{1 \le i \le k} V_i$; and
$A = ( \bigcup_{1 \le i \le k} A_i ) \cup A'$, such that for each $a = (u, v) \in A'$ we have $u \in V_i, v \in V_j$ with $i < j$.

Now suppose we want to find the shortest $s$-$t$ path for a given pair of vertices $(s, t) \in V^2$. Can precomputing all-pairs shortest paths in $H_1, \dots, H_k$ be used to speed up the algorithm?

Any references to papers that use similar ideas would be helpful.


texts: Minimizing the gaps with incremental capacity

texts:
There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 capacity i.e., the available capacity $C(t)$ at slot $t$ is $C(t):=\sum_{s\leq t}\zeta(s)$ (if the job was not scheduled at $t$ or before $t$). If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the available capacity $C(t)$. If the job is not scheduled for a period of $x$ consecutive slots, then a penalty of $\lfloor x/2\rfloor$ occurs.
EDIT

We have to guarantee that $C(t)=\sum_{s\leq t}\zeta(s)-\sum_{s\in S}c(s)\geq 0$ for all $t$ where $S\subseteq\{1,2,\ldots,t\}$ is the set of slots where the job was scheduled.

For the penalty: there is a penalty for every contiguous unused block.

Here, is an example to illustrate the problem. Say $n=8$ and the job is scheduled at time $1$, $4$, and $8$. Here, we have a penalty of $\lfloor{2/2}\rfloor=1$ between time $1$ and $4$ since the job is not scheduled for a period of 2 consecutive slots ($2$ and $3$). Also, we have a penalty of $\lfloor{3/2}\rfloor=1$ between time $4$ and $8$ since the job is not scheduled for a period of 3 consecutive slots ($5$, $6$ and $7$). Thus, the objective here is $1+1$.
Given $\zeta(t)$, $c(t)$ for all $t=1,2,\ldots,n$, the objective is to schedule the job during the $n$ slots in order to minimize the sum of penalties while respecting the capacity of machine in all scheduled slots.
Is this problem NP-hard?
I tried to reduce the knapsack problem to it but I did not succeed yet. Also, I tried to solve the problem in polynomial-time using dynamic programming but failed also due to the incremental capacity.


texts: tournament selection in genetic algorithms

texts:
I have a question about how to use a tournament selection in GA. Suppose that I have 100 individuals as an initial population and then I want to apply tournament selection for n generations, so I end up with only 20% of chromosomes for each iteration.
The algorithm that I came up with is:

choose 20% of the initial population
while (not end of iterations)
    select randomly n individuals from the left population (20%)
    if (number of chromosomes greater than two)
        select the best and mutate
        add to the population
    if (number of chromosomes greater than three)
        select best two of each pair and crossover them
        add crossover product to the population
    repeat process with new population
end while

is this schema correct?
Thanks


texts: What is the motivation behind the definition of fixed parameter tractability?

texts:
Wikipedia writes:

  FPT contains the fixed parameter tractable problems, which are those
  that can be solved in time $f(k)\cdot|x|^{O(1)}$ for some computable function $f$. Typically,
  this function is thought of as single exponential, such as $2^{O(k)}$ but the
  definition admits functions that grow even faster. This is essential
  for a large part of the early history of this class. The crucial part
  of the definition is to exclude functions of the form $f(n,k)$, such as $n^k$.

Question: What is the motivation behind this definition?

What's puzzling me is that, if $k$ is fixed (as per "fixed parameter tractability"), then $n^k$ is a polynomial in $n$.  So, why is it crucial to exclude $n^k$?


texts: Relaxing $\ell_0$ constraints in an optimization

texts:
I have a feasibility question that can be framed as follows. I'm given a point $p$ in a $d$-dimensional vector space, and I want to find the closest point $q$ to $p$ that satisfies a set of "$\ell_0$ constraints" of the form

  Given a set $S \in [1\ldots d]$, at
  most one of $\{q_j, j \in S\}$ can be
  nonzero.

The notion of closeness varies, but for now it is sufficient to assume a convenient distance like $\ell_2^2$.

Are there any known relaxations to linear constraints that are "good" in the sense of providing a "close enough" polytope to approximate the original constraints, where I'm also pretty flexible on the definition of "close enough"


texts: Holant problems and holographic reduction: simple graphs or multigraphs?

texts:
From what I can understand, Holographic reductions for Holant problems are used to show #P-hardness or polynomial time computability of certain counting problems on undirected graphs that have very restricted forms (for instance, 3-regular graphs, or 2-3-regular bipartite graphs).

My concern is about the confusion between the use of the word "graph" to mean either a) a simple graph, without self-loops and parallel edges or b) a multigraph, that can have self-loops and parallel edges (i.e., multiple edges between the same pair of vertices). I will first expose my problem by examples, then ask more precisely my questions.

Examples:

In the paper Cai, Lu and Xia, Holographic Reduction, Interpolation and Hardness, 2012, the authors provide a dichotomy for all problems of the form $\mathrm{Holant}([x,y,z][t_1,t_2,t_3,t_4])$, so over 2-3-regular bipartite graphs. They do not specify if they talk about simple graphs or multigraphs. A search for "self loops" reveals that they might be using graphs with self loops, but this is not very explicit (and what about parallel edges?). However nowhere else in the paper this distinction is discussed, and all the gadgets they use seem to be simple graphs (in the Appendix).
In Tyson Williams' thesis, by default the graphs considered are multigraphs (see page 4). He also says that Holant problems always consider multigraphs, suggesting that the first paper I cited considers multigraphs. In some of his results, he mentions the distinction between the two notions of graphs: for instance, Theorem 10.2.7 states that some problem is hard on 3-regular multigraphs, and he shows in Theorem 10.2.8 that the same problem is aslo hard on 3-regular simple graphs. By looking at the proof you see that the trick used is specific to this particular problem.
In the paper Xia, Zhang and Zhao, Computational complexity of counting problems on 3-regular planar graphs, 2007, the abstract talks about 3-regular graphs. When I first read it I thought that they are considering simple graphs, but actually I did not find a place where they say this.

At this point, I want to say that this post is not a critic to the authors of all these papers (I know that this kind of details can be annoying to present rigorously), the goal is just to clarify what is happening here.

Questions:

1) Do all the PTIME results of, say, the first paper I cite, work for multigraphs?

2) Do all the hardness results of that paper work for 2-3-regular simple bipartite graphs?

3) If not, is there a simple general fix so that the hardness results work for simple graphs, or does one have to find an ad hoc patch for each one of these problems? (for example, as in Theorem 10.2.8 of Tyson Williams' thesis)

4) If yes, do they also work for 2-3-regular simple graph that also satisfy this special property: no two nodes of the partition of degree 2 have the same neighbors. This condition would insure that, when you take a 2-3-regular simple graph that satisfies this, then contracting the nodes in the partition of degree 2 would always give a 3-regular simple graph. (without this condition, we could end up with parallel edges.)

This post is also related to this post and this one, where the same kind of confusion arose (a positive answer to question 4) would solve these problems). I decided to create a new question because I realized that the problem is more general that the ones exposed in these posts.


texts: Complexity of validity problem for Monadic First Order Logic?

texts:
Monadic First Order Logic is FOL with no function symbols, and predicate symbols restricted to arity 1. For this question, let's say that the = symbol is also forbidden. I want to know the complexity of determining if a monadic FOL sentence is valid, ideally in the form of a completeness result (say, under some notion of reduction that the class NE is closed under).

According to this presentation, it was proved a century ago that if S is a satisfiable monadic FOL sentence, then S has a model of size at most $2^kr$, where $r$ is the number of variables and $k$ is the number of predicate symbols. From that it follows that the problem is in $NTIME(2^{n^2})$ and $SPACE(2^n)$: First, guess a (respectively, try every) structure of size $\leq 2^k r \leq 2^n n$. Then evaluate the sentence on that structure in the most straightforward deterministic way, by enumerating all the elements of the structure at every quantifier, and evaluating the quantifier-free parts of the sentence in polynomial time. That takes time $(2^n n)^r poly(n)$, which is in $O(2^{n^2})$. On the other side, it is easy to show that the problem is hard for $PSPACE$.


texts: Parallel algorithms for directed st-connectivity

texts: Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for directed st-connectivity ? Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial). Are there any $o({\log}^2{n})$ time parallel algorithms known for any special cases of directed st-connectivity ?


texts:
$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational complexity theory.

Let $v_1, v_2, \dots, v_N$ be points in $\{0,1\} \subseteq \mathbb{R}^n$.  Does every facet of the convex hull of these points lie on a supporting hyperplane $$\sum_{i=1}^n a_i x_i = t,$$ where every coefficient $a_i$ is either 0 or 1?
If not, how many bits are needed to express the coefficients $a_i$ of a facet hyperplane?


texts:
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The only part I don't understand is on page 4-5, when they claim that $\tilde x(\tilde \delta(U)) \geq \tilde x(\tilde \delta(X' \setminus W')) + \tilde x(\tilde \delta(W \setminus X))$. I don't understand why this doesn't hold with equality, since the values on copied edges in the duplicated graph are identical.
Can someone clarify this proof? Is it a mistake?


texts: Universal Turing Machines in "Computational Complexity" by Papadimitriou

texts:
The first part of this question has been solved (see comments).

In the book "computational complexity" by Papadimitriou, a Universal Turing Machine is given. But this machine is not concrete, in the sense that it contains variable parameters. For example, the states of the input Turing Machine are represented as binary strings of fixed length. Hence, no matter how long we let this length be, there will always be Turing Machines with so many states that they cannot be represented. Can this machine then really be called a UTM, or at least a template for a UTM?

I also read that a 2-state, 3-symbol UTM has been discovered. This would mean that the action table contains only 6 entries. Am I right in my conjecture that such a machine must have a very complex encoding of the input TM?


texts: Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

texts:
While searching The information System on Graph Classes and their Inclusions, I found several graph classes for which  the Hamiltonian Cycle problem is NP-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are bipartite maximum degree 3 graphs, maximum degree 3 grid graphs, and 2-connected cubic planar graphs. Also this phenomena applies to circle graphs and triangular grid graphs.

  Is there an update to the complexity of Hamiltonian path problem on those classes? Is there an explanation for this phenomena?

EDIT: I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.


texts: Clarification regarding Bounded Quadratic Congruence Problem

texts:
Given: 3 positive integers $a, b, L$.
Problem: Is there a positive integer $x < L$ such that $x^2 \equiv \ a (mod\ b)$?

The above problem is NP Complete (as mentioned in G&J) even if we have the factorization of $b$ given. My query is the following:

Suppose we have a promise/condition imposed that, the number of total occurrences of the residue $a$ is polynomially bounded w.r.t. number of prime factors in $b$, i.e. the number of occurrences of $a$ is always less than ${pct}^C$.

$pct$ = number of Prime factors of $b$ , $C$ = some positive integer constant.

Does this problem still remain NP-Complete or it becomes P time solvable.

Essentially, does the number of times a residue occurs is what makes this problem difficult or it doesn't matter and its just dependent on the number of prime factors in $b$?


texts:
Say that a function $f$ is a RAMSEY COLORING if on unary input $n$, it returns a complete graph on $n$ vertices with its edges colored red and blue without a monochromatic clique of size $10\log n$.
The big open problem is to prove or disprove that there is an $f\in$ RAMSEY COLORING such that $f\in FP$.
Is there anything known about smaller complexity classes, like an $f\in$ RAMSEY COLORING such that $f\in NC$ or $f\in LOGSPACE$?

I suppose $LOGSPACE$ is out of reach, but $f\notin AC_0$ seems to be trivial.


texts: Agnostic learning over arbitrary distributions

texts:
Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:
$$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$$
and let:
$$OPT(C,D) = \min_{f \in C}\ err(f,D)$$
Say that an algorithm $A$ agnostically learns $C$ over any distribution, if for any $D$ it can with probability $2/3$ find a function $f$ such that $err(f,D) \leq OPT(C,D) + \epsilon$, given time and a number of samples from $D$ that is bounded by a polynomial in $d$ and $1/\epsilon$.

  Question: What classes of functions $C$ are known to be agnostically learnable over arbitrary distributions?

No class is too simple! I know that even monotone conjunctions are not known to be agnostically learnable over arbitrary distributions, so I'm just looking for nontrivial classes of functions.


texts: Fast Computation of First k Eigenvectors of Graph Laplacian

texts:
I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$

Algorithm(s) to efficiently estimate the first $k$ (smallest in magnitude) eigenvectors of $L$ -- and, the time complexity of such an algorithm. Denote these eigenvectors by $U_{:,1:k} \in \mathbb{R}^{n\times k} $.
For $1 \leq i, j \leq n$ and $p \in \{1,2\}$, can we determine whether or not $||U_{i,1:k} - U_{j,1:k}||_p$ is a close estimate of $||U_{i,:} - U_{j,:}||_p$ up to small multiplicative error, with high probability?

Edit 1: Based on helpful comments, I've corrected Q2 to hopefully something more accurate.


texts: Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?

texts:
Is the following problem in PTIME, or coNP-hard:

Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ and $\vee$). Decide whether $e_1 \equiv e_2$, that is they have the same value for all assignments to the variables.

If both expressions would be given in DNF, then the problem is in PTIME since we could first lexicographically order the conjunctive clauses and compare. But bringing an arbitrary expression to DNF can blow up exponentially. A similar argument seems to hold for binary-decision-diagrams.

Obviously, the problem is in coNP.

I was Googling around a fair amount, but couldn't find any answer.

Apologies for the elementary question.


texts:
Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer queries of the form "distance between $u$ and $v$" in time O(n)?

The problem seems too basic to be unsolved.


texts:
I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not.

The background is that I am a "practitioner" (PhD student, I don't study CS theory) but I have a reasonable foundation in undergraduate algorithms and math. Nevertheless, discussions with theorists are usually very surface-level, as if they're afraid to use mathematical terms with me in case I get scared. In reality, I'm perfectly comfortable with and interested in theory, but I'm just not used to discussing it so I probably don't always use terms that would flag me as "theorist". I find that the direct approach ("please tell me the details") doesn't always work, particularly if the theorist in question has assumed a condescending tone that sets a high bar for expertise (this happens often).

As theorists, if you filter people in this way, do you have recommendations for how a practitioner can avoid being "flagged" by your filter?


texts: MSO properties, planar graphs and minor-free graphs

texts:
Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known algorithmic meta-theorems.

Motivated by Courcelle's theorem, I made the following conjecture :

  Conjecture : Let $\psi$ be any MSO-definable property. If $\psi$ is solvable in polynomial-time on planar graphs, then $\psi$ is solvable in polynomial-time on all classes of minor-free graphs.

I want to know if the above conjecture is obviously false i.e., is there an MSO-definable property that is polynomial-time solvable on planar graphs but NP-hard on some class of minor-free graphs ?

This is the motivation behind my earlier question : Are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g.


texts: Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. -- known problem?

texts:
Consider the following problem. Let $X$ and $Y$ be discrete random variables. The goal is to find a random variable $Z$ such that, informally, $I(Z;X)$ is high and $I(Z;Y)$ is low.

More precisely, either: $~\max_Z I(Z;X) ~\text{s.t.}~ I(Z;Y) \le c~$ or $~\min_Z I(Z;Y) ~\text{s.t.}~ I(Z;X) \ge c~$ (for some constant $c$).

This seems like a very natural, fundamental (if toy?) problem, so surely something is known about it. (I know that for $X,Y$ both with finite support, (large) linear programs can be written to solve for such $Z$, but I imagine there's a neater way.) Any pointers would be appreciated.

Thanks!


texts:
I once read in a paper: "given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm."
What is the approach to this?


texts: Number of Automorphisms of a graph for graph isomorphism

texts:
Let $G$ and $H$ be two $r$-regular connected graphs of size $n$.
Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$.
If $G=H$ then $A$ is the set of automorphisms of $G$.

  What is the best known upper-bound on the size of of $A$?
  Are there any results for particular graph classes (not containing complete/cycle graphs)?

Note:
Constructing the automorphism group is at least as difficult
(in terms of its computational complexity) as solving the graph isomorphism problem.
In fact, just counting the automorphisms is polynomial-time equivalent to
graph isomorphism, c.f. R. Mathon, "A note on the graph isomorphism counting problem".


texts: Name of the problem to find the maximum number of characters covered by a set of strings

texts:
I am interested in the following problem. One has two collections $Q$ and $T$ of strings, and a set $A$ of alignments of strings in $Q$ to strings in $T$. I want to find a subset $A'$ of $A$ that (i) involves each element of $Q$ only once and (ii) maximizes the total number of characters in elements $T$ that are covered by an alignment in $A'$.

(To be precise: Let $a$ be an alignment in $A$. We can think of $a$ as a tuple $(q,t,f)$ where $q\in Q$, $t\in T$, and $f : \mathcal I_a \to \mathcal J_a$ is a bijection such that $f(i)=j$ if $a$ aligns the $i$th character of $q$ to the $j$th character of $t$. Here $\mathcal I_a \subset \{1,2,\dots,|q|\}$ and $\mathcal J_a \subset \{1,2,\dots,|t|\}$, where $|\cdot|$ means length. We can think of characters in elements of $T$ as pairs $(t,j)$ where $t\in T$ and $j\in\{1,2,\dots,|t|\}$. We say that $(t,j)$ is covered by an alignment in $A'$ if there exists $a=(q,t',f)\in A'$ such that $t=t'$ and $j\in\mathcal J_a$. (Note that there might exist several such $a\in A'$.) Let $\chi(t,j,A') = 1$ if such an $a\in A'$ exists, and 0 otherwise. We want to maximize the cardinality of $\{(t,j) : \chi(t,j,A')=1\}$ over $A'\subset A$ such that for all $q\in Q$, there exists at most one $a=(q',t,f)\in A'$ with $q=q'$.)

My question: What is a name for this problem, if any? Thanks in advance! I guess that it is related to maximum matchings and maximum coverage, but it's not quite the same as either.


texts: One way randomised communication complexity of disjointness

texts:
I am looking for a reference for the (classical) one way randomised communication complexity of disjointness when the universe can be large. Say Alice and Bob both have sets of size $m$ chosen from a universe of size $U$ and Bob wants to determine if the intersection of their sets is empty or not.  I would like prob of error $<1/3$, say.

I can find the standard $\Omega(m)$ bit lower bound and some work on two-way communication complexity, but is there a reference for something tighter for one-way?

EDIT: I should have specified that I am interested in the private  randomness (not public coin) model.


texts: 3-colourability of Eulerian maximal planar graph

texts:
The following paragraph is from this answer by David Eppstein (emphasis mine).

A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles).

(A maximal planar graph is a graph with a planar embedding such that every face is a triangle).
I don't quite understand how emphasized part works as a proof. Let $G$ be a maximal planar graph. If $G$ is 3-colourable, then the 3-colouring is unique (upto swapping of colours) because in every diamond subgraph of $G$, both degree-2 vertices of the subgraph should get the same colour. I suppose this suggests an algorithmic method for testing 3-colourability of $G$ namely (i) pick a triangle, (ii) give a 3-colouring to it arbitrarily, (iii) repeatedly extend it to adjacent triangles (assuming there is no inconsistency), and (iv) finally verify that the assignment is indeed a 3-colouring. If there is a vertex of odd degree, we will not succeed in assigning colour to all vertices. My question is this:-
How can we guarantee that the assignment will be consistent provided all vertices have even degree?
Note: I don't see how Eulerian property (aka all vertices having even degree) ensures consistency of the assignment. I am asking this as a new question rather than a comment to the linked answer because he was answering a different question.


texts: Inferring an LP cost vector from its solution

texts:
Say I have the following linear programming formulation in standard form:

\begin{equation*}
\begin{array}{rl}
    \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}}        & \mathbf{c}^T\mathbf{x} \\
    \mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\
                & \mathbf{x} \ge 0,
    \end{array}
\end{equation*}

with $\mathbf{x}^*$, $\mathbf{A}$ and $\mathbf{b}$ known, but $\mathbf{c}$ unknown.

Are there any known methods for computing $\mathbf{c}$ ?


texts: Reference for Turing to many-one reductions

texts:
I am looking for a reference on `reducing' Turing reductions to many-one reductions.  I have in mind a statement of the following form (similar enough statements would also satisfy me):

Theorem.  If $\mathsf{A}\leq_T^f \mathsf{B}$, then $\mathsf A\leq_m^{2^f}\mathsf B^{tt}$.

where "$\leq_T^f$" and "$\leq_m^f$" denote respectively Turing and many-one reductions in deterministic time $f(n)$, and "$\mathsf{B}^{tt}$" denotes a `truth table' variant of the language $\mathsf{B}$, which evaluates a Boolean combination of checks "$x\in\mathsf{B}$".

Proof idea for the statement:  Simulate the $f(n)$-time bounded oracle Turing machine used in the Turing reduction: it's easy enough to obtain a nondeterministic Turing transducer also in time $f(n)$ that guesses the answers of the $\mathsf B$ oracle and writes a conjunction of checks "$x\in\mathsf B$" or "$x\not\in\mathsf{B}$" on the output, to be evaluated by an $\mathsf B^{tt}$ machine.  This transducer can be determinized by exploring both outcomes of the oracle calls, and handling them through disjunctions in the output; it now works in time $2^{f(n)}$.

Oddly enough, I cannot seem to find any related result in complexity textbooks.

Edit: renamed "$A\mathsf B$" into "$\mathsf B^{tt}$" to emphasize the relation with truth tables, as pointed out by @MarkusBläser.


texts: What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?

texts: I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.


texts: Complexity of Tensor Rank over an Infinite Field

texts:
A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank one tensors that sum to $T$. A vector and matrix are tensors of degree 1 and 2 respectively.

The elements in $T$ come from a field $\mathbb{F}$. If $\mathbb{F}$ is finite, then Håstad proved that deciding if the rank of a degree 3 tensor is at most $r$ is NP-complete, but when $\mathbb{F}$ is an infinite field like the rationals $\mathbb{Q}$, he gives (or cites) no upper bound.

  Question: What is the best known upper bound for the complexity of deciding if the rank of a degree 3 tensor $T$ over $\mathbb{Q}$ is at most $r$?


texts: Computing the Fourier expansion of the complete quadratic function

texts:
I am working through Ryan O' Donnell's book on the analysis of Boolean functions. One of the exercises (1.1) is to compute the Fourier series of the `complete quadratic function' on $\mathbf{F}_2^n$

$$ CQ(x) = (-1)^{\sum_{i < j} x_i x_j} $$

Without any fancy harmonic analysis terminology, the problem asks us to calculate the expectations

$$\widehat{f}(S) = \mathbf{E}[CQ(X)(-1)^{\sum_{i \in S} x_i}]$$

for any subset $S \subset \{ 1, \dots, n \}$, where $X$ is uniformly distributed on $\mathbf{F}_2^n$, in which case we can write

$$ CQ(x) = \sum_{S \subset [n]} \widehat{f}(S) (-1)^{\sum_{i \in S} x_i}$$

An important first step to solving the problem is noticing that $CQ(x)$ depends only on the number of indices $i$ such that $x_i = 1$. That is, $CQ(x) = 1$ if and only if $n(n-1)$ is divisible by 4. However, I can't seem to get anywhere from this. This makes it easy to compute the expectation of $CQ(x)$ (though I can't seem to see a nice `general' formula, I've just broken down the analysis depending on $n$'s congruence class modulo 4). In order to calculate $\widehat{f}(S)$ in general, I've tried calculating the expectation by condition on both $(-1)^{\sum_{i \in S} x_i} = \pm 1$, and conditioning on the latter gives (assuming $S$ has $m$ elements)

$$ \mathbf{E}(CQ(X) (-1)^{\sum_{i \in S} x_i} = (1/2^n) \sum_{k = 0}^m \sum_{l = 0}^{n-m} (-1)^k {m \choose k} {n - m \choose l} r_{k+l} $$

where $r_x = 1$ if $x$ is congruent to 0 or 1 (mod 4), and $r_x = -1$ if $x$ is congruent to 2 or 3 (mod 4). But my knowledge of binomial identities is really rusty and I don't know how to reduce the sum any further. Any guidance?


texts:
The inspiration for this question is the following (vague) question: What are the programming language/logical foundations for having an AI which could reason about its own source code and modify it?

This isn't at all rigorous, so here is my attempt to extract a concrete question out of it. There are two things I'm interested in:

(A) A programming language P that can represent and manipulate its own programs as a datatype Program (e.g., as an AST). (If desired, a object of type Program can be converted into a String, which is the text of a valid program in that language. This would be the opposite of what a compiler does.)

(B) A method to reason about what a program in language P does. Here are two levels I'm thinking about it:

Another language Q (with theorem proving capabilities) which models what a P-program does. It should be able to express and prove statements like "the outcome of running Program p is foo."
A way to reason about what a program p:Program does in the language P itself. (So we are taking P=Q above.)

To what degree has something like this been implemented, or what is progress in this direction? What are the practical obstacles? In light of the original intention of the question, what is the best way to formalize the problem?

*

As the answers show (thanks!), both (A) and (B1) can be done separately, though it seems doing them together is more of a research question.

Here were some of my first thoughts on the question (warning: rather vague). See also my comments on Martin Berger's answer.

I'm interested in the programming language modeling the same programming language, rather than a simpler one (so P=Q above). This would be a "proof of concept" of a program being able to "reason about its own source code." Dependently typed programming languages can give guarantees about the outputs of its functions, but this doesn't count as "reasoning about its own source code" any more than a "Hello world!" counts as a quine in a language that will automatically prints out a naked string---there needs to be some kind of quoting/self-reference. The analogue here is having a datatype representing Program.

It seems like a rather large project - the simpler the language, the harder it is to express everything within it; the more complicated the language, the more work has to be done to model the language.

In the spirit of the Recursion Theorem, a program can then "get" its own source code and modify it (i.e., output a modified version of itself). (B2) then tells us that the program should be able to express a guarantee about the modified program (this should be able to recurse, i.e., it should be able to express something about all future modifications-?).


texts: Reordering data (set of strings) to optimize for compression?

texts:
Are there any algorithms for reordering data to optimize for compression?  I understand this is specific to the data and the compression algorithm, but is there a word for this topic?  Where can I find research in this area?

Specifically, I have a json list of 1.5 million strings, and I want to reorder the strings so that gzip (for HTTP) compression is optimized.  Sorting the strings does pretty well, but I don't really know if that is optimal.


texts: Locality Sensitive Hashing - meaning of a block

texts:
I'm reading one of the early LSH papers and I'm a little confused by the meaning of a "block". In particular, in the proof of theorem 1 in section 3.2 (p 522), what are the blocks being pointed to? Just hash buckets? The step I'm having trouble with is "The expected number of blocks allocated for $g_j$ which contain exclusively points from $P'$ does not exceed 2" - I'm having trouble parsing this sentence, even though the paper makes it sound trivial.

Am I missing something obvious?


texts: Can we confirm that 2-SAT can indeed be transformed into Horn-SAT in this manner?

texts:
In the question, Translating SAT to HornSAT, Martin Seymour gives a method due to Joshua Grochow.  It transforms 2-SAT into Horn-SAT, by creating a variable for every possible 2-SAT clause.  Then, if a clause (or new variable) follows from two other clauses (variables) from "a single resolution step", it adds this implication to the formula.  Finally, the unit clauses are added, along with a clause signifying not empty.

Can someone please explain, in detail, why we add clauses from "single resolution steps"?  Am I correct in assuming that this means a single resolution step from unit propagation?  Also, and perhaps most importantly, can someone prove that this method works?

Essentially, I'd like to know everything I can to ensure that I can implement this method, and also prove that it works.  I'm also wondering if perhaps this method can be found in the literature somewhere.


texts:
Given an undirected graph $G=(V,E)$ with non-negative node-weights $\text{w}(v)$, $v \in V$,
I want to find a spanning tree $T$ of $G$ with minimum "cost"
$\text{w}(T) = \sum_{v\in V} \deg_T(v)\cdot \text{w}(v)$, where $\deg_T(v)$ is the degree of $v$ in $T$.

Can this spanning tree problem be solved efficiently?


texts: Are types propositions? (What are types exactly?)

texts:
I've been reading a lot on type systems and such and I understand roughly why they were introduced (in order to resolve Russel's paradox). I also understand roughly their practical relevance in programming languages and proof systems. However, I'm not entirely confident that my intuitive notion of what a type is, is correct.

My question is, is it valid to claim that types are propositions?

In other words the statement "n is a natural number" corresponds with the statement "n has the type 'natural number'" meaning that all the algebraic rules that involve natural numbers hold for n. (I.e. Said another way, algebraic rules are statements. Those statements that hold true for natural numbers also hold true for n.)

Then does this mean that a mathematical object can have more than one type?

Furthermore, I know that sets are not equivalent to types because you cannot have a set of all sets. Could I claim that if a set is a mathematical object similar to a number or a function, a type is a sort of meta-mathematical object and by the same logic a kind is a meta-meta-mathematical object? (in the sense that every "meta" indicates a higher level of abstraction...)

Does this have some kind of link to category theory?


texts:
It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function.

What other models are there that are also universal function approximators


texts: How do database aggregations form a monoid?

texts:
On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package.

The github page has some clues:

  Implementations of Monoids for interesting approximation algorithms,
  such as Bloom filter, HyperLogLog and CountMinSketch. These allow you
  to think of these sophisticated operations like you might numbers, and
  add them up in hadoop or online to produce powerful statistics and
  analytics.

and in another part of the GitHub page:

  It was originally developed as part of Scalding's Matrix API, where
  Matrices had values which are elements of Monoids, Groups, or Rings.
  Subsequently, it was clear that the code had broader application
  within Scalding and on other projects within Twitter.

Even Oskar Boykin of Twitter chimed in:

  The main answer is that by exploiting semi-group structure, we can
  build systems that parallelize correctly without knowing the
  underlying operation (the user is promising associativity).

  By using Monoids, we can take advantage of sparsity (we deal with a
  lot of sparse matrices, where almost all values are a zero in some
  Monoid).

  By using Rings, we can do matrix multiplication over things other than
  numbers (which on occasion we have done).

  The algebird project itself (as well as the issue history) pretty
  clearly explains what is going on here: we are building a lot of
  algorithms for aggregation of large data sets, and leveraging the
  structure of the operations gives us a win on the systems side (which
  is usually the pain point when trying to productionize algorithms on
  1000s of nodes).

  Solve the systems problems once for any Semigroup/Monoid/Group/Ring,
  and then you can plug in any algorithm without having to think about
  Memcache, Hadoop, Storm, etc...

How are Bloom filters / hyperloglog / countminsketch like numbers?

How is it that database aggregations have a monoidal structure?
What does this monoid look like?  Do they ever have group structure?

Literature references would be helpful.


texts: Finding a Travelling Salesman/Vehicle Routing with cheap and expensive distances

texts:
If I need to find a shortest road (not great-circle) route between ~11,000 real world lat, long coordinates within a reasonable period of time. To further complicate things, there is no necessary starting point (however starting on one of the points at the edge would be beneficial), and the route shouldn't return to the initial location.

Clearly it is impractical to poll an online api with 11,000^2 requests for the distance between every point. Google maps is limited to 1000 objects per day (Presumably 2 objects required per distance) as a casual user, and 100,000 as a business user. Bing maps does not list a casual limit (although its likely after a point they would blacklist you), and the business limit is 100,000 requests per day.

To accomplish this using a heuristic algorithm I expect that I would need to utilise two tiers of distance using the great-circle algorithm for a cheap cost and an API request for an expensive cost. To provide greater accuracy than calculating the route using great-circle and finding the accurate distance of that route.

There are numerous heuristic approaches to the travelling salesman, however I have not yet found any that would support a two tier cost approach. Does anyone have experience with implementing a similar algorithm? or Suggestions of how you would implement it?

Thanks


texts:
I'm looking through some lectures and books to understand the PCP verifier constructed by Hastad. I noticed that the subtle difference of an adaptive or non-adaptive PCP verifier seems to correspond to verifier with perfect or non-perfect completeness.

In "A tight characterization of NP with 3 query PCPs" the authors point out that there are (due to Trevisan and Zwick) strong restrictions using non-adaptive PCPs, e.g.
$$P = PCP_{1, \frac{5}{8} + \epsilon}(log(n), 3)$$
and they construct an adaptive PCP finally showing that $NP = PCP_{1, \frac{1}{2}+\epsilon}(log (n), 3)$.

Then again the definition in the textbook from Arora, Barak (and in other lectures) uses explicitly non-adaptive verifiers with perfect completeness (well, with soundness $\frac{1}{2}$).

Could someone give further explanations on this? Are different definitions with soundness paramter $\frac{1}{2}$ equivalent?

And one further question: Is it possible to construct a linear dictatorship test (as basis of the Hastad Verifier) which is complete AND non-adaptive?


texts: Finding an index set so that row sums are positive

texts:
Assume $A$ is a $n$-dimensional matrix of real numbers. The diagonal entries are non-negative, and all other entries are non-positive. I would like to find a subset $I \subseteq \{1, 2, \ldots n\}$ of maximum size such that the sub-matrix of $A$ defined by $I$ has positive row sums, for every row. The sub-matrix of course only includes entries $A_{ij}$ such that $i, j \in I$.

Now, this problem generalizes max independent set, so I am not expecting anything great. Just wondering if anything at all, algorithmically, is known about this problem. Even special cases.


texts: Computing the convex hull of several polyhedra

texts:
Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities.
How easy is it to compute an efficient description (half-space representation, or vertex representation) of the convex hull:
$$
conv(K_1,...,K_n).
$$
Is there an algorithm running in time $poly(n)$,  $poly(n,m)$ ?

Similarly, given membership oracles to $K_1,...,K_n$ can one determine in polynomial time, w.r.t. these oracles, whether a point $x$ belongs to $conv(K_1,...,K_n)$?


texts: What's new in sparse eigensystems solution

texts:
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are needed, but with high precision. Currently I am using Arpack (Arnoldi method with shift-inverse when precision is preferable or spectrum folding when size is important). As an option plan to use TRLan (thick restart Lanczos) and try Chebyshev filtering instead of spectrum folding.

Probably, newer methods exist for this purpose? I am not an expert in CS, maybe somebody has some clues on recent progress in this field?


texts:
Assume that NP=co-NP and polynomial $p(x)$ bounds the length of the proof of unsatisfiability for a 3-CNF instance $x$. Then are there any results on what form any proof of unsatisfiability for $x$ of length $\leq p(x)$ can take?
I.e. in general, would such a proof have to, for instance, use the full power of second-order logic over infinite structures (I am aware that the proposition to prove - that a formula is unsatisfiable can be expressed in second-order logic over finite structures but intermediate steps in the proof to get to that might require reasoning over infinite structures).
Since there is no effective, complete and sound system of inference for second-order logic, would it be possible to use such a result to prove NP $\neq$ co-NP?


texts: About increasing the objective values of certificates for Max-Clique SDP

texts:
Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and produce for this graph a certificate for the SDP which corresponds to having found a clique of size $n^\alpha$ in $G_1$ for some $\alpha \in (0,1]$.

Now using this certificate (or any other means!) is it possible to construct another graph $G_2$  of size $N$ (might be necessary that $N>n$) and a certificate for it for this same SDP which would correspond to having found a $N^{ 1-\epsilon }$ size clique in $G_2$ for some $1 - \epsilon > \alpha$? (its okay even if $G_2$ is shown to exist in some probabilistic sense)

Are there examples of doing such a blow-up of the objective value for a Max-Clique SDP?

Not sure if its immediately related but putting this out here : Is there any obvious reason why this very famous paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf does not deal with Max-Clique? Isn't it true that the complement of the Max-Independent-Set integrality gap instance does not give the integrality gap instance of Max-Clique?


texts:
This is a followup question to: Lower bound on the largest restrained cubic subset

How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$

This question may be seen as a generalization of counting simple cycles in $K_{n,n}$, via the hypergraph description of xyz-graphs given in the linked article. With that in mind, the problem reduces to solving for the number of "Hamiltonian" xyz-graphs, which in our generalization will be xyz-graphs (thought of as sets of hyper-edges) which touch every 2-edge in $K_{n,n,n}$ exactly twice. One example of such a Hamiltonian xyz-graph is provided in the linked question and at https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html and is given by the set:

$\{(x,y,z) \ | \ x+y+z=0\} \ \cup \ \{(x,y,z) \ | \ x+y+z=1\}$

where addition is done mod n. Let the number of Hamiltonian xyz-graphs of $K_{n,n,n}$ be $H(n)$. Now we may simply look at how many copies of $K_{i,i,i}$ exist in $K_{n,n,n}$. This is simply ${n \choose i}^3$, which gives us the formula:

$
C(n) = \sum\limits_{i=2}^n {n \choose i}^3H(i)
$

Note that $H(n)= \frac{n!(n-1)!}{2}$ in the 2-dimensional case of $K_{n,n}$. It seems like we could use a similar strategy for the 3-dimensional case and end up with something along the lines of $\frac{n!^2(n-1)!^2}{4}$ which would lead to

$
C(n) = \frac{1}{4}\sum\limits_{i=2}^n \frac{(i-1)!}{i}(n)_i^3
$

However I'm fairly certain this number is far too large, so there must be a number of extra constraints when building these Hamiltonian cycles.

EDIT: Unfortunately there are trivial examples of xyz-graphs which are not hamiltonian for some n, meaning that the above would only give a lower bound.


texts: Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron

texts: I am interested in the upper bound of the number of inequalities to describe the integer hull of a polyhedron. That is, given an integer programming problem with n inequalities which construct a polyhedron P, we often adding some inequalities to get the integer hull P_I of P. Then what is the maximum number of inequalities needed to describe this P_I? I have known that there are some conclusions on this topic but I don't what they are. I need some paper about it. Please tell me if you know it.


texts:
This is a question in the spirit of this one where I answered that it is important to keep track of what you have done something, why you have done it and what is not working.
I personally use notebooks for that purpose, but it has several drawbacks: first I need a lot of storage surface, second when I travel I cannot access my data, and finally this is not collaborative. It has however a strong plus: the notebook can be used as the equivalent of a laboratory notebook (you just have to find somebody to sign each page...).

So, I am interested in knowing how other researchers proceed for that matter. For example, is there any specific software that solve all the issues I mentioned?


texts:
I'm a master student focused on distributed systems but also interested on theoretical computer science. I was wondering if there is a formal representation of a distributed system on top of a turing machine? That is, is it possible to extend (make a variant) the concept of a turing machine to take advantage of distributed computing?

One idea, is to make a shared tape (something similar to Tuple Space) between TM.


texts: Generalizing a set of positive and negative examples through DFAs

texts:
Possible Duplicate:
  Is finding the minimum regular expression an NP-complete problem?

Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two disjoint finite sets of words over $\Sigma$. I say that a deterministic finite automaton (DFA) over $\Sigma$ is acceptable if it accepts all words of $P$ and rejects all words of $N$ (the behavior on words in $\Sigma^* \backslash (P \cup N)$ is unspecified).

What is the complexity, given $P$ and $N$, of building a minimal acceptable DFA? Can we say that the number of states of a minimal acceptable DFA expresses an interesting intrinsic property of $P$ and $N$? Does a minimal acceptable DFA generalize the sets $P$ and $N$ in a useful way? In other words, does the behavior of a minimal acceptable automaton on $\Sigma^* \backslash (P \cup N)$ reflect a reasonable rule to distinguish $P$ and $N$?

Here is a simple example to explain why I ask this question. If P = {abc, ade, aaaac} and N = {bac, bbe, baabb}, then a minimal acceptable DFA would be the one which only reads the first letter and either accepts or rejects; this represents the reasonable rule "words starting by 'a' are in $P$, words starting by 'b' are in $N$". Likewise, if $P = \{aaaa, cab, baa, aab\}$ and $N = \{aba, abb, bba, bb, cbac\}$, I would expect the minimal acceptable DFA to accept or reject based on the second letter. I wonder what is the expressiveness of DFAs to generalize this sort of examples.


texts: The Maxwell's Demon and Computer Science

texts: What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I have an impression that this argument has some flaw, because all the sources I know use natural language. However, I would like some source that demonstrates formally.


texts:
Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a sense this is similar to finding a spanning tree inside a graph. Furthermore we usually don't want just an arbitrary expander, we have some cost function on the edges and we want to minimize the total cost of the edges we select for our expander (similar to minimum wight spanning tree problem). Is there a good algorithm for this purpose? Or is this problem computationally difficult to solve?

  Minimum Expander Problem:
  Given a graph $G$ with weights for its edges, and two numbers $d$ and $h$,
  Find a a sub-graph of $G$ which is expander of degree $d$ and expansion $h$ and
  has the minimum total weight among such sub-graphs.

We can relax the problem to get an approximation version (e.g. the total weight is at most twice of the optimal weight, and the sub-graph is close to a $d$ and $h$ expander.)

What is known about these problems?


texts: Identify all of the non-overlapping rectangular regions of a simple concave polygon

texts:
I am looking for an algorithm to identify all of the rectangles bounded by two parallel edges of a polygon. The rectangle must remain inside of the polygon at all times. My polygon is simple and will never have an acute angle. I have looked for algorithms already, but they seem to only work for convex or orthogonal polygons. Is there a good approach to this. At this point, I am thinking I should group all edges by parallelity and inspect those sets to find rectangular regions. It sounds bad.

This post is related to another post: Cover a Concave Polygon with a minimum number of rectangles

I am hoping to split up the questions so I can attract better answers.


texts: Proof for multiplicative dominance of universal probability distribution

texts:
I'm looking for the proof of the Leonid Levin theorem that states that the universal prior distribution function multiplicatively dominates all other functions of its type.
The original article is Levin 1974 but it is in Russian
Thanks


texts: L1 - embeddability of metrics supported on the Hypercube

texts:
I am quite new to the area of metric embeddings so this question might turn out to be extremely easy.

Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge of the boolean hypercube has a non negative distance associated with it and the metric is defined by the length of the shortest path according to the distance function between any two vertices. Can we put upper bounds/lower bounds on the distortion when we embed such a metric into $l_1$ ?

Any references would be highly appreciated.


texts: Asymptotic Approximation to Number of Knapsack Solutions

texts:
Is there an asymptotic approximation to the fraction of sets satisfying a knapsack feasibility constraint?

More precisely, imagine I have a large number $n$ of items with bounded weights $X_1,...,X_n \in [0,1]$. For a given bound $Y$, I want to compute the fraction of sets $S \subset \{1,...,n\}$ which satisfy the feasibility constraint $\sum_{i \in S} X_i \leq Y$. That is, I want to compute:

$$N(X_1,...,X_n,Y) =  \frac{\# \{S: \sum_{i \in S} X_i \leq Y\}}{2^n}$$

I want to understand how the ``partial derivatives'' of $N$ behave when $X$ and $Y$ change. That is, I want to compute some analogue of $\frac{\partial N}{\partial X_i}$ or $\frac{\partial N}{\partial Y}$. As defined, the function $N$'s partial derivatives are not very interesting: the function is constant, except at regions of discontinuity where the number of feasible sets changes, and at those points the derivatives do not exist.

More concretely, I want to know if there's a function $F(X_1,...,X_n,Y,n)$ such that

F is differentiable in $X_1,...,X_n,Y$
$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y)} = 1$

I know that, when $X_1,...,X_n = 1$, then $N(X_1,...,X_n,Y)=\sum_{k=0}^{\lfloor Y \rfloor} \frac{\binom{n}{k}}{2^n}$, which converges to the normal CDF $\Phi(Y; \frac{n}{2}, \frac{n}{4})$. But I don't know if this kind of approximation generalizes to arbitrary bounded $X_i$.


texts: Minimum cut through vertices/nodes - not edges

texts: we all know and love s-t minimum cut algorithms, but they all cut through the edges in the graph. Are there any variants that cuts through nodes?


texts:
Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability $(1-p)$.  Now repeat this experiment $n$ times, and let the total number of positive outcomes (heads) be $k$.

Now, given $n$ and $k$ but not $p$ what is the probability that the Bernoulli experiment (flipping the coin) again will result in a positive outcome (head)?

If $n$ and $k$ were 0 this would be an easy task: as there is no further information and the outcomes could be defined the other way around, it is symmetric and thus $p=0.5$.

Otherwise it's a little more complicated (the dependency on n ($|n$) is omitted for clarity).
The expected probability is:
$\langle p |k\rangle = \int _0 ^1 p\cdot f(p|k) \,\mathrm{d} p$.

Using Bayes' theorem gives
$f(p|k) = p(k|p) \frac{f(p)}{p(k)}  $
and marginalization gives $p(k)=\int_0^1 p(k|p) \cdot f(p) \,\mathrm{d} p$. The Binomial distribution further tells us that $p(k|p)=\binom{n}{k}\cdot p^k \cdot (1-p)^{n-k}$. But what is the correct term for the prior of $p$, $f(p)$?

Jaynes & co. tell me to use a maximum Entropy prior.
To maximize entropy of $p$  ($H(p)=-\int_0^1 f(p) \cdot ln(f(p)) \,\mathrm{d} p$), set $f(p)=1$. But this would not maximize the entropy of $k$; the entropy of $k$ would be maximal if $p$ was $0.5$ thus if $f(p)=0$ but infinity at 0.5 (integrating to 1).

So, what is the correct prior to choose for $f(p)$? Does it depend on $n$?


texts: What hierarchies and/or hierarchy theorems do you know?

texts:
I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, from theology and sociology to biology and chemistry. Seeing that the amount of information is vast, I hope that I could ask for some help by this community. Of course, I don't want you to do a bibliographic search for me, but rather I am asking for two kinds of information:

Hierarchies and hierarchy theorems that are the result of your work or the work of your colleagues or other people you are familiar with and you think that are not that well known. This could be for example a hierarchy theorem for an obscure computation model that you're interested in or a hierarchy of specific classes, e.g. related with game theory.
Hierarchies and hierarchy theorems that you deem absolutely necessary to be included in a survey of this kind. This would probably be known to me already, but it would be useful to see what hierarchies you consider more important and why. This could be that of the kind "I deem $PH$ very important because without it we wouldn't be able to do this kind of research" or "Although not so well known, in logic-based TCS we constantly use this hierarchy and I deem it an important tool." . And yes I do believe that people from logic have a lot of hierarchies to mention, however keep in mind we are talking about hierarchies of problems.

I will keep an updated list here:

$DTIME$ Hierarchy
$NTIME$ Hierarchy
$SPACE$ Hierarchy
Arithmetical (also known as Kleene) Hierarchy
Hyperarithmetical Hierarchy
Analytical Hierarchy
Chomsky
Hierarchy
Grzegorczyk hierarchy
and the related: Wainer hierarchy
(fast-growing) , Hardy hierarchy
(slow-growing) and the Veblen
hierarchy
Ritchie's hierarchy
Axt's hierarchy (as defined in Axt63)
The Loop Hierarchy (defined in MR67)
$NC$ ($AC$,$ACC$) Hierarchy
The depth hierarchy, as defined in Sipser83
Polynomial Hierarchy ($PH$) and the less refined Meyer-Stockmeyer hierarchy (no dinstinction between quantifiers)
Exponential Hierarchy ($ELEMENTARY$)
$NP$-Intermediate hierarchy
(Ladner's theorem)
The not-so-sturdy $AM$ (Arthur-Merlin)
The $W$ (Nondeterministic Fixed-Parameter) hierarchy and the related Alternating W hierarchy ($AW$-hierarchy) and $W^{*}$-hierarchy (W with Parameter-Dependent Depth)
Counting Hierarchy
Fourier Hierarchy
Boolean Hierarchy (over $NP$) , also equal to the Query Hierarchy (over $NP$)
Hierarchies for property testing, as seen in GoldreichKNR09
The dot-depth hierarchy of star-free regular languages
$BP_{d}(P)$ : The classes solvable by polynomial size branching programs, with the additional condition that each bit of the input is tested at most d times, form a hierarchy for different values of $d$
The time hierarchy for Circuit Complexity
The polynomial hierarchy in communication complexity

Note: If you do not want to be mentioned exclusively, please say so. As a rule of thumb, I will mention both the community and also the specific person that brings new information to light.


texts:
The previous question

Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I couldn't find a reference.

An Answer to the previous question

Use Schöning's theorem:

  Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties:

  $A_1 \notin C_1$, $A_2 \notin C_2$
  $C_1$ and $C_2$ are recursively presentable,
  $C_1$ and $C_2$ are closed under finite variations.

  Then there exists a recursive set $A$ such that:

  $A \notin C_1$, $A \notin C_2$,
  if $A_1 \in \mathsf{P}$ and $A_2\notin \{ \emptyset, \Sigma^* \}$, then $A \leq^{\mathsf{P}}_m A_2$.

For the purposes of counting dichotomy theorems, the two relevant classes of decision problems are $\text{P}$ and $\text{P}^{\#\text{P}}$.

My question

  Is there a concrete example of #P intermediate problem under some plausible assumption?
  More specifically, is there an explicit function $F$ satisfying the following conditions?
  $F\notin \mathsf{FP}$ and $F$ is not  $\# \mathsf{P}$-complete.


texts: Significance of Logic in Computer Science

texts:
I understand the significance of the theory of comptuation, for example NP-hardness of a problem signals us to forget about implementing it's exact solution and rather try approximating it.

In the similar fashion, I am not able to get intuition of how to bridge the theory and practical aspects of the course "Logic in Computer Science". Let's say, some problem does not belong to Predicate or First-order logic, and that can be rather modeled by LTL or CTL. So what does that signify?

Any links or pointers will be helpful. Thanks in advance.


texts: Function that is guaranteed to be one-way if one-way functions exist?

texts:
There is an old trick for writing down an algorithm that, if P = NP, solves SAT in polynomial time.  Essentially, one lists all polynomial time machines and multi-tasks over them.

Is there an analogous trick for one-way functions (or even one-way trapdoor functions)?  That is, can we write down a function that, if one-way functions exist, is necessarily a one-way function?

There seems to be no easy way to mimic the P = NP trick.  In that case, we can quickly recognize a solution when we get one.  But if I multi-task over all polynomial time functions, there's no obvious way to recognize a one-way function when I arrive at one.

If the answer to the above question is no, is there some kind of argument why we can't do it?  Maybe writing down such a function would somehow prove that one-way functions exist?


texts: Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

texts:
Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several (T)CS researchers. However the (possibly deep?) links to (T)CS are not so obvious.

  What are the link(s) of the EDP to (T)CS?

Here are some references that show interest of the (T)CS community in EDP:

SAT attack on EDP by Konev and Lisitsa, and reaction by Gowers; also, other connections to empirical/experimental TCS (e.g. SAT automated theorem proofs)
Intro to EDP and techniques on Lipton's blog
EDP and Differential Privacy on the Windows on Theory blog, by Talwar
EDP polymath project, with some contributions by computer scientists


texts: The Complexity of Advice in Computational Indistinguishability

texts:
One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc.

Below, we will first define this concept, and then investigate some of its properties:

Let $U=\{U_n\}$ and $V=\{V_n\}$ be two distribution ensembles, indexed by natural numbers. That is, for every $n \in \mathbb{N}$, $U_n$ and $V_n$ are probability distributions. We call $U$ and $V$ computationally indistinguishable if, for all probabilistic Turing machine $D$ which is polynomial-time in the length of its first input, all positive polynomial $p(\cdot)$, every sufficiently large $n \in \mathbb{N}$, and all advice strings $z \in \{0,1\}^*$:

$\left|\Pr_{u \leftarrow U_n}[D(1^n,u,z)=1]-\Pr_{v \leftarrow V_n}[D(1^n,v,z)=1]\right|<\frac{1}{p(n)}.$

The probability is taken over the choice of $u$ and $v$, as well as the internal coin tosses of $D$.

An equivalent definition is obtained by replacing the $\forall z \in \{0,1\}^*$ part by a quantifier over all functions $f$, and letting $z=f(1^n)$. Note that $f$ can be an uncomputable function.

The question is:

  Are there distribution ensembles $U$ and $V$ which are computationally distinguishable, but if we restrict $f$ to computable functions, then $U$ and $V$ are computationally indistinguishable?

Goldreich argued that in cryptographic settings, where all parties are modeled by probabilistic polynomial-time Turing machines, $f$ must be computable by a polynomial-time machine.

Now consider other settings, such as the case of single- or multi-prover interactive proofs. It is proven (Shamir, Babai et al.) that the parties in such systems need not be more powerful than PSPACE and NEXP machines, respectively.

  Is it rational to consider uncomputable functions $f$ in such cases? In particular, do we need to consider $f$ to be computable by machines whose power is beyond PSPACE or NEXP, respectively?


texts:
What are the examples of problems known to be in $\mathsf{AM}$ (resp. $\mathsf{MA}$) which are not known to be in $\mathsf{NP}$ nor in $\mathsf{BPP}$?

For $\mathsf{AM}$, I know the following two examples:

Graph non-isomorphism: Given two labeled graphs $G$ and $H$, are they the same graph up to permutation of the vertices?
Lower bound protocol: You are given a set $S\subset\{0,1\}^m$ such that you know that either $|S|\le\alpha|U|$ or $|S|\ge 4\alpha|U|$ for some $0\le\alpha\le 1$, and such that $S\in\mathsf{AM}$ (that is, given $y\in U$, checking whether $y\in S$ can be solved in $\mathsf{AM}$), and you have to decide whether $|S\ge 4\alpha|U|$.

For $\mathsf{MA}$, I do not know of any example.

My refined question: Do we know other problems in $\mathsf{AM}$ or $\mathsf{MA}$, not known to be in $\mathsf{NP}\cup\mathsf{BPP}$?

I am not interested in problems for which the only proof that they belong to $\mathsf{AM}$ is by using one of these two protocols.

Edit: My main motivation is to be able to give examples of $\mathsf{AM}$ or $\mathsf{MA}$ algorithms to explain what these classes are.


texts: Questions about the definition of the Quantum Turing Machine

texts:
I am trying to have a better understanding of the definition of the Quantum Turing Machine.

My questions:

If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian and is an irrational number, how do we finish writing it on the output tape?
How do we deal with the gates / unitary matrices when we are supposed to write the shortest description of a quantum program? We can always squeeze a deep quantum circuit into a single unitary matrix.


texts: Complexity of finding automorphism group of code

texts:
What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for eg. Reed Muller codes, goppa codes, quasi-cyclic codes, hadamard etc?

Here is reminder for definition of aut group for code generated by Generator matrix G

$aut({G})= (A,P) :AGP=G$


texts: Different version of approximation complexity and algorithm for densest-k-subgraph problem

texts:
In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[S]|$.

Let the optimal solution be $S^*$, the approximation problem finds another $S$ with size $k$ and the approximation ratio $\alpha$ means $|Ind[S]| = \frac{1}{\alpha} |Ind[S^*]|$. I have learned that there is an $n^{1/4 +\epsilon}$ approximation algorithm.

However，I want a different version of approximation: a $\beta-$approximation algorithm should return a vertices set $S$ of size $\beta\cdot k$ and $|Ind[S]| \ge |Ind[S*]|$.

I want to know if there are approximation algorithm for densest-k-subgraph under this definition of approximation, and some results on the hardness of approximation.

Thanks in advance.


texts: Attribute efficiently learning the relevant attributes of juntas with membership queries

texts: Can the relevant attributes of k-juntas be learned attribute efficiently given a membership query oracle? What's the best known lower bound for this problem?


texts: List of theorems stating that P does not equal NP if and only if

texts: I think it would be a good idea to make a list of theorems stating that P does not equal NP if and only if such and such exits, some complexity class is contained in another complexity class and so on and so forth.


texts: Finding the longest path between two nodes in a bidirectional unweighted graph

texts:
I'm looking for an algorithm to find the longest path between two nodes in a bidirectional, unweighted, cyclic graph.

The path must not have repeated vertices (otherwise the path would be infinite of course).

Would someone point me a to a good one (site or explain)?

The graph will be sparse.

Thanks for any help!


texts: programming language with type-level functions

texts:
Is there any programming language out there that allows the same set of tools it offers, to be used at the type level as well? I know, Haskell and some other ML family languages allow parametric types but those are usually very limited and have a very adhoc syntax to define a new type.

To clarify, imagine the following pseudo code:

person = { name: 'jon', lastName: 'doe', age: 600 }
assoc = (k, v, obj) =>
   returns { name: 'jon', lastName: 'doe', age: 600, k: v }

assoc('color', 'red', person)
   // evaluates to { name: 'jon', lastName: 'doe', age: 600, color: 'red' }

So this is at the value-level. But I'm looking for a language that allows me to do the same thing at the type level:

type Person = { name: String, lastName: String, age: Int }
type Color = Red | Yellow

assoc = (k, v, type) =>
   returns a new type { name: String, lastName: String, age: Int, k: v }

assoc(color, Color, Person)
   // evaluates to { name: String, lastName: String, age: Int, color: Color }

You get the point, right? Basically, things that the PL allows you to do on values can be done on the types as well. It treats types as values, if you will.


texts: Learnability of constraint satisfaction problems CSPs?

texts:
This may sound more like a soft question but I am struggling to find an answer for it.

While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of machine learning and learning theory, there is almost nothing on learning CSPs. Given that CSP is a well known constraint formalism, I found this very weird. Am I missing something here?


texts: Maintaining the product of a queue of semigroup elements

texts:
I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time.  The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication.  Let the current state of the $Q$ be the sequence $(s_1,\ldots,s_n)$.  I am interested in the product

$$\prod Q = s_1 \cdots s_n.$$

Question: Is it possible to maintain this product in amortized constant time as elements are added and removed?


texts: Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)

texts:
My question is at the bottom.
(Most of the descriptive words come from Chris. Bishop's Neural Networks for Pattern Recognition)

let $w$ be the weight vector of the neural network and $E$ the error function.

According to the Robbins-Monro algorithm, this $$w_{kj}^{(r+1)}=w_{kj}^{(r)}-\eta\left.\frac{\partial E}{\partial w_{kj}}\right|_{w^{(r)}}$$ will converge to where $$\frac{\partial E}{\partial w_{kj}}=0$$

In general the error function is given by a sum of terms each of which is calculated using one of the patterns from the training set, so that $$E=\sum_nE^n(w)$$
And in applications we just update the weight vector using one pattern at a time $$w_{kj}^{(r+1)}=w_{kj}^{(r)}-\eta\frac{\partial E^n}{\partial w_{kj}}$$

My question is: Why the algorithm will converge using the last formula? Once we use it to update the $w$, the value of $w$ is changed, I can't prove the convergence using $$\frac{\partial E}{\partial w_{kj}}=\sum_n \frac{\partial E^n}{\partial w_{kj}}$$


texts: How to prove $\tilde{\mathbb{E}}PQ=0$ when $\tilde{\mathbb{E}}P^2 = 0$?

texts:
Let $\tilde{\mathbb{E}}$ be a degree-$r$ pseudo-distribution. If $\tilde{\mathbb{E}}P^2 = 0$, how to prove that $\tilde{\mathbb{E}}PQ=0$ for all polynomials $Q$ such that $\mathrm{deg}(PQ)\le r$?

We can prove the case $\mathrm{deg}(PQ) < r$ by induction, but it fails when $\mathrm{deg}(PQ) = r$.


texts: Partitioning the vertices of a complete graph with weights on both vertices and edges with constraints

texts:
Given the complete graph on n vertices. Each vertex and each edge has a positive weight associated with it. What is desired is to partition the vertices into parts so that the sum of the weights of the vertices of any part is less or equal to the minimum of the weights of edges connecting vertices in that part. What is the minimum size of such a partition?

Has anyone seen this before?


texts: Where is the error in the following P != NP pseudo-proof ?

texts:
Here is a necessarily wrong proof of $P \neq NP$ as it relativizes, but I can't find the error :

Le $U$ be a universal Turing machine, whose inputs are restricted to Turing machines accepting languages in P.
Let $L = \mathcal{L}(U)$ the language accepted by $U$, hence the acceptation language restricted to P.

L is in NP as for each instance  where $\mathcal{L}(M) \in P$ and $x$ an input of $M$, the certificate of $x$ is a certificate for L too
L is not in P as it would be in $DTIME(n^k)$ for a fixed $k$ and as $DTIME(n^{m+1}) - DTIME(n^m) \neq \emptyset$, if we choose a M in $DTIME(n^{k+1})$ and fix it, U would decide the problem in $\mathcal{O}(n^k)$


texts: Sampling from a distribution with a given covariance matrix

texts:
Let $\bf X$ be a binary vector of $n$ (non-independent) random variables $X_1,\ldots, X_n$.
Covariance of two random variables is defined as follows: $$\mathrm{cov}(X_i, X_j) = \mathrm{E}(X_i - \mu_i)(X_j - \mu_j),$$
where $\mu_i = \mathrm{E}(X_i).$ Covariance matrix for $\bf X$ is $n\times n$ symmetric matrix $C$, whose elements $c_{ij} = \mathrm{cov}(X_i, X_j)$.

Given a matrix $C$, are there any known efficient sampling algorithms for distribution that is close to the distribution of $\bf X$ (= distribution with the same matrix $C$)?

The same question for the case where $C$ is a correlation matrix:
$$c_{ij} = \frac{\mathrm{cov(X_i, X_j)}}{\sigma(X_i)\sigma(X_j)},$$
where $\sigma(X_i)$ is a standard deviation of $X_i$.

Any hints on papers etc. are welcome!

Thanks, Sasha


texts: Looking for a nice problem inside SC but not in the first two levels

texts:
The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$ but not known to be in $\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$.

As a side question, is there any known reason why finding examples of nice problems in higher levels of hierarchies ($\mathsf{AC}$, $\mathsf{NC}$, $\mathsf{SC}$, $\mathsf{PH}$, etc.) is more difficult than the first levels?

$\dagger$ although nice is not a mathematical term I think we intuitively understand what it means, e.g. accepting problem for NTMs is an artificial problem that people are not interested in it aside from it being complete for $\mathsf{NP}$, while the graph coloring problem was interesting before being known to be in/complete for $\mathsf{NP}$ and is still interesting aside from the complexity class it belongs to.


texts: The Number of Short Vectors in a Lattice

texts:
Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the number of lattice vectors $v$ with $|v| \leq c$ without actually enumerating these vectors?  The basis $v_1,\ldots, v_m$ of the lattice can be assumed to be LLL reduced.

Also asked at: https://mathoverflow.net/questions/71052/estimating-the-number-of-short-vectors-in-a-lattice


texts: Application of graph theory in computer science

texts:
I am a CS student. We did graph theory in one course. I found it interesting.

What are the real applications of graph theory in the computer science field?

For example, I found that some concepts in graph theory can be used to design networks. What are other similar applications?


texts: Can it be determined if language L lies in NP?

texts: Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?


texts: Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)

texts:
In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$.  However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$.  Is there a special name for this variant of an Ising model?

I'm asking this question because I'm curious if the results of (Barahona -- http://yaroslavvb.com/papers/barahona-on.pdf) & (Istrail 2000 -- http://www.brown.edu/Research/Istrail_Lab/papers/p87-istrail.pdf), showing the that calculation of the ground state is NP-hard for three-dimensional integer lattices (Barahona) and more generally non-planar lattices (Istrail), hold for an Ising model with $\sigma_i = (0,1)$ spin assignments?

It seems that it should from their proof arguments, though I do wonder if I'm missing something?

Generally speaking, what sort of rules can I "get away with" for spin state assignments while allowing for the results of (Barahona 1982) & (Istrail 2000) to hold?


texts: Presburger Arithmetic Decision Procedures

texts: What are good textbook references for Presburger Arithmetic decision procedures?


texts: Is the problem of finding the "all-terminal connectivity polynomial" polynomially bounded?

texts:
I want to proof whether the problem of finding the "all-terminal connectivity polynomial" of a given graph G(V,E) is checkable in a polynomial time. In order to do so I should first proof that it is polynomially bounded, i.e $|y| < p(|x|)$.
In this case I guess that $|x| \text{~} n^2$
but I am not sure about $|y|$ .

Note - Definition
For a given graph $G(V, E)$ each edge $E_{ij}$ has a $p_{ij}$-probability of being reliable and $(1 - p_{ij})$ probability of failure. Considering that each edge fails independently and nodes are perfectly reliable, the function

$Rel(G)$ = $Pr[$ for each pair of nodes $x_{i}$ and $x_{j}$ there exists at least one reliable path between them $]$

is called all-terminal connectivity (or reliability) function of the network.


texts:
So an idea I've had bouncing around for a while goes like this: suppose we have some TM that runs in possibly exponential time, and thus can use possibly exponential space.  But let's say that it doesn't use its available space very often: say, it's oblivious and makes a constant number of passes back and forth across the input.

It seems to me that such a machine can have its space usage improved, but I'm not sure of any relevant results.  Can we simulate such a machine in some smaller space bound (ideally polynomial or close to it...), if we allow the simulator to use that smaller amount of space however it wants?  Anyone know of such a result?


texts: Measuring the randomness of CNF formulas

texts:
It's widely known that CNF formulas can be roughly partitioned in 2 broad classes: random vs. structured. Structured CNF formulas, in opposition to random CNF formulas, exhibit some sort of order, showing patterns that are unlikely to happen by chance. However, one may find structured formulas showing some degree of randomness (i.e. certain specific groups of clauses seems much less structured than others), as well as random formulas with some weak form of structure (i.e. certain specific groups of clauses seems less randomic than others). Hence it seems that the randomness of a formula is not just a yes/no fact.

Let $r: \mathcal{F} \rightarrow [0,1]$ be a function that, given a CNF formula $F \in \mathcal{F}$, returns a real value between $0$ and $1$ inclusive: $0$ means a pure structured formula, while $1$ means a pure random formula.

I wonder if someone has ever tried to invent such a $r$. Of course the value returned by $r$ would be (at least this is my intent) just a practical measurement according to some reasonable criteria, rather than a solid theoretical truth.

I'm also interested to know if someone has ever defined and studied any statistical indicator that can be used in the definition of $r$, or in determining other useful overall properties of a formula. By statistical indicator I mean something like that:

HCV (Hit Count Variance)Let $h_F: \mathbb{N} \rightarrow \mathbb{N}$ be a function that, given a variable $v_j \in \mathbb{N}$, returns the number of times $v_j$ appears in $F$. Let $V$ be the set of variables used in $F$. Let $\bar{h}_F = \frac{1}{|V|} \sum_{v_j \in V}{h_F(v_j)}$ be the AHC (Average Hit Count). The HCV is defined as follows:

$HVC = \frac{1}{|V|} \sum_{v_j \in V}{(h_F(v_j) - \bar{h}_F)^2}$

In random instances, the HCV is very low (all variables are mentioned almost the same number of times), while in structured instances it is not (some variables are used very frequently and some others are not, i.e. there are "clusters of usage").
AID (Average Impurity Degree)Let $h_F^{+}(v_j)$ be the number of times $v_j$ occurs positive, and let $h_F^{-}(v_j)$ the number of times it occurs negative. Let $i: \mathbb{N} \rightarrow [0,1]$ be a function that, given a variable $v_j \in V$, returns its ID (Impurity Degree). The function $i(v_j)$ is defined as follows: $i(v_j) = 2 \cdot \frac{min(h_F^{+}(v_j), h_F^{-}(v_j))}{h_F(v_j)}$. Those variables occurring half of the times positive and half of the times negative have maximum Impurity Degree, while those variables occurring always positive or always negative (i.e. pure literals) have minimum Impurity Degree. The AID is simply defined as follows:

$AID = \frac{1}{|V|} \sum_{v_j \in V}{i(v_j)}$

In random instances (at least in those generated by negating variables with probability $0.5$), the AID is almost equal to $1$, while in structured instances it is usually far from $1$.
IDV (Impurity Degree Variance)The IDV is a more robust indicator than the AID alone, since it accounts for random instances generated by negating variables with probability different than $0.5$. It is defined as:

$IDV = \frac{1}{|V|} \sum_{v_j \in V}{(i(v_j) - AID)^2}$
In random instances the IDV is $0$ (because every variable is negated with the same probability), while in structured instances it is far from $0$.

  Motivations

  To better understand how CNF formulas work, how their randomness/structure could be measured, if other useful overall properties could be inferred by looking at their statistical indicators, if and how such indicators could be used to speed up search.
  Wonder if the satisfiability (or even the number of solutions) of a CNF formula could be inferred by just cleverly manipulating its statistical indicators.

  Questions

  Did anyone ever proposed a way to measure the randomness of a CNF formula?
  Did anyone ever proposed any statistical indicator that can be used to study or even to mechanically infer useful overall properties of a CNF formula?


texts: NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

texts:
It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049

For a problem I'm thinking about, it would be insightful to know if the Hamiltonian cycle problem was also NP-complete on the family of plane graphs whose dual is cubic and triply connected.

I would be interested in any result of the following form:

Let $D_d = \{ G \text{ a planar graph} : G^* \text{ has max degree bounded by } d \}$. Then for some $d$, Hamiltonian cycle is NP complete on $D_d$.


texts: Optimality of Greedy algorithm for minimization Knapsack Problem

texts:
Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized.

The greedy algorithm simply sorts items based on ratio $\frac{p_i}{w_i}$. It scans and sum up the sorted items in increasing order, until $\sum{w_i}\geq{W}$. Then outputs $\sum{p_i}$.

If the distribution of $p_i$ is known (say, following zipf distribution) and $w_i$ is randomly distributed, and independently with value of $p_i$, then what is the average optimality ratio which is ratio of $\sum_{i\in{I}}{p_i}$ to the optimal results.

Note: in worst case, this greedy algorithm can be arbitrarily bad, according to
following book. P412, Knapsack Problems, By Hans Kellerer, Ulrich Pferschy, David Pisinger.


texts:
I'm using random numbers for simulations. The main reason is to have an input sequence where no (simulation) algorithm is going to lock on a pattern and introduce unwanted effects into the simulation. So it seems random numbers have irreversibly lost the structure and it's unlikely that an algorithm is going to "reverse-engineer" it.

Is there a formal way to quantify this, such that pseudo-random numbers come out as being very unstructured?

I've read something about Kolmogorov complexity, but strictly speaking there is a very simple algorithm which can generate (pseudo)random numbers?! So they are not complex in this sense?


texts: Designing an appropriate training set for CART classification using imbalanced data

texts:
I'm experimenting with using CART (or maybe Random Forest) to classify genomic data.
There are essentially two classes, whereof one is the 'normal' state and the other is the 'exceptional' state.

Now, I don't know how to properly set up a training set, because the 'normal' class appears with a much higher frequency (about factor 1000) than the 'exceptional' class.

In order to get the CART to work properly, do I rather use a 1:1 ratio of the samples in my training set or keep the 1000:1 ratio?,

I'm quite a beginner in this field, so any help is appreciated.


texts: Size of decision tree for f is polynomial in the DNF size of f and CNF size of f

texts:
I've been having hard time with proving the following claim:
Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the number of leaves) decision tree for $f$. Also, let $size_{CNF}(f),size_{DNF}(f)$ denote the number of clauses, terms in the minimal $CNF,DNF$ formulas for $f$ respectively.

Prove that $size_{DT}(f)\in poly(n,size_{DNF}(f),size_{CNF}(f))$.


texts: Is there any known Poly-APX-complete minimimization problem?

texts:
All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (Max again!) the number of customers preferring it, provided that preferences are additive (http://www.sciencedirect.com/science/article/pii/S1568494617300510). Max, max, max... Is there any known Poly-APX-complete Min problem?

I suspect a problem I'm dealing with might be Poly-APX-complete, but it's a minimization problem. If there were some known Poly-APX-complete Min problem, an AP-reduction from it into my target problem would map Min into Min, so proving the Poly-APX-hardness of my target problem would probably be more natural and easier.