texts: Connected Components over Graph with "colored" edges.

texts:
We have an undirected graph $G(V,E)$. Each edge $e \in E$  is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. For example if we have $C=\{\;\mathrm{red},\;\mathrm{black},\;\mathrm{yellow}\}$. The Red connected components are all the connected components considering only the edges that contains  red in the color set.
Now a naive algorithm is to do the normal search for each $c\in C$. The cost seems to be $O(|C|(|V|+|E|))$. The question is: is it possible to do better?


texts: Terminology: FNP, with P replaced by NP?

texts:
Consider these two classes of search problems:

Search problems with poly-sized solutions s.t. verifying solutions is in P.
Search problems with poly-sized solutions s.t. verifying solutions is in NP.

Class 1 is FNP. Is there any commonly used name for class 2?

Examples of problems in these classes:

Given a graph with n nodes, find a proper 3-coloring.
Given a graph with n nodes, find a partial 3-coloring such that the first n/2 are colored and the partial coloring can be extended to a proper 3-coloring.

Note that these two problems are, in essence, equivalent, but the key point is that a solution to problem 2 requires a proof, while a solution to problem 1 is already a proof.


texts:
Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)?

For simplicity let's say the string is binary,
the obvious answer is exponential to input length.
But the question is can we do better?

(Sorry if I mixed up some notations,
been a while since my Theory of Computation class.)

I somehow feel like I can make something out of

Are runtime bounds in P decidable? (answer: no)

but can someone please give a hint?


texts: What is the axiomatic (set theory) context of the P vs NP and NP=EXPTIME conjectures?

texts:
When the conjecture $\mathbf{P} = \mathbf{NP}$ or $\mathbf{P} \neq \mathbf{NP}$ is set (e.g. by the Clay Mathematical Institute by S. Cook, see here) what mathematical axiomatic system is assumed?

In order to prove or disprove such statements, you need to assume some axioms. Which ones? Only the Peano (2nd order formal language) arithmetic? The Zermelo–Fraenkel set theory with the axiom of choice? Smaller axiomatic set theories (e.g. Gödel's constructible sets, where the continuum hypothesis holds too, see here)?

Obviously, it should be an axiomatic theory that accepts the countable infinite. But which in particular? Is there any published result that would prove them consistent in a particular axiomatic set theory? (In other words, defining a model in which it is true, but not claiming to be true in all models).


texts:
The set of languages recognized by POSIX regex is a true superset of type 3 languages. But how powerful is POSIX regex really? Is it in an already known class? Is it its own class? If so, what is the next bigger class (for some context)?

Proof that POSIX regex is more powerful than type 3:

(a+)b(\1) which recognizes $\{ a^nba^n | n \geq 1 \}$

I haven't found a really good description of what features POSIX regex allows but this is one link that lists all features (as far as I know): regex manual

Emil Jeřábek mentioned that POSIX regex is not even completely contained in type 2 languages because (.*)\1 is $\{ ww | w \in \Sigma^* \}$. So, it recognizes all type 3 languages, some type 2 languages and some type 1 languages, maybe even some type 0 languages.


texts: Will Martin-Löf Type Theory lead to a greater ability to write provably correct code?

texts:
This post refers to the Curry-Howard isomorphism and the Martin-Löf Type Theory.

The post makes the claim of a future 'unification' between the the describing language of math, and the operation based language of computer programming.

My questions are:

Will these ideas lead to a better ability (through languages) to write provably correct code?
Have the full implications of MLTT been discovered on a theoretical level?
Does this post describe anything could couldn't already do in COQ or Agda?


texts: Uses of quasi-PERs/difunctional relations/zig-zag relations?

texts:
Given sets $A$ and $B$, a difunctional relation $(\sim) \subseteq A \times B$ between them is defined to be a relation satisfying the following property:

  If $a \sim b$ and $a' \sim b'$ and $a \sim b'$, then $a' \sim b$.

Difunctional relations are a generalization of the concept of partial equivalence relations which permit one to define a notion of equality from different sets. As a result, they are also known as quasi-PERs (QPERs), and they are also known as zig-zag relations, due to the following picture:

I'm writing a paper that uses them, but I've had trouble tracking down good references for their use in semantics.

Martin Hoffman uses them in Correctness of Effect-Based Program Transformations.
I have seen mentions (but no good references) claiming that Tennant and Takeyama have proposed their use as well.

They are such a pretty idea that I have trouble believing my particular use of them is original. I would really appreciate any further references.


texts: Using Max-Flow (Ford Fulkerson) to find satisfying flow

texts:
i am trying to find a first allowed flow from vertex q to vertex s in a network N which has both minimum and maximum capacities.

1.) To solve the problem I started by creating a helper network NH by adding a new source and sink to the graph and subtracting max-capacities and min-capacities and setting min-capacities to zero on every edge.

2.) Additionally I added some new edges depending on the amount of flow into and out of a vertex (see below). This gives me a graph where I can apply the Max-Flow algorithm by Ford and Fulkerson. After doing so I get a satisfying flow through the network.

By applying 1 and 2 I get the network shown in the second image (from top).

3.) Now i applied the Ford/Fulkerson algorithm to find a max flow from q0 to s0 (the newly added source/sink) For this example I found only two paths to increase the network flow (  and  each with a flow of 1. NOTE: I used the method for Ford-Fulkerson using increment-networks

4.) By adding the min-capacities of the original network to the flow for each edge, I should now find a first flow through the original network.

However I do not come up with the (correct) solution provided at the bottom of the image (with different flow values for some edges). Applying Ford-Fulkerson simply does not generate a flow for those edges. Or am I missing something?

I think my problem is that I am not using the Infinity path created in NH (e.g. to move 3 units to q), however I do not see how I should come to use this path.

My network:

See http://s1.directupload.net/file/d/3179/36dvrm3u_jpg.htm

Note:

q - source of original problem

s = sink of original problem

q0 - source of helper graph NH to use Ford-Fulkerson

s0 - sink of helper graph NH to use Ford-Fulkerson

in the image on the top, the pairs mean min-capacity and max-capacity (e.g. 0|3 means min-cap 0 and max-cap 3) In the second image the numbers mean max-caps (Min-caps are all 0 so I ignored them). In the third and fourth image the numbers represent the resulting flow (which lies between min - and maxcap)

Thank you for any help!

P.S. I tried to translate the terminology from german, so please excuse me should I be using incorrect english terminology.

EDIT:

I see that my solution is correct by using the ford fulkerson algorithm, however  I don´t get a correct flow since the source q is not sending out any transport units in my solution. Should I just add the 3 necessary transport units from q to 3 to get a correct flow through the network?
Please help


texts: Identifying Reducible/Irreducible polynomials over $Z[x]$

texts:
It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$.

Say one only seeks to identify whether a given polynomial over $\mathbb{Z}[x]$ is reducible, then what are the best ways known to solve this? If reducible, the algorithm should correctly say yes and if not, it should say no.


texts: Is iszero of the untyped lambda calculus sound and complete?

texts:
I am using the following definitions in the notation of Haskell. In case it matters, I would like to use only the $\alpha,\beta,\eta$ reductions rather than the Haskell evaluation rules.

-- boolean constants
true = \x y -> x
false = \x y -> y

-- 0 and increment (successor)
zero = \f x -> x
inc n = \f x -> f (n f x)

-- IS THIS iszero SOUND AND COMPLETE?
iszero = \n -> n (\x -> false) true

It seems to me that iszero needs to check if two functions are identical. Since the equivalence of two arbitrary Turing Machines are undecidable, I am wondering if the it really works. In particular,

Soundness: are all functions for which iszero returns true really zero?
Completeness: for any arbitrary function $f$, can iszero correctly determine if $f$ is equal zero?


texts: Finite intersection property of polymorphic type families

texts:
Let $\Phi$ be a type functor definable in polymorphic lambda calculus:
$$ \alpha : * \vdash \Phi(\alpha) : * $$
$$ f : A \to B \vdash \mathsf{Map}^{A,B}_\Phi(f) : \Phi(A) \to \Phi(B)$$
Suppose further that $\Phi$-types form a filter:
$$ \vdash \cap^{A,B}_\Phi(x,y) : \Phi(A) \to \Phi(B) \to \Phi(A \land B) $$

Does there exist a type $\mu \Phi$ with the following properties:

$\qquad \vdash a : \Phi(A)\quad \Longrightarrow \quad \vdash \varphi_{A,a} : \mu \Phi \to A$
$\qquad \vdash \varphi_0 : \Phi(\mu \Phi)$

(Intuitively, the denotation of $\mu\Phi$ should be $\bigcap \{ [\![A]\!] \mid \Phi(A) \}$.)

If we put $\mu\Phi := \forall \alpha. (\Phi(\alpha) \to \alpha)$, then the first condition obtains via $\varphi_{A,a} = \lambda m. m A a$.

Is it always possible to satisfy the second condition too?  Or is there a counterexample?


texts: Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas

texts:
The k-FLIP SAT parametrized problem is defined as:

Input: a 3-CNF formula $\varphi$ with $n$ variables and a truth assignment $\sigma : [n] \to \{0,1\}$
Parameter: $k$
Question: can we transform the assignment $\sigma$ into a satifying assignment $\sigma'$ for $\varphi$ flipping the truth value of at most $k$ variables?

The problem is clearly in FPT (Stefan Szeider: The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Discrete Optimization 8(1): 139-145 (2011))

  Does it admit a polynomial kernel ? (under reasonable complexity assumptions)

The recent cross-composition techniques (see Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch, "Kernelization Lower Bounds By Cross-Composition") seem unuseful for this problem. And they also seem unuseful for similar problems that ask if a given solution to an NP-hard problem can be found from a given instance by local search (limiting the search to the neighbours of the given instance, under some natural distance measure).


texts: References on implementing universe levels over MLTT?

texts:
I've followed the tutorial on Checking Dependent Types with Normalization by Evaluation: A Tutorial by David Christiansen, where we implement a small dependently typed kernel with the axiom Univ : Univ. The "Projects" section of the tutorial provides a project on replacing this with a universe hieararchy:

7.Replace U with an infinite number of universes and a cumulativity relation. To do this, type equality checks should be replaced by a subsumption check, where each type constructor has variance rules similar to other systems with subtyping.

I've looked around a little, and it seems like both Agda and Lean implement a universe hierarchy using levels, which have the following operations:
lzero : Level
lsuc  : (n : Level) → Level
_⊔_   : (n m : Level) → Level

Who came up with this encoding of universes based on levels originally? Why not simply reuse the natural numbers for universe levels? There must be some reason to introduce a new Level type, instead of reusing the already present Nat?
How does one type-check and perform normalization-by-evaluation on universe levels?
What are the subtleties one should be aware of when implementing universes?
How should I test that my universe hierarchy implementation is correct? Are there short, well-known theorems that depend on a universe hierarchy, which I should try to encode?

I am hesitant to try my hand at naively implementing universes based on my intuition, because all the references I have read (ATAPL, MiniTT, and the above tutorial) all stop short of explaining universe levels. I get the feeling that there is non-triviality which I am unable to see, and thus would like to know how to (a) implement, and (b) test universes, on top of the kernel I now have


texts: Several papers appear to imply P=NP via chordal graphs, what is wrong?

texts:
Several papers appear to imply P=NP via chordal graphs,
which suggests something is wrong.

As usual $\gamma(G)$ is the domination number and $i(G)$ and $\gamma^i(G)$
are the independence domination number.

According to VIZING’S CONJECTURE FOR CHORDAL GRAPHS, p.1

  Theorem 1.1. [2] In chordal graphs $\gamma(G)=\gamma^i(G)=i(G)$.

According to graphclasses.org

and a paper p. 55 of the document and 65 of the pdf:

  In chordal graphs Domination is NP-complete and Independent Domination is
  polynomial.

The equality in Theorem 1.1 appears to imply P=NP since we can compute
$\gamma(G)=i(G)$ in chordal graphs by the above result.

  What is wrong with this?


texts: Complexity of finding minimal cover of FDs

texts:
Given a relational database and the problem is to generate some minimal cover (i.e. the minimal (by cardinality) set of functional dependencies that all other FD follows from them by Armstrong rules) in output polynomial time.

It's look like that this problem can not be solved in output polynomial time unless $P=NP$, but I couldn't find any papers about it.


texts: Is Redis with all its data types (Strings, Lists, Hashes, Sets, Sorted Sets, etc.) Turing Complete?


texts: Submodular function re-optimization (after an update)

texts:
The problem I have is as follows:
I know the minimizer/minimum of a non-negative submodular function, and want to use this to efficiently compute the minimizer/minimum of a "perturbed" submodular function.

E.g. Consider the special case of the submodular function being the cut-capacity function; i.e. We have a directed s-t graph $(V,E)$ with $n$ nodes and $m$ edges and the cut-capacity function is defined as $f(S)=\sum_{s\in S,t\in S^c} c(u,v)$ where $S\subseteq V$ and $c(u,v)$ denotes the capacity of the edge $(u,v)$. We find the s-t min-cut $A\subset V$. Now we add/delete an edge to the graph, which changes the cut-capacity function only slightly (i.e. the function value is unchanged for most of the arguments). Finding the new min-cut by utilizing the "warm start" $A$ can be done in time $O(m)$. This is more efficient than finding the min-cut from scratch which takes time at least $O(nm)$.

I am looking for any references/keywords for cases more general than the simple cut-function described above. It doesn't have to be the most general submodular function  e.g. I can restrict my attention to graphs but allow the cut function $f:2^V\rightarrow \mathbb{R}_+$ to be a more general (non-negative submodular) function, based on the capacities of the edges crossing the cut.

Thanks.

P.S. I am aware that there is some work on parametric submodular function minimization, however I can't use that since I have to do the above problem repeatedly. E.g. in the graph example I described, I have to add/delete an edge, reoptimize, add/delete an edge, reoptimize and so on. This does not fall in the parametric framework.


texts: "Smallest" path that visits a given set of vertices

texts:
I use smallest rather than shortest to distinguish between the shortest path problem. The problem is as follows:

  Given a directed graph $G=(V,E)$, two vertices $s$ and $t$, and a set of $p$ vertices $x_1,x_2,\ldots, x_p$. The goal is to find a $s-t$ path  which visits all of $x_1,\ldots, x_p$, such that the size of the set of visited vertices is minimized. Here we can assume $p$ is a constant, and the path needs not to be simple.

At first I thought this is the same as "shortest path that visits a certain set of vertices" problem, and I know this problem can be reduced to the TSP problem. Since $p$ is a constant, I can enumerate all possible visiting orders of $x_1,\ldots,x_p$ and compute the union of the shortest paths between consecutive vertices in each order.

However, because we don't require the path to be simple, I'm not sure whether the shortest path is equivalent to the smallest path desired by the problem. I feel that it's possible to find a path which is long in the sense that some vertices of it are visited many times, but small in the sense that the number of all unique vertices are small. But till now I don't find such an example.

Although I don't have an algorithm, I believe the problem is polytime solvable. Any suggestions?


texts: Does Rabin/Yao exist (at least in a form that can be cited)?

texts:
In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation".  This is for the result that the bounded-error communication complexity of the equality function EQ$_N$ (whether two integers in the range $0$ to $N-1$ are equal) is $O(\log\log N)$.

Andrew Chi-Chih Yao, Some Complexity Questions Related to Distributed Computing (Preliminary Report), STOC 1979, pp. 209–213.  doi:10.1145/800135.804414

Alexander Razborov's introductory survey on communication complexity proves this result and states "the following beautiful construction [is] usually attributed to Rabin and Yao".  The idea is to consider the bit strings as coefficients of a predetermined polynomial $P(x)$; Alice then picks a random integer $q$ from 0 to $p-1$ for some predetermined prime $p \in [3n,6n]$, where $n = \lceil \log N\rceil$, and sends $(q, P(q) \mod p)$ to Bob.

Alexander Razborov, Communication Complexity, chapter 8 of "An Invitation to Mathematics", pp. 97–117, Springer, 2011.  (preprint)

Did the Rabin/Yao paper ever get to be at least a personal communication/draft/sketch in someone else's paper, or is this one of those indications of the "golden era" where giants roamed the earth and didn't always touch ground when stepping from breakthrough to breakthrough?


texts: Comparing Two Algorithms for 3SUM problem over Integers

texts:
The paper "Subquadratic Algorithms for 3SUM", by Ilya Baran, Erik D. Demaine, Mihai Patrascu has the following complexity for the

3SUM problem: given a list $L$ of $n$ integers if there are $x,y,z \in L$ such that $x+y=z.$

They state, "On a standard word RAM with $w-$bit words, we obtain a running time of
$O(n^2/ \max\{w \log w, \log n (\log \log n)^2 \})$. In the circuit RAM with one nonstandard $AC0$ operation, we obtain $O(n^2/ w^2 \log w)$. In external memory, we achieve $O(n^2/(MB))$, even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of $O(n^2/ MB \log M )$. In all cases, our speedup is almost quadratic in the “parallelism” the model can aﬀord, which may be the best possible. See the Baran, Demaine, Patrascu paper here.

Recently, a paper "Threesomes, Degenerates, and Love Triangles" by Grondlund and Pettie has proved that "the decision tree complexity of 3SUM is $O(n^{3/2}\sqrt{\log n})$,  and that there is a randomized 3SUM algorithm running in $O(n^2(\log \log n)^2/\log n)$ time, and a deterministic algorithm running in $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ time.

These results refute the strongest version of the 3SUM conjecture, namely that its decision tree (and algorithmic) complexity is $Ω(n^2)$."

See this second paper here.

Clearly, both are important papers. Not being an expert to this area, my question is about how to compare the impact and significance of either, given the different complexity models. Any other insightful comments about this problem is also welcome. For example had the first paper already ruled out the $\Omega(n^2)$ bound?


texts:
Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$?

If $e\log b$ bits are available, the number can simply be calculated by standard techniques and the 1s counted.  But what techniques are possible when less memory can be used?


texts: How to sample from a distribution with submodular weights

texts:
Is there a known algorithm for sampling a set $S \subset \{1,...,n\}$ with probability
$p_S = \frac{e^{f(S)}}{\sum_{T \subset \{1,...,n\}} e^{f(T)}}$ where $f: 2^{\{1,...,n\}} \to \mathbb{R}$ is a submodular function?

Thanks!


texts: Simulating nondeterministic space-bounded computation using randomness

texts: Let's suppose that a language $L \in$ NSPACE($f(n)$) where $f(n)$ is $O(\log n)$. And now let's suppose that I have a probabilistic Turing machine. Can this machine run in $O(f(n))$ space and answer yes when $x \in L$ with $\Pr(yes) > 1/2$ and answer no when $x \not\in L$ with $\Pr(no) = 1$? Let's suppose I dont care about time as long as the machine halts.


texts: Standard reference for basic model theory definitions

texts:
I am trying to give a formal presentation of the model-theoretical semantics of a language and I am a bit lost in the terminology. In particular, could somebody clarify the exact definitions of model-structures or pre-interpretations, interpretations and interpretation functions ? It would be great if you could point me to a standard reference.

The way I see it, a "pre-intepretation structure" is defined for the signature of a particular language/logic as regrouping a domain and a mapping ("interpretation function" ?) of constants and predicates to that domain.  Next, one has to assign particular truth values to each of the constructs of the language, according to a specific "interpretation" and valuation. Is this the standard terminology ? Thank you !


texts: Can all linear lambda calculi be linearity checked syntactically?

texts:
Given a lambda calculus with explicit linearity and usual application and abstraction, can the linearity check be done on an untyped syntax tree if we keep track of the structural types? Are the explicit operators necessary?

I suspect the answer is yes, from these course notes by Frank Pfenning because syntactic constructs are needed to use $A \& B$, $A \otimes B$, and $A \oplus B$.

However, if named functions exist (as in an actual programming language), some types are clearly necessary: consider the function $cond \colon Bool \to A \& A \multimap A$.

Can type checking and linearity checking be done in two steps, and can linearity checking happen before type checking?

Edit: The algorithm provided in the above course notes type checks linear lambda calculus terms, which includes determining if the term is linearly well-formed. Is it possible to determine if a term is well-typed via a syntactic linear well-formedness check (which would eliminate $\lambda x. x x$) followed by a type check which does not consider linearity? Or is this interaction essential to complete type inference?


texts: Is there any work on purely functional approximation algorithms?

texts:
It seems to me that approximating a solution to an NP-hard problem would be especially hard for the functional programmer.  For example, graph problems are commonly NP-hard.  But graphs are notoriously awkward to work with functionally.  This makes me think that problems that can be easily solved in a purely functional sense are somehow easier than those that require state.  This distinction in turn might shed some light on what makes hard problems hard.

So, is there any work on purely functional approximation algorithms?  My general impression is that both communities ignore each other.


texts: Pseudorandom generator for finite automata

texts:
Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata?

Here, a $d$-state finite automata has $d$ nodes, a start node, a set of nodes representing accept states, and two directed edges labeled 0, 1 coming out of each node. It changes state in the natural way as it reads input. Given an $\epsilon$, find $f:\{0,1\}^{k}\to \{0,1\}^n$ such that for every $d$-state finite automaton computing some function $A$,

$$|\mathbb P_{x\sim U_{k}}(A(f(x))=1)-\mathbb P_{x\sim U_n}(A(x)=1)|< \epsilon.$$

Here $U_k$ denotes the uniform distribution on $k$ variables, and we want $k$ to be as small as possible (e.g. $\log n$). I'm thinking of $d$ being on the order of $n$, though we can also ask the question more generally (ex. would the number of bits required grow with $n$?).

Some background

Construction of pseudorandom generators is important in derandomization, but the general problem (PRG's for polynomial-time algorithms) has so far proved too difficult. There has however been progress on PRG's for bounded-space computation. For example this recent paper (http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf) gives a bound of approximately $\log n\log d$ for regular read-once branching programs. The question with general read-once branching programs is still open (with $k=\log n$), so I'm wondering if the answer for this simplification is known.  (A finite automaton is like a read-once branching program where every layer is the same.)


texts: SOS and the small set expansion property

texts:
For what graphs do we know that their small set expansion property has a low degree SOS proof?
Is this known to be true for say the complete graphs?

A terminology issue about what is ``low degree" :

Around page 13 here, http://www.boazbarak.org/sos/files/lec2d.pdf, when this was shown for the Boolean hypercube graph the author claimed that this is a degree $4$ SOS certificate. This terminology is a bit peculiar to me. Because as one sees in the proof it uses non-negativity of the pseudo-expectation of polynomials of the form $(fg)^2$ where $f$ and $g$ are degree at most $d$ polynomials in $n-1$ variables. So I think this should have been called a degree $4d$ SOS certificate. But somehow they want to see this as a degree $4$ SOS proof in the space of Fourier coeffients because the product $fg$ is obviously degree $2$ over Fourier coefficients. I am not sure if this way of thinking makes sense! It would be helpful to know why this way of counting makes sense!


texts: Cite a conference contribution as conference paper of book chapter

texts:
Let's say you submit a paper to a TCS conference and it is accepted. Then you go there and give a talk. When you put this information in your CV;

do you write it as two items in different sections; first in conferences and second the published paper or just as one single thing?
if the paper is published in some sort of a book (book of abstracts, LNCS, etc) with ISBN, will you cite it as conference paper or as book chapter?

Thanks


texts: How not to compute the smallest circle enclosing a finite set of circles

texts:
Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of Matoušek, Sharir and Welzl [1] to find a basis $B$ of $L$, and let $D=\langle B\rangle$, the smallest disk containing $\bigcup B$. The disk $\langle B\rangle$ may be computed algebraically using the fact that, since $B$ is a basis, each disk in $B$ is tangent to $\langle B\rangle$.

($B\subseteq L$ is a basis of $L$ if $B$ is minimal such that $\langle B\rangle=\langle L\rangle$. A basis has at most three elements; in general for balls in $\mathbb{R}^d$ a basis has at most $d+1$ elements.)

It is a randomised recursive algorithm as follows. (But see below for an iterative version, which may be easier to understand.)

Procedure: $MSW(L, B)$
Input: Finite sets of disks $L$, $B$, where $B$ is a basis (of $B$).

If $L=\varnothing$, return $B$.
Otherwise choose $X\in L$ at random.
Let $B'\leftarrow MSW(L-\{X\}, B)$.
If $X\subseteq\langle B'\rangle$ then return $B'$.
Otherwise return $MSW(L, B'')$, where $B''$ is a basis of $B'\cup\{X\}$.

Used as $MSW(L, \varnothing)$ to compute a basis of $L$.

Recently I had cause to implement this algorithm. After verifying that the results were correct in millions of randomly-generated test cases, I noticed that I had made an error in the implementation. In the last step I was returning $MSW(L-\{X\}, B'')$ rather than $MSW(L, B'')$.

Despite this error, the algorithm was giving the right answers.

My question: Why does this incorrect version of the algorithm apparently give correct answers here? Does it always (provably) work? If so, is that also true in higher dimensions?

Added: some misconceptions

Several people have proposed incorrect arguments to the effect that the modified algorithm is trivially correct, so it may be useful to forestall some misconceptions here. One popular false belief seems to be that $B\subseteq\langle MSW(L, B)\rangle$. Here is a counterexample to that claim. Given disks $a,b,c,d,e$ as below (the boundary of $\langle a,b,e\rangle$ is also shown in red):

we can have $MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$; and note that $e\notin\langle c,d\rangle$:

Here is how it can happen. The first observation is that $MSW(\{c\},\{a,b,e\})=\{b,c\}$:

We wish to compute $MSW(\{c\},\{a,b,e\})$
Choose $X = c$
Let $B' = MSW(\varnothing, \{a,b,e\}) = \{a,b,e\}$
Observe that $X\notin\langle B'\rangle$
So let $B''$ be a basis of $B'\cup\{X\} = \{a,b,c,e\}$
Observe that $B''=\{b,c\}$
Return $MSW(\{c\}, \{b,c\})$, which is $\{b,c\}$

Now consider $MSW(\{c, d\}, \{a,b,e\})$.

We wish to compute $MSW(\{c, d\}, \{a,b,e\})$
Choose $X=d$
Let $B' = MSW(\{c\}, \{a,b,e\}) = \{b,c\}$
Observe that $X\notin\langle B'\rangle$
So let $B''$ be a basis of $B'\cup\{X\} = \{b,c,d\}$
Observe that $B''=\{c,d\}$
Return $MSW(\{c,d\}, \{c,d\})$, which is $\{c,d\}$

(For the sake of definiteness, let us say that the disks $a,b,c,d,e$ all have radius 2, and are centred at $(30,5)$, $(30,35)$, $(10, 5)$, $(60, 26)$, and $(5, 26)$ respectively.)

Added: an iterative presentation

It may be easier to think about an iterative presentation of the algorithm. I certainly find it easier to visualise its behaviour.

Input: A list $L$ of disks
Output: A basis of $L$

Let $B\leftarrow\varnothing$.
Shuffle $L$ randomly.
For each $X$ in $L$:
  If $X\notin\langle B\rangle$:
    Let $B$ be a basis of $B\cup\{X\}$.
    Go back to step 2.
Return $B$.

The reason the algorithm terminates, incidentally, is that step 5 always increases the radius of $\langle B\rangle$ – and there are only finitely many possible values of $B$.

The modified version doesn’t have such a simple iterative presentation, as far as I can see. (I tried to give one in the previous edit to this post, but it was wrong – and gave incorrect results.)

Reference

[1] Jiří Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4-5):498–516, 1996.


texts: Proving that inclusion is antisymmetric in Coq

texts:
I'm a Coq newbie and I'd like to prove that the inclusion relation is antisymmetric, that is: $\forall x\forall y(x\subseteq y\land y\subseteq x\rightarrow x=y)$.

I wrote the following thing:

Section Test.
Variable set : Type.
Variable element : set -> set -> Prop.
Definition subset (x:set) (y:set) := forall z:set, element z x -> element z y.
Axiom equality : forall x y:set, x = y <-> forall z:set, element z x <-> element z y.
Theorem inclusion_is_antisymmetric : forall x y:set, subset x y /\ subset y x -> x = y.
Proof.
intros a b.
unfold subset.
intro H.
destruct H as [H0 H1].

At this point I get the following output:

1 subgoal
set : Type
element : set -> set -> Prop
a : set
b : set
H0 : forall z : set, element z a -> element z b
H1 : forall z : set, element z b -> element z a
______________________________________(1/1)
a = b

I'm stuck now because I don't know how to:

change the goal from $a=b$ to $\forall z(z\in a\leftrightarrow z\in b)$ and then to $c\in a\leftrightarrow c\in b$
change H0 from $\forall z(z\in a\rightarrow z\in b)$ to $c\in a\rightarrow c\in b$
change H1 from $\forall z(z\in b\rightarrow z\in c)$ to $c\in b\rightarrow c\in a$

That is, I know how to prove this theorem on paper but not with Coq.


texts: Complexity of comparing polygon perimeters

texts:
The problem of comparing the lengths of two paths of line segments connecting points in $\mathbb{Q}^2$ is not known to be in $\text{P}$, nor even in $\text{NP}$.

Does requiring that the paths begin and end on the same point change anything about our state of knowledge?

What if additionally the paths are not permitted to self-intersect, that is, they are polygons?

Finally, what if the polygons are required to be convex?

My understanding of the obstruction is that the length of a path with $n$ segments is the root of a $2^n$-degree polynomial and we can't rule out that those might end up being so close together that we have to compute exponentially many digits.  Superficially, we're in the same situation with bumpy wheels as with wild scribbles.


texts: Does an infinitely long tape make any difference when proving theorems about Turing Machines?

texts:
Standard accounts of Turing Machines in the literature assume an infinitely long tape in at least one direction (and indeed infinitely time long to perform its computations). Clearly in practice no computer could have an infinite amount of cell storage either from the commencement of computations (even if we disregard the infinite amount of available time) or by adding blank cells at the end of the tape as required (which we'll eventually need if we assume infinite amount of time).

So my question is this: do the properties about Turing Machines obtained by assuming an infinitely long tape still hold of practical computing devices, for instance the existence of uncomputable functions? If so what does the assumption of an infinite tape buy us in terms making it easier to prove such properties?


texts: When have we found better bounds for known algorithms?

texts:
Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - obviously that's happened! But better analysis leading to a better bound on an existing algorithm

I thought matrix multiplication was an example of this, but I have talked myself out of it (perhaps incorrectly!) after trying to understand Coppersmith–Winograd and its friends better.


texts:
In functional programming and in the theoretical setting of the $\lambda$-calculus it is standard to consider a lambda abstraction $\lambda x.M$ as a value. In my understanding, the intuitive reason is that a function $\lambda x.M$ is an finished piece of data, sharing with other values like $3$ or $\mathtt{true}$ the following ontological status:  something that one can handle independently of a notion of execution. (Indeed, you cannot execute $\lambda x.M$ until you apply it to something. Of course you may reduce a $\beta$-redex in $M$, but then intuitively you are not reducing the whole piece of code $\lambda x.M$.)

Now, when it comes to dependent type theories, or more generally any type system having some vertex of Barendregt's cube as its core, all levels of the syntax - objects, types, kinds and possibly all the infinite higher kinds - have the status of terms. So it makes sense to ask when one of them is a value. Let us ask the question for types, but of course the same applies to all possible superior kinds.

Obviously a functional type $\lambda x: T. T' : \Pi x: T.A $ (for $A: \mathtt{Kind}$ and $T:\mathtt{Type}$) is a value. (Notice that in basic dependent type theory, the one without the higher-dimensional kinds $\omega$, the kind $\Pi x: T.A$
 is actually $T\to A$).

Now, what about the universal type $\Pi x: T.T'$ (where $T,T': \mathtt{Types}$) ? From a mathematical perspective it is a family, hence a function. It corresponds to my definition of ontology of a value above: something that one can handle independently of a notion of execution.
But on the other side $\Pi x: T.T'$  has a relevant difference from $\lambda x: T. T' $: the latter has a destruction operator (the application), whereas the former does not. In light of this, would you consider $\Pi x: T.T'$ as a value?

In a way, I am asking the following (philosophical?) question. Which intuition do you prefer:

a value is something that one can handle independently of a notion of execution
a value is something that one can handle independently of a notion of execution and when it is not ground can be decomposed via an appropriate operator.

In case 2  the "dependent arrow" type $\Pi x: T.T'$ is not a value, only the functional type $\lambda x: T. T'$ and the polymorphic universal type $\forall X.T$ are.

I am personally inclined towards option 2, but I would like to hear from more experienced researchers.


texts: Which properties of planar graphs generalize to higher dimension / hypergraphs?

texts:
A planar graph is a graph which can be embedded in the plane, without having crossing edges.

Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k.

There has been some work done on embedding hypergraphs in the plane (with the context of clustering or some other application), but often, the data just can't be embedded in the plane. The solution could be either to force it, with some loss, or embed it in higher dimension as I suggest here:

A natural extension of planarity (IMO, at least) is a "$k$-simple-embedding" (is there a known different name for it?) of $G$: an embedding $\mathcal{M}:X\to \mathbb{R}^k$, such that there exist surfaces which connect all of the vertices of each hyperedge, and these do not intersect except for the endpoints.

(Think of the analogue in 2D, where each surface is an edge you can draw however you like).

Here's an example of a valid 3-simple-embedding of a 3-uniform-hypergraph. (Each vertex is colored by the hyperedges it is contained in, and each face represents an hyperedge).

Another example of 3-simple graph is the complete 3-uniform-hypergraph on 5 vertices $G=(V,V\times V\times V)$. To see this simply take 4 points in $\mathbb{R}^3$ which don't lie on a 2D plane, create a triangular pyramid (their convex hull), and place the fifth point in the center of the pyramid, connecting it to the other vertices.

Similarly, it seems that the complete 3-uniform-hypergraph on 6 vertices doesn't have a 3-simple-embedding.

There are some very useful properties of planar graphs which allow improved algorithms for hard problems when the graph is planar. Unfortunately, the data is often not planar, although sometimes it is of low dimensionality. I think that understanding which properties of planar graphs generalize will help us figure out which algorithms can be adapted for higher dimension with the same tool.

An example of a property that could be useful comes from Fáry's Theorem which suggests every planar graph can be embedded in a way that all of its edges are straight line segments.

Does Fáry's Theorem hold in higher dimension?, i.e. if a graph has a $k$-simple-embedding, does it have an embedding in which all of the hyper edges are hyperplanes?

Are there any other properties that can be generalized? for example, can Euler's Formula for planar graphs be generalized somehow to higher dimension? (although at the moment I'm not sure what would be the meaning of it).


texts: What is the interpretation of an infinite formal context-free grammar?

texts:
Let $L$ be a language as follows:

$$
\begin{align*}
L  &::= a\ |\ L^{*}\\
\end{align*}
$$

Now, suppose I apply some sort of transformation $T : N \rightarrow N$ where $N$ is the set of non-terminals in the grammar. Suppose that this results in $L$ being transformed into a modified version of $L$ by adding a unique prefix and postfix terminal to the $L^{*}$, and adding that new alternative parse to the grammar.

$$
\begin{align*}
L  &::=  &  a\ |\ L^{*}\\
   &\ |  & (hello)\  L^{*}\ (bye)
\end{align*}
$$

As we apply $T$ infinitely many times to the context-free grammar, where the added terminals can be any arbitrary pairs of strings:

$$
\begin{align*}
L  &::=  &  a\ |\ L^{*}\\
   &\ |  & (hello)\  L^{*}\ (bye)\\
   &\ |  & (hi)\  L^{*}\ (goodbye)\\
   &\ |  & (begin)\  L^{*}\ (end)\\
   &     \vdots & \vdots
\end{align*}
$$

...is the resulting grammar still context-free or is it now context-sensitive?

In short -- if a grammar has an infinite set of prefix/postfix pairs for a given non-terminal, is it a context-free grammar?


texts: In domain theory, what can the extra structure present in metric spaces be used for?

texts:
Smyth's chapter in the handbook of logic in computer science and other references describe how metric spaces can be used as domains. I do understand that complete metric spaces give unique fixed points but I don't understand why metric spaces are important. I'd really appreciate any thoughts on the following questions.

What are good examples of the use of (ultra/quasi/pseudo)metric spaces in semantics?
In particular related to any example:
  Why do we need the metric structure?
  What do $\omega$-CPOs lack that the metric supplies?

Also:
Is the unique fixed point property important? What's a good example?

Thanks!


texts: About the decidability of sets enumerated in non decreasing order

texts:
It is well known that a set of numbers enumerable in nondecreasing order is
decidable. However, the typical proof, by cases on the finiteness of the
enumerated set, is not constructive. In general, it does not seem possible
to effectively derive the decider from the enumeration function (and its properties): can this be proved?

Here is a possible formalization of the problem. Let $\varphi$ be an effective enumeration of all computable functions.
Let $c_A$ be the characteristic function of $A$, Let $f$ be a function such that

$$\varphi_{f(i)} =
\begin{cases}
c_{cod{(\varphi_i})} & \mbox{if $\varphi_i$ is total and non decreasing}\\
                 \mbox{arbitrary} & \mbox{otherwise}
\end{cases}
$$
Prove that no such $f$ is computable (or that it is indeed computable).


texts: Non-trivial existence proof in type theory

texts: What are some examples of existence proofs in Coq/Agda etc., where the constructed natural number is useful from mathematical point of view, but it's non-obvious from the proof what it should be? I am aware of the Brunerie number in homotopical versions of type theory, but as far as I know, this doesn't really compute or takes far too long in current implementations of Cubical Type Theory. Are there any interesting applications in Agda/Coq etc. with K, which compute and weren't done by hand on paper? Are there any interesting numbers in Cubical Agda, which were computed?


texts: Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?

texts:
It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$.
It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$.
$\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) = \mathsf{BPP}/f(n)$ for all $f(n)$.

What is the smallest class of functions $f(n)$ such that
$\mathsf{P}/f(n) = \mathsf{BPP}/f(n)$ is known?


texts: Type systems preventing laziness-related memory leaks?

texts:
Perhaps the main source of performance problems in Haskell is when a program inadvertently builds up a thunk of unbounded depth - this causes both a memory leak and a potential stack overflow when evaluating. The classic example is defining sum = foldr (+) 0 in Haskell.

Are there any type systems which statically enforce lack of such thunks in a program using a lazy language?

Seems like this should be on the same order of difficulty as proving other static program properties using type system extensions, e.g. some flavors of thread safety or memory safety.


texts: The computational complexity of spectral norm of a matrix

texts:
How hard is computing the spectral norm of a matrix? This paper says,

  ... it suffices to say that, except for few particular cases, the Matrix
  Norm problem is NP-hard.

I expected that the relevant chapter 2 would describe those exceptional cases but failed to find it.

Can anyone suggest a more definitive reference for computational complexity of spectral norm of a matrix?


texts: Computing the edge orbits of a graph (and discussing definitions)

texts:
A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a graph induce a partition of the vertices into orbits, where two vertices belong to the same orbit if and only if there exists an automorphism that takes one to the other. Intuitively, the orbits correspond to vertices that are structurally equivalent in the graph (one also says symmetrical). For example, in the left graph $G$ below, there are three orbits: $\{a\}$, $\{b\}$, and $\{c,d\}$.

The present question focuses on the analogue concept for edges. Several definitions of edge automorphisms seem to co-exist, which confuses me. For instance, Wolfram MathWorld
(link) defines an edge automorphism as a permutation of the edges that preserves adjacency among the edges (where two edges are adjacent iff they share an endpoint). Accordingly, the edge automorphism group of a graph is defined as the vertex automorphism group of its line graph.
What troubles me with this definition is that edges such as $ab$ and $cd$ in graph $G$ end up being in the same orbit of the edge automorphism group even though they are not symmetrical, because the corresponding vertices in the line graph $L(G)$ are (see the right-side picture). In fact, this definition seems to clash with that of edge-transitive graphs, where the concept of automorphism relates to symmetry, not adjacency. For the sake of disambiguation, I will subsequently refer to these two versions of edge automorphisms as adjacency-based versus symmetry-based.
Now, my questions:

Is there something wrong with my understanding of edge automorphisms, or is there inherently two different concepts considered in the literature? In the first case, please kindly point me to the mistake.

The actual motivation for posting the present question was to find a way to compute the symmetry-based version of the edge orbits of a given graph. Initially, I was computing them by reducing the problem to computing the vertex orbits of the line graph (as prescribed by the MathWorld definition), then calling standard automorphism routines on existing software like SageMath... until I realize that this was not what I wanted.
Of course, I do not expect an efficient algorithm for this problem, but any conceptually simple algorithm or reduction to another natural question would be much appreciated.

(Bonus question.) In the particular case that the edges are properly colored, are there reasons to believe that there could be an efficient way to compute the symmetry-based, color-preserving edge orbits? In fact, I could not find anything related even to classical automorphisms of properly vertex-colored graphs, so any pointer related to this natural case is also welcome.


texts: Where's the Flaw in Blum-Feldman-Micali's Method

texts:
Blum, Micali, and Feldman (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some distribution (usually, uniform distribution) by a trusted party. It is called the reference string, and the model is aptly named the common reference string (CSR) model.

The model allows us to perform many interesting interactive protocols non-interactively, replacing queries by bits from the reference string. In particular, zero-knowledge proofs for any NP language can be conducted non-interactively, giving rise to the notion of non-interactive zero-knowledge (NIZK).

NIZK has a lot of applications, such as providing a method for realizing public-key cryptosystems secure against (adaptive) chosen-ciphertext attacks.

BFM first proved the existence of a single-theorem version of NIZK for every NP language; that is, given a reference string $\rho$ and a language $L \in \bf{NP}$, one can prove only one single theorem of the form $x \in L$. In addition, the length of the theorem is bounded in $|\rho|$. If the prover attempts to reuse some bits of $\rho$ in later proofs, there's a danger of knowledge leakage (and the proof will no longer be NIZK).

To remedy this, BFM used a multi-theorem version based on the single-theorem NIZK. To this end, they used a pseudo-random generator to expand $\rho$, and then used the expanded bits. There are some other details as well, but I'm not going to dig in.

Feige, Lapidot, and Shamir (in the first footnote on the first page of their paper) stated:

  The method suggested in BFM for overcoming this difficulty was found to be flawed.

(The difficulty refers to obtaining multi-theorem proofs rather than single-theorem ones.)

  Where does the BFM flaw lie?


texts: Relation between Code Length and Symbol Weight in a Huffman Code

texts:
I'm not sure if I should ask this here or over at StackOverflow (sorry if this is not the right place).

I'm constructing a Huffman code for a series of symbols with associated weights. I have a list of the code-lengths corresponding to each symbol, sorted by symbol weight (in non-decreasing order). Does it follow that this list is also sorted by code-length (in non-increasing order)?

I suspect that the answer is yes (since lower-weighted symbols will generally have shorter code lengths), but I'm not sure if this is guaranteed.

I guess what I really want to know is, "if a Huffman tree has two leaves a and b, where a had a higher weight than b, is b's code length always at least that of a's?"

Thanks!


texts:
I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). It defines the language of a  pom-CFG by reduction to a normal context-free grammar, which excludes some (otherwise) possible words from the language, I think.

Thus I'm looking for other work.

What I mean by partially ordered CFG

The production rules don't produce linear strings of symbols but partially ordered (multi) sets of symbols. Thus the "words" of the generated language are also partially ordered multi-sets of symbols. For example this:

  b-c
 /   \
a     d-a
 \   /
  a--

The possible linearizations of this partially ordered word are aabcda, abacda, abcada.


texts: Can the Banach-Tarski paradox be "realized" by floating-point round-off?

texts:
The Banach-Tarski paradox says that
a ball in $\mathbb{R}^3$ can be partitioned into a finite number of pieces, whose rearrangement has a larger volume than the original.
It occurred to me that it might be possible to define the pieces
$P_1,P_2,\ldots,P_n$ by a finite amount of geometric data, such that
the applied rearrangement function $f(P_i)$ actually does increase the volume of $P_i$, because
of floating-point round-off error: $f$ is an isometry but when implemented
in floating-point hardware it is not an exact isometry. So it might be possible that
$$\textrm{Vol}(f(P_1))+\ldots \textrm{Vol}(f(P_n)) > \textrm{Vol}(P_1)+\ldots \textrm{Vol}(P_n) \;.$$
Repeating, this might lead to a type of "realization" of the paradox in terms of floating-point
computations.

Whether you think this would be as interesting as I do is in the eye of the beholder.


texts: Computing dual of the spectral norm of tensor of order 3

texts:
It is shown in http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf that computing the spectral norm (see Definition 6.6) of a $3^{rd}$ order tensor $T \in \mathbb{R}^{d_1 \times d_2 \times d_3}$ is NP-hard (Theorem 1.1 in fact shows it is np-hard to approximate it to with a certain factor). Does this statement imply (trivially ?) any hardness result about computing the dual of the spectral norm ? The dual in this case is defined as:

\begin{equation}
\max_{ Y \in\mathbb{R}^{d_1 \times d_2 \times d_3}, \|Y\| \leq 1 } \langle T,Y  \rangle,
\end{equation}
where $\langle \cdot, \cdot \rangle$ is the (tensor) inner product and $\| \cdot \|$ is the spectral norm.

(Note that in the matrix case, dual of the spectral norm is just the sum of singular values of the matrix; also called nuclear norm of the matrix)


texts:
I am new to combinatory logic, and I am interested in its relationship to first-order logic. In particular, I am wondering if there is a universal translation of first-order logic to combinatory logic with the usual combinators S, K, B, C, I, together with Schonkinfel's combinator U (which stands for disjoint class: UPQ=$\neg\exists x(Px\wedge Qx)$). For instance, given a sentence $\forall y\exists x(Ny\supset (Px\wedge Gxy))$, its translation in CL is $UN\mathrm{B}(UP)(\mathrm{C}G)$ (this example is taken from https://plato.stanford.edu/entries/logic-combinatory/). Is there a universal procedure for translating first-order formulas (and is there a way of translating combinators into first-order formulas)?
On this note, I am also curious if the combinator U can be defined in terms of S and K.

Many thanks in advance.


texts: Bigger picture behind the choice of matrices in the Strassen algorithm

texts:
In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the algorithm proceeds recursively computing $7$ block matrix-matrix products as opposed to a naive $8$ block matrix-matrix products, i.e., if we want $\mathbf{C}=\mathbf{A} \mathbf{B}$, where
$$\mathbf{A} =\begin{bmatrix}
\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\
\mathbf{A}_{2,1} & \mathbf{A}_{2,2}
\end{bmatrix}
\mbox { , }
\mathbf{B} =
\begin{bmatrix}
\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\
\mathbf{B}_{2,1} & \mathbf{B}_{2,2}
\end{bmatrix}
\mbox { , }
\mathbf{C} =
\begin{bmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2}
\end{bmatrix}$$
then we have
$$
\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}\\
\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}\\
\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}\\
\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} $$
which requires $8$ multiplications. Instead in Strassen, we compute
$$
\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})\\
\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}\\
\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})\\
\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})\\
\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}\\
\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})\\
\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})
$$
and obtain $\mathbf{C}_{i,j}$'s using $\mathbf{M}_{k}$'s as
$$
\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}\\
\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}\\
\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}\\
\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}
$$
However, the choice of the matrices $\mathbf{M}_k$'s seem arbitrary to me. Is there a bigger picture as to why we choose these specific products of sub-matrices of $\mathbf{A}$ and $\mathbf{B}$? Also, I would expect $\mathbf{M}_k$'s to involve $\mathbf{A}_{i,j}$'s and $\mathbf{B}_{i,j}$'s in a symmetric fashion, which does not seem to be the case here. For instance, we have $\mathbf{M}_2: = (\mathbf{A}_{2,1}+\mathbf{A}_{2,2})\mathbf{B}_{1,1}$. I would expect its counterpart say $\mathbf{A}_{1,1} (\mathbf{B}_{1,2} + \mathbf{B}_{2,2})$ also to be computed. However, it is not since it can be obtained from other $\mathbf{M}_k$'s.

I would appreciate if someone could throw some light on this.


texts:
There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc.

In this case I wonder whether a problem can be meta-undecidable. This means (at least in my head) we cannot tell whether it is decidable or not.

Maybe it's known decidability is undecidable (everything is meta-undecidable) and no algorithm exists to prove decidability for anything, so decidability has to be proven by hand on a case by case basis.

Maybe my question doesn't make sense. Maybe I'm assuming we are carbon machines running very complex algorithms and that's why the question makes sense only in my head.

Please let me know if the question needs further clarification. I may need that myself at this moment.

Thank you.


texts: Does the physical Church-Turing thesis imply that all physical constants are computable?

texts:
The physical Church Turing thesis is a conjecture that any physically computable algorithm can be computed by a Turing machine.

Let us create a machine that, for example, outputs the digits of the fine-structure constant. The Fine-structure constant is measurable, and does not depend on the units of measure.

This would seem to imply, via the physical Church Turing thesis, that the fine-structure constant is computable by a Turing machine! This seems unlikely, since only countable many numbers have that property.


texts: Are there presentations of set theory in terms of lambda-calculus?

texts: I am planning to implement in software a set theory language, based on a binary function, which in set theory is the so called adjunction operation: $f(x, y) = x \cup$ {y}. Therefore, a presentation of set theory in terms of lambda-calculus will really help. Are there such presentations or attempts to do it?


texts:
Possible Duplicate:
  What would it mean to disprove Church-Turing thesis?

Are there any models of computation currently being studied with the possibility of being more powerful than Turing Machines?


texts: Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions

texts:
Consider a planar subdivision, with F faces, V vertices, E edges, and I face-vertex incidences. For simplicity, assume a "non-degenerate" situation in which each vertex occurs on the boundary cycle of each face only once. Then I is the sum over all faces of the number of vertices per face, or equivalently, the sum over all vertices of the number of incident faces. We have I = 2E, and therefore Euler's formula gives us:

F + V = I/2 + 2.

All I actually care about is:

F + V < I/2.

Does this also hold in for three-dimensional subdivisions, when F is the number of three-dimensional cells of the subdivision, and V and I are as defined above?

Note that I am looking for an inequality that is independent of the number of one- and two-dimensional faces in the subdivision. When the cells are convex I can get something using quite a bit of geometry, but it seems to me that the requirement that the cells be convex is an artifact of my proof technique, and something more general should be possible and/or known. Does anybody have an idea where to look for the answer?


texts: Estimating a percentile among distributed nodes without revealing values

texts:
I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it.

Problem: Suppose a list of N numbers is shared among a set of participants in such a way that no single participant actually knows any of the numbers they share. All participants know N (the size of the list of numbers) and the sum of all of the numbers on the list, but nothing more a priori.

By working together, it is possible to compare two shared numbers a and b in such a way that the participants learn whether the statement "a < b" is true, but nothing more. However, this is an extremely expensive thing to do (read: it could take many seconds, perhaps even minutes, to complete a single comparison). See the end of this post for a bit more information on how such a thing is possible.

At the end of the day, the parties wish to output of which indices in the list correspond to the "top K percent" (the K% which is largest) shared numbers in the list. This can of course be done by sorting, or using a "top K" selection algorithm. However, these tend to use an aweful lot of comparisons, which is to be avoided. (These are either O(n log n) or O(n), with fairly large hidden constants.)

Another alternative is to "guess" at a number X for which (1-K)% are smaller than X and K% are larger. Then you can compare each element with X and see how many are larger and how many are smaller. If your guess was wrong, revise it using something like a binary search until you converge on a correct solution. This takes far fewer comparisons if your guess is good.

So, my question is,

  Given only N and the sum, what is the best way to "predict" X?

Of course this will depend on the underlying distribution. For different use-cases the underlying distribution will likely be different but will be known, so I am interested in good solutions for all the common ones (normal, uniform, exponential, perhaps a few others). I would also love to hear suggestions regarding how best to do the "binary-like" search to minimize the number of steps given an assumption about the underlying distribution.

APPENDIX: Each value on the list is shared among participants using Shamir's secret sharing scheme. Suppose there are M participants and the list is of length N. Then, the i-th number on the list is represented by a polynomial $f_i$ of degree M-1 over some finite field F. The constant term of $f_i$ is the number that is shared, all other coefficients are chosen uniformly at random from F. The j-th participant's shares are then $f_i(j)$, $1\leq i\leq N$. Given this share, the participant has no information (in an information-theoretic sense) about the number; in fact, no proper subset of participants can combine knowledge to learn any information about the shared numbers. However, using a sophisticated secure multi-party computation technique, it is possible to determine if one shared value is less than another without revealing any more information. This technique involves all participants cooperating, which is why it is so costly to do and should be done the fewest number of times possible.


texts: Number of bits required for encoding variables with fixed sum?

texts:
Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$

It's easy to store the variables using $r\log N$ bits, but this doesn't take advantage of the fact that their sum is bounded.

Furthermore, in my application $r$ is not fixed and could vary from $\frac{M}{N}$ to $M$, so I would need $M\log N$ bits in the worst case if I use the naive encoding.

So the questions are as follows:

How many bits are required to encode the variables, given that an adversary picks the values of $r$ and $x_1,x_2,\cdots,x_r$?

Is there an data structure that uses close-to-optimal space for this that supports efficient replacement operations (where replace$(i,j)$ increases the value of $x_j$ by 1 and decrements the value of $x_i$ by 1)?

If it helps, you may assume $M=N$ (which is what I need for my application), but I think it's interesting for general $M,N$.


texts: Finding $x_1,x_2,...,x_k$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is minimal

texts:
Here is a problem I'm trying to solve:

Given an integer $n$ return a list $[x_1,x_2,...,x_k]$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is as low as it can be.

I'm thinking of creating a list of n ones, then pairing them as long as I can (so for example $[1,1,1,1,1]$ becomes $[2,2,1]$) then I want to exchange all triples of $[2,2,2]$ to one $3$ (because $2!+2!+2!=3!$) and so on...

Intuitively this should be correct, and also quite fast - the input on which I'm executing my "concatenations" shrinks as fast as factorial function grows...

But is my method correct? And also if I were to find complexity of my algorithm in terms of $n$, how should I do that? One more thing, maybe there is simpler way to solve this algorithmic problem - any ideas?


texts: Lower bounds for Polynomials computing the boolean functions

texts:
Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields.
One of the most popular examples is Fourier Analysis e.g.  http://analysisofbooleanfunctions.org/ .
Another topic is transforming small depth circuits to polynomials over the integers with small degree and  magnitudes of small weights. For example, the transformation from ACC circuits to polynomials proved by Yao and Beigel and Tarui is notable.
My questions are:

Qestion A. Is there a list of results about lower bounds and remarkable techniques for polynomials computing boolean functions.
I know Williams' separation between NEXP and ACC.
Question B. Does the recent separation result about ACC $\circ $ THR circuits by Williams contain some interpretation relating with polynomials computing boolean funcitons ?
Question C. Is proving lower bounds on the number of monomials or the degree or other  formally defined complexity measures related with algebraic complexity theory and arithmetic circuit complexity established by Valiant with VP v. VNP problem??
I am reading the survey written by Shiplka, and have met a difference between boolean complexity and arithmetic complexity: semantic versus syntatic.

Here is a response to the J's question.
The survey has a remark about the difference between polynomial and polynomial function.
Taking an example, $x^{2}-x$ is a polynomial which is NOT identicdally zero but is a polynomial function $GF(2)^{n}\rightarrow GF(2)$ identically zero over $GF(2)$.
In algebraic complexity, Valiant's question is  about complexity of the expressing polynomial (not polynomial function).
However, I mainly want to consider polynomial functions. Thanks.


texts:
David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way.

This statement isn't very precise, but let me try to rephrase it in a slightly more formal way: For every collection type C, there exists a lock-free collection type CLF that offers the same set of operations, and where each operation on CLF has the same big-O complexity as the corresponding operation on C.

I don't expect a transformation, by the way.


texts: The algebraic connectivity of graphs with large isoperimetric number

texts:
I asked this question on MO, but no answer. Let $G = (V,E)$ be an undirected graph with maximum degree $\Delta$. the isoperimetric number of $G$, denoted $i(G)$, is defined by
$$i(G) = \min_{|S| \leq |V|/2} \frac{e(S,\bar{S})}{|S|},$$
where $e(S,\bar{S})$ is the number of edges between $S$ and its complement $\bar{S}$.
The Cheeger inequality asserts that:
$$\frac{\lambda_2}{2} \leq i(G) \leq \sqrt{\lambda_2(2\Delta-\lambda_2)},$$
where $\lambda_2$ is the second smallest eigenvalue of the Laplacian matrix $L=D-A$ (which also known as the algebraic connectivity of $G$). In general, $i(G)$ can be far from $\frac{\lambda_2(G)}{2}$. For example, if $C_n$ is the cycle of order $n$, then $i(C_n) = \Omega(\frac{1}{n})$ and $\lambda_2(C_n) = O(\frac{1}{n^2})$. Can this be occurred if $i(G)$ be sufficiently large? Specifically, is this true that

  if $i(G) \geq 1$, then $\lambda_2(G) \ge 1$?

Is there any known result similar to this statement?


texts: Reducing factoring prime products to factoring integer products (in average-case)

texts:
My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring.

Assuming the problem of

  FACTORING:[Given $N = PQ$ for random primes $P, Q < 2^n$, find $P$, $Q$.]

cannot be solved in polynomial time with nonnegligible probability, the function

  PRIME-MULT: [Given bit string $x$ as input, use $x$ as a seed to generate two random primes $P$ and $Q$ (where the lengths of $P$, $Q$ are only polynomially smaller than the length of $x$); then output $PQ$.]

can be shown to be one-way.

Another candidate one-way function is

  INTEGER-MULT: [Given random integers $A, B < 2^n$ as input, output $A B$.]

INTEGER-MULT has the advantage that it is easier to define compared to PRIME-MULT. (Notice in particular that in PRIME-MULT, there is a chance (though fortunately negligible) that the seed $x$ fails to generate $P, Q$ that are prime.)

At least in two different places (Arora-Barak, Computational Complexity, page 177, footnote 2) and (Vadhan's Introduction to Cryptography lecture notes) it is mentioned that INTEGER-MULT is one-way assuming average hardness of factoring. However, neither of these two gives the reason or a reference for this fact.

So the question is:

  How can we reduce in polynomial time factoring of $N = PQ$ with nonnegligible probability to inverting INTEGER-MULT with nonnegligible probability?

Here is a possible approach (that as we will see does NOT work!):
Given $N = PQ$, multiply $N$ by a much (though polynomially) longer random integer $A'$ to get $A = NA'$. The idea is that $A'$ is so large that it has lots of prime factors of size roughly equal to $P, Q$, so that $P, Q$ do not "stand out" among the prime factors of $A$. Then $A$ has approximately the distribution of a uniformly random integer at a given range (say $[0,2^n-1]$). Next choose integer $B$ randomly from the same range $[0,2^n-1]$.

Now if an inverter for INTEGER-MULT can, given $AB$, with some probability find $A', B' < 2^n$ such that $A'B' = AB$, the hope is that one of $A'$ or $B'$ contains $P$ as a factor and the other contains $Q$. If that was the case, we can find $P$ or $Q$ by taking gcd of $A'$ with $N = PQ$.

The problem is that the inverter may choose to separate the prime factors, for example, putting the small factors of $AB$ in $A'$ and the large ones in $B'$, so that $P$ and $Q$ end up both in $A'$ or both in $B'$.

Is there another approach that works?


texts: Making an adjacency matrix positive semidefinite

texts: I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can find on which nodes to set self-loops and how many of those.


texts: What is the time complexity of substitution algorithms(normalization by evaluation, explicit subtitution)?

texts:
I'm studying the substitution algorithms of lambda calculus. I think now I understand how they work, but I couldn't find any materials about their time complexity yet.
This is what I've thought about each algorithm so far.

dumb substitution(Just recursively finding variables to substitute)
I think it's O((avg of the number of terms in each abstraction) * (maximum abstraction level) ^ 2) in pathological cases.

normalization by evaluation
I think it's O(the number of terms), which is linear. But I'm not sure that it really is with consideration of operations in the host language. In my thoughts, the host language needs to manage context for each abstraction and this task might not be free.

explicit substitution.
I checked simple cases and they were linear. But I feel hard to find the pathological cases. Can someone give me some examples?


texts:
Does every Turing-recognizable undecidable language have a NP-complete subset?

The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an infinite decidable subset.


texts: Applications of HHL's algorithm for solving linear equations

texts: In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a problems which would classically use the solutions of the linear equations?


texts:
Suppose you have a large set of queries (could be in SQL form, but conceivably the same problem exists for search engine query strings or Lucene expressions, etc...) stored and you want to know which of these queries matches a specific object X: is there a general approach to this problem?

Naive implementation would of course be to iterate over all queries, execute them and see if object X is an element of the results found. I expect that a solution would consist of using the indexes that are useful for the operation "query -> results" to perform the "result -> queries" search to find a small superset of the correct set of queries.


texts: Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?

texts:
By BPP/linear I refer to BPP machines with linear advice, which fulfills the promise when given the "correct" advice,
and the derandomization should give us, say, a P/linear or (SUBEXP/linear) algorithm.

If we use non-uniform assumptions, I think classical results should work, because we can "fool" non-uniform adversaries.

However, using uniform assumptions, say $EXP\neq BPP$,  non-trivial derandomization seems like a harder question.

Do there exist results regarding this kind of classes, not necessary BPP/linear?


texts: How are new probabilities computed when simulating measurement on a set of qubits?

texts:
Suppose I have a set of 3 qubits and I have the probabilities for their distribution. This could be arbitrarily entangled or pure:

|000> -> a
|001> -> b
|010> -> c
|011> -> d
|100> -> e
|101> -> f
|110> -> g
|111> -> h

With it holding that a^2 + b^2 ... h^2 = 1.

a) Now suppose I wanted to measure the third qubit. Would it be valid to generally take the probability of the measurement being 0 as a^2 + c^2 + e^2 + g^2?

b) Assume I had measured the third qubit as 0. How would I construct a new probability distribution across my remaining 2 qubits:

|00> -> w
|01> -> x
|10> -> y
|11> -> z

Where w, x, y and z are computed from a, b ... h

Thank you in advance for any guidance you can give me!


texts: What is simplest polynomial algorithm for PLANARITY?

texts:
There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm that one could easily and fast explain in class and would show that PLANARITY is in P. Do you know any?
If necessary, you can use Kuratowski's or Fary's theorem but no deep stuff, like the graph minor theorem.
Also note that I do not care about the running time, I just want something polynomial.
Below are the so far 3 best algorithms, showing a simplicity/no-deep-theory-needed trade-off.

Algorithm 1: Using that we can check whether a graph contains a $K_5$ or a $K_{3,3}$ as a minor in polynomial time, we get a very simple algorithm using deep theory. (Note that this theory already uses graph embeddings, as pointed by Saeed, so this is not a real algorithmic approach, just something simple to tell students who already knew/accepted the graph minor theorem.)
Algorithm 2 [based on someone's answer]: It is easy to see that it is enough to deal with 3-connected graphs. For these, find a face and then apply Tutte's spring theorem.
Algorithm 3 [recommended by Juho]: Demoucron, Malgrange and Pertuiset (DMP) algorithm. Draw a cycle, components of remaining graph are called fragments, we embed them in a suitable way (meanwhile creating new fragments). This approach uses no other theorems.


texts: Regarding proper form of production rules of Context-free tree grammars

texts:
Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?

$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\in L(G_t)\}$

I've tried to do it, using commonly used definition of CFTG (for instance see here), but I failed to express proper context-sensitive rules, using rules of the form $A(x_1,\dots,x_n)\rightarrow\alpha$. Looks like its description power is not enough, as I we can not operate subtrees structure in left side of the rule.

This question induced by well-known obvious relation between Regular Tree Grammars and Context-free word languages.

I would be happy if somebody would build such CFTG or confirm my assumption, that it is simply not possible.

UPD: More specifically, the problem is definition of variables inside rules: $A(x_1,\dots,x_n)\rightarrow\alpha$. It seems to be quite blur, as it is not quite clear: what are these variables? Can we say, that $x_i\in T_{\Sigma\cup X_n}$, where $X_n=\{x_1,\dots,x_n\}$, or not?

If we can describe CFTG rule as: $A(f(x))\rightarrow A_t(a, A(x))$, then problem goes away, it solves the question. But would it satisfy CFTG definition?


texts: Inequality for p-norm of probability distributions

texts:
I want to show the following inequality, which seems like it should have an elementary proof (or even a well-known name).

Suppose $p, q$ are discrete probability distributions. And suppose that $p_i \leq x q_i$ for some $x > 1$. Then I want to show that for $r > 1$ we have the inequality:
$$
\sum p_i^r \leq x^{r-1} \sum q_i^r
$$

If we take away the requirement that $p$ is a probability distribution, then of course we have instead $\sum p_i^r \leq x^r \sum q_i^r$.

EDIT: This is not true. The best inequality one can show is the obvious one $\sum p_i^r \leq x^r \sum q_i^r$.


texts: Decidability of type inference and type checking in MLTT

texts:
In Martin-Löf's An Intuitionistic Theory of Types: Predicative Part it is proved that type checking $a \colon A$ is decidable subject to $a$ being typeable in the first place, by proving a normalization theorem for closed typeable terms.
On the other hand, I've seen it written in multiple places (Wikipedia, Nördstrom etc.) that type-checking in (intensional) MLTT is decidable; are they implicitly restricting to typeable terms?
Is anything known about the decidability of type inference or type checking in intensional MLTT if we do not restrict to the typeable terms?
For instance, perhaps there is a decision process that recognizes untypeable terms, say by normalizing to a form that doesn't correspond to any of the constructors, or by showing that there is no non-periodic sequence of reductions for any untypeable term.

I haven't been able to find very much in the literature.


texts: Is it $NP$-complete to decompose bridgeless cubic bipartite graph into edge-disjoint paths of length 3?

texts:
Motivated by this post on cubic graphs decompositions, I am interested in decomposing a connected bridgeless graph into edge-disjoint paths of length 3 (P4). My intuition is that it should be NP-complete but did not find a reduction.

I am aware that it is $NP$-complete to decide whether a cubic bipartite planar graph is decomposable into vertex-disjoint paths of length 2 (P3).

  Is it $NP$-complete to decide whether a bridgeless cubic bipartite graph is decomposable into edge-disjoint paths of length 3 (P4)?

In a related note, Barnette conjecture states that every 3-connected cubic bipartite planar graph is Hamiltonian. This is equivalent to decomposing every such graph into Hamiltonian cycle and a perfect matching. Feder and Subi proved that if there is a single graph in the class of the conjecture which does not admit such decomposition then deciding the existence of Hamiltonian cycle in $NP$-complete in that class.

  For general connected cubic graph decomposition problems, under which conditions does the existence of a non-decomposable graph imply the $NP$-completeness of the decomposition problem?

EDIT For the second question, Is there a subclass of connected bridgeless cubic graphs where non-decomposable graphs exist but it is polynonial time to decide the existence of a (edge) decomposition?

The linked post on MthOverflow provides some interesting examples of connected cubic graph decomposition problems.

EDIT The problem is posted on MathOverflow: Connection between Barnette conjecture and hardness of cubic graph decomposition


texts: Efficiently approximating derivative of a well-behaved function

texts: I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling range. If it has no minimum in the sampling range it is monotonic. The derivatives of the first and of the second order exist in any point in the sampling range and are continuous as well as the function itself. The algorithm must take the minimum number of points of the objective function and allow computing its derivative in any point in the sampling range with prescribed accuracy (number of precise digits of the derivative). Probably such an algorithm is already developed and well-tested. Please help me to find it. The algorithm is supposed to be implemented in the Wolfram Mathematica system.


texts: W[1]-hard problems with FPT time approximation algorithms

texts:
I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:

R1. W[1]-hard.

R2. Admit a (preferably constant) approximation algorithm in FPT time.

The problem I'm familiar with is counting the number of simple paths of length $k$ in a graph. It is known to be #W[1]-hard, but admits a $(1+\epsilon)$-approximation in FPT time (for any constant $\epsilon$).

Also interesting would be problems that satisfy R1 and R2, and also:

R3. There exists $\epsilon>0$ such that the problem is not $(1+\epsilon)$ approximable in FPT time (unless W[1]=FPT).

  What other problems satisfy R1 and R2, and possibly R3?


texts: Is counting the total number of faces of a polytope $\#P$ hard?

texts:
Let $P$ be a polytope defined by $Ax = b, x \geq 0$.

Question: What is the complexity of computing the total number of faces of $P$?

I know counting vertices is $\# P$-complete, but this problem is potentially different. Does anyone know if it is has been studied before, and where to find the known results?

Motivation: (I think this question is intrinsically interesting, but this "motivation" is just a description of how I came to it.)

As noted here https://math.stackexchange.com/questions/3377451/is-smoothness-required-in-order-for-this-mathbbf-p-point-counting-formula-t , this (appears to be) the number of $\mathbb{F}_2$ points of the corresponding toric variety.

It's plausible to me that this is possible to compute in a fixed parameter tractability kind of way, depending on the description of that toric variety. This hunch is similar to what I was asking about here: https://mathoverflow.net/questions/342756/polynomial-size-embeddings-of-toric-varieties-from-polytopes, where counting $\mathbb{F}_2$ points can be done FPT in the treewidth using the results here https://arxiv.org/pdf/1411.1745.pdf (if I'm interpreting Thm 29 correctly) - provided one could write down equations for the variety and find low dimensional embeddings.

However, it's starting to seem that that approach via finding small embeddings will not be fruitful in general, because there are obstructions to finding polynomial size embeddings. But maybe there are other ways to count the $F_2$ points in a fixed parameter tractable way. It would be interesting, therefore, if this problem was $\# P$ hard.


texts: Most efficient inplace merge algorithms (stable and unstable)

texts:
I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and m, and the goal is to merge it in place into a single sorted array (of size n + m).

I have found this reference (Geffet et al., 2000), but I was wondering if better algorithms were found since then.

I am interested in research in three categories about these algorithms:

stable inplace merge (regardless of the "implementation difficulty" of the algorithm)
unstable inplace merge (regardless of the "implementation difficulty" of the algorithm)
"easily implementable" stable inplace merge

What are the current bests algorithms in these categories?


texts: Deciding whether a 2nfa halts on every input on every branch

texts:
A 2nfa is a nondeterministic finite automaton that can move its head left or right on the input tape, or not.  Is the following language known to be decidable?
$$
\textit{H}_{\mathsf{2nfa}} = \{ \langle M \rangle \mid M \textit{ is a } \mathsf{2nfa} \textit{ that halts on every input and on every branch} \}
$$

Note:
This is not the same as the halting problem on 2nfa's:
$$ \mathit{HALT}_{\mathsf{2nfa}} = \{ \langle M, x \rangle \mid M \textit{ is a } \mathsf{2nfa} \textit{ that halts on every branch, running on } x \} $$
Albeit the two are related, and as follows:
$$ \langle M \rangle \in \textit{H}_{\mathsf{2nfa}} \iff \forall x, \langle M, x \rangle \in \textit{HALT}_{\mathsf{2nfa}} $$

I have attempted to write an algorithm deciding $\textit{H}_{\mathsf{2nfa}}$.  It looks for the sequence of transitions of $M$, that start and end at the same state and the overall displacement of the head along the sequence is $0$.  If there is such a loop, and some further details are satisfied, the algorithm decides that $M$ is not halting.
The problem is that I could not establish any bound on the length of the sequences to look for.  I guess that looking for sequences of length up to some function of $M$'s number of states should be enough.
Is there perhaps another, more elegant way? Even better, a known result to refer?


texts: Given a polynomial of degree $n$, namely, $y=a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$, with $a_i\in \mathbb{R}$,  I would to know if it is possible to compute a rational number $K$ such that the distance between each of the (at most $n$) real roots of the polynomial is $K$.


texts: Computational complexity of learning (classification) algorithms - fitting the parameters

texts:
My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume anything about its distribution (it may be symmetric or very skewed). In statistics, we choose a predictive model and fit its parameters. What is the time complexity of fitting

naive Bayesian classifier
logistic regression
$k$-nearest neighbor classifier
SVM
$\ldots$

I understand that in some cases additional parameters or assumptions about the data (types of variables) are required. These parameters can be of course incorporated in your answer. Thank you very much!


texts: Combination of Disjointness and Gap Hamming Distance communication complexity

texts:
Consider the two player constant-round communication problems:

Gap Hamming Distance $\Delta(a,b)$ where Alice and Bob each has an $n$-length bit string $a$ and $b$ respectively.

YES case: $\Delta(a,b) \geq n/2+\sqrt{n}$.

NO case:  $\Delta(a,b) \leq n/2-\sqrt{n}$.

Known result: Distinguishing between YES and NO requires $\Omega(n)$ bits of communication

Consider $m$ instances of Gap Hamming Distance $a_i,b_i$ for $i=1,2,\ldots,m$. Alice has $a_i$ and Bob has $b_i$. We are promised such that either all $(a_i,b_i)$ are NO instance (Case 1). Or exactly one pair of $(a_i,b_i)$ is a YES instance (Case 2).

Is is true that the communication complexity to distinguish Case 1 and Case 2 of this new problem is $\Omega(mn)$?


texts: A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

texts:
I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence between the MAX-CUT reduction and constructing particular tests for long codes. Because of my own lack of clarity about that equivalence, I struggle to follow this train of thought.

It also seems clear from these expositions that one could describe the reduction purely in terms of graphs, but that by coincidence or preference nobody chooses to do it that way. For example, in these lecture notes of O'Donnell he hints that the long-code test corresponds to a natural definition of the edges in the graph being constructed, but since it's not spelled out that rule seems to depend on the choice of a cut to define the boolean function being tested, and it has left me rather confused.

So I'm asking for someone to explain the reduction "just" graph-theoretically. I think this will help me understand the equivalence between the two viewpoints.


texts:
Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been cited for use in stream algorithms thus far:

$k$-wise independent PRGs like the 4-wise independent family used by Alon/Matias/Szegedy for the original $F_2$ estimation problem, and generalizations for 2-stability-based methods for (say) $\ell_2$ sketching
Nisan's PRG that works in general for any kind of small-space problem.

I'm particular interested in methods that can be implemented. On the face of it, both of the above approaches seem relatively easy to implement, but I'm curious if there are any others out there.


texts:
Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are i.i.d. samples from $\Omega$. It is known that

  Theorem 1. If $\mathcal{F}$ has finite VC-dimension $d$,
  $$
\mathbb{P}\left(\sup_{f \in \mathcal{F}} |P_n(f) - P(f)| \leq \sqrt{\frac{8}{n} \left(\log(\frac{4}{\delta}) + d\log(\frac{ne}{d})\right)}\right) \geq 1 - \delta
$$

The following bound based on the Rademacher complexity of $\mathcal{F}$, denoted $\mathcal{R}_n(\mathcal{F})$, is also known.

  Theorem 2. $$
\mathbb{P}\left(\sup_{f \in \mathcal{F}} |P_n(f) - P(f)| \leq 2\mathcal{R}_n(\mathcal{F}) + \sqrt{\frac{1}{2n} \log (\frac{2}{\delta})}\right) \geq 1- \delta
$$

Are there other bounds on $\sup_{f\in \mathcal{F}}|P_n(f) - P(f)|$ tighter than the ones above?


texts: Detect highly weighted but also densely inter-connected subnetworks

texts: In a connected / undirected / node weighted (with both positive and negative weights) network, there are many papers studied about the 'Maximum weight connected subgraph' problem. But are there any algorithms (even heuristic) to find highly weighted (not necessarily maximum) subnetworks that are densely inter-connected?


texts: Constrained version of vertex cover in a bipartite graph

texts:
Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if there is a vertex cover $A\cup B$ with $|A|\leq l$
and $|B|\leq k$,  where $A\subseteq V_1, B \subseteq V_2.$

Now, I have following two questions:

1) What is the complexity of the above problem when both $k$ and $l$ are part of input. (Intuitively, it appears to be hard.) If it is hard, then is there any PTAS known to approximate the problem.

2) What is the complexity of the problem when one of the parameters $k$ or $l$ is constant?

Pls let me know if there is any doubt about the problem.


texts: Journals or conferences to submit formally verified libraries?

texts:
This is a soft question aimed at understanding whether there is any value to publishing formally verified libraries. I have formally verified (in Coq) implementations of:

synthetic differential geometry
Chains of recurrences

Are these of interest in terms of publication anywhere? what is the bar for "what can be formally verified and published"? Are these even "put on on Arxiv" worthy? In general, what's the boundary that separates "routine proof" from "publishable proof"?

Thanks a lot!


texts: Do there exists reversible gate sets of intermediate growth?

texts:
Suppose that $f_{1},...,f_{k}:\{0,1\}^{r}\rightarrow\{0,1\}^{r}$ are bijective functions.

For all $n\geq r$, let $G_{f_{1},...,f_{k};r}=\subseteq S(\{0,1\}^{n})$ be the subgroup generated by

i. the functions $f_{i}\times Id_{n-r}$ where $Id_{n-r}:\{0,1\}^{n-r}\rightarrow\{0,1\}^{n-r}$ is the indetity function, and

ii. the mappings $\pi_{\sigma}$ for permutations $\sigma\in S_{n}$ where $\pi_{\sigma}(x_{1},...,x_{n})=(x_{\sigma(1)},...,x_{\sigma(n)})$.

Let $t_{f_{1},...,f_{k};n}$ be the largest natural number $m$ such that the symmetry group $S_{m}$ embeds in the group $G_{f_{1},...,f_{k};r}$. We say that $(f_{1},...,f_{k})$ is of exponential growth if there is some $\alpha>1$ and $c>0$ where
$t_{f_{1},...,f_{k};n}>c\cdot\alpha^{n}$ for all $n\geq r$. We say that $(f_{1},...,f_{k})$ is of polynomial growth if there is some polynomial $p$ where $t_{f_{1},...,f_{k};n}<p(n)$ for all $n\geq r$. We say that $(f_{1},...,f_{k})$ is of intermediate growth if it is not of polynomial nor exponential growth. Does there exist a collection of bijective functions $(f_{1},...,f_{k})$ of intermediate growth?


texts: Complexity of the coset intersection problem

texts:
Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold?

As far as I know, the problem is known as the coset intersection problem. I am wondering what's the complexity? In particular, is this problem known to be in coAM?

Moreover, if $H$ is restricted to be abelian, what does the complexity become?


texts:
I don't think I understand type classes. I'd read somewhere that thinking of type classes as "interfaces" (from OO) that a type implements is wrong and misleading.
The problem is, I'm having a problem seeing them as something different and how that is wrong.

For example, if I have a type class (in Haskell syntax)

class Functor f where
  fmap :: (a -> b) -> f a -> f b

How is that different than the interface [1] (in Java syntax)

interface Functor<A> {
  <B> Functor<B> fmap(Function<B, A> fn)
}

interface Function<Return, Argument> {
  Return apply(Argument arg);
}

One possible difference I can think of is that the type class implementation used at a certain invocation is not specified but rather determined from the environment -- say, examining available modules for an implementation for this type. That seems to be an implementation artifact that could be addressed in an OO language; like the compiler (or runtime) could scan for a wrapper/extender/monkey-patcher that exposes the necessary interface on the type.

What am I missing?

[1] Note the f a argument has been removed from fmap since given it's an OO language, you'd be calling this method on an object. This interface assumes the f a argument has been fixed.


texts:
I have a large collection of microscopy images of cell cultures.  Each image consists of $10^{10} \times 10^{10}$ pixels.  These images have been "segmented", meaning that their pixels have been partitioned into disjoint sets (aka regions) corresponding either to the background or to individual cells.  I'm looking for a reasonably efficient algorithm to assign "colors" to these regions so that no two adjacent regions have the same color, and the number of colors used is "small".

In principle, 4 colors should do, but the problem of finding a 4-coloring for a partition of a plane region into disjoint subregions is NP-hard.

Nevertheless, this statement (and the 4-color problem in general) applies to a more general situation (e.g. arbitrarily complex shapes) than the one I am dealing with, so I'm alert to the possibility that some features of this special case may make the problem reasonably tractable in practice.

First, typically most of the cell regions are in fact isolated (i.e. they are surrounded entirely by background), so the problem of assigning a color to them is trivial.  Second, even when there are adjacent cell regions, these regions have relatively "well-behaved" shapes: they are basically roundish blobs, with no weird curlicues, etc.  In fact, any two pixels in a cell region are connected by a taxicab-path consisting of pixels all belonging to the region.  (By taxicab-path I mean one in which the Manhattan distance between adjacent pixels is always 1; i.e. each step along the path is either vertical or horizontal.)  Also, there is some leeway on the exact boundary of these regions, so it may be acceptable to modify the segmentation algorithm in such a way that the resulting regions are more easily colorable.

I have not found any prior work on coloring that attempts to exploit the features described above, so I thought I'd ask here.

It may very well be that these features of my special case do not result in any simplification of the 4-coloring problem, in which case an algorithm that can efficiently produce a 5-coloring, or even a 6-coloring, would be adequate.

Thanks in advance for your suggestions,

kj


texts: Does coNP-complete problem have subexponential size certificate?

texts: Assuming NP != coNP, then there is no polynomial size certificate for coNP-complete problem. But what about subexponential size certificate? Particularly for coSAT, is there subexponential size proof to prove a formula is unsatisfiable? If not, what is the negative evidence? Thanks