texts: Another Solution Problem (ASP) of integer multi-commodity flow: is it NP-complete?

texts:
I know that integer multicommodity flow is NP-complete. It was proven in

On the complexity of time table and multi-commodity flow problems

that any SAT problem can be reduced to an integer multicommodity problem.

I also know that the ASP version of SAT (finding additional solutions to a SAT problem when a number of solutions are already known) is also NP-complete. It was shown in

Complexity and completeness of finding another solution.

My question: is the ASP version of integer multicommodity NP-complete as well?

The authors of the second article defined an ASP reduction, and proved that if one problem can be reduced by ASP-reduction to a problem that is ASP-complete, then that problem is also ASP-complete.

I never formally studied computer science, and I'm not sure if the reduction between integer multicommodity to SAT is an ASP reduction... I'd be grateful if someone from this field would know the answer.


texts: Unambiguous Problems and Classes over Reals

texts:
Are there  unambiguous analogues of $NP_{R}$ (using the BSS model, in all discussion)complete problems, and any results known about them? For instance, the canonical $NP_{R}$ complete problem $4FEAS$ ( ref. here but there could be a better reference ) could have an unambiguous version - $U4FEAS$ ( not allowing degenerate roots, for simplicity)in which there is only one zero or root for a system of degree 4 polynomial (for more about quantifiers over reals ). Of interest to study such unambiguous classes could be  (loosely) Smales' 17th problem. How would the complexity differ (from say, $NP_{R}$, or higher in the $PH_{R}$ hierarchy) when we just have one root for a system of polynomials in the above context?
As the $PH$ can be defined over arbitrary structures - $K$, there is a $PH_{K}$, over that structure. We could have an Unambiguous Polynomial Hierarchy over the structure $K$- $UPH_{K}$-  ( analogous Unambiguous Polynomial Hierarchy), are there any results of Unambiguous versions of classes over Reals?


texts: Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

texts:
Problem statement :

Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?

Is this problem NP-complete? Has it been studied? Is there an algorithm allowing to find such a word?


texts: Hardness of computing circles with max number of lattice points

texts: You're given an $n\times n$ lattice $\mathcal{L}$, and you're asked to compute the maximum number of points in $\mathcal{L}$ that can belong to the same circle (the circle has to be enclosed by the outer sides of $\mathcal{L}$ and its center does not need to be in $\mathcal{L}$). How hard is this problem? Is it harder than factoring $n$? Are there decent bounds or estimates on the max number defined above?


texts: Time-bounded Kolmogorov complexity and non-random strings

texts:
If $t$ is a time constructible function then we can define the time-bounded Kolmogorov complexity of a string $x$ as:

$C^t(x)$ = the size of the smallest program p that generates $x$ in $t(|x|)$ steps

We can also extend the incompressibility notion: a string $x$ is incompressible if $C^t(x) \ge |x|$ (otherwise $x$ is compressible).

Now we can define the function:

$f^t(n) = | \{ x \text{ : } |x|=n \text{ and } x \text{ is compressible with respect to } C^t \} |$

( $f^t(n)$ is the total number of compressible strings of length n ).

What is the relation (if any) between $t$ and the rate of growth of $f$? Can we say something about it?

EDIT:
For example, can we choose $t$ to make $f$ grow polynomially? ... NO


texts: generalizations of hidden subgroup problem

texts:
Quantum Fourier Sampling tries to solve hidden subgroup problem which is defined via a map $f$ from group $\mathrm{G}$ to some set $X$ that separates cosets of sum unknown subgroup $\mathrm{H}$.
$f(g_1)=f(g_2)$ iff $g_1 \in g_2 \mathrm{H}$. The task is to find (generators of) $\mathrm{H}$. The underlying map $f$ partitions $G$ into cosets of $\mathrm{H}$. Are there any generalizations where $f$ is not necessarily distinct on distinct cosets. In particular if there are some cosets which are 1 and some others are 0, and we ask to find either $\mathrm{H}$,  how effective is QFS? If not, then how close can we go? Lets say finding some or all cosets of $H$ going to 0.


texts: NIZK proofs: Why is the prove function necessary?

texts:
In NIZK proofs, the prover can generate its proof for statement $y$ and witness $w$ using

$$\pi \gets \mathrm{Prove}(\sigma,y,w)\text{,}$$

where $\sigma$ is the common reference string. Source: Wikipedia.

However, the zero knowledge property tells us that everyone could have generated a pair $(\sigma, \pi)$ itself. Source: Wikipedia.

So what is prove needed for? I guess it is needed, because the verifier forces the prover to use a given common reference string $\sigma$? This is probably the reason why the verifier can not convince any other verifier?


texts: Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates?

texts:
In "Attacking the busy beaver 5" by Heiner Marxen and Jürgen Buntrock, an algorithm to create tree normal candidates is explained (it also contains a concise introduction of the relevant terms).

If during simulation an undefined transition is found, the selection of the enumeration values is made as follows:

  Enumerate all meaningful values (see below) for this transition, and
  recursively do step 2 with M set to each of these more completely
  defined machines.

  The set of legal transition values is formed by an arbitrary
  combination of (n+1) target states, 2 symbols to write, and 2
  directions to move. The set of meaningful transitions enumerated in
  step 6 is a subset of all legal ones by the following reduction rules:

  From the set of states M has not yet taken, only the smallest one (according to some arbitrary but fixed order on the states) is used as
  target state (isomorphism).
  When defining the very first transition force a state change (else M never halts), write a one (isomorphism), and move left (symmetry).
  This completely fixes the very first transition.
  When defining the very last transition, consider only the halt state as target state.
  If the target state is the halt state, go left (makes no difference) and write a one (never worse). This completely fixes the
  last transition.
  If there is a state that M has not yet taken, do not consider the halt state as target state.

I'm not sure if I'm missing something, but should there not be a rule that enforces using a new state if we're determining the last open slot of all currently used states? This new rule would replace/extend rule 3 above.

In other words: With $2k-1, k \leq N$ transitions defined, and the maximum index of states used being $\leq k$, the $2k$-th transition must point to a state with index > $k$.

If we don't do this, it would be possible to create closed subsets, or equivalently, unreachable states (described e.g. by Kellett, MA thesis, 2005, p.46), one of whom will be the halting state. Those machines cannot possibly halt obviously.

For instance, given the partially defined 3-state machine 1RB 0RB, 1LA -?-, -?- -?-, the next transition (which in this example happens to be $\delta(B,1)$) must point exactly to state C.

Pointing to H is not allowed because it would quit too early (unused state C).
Pointing to A or B is not allowed because it would lead to a closed state subset with no way to leave.


texts: How do you decide when you have enough research results to write a paper and to which journal you submit the paper

texts:
In some research area in CS we got some very interesting results. Now we are thinking about publishing them. In the group we are, the philosophy is to publish inmediately small things in conference papers, which is ok but not the best. Now I am thinking about collecting more of these "small things" and publish in a JCR paper, impact factor more than 2. My question here is how would you decide when you have enough material to prepare a decent paper in a JCR journal? And furthermore, once you think this is ok, how would you decide to which journal you submit the paper to?

PS: JCR refers to Journal Citation Reports, an extensive list that collects info about the most representative and relevant journals in all scientific areas along with their impact factors, so they are usually refereed and no conference papers there


texts: Reaching the double exponential upper bound in Fourier-Motzkin elimination

texts:
One round of Fourier-Motzkin elimination may yield $n^2/4$ inequalities where $n$ is the original number of linear inequalities, whence an upper bound of $n^{2^d}/2^{2^{d+1}-2}$ for $d$ rounds of elimination without removal of redundant constraints.

I'm wondering whether it is possible to meet this upper bound.

(Note: this is a distinct question from that of counting the number of true faces in a projection, that is, after removal of redundant constraints, for which McMullen's upper bound provides a tighter bound.)


texts: What is the complexity class most closely associated with what the human mind can accomplish quickly?

texts:
This question is something I've wondered about for a while.

When people describe the P vs. NP problem, they often compare the class NP to creativity.  They note that composing a Mozart-quality symphony (analogous to an NP task) seems much harder than verifying that an already-composed symphony is Mozart-quality (which is analogous to a P task).

But is NP really the "creativity class?"  Aren't there plenty of other candidates?  There's an old saying:  "A poem is never finished, only abandoned."  I'm no poet, but to me, this is reminiscent of the idea of something for which there is no definite right answer that can be verified quickly...it reminds me more of coNP and problems such as TAUTOLOGY than NP or SAT.  I guess what I'm getting at is that it's easy to verify when a poem is "wrong" and needs to be improved, but difficult to verify when a poem is "correct" or "finished."

Indeed, NP reminds me more of logic and left-brained thinking than creativity.  Proofs, engineering problems, Sudoku puzzles, and other stereotypically "left-brained problems" are more NP and easy to verify from a quality standpoint than than poetry or music.

So, my question is:  Which complexity class most precisely captures the totality of what human beings can accomplish with their minds?  I've always wondered idly (and without any scientific evidence to support my speculation) if perhaps the left-brain isn't an approximate SAT-solver, and the right-brain isn't an approximate TAUTOLOGY-solver.  Perhaps the mind is set up to solve PH problems...or perhaps it can even solve PSPACE problems.

I've offered my thoughts above; I'm curious as to whether anyone can offer any better insights into this.  To state my question succinctly:  I am asking which complexity class should be associated with what the human mind can accomplish, and for evidence or an argument supporting your viewpoint.  Or, if my qusetion is ill-posed and it doesn't make sense to compare humans and complexity classes, why is this the case?

Thanks.

Update:  I've left everything but the title intact above, but here's the question that I really meant to ask:  Which complexity class is associated with what the human mind can accomplish quickly?  What is "polynomial human time," if you will?  Obviously, a human can simulate a Turing machine given infinite time and resources.

I suspect that the answer is either PH or PSPACE, but I can't really articulate an intelligent, coherent argument for why this is the case.

Note also:  I am mainly interested in what humans can approximate or "do most of the time."  Obviously, no human can solve hard instances of SAT.  If the mind is an approximate X-solver, and X is complete for class C, that's important.


texts: How are imperative languages more different from each other than functional languages?

texts:
I'm reading Simon Peyton Jones's The Implementation of Functional Programming Languages and there's one statement that surprised me a little bit (on page 39):

  To a much greater extent than is the
  case for imperative languages,
  functional languages are largely
  syntactic variations of one another,
  with relatively few semantic
  differences.

Now, this was written in 1987 and my thoughts on this subject might be influenced by more modern programming languages that weren't around or popular then.  However, I find this a bit hard to believe.  For instance, I think that the described Miranda programming language (an early predecessor to Haskell) has much more different semantics compared to a strict language like ML than say C has to Pascal or maybe even C has to smalltalk (although I'll cede that C++ provides some validation of his point :-).

