texts:
Sylvester's inertia law deals with the signatures of quadratic forms. I was thinking that it may be possible to extend this to multilinear forms; here is a first attempt.

Let $M$ be a $k$-linear form over the reals. For $1 \leq i \leq k$, define $\lambda_i(M)$ as the maximum dimension of a vector space $F$ such that

(*) $M(u_1,...,u_i,v_{i+1},...,v_k) \neq 0$ for every non-null $u_1,...,u_i \in F$, $v_{i+1},...,v_k \in F^{\bot}$.

If we define $\mu_i(M) = \lambda_i(M) - \lambda_{i-1}(M)$, is it true that these values form a partition of $n$? If so, can we formulate some "extended inertia law"? There might be some connection with Young tableaux but we probably don't require that for our needs.


texts: Talk for K-12 Students + General Audience Reference Request

texts:
I will be giving talks about general topics in CS, and want to hit on TCS as well. The talks will be given to K-12 schools, so not all of them will be seniors who may go to an undergraduate program at a university (Note: this question is different than Inspirational talk for final year high school pupils, which only concerns seniors).

I am looking for references/videos/lecture slides/etc. that deal with CS/TCS topics in a general perspective given towards high/middle/lower school students.

The only one I have been able to find so far is this one: https://www.youtube.com/watch?v=msp2y_Y5MLE by Michael Sipser on the P vs NP problem. It is interesting, but I want to know if there are other sources that give insight into major CS topics that they + a general audience may not have heard about before.


texts:
If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. Though there is not a canonical rant for it, I've also been told that regex aren't powerful enough to parse SQL.

I'm a self-taught programmer, so I don't know much about languages from a theoretical perspective. Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

Edit: To clarify, I'd really like a few examples of languages that are used in the real world that fit in the category of regular languages, rather than some axioms or equivalent conditions, etc.


texts: Best Sorting for unlimited integer range

texts:
Is there a better than time $O(n\log n)$ and space $O(n)$ deterministic algorithm in the RAM model to sort $n$ positive integers whose range is unbounded?

How about randomized?


texts:
I was puzzled by a seeming simple inference in rewriting theory:

if $y_1 \overset{*}{\leftarrow} x \overset{*}{\rightarrow} y_2$ then $y_1 \overset{*}{\leftrightarrow} y_2$.

I don't understand how could the consequence be inferred. For example, given $b_2 \leftarrow b_1 \leftarrow a \rightarrow c_1 \rightarrow c_2$, how could you say that $b_2$ and $c_2$ can reduce to each other?

EDIT:

After reading Ohad's answer, in particular

  a sequence of reverse rewrites followed by a sequence of direct rewrites is indeed a sequence of (either direction) rewrites.

I suddenly realized that the inference is indeed immediate, because $\rightarrow$ represents a (rewriting) relation, which means it's just a set of pairs. Its reflexive closure ($\overset{=}{\rightarrow}$), symmetric closure ($\leftrightarrow$), transitive closure ($\overset{+}{\rightarrow}$) are all defined as a superset of it. In particular, its reflexive, transitive and symmetric closure ($\overset{*}{\leftrightarrow}$) also contains it. In other words, we have $\rightarrow\;\subset \overset{*}{\leftrightarrow}$, then recall that a subset relation can be read as an inference which is exactly the statement that puzzled me. [EDIT: this reading doesn't help here!] Take the example I gave, $\rightarrow = \{(a, b_1), (b_1, b_2), (a, c_1), (c_1, c_2)\}$, its reflexive, transitive and symmetric closure $\overset{*}{\leftrightarrow} = \{(a, b_1), (b_1, b_2), (a, c_1), (c_1, c_2), (a, b_2), (a, c_2), (b_2, b_1), (b_1, a), (c_2, c_1), (c_1, a)\}$, the subset relation definitely holds. I hope this may also help others.

*EDIT*${}^2$:

I just realized that back then, I forgot to give the context of the inference.  The inference is formed via transitivity of logical inference from two others:

$y_1 \overset{*}{\leftarrow} x \overset{*}{\rightarrow} y_2 \Rightarrow y_1 \downarrow y_2$
$y_1 \downarrow y_2 \Rightarrow y_1 \overset{*}{\leftrightarrow} y_2$

where $y_1 \downarrow y_2$ means $\exists z . y_1 \overset{*}{\rightarrow} z \overset{*}{\leftarrow} y_2$ and the first is known to be the confluence.


texts: Approximating a convex polyhedron, with fewer inequalities

texts:
I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers.  In other words,

$$\mathcal{P} = \{x \in \mathbb{R}^d : \forall i . a_i \cdot x \le c_i, \forall j . x_j \ge 0\},$$

where $a_1,\dots,a_n \in \mathbb{R}^d$ and $c_1,\dots,c_n$ are given.

I'm given $m$, where $m < n$.  I want to find a new convex polyhedron $\mathcal{Q}$ defined by $m$ linear inequalities, so that $\mathcal{Q}$ is contained within $\mathcal{P}$.  In other words, I want to find $b_1,\dots,b_m \in \mathbb{R}^d$ and $d_1,\dots,d_n$ such that the convex polyhedron

$$\mathcal{Q} = \{x \in \mathbb{R}^d : \forall i . b_i \cdot x \le d_i, \forall j . x_j \ge 0\}$$

is wholly contained within $\mathcal{P}$ ($\mathcal{Q} \subseteq \mathcal{P}$).

So far, this is easy, but there is an objective function I am trying to minimize.  Fix vectors $\mu,\sigma \in \mathbb{R}^d$.  Let $X$ be a random variable over $\mathbb{R}^d$, where the $i$th component $X_i$ of $X$ has a $\mathcal{N}(\mu_i,\sigma_i^2)$ distribution, and where the $X_i$'s are mutually independent.  The "badness" of $\mathcal{Q}$ is given by $\Pr[X \in \mathcal{Q} \setminus \mathcal{P}]$.

My goal: given $\mathcal{P}$ and $m,\mu,\sigma$, find a convex polyedron $\mathcal{Q}$ defined by $m$ linear inequalities that is contained within $\mathcal{P}$ and whose "badness" is as small as possible.

If there is no efficient solution to this optimization problem, I would be happy with an approximation algorithm or a heuristic.  In my application, I would expect to have $m,n \le 50$ or so (perhaps even smaller), but $d$ is large (say $d \approx 10^4$ or so).  Also, if a solution for the general problem is too hard, I would be satisfied with a solution for the special case where we are guaranteed that $a_i,c_i$ are all $\ge 0$.

Can you suggest any methods that might be effective for this problem?


texts: What are the relationship and difference between ambiguous grammars and non-deterministic ones?

texts:
Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars.  According to Wikipedia however, this is false:

  there are non-deterministic unambiguous CFGs

What is the difference between ambiguity and determinism in grammars?  What is an example of a grammar that is non-deterministic but unambiguous?


texts: How do I use canonical ordering to reduce symmetry in the SAT encoding of the pigeonhole problem?

texts:
In the paper "Efficient CNF Encoding for Selecting 1 from N Objects", the authors introduce their "commander variable" technique for encoding the constraint, and then talk about the pigeonhole problem.
Since my error may exist in lower-level understanding, let me declare what I think I know before posing the question:

Let $m$ and $n$ be the number of pigeons and holes. The naive encoding uses a propositional variable $X_{i,j}$ that is true when the $i'th$ pigeon is to be put in the $j'th$ hole. The clause $ExactlyOne(X_{1,1}, X_{1,2}, ..., X_{1,n})$ enforces that pigeon 1 must occupy exactly one hole; identical clauses are added for the other pigeons. The clause $AtMostOne(X_{1,1}, X_{2,1}, ..., X_{m,1})$ enforces that no more than one pigeon occupies hole 1; identical clauses are added for the remaining holes.
When there are more pigeons than holes (m > n), the problem is unsolvable (obvious to humans) but the SAT solver doesn't "see" this fact. When it can't find a way to place pigeons $1,2,3,..,m$ it will search an attempt with pigeons $2,1,3,...,m$. It doesn't understand that the order of the pigeons is irrelevant. The paper, among others, calls this symmetry.
Instances where $m=n+1$ are used as a strenuous test of a SAT solver's ability to detect unsatisfiability.

The paper proposes to break the symmetry by enforcing order on pigeons. Pigeon $i$ must be placed in a hole in front of the hole of pigeon $i+1$ (i.e., the pigeon in hole $j$ must have a smaller number than of the pigeon in hole $j+1$). It then disappointingly says, "Due to space limitations, we do not explicitly describe in detail the canonical-ordering encoding, but the number of clauses generated is of order $O(n*log(n))$".
So my question is: what did they do to get these results?
I want to treat the variables $\{X_{1,1}, X_{2,1}, ..., X_{m,1}\}$ as string of bits that, numerically, identifies the choice of which pigeon went into hole 1, and so on. Follow this with $n-1$ comparators to enforce the paper's suggestion. My naive comparator construction, however, requires m clauses, one for each bit (of increasingly ugly size). Help! :)


texts:
I've given a planar graph (with clockwise ordering of vertices). I would like to make it biconnected by adding some number of edges. Graph should remain planar, of course. How can I do this?

Few more notes:

By biconnected I mean no single cut vertex and no bridge,
We cannot change given embedding,
We do not have to minimize number of edges added


texts: Directed multigraphs as minimal automata

texts:
Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by forgetting labels of transitions, final states). We keep the initial state because every vertex must be accessible from it.

Is the converse true ? I.e. given a directed connected multigraph $G$ with constant out-degree and initial state such that every vertex is accessible from it, is there always a language $L$ such that $G$ is the underlying graph of the minimal automaton of $L$ ?

For instance if $|A|=1$ it's true, since the graph must be a "lasso" with a prefix of size $i$ and a loop of size $j$, and corresponds to the minimal automaton of $L=\{a^{i+nj}~|~n\in\mathbb N\}$.

The motivation comes from a related problem encountered in a decidability reduction, where the solution is easier : starting from a non-oriented simple graph, and with more operations allowed like adding sinks. But I was wondering if someone had already looked at this more natural question ?

The only things remotely connected I could find in the literature are papers like Complexity of Road Coloring with Prescribed Reset Words, where the goal is to color such a multigraph so that the resulting automaton has a synchronizing word. However minimality does not seem to be considered.

Update: Follow-up question after the answer of Klaus Draeger: what is the complexity of deciding whether a graph is of this shape ? We can guess the labeling and polynomially verify minimality of the automaton, so it is in NP, but can we say more ?


texts:
For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a maximum flow computation.

Define that

$\lambda(G) = \min_{x,y\in V(G), x\neq y} \lambda(x,y)$ to be the (min) edge connectivity.
$\bar\lambda(G) = \max_{x,y\in V(G), x\neq y} \lambda(x,y)$ to be the max edge connectivity.

Because of max-flow min-cut theorem, the first problem is much easier. We just need to find a global min-cut, namely a partition $(S,V\backslash S)$, such that the number of edges from $S$ to $V\backslash S$ is minimized.

The global min-cut for both undirected and directed graphs can be solved in $O(nm)$ through Hao-Orlin's algorithm. $^1$

Max edge connectivity seems harder. I do not know of any algorithm that does less work than find all $\Omega(n^2)$ possible $\lambda(x,y)$ and take the max. This means $\Omega(n)$ max flow computation in undirected graphs by constructing the Gomory-Hu tree, and $\Omega(n^2)$ max flow in directed graphs.

Is there an algorithm that solves this problem faster?
It seems that $\Omega(n)$ max flow is required. Since for each component we need to compute at least one $\lambda(x,y)$ for $x,y$ in the component. Or something equivalent. There are graphs with $\Omega(n)$ components, and one must determine which component contains the largest local edge connectivity. (although in that case, most max flow computation would incur constant cost. )

Hao, Jianxiu X.; Orlin, James B. (1994). "A Faster Algorithm for Finding the Minimum Cut in a Directed Graph". Journal of Algorithms 17 (3): 424. doi:10.1006/jagm.1994.1043.


texts:
I came upon a problem and have been trying to find a method more efficient then brute force, but I came up with nothing; and I am not even sure how to approach it...

You have a list of numbers and a target number all of which are positive and can have decimals. You must add the numbers in the list to get as close as possible to the target value without overshooting. Each number in the list can be used any number of times including not at all. The solution is the closest number that uses the least total numbers. To be clear, the least total numbers only applies when there are two identically close solutions.

It isn't very hard to make a program that checks every possible combination, but is there a way to make it more efficient?


texts: Approximating liveness properties with safety properties

texts:
Given a finite alphabet set $\Sigma$, the set $\Sigma^{\omega}$ of infinite words over $\Sigma$ can be topologized with a metric $d: \Sigma^{\omega} \rightarrow \mathbb{R}$ such as:

$\forall w_1, w_2 \in \Sigma^{\omega}:\ d(w_1, w_2) = \frac{1}{2^n}$, where $n$ is the longest common prefix.

Given a linear-time (LT) property $P \subseteq \Sigma^{\omega}$, $P$ is a liveness property iff it is a dense subset of $\Sigma^{\omega}$. Also, $P$ is a safety property iff it is a closed set.

According to this topology, every finite prefix $u \in \Sigma^{\ast}$ corresponds to the ball of all infinite extensions of $u$. The radius of that ball is inverse-exponentially related to the length of $u$.

I have one question:

  Is there some precise sense in which a liveness property $P$ can be approximated with a safety property, e.g., by applying some (possibly arbitrarily large) timeouts on all eventualities in $P$?

What is meant by timeout, since temporal logic does not know about real time? This question mainly arose in synchronous digital circuits where there is a clock signal and every clock edge means an event $\sigma \in \Sigma$ depending on logic signal values observed by that edge.

This question might sound odd, but the answer will surely be illuminating to me (e.g., a topologist might say dense subsets can only be approximated by the entire space $\Sigma^{\omega}$, which is the only property that is both liveness and safety).


texts: what is "one-to-one reduction from a function f to another function g"

texts:
I am reading a paper called "Rational Proof". It mentioned the following one-to-one reduction. I cannot google an introduction of it.

An excerpt from the paper.
"Recall that a one-to-one reduction from a function $f$ to another function $g$ is a triple of polynomial time computable functions ($\alpha$, $\beta$, $\gamma$) such that:

For all $x$ in the domain of $f$ we have $y=f(x)$ if and only if $g(\alpha(x))=\beta(y)$
For all $x$ in the domain of $f$, let $w=\alpha(x)$. Then we have $g(w)=z$ if and only if $f(x)=\gamma(z)$.
"

Any reference for the formal definiton of the so-called "one-to-one reduction" is appreciated. Thanks.


texts:
Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags as they are. Your goal is have a distribution of apples that is as close to uniform as possible.

I realize this is a variation of the multiple knapsack problem but with some differences: all bags must be distributed, so some people will inevitably receive slightly more apples than their fair share while others will receive less.

Does this problem have a name? I am almost certain it is NP-hard, but is there a good approximate algorithm for this?


texts: Is it possible to add quantum physics theory to traditional machine learning algorithms to get more accurate results

texts:
Lets suppose your data set includes locations in several dimensions and the kind of entity which is the class of the data set, is there other kind of information you need to add (such as times, observer data, etc.. ) to the data set in order to be able to include quantum calculation in the algorithm that builds the model and predicts results?

Which are the main changes all or some of the algorithms need?
Are there examples of implementations of this algorithms in the web, is so where are them?


texts:
Given two finite sets of points, $R, B \subseteq \mathbb{R}^d$, compute a map $f : R \to B$ where:

$f(r) = \text{argmin}_{b \in B} |r - b|$

That is $f(r)$ is the closest point in $B$ to the point $r$ in $R$.

What is the current fastest algorithm for computing $f$ in low to mid sized dimensions (for example d=3)?

Some things I already know:

The trivial brute force algorithm would take $O( |R| |B| )$
In 1D the problem is easy, just merge two sorted lists
In 2D it is easy to solve with a Voronoi diagram
For non-bichromatic point sets the well-separated pair decomposition gives a solution in expected $O( c^d n \log(n))$ time.  Other solutions with similar performance are known.
Finding the bichromatic closest pair is solvable in $O(2^d n \log(n))$

A solution to this problem would be nice for shape matching/registration problems where one is repeatedly querying the same data set with some collection of points.  You could do something like incrementally call out to a nearest-neighbor subroutine for each point, but maybe you can do better amortizing over the cost of many queries?


texts: *Simple* explicit constructions of bounded-degree expanders of "largish" spectral gap

texts:
I want to use for some work of mine bounded-degree (balanced bipartite) expanders with "decent" spectral gap. They need not be Ramanujan graphs. I'm ok with a degree that's a constant factor (ideally smallish) larger than the minimum necessary for a given ratio $\lambda_1/\lambda_2$, where $\lambda_1$ and $\lambda_2$ are the two largest eigenvalues.

But, in order of importance:

I must have strong control on their size; at the very least I need to be able to construct them with size equal to every power of $2$. "An infinite family" is not nearly good enough for me, even an "infinite linear family" is iffy.
I must have some control on their degree; let's say there must be a (smallish) constant $c$ such that for every $d$, I must be able to grab  family with degrees between $2^d$ and $2^{d+c}$, guaranteeing me a second eigenvalue no larger than $2^{(d+c)/2+1}$.
They must admit a fully explicit construction, in "little" time, ideally linear or slightly superlinear. "Polynomial" is not nearly as good.
Ideally, the constants involved must not be gargantuan, but this has much lower priority than 1,2 or 3.
"Simple" would be icing on the cake...

None of the constructions of Ramanujan or "quasi-Ramanujan" graphs I've seen seem to satisfy 1 & 3, and most fail to satisfy 4; but maybe I've been just too hasty. Any pointer would be greatly appreciated!


texts: Problem in deterministic time $n^p$ and not lower

texts:
I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable).

I'm interested in a concrete example, languages of the type " Given $M,x,1^n$ is M printing 1 on input x in less than $n^p$ steps" is known not to belong in $DTIME(n^{p-1})$ but it's very hard to understand why intrinsically it is not in $DTIME(n^{p-1})$.

To my knowledge it is a big open question to find such an explicit $L$, so I'm fine with languages conjectured to be in such classes.

I'm also interested if you replace deterministic time with space, non deterministic time, or probabilistic time, but it should remain polynomial.

Edit: More generally I'm also trying to avoid problems which can be shown to be equivalent to simulations of TM. Unless the lowerbound does not use this fact.

One example of a problem i'd be interested in could be something like "is this graph planar ?". Unfortunately this problem is known to be solvable in linear time.


texts: Complexity of Finding Optimal Synergistic Set Packings

texts:
Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and sometimes we should recompute them from scratch.

We were able to reduce the problem of determining the optimal set of intermediate results to cache to the following very natural problem, which I call synergistic set-packing.

Problem: We are given a universe of $m>0$ elements $U = \{e_1, e_2, \ldots, e_m\}$, as well as a function $c : U\rightarrow \mathbb{Z}^+$ which maps each element to some positive integral cost. We are furthermore given a collection $\mathcal{C}$ containing $n>0$ nonempty subsets of $U$; $\mathcal{C} = \{S_1, S_2, \ldots, S_n\}$. Finally, we are also given a function $p : \mathcal{C} \rightarrow \mathbb{Z}^+$ which maps each $S_i$ to some positive payoff.

Our goal is to choose $X \subseteq U$ that maximizes the following benefit function of payoff - cost:
$$
\left(\sum_{S_i\in\mathcal{C} \text{ with } S_i\subseteq X}p(S_i)\right) - \left(\sum_{e_j\in X} c(e_j)\right)
$$

That is, if we pick all of the elements for some $S_i \in \mathcal{C}$, we get a payoff of $p(S_i)$, but we must pay for all of the elements in $S_i$ to get this payoff.

Approaches: At first glance, this problem seems pretty similar to the (somewhat obscure) NP-hard minimum K-union problem (1), where our goal is to pick the $k$ sets whose union cover the fewest elements (in our problem, in the case of unit costs / payoffs, we would try to pick the $k$ elements that hit the fewest number of sets, and then include the rest of the $m-k$ in $X$, but the analogy does not quite work since there is no requirement that we choose $X$ to have at most $m-k$ elements).

Any help with characterizing this problem's complexity is of course much appreciated!

Example: I will put the cost/payoff next to each item, after a colon. Suppose $U$ is given by (along with costs) $\{e_1: 2, e_2: 2, e_3: 1\}$, and in our collection we have:
$$S_1 = \{e_1, e_2\} : 1$$
$$S_2 = \{e_2, e_3\} : 4$$

Then in this case we would pick $X = \{e_2, e_3\}$, for a total cost of 3 and a payoff of 4, for a net benefit of 1.

(1) Staal A. Vinterbo (2002). A Note on the Hardness of the k-Ambiguity Problem. DSG Technical Report 2002-006.


texts: On a Linearization of the Quadratic Assignment Problem

texts:
The Quadratic Assignment Problem formulated as an integer program:
\begin{align}
 \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n c_{ijkl}x_{ij}x_{kl}\\
 \mbox{subject to}\quad &\sum_{i=1}^n x_{ij} = 1 \quad \forall j=1,\ldots,n,\\
&\sum_{j=1}^n x_{ij} = 1 \quad \forall i=1,\ldots,n,\\
 &x_{ij}\in\{0,1\}\quad \forall i,j=1,\ldots,n.
 \end{align}

A simple and natural linearization:
\begin{align}
 \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n c_{ijkl}y_{ijkl}\\
 \mbox{subject to}\quad &\sum_{i=1}^n x_{ij} = 1 \quad \forall j=1,\ldots,n,\\
&\sum_{j=1}^n x_{ij} = 1 \quad \forall i=1,\ldots,n,\\
& y_{ijkl} \le x_{ij} \quad \forall i,j,k,l=1,\ldots,n,\\
& x_{ij} + x_{kl} \le 1+y_{ijkl} \quad \forall i,j,k,l=1,\ldots,n,\\
& y_{ijkl} = y_{klij} \quad \forall i,j,k,l=1,\ldots,n,\\
&x_{ij},y_{ijkl}\in\{0,1\}\quad \forall i,j,k,l=1,\ldots,n.
 \end{align}

My question is: Has this linearization already been considered in the literature?
I did not see it in any papers (this one for example).


texts: Finding a cutting plane that splits a polyhedron evenly

texts:
Say we have a polyhedron in standard form:

\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}

Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same?  (i.e. an algorithm that minimizes the absolute difference of vertex cardinalities on the two sides of the split).

Also, are there any known results regarding the complexity of this problem?

Addendum: Restricting the types of cuts:

Here is a variation of the original problem with the hope that it is easier to solve than the original one:

Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all  possible such splits.

Note: After a few days of little progress, I posted this question at MathOverflow too.


texts: Does this meet the space requirements for the lower 3-SAT bounds?

texts:
According to "What are the best current lower bounds on 3SAT?", Ryan Williams has an answer that states that the (time * space) requirements for 3-SAT must meet or exceed $n^{2 \cos(\pi/7) - o(1)}$ infinitely often.  See

 Ryan R. Williams
 Better Time-Space Lower Bounds for SAT and Related Problems
 20th IEEE Conference on Computational Complexity, pages 40-49
 2005

...or his link here.

If we consider Atkin and Bernstein's sieve:

 A.O.L Atkin and D.J. Bernstein
 Prime sieves using binary quadratic forms
 Mathematics of Computation, Volume 73, Number 246, pages 1023-1030
 December 19, 2003

...It requires $O(\frac{n}{\log \log n})$ additions and $n^{1/2 + O(1)}$ space.  So does this sieve alone meet the time/space requirements for 3-SAT?  Or are the results inconclusive for the sieve?


texts: Choices for the group in Public Key Cryptography

texts: I am only aware of two alternatives for the group used in Diffie-Hellman scheme (and similar ones) where logarithms are conjectured to be hard. Those are $\mathbb{F}_p$ and Elliptic Curves. Are there any other explored choices?


texts: Distribution attaining minimum discrepancy of disjointness function

texts: Is it true that for the optimal distribution $\nu$ (not necessarily uniform) that attains minimum discrepancy $\mathsf{disc}(\mathsf{DISJ}_n)$ for the disjointness function $\mathsf{DISJ}_n$ we have for every rectangle $\mathcal R\subseteq\binom{\{1,2,\dots,n-1,n\}}{\sqrt n}\times\binom{\{1,2,\dots,n-1,n\}}{\sqrt n}$ $$\nu(\mathsf{DISJ}_n^{-1}(0)\cap\mathcal R)\geq\alpha\nu(\mathcal R)-e^{-\alpha n^\beta}$$ for some $\alpha>0$ and $\beta\in(0,1)$?


texts: Combinatorial Independent set Algorithms for sub-classes of perfect graphs

texts: As an extension to the question posed recently by Bulatov, I wonder what are the maximal sub-classes of perfect graphs for which we know of combinatorial algorithms to compute a maximum independent set.


texts: Cheapest dissection of a grid polygon into rectangles with cost

texts:
My problem:

Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.)
The rectangles must be taken from a predefined set (which includes a 1×1 rectangle, so the dissection is always possible).
Each rectangle has a cost which is not directly proportional to its size (a 2×3 rectangle may cost less 'per grid square covered' than a 1×1 rectangle).
No gaps or overlaps are allowed.
The optimal solution is the cheapest that covers the area.

My first thoughts were to work out the cheapest 'per square covered' rectangle and fit as many of those into the area as possible, but it seems that might perform poorly if it means filling a lot of spaces with small, expensive pieces.

I realise this is likely NP-hard, so I am probably looking for a heuristic rather than an algorithm. It seems in some ways similar to a bin-packing problem or a knapsack problem, but I can't see how to extend the solutions to these problems. I may just be lacking the right terminology, so if anyone could point me in the right direction to get started, I'd be grateful.


texts: Are there some popular journals in the field of theoretical CS that serve the kind of purpose that a journal like "Physics Today" does for the Physics community ?


texts: Using Graphs/Graph Similarity as Features for a Learner

texts:
I'm working to construct a learner than can recognize whether two vertices in a property graph (digraph, vertices and edges can have arbitrary keys/values) modelling a social network in fact represent the same person. I want to use the structure of the graph local to two vertices, compare those structures, and use the similarity as a feature.

I've had trouble finding related work. Light review of the literature leaves me stuck on graph methods - eg, Bayesian networks and graphs-as-learners- as opposed to learning graph-based domains. Are there any good resources I'm missing, or maybe suggested methods?


texts: Worst-case asymptotic-complexity of the Set-cover problem?

texts:
What's the worst-case asymptotic-complexity of the Set-cover problem in Big O notation?

I've been developing some novel techniques to try and solve this problem but am having trouble finding the theoretical limits I need to surpass.

Thanks for all information


texts: Examples of the use of biased estimators

texts: Biased estimators are useful in statistics because they can optimize mean-squared error more than what an unbiased estimator can manage. I was wondering if in theoryCS if there are any very notable examples of the effective use of biased estimators. I realize this list could get long, and if it does I can modify this question to a big-list CW question, but for now I'm just curious.


texts:
Consider a naive MAX SAT approximation algorithm:

pick a literal $l$ which appears in maximum number of clauses
set the corresponding variable of $l$, such that all clauses containing $l$ are satisfied
repeat on the reduced formula until no variables remain

What is the approximation factor of the algorithm?

It's easy to show by induction, that at least half of all clauses will end up sattisfied. But I can't find a tight example  with only 1/2 clauses sattisfied and all clauses satisfiable. I expect, that the approximation ratio is better than 1/2, but I can neither prove it nor disprove it.

Thank you very much.


texts: Surprising Results in Complexity (Not on the Complexity Blog List)

texts:
What were the most surprising results in complexity?

I think it would be useful to have a list of unexpected/surprising results.  This includes both results that were surprising and came out of nowhere and also results that turned out different than people expected.

Edit: given the list by Gasarch, Lewis, and Ladner on the complexity blog (pointed out by @Zeyu), let's focus this community wiki on results not on their list.  Perhaps this will lead to a focus on results after 2005 (as per @Jukka's suggestion).

An example: Weak Learning = Strong Learning [Schapire 1990]: (Surprisingly?) Having any edge over random guessing gets you PAC learning. Lead to the AdaBoost algorithm.


texts:
Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion to a word $w=a_1, \cdots, a_m$ and $f_w=f_{a_1}\circ \cdots \circ f_{a_m}$ where $\circ$ denotes function composition. Furthermore we denote $G=\{f_w\mid w\in \Gamma^*\}$ and $G$ is monoid.

[$G$ is usually called transition monoid in the standard textbook, but here I reproduce the definition for clarity.]

The question is, given a function $f:Q\rightarrow Q$, can we decide $f\in G$ (ideally in polynomial time), and if this is the case (i.e., there exists a $w$ such that $f=f_w$), whether $w$ is only polynomially long, or can be exponentially long?

[I guess that indeed such a word could be exponentially long, but I am looking for a simple example.]


texts: Efficient algorithm for computing equally distributed points in polytope?

texts:
Given a $d$-dimensional (rational) convex polytope $P$ with vertices $v_1, \ldots, v_n$, I would like to compute many equally distributed points that lie in $P$. "Equally distributed" is of course not a precise term. It should just mean that points don't accumulate at some point in $P$ much more than at others (like they would be by doing a repeated barycentric subdivision, for example).

Now, there are two obvious solutions: First one is to just generate a lot of random points in the polytope. This can be done quickly with a software like Polymake. But the problem is that the coordinates have huge denominators which make subsequent computations very slow.

The second approach would be to generate coefficient vectors that sum up to $1$ and have entries $\geq 1/k$. The coefficients have small denominators but the algorithm would generate ${n-k-1 \choose k-1}$ coefficient vectors, while only a tiny fraction of them give distinct points in the polytope (at least for the polytopes I am interested in).

  Are there any algorithms that do what I want efficiently with small denominators?


texts: What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

texts:
There are many problems which have implications on P vs. NP and other complexity classes.  Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier transforms carry any implications for P vs. NP or other complexity classes?  For example, I seem to recall seeing something regarding faster matrix multiplication as it relates to P vs. NP.

I'm really trying, although I may be somewhat vague, to determine if any Fourier-related transforms have P vs. NP implications, even if we have to trace implications through several problems or complexity classes.


texts: What is the origin and meaning of the phrase "Lambda the ultimate?"

texts:
I've been messing around with functional programming languages for a few years, and I keep encountering this phrase.

I understand what lambda means, the idea of an anonymous function is both simple and powerful, but I fail to understand what "the ultimate" means in this context.

I feel like I'm missing a reference here, can anyone help?


texts: Gentle introduction to graph isomorphism for bounded valance graphs

texts: I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it too abstract. I would be thankful if anybody can suggest me some references of expository nature. I do not have strong background in group theory, so I would prefer papers which use group theory in a gentle way (my background is in CS).


texts: Complexity of finding an edge set yielding specified vertex degrees

texts:
I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:

Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\subset\,E$ such that in the graph $G'=(V,E')$ the degree of each vertex $v_i\in\,V$ is $d_i$?
Q2: Given a graph $G=(V,E)$ and integers $x_i,\,y_i,\,1\leq\,i\leq\,|V|$, does there exist a subset $E'\subset\,E$ such that in the graph $G'=(V,E')$ for every $v_i\in\,V$ we have $x_i\leq\deg(v_i)\leq\,y_i$?

I know already that certain restrictions of Q1 are known to be in P.

If all of the $d_i=1$ then the problem is finding a perfect matching
If all of the $d_i=2$ then the problem is finding a vertex cycle cover.
If $G$ is a complete bipartite graph then the problem can be solved by the Gale-Ryser theorem.

However, I haven't found an efficient algorithm for Q1 in general and nothing specific for Q2. Is anything else known?


texts:
Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes $S_i \backslash S_j$ for any $i$ and $j$?
Has this problem been studied before in the literature? If an output-sensitive algorithm (after preprocessing the sets) is not possible, what is the best complexity we can attain?
I found that there is a related problem which focuses on set intersection rather than set difference. To the best of knowledge, there is no output-sensitive algorithm for the case of set intersection.


texts: Quantum Hardness of Approximating Lattice Problems

texts:
A common claim in lattice-based cryptography is that cryptosystems based on the Learning with Errors ($\mathsf{LWE}$) problem are hard to break (for a per-system definition of "break") for quantum attackers.

For instance, the standard paper on $\mathsf{LWE}$, Regev2005, makes multiple references to the security of $\mathsf{LWE}$-type systems based on the quantum hardness of solving, say, $\mathsf{GapSVP}_\alpha$ for polynomial approximation ratios $\alpha$. But, as far as I see, there is no mention here as to why a critic might be convinced that such quantum hardness holds.

Across the host of lattice-based cryptography, the reference is generally made back to Regev's first paper, with no more explanation. And this association is quite important to the broader theory community, because likely tens of millions (or more) dollars are handed out in cryptography grant money based (in part) on this high-level claim.

Searching the CSTheory site also turns up no answer to this question. Perhaps there is a simple place to look up this information online.. in which case, consider this question the "CSTheory catalogue" of where to find this information!

$\underline{\rm Question}:$ What is the proper, "standard" justification for why it is believed hard for efficient, quantum algorithms to approximate $\mathsf{GapSVP}_\alpha$ to within polynomial approximation factors $\alpha$?

$\underline{\rm Question\; Clarification\, /\, What\; I'm\; Looking\; For:}$

What structural property of factoring allows Shor's algorithm to run
quickly, but appears to be missing from worst-case lattice (approximation) problems?
In particular: How is this gap related to our current understanding of the Abelian Hidden Subgroup Problem (HSP) vs non-Abelian variants of the HSP?


texts: What is the advantage of designing deterministic distributed algorithms?

texts:
Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem.

Paxos is deterministic in the sense that given the assumption it makes, it always works.
In constrast, randomized consensus works with a given probability.

What is the advantage of designing and using a deterministic algorithm?

The assumptions upon which deterministic algorithms rely have also a probability of holding in the reality (what is called their assumption coverage). Hence, there is always a probability that a deterministic algorithm does not work in the reality.


texts: Balanced and general $MAXkSAT$ known approximation results and bounds from $UGC$

texts:
$MAX2SAT$ has a $0.9401$ to $0.9402$ approximation algorithm which is conjectured to be optimal by $UGC$ while there is a balanced $MAX2SAT$ bound of $0.943$ approximation which is conjectured to be optimal by $UGC$.

For other values of $k$ do we know the optimal values conjectured by $UGC$ for both balanced and general situations and the status of algorithmically achievable results known?

A sanity check for $MAXSAT$: For $MAXSAT$ it is $NP$-hard to beat $7/8$ approximation and we have an algorithm which achieves $7/8$ and do we know $UGC$ provides the same bound for both balanced and general situations (I am unable to locate what $UGC$ says about $MAXSAT$ and we know if $UGC$ says a strictly lower than $7/8$ bound then trivially $UGC$ is false and so this sanity check)?


texts: Probability of detecting small bias of a die in the low confidence regime / balls and bins

texts:
We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which of the sides is biased given $t$ independent throws. Naturally, the optimal way to do that is to output the side with the largest count (with randomized tie breaking).

I'd like to give a lower bound on the success probability of this method when the number of throws is too small to get high probability of success.
More formally, assume that $\gamma \leq \frac{1}{\sqrt{tm}}$ (which is roughly the standard deviation of each of the counts). You can also assume that $t\geq c m \log m$ (for any fixed constant $c$).
In the case of $m=2$ a simple calculation shows that success probability in this regime is $\geq \frac{1}{2} + \Omega(\sqrt{t}\gamma)$.
More generally, based on some back-of-the-envelope calculations and simulations the answer should be $\geq \frac{1}{m} + \Omega(\sqrt{t}\gamma)$. However, I do not see a formal argument that proves this (and a direct calculation in this case seems very painful).

The question can also be reduced to the following question about a regular unbiased die (or the standard balls-and-bins model). What is the probability that the first count is exactly equal to the maximum of the rest of the counts?

Would be grateful for references or analysis suggestions.


texts: Determining if a word of specific length exists that is not accepted by a NFA

texts:
It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?

Given an NFA and a natural number $n$, determine if there exists a word of length $n$ that is rejected by the NFA.

At first I thought that it is possible to prove this is NP-Hard by reducing the problem of checking if every word is accepted by an NFA to it, by checking every word length until hitting an upper bound. but according to Yuval Filmus in this question, the upper bound is exponential in the number of states of the NFA, so this reduction does not work.

Is there a valid reduction from a NP-Hard problem, or is this problem solvable in polynomial time?


texts: Funding opportunities for non-european people going to Europe for a PhD in TCS

texts:
There are two chinese students who would like to come to Spain to pursue a PhD in TCS in our group. I know of course the funding possibilities in my country but wonder if you know any European and non-European and Chinese funding calls or opportunities for doing PhD.

An extension of this questions; is it there around any funding/grant stack exchange site or which ones do you use to track grants?


texts: Implications of resolving $BPP$ vs $PSPACE$

texts:
The relationship between the complexity classes $BPP$, $P$, and $NEXP$ is currently undetermined. We know that $P \neq EXP$ by the time hierarchy theorem, but we don't know if $BPP = P$ (as many believe) or $BPP = EXP$ (considered unlikely) or somewhere in between. But, we do know a few interesting implications that would result from determining this one way or another:

$P \neq BPP \implies P \neq NP$
$P = BPP \implies BPP \neq EXP$

and so forth.

What I am wondering is, how does the relationship of $BPP$ to $PSPACE$ affect these relationships?

For instance, we know that $BPP \subset PSPACE$, but it is not known whether $BPP = PSPACE$ (considered unlikely) or $BPP \neq PSPACE$.

If this relationship is finally determined one way or the other, would it have any effect on what we know about the relationship between $BPP$ and $EXP$, on $BPP$ and $P$, on $P$ and $PSPACE$, on $PSPACE$ and $EXP$, or on $P$ and $NP$?

Conversely, would clearing up anything about the undetermined relationships of these other classes imply or lead to a proof that $BPP \neq PSPACE$?

I believe $BPP = PSPACE$ would make $PH$ collapse to at least its second level, which is where $BPP$ is contained; I am not sure if it would collapse entirely.


texts: Non-backtracking paths and the zeta function of graphs

texts:
This question has also been posted on mathSE here: https://math.stackexchange.com/questions/2215888/non-backtracking-paths-and-the-ihara-zeta-function

For a connected $d$-regular graph $G=(V,E)$ with adjacency matrix $A$, we defined a sequence of matrices
$$A_0,A_1,A_2,A_3,\dots$$
defined using powers of $A$ inductively as follows:
 $$A_0=I$$
 $$A_1=A$$
 For $k \geq 2$,
$$A_{k}=A_{k-1}A-(d-1)A_{k-2}$$
Just like $(A^k)_{v,w}$ counts the number of walks on $G$ from $v$ to $w$, the value $(A_k)_{v,w}$ counts the number of walks on $G$ from $v$ to $w$ without backtracking.
The recurrence relation above can be used to easily show that the ordinary (matrix) generating function for the above sequence is
$$\sum \limits_{k=0}^{\infty} t^k A_k = (1- t^2)I. \left( I-tA + (d-1)t^2 I \right)^{-1}$$
With some abuse of notation, we can rewrite this generating function as
$$\frac{1-t^2}{I-At+(d-1)t^2}$$

On the other hand, the Ihara zeta function of the graph $G$ is given by
$$\zeta_G(t) = exp \left( \sum \limits_{k=1}^{\infty} N_k \frac{t^k}{k} \right)$$
where $N_k$ is the number of closed non-backtracking walks on $G$ of length $k$. It is known that $\zeta_G(t)$ has an alternate expression using determinants as
$$\zeta_G(t) = \frac{(1-t^2)^{|E|-|V|}}{det(I-At+(d-1)t^2)}$$

My question is: can the determinant formula for the Ihara zeta function be derived from the generating function for the matrices $A_k$? After all,
$$N_k = Tr(A_k)$$
and the expressions for the generating function and zeta function involve the same matrix expressions.

However, I am not clear what taking the determinant of a generating function intuitively gives us, nor is it clear if matrix operations like taking trace or determinant are even well-defined when applied on such generating functions. A similar question has been asked here https://math.stackexchange.com/questions/583883/how-to-get-from-chebyshev-to-ihara?noredirect=1&lq=1
and I have also been trying out ideas from here https://math.stackexchange.com/questions/154776/proof-of-2-matrix-identities-traces-logs-determinants
But I am not interested in the Chebychev polynomial connection here: just whether the generating function can be manipulated using logarithms and traces to obtain the expression for the zeta function. Thanks.


texts: Improved lower bound on monotone circuit complexity of perfect matching?

texts:
Razborov proved that every monotone circuit that computes the perfect matching function for bipartite graphs must have at least $n^{\Omega(\log n)}$ gates (he called it "logical permanent"). Has a better lower bound for the same problem been proved since then? (say $2^{n^\epsilon}$?) As far as I remember this problem was open in the mid 1990's.

I am aware that the clique function requires exponential-size monotone circuits and so on, but I am interested in perfect matching specifically.


texts: What are possible implementations of Haskell's type classes and what are their (dis)advantages?

texts:
As far as I know, a Haskell function with type classes constraints is internally compiled to a function with additional arguments that receive dictionaries with the necessary implementations of each particular type class.

Are there any other possibilities how compile type classes?
If so, what are their (dis)advantages?
And what compilers use them?


texts: Complexity of constructing minimum depth decision trees

texts:
I am interested in the computational complexity of

Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does there exist a binary decision tree of depth at most $n$ with decisions $x_j \overset{?}{=} 1$ for any $x \in \{0,1\}^J$ and any $j \in J$ such that, at any leaf of the tree, there are only elements of $A$ or only elements of $B$?

I often see claims of Problem 1 being NP-complete due to a famous reduction of 3-dimensional perfect matching, via exact cover by 3-sets, by Hyafil and Rivest (1976). My understanding, however, is that they establish NP-completeness of the slightly different

Problem 2: Given a finite, non-empty set $J$, given $A \subseteq \{0,1\}^J$ and given $n \in \mathbb{N}$, does there exist a binary decision tree of depth at most $n$ with decisions $x_j \overset{?}{=} 1$ for any $x \in \{0,1\}^J$ and any $j \in J$ such that, at any leaf of the tree, there is at most one element of $A$?

Can anyone help me fill the gap or point me to other work establishing complexity results for Problem 1?

Remark: While Hyafil and Rivest (1976) establish a result for an average depth, their argument is easily adapted to the minimum depth.

One further remark (risking to make the question seem less relevant to some):
Consider the following generalization of Problem 1 that specializes to the latter for $m = 2$.

Problem 3: Given a finite, non-empty set $J$, given $m \in \mathbb{N}$, given pairwise disjoint $A_1, \ldots, A_m \subseteq \{0,1\}^J$, and given $n \in \mathbb{N}$, does there exist a binary decision tree of depth at most $n$ with decisions $x_j \overset{?}{=} 1$ for any $x \in \{0,1\}^J$ and any $j \in J$ such that, at any leaf of the tree, there are elements of at most one of the sets $A_1, \ldots, A_m$?

Problem 2 is polynomially reducible to Problem 3, for instance, by defining for each $a \in A$ of Problem 1 a separate subset $A_a = \{a\}$ of Problem 3. This reduction requires, however, that we can choose $m = |A|$. It is not generally possible in the special case of Problem 3 where $m = 2$, which is Problem 1.

At the same time, reducibility of Problem 2 to Problem 3 is sufficient for  many informal claims, e.g., of exact learning of binary classification trees from examples being NP-hard due to Hyafil and Rivest (1976), or of extending partial pseudo-Boolean functions by minimum depth decision trees being NP-hard due to Hyafil and Rivest (1976).
I just do not see how this holds for two-class classification and Boolean functions, respectively.


texts: Nonregular Languages in Sublogarithmic Space

texts: Are there any known languages that require $o(\log n)$ space but are also not regular?  I'm looking for a problem "just below" undirected connectivity.


texts: Languages that we cannot (dis)prove to be Context-Free

texts:
I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.

  Is there a recent survey on the subject or an open problem section from a recent conference ?

  Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.

The examples I found are:

the well known language of Primitive words $Q = \{ w \mid w \neq u^i (|u| > 1) \}$ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)
the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory, which perhaps has been solved by domotorp, see his preprint)

Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_{Goldbach} = \{ 1^{2n} \mid 2n$  cannot be expressed as a sum of two primes$\}$). I'm not quite interested in such examples.


texts: Is parametrized maximum independent clauses problem in FPT?

texts:
Parametrized maximum independent clauses problem:
Input : A r-CNFSAT formula F having n variables and m clauses, k
Ques  : Does there exists at least k clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.
Parameter : k
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated.


texts: Maximum weight matching and submodular functions

texts:
Given a bipartite graph $G = (U \cup V, E)$ with positive weights let $f: 2^U \rightarrow \mathbb{R}$ with $f(S)$ equal to the maximum weight matching in the graph $G[S\cup V]$.

Is it true that $f$ is a submodular function?


texts: On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

texts:
It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses.
Being $s_k=\text{inf}\{\delta: \text{there exists }2^{\delta n}\text{ algorithm for solving }k\text{-SAT}\}$, it has been shown in [2] that, assuming $\text{ETH}$, $s_k$ increases infinitely often as $k\to \infty$, that is to say the complexity of $k\text{-SAT}$ grows as $k$ grows.

Question
Is the second statement known to hold, under $\text{ETH}$, also in the $2^{o(m)}$ realm?
More precisely, being $\mu_k=\text{inf}\{\delta: \text{there exists }2^{\delta m}\text{ algorithm for solving }k\text{-SAT}\}$, does $\text{ETH}$ imply that $\mu_k$ increases infinitely often as $k \to \infty$?

Which Problems Have Strongly Exponential Complexity? by R. Impagliazzo, R. Paturi and F. Zane (December 1999)
On the Complexity of $k$-SAT by R. Impagliazzo and R. Paturi (January 2001)

Update 22/11/2020
To avoid ambiguities or misunderstandings, let me clarify that here the number of clauses is not super-linear in the number of variables. The $k\text{-SAT}$ instance I'm talking about is already sparse, that is to say $m = \Theta(n)$. I'm interested in knowing the consequences on $\text{ETH}$, if any, of an algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$. The existence of such algorithm proves that the sequence $\mu_k$ as defined above decreases monotonically, rather than increasing infinitely often. That's precisely why I've asked this question in the first place.
Update 26/11/2020
Following daniello's comment below, let me clarify that here each clause has exactly $k$ distinct literals, and that trivial clauses are not allowed to be present.


texts: Relationship between Turing Machine and Lambda calculus?

texts: Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?


texts: Questions about computing matrix rigidity

texts:
Matrix rigidity was introduced by Valiant in 1977:

The rigidity $Rig_M(r)$ of boolean matrix $M$ over GF(2) is the
smallest number of entries of $M$ that must be changed in order to
reduce its rank over GF(2) down to $r$.

$Rig_M(r)$ has a deep connection to boolean function complexity & circuit lower bounds by a result of Razborov 1989 see eg [1]. It also has a connection to finding locally correctable codes eg see [2]
It appears to me there is little to no published empirical analysis of $Rig_M(r)$ & that it could give some useful insight into its properties (thinking for example of the transition point research with SAT).
As a start I was interested in analyzing $Rig_M(r)$ using a simple greedy algorithm. The idea is as follows.

generate random matrixes $M$.

Compute Delta_row(i,j) where i,j are row (vectors) of $M$ and Delta_row(i,j) is the Hamming distance between the two rows

likewise calculate the Delta_col(i,j) where i,j are column vectors of $M$ (equivalent to calculating Delta_row(i,j) of the transpose of M).

next sort Delta_row(i,j) and Delta_col(i,j) and remove the column or row from $M$ with the "lowest value". (the lowest value is associated with a row or column pair, remove either row or column of the pair).

This greedy algorithm can be used to estimate $Rig_M(r)$ by giving a (fairly tight?) upper bound. One repeatedly reapplies the greedy algorithm until the matrix $M$ has been reduced to size $r$ and counts the sum of the Delta_row/col values of removed rows. and note that upon removing rows or columns, the new Delta_row and Delta_col arrays can be computed efficiently without recalculating the whole arrays.

how far off can the greedy algorithm be from the optimal value $Rig_M(r)$?

what kind of matrices maximize the difference between the greedy algorithm and the optimal rigidity measure?

can a modified local greedy algorithm find the optimal value $Rig_M(r)$

[1] Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 "rigid matrices require large circuits"
[2] On matrix rigidity and locally self-correctable codes by Zeev Dvir
[3] ECCC reports tagged matrix rigidity
[4] Matrix rigidity talk/overview by Mahdi Cheraghchi
[5] The geometry of matrix rigidity by Landsberg et al
[6] Blog note on Midrijanis paper on Matrix rigidity by Lance Fortnow
[7] Empirical results in CS papers


texts: Complexity lower bound of finding the factorial of a number

texts:
I was wondering about the complexity of the factorial of a number mostly because this problem is not referenced in the complexity books I have read.

Two similar problems, Matrix Multiplication and Factorization are in, almost, all discussions about $\mathrm{P}$ and $\mathrm{NP}$. The complexity of the first is a major research field, see here, and we are trying to put Factorization inside $\mathrm{P}$.

But for the, seemingly, close problem of Factorial nothing is being said. Almost no result at all. The only one I could find is the one mentioned here and the wiki article from the far away 1983.

Why there is no interest in it? Can it have any implications in Complexity Theory like Factoring? Can Factorial be in $\mathrm{P}$ ?

Lastly one thought, Factorial must be in $\mathrm{NP}$ (or better in $\mathrm{FNP}$?) the certificate would be the actual number? that is $n!$ ?


texts:
[This question was initially asked here. It went unanswered so I thought I should ask it in a different community.]

I am reading this paper by Hopfield et al. On page six, the authors defined the energy function of the Traveling-Salesman-Problem (TSP) mapped onto an artificial neural network as follows:

$$E = \frac{A}{2} \sum_X \sum_i \sum_{j \ne i} V_{Xi} V_{Xj} + \frac{B}{2} \sum_i \sum_X \sum_{X\ne Y} V_{Xi} V_{Yi} + \frac{C}{2} (\sum_X \sum_i V_{Xi} - n)^2 + \frac{1}{2D} \sum_X \sum_{Y\ne X} \sum_i d_{XY} V_{Xi} (V_{Y, i+1} + V_{Y, i-1})$$

Here the first three terms maintain correctness of the function while the final term calculate actual distance of the tour. Later on page seven, the authors picked the values of A, B, C and D for simulation.

I don't understand on what basis they choose those values. Any help?


texts:
Let $\mathcal{X}= \{1,-1\}^n$, $E$  the set of edges and $J$ some real-valued matrix. Van der Waerden's theorem gives constant $c$ and set of edge weights such that

$$\sum_\mathbf{x\in \mathcal{X}} \exp \sum_{ij \in E} J_{ij} x_i x_j = c \sum_{A\in C} f(A) $$

Where $C$ consists of Eulerian subgraphs over $E$, $f(A)$ is the weight of $A$ defined as the product of weights of edges in $A$

Edge weights are strictly below 1 in magnitude. Suppose only a small number of self-avoiding loops on the graph have non-negligible weight. We can approximate the sum by only considering Eulerian subgraphs including these loops. However, a small number of such loops can give a large number of Eulerian subgraphs. Is there a more efficient way?


texts:
The Complexity Zoo points out in the entry on EXP that if L = P then PSPACE = EXP.  Since NPSPACE = PSPACE by Savitch, as far as I can tell the underlying padding argument extends to show that $$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} = \text{EXP}).$$  We also know that L $\subseteq$ NL $\subseteq$ NC $\subseteq$ P via Ruzzo's resource-bounded alternating hierarchy.

If NC = P, does it follow that PSPACE = EXP?

A different interpretation of the question, in the spirit of Richard Lipton: is it more likely that some problems in P cannot be parallelized, than that no exponential-time procedure requires more than polynomial space?
I would also be interested in other "surprising" consequences of NC = P (the more unlikely the better).
Edit: Ryan's answer leads to a further question: what is the weakest hypothesis that is known to guarantee PSPACE = EXP?

W. Savitch. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.
W. L. Ruzzo. On uniform circuit complexity, Journal of Computer and System Sciences 22(3):365-383, 1971.

Edit (2014): updated old Zoo link and added links for all other classes.


texts:
When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. In this context we do not need a tight bound on the running time of the reduction. It suffices to have any polynomial bound, allowing that it may possibly have a very high degree.

Nevertheless, for natural problems, the bound is typically a low degree polynomial (let us define low as something in the single digits). I do not claim that this must always be the case, but I am not aware of a counterexample.

Question: Is there a counterexample? That would be a polytime computable many-one reduction between two natural $NP$-complete problems, such that no no faster reduction is known for the same case, and the best known polynomial running time bound  is a high degree polynomial.

Note: Large, or even huge, exponents are occasionally needed for natural problems in $P$, see
Polynomial-time algorithms with huge exponent/constant. I wonder if the same also occurs in reductions among natural problems?


texts: Automata recognizing $X^*$ for a finite code $X$

texts:
Let $\Sigma$ be a finite alphabet. A code $X$ over $\Sigma$ is a subset of $\Sigma^*$ such that each word in $X^*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is finite if $|X|$ is finite. What is known about (minimal) automata recognizing $X^*$ for a finite code $X$? Is there any characterization of such automata (in terms of the structure of the automaton, without knowing $X$)? Is it possible, having such automaton, extract the code $X$ in polynomial time?

I am also interested in these questions when we omit the fact that $X$ is a code, i.e., assume only that $X$ is a finite set of words.


texts: K-Clustering of a Graph maximizing intra-cluster weights?

texts:
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.

Input: A complete graph G with non-negative integer weights on edges and an integer $K\ge 2$.

Output: A $K$-partition $P=\{P_1, ..., P_K\}$ of $V(G)$

Measure (to maximize): The sum of the weights for the edges with both endpoints in the same set of $P$, i.e.:
$$
M(P)=\sum_{i=1}^k \sum_{u,v\in P_i} w\left( u,v \right)
$$
where $w$ is the edge-weight function.

Thanks in advance for any suggestion.


texts: How to describe the set of "all computable functions" using Coq?

texts:
Would the set of all computable functions be just the set of all maps of the form

f : forall n : nat, P n -> nat

where P : nat -> Prop, and (P n) has a proof whenever (f n) is defined - so, n is in the domain of f. Is this some smaller set of maps actually computable by Coq, or is this what I want?

If not, is there an existing formalization? Using lambda calculus, or combinators K and S, or some basic concept of an algorithm?

Perhaps along with a proof of the Snm theorem - that says this set is enumerable?


texts: Observational Equivalence of open terms in PCF

texts:
The notion of observational equivalence is rather intuitive, but formally I'm having some doubts in the particular case of open terms.

Lets consider the simple case where  the terms M and N are free variables, M = x and N = y. Choosing the program context C[-] = (λxy.[-]) v w we have,
C[M] = (λxy.x) v w →* v
C[N] = (λxy.y) v w →* w
So by definition M and N wouldn't be observationally equivalent.

However, consider any adequate denotational semantics of PCF. Then by definition of adequacy, ⟦M⟧ = ⟦N⟧ implies M and N observationally equivalent. The denotations of both (open) terms are,
⟦M⟧ = ⟦x ⊢ x⟧ = id
⟦N⟧ = ⟦y ⊢ y⟧ = id
From what we conclude M and N  to be observationally equivalent.

So, surely I must be going wrong somewhere, and I suspect it to be some trivial mistake. But where?


texts: Why is complementary slackness important?

texts:
Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint.

The two primary reasons for applying CS (as taught in graduate courses and textbooks):

To check the optimality of the LP
To help solve the dual

Given today's computing power and polynomial algorithms for solving LPs is CS still relevant from a pragmatic viewpoint? We could always just solve the duals and address both the points above. I agree that it's "more efficient" to solve the dual with the help of CS but is that it? Or is there more to CS than meets the eye? Where exactly is CS useful beyond the above two points? I've commonly seen texts alluding to the concept of CS when talking about approximation algorithms but I fail to understand its role there.


texts: Examples of the value of proofs for algorithms

texts:
In teaching Intro. Algorithms to undergrads, one of the most difficult tasks is to motivate why they need to know how to prove things about algorithms. (For many students, at least in many US universities, they may see some basic proofs in Discrete Mathematics, but Algorithms is often the first time they have to use proofs to reason about algorithms.) While I think I can do a decent job motivating this at an abstract level, concrete examples are much more convincing, hence my question:

  I'm looking for concrete examples that show the value of proofs in algorithms.

A couple questions already address this, and if you have answers to those, please add them there:

Examples of algorithms and proofs that seem correct, but aren't
How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect

However, I think there are other ways proofs can be valuable beyond the above. E.g., by working through the proof you can gain an insight that leads to a more efficient algorithm, or to an algorithm for a related problem, or to an idea for developing a better test suite to test your implementation, etc.

Some criteria:

Answers here ideally shouldn't fit one of the questions above (as I said, please add an answer there if you have it)
Should be presentable to Intro. Algorithms students. While the proof itself need not be presentable, the story should be presentable (e.g. the statement of the problems involved, some idea of how the proof led to something that just "eyeballing correctness" would not have). If you are unsure about this point, go ahead and add it as an answer and I'll do my best to see if it can be presented to this audience.
Should be as natural as possible. Artificial examples are kinda okay, but real examples are much more motivating to students.
Note that I am talking here about abstract proofs for abstract algorithms, not formal (/automated/etc) proofs of algorithm implementations. As a litmus test, the ideas involved should not be language-specific.

(While this question is not exactly research-level, I think it might get more answers here than on cs.SE, as I suspect the answers will come from  historical examples in the theory of algorithms that expert researchers on this site are more likely to be familiar with.)


texts:
I'm unsure whether the following three equations constitute a valid instance of a reader/environment monad on the simply-typed lambda calculus, where $\alpha$ is any type (I subscript some terms with their types), $\mathbb{M}$ is the proposed monadic type modality), $\eta$ is the unit of the monad and $\mu:\mathbb{M} \mathbb{M}\alpha → \mathbb{M}\alpha$ is the join of the monad:
$$\mathbb{M} \thinspace α = ((s → t) → t) → α  \hspace{1cm} ∀α$$
$$ \eta \, a_{\alpha} = \lambda c_{((s \to t)\to t)}.\; a \hspace{2cm} ∀a_{\alpha}$$
$$\mu\,b_{\mathbb{M}\mathbb{M} \alpha} = λc_{((s → t) → t)}.\; b_{\mathbb{M}\mathbb{M}\alpha}\, c\, c \hspace{1cm} ∀b_{\mathbb{M}\mathbb{M} \alpha} $$
I'm unsure because this would allow us to generate terms of type $((s → t) → t) → s$, which is not constructively valid, given $((s → \bot) → \bot)$ does not constructively entail $s$. However, in the type system I am using, type $s$ is not the type of truth values, but the type of Kripke states. I don't know whether this matters.
If I changed the definition of the monad so that the first equation was substituted by the following equation, would it be a valid instance of a reader monad?
$$\mathbb{M} \thinspace α = ((\beta → t) → t) → α , \hspace{1cm} ∀α \text{ and where } \alpha \neq \beta$$

Edit:
Following on from Andrej Bauer's comment below, I suppose I am confused about whether we can we always construct a reader monad by type synonyms of the form $u = x$, for arbitrary function types $x$?


texts: Maximizing a monotone supermodular function s.t. cardinality

texts:
I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this.

  Question: Is it known to be true or is there a hardness result contradicting that, for a monotone non-decreasing supermodular $f$, there is a polynomial-time
  constant-factor approximation algorithm for maximizing $f$ subject to
  a maximum cardinality constraint?

Background: Given a ground set $U$ of items, $f: 2^U \to \mathbb{R}_{+}$ is supermodular if for all subsets $A,B$ of $U$, we have $f(A) + f(B) \leq f(A \cup B) + f(A \cap B)$. It is monotone non-decreasing if $S \subseteq S' \implies f(S) \leq f(S')$. A maximum cardinality constraint means to maximize $f(S)$ over all subsets $S$ of size at most $k$, where $k$ is given as input.

My current understanding: This problem seems under-studied because supermodular maximization is equivalent to submodular minimization, so people focus on the latter. Submodular minimization subject to a smallest-size cardinality constraint (i.e. $|S| \geq k$) has a very strong lower bound[1].

But there are several issues in transferring such bounds. (1) It is not clear how the notion of approximation factor would transfer (I'm assuming my supermodular function is nonnegative so the transformation would be always negative...). (2) I'm assuming my supermodular function is montone increasing, whereas it seems nobody has been motivated to study the case of negative decreasing submodular minimization. (3) In this particular example, the cardinality constraint "goes the wrong way".

For a different example approach, you might try to reason as follows. The clique problem (find a clique of size k) is hard, and in fact, known to be inapproximable, hence my objective is inapproximable. However, when you think about the supermodular objective function for clique, it would be "find the set of at most $k$ vertices having the most edges in their induced subgraph", whereas the inapproximability result applies to "find the largest clique of size at most $k$". And I don't see a hardness result anywhere for the correct objective. The same kind of issue seems to go for planted clique and densest $k$-subgraph.

In short, it seems that it would be very surprising to have an approximation, but nobody has bothered to prove this in so many words (though actually for all I know, an efficient approximation algorithm exists).

[1] Svitkeina, Fleisher 2008 http://arxiv.org/abs/0805.1071


texts:
EDIT at 2011/02/08:
After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic classes part please see Benefits for syntactic and semantic classes.

$\mathsf{UP}$ (the unambiguous polynomial time, see wiki and the zoo for references) is defined as languages decided by $\mathsf{NP}$-machines with an additional constrain that

There is at most one accepting computation path on any input.

The precise relations between $\mathsf{P}$ vs $\mathsf{UP}$ and $\mathsf{UP}$ vs $\mathsf{NP}$ are still open. We know that worst-case one-way functions exist if and only if $\mathsf{P} \neq \mathsf{UP}$, and there are oracles relative to all possibilities of the inclusions $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$.

I'm interested in why $\mathsf{UP}$ vs $\mathsf{NP}$ is an important question. People tend to believe (at least in literature) that these two classes are different, and my problem is:

  If $\mathsf{UP} = \mathsf{NP}$, are there any "bad" consequences happened?

There is a related post on complexity blog in 2003. And if my understanding is correct, the result by Hemaspaandra, Naik, Ogiwara and Selman shows that if

There is an $\mathsf{NP}$ language $L$ such that for each satisfiable formula $\phi$ there is a unique satisfying assignment $x$ with $(\phi,x)$ in $L$,

then the polynomial hierarchy collapses to the second level. No such implication is known if $\mathsf{UP} = \mathsf{NP}$ holds.


texts: Break text evenly into certain number of lines

texts:
There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth & Plass) and "evenly" means:
http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Is there an algorithm or a concave cost function for algorithm above which would take into account the number of lines I would like the text break into, instead of the maximum line width? Also in linear time?

In other words, I'm looking for a line breaking (or paragraph formation, or word wrapping) algorithm where the input is the desired number of lines, not the desired line width.

Just to describe a practically unusable approach: There are N words and N-1 spaces in-between each word pair, M is the desired number of lines (M <= N). After each space there might be at most one (possibly zero) line-break. Now, the algorithm would try to place the breaks in each possible combination, calculating the "raggedness" and return the best one. How to do it much faster?

Also, does such a problem have a name? What "family" of problems does it belong to? (E.g. "bin packing") If I wouldn't need the perfectly optimal solution, just a very good one, is it possible to solve it much faster? (some form of heuristics could be usable, if for a given input there were always the same, possibly sub-optimal, solution).

Update

Chandra Chekuri suggested bellow "a problem in Kleinberg and Tardos chapter on dynamic programming". It was a good read but it deals with line breaking based on width rather than line count. It might be adaptable to this problem which is something I'm trying to figure out now. Here is a good link to the solution, they even claim to solve it in linear time:
http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

Also, there is a chapter "8.5 The Partition Problem" in The Algorithm Design Manual by Skiena which seems to be exactly on-topic, I'm still reading it, tough. (Unfortunately, from what I understood it has quadratic time complexity)


texts: Help with a special case for Hungarian algorithm

texts:
I am working on a problem and it appears to be a special case of Hungarian algorithm.

In Hungarian algorithm for assignment problem, there are n people and n jobs.
Each person can do any of n jobs and incur a corresponding cost C.
The goal is to minimize the cost by assigning n people to n jobs.
My special case that for each person, he can be assigned only 2 specific
jobs out of n jobs. Given this condition, is there any optimization
possible for Hungarian algorithm that will reduce its complexity from
O(n^3) to lower.

Thanks for your help.


texts: Algorithm to Bulk Delete nodes from a Treap

texts:
I have a Treap, and want to bulk delete nodes in a given key range (i.e. the nodes to be deleted are consecutive nodes in an in-order walk of the tree). If I have $n$ nodes in the Treap, and $k$ nodes are to be deleted, is there an algorithm that can let me do this in $O(k + \log n)$. Or maybe provide a lower-bound proof that shows that that is impossible?

The obvious algorithm seems to be the one where the following steps are performed:

The treap is first split into 2 treaps by rotating the predecessor of the first node to be deleted to the root: $O(\log n)$
Detach the right child of the root: $O(1)$
Rotate the successor of the last node to be deleted in the detached treap and throw away the left subtree of this treap: $O(\log n)$
Meld the 2 remaining treaps: $O(\log n)$

However, I'm worried that the treap will get skewed (or will they)?


texts: How to recognize safe queries in tuple relational calculus?

texts: How do I determine whether query in tuple relational calculus is a safe query?


texts:
Assume you are given a matrix
$$
X=
\begin{bmatrix}
x_1^1 & x_1^2 & \dots & x_1^m \\
x_2^1 & x_2^2 & \dots & x_2^m \\
\vdots & \vdots & \ddots & \vdots \\
x_n^1 & x_n^2 & \dots & x_n^m
\end{bmatrix}
$$
such that all $x_i^j \in \big\{0,1\big\}$, $\vee$ is the logical OR, and:
$$
\forall i,j, \quad x_{i}^j =
\begin{cases}
x_{i+1}^{j}\vee x_{i+1}^{j-1} & \text{if }\:j\neq1,\\
x_{i+1}^1\vee x_{i}^m & \text{otherwise}.
\end{cases}
$$
This is quite similar to the Pascal triangle with binomials, except here we are dealing with $0/1$ variables and regular addition is replaced by the logical OR.

The problem now is to minimize: $$S=\sum_{i,j} x_i^j,$$ where the trivial case $S=0$ with all $x_i^j=0$ is not an option. The sum is the one in the integers: $0<S\leq n m$.

EDIT: What can we say about the case where the $\vee$ operator is no longer the logical OR, but is defined by: $0\vee0=0$, $1\vee0=0\vee1=1$ and $1\vee1\in\{0,1\}$.

Does this problem reduces to another one? Maybe there are references that I am not aware of.

Thanks for your help.


texts:
Let $X\in\{0,1\}^d$ be a Boolean vector and $Y, Z\in\{0,1\}$ are Boolean variables. Assume that there is a joint distribution $\mathcal{D}$ over $Y, Z$ and we'd like to find a joint distribution $\mathcal{D}'$ over $X, Y, Z$ such that:

1). The marginal of $\mathcal{D}'$ on $Y, Z$ equals $\mathcal{D}$.

2). $X$ are independent of $Z$ under $\mathcal{D}'$, i.e., $I(X;Z) = 0$.

3). $I(X; Y)$ is maximized,

where $I(\cdot;\cdot)$ denotes the mutual information. For now I don't even know what is a nontrivial upper bound of $I(X;Y)$ given that $I(X;Z) = 0$? Furthermore, is it possible we can know the optimal distribution $\mathcal{D}'$ that achieves the upper bound?

My conjecture is that the upper bound of $I(X;Y)$ should have something to do with the correlation (coupling?) between $Y$ and $Z$, so ideally it should contain something related to that.


texts: What is the standard name for the function which inflates a string by duplicating each of its characters?

texts:
Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters.

For instance:
$$ f(abc) = aabbcc$$
or, more generally, a second argument could be provided to specify the number of copies:
$$ f(xy,4) = xxxxyyyy$$

This should be embarassingly standard, so don't hesitate to shoot me in your response!
(on the other hand, it is always difficult to search for something you cannot name, but I wouldn't accept such a lame excuse from my students, so...)


texts: First use of sans serif for complexity classes

texts:
(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...)

It seems that it has become popular in recent years to write the names of complexity classes in a sans serif font (see e.g. these two papers). My question is: where does this notation come from? In particular, what is the first occurrence of the use of this notation in the literature?

The paper "Algorithms for Boolean Function Query Properties" by Scott Aaronson (SIAM Journal on Computing 32(5):1140-1157, 2003; the arXiv version dates back to 2001) uses this notation, but is there anything earlier?


texts: First order satisfiability that doesn't have finite models

texts:
We know from Church's theorem that determining first order satisfiability is undecidable in general, but there are several techniques we can use to determine first order satisfiability. The most obvious is to search for a finite model. However, there are a number of statements in first order logic that we can demonstrate have no finite models. For instance, any domain in which an injective and non-surjective function operates is infinite.

How do we demonstrate satisfiability for first order statements where there aren't finite models or the existence of finite models is unknown? In automated theorem proving we can determine satisfiability several ways:

We can negate the sentence, and search for a contradiction. If one is found, we prove first order validity of the statement and thus satisfiability.
We use saturation with resolution and run out of inferences. More often than not, we will have an infinite amount of inferences to make, so this isn't dependable.
We can use forcing, which assumes the existence of a model and also the consistency of the theory.

I don't know of anyone implementing forcing as a mechanized technique for automated theorem proving, and it doesn't look easy, but I'm interested if it's been done or attempted, as it's been used to prove independence for a number of statements in set theory, which itself has no finite models.

Are there other techniques known for searching for first order satisfiability that are applicable for automated reasoning or has anyone worked on an automated forcing algorithm?


texts: Harmonic analysis of sequences of Boolean functions (i.e. of words in $(\{0,1\}^n)^*$)

texts:
Is there any research on harmonic analysis of sequences of Boolean functions, which represent the application of a Boolean function on a word in $(\{0,1\}^n)^*$?
I'm looking for any reference on this, since my searches are not coming up with anything. Maybe I'm missing the right keywords.
To be more precise, consider a Boolean function $f:\{0,1\}^n\to \{0,1\}$, and extend it to a function $f^*:(\{0,1\}^n)^*\to \{0,1\}^*$ by $f^*(w_0w_1\cdots w_m)=f(w_0)f(w_1)\cdots f(w_m)$.
Now, for example, we can now measure the influence of a coordinate $i$ on $f^*$ by measuring the measure of words $x$ for which flipping the $i$-th coordinate in some letter of $x$, causes a change in the resulting word $f^*(x)$.
Are such notions studied anywhere?


texts:
At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and co-RE. However, something else defined through computability theory is the concept of an immune set. Immune sets are ones where you are unable to enumerate even an infinite subset.

My question is this: is there a complexity class of decision problems where an infinite subset of "yes" instances can be enumerated, and is there a "better" name for it than "not immune"? I ask this because complexity classes are typically named for what they are, but "immune" describes what the decision problem is not.


texts: What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)

texts:
According to Immerman's Descriptive Complexity diagram, there is a logic called $\mathsf{FO(REGULAR)}$ which captures $\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. Does anyone know the definition? And what paper originally proved this result?

Unlike the classes $\mathsf{AC}^i$ which are captured by iterated quantifiers ($\mathsf{FO}[\log^i(n)]$), it is interesting that $\mathsf{NC}^1$ would require extending the language with a new construct. I might imagine that it is some form of querying for membership in a regular language, but this is only a guess.

My copy of Descriptive Complexity (Immerman 1999) doesn't seem to mention the result (maybe I need the newer version). The best I can find is the paper

An algebra and a logic for NC1. Kevin J. Compton and Claude Laflamme, 1990.

which gives a logical characterization of $\mathsf{NC}^1$, but an apparently different one: it is called $\mathsf{FO} + \mathsf{RPR} + \mathsf{BIT}$ (first order logic extended with "relational primitive recursion" and the BIT relation, which gives binary representations of integers).

My interest in this is that I want a "natural" logic that extends both FOL and regular languages, and $\mathsf{NC}^1$ is the most immediate class to try. (Other possible choices are $\mathsf{L}$, $\mathsf{NL}$, and $\mathsf{NC}$, but these extensions would be less conservative.)


texts: Complexity of the Schönhage–Strassen algorithm

texts:
In the Wikipedia article, the complexity is listed as $O(n \cdot \log (n) \cdot \log (\log (n)))$, where $n$ is the number of bits.

Would the real bound be given by setting $n=\frac{b}{w}$, where $b$ is the number of bits and $w$ is the word length in the computer? i.e., if I assume that numbers of size $\log (n)$ can be multiplied in $O(1)$ time, then can two numbers of size $r \log (n)$ be multiplied in $O(r \cdot \log (r) \cdot \log( \log (r)))$?


texts: Data structure for storing points and finding a predecessor of a point

texts:
I am looking for a good data structure for storing a set of points
$P\subset \mathbb{N}^n$ that is able to answer the following query:

  Given a point $x=(x_1,\cdots,x_n)$, does there exist a point $p = (p_1,\cdots,p_n)\in P$ such that $p \leq x$, meaning that $p_i\leq x_i$ for all $i\in \{1,\cdots, n\}$?
  If the answer is yes, then the data structure should return one such point.

Ideally, it should be possible to dynamically add points to $P$.

The data structure can 'forget' a point $p \in P$ if there exists another point $p'$ with $p' \leq p$.

The use case that I am thinking about has 'small points'.
Something like $x = (x_i)$ with $\sum_i x_i \leq 30$.
But has a somewhat larger $n$.

ps: I have removed the copy on SO.


texts: Is solving the following system of boolean equations NP-hard?

texts:
I reduced a problem I'm currently working on to the following system of boolean equations:
$$
X_i \iff
\begin{cases}
\bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\
true \\
false
\end{cases}
$$
Where $|B|>=1$ for all $B \in A_i$ and each $X_i$ has exactly one of these defining equations.
I need to find $X_i$ that satisfies all these equations ($A_i$ are given). I'm wondering if this problem is NP-hard. I couldn't reduce the general boolean satisfiability problem to it yet.
Ideally, I would find an algorithm to solve this problem in polynomial time. If it's NP-hard I guess I have to hope that SAT solvers can solve it reasonably fast.
Thanks!

Here's an example:
$$
X_1 \iff true \\
X_2 \iff false \\
X_3 \iff X_4 \\
X_4 \iff X_1 \vee (X_2 \wedge X_3)
$$


texts: Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

texts: An answer to the traveling salesman (and similar) problems can be easily verified on light lambda-calculi. Also, if I understand correctly, the light lambda-calculi can compute every polinomial-time computable function. That way, if one can prove that the traveling salesman problem can't be encoded on the light lambda-calculi, that would also prove the problem can't be solved in poly-time, which would also prove P!=NP. Is that correct, or am I confusing some concepts?


texts: Independent set size in triangle-free graphs

texts:
Consider a triangle-free graph $G$. The notations used are:

$\alpha(G) = $ the size of a largest independent set of $G$.
$n(G) = $ the number of vertices in $G$.

Theorem (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$,

$$\alpha(G) \geq \frac{n(G)}{8\Delta}\log_2\Delta.$$

The book "Probabilistic Methods" by Alon-Spencer gives a very cute proof in the section "The Probabilistic Lens", (pg 272).

But the theorem is true even when $\Delta$ is subsituted by the average degree $d_{avg}$ in the above expression and Bollobas proves this in his book "Random Graphs, 2nd edition", pg 332, using completely different techniques.

My Question : Can we obtain Bollobas' result by tweaking the technique used by Alon-Spencer?

PS: For a graph theory enthusiasts, both proofs are worth reading!

Thanks in advance!


texts: Is minimal cover under symmetric 3-deduction NP-complete?

texts:
Forgive me if this problem is known by another name, I do not know any references for it.

Symmetric deduction. An equation $e \in E$ is a subset of variables $V$ such that knowing $|e| - 1$ of the variables allows you to deduce the missing one.
Minimal cover under symmetric deduction. Does there exist a set of $k$ variables such that their closure under symmetric deduction with equations $E$ equals all variables $V$?

This problem is proven NP-complete in this question. There is a limited version of this problem:

Minimal cover under symmetric $d$-deduction. Same as before, except $\forall e\in E: |e| \leq d$. That is, each equation has degree $d$ or lower.

This problem is trivial for $d = 2$ (choose one variable per connected component), and NP-hard for $d = 4$ as shown by Thinh D. Nugyen here.
What about $d = 3$?


texts: Formalization of proofs and computational complexity paradox?

texts:
While reading some articles on formal proofs (see also my previous question on cstheory about the length of ZFC proofs versus human written proofs), I came up with this apparent paradox.

Let $M_{const}$ be a program that given Turing machine $M$ checks if there is a short ZFC proof $\Gamma$ of length $|\Gamma| \leq |M|^2$ that $M$ runs in constant time.

Program M_const( M )
  enumerate all strings S of length  <= |M|^2
    verify if S is a proof of "M in O(1)"
      if it is a valid proof the halt and accept
  if no valid proof is found halt and reject

Now, we can build $M_{paradox}$ that knows its own code (by the recursion theorem) and on input $x$
first simulate $M_{const}( M_{paradox} )$; if it accepts then loop from $1$ to $|x|$
 (so it falls in $O(n)$), otherwise halts (so it falls in $O(1)$).

Program M_paradox( x )
  String M = self_code()  // ok by the recursion theorem
  simulate M_const( M )   // simulate M_const on M_paradox
    if it accepts then for i = 1 to |x| do nothing // -> O(n)
    otherwise halts                                // -> O(1)
  some dummy unused code here  // see below

It is clear (and hopefully provable in ZFC) that:

$M_{const}$ always halts and is correct;
if $M_{const}( M_{paradox} ) = Yes$ then $M_{const} \notin O(1)$ by construction; so we have a contradiction;
so $M_{const}(M_{paradox}) = No $; and we can have:

(a) $M_{paradox} \notin O(1)$ OR
(b) $M_{paradox} \in O(1)$ AND there is not a short proof of it;

but case $(a)$ cannot hold by construction; so ...

$M_{paradox} \in O(1)$
AND there is not a short proof of it;

But steps 1--4 can be formalized in ZFC and (unless I'm missing something, its length depends only linearly on $|M_{paraox}|$) so we can add some dummy code to $M_{paradox}$  until such ZFC proof is shorter than $| M_{paradox}|^2$ (we can use the fact that the runtime of a Turing machine doesn't change if we add unused states, it only affects the self representation); so we get a contradiction with point 5 which says that there is not a short proof of $M_{paradox} \in O(1)$ ???

  Q1. What is the output of $M_{const}( M_{paradox} )$ ?

Update: There were another question Q2 here, but it I decided to post it as a new "Part II" question to avoid confusion.


texts:
Is it known if tensor rank of three dimensional tensors lies in VNP (non deterministic valiant class)? If yes, what is known about high dimensional tensor rank?

In fact I am interested in much more simple problem. I would like  to know if one can construct class non-zero polynomials $f_n$ which lies in VNP, in $n^3$ variables such that $f_i(T)=0$ if tensor rank of $T$ less than $n^{1.9}$.
For simplicity let us assume that we are working over $\mathbb{C}$.

I would like to mention that it is O.K. if $f_i(T)=0$ for $T$ of high rank only what I need is that $f_i(T)=0$ for all small rank tensors.


texts: reference for lexicographic path ordering

texts:
Can you recommend a good reference for reading about lexicographic/recursive path orderings?

I'm currently reading about lpo's in Chapter 2 of the Handbook of Automated Reasoning, 'Resolution Theorem Proving' by Bachmair and Ganzinger, but the presentation is really terse. I would ideally like a more tutorial-like introduction w/ examples.


texts: Is there any equation-based method for transforming Büchi-automata to omega-regular language?

texts:
I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows.
      First we construct a set of equations named "(1)" based on an automaton $A$:
            \begin{equation}\begin{aligned}&l_1 = \varepsilon + p_{11}l_1 + p_{12}l_2 + ... + p_{1n}l_n\\
                         &l_2 = \varepsilon + p_{21}l_1 + p_{22}l_2 + ... + p_{2n}l_n\\
                         &...\\
                         &l_n = \varepsilon + p_{n1}l_1 + p_{n2}l_2 + ... + p_{nn}l_n, \end{aligned}\end{equation}
where are $l_1,...,l_n$ are the locations (or called "states") of $A$ with $l_1$ the initial location, $p_{ij}$ are regular expressions. Then we apply Arden's rule:

"$X = p^*q$ is the unique solution for equation $X = q + pX$"

to solve the equations. The result of $l_1$ is the regular expression we want.

Now my question is, is there a similar method for transforming Büchi automata into omega-regular language?


texts:
What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones.

In particular, would it have any consequences on the lower classes?


texts: Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?

texts:
Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H_n$ greedy algorithm does not readily extend to the set partial cover problem, where the goal is to pick a minimum-cost family of sets to cover $p \cdot n$ of the $n$ elements, where $0<p<1$ is a constant. But it sure seems to!

Greedy: repeatedly choose the most cost-effective set, i.e., one minimizing $c(S)  /\min(|S-C|,pn-|C|)$, where $C$ is the set of elements covered so far.

That is, the standard set cover greedy's cost-effectiveness definition is modified so that the benefit of a set is the min of # new elements and # of additional elements you still need to get.

Then it would seem that you can just say: number the elements $e_1,...,e_{pn}$ in order covered (ignoring any additional ones covered--we'll allocate all the costs to these first $pn$ elements), and argue that at the moment when greedy covers $e_k$, choosing all of $OPT$ would take care of your outstanding $\ge pn-k+1$ element needs, with cost per "satisfied element need" of at most $\alpha = OPT/(pn-k+1)$, so there's got to be a set that's at least that good, so greedy's going to choose one at least that good, which gives us a total bound of $OPT \sum_{i=1}^{pn} 1/(pn-k+1) = H_{pn} OPT$.

But apparently this argument is flawed. How so?

(Slivak writes in his thesis, "Even though [the algorithms] are quite similar, it turns out that the approach used by Chvatal, Lovasz, or Johnson cannot be used to establish a reasonable bound on the performance [...]. The reasons are that only a fraction of points of the set $U$ are covered and that the part of $U$ covered by the optimum partial cover can be completely different from the part covered by the greedy cover. This makes the analysis of the performance bound [...] quite complicated."
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.5734&rep=rep1&type=pdf And Kearns proved a $2H_n+3$ bound, and presumably not because he simply overlooked the obvious approach.)


texts: Rademacher complexity and lowerbounds in learning theory

texts:
Is there any function class known whose Rademacher complexity has a non-trivial lowerbound?
Can the Rademacher complexity be used to lowerbound the generalization error in any learning situation?


texts: Simulating Turing machines (output included) with circuits

texts:
A Turing machine with input alphabet {0,1} computes a partial or total function $f \colon \{0,1\}^* \to \{0,1\}^*$. Is it possible to construct a circuit family $\{C_n\}$ such that for an input $x$ of length $n$, $C_n(x) = f(x)$? I have not seen this kind of circuit family in any of the standard texts, nor have I encountered it after lots of googling.

I understand that for decision problems, it is unnecessary to consider such circuit families (which is probably why nobody has bothered to consider them). Or maybe it is just a trivial modification and so is relegated as an exercise to the reader (although I haven't seen such an exercise mentioned anywhere).

There are two immediate obstacles, which I see, that such a circuit family would need to overcome:

What does $C_n(x)$ do when $f(x)$ diverges?
If $|x| = |y|$, but $|f(x)| < |f(y)|$, the output of $C_n(x)$ will contain less bits than $C_n(y)$. How would this work?

I personally don't see any method of overcoming these obstacles.