But then again, I'm basing this on my intuitive understanding.  Is Simon Peyton Jones largely correct in saying this, or is this a controversial point?


texts: Is this some variant of the Knapsack Problem?

texts: We are a set of items $I = \{I_1, I_2,.. I_n\}$, which need to be placed in a certain number of knapsacks $K$. We can use as many knapsacks as we want and each knapsack has an infinite capacity but certain pairs of items $N = \{(I_i,I_j),..\}$ cannot be together in a knapsack, certain pairs of items $Y = \{(I_i,I_j),..\}$ have to be placed together and for certain pairs there is a cost of not placing them together in a knapsack given by $M = \{(I_i,I_j, C_{ij}),..\}$. The objective is to place all the items in knapsacks such that the constraints specified by $Y$ and $N$ are satisfied and the sum of the overall cost incurred due to not placing items together (given by $M$) is minimised.


texts:
Say I want to find a unification for the following two sentences in first-order logic:

P(x) & Q(y)
Q(A) & P(B)

Common sense tells us that {x: B, y: A} is such a unification. However, if I apply the standard unification algorithm, then we will go through the following steps:

Attempt to match & with & (succeeds, returns {}, go to step 2)
Attempt to unify P(x) with Q(A) (go to step 3)
Attempt to match P with Q (return failure)

The algorithm returns failure because it doesn't know that & is commutative.

We could fix that by telling our unification algorithm that And and Or are commutative. But more generally we might have a user-defined relation that is commutative, for example

IsRelated(Mother(x),Father(x))
IsRelated(Father(John),Mother(John))

Again, the standard unification algorithm would return failure, even though these terms can be unified.

How is this dealt with in practice, e.g. in theorem provers, or type inference algorithms?


texts:
Consider the following process:

There are $n$ bins arranged from top to bottom. Initially, each bin contains one ball. In every step, we

pick a ball $b$ uniformly at random and
move all the balls from the bin containing $b$ to the bin below it.
If it already was the lowest bin, we remove the balls from the process.

How many steps does it take in expectation until the process terminates, i.e., until all $n$ balls have been removed from the process? Has this been studied before? Does the answer follow easily from known techniques?
In the best case, the process can finish after $n$ steps. In the worst case it can take $\Theta(n^2)$ steps. Both cases should be very unlikely though. My conjecture is that it takes $\Theta(n\log n)$ steps and I did some experiments which seem to confirm this.
(Note that picking a bin uniformly at random is a very different process that will obviously take $\Theta(n^2)$ steps to finish.)


texts: Is this minimization problem NP-Complete?

texts:
We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns.

The problem is to partition the columns of $A$ into at most $m$ subsets, each of size at most $b$, such that the number of critical subsets is minimized (with minimum $m$), where a critical subset is a subset of the set of columns such that if we remove it from $A$ the reduced matrix has rank less than $n$.

By the phrase "minimum m" I mean that we want to partition using minimum subsets (at the max we can use $m$ subsets) without sacrificing the number of critical subsets. For example, suppose we are getting the optimum config (i.e number of critical subsets is minimum) with $m_1$ subsets ($m_1$ < $m$), then we need not use all the $m$ subsets. In real world these $m$ subsets are $m$ boxes. If I can get the optimum config with less than $m$ boxes, I need not use the remaining ones, they can be saved. Our aim is to solve the problem for any $n$,$k$,$m$,$b$ and any $A$ matrix with the mentioned properties i.e. we want to design a general polynomial time algorithm or prove that the general algorithm is NP-Complete.

The problem seems NP-Complete to me. It a special case of "set cover/maximum coverage problem" and that's why it is becoming very difficult to reduce from the general set cover/maximum coverage problem.

The elaborate problem definition/relevant discussion can be found at https://math.stackexchange.com/questions/57412/optimization-problem-for-a-parity-check-code. As we could not reach to any solution there, I am posting it here.


texts: Classes of graphs with easy Hamiltonian cycle but NP-hard TSP

texts:
The Hamiltonian Cycle Problem (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The Travelling Salesman Problem (TSP) consists in finding a cycle that goes through all vertices in a given edge-weighted graph and minimizes the total distance measured by the sum of the weights of the edges in the cycle. HC is a special case of TSP, and both are known to be NP-complete [Garey & Johnson]. (See the links above for more details and variants of these problems.)

Are there any studied classes of graphs on which the Hamiltonian Cycle Problem is solvable in polynomial time via a non-trivial algorithm, but the Travelling Salesman Problem is NP-hard?

Non-trivial is to exclude classes such as the class of complete graphs, where a Hamiltonian cycle is guaranteed to exist and can be found easily, or generally classes of graphs where a HC is always guaranteed to exist.


texts:
Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

I cannot find an reference.


texts: Results about computability power or limitations of shared read/write registers

texts:
I want to know more results about the computability power or limitations of shared $\texttt{read/write}$ registers/objects in distributed/concurrent computing theory.

Two typical examples are:

[1]. All types of atomic $\texttt{read/write}$ registers are equivalent in terms of computability: we can simulate the most complex one (i.e., multi-writer multi-reader multi-value atomic register) using the simplest ones (i.e., single-writer single-reader binary atomic registers).

[2]. Atomic $\texttt{read/write}$ registers have consensus number $1$. Therefore, from a set of atomic registers, it is impossible to construct a wait-free implementation of stack, queue, test&set, compare&swap, or memory-to-memory swap.

[1] "The Art of Multiprocessor Programming (book abstract)" by Maurice Herlihy and Nir Shavit, 2008.

[2] "Wait-Free Synchronization" by Maurice Herlihy, ACM Transactions on Programming Languages and Systems, 1991.

  Do you know any other results about the computability power or limitations of shared $\texttt{read/write}$ registers in distributed/concurrent computing theory?

Pointers to the literature would be appreciated.


texts: Generalization Issues with Practical Suggestions from Universal Approximation Theorem with Neural Networks

texts:
After having read matus's beautiful answer in this thread  explaining (among other things) Cybenko's proof of the Universal Approximation Theorem for Neural Networks, I wonder: if we use a piecewise constant function to approximate the target function, won't this have horrendous implications for generalization?

In practice, the only information we have about the target function comes from the training data, which makes up a discrete set. The machine learning task, as perhaps suggested from the Universal Approximation Theorem, could be dealt with by taking 'the simplest' piecewise constant function which perfectly fits the training set, and representing that as a neural net with one hidden layer, sigmoid transfer functions, and an identity output node.

But one can intuitively tell that such a trained model would perform terribly on test data! Because given an unseen case C, lying between training cases A1, A2, ..., Ak, instead of assigning as output some middle ground between the output for cases A1 .. Ak, it will assign exactly the output for Ap, where Ap is the nearest of the Ai to C.

So is there not a lot less value in this theorem if it cannot enrich the intuition of a machine learning engineer wishing to construct the optimal neural network for a given task?


texts: Scrambling a Rubik's cube by an adversarial noob

texts:
My friend dislikes Rubik's cubes, and he asked me how to frustrate amateur solvers by adversarially scrambling the cube. I expect that the answer depends highly on the particular solving algorithm.

  Are there "human" algorithms for solving a Rubik's cube that are known to be very inefficient (compared to optimal) against particular "bad" configurations?

By "human", I mean the common algorithms that are taught in practice to amateurs or used by enthusiasts. There might be too much variety in common human techniques for this question to make sense, but even that would be good to know. (I'm looking for something more interesting than naive random walk, which is clearly almost always inefficient.)

And the relevant followup question:

  Are there ways to find these bad configurations by applying random moves?

That is, is there an easy way to randomly generate hard cube instances for a particular human algorithm?

This is (somewhat) related to another question of mine about shortest paths to solution when randomly scrambling a Rubik's cube.


texts: Another edge partitioning problem on cubic graphs

texts:
This question was motivated by a closely related problem
An edge partitioning problem on cubic graphs

Input: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$

Question: Is there a partition of $E$ into subgraphs isomorphic to $K_{1,2}$ and $K_{1,1}$  such that the sum of the orders of the corresponding subgraphs is exactly $k$ ?

  Is this problem polynomial time solvable or is it $NP$-complete?

Edit: Changed input graph to at most cubic graphs to avoid triviality.


texts:
I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem.

Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has exactly $k$ ones. For any element $x \in \{0,1\}^n$ let $N_l(x)$ be the set of elements obtained by flipping one of the 1's in x to 0. (Generally referred to as the lower shadow of X)

Let the majority upper shadow of $A_k$ referred to as $M_u(A_k)$ be the set such that for each $a \in M_u(A_k)$ number of ones in $a = k+1$ and $|N_l(a) \cap A_k| \geq (\frac{k+1}{2})$. That is more than half of a's neighbours are present in $A_k$. Given the size of $A_k$ can we put an upper bound on the size of $M_u(A_k)$.

Has this problem been studied and are there results are relevant to the above. Note that in case $|A_k| = \binom{n}{k}$ we of course have that $|M_u(A_k)|=\binom{n}{k+1}$. In general I am looking at the size of $A_k$ to be $\epsilon\cdot \binom{n}{k}$ where $\epsilon$ is a small constant.

Could you also refer to me a good survey of the Kruskal-Katona Theorem in general , one that surveys recent results in this setting ?

Thanks in advance


texts: Problems rephrased as quadratic unconstrained binary optimization

texts:
I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions. A very nice review with many examples can be found in Andrew Lucas' Ising formulations of many NP problems. He shows problems such as Graph Coloring or 3SAT as a minimisation problem.

My question is: In general, what type of problems can be mapped to QUBO? In particular, is it possible to map even more difficult problem (such as counting solutions of 3SAT or other #P problems) to QUBO?

Are there examples for that, or would that contradict some results or strongly believed conjectures about computation complexity?


texts: Has the semantics of TeX (as a programming language) ever been formalized?

texts:
It seems to me that the macro language employed by $\TeX$ can maybe be seen as some kind of term rewriting system or some kind of programming language with call-by-name scoping.

Even modern implementations of the $\TeX$ engine (e.g. $\mathit{Xe}\TeX$) interpret code in a quite direct way and I'm not aware of any attempt at optimizing the execution (like modern optimizing interpreters can do). However, devising correct optimization passes for a language like $\TeX$ is going to be very difficult because of the "action at a distance" that macro redefinitions can have, and the ability of redefining macros by calling them by name.

So implementing an hypothetical optimizing interpreter for $\TeX$ sounds a very difficult problem in practice but also a very useful one, since $\TeX$ is used all over math and science and slow compilation times are a known drawback of the system. Note that the majority of time is spent interpreting code, not computing the actual typesetting, especially when computationally heavy packages are used (such as tikz).

Maybe a formal semantics for the language could be a start to address the problem. So has the semantics of the $\TeX$ programming language ever been formalized?


texts: On the interpretation of coinduction in type theory

texts:
The notion of (co)datatype can be modeled satisfactorily in category theory  as fixed-points of polynomial functors. Then, (co)induction principles are derived from initial algebras/terminal coalgebras structures.

I was wondering (following Harper's idea of computational trinitarianism), if such a nice model exists in the context of type theory.

Somewhat related is the situation in the Isabelle and Coq proof assistants. In Isabelle, the (co)datatype package builds on the notion of bounded natural functor (thus, category theory). The situation in Coq and other systems looks like codatatypes are constructed in terms of datatypes (similarly for coinduction/induction).

I have seen several discussions about how Coq or other systems that reduce coinduction to induction produce, when sound, formalisms that restrict syntactically the users. Thus, the engineering question here is, could Coq given its type theory foundations implement a similar (co)datatype package as Isabelle?

Note that Isabelle/HOL formalism can be understood as a form of weakly typed set theory.


texts: Taxonomy of notable regular expression automata

texts:
I'm trying to draw up a taxonomy of algorithms for transforming regular expressions into automata so as to perform some empirical tests of their complexity properties in specific domains.

I'm aware of several of the 'bigger' names, e.g.,

Thompson

"Regular Expression Search Algorithm", Thompson, 1968

Glushkov

"A New Quadratic Algorithm to Convert a Regular Expression into an Automaton", Ponty, et. al, 1996

Antimirov

"Partial Derivatives of Regular Expressions and Finite Automata Constructions", Antimirov, 1996

Follow

"Follow Automata", Ilie, et. al, 2003;

"Computing the follow automaton of an expression", Champarnaud, et. al, 2002

Hromkovic

"Translating Regular Expressions into Small e-Free Nondeterministic Finite Automata", Hromkovic, et. al, 2001

and their distinguishing properties (epsilon-free-ness, determinism, size, minimization, etc.) but I know this is not an exhaustive list.

I'm particularly interested in algorithms which present either significantly different time complexities to those listed above, and/or significantly different topologies.

If you know of others, a link to a paper which describes the construction algorithm in detail would be greatly appreciated (read necessary if I'm going to implement it!)

Edit: Added some references as per requested.


texts: Avoiding Cycles with Unification and Subtyping

texts:
Context

I realize that subtyping often doesn't admit principle types, and that inference in the presence of subtypes is undecidable. I'm working in a context where typechecking should simply fail there is not a single most general solution, and where annotations can be added to aid inference.

Suppose that we have a type system where, during typechecking, some types need to be inferred using unification, and may be type variables $\alpha, \beta$ etc.

If, at some point, the constraint $\alpha <: T_1 \to T_2$, where $\to$ is the usual function type constructor, then we can decompose this into $\alpha = \alpha_1 \to \alpha_2$, with $T_1 <: \alpha_1$ and $\alpha_2 <: T_2$.

The Problem

The problem arises if you have constraints  $\alpha_2 <: \beta_1 \to \beta_2$, $\beta_2 <: \alpha_1 \to \alpha_2$.

In such a case, we get:
$\alpha_2 = \alpha_{21} \to \alpha_{22}, \beta_1 <: \alpha_{21}, \alpha_{22} <: \beta_2 $ from the first constraint,
and $\beta_2 = \beta_{21} \to \beta_{22}, \alpha_2 <: \beta_{21}, \beta_{22} <: \alpha_2$ from our second problem.

If we substitute from our equalities, we then get (among other constraints), $\alpha_{22} <: \beta_{21} \to \beta_{22}$ and $\beta_{22} <: \alpha_{21} \to \alpha_{22}$, which is  identical to the form of our original problem. Clearly if we continue solving this way, we will never terminate.

When going to write a proof of termination, the problem is that substitution decreases the number of unsolved variables but increases the structural-size of the problems, and solving subtyping decreases the structural size of the problems, but increases the number of unsolved variables, so they don't work in a well-founded ordering.

My Solution Attempt

With my definition of subtyping, if $\alpha_2 <: \beta_1 \to \beta_2$, $\beta_2 <: \alpha_1 \to \alpha_2$ has no solution. The problem seems to be the "cycle", so if we do a sort of occurs check and fail when cycles are detected (or turn them into equality cycles, which will fail except for $\alpha <: \beta \wedge \beta <: \alpha$).

I'm not exactly certain how to formalize a cycle like this, and how such a check would give me something that I can use in a proof of termination.

My Question

My work is about the specifics of a particular subtyping system, but the problem here seems very general, so I'm wondering if this is a known problem, if there are known solutions to it, and if there is research that either formalizes or disproves my intuition about cycles.

What kind of cycles in subtyping constraints do I need to eliminate to avoid this infinite looping? Or is this a deeper problem with no solution?


texts:
I'm interested in sampling monotone increasing Boolean functions on $n$ input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers ($D_n = $ the number of monotone increasing Boolean functions on $n$ bits), so I don't expect a method to be very efficient, but I'm interested in a nontrivial method: not generating all of them and sampling from them and not rejection sampling.

Antichains are sets of incomparable points in a poset. The approach that seems to make sense to me would be sampling antichains in the Boolean cube: every monotone increasing Boolean function $f$ is defined by its minimal incomparable $1$s, which we will call $\partial f$ in this thread, and every set of incomparable bitstrings correspond to a monotone increasing (and decreasing) Boolean function. I've attempted to sample these, but all of my methods are not uniform, biased towards unbalanced functions.

Any thoughts on this would be appreciated; I am not necessarily expecting a full solution to be found in this thread.


texts: Job scheduling: minimizing number of reads

texts:
Consider the following scheduling problem:

input:

set of computations $C = \{c_1, ..., c_n\}$
set of computing nodes $P = \{p_1, ..., p_n\}$
Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ means $c_i$ depends on/reads $c_j$

output:

Schedule S = subset of $C \times [1,n]$ where $(c_i,k)$ means that job $c_i$ will be executed in timeslot $k$
the following conditions hold:

precisely one timeslot per job
dependencies have lower timeslots

Now, we want to minimize the cost of the schedule:

$cost(c_i,S) = |\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}|$
i.e. the cost of a job is the number of levels where it is read
$totalCost(S) = \sum_{c_i \in C} cost(c_i,S)$

Hence, we want to calculate the best way of assigning the computations to timeslots, such that the number of reads are minimized. Note that the number of computing nodes is irrelevant.

I cannot seem to find any papers on this specific problem. Does anyone know whether this has been investigated? It seems it has to be... :)

Edit:

we can rephrase this as a graph problem:
Consider a DAG $G = (V,E)$.

A schedule is a mapping $S:V\rightarrow\mathbb{N}$ which assigns a number to each node, such that if $v_1$ is reachable from $v_2$, then $S(v_1) < S(v_2)$.

Define the cost of a node $v_1$ is defined as $cost(v_1) = |\{S(v_2) \mid (v_2,v_1) \in E\}|$, i.e., the number of different numbers that are assigned to parent nodes.

The problem: find a schedule S that minimizes the total cost over the nodes.


texts: Clustering of letters - what approach would give the best results?

texts:
I am working on letter recognition program. I have a text and divide it into letters, every single letter is written to separate file.

Now I want to apply a clustering algorithm to these images to divide letters into classes. Ideally each cluster would correspond to single letter (this is not possible, because some letter patterns like "ri" or "ff" are classified as one letter by my text-dividing algorithm, but I'll address that later). The images contain some noise, as the text is scanned and also not every letter is at the center of the image: some are slightly shifted.

I am quite new to machine learning. Could you advise me on the choice of clustering algorithm? Which would give the best results in this case?

PS.: I am using python for this project, so any algorithms that have implementation in python (even partial) are of particular interest to me.


texts: What are the prerequisite disciplines for Computability theory? How much is Theory of Computation, Automata Theory, etc and how hard would it be studying it without those prerequisites?


texts: Class of languages recognizable by single-tape 3-state TMs

texts:
I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note that I allow arbitrary (finite) tape alphabets (i.e., the tape alphabet is not restricted to equal the input alphabet).

For convenience, call the class of languages recognizable by such TMs $C_3$. I have several questions about this class:

Has $C_3$ previously been studied?
Is $C_3$ known to equal any other complexity/computability classes of interest?
Is the class $C_3$ robust to changes in model. For example, if the TMs used are allowed to stay in place during a single transition (as opposed to always moving either left or right) or if the tape is made to be infinite in both directions instead of just to the right, does the class of languages recognizable by 3-state 1-tape TMs change?
How does $C_3$ relate to the class of regular languages, $Regular$? (In particular, is every regular language in $C_3$?)

A (rather cursory) search brought up only this cs.stackexchange post which is relevant but doesn't answer my questions and this paper, which I haven't read in enough detail to be sure that it concerns exactly the class $C_3$ rather than a similar but different class (the paper claims to prove that (1) every language in $C_3$ is decidable and (2) that $C_3$ and $Regular$ are distinct classes with non-empty intersection). As pointed out in the comments of the cs.stackexchange post, these kinds of TMs can be thought of as very particular cellular automata, so maybe someone who knows the literature on cellular automaton theory could help.


texts:
In the normal version of the matching problem, we are given a set of vertices $X$, $Y$, and $Z$, each of size $n$, and a set of edges $E\subseteq X\times Y\times Z$. We need to find a matching $M\subseteq E$ s.t. $|M| = n$ and it covers each element of $X$, $Y$, and $Z$ exactly once.

The variation is, can we find $M$ s.t. for any $(x_i,y_i,z_i), (x_j,y_j,z_j) \in E\smallsetminus M$, $x_i = x_j$ or $y_i = y_j$ or $z_i = z_j$?

This is the decision version of the 3d-matching variant. I wanted to know if this would also be NP-complete.


texts: Get Largest Inscribed Rectangle of a Concave Polygon

texts:
I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.

In other words, I want to continually cut my polygon down using rectangles until I am left with regions were the largest-inscribed rectangle is not sharing an edge with the original polygon.

Is there a known algorithm for this?

An example:

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

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


texts: Consequences of sub-exponential proofs/algorithms for SAT

texts: Would there be any major consequences if SAT had at most subexponential unsat proofs or even more strongly, SAT had subexponential-time algorithms?


texts: Is a CNF SAT problem NP hard when the total number (but not the width) of the 3-or-more-term clauses is bounded above by a constant?  What about specifically when there's only one such clause?


texts: Finding a graph that minimizes the number of nodes for a given number of paths

texts: There is a problem that is of great interest for communications and optics, but I do not know if there is an easy solution of it. We are looking for an oriented graph that goes from a node A (starting point) to a node B (ending point) that has a fixed number N different paths from A to B. Intermediate nodes that can only split or recombine two edges (so two input and two output nodes). What are the graphs that minimize the number of nodes met in all the N paths.


texts: Where do most REGEX implementations fall on the complexity scale?

texts: Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do these features let them parse statements that can't be described with a finite, non-pushdown automaton? How much closer to turing complete does this make them if they can?


texts: What is the name of a graph with local clustering coefficients equal to zero?

texts:
I am struggling to find in literature a name for a kind of graph where all local clustering coefficients are equal to zero (or, at least, bounded).
For instance, domino, a subset of cacti and all linear graphs belong to this class.
I do not know if such objects are named.


texts: Algorithm for identifying unprovable statements

texts:
I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms?

For example: If there is some conjecture that I am trying to prove, but might not be provable, can I know it in advance by some automatic method?

If this is generally undecidable, can 'some' (maybe not all) conjectures be ruled out automatically? Can this be done at least partially?

I am mainly concerned about complexity class relations. Are there any known unprovable relations in this field? If there are, how where they achieved?

In addition, can the "undecidability of proof existence" for some complexity class relation conjectures be proved?

A more specific example: It was proved that IP = PSPACE. Could we have proven that this can be proved (i.e. prove that either IP=PSPACE or IP not equal to PSPACE actually have a proof) without having a proof either way? Or at least, could we decide that a proof exists?


texts:
Given a strongly connected digraph G with weighted edges, I would like to identify edges that are provably not part of any minimal strongly connected subgraph (MSCS) of G.

One method for finding such edges is a modified Floyd-Warshall algorithm. Using the Floyd-Warshall algorithm, one can identify which edges are never the best option for going from vertex i to j. These nodes can't be part of a MSCS because it's better to replace them with two or more other edges.

The Floyd-Warshall pruning technique works quite well when edge weights vary significantly, but very poorly when edge weights are similar but large in magnitude.

Do you know any effective pruning methods for large, similar edge weights? Is this problem equivalent to a more common problem that I don't recognize? Has this sort of pruning been studied before in the literature?


texts: An algorithm for counting to Graham’s Number

texts:
I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory.

I thougth of the way to organize counter suitable for calculating $a{\uparrow\uparrow}b$, but got stuck at even smaller problem of counting to $2^a$, where $a$ is a 64-bit integer ($2^{21}$Tb needed for storage of such number is above what I assume reasonable).

Is there some clever technique to count beyond $2{\uparrow\uparrow}6$? Or is there any conceptual limitations on the counters with a polynomial-bounded memory?


texts:
How to solve the recurrence relation:

T(n) = T(n - 1) + T(n / 2)+ n

by recursion tree to get an asymptotic upper bound?

The height is n, but how to generalize the sum at each levels?


texts: NP-Completeness of Finding Minimum Automaton, in Gold's paper

texts:
I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "System Identification Via State Characterization", and I am confused now.
I also checked Is finding the minimum regular expression an NP-complete problem? but I am still confused.

Let us call Problem 1: Finding a minimum regular expression for a
given regular expression which has same language L.

Let us call Problem 2a: Finding automaton which can explain some data D.

Let us call Problem 2b: Finding an automaton with minimum states for
Problem 2a.

In "Complexity of Automaton.." paper, it states that
"However, it is the objective of this paper to show that the construction of a minimum state
automaton which agrees with given data is, in general, computationally difficult."

Then later, in Theorem 2:
"Minimum Automaton Identification Question Qmin(D, n). Given: data D,
 positive integer n. Question: Is there a finite automaton with n states which
 agrees with D ?

Now, I can easily create an automaton which fits the data. Lets call it G. I can also minimize G to get G*, and count the number of states.
As I wrote the whole question, I realized that if the answer to the following statement is "NO", then I do need further help. If the answer is "YES", elaboration is appreciated, but a simple yes will clear lots of confusion.
Given arbitrary automaton G for language L, if we use some Polynomial algorithm
to minimize it to G* (and P =/= NP), can there exist another smaller automaton S < G
(in number of states) such that language of S is exactly L?

If answer is "NO", please proceed. If the answer is "YES", feel free to elaborate. Any help is appreciated.
First question:

Gold assumes that a blackbox can be "identified in the limit". However I find that an a regular expression: ab(ab*)* to not apply here, since we don't know the number of states in the FSM we are trying to identify. Hence, this makes me believe Problem 1 is different than Problems 2a and 2b. Correct?

Second question:

Given the data, I can easily create an automaton, then minimize it. Based on what I've seen (and yet don't understand), the minimal automaton G* is not necessarily the "minimum automaton which can explain the data". There is confusion about what "explain the data" mean. If I minimize G to get G* some known polynomial algorithm, wouldn't that be "Exact" fit for the data? meaning all the data is accepted by G* and G*'s language is only all the data?

Third question:

Depending on how second question is answered, if there could be another smaller automaton which is difficult to obtain, then that should imply that polynomial minimization algorithms may produce different "minimal" automaton, based either on the algorithm, which I find absurd, or based on the "initial constructed automaton".

I think question 3 is absurd, which is forcing me to believe that Gold meant something specific  with "agrees with given data".
Any help is appreciated.


texts:
Is every Eulerian triangulated (planar) graph Hamiltonian?

On the other hand we have that:

  Barnette's Conjecture (Open): Every cubic bipartite (3-connected) planar graph is Hamiltonian.

Notice that: Eulerian triangulated planar graphs and cubic bipartite planar graphs are mutual duals.

I would be happy to know of a proof or a counterexample (I have not been able to find either). In the absence of both is this a well known conjecture?

Some additional facts (possibly relevant):

Every Eulerian triangulated planar graph is $3$-colorable (see this).
(Whitney's Theorem) Every $4$-connected triangulated planar graph is Hamiltonian.

Definitions:

Hamiltonian Graph: Undirected Graph with a simple cycle through every vertex.
Eulerian Graph: Connected graph with all degrees even.
Triangulated (planar) Graph: Planar graph with every face a triangle.
Cubic Graph: Graph with every vertex having degree exactly $3$.

Edit: (Thanks@domotorp) Triangulated planar graphs are not necessarily Hamiltonian (e.g. see this)


texts:
Inspired by this answer given by Noam, which I think implies (if I understood correctly his answer ) that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from a strings space $S$ to combinatorial objects in some space $Y$ such that $A$= $\{ a: a=f(x), x \in S \}$. The space $S$ represents the set of all witnesses $x$ of an $NP$ problem $A$.

This motivates studying the properties of the space $S$ (of all witnessing strings $x$) for various $NP$ problems.

  Is there a published work that studies space $S$ for various problems inside $NP$ such as $P$ problems, $NPI$ problems, and $NP$-complete problems?

UPDATE 9/7/2015:

The following formalism is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest  if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

Now, assume that there exists a universal witness set $W \subseteq \Sigma^*$ such that for every $NP$-complete set $D_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $g_i:W\to \Sigma^*$ such that $D_i=Range(g_i)$.

  What are the consequences of existence of a universal witness set for $NP$? Does it imply $P \ne NP$?

The last question is interesting only when the universal witness set $W$  is in $P$ (3SAT can be seen as universal witness set but it is not known to be in $P$).


texts: Term for a correspondence of two point sets regarding their ordering in each dimension

texts:
Let there be two sets of points $S$ and $S'$ in $R^d$. $|S| = |S'|$, and for each point $s_i$ in $S$ it exists exactly one corresponding point $s'_i$ in $S'$, such that the ordering of $S$ equals the ordering of $S'$ with respect to any axis of $R^d$.

Is there any term that describes this relationship or 'morphism' between $S$ and $S'$?

E.g. in $R^2$, if $x_{s_i} < x_{s_j}$ then $x_{s'_i} < x_{s'_j}$, or if $y_{s_i} \ge y_{s_j}$ then $y_{s'_i} \ge y_{s'_j}$, etc.


texts: Salomaa's axiomatisation of regular languages and the use of regular expression in it

texts:
I am reading the classical article of A. Salomaa where he gives two axiom systems for regular sets and proofs consistency and completeness.

As I have understood it, an axiomatic system in some logic (lets suppose predicate first order logic) are axioms formulated in the language of the logic, i.e. well-formed formulas together with primitive notions (constant, predicate or function symbols). And a (set theoretical) model is an interpretation for this.

For example, consider the theory of groups. The primitive notions are groups, multiplication, inversion and idenity, mostly written as $(G, \cdot, ^{-1}, 1)$ and the axioms would be
\begin{align*}
 & \forall x,y,z : (xy)z = x(yz) \\
 & \forall x \exists y : xy = 1 \\
 & \forall x : x1 = x \land 1x = x.
\end{align*}
The existence of certain groups shows its consistency, and as there are models such that for example the sentence $\forall x \forall y : xy = xy$
is either true or false, it is not complete. But essential here is that when talking about the theory we have just the axioms in mind, without bearing to any actual realisation/model.

Now to come back to Salomaa's paper, in his system $F_1$ he lists $11$ Axioms. Now it is easy to see that regular expression (defined as terms over some alphabet) are a model for these axioms, but besides that their might be other models. When dealing with questions about this axiom system in general we cannot argue with one specific model, or?

To be more specific, in Lemma 4 of his paper he shows that every regular expression has an equational characterisation (i.e. a set of equations this expression fulfills) and this is essential for the completeness proof. And the proof goes by induction over the construction of regular expression, so it works just for this specific model. But in fact he must how that everything (not just regular expressions) obeying the axioms have such an equational characterisation, so he must argue more general than using the specific model of regular expression?

Am I right? Or why does this works out... or am I confusing something here, in what sense does regular expressions go into the axiom system that we can use this model in proving statements about the axiom system (I guess this is not the only model, or?).


texts:
By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf

If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$.

If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\ne NP$).

$PP$ is the class of decision problems analog for $\#P$ and $P\subseteq PP\subseteq PSPACE$,

but neither $P=PP$ nor $PP=PSAPCE$ is known. But is it true that

$coNP^{\#P}=NP^{\#P}=P^{\#P}$?


texts: Universal Approximation Theorem for non-sigmoidal activation functions

texts:
The most cited Universal Approximation Theories for multi-layer feedforward neural networks by Cybenko (1989) and Hornik (1991) assume the activation functions of the network to be sigmoidal. However, currently one mainly uses ReLU activation functions (or variants) which are not sigmoidal (not even bounded).

I found a proof of the Approximation Theory summarized in Pinkus: Approximation theory of the MLP model in neural networks (1999), where he shows the approximation result for continuous activation functions $\sigma \in C(\mathbb{R})$ if $\sigma$ is not polynomial. Unfortunately, he only does this for the case of one hidden layer. I am unable to find a proof that also covers multi-hidden-layer neural networks with continuous activation functions that are not sigmoidal.

Does anyone know of such a result? Or is it easy to extend the result by Pinkus mentioned above to a network with more hidden layers?


texts:
I hope this is a suitable place to ask this question.

An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am interested in efficient algorithms to evaluate $x_n$ over $\mathbb N$.

Upper bounds

The obvious algorithm is to evaluate every $x_i$ as a binary number and store the results. This uses $\mathcal O(\sum \log x_i)$ time and space. Clearly, if $x_1 = 1$ then $x_i < 2^i$ so the time and space can be bounded by $\mathcal O(\sum i) = \mathcal O(n^2)$. There exist chains with $x_i = \Theta(2^i)$ e.g. $x_{i+1} = x_i + x_i$, so this bound is also tight.

There is an improvement that uses $\mathcal O(n)$ space: the idea is to calculate one bit of the result at a time, while using $\mathcal O(1)$ bits for each term to store the carry to the next bit. However, the running time is still quadratic.

Lower bounds

We can implement multiplication of $\frac n 4$-bit numbers using an addition chain of size $n$. This gives a non-trivial lower bound of $M(\frac n 4)$ which is $\Omega(n \log n)$ (based on the best known multiplication algorithms).

A better bound via matrix multiplication: use a size-$\frac n 3$ chain to encode rows of a square matrix over $GF(2)$ with side length $\mathcal O(n^{1/2}/\log n)$, where the $\log n$ is spent on padding each entry with some zeroes to avoid overflow. We add another size-$\frac n 3$ chain to express linear combinations of these rows, and a final $\frac n 3$ chain to construct a single integer $x_n$ that contains all bits of the result. This implies a lower bound of $n^{\omega/2 - \epsilon}$ where $\omega$ is the difficulty of matrix multiplication (currently about $2.37$).

I am wondering if there is a better lower or upper bound for evaluating $x_n$.

This problem comes up in data structures that compress a very large tree into a DAG. Calculating the size of the underlying tree is equivalent to evaluating an addition chain over the graph.


texts: How does the BosonSampling paper avoid easy classes of complex matrices?

texts:
In The computational complexity of linear optics (ECCC TR10-170), Scott Aaronson and Alex Arkhipov argue that if quantum computers can be efficiently simulated by classical computers then the polynomial hierarchy collapses to the third level.  The motivating problem is sampling from a distribution defined by a linear-optical network; this distribution can be expressed as the permanent of a particular matrix.  In the classical case all entries of the matrix are non-negative, and so a probabilistic polynomial-time algorithm exists, as shown by Mark Jerrum, Alistair Sinclair, and Eric Vigoda (JACM 2004, doi: 10.1145/1008731.1008738).  In the quantum case the entries are complex numbers.  Note that in the general case (when the entries are not required to be non-negative) the permanent cannot be approximated even within a constant factor, by Valiant's classic 1979 result.

The paper defines a distribution $D_A$ defined by a matrix $A$, and a sampling problem

  BosonSampling
  Input: matrix $A$
  Sample: from distribution $D_A$

Using a hardness result seems to be weak evidence for a separation between the classical and quantum worlds, since it is possible that the class of matrices in the specific quantum setup will all be of special form.  They might have complex entries, but may still possess a lot of structure.  There could therefore exist an efficient sampling procedure for such matrices, even though the general problem is #P-hard.

  How does the use of BosonSampling in the paper avoid easy classes?

The paper uses a lot of background I don't have in quantum complexity.  Given all the quantum people on this site, I'd really appreciate a pointer in the right direction.  How would the arguments hold up if one were to discover that the class of complex-valued matrices seen in a specific experimental setup actually corresponded to a class of distributions that was easy to sample from?  Or is there something inherent in the quantum system that guarantees this cannot happen?


texts:
The PCP theorem can be stated like this :

There is a polynomial time reduction from SAT to  $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $\psi$ of  $Gap\text-MAX\text-3SAT_{c}$ such that

If $\phi$ is satisfiable, so is $\psi$.
If $\phi$ is unsatisfiable, then $OPT(\psi) \leq c$, i.e., there is no assignment to the variables of $\psi$ that satisfies more than a fraction $c$ of the  clauses.

What is the blow-up of this reduction? That is, what are the parameters of the instanceof  $Gap\text-MAX\text-3SAT_{c}$ in terms of parameter of the given instance of SAT. Is the blow-up linear?


texts: Why is 2-connectedness characterized by the existence of an ear decomposition ?

texts:
Reading the book "Introduction to Graph Theory" (West, 2nd ed.) I have come across the following definition and statement:

Why is this statement true ?

Suppose I have a graph $G$ that consist of a cycle $C$ and a path $P$ that share no vertices. Then $G$ has an ear decomposition ? Well, I can decompose $G$ into $P_o = C$ and $P_1 = P$ ? $P_o$ is a cycle and $P$ is an ear of $P_0 \cup P_1$ - $P$ is a maximal path whose interval vertices have degree $2$ in $G$ ? But $G$ is not connected and therefore is $0$-connected and not $2$-connected ?


texts: complexity of deciding whether there's a small polynomial with a given root

texts: Let $f\in (\mathbb{Z}/p\mathbb{Z})^\ast$ be a nonzero element of a prime finite field.  For $d, r\in \mathbb{N}$ consider the problem of deciding whether there is a nonzero polynomial $$P(x) = a_0 +a_1x+a_2x^2+...+~a_dx^d \in \mathbb{Z}[x]$$ of degree not exceeding $d$, and also $|a_i|\leq r$ for all $i$, and also such that $\overline{P}(x)\in (\mathbb{Z}/p\mathbb{Z})[x]$ has $f$ as a root.  (So this is a decision problem depending on $f, p, d, r $).   Is there anything known about the general time complexity of this problem?


texts: Are patents good sources for academic research?

texts:
I'm a freshman Master's student in Computer Science and I need to write a paper for my Operating System class. While looking through research articles using google scholar I found that a lot results lead me to patents. I was wondering if patents are good sources for writing an academic paper or if I should steer clear from them?

My goal is to be able to summarize various papers from a specific topic related to operating systems. Also if possible (but not mandatory) to provide some kind of solution. Any advice would be greatly appreciated since this would be my first time writing a technical paper.


texts:
Can we consider a Haskell class as a loose signature-only-specification (denoting a theory) and an instance as an implementation (denoting a model)? In the example below the specification of the class $\mathcal{BUILDING}$ is textually smaller than the specification of the class $\mathcal{HOUSE}$, though in Haskell  $\mathcal{BUILDING}$ is a super class of  $\mathcal{HOUSE}$. Is there a Galois correspondence between a Haskell class hierarchy and  its instance hierarchy?

 --General Idea--

$\small\mathcal{Theory}\subseteq\mathcal{Theory'}\iff\mathcal{Model'}\subseteq\mathcal{Model}$

 --A specific  example with Haskell class-to-instance relation --
1

$\small\mathcal{class(BUILDING)}\subseteq_{C}\mathcal{class(HOUSE)}\iff\mathcal{instance(HOUSE)}\subseteq_{I}\mathcal{instance(BUILDING)}$

 ----------------

data House = House deriving Show
data Building = Building  deriving Show

class BUILDING building where
 -- specify the behavior of buildings here, if any
 supportRoof :: building -> String

class BUILDING house => HOUSE house where
 -- specify additional behavior of houses here, if any
  live::house -> Bool

instance BUILDING Building where
-- specify how the type Building implements the behavior of type class BUILDING
  supportRoof b = "BUILDING.Building"
-- A particular b which is a BUILDING.Building.particular can support a roof

instance BUILDING House where
  supportRoof h = "BUILDING.House"
-- A particular h which is a BUILDING.House.particular can support a roof

instance HOUSE House where
-- specify how the type House implements the behaviour of type class HOUSE
   live h   = if ((supportRoof h) == "BUILDING.House") then True else False
-- An particular h HOUSE.House.particular can support a roof in exactly the same way as BUILDING.House.particular can.

instance HOUSE Building where
-- specify how the type Building implements the behaviour of type class HOUSE
   live b   = if ((supportRoof b) == "BUILDING.Building") then True else False
-- An particular b HOUSE.Building.particular  can support a roof in exactly the same way as BUILDING.Building.particular can.


texts: Are two-qubit unitaries necessary for universal quantum computation?

texts:
I was going through Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said,

  Two-qubit unitaries $U_t$ are necessary for universal quantum
  computation

I understand that there are universal sets of two-qubit quantum gates but does it imply that the set must always consist of two-bit gates?


texts: Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover

texts:
This problem came up in my study of digraphs:
Given a connected bipartite graph $G = (A \cup B, E)$, a vertex cover is a set $S$ of vertices such that every edge has some endpoint in $S$.
Note that $A$ and $B$ are vertex covers. A non-trivial vertex cover is a vertex cover which does not contain $A$ and does not contain $B$.
A set $F \subseteq E$ of edges intersects a vertex cover $S$ if the set $E[S] \cap F$ is not empty. That is, if there is an edge $e=(u,v) \in F$ such that both $u$ and $v$ are in $S$.
I decided to call a set of edges which intersect all non-trivial vertex covers, a VC cover.
Is there a polynomial time algorithm to find a minimum cardinality VC cover?


texts: Is the following restriction of cellular automata / tile assembly / CRN a known model?

texts:
Consider the following model: we work in the $d$-dimensional grid $\mathbb{N}^d$, and we have an alphabet $\Sigma$.
The initial cell $(0,\ldots,0)\in \mathbb{N}^d$ is marked with some letter $\Sigma$, and from that we mark each cell with a letter from $\Sigma$ according to its immediate predecessors. That is, we have a function $f:\Sigma^d\to \Sigma$, and for each cell $(a_1,\ldots,a_d)$, we mark it with
$f(\sigma_1,\ldots,\sigma_d)$, where $\sigma_i$ is the labeling of the neighbor $(a_1,\ldots,a_i-1,\ldots, a_d)$.
This means that the marking is completely determined by $f$ and the initial symbol.
Note that at the edges, where there are fewer then $d$ neighbors, we ignore the missing values (technically, we can assume that anything outside $\mathbb{N}^d$ has some constant fixed marking).
I want to study certain properties of this model (specifically, I want to show that it is semilinear, in a sense). But I couldn't find any resources on it.
Specifically, I would like to know if this model is Presburger-definable.
However, it is a very natural restriction of several models:

Cellular automata: it can be thought of a single-state cellular automaton, that can only change the value of a cell once (i.e., a cellular transducer).
Tile Self-assembly: where the glue relations allow only a deterministic assembly, but the model is not two-dimensional.
Multidimensional subshifts: it's not really a shift, but it does have the same flavour of finite rules.
Chemical-reaction networks: I'm actually not sure if this is a restriction, but it seems somewhat related.

I'd appreciate any leads on this.


texts:
We know NP$\subseteq$ $\exists \mathbb R$$\subseteq$ PSPACE=IP, but is there some more direct proof for $\exists \mathbb R\subseteq$ IP?

What about the other direction, are there some Arthur-Merlin games that are in $\exists \mathbb R$?


texts: How do I describe this (graph-)problem for a research paper?

texts:
I have a function f(x, y) which takes two integers and returns a scalar.

My task is to find the set of (x, y) pairs, 0<x<W, 0<y<H where f(x, y)>0, which maximize the sum f(x_i, y_i) with the constraint that no two pairs shall overlap.
Two pairs (x1, y1) and (x2, y2) overlap if (x2 >= x1 and x2 < x1+y1).

I have implemented a practical solution which processes in O(WxH) time with O(W) memory. I'm pretty sure this is optimal. It seems to me that it is a kind of a graph flow algorithm, but I don't know how to formally describe it without pseudo code.

Can anybody tell me what class of problems this problem belongs to?

I attach a screenshot of a solution to one configuration (darker means higher f(x, y)).


texts: Why have we not been able to develop a unified complexity theory of distributed computing?

texts:
The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed computation that are simply not compatible with each other. The sheer explosion of varying temporal properties (asynchrony, synchrony, partial synchrony), various communication primitives (message passing vs. shared memory, broadcast vs. unicast), multiple fault models (fail stop, crash recover, send omission, byzantine, and so on) has left us with an intractable number of system models, frameworks, and methodologies, that comparing relative solvability results and lower bounds across these models and frameworks has become arduous, intractable, and at times, impossible.

My question is very simply, why is that so? What is so fundamentally different about distributed computing (from its sequential counterpart) that we haven't been able to collate the research into a unified theory of distributed computing? With sequential computing, Turing Machines, Recursive Functions, and Lambda Calculus all truned out to be equivalent. Was this just a stroke of luck, or did we really do a good job in encapsulating sequential computing in a manner that is yet to be accomplished with distributed computing?

In other words, is distributed computing inherently unyielding to an elegant theory (and if so, how and why?), or are we simply not smart enough to discover such a theory?

The only reference I could find that addresses this issue is: "Appraising two decades of distributed computing theory research" by Fischer and Merritt DOI: 10.1007/s00446-003-0096-6

Any references or expositions would be really helpful.


texts: What specific evidence is there for P = RP?

texts:
RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error.  P is the usual class of problems decidable by a deterministic Turing machine that terminates in polynomial time.

P = RP follows from a relationship in circuit complexity.  Impagliazzo and Wigderson showed that P = BPP follows if some problem that can be decided in deterministic exponential time also requires exponential size circuits (note that P = BPP implies P = RP).  Perhaps due to these results, there seems to be a feeling among some complexity theorists that probabilistic reductions can probably be derandomized.

  What other specific evidence is there that P = RP?


texts: New Space Lower-Bound Techniques for Streaming Algorithms

texts:
Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if conditional lower bounds?

In general, are we satisfied with the progress achieved via CC? Or seeking alternative techniques (even if conditional) would be an interesting direction?


texts: Effect handlers, arrows and applicatives

texts:
After reading Lindley's paper on effect handlers for arrows and applicatives, I got the gist about dynamic and static flow and that it was added to the effect system and so on. However, I do not understand two things about this paper:

Why does it need that G unary operator? I kind of understand that you have to have another type to represent the function as an arrow, and that's how it was solved. I do not understand why is G needed for applicatives.
Why it requires a lambda expression receiving a z of type B for both arrow and applicative handling? Does it mean that everything that's static gets dumped into scope?

I've read previous papers by Lindley on effect handlers, and I am familiar with arrows and applicatives in Haskell.


texts: Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P?

texts:
I have been facinated by the extraordinary explosion in Smoothed Analysis and was struck by a assertion in the paper Smoothed Analysis of Integer Programming. This stated that Integer Linear Programming is in Smoothed P if Polynomially Bounded. This was essential true by the virtue that Integer Programming is Pseudo-polynomial!

The question therefore is:

  Does this carry over to other problems universally? In particular what are the constraints?


texts: Are there local maxima in the number of moves required to solve a Rubik's Cube?

texts: Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP. As Peter pointed out, my approach fails in some instances. One potential case of such an instance is where there exists a local maxima in the path length. By this I mean that it may take $S_A$ moves to solve the cube from configuration $A$, and either $S_A$ or $S_A - 1$ moves to solve the cube from any position which can be reached in one move from $A$. Now, this isn't necessarily such a problem if $S_A$ is maximum number of moves required to solve the cube in general (God's Number for that cube), but is definitely a problem if $S_A$ is strictly less than God's Number for that cube. So my question is do such local maxima exist? Even an answer for the $3 \times 3 \times 3$ cube would be of interest to me.


texts: The unreasonable power of non-uniformity

texts:
From the common sense point of view, it is easy to believe that adding non-determinism to $\mathsf{P}$ significantly extends its power, i.e., $\mathsf{NP}$ is much larger than  $\mathsf{P}$. After all, non-determinism allows exponential parallelism, which undoubtedly appears very powerful.

On the other hand, if we just add non-uniformity to $\mathsf{P}$, obtaining  $\mathsf{P}/poly$, then the intuition  is less clear (assuming we exclude non-recursive languages that could occur in $\mathsf{P}/poly$). One could expect that merely allowing different polynomial time algorithms for different input lengths (but not leaving the recursive realm) is a less powerful extension than the exponential parallelism in non-determinism.

Interestingly, however, if we compare these classes with the very large class $\mathsf{NEXP}$, then we see the following counter-intuitive situation. We know that $\mathsf{NEXP}$ properly contains $\mathsf{NP}$, which is not surprising. (After all, $\mathsf{NEXP}$ allows doubly exponential parallelism.) On the other hand, currently we cannot rule out $\mathsf{NEXP}\subseteq \mathsf{P}/poly$.

Thus, in this sense, non-uniformity, when added to polynomial time,  possibly makes it extremely powerful, potentially more powerful than non-determinism. It might even go as far as to simulate doubly exponential parallelism! Even though we believe this is not the case, but the fact that currently it  cannot be ruled it out still suggests that complexity theorists  are struggling with "mighty powers" here.

  How would you explain to an intelligent layman what is behind this  "unreasonable power" of non-uniformity?


texts: Partitioning a rectangle without harming inner rectangles

texts:
$C$ is an axis-parallel rectangle.

$C_1,\dots,C_n$ are pairwise-interior-disjoint axis-parallel rectangles such that $C_1\cup\dots\cup C_n \subsetneq C$, like this:

A rectangle-preserving partition of $C$ is a partition $C = E_1\cup\dots\cup E_N$, such that $N\geq n$, the $E_i$ are pairwise-interior-disjoint axis-parallel rectangles, and for every $i=1,\dots,n$: $C_i \subseteq E_i$, i.e, each existing rectangle is contained in a unique new rectangle, like this:

What is an algorithm for finding a rectangle-preserving partition with a small $N$?

In particular, is there an algorithm for finding a rectangle-preserving partition with $N=O(n)$ parts?


texts:
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.

It is also suspected (somewhat less widely) that even deciding SAT should take time $2^{n−o(n)}$ according to the strong exponential time hypothesis.

I was wondering if there are any hardness results for APPROXIMATE-#SAT, namely counting the number of satisfying assignments up to additive errors? In particular, are there any explicit lower bounds?  What if we only want to approximate up to an error of $\sqrt{2^n}$?

Thanks!


texts: Complexity of variant polynomial factorization

texts:
Few years back a question on whether a variant of integer factorization was $\mathsf{NP}$ complete was asked, which according to state of mathematics today does not have a conclusive answer.

Is following variant of polynomial factorization, 'given $p(x)\in\Bbb Z[x], l,u\in\Bbb N$, is there a $q(x)\in\Bbb Z[x]$ with $l\leq\mathsf{deg}(q(x))\leq u$ such that $q(x)|p(x)$', $\mathsf{NP}$ complete?


texts:
Does anyone know if the verified software repository is still alive?  Bar that, are there other repositories out there of verified (or just certified) software?  The archive of formal proofs is nice, but not quite 'right'.

Finding singular examples of verified software is possible (with seL4 and CompCert being obvious examples), but finding whole groups of them is hard.  I would have expected to be able to find whole repositories of certified software components by now, but I have been unable to do so.

[While not TCS per se, the amount of underlying TCS issues involved in software verification/certification is enormous, so hopefully this will be considered to be on topic]


texts: Convergence of online convex optimization methods

texts:
I am new to this subject so this question might seem a bit trivial

Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for example Online gradient descent guarantees a sub-linear regret
(Assuming that our loss functions are convex). However does it guarantees a convergence  $x_t \rightarrow x_*$ where  $x_*$ is the best choice in hindsight? and in which rate?

If the answer is yes I will be greatful if you will provide me some reference

Thanks


texts:
A discrete-time Markov chain (DTMC) is a tuple $M=(S,s_{init},P)$ where $S$ is a finite set of states, $s_{init}\in S$ the initial state, and $P:S\times S\to[0,1]$ the one-step transition probability matrix.

For a subset $S'\subseteq S$ with $s_{init},t\in S'$ we define the induced sub-DTMC $M_{S'}=(S',s_{init},P')$ with $P'(s,s')=P(s,s')$ for all $s,s'\in S'$.
If the sum of the out-going probabilities of a state $s\in S'$ is less than 1, a deadlock state is entered with probability $1-\sum_{s'\in S'}P(s,s')$ such that $t$ cannot be reached anymore.

Assume we are given a DTMC $M=(S,s_{init},P)$ and a target state $t\in S$ such that the probability to finally reach $t$ from $s_{init}$ is larger than a given bound $\lambda$. We are interested in subsets $S'\subseteq S$ with $s_{init},t\in S'$ such that the probability of reaching $t$ from $s_{init}$ in $M_{S'}$ is still larger than $\lambda$.

Question: What is the complexity of deciding whether there is such a $S'$ containing at most $k$ states (for a given $k$)?

We suppose that this problem is NP-complete (obviously it is in NP: guess an appropriate $S'$ and compute the reachability probabilities to check if the bound $\lambda$ is exceeded; this can be done by solving a linear equation system). However, we have not found a reduction to show the NP-hardness. Maybe someone can help ...

For Markov decision processes, which feature non-deterministic choices in addition to the probabilistic choices of DTMCs, the same problem has been proven to be NP-complete, see

Chadha, Viswanathan - A counterexample-guided abstraction-refinement framework for Markov decision processes, ACM Trans. Comput. Log. 12(1), 2010
http://dl.acm.org/citation.cfm?doid=1838552.1838553

The same holds also for DTMCs and PCTL properties, if nested formulae are allowed. However, for pure reachability I was not able to find a proof for NP-hardness.


texts: Are there any NP-complete for continuous mathematics?

texts: Looking at this wiki page, it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete analysis? If none, why not?


texts: Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

texts:
Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science.  The best examples are those where the connection was not obvious, but once it was discovered, it is clearly the "right way" to do it.

This is the opposite direction of the question Applications of TCS to classical mathematics?

For example, see "Green's Theorem and Isolation in Planar Graphs", where an isolation theorem (which was already known using a technical proof) is re-proven using Green's Theorem from multivariate calculus.

What other examples are there?


texts: Is there any quantum analog of the VP vs. VNP problem?

texts:
From Wikipedia:

$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$  of polynomial degree that have polynomial size circuits over a fixed field $K$.
$\mathsf{VNP}$: The class VNP is the analog of NP. VNP can be thought of as the class of polynomials $f$ of polynomial degree such that given a monomial we can determine its coefficient in $f$ efficiently, with a polynomial-size circuit.

There have been attempts to implement polynomials $f$ using quantum circuits, cf. arXiv:1805.12445. So does there exist any quantum analog of the $\mathsf{VP}$ vs. $\mathsf{VNP}$ problem? Is there any paper on this topic?
P.S: I've asked a very related question on the Quantum Computing site.


texts: Hilbert's Tenth Problem and nonrecursive Diophantine sets

texts:
In her paper Defining Integers, Alexandra Shlapentokh presents the following as an immediate corollary of the undecidability of Hilbert's Tenth Problem --- that is, the language $\{p : p$ is a polynomial with integer coefficients with at least an integer root $\}$:

Corollary 1.5. There are undecidable Diophantine subsets of $\mathbb{Z}$

I'm not sure this is a consequence of the undecidability of HTP, so maybe I misread, and what the author is saying is that this is a consequence of the correspondence between recognizable sets and Diophantine sets.

Question: Is Corollary 1.5 a direct consequence of the undecidability of HTP?

Question (rephrased): Suppose every Diophantine set is decidable; does this imply that HTP is decidable?


texts: Brackets expression incremental parsing algorithm

texts:
I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets.

Consider the example with expression like "((1)())(2)". Parse tree for that expression is:

((1)())(2)
    ((1)())
        (1)
            1
        ()
    (2)
        2

Lets assume we inject additional symbols ")(" in the middle of the expression: "((1)()())(2)". My question is how to apply changes in the parse tree without reparsing of the whole input?


texts:
If a circuit ({AND OR NOT} circuit) with depth d computes the majority function, what's the best lower bound for majority function?
I know the lower bound for parity function is $ 2^{\Omega (n^{1/d})} $


texts: Hardness of finding similar (quantum) states

texts:
Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce a qubit with reduced density matrix of $\rho$, where $\langle \psi \vert \rho \vert \psi \rangle = 5/6$. (for references see Robin Kothari's answer)

Suppose we call any two states $\lvert \psi \rangle$ and $\lvert \phi \rangle$ Similar, if $\langle \psi \vert \phi \rangle \langle \phi \vert \psi \rangle > 5/6 + \epsilon$, where $\epsilon$ is some small fraction

So, given a state $\lvert \psi \rangle$, is finding another 'Similar' state computationally hard, or information theoretically?


texts: Citation request: Complexity of determining if a graph exists with a minor but no subgraph in set

texts:
I'm looking for a reference of the complexity of the following problem.

Let our input $C$ be a finite set of graphs. Is there a graph $G$ such that:

$G$ has a minor in $C$
$G$ has no subgraph in $C$?

As per Robin's suggestion, here's why I believe it's $NP$-hard and within $NP^{NP}$. This is just written out informally, I can formalize if it'd help.

co-NP Hardness

Let $G = (V, E)$ be an arbitrary graph with internal and external edges, an even number of vertices, and maximum degree 3. Such graphs in general are still $NP$-hard for Hamiltonian Path.

First, create a subvidided claw $H$ by attaching 3 paths of lengths $|V|/2$, $|V|/2$ and $|V|$ to a central vertex. Next, make $|E|$ copies of $G$, labelled $G_1, ..., G_{|E|}$. For each $G_i$, subdivide edge $i$ once, and to this new intermediate vertex, attach a dangling path $P_i$ of length $|V|$. Finally, attach one new vertex to the second-to-last vertex in this path, so that the addition consisted of 2 external and $|V|-1$ internal edges. Finally, let $G'$ be the disjoint union of all $G_i$.

Now, we can define $C$ as $\{G', H\}$.

Suppose that $G$ has a Hamiltonian Path. Then $H$ is a subgraph of some $G_i$, as the long arm fits into some $P_i$, the central vertex on the vertex added thru subdivision, and the other two arms make the path.

Suppoes that $H$ is a subgraph of $G'$. Well, $H$ is a simple component, and a little simple math shows that $G$ must have a Hamiltonian path.

OK, now we have that $H$ is a minor and subgraph of $G'$ iff $G$ has a Hamiltonian path. So consider the graph $G''$ obtained by subdividing an edge on $P_1$ a bunch of times. As this edge is internal, $G'$ is not a subgraph of $G''$. And $H$ is a subgraph of $G''$ iff $G$ has a Hamiltonian path.

NP to the NP

From my comment, why $G$ won't be too big: Let's consider the smallest such $G$. Let $x$ be number of edges in graph of $C$ with most edges. No graph in C can consume all of a path of length $x+1$. As $G$ has as a minor some $H \in C$, we can look at the model of $H$ in $G$. Clearly, no reason to simply add edges or vertices to $H$. So we can get from $G$ to $H$ with just contraction. No path needs to be contracted more than $x+1$ times or we could have shortened it. This gives a reasonable size bound.

For $NP^{NP}$: given a graph $G$ with a minor in $C$, we need to ensure that for each graph $H$ in $C$, $H$ is not a subgraph $G$. One can imagine a TM which has a computation path for every each graph and way to split its vertices, which then queries an $NP$ oracle for each graph in $C$ to see if it's not a subgraph.

Any citations out there?

I'm also interested in a version where either all graphs of $C$ are subcubic or condition 1 is for topological minors instead of normal ones.


texts: Characterization of read-once formulae over the full binary basis

texts:
Background

A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (which has the 2-bit gates AND and OR, and the 1-bit gate NOT) and the full binary basis (which has all 2-bit gates).

So for example, the AND of 2 bits can be written as a read-once formula over either basis, but the parity of 2 bits cannot be written as a read-once formula over the De Morgan basis.

The set of all functions that can be written as a read-once formula over the De Morgan basis has a combinatorial characterization. See, for example, Combinatorial characterization of read-once formulae by M. Karchmer , N. Linial , I. Newman , M. Saks , A. Wigderson.

Question

Is there an alternate characterization of the set of functions that can be computed by a read-once formula over the full binary basis?

Easier Question (added in v2)

While I'm still interested in an answer to the original question, since I haven't received any answers I thought I'll ask an easier question: What are some lower bound techniques that work for formulae over the full binary basis? (Other than the ones I list below.)

Note that now I'm trying to lower bound the formula size (= number of leaves). For read-once formulae, we have formula size = number of inputs. So if you can prove that a function needs a formula of size strictly greater than n, then that also means it cannot be represented as a read-once formula.

I'm aware of the following techniques (along with a reference for each technique from Boolean Function Complexity: Advances and Frontiers by Stasys Jukna):

Nechiporuk's method for universal functions (Sec 6.2): Shows an $n^{2-o(1)}$ size lower bound for a certain function. This doesn't help you find lower bounds for a particular function that you might be interested in though.
Nechiporuk's theorem using subfunctions (Sec 6.5): This is a proper lower bound technique in the sense that it will provide a lower bound for any function you're interested in. For example it shows that any formula over the full binary basis that represents the element distinctness function has size $\Omega(n^2/\log n)$. (And this is the largest lower bound the technique can prove — for any function.)


texts:
Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement.  More conferences and workshops are videotaping their talks.  What are videos online that you think everyone should know about?

I'll seed this with a few answers to presentations that are mostly expository, but what I'm hoping might happen is that this community wiki could turn into a resource to share excellent presentations of new research, as well as a place to learn (or reinforce) background in an unfamiliar area.


texts:
Consider the following problem:

SUBSET-SUM-DIFFERENCE: Let $S=\{s_1,\dots,s_n\}$ be a set of $n$ integers and $t$ be a "target" integer. Are there two disjoint subsets of $S$ (call them subsets $I$ and $J$) such that $\sum_{i \in I}s_i - \sum_{j \in J} s_j=t$.

The Meet-in-the-Middle algorithm will solve this problem in $\Theta(3^{n/2})$ time. Is there an exact and deterministic algorithm which solves this problem in $o(3^{n/2})$ time?


texts: Typo in the calculus of constructions paper?

texts:
In the classic the calculus of constructions paper there is a rule that states

(page 7 of the pdf, page 101 of the original document)

This rule would mean that any context is reducible to a member of that context.  This seems like it shouldn't be correct, as it would entail

1 ≅ Nat
3 ≅ Nat
1 ≅ 3

if Nat is a context.

I think the best interpretation is that the lower delta was meant to be an M.  Especially considering the rules given on the next page.

So is this simply a typo, or some subtle logical rule that I don't understand?


texts: How many sets of vectors can be represented as the solutions of a Horn-SAT instance?

texts:
Let the solution space of a SAT instance be the set of Boolean vectors of satisfying assignments of $\{0,1\}$ to the variables (that result in the formula evaluating to TRUE).
In other words, a solution space represents all the solutions of an instance.
There are at most $2^n$ solutions, so $n$-variable SAT (denoted here by SAT$_n$) can represent at most $2^{2^n}$ different solution spaces.
Moreover, it is easy to see that this number can actually be reached, by considering instances where every clause contains all $n$ variables.

We know that Horn-SAT is less expressive than SAT, for instance there is no Horn-SAT$_2$ representation of the solution space of $a \lor b$, which contains the 3 vectors $01, 10, 11$.
Hence Horn-SAT$_n$ must be able to represent fewer than $2^{2^n}$ solution spaces.

  What is the number of solution spaces of a Horn-SAT$_n$ instance?

For completeness, recall that a literal is either a variable or its negation,
and that $n$-variable SAT consists of formulas built from at most $n$ variables (we can fix the set of variable names, e.g. $\{1,2,\dots,n\}$), in conjunctive normal form (a conjunction of disjunctions), where each disjunction of literals is known as a clause.
Horn-SAT$_n$ is the fragment of $n$-variable SAT where each clause in an input formula contains at most one non-negated variable.

An equivalent counting formulation of the question is: how many different values can #Horn-SAT$_n$ have?
However, note that I am not interested here in the complexity of #Horn-SAT, just its range of values for each number of variables.

If one tries to work syntactically, then one faces the same challenge as for SAT.
Suppose one tries to count the number of different SAT instances syntactically.
There are $2^{3^n}$ different ways to write down a SAT instance with $n$ variables and no repeated clauses (if the variable order is fixed and no variable may appear more than once in a clause), so one has to find the equivalence classes of syntactically different instances that lead to the same solution space, to retrieve the $2^{2^n}$ number.
One then needs to similarly take the quotient of the set of different Horn-SAT instances with $n$ variables to obtain the correct value of the number of different solution spaces.
It is not clear to me how to take quotients for SAT, let alone how to do so for Horn-SAT.


texts: Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$

texts: It is known that some (non-relativized) syntactic complexity classes between ${\bf P}$ and ${\bf PSPACE}$ have the following property, ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P} \subseteq {\bf PP} \subseteq {\bf PSPACE}$. I am wondering if there exists a (non-relativized) syntactic complexity class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$? What are the implications of existence or non-existence of complexity class ${\bf X}$ ?


texts: Mathematical analysis and computational complexity?

texts:
computational complexity involves large amounts of Combinatorics and number theory, some ingridiences from stochastics, and an emerging amount of algebra.

However, being a analysist, I wonder whether there are applications of analysis into this field, or maybe ideas inspired by analysis. All I know which slightly corresponds to this is the Fourier transform on Finite groups.

Can you help me?


texts: Automated theorem proving in linear logic

texts:
Is automatic theorem proving and proof searching easier in linear and other propositional substructural logics which lack contraction?

Where can I read more about automatic theorem proving in these logics and the role of contraction in proof search?


texts: What is the use of the multi-project scheduling problem compared to single-project?

texts:
I am doing some research regarding (resource-constrained) scheduling, and in several papers I find multi-project scheduling problems. What is so special about multi-project scheduling problems compared to single-project scheduling problems?

This is what I understand the problems to be:

The single-project scheduling problem consists of a set of tasks with temporal relationships between those tasks (defining lower and/or upper bounds between start or end times of tasks), and a set of resources. Tasks require resources during execution, which are released when execution is finished.
Depending on the problem that is being solved, different properties are optimized (for example makespan or tardiness).

The multi-project scheduling problem consists of several such projects, which can have different release dates or deadlines.

My intuition is that the multi-project scheduling problem can be very easily reduced to the single-project scheduling problem by combining the tasks and temporal constraints and adding some dummy tasks and constraints to create a single release time and deadline for the whole instance.

There are two reasons why this bothers me:

If there is no actual difference between the two problems, why bother with having distinct problems?
Having multiple projects requires extra indices (for example $e_{ijmM}$ instead of $e_{imM}$, or a[i][j][m][M] instead of a[i][m][M] in code). This makes it harder to work with and increases the probability of errors, both in notation and in code.

Therefore my question is: is there a use for the distinction between single- and multi-project scheduling?


texts: Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?

texts:
(As for the question in the title: the answer must be no, but then I don't understand what is intended.)

The Wikipedia page on one way functions states:

  Goldreich gives one construction of a universal one-way function, which is denoted by $f_{univ}$ here.

  $f_{univ} (desc(M), x) := (desc(M), M(x))$,
  where $desc(M)$ is the description of Turing machine $M$, and $x$ is an input string. $M(x)$ is defined as the output of machine $M$ given $x$ as input if the running time is at most quadratic on the length of $x$, and otherwise, $M(x) := x$. This definition of $M(x)$ guarantees $f_{univ}$ can be efficiently computed within polynomial time.

The point of $f_{univ}$ is that whenever there exists one way functions that run in quadratic time, then $f_{univ}$ is a one-way function as well. (And the Goldreich reference proves that whenever one-way functions of any running time exist, they can be used to create one way functions that run in quadratic time, hence obtaining the result that the 'concrete' function $f_{univ}$ is a one way function if and only if one way functions exist at all.)

I am, however, not convinced that the last statement from the quote is obvious.

As I understand it, a computer wanting to compute $M(x)$ needs to do two things:

1) Decide whether or not the running time of machine $M$ given $x$ as input is "at most quadratic on the length of $x$"

2) Either return $x$ or let $M$ run on input $x$ and return the output

Now it is clear that step 2) takes at most quadratic time in the length of $x$ and hence certainly in the length of the total input of $f_{univ}$. What is not clear is that step 1) can be carried out in polynomial time.

To be clear: I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$. I can also think up an algorithm that test in polynomial time (even time $1000|x|^2$) whether or not $M$ runs for at most $1000|x|^2$ steps. Etc etc etc. However the term 'quadratic' gives us no information on how big or small the implied constant is.

It seems that whenever I make the definition of $f_{univ}$ concrete as in the example above (so output the output of $M$ on $x$ whenever it can be computed in less than $1000 |x|^2$ steps and otherwise output $x$), there might be a world imaginable where quadratic time one way functions exist but all of them take time longer than 1000 times their input length squared and $f_{univ}$ is not one way at all. The only way I can think of to avoid this is for the computer to somehow decide if $M$ halts on $x$ at all but that is known to be a hard problem.

What am I missing?

UPDATE: I see another way out of this: when the proof that any one-way function $f$ can be transformed into a one way function $g$ that runs in quadratic time does in fact give that $g$ runs in time $< cn^2$ for a very concrete $c$. However here it is crucially important that $c$ does not depend on the unkonwn function $f$. This is not clear from me from the Goldreich notes Wikipedia links to. (The proof is in section 2.4.2.) Any help clarifying this is appreciated!