texts:
According to this Wikipage series-parallel graphs are characterized like this:

2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to $K_4$.

I couldn't find a similar characterization for series-parallel directed acyclic graphs (DAGs), however I think that the prohibited subgraph in this case can be a little simpler ($K_4$ minus one edge plus specific orientation):

Is it correct? Is it proven anywhere?


texts: How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?

texts:
In "Real Time Queue Operations in Pure LISP" (ML implementation), Hood and Melville show an $O(1)$ worst-case simulation of a queue using 6 stacks and global rebuilding. Can a real-time queue be simulated with fewer stacks?

In "Simple and Efficient Purely Functional Queues and Deques", Okasaki shows an implementation using one stack and two lazy stacks.

Both Okasaki's and Hood & Melville's queues require purely functional stacks as building blocks, and both produce purely functional queues. If push and pop are destructive, can global rebuilding be used to simulate an ephemeral queue with 6 ephemeral stacks? Fewer?


texts: Modifying Hopcroft-Karp algorithm to get approximate bipartite matching

texts:
I am trying to find an algorithm to find an $\epsilon$-approximate maximum matching $M_{\epsilon}$ in a bipartite graph in $O(m/\epsilon)$. The partite groups are of equal size, they are $A$ and $B$.  So the graph is:

$$G(A ∪ B, E)\ \ where\ \  |A| = |B| = n, \ \ \ \ E ⊆ A × B \  \ \ and\ \ \  |E| = m$$

The algorithm should produce an $\epsilon$-approximate maximum matching $M_{\epsilon}$ such that:

$$|M_{\epsilon}| \geq (1-\epsilon)M_{optimal} \ \ \ for\ \ \ 0 \leq \epsilon \leq 1$$

I am aware that the Hopcroft-Karp algorithm can produce an $M_{optimal}$ but I have heard one can modify Hopcroft-Karp to produce an $\epsilon$-approximate maximum matching ($M_{\epsilon}$) instead.  I am currently out of ideas in how to approach this.

To clarify: I am only concerned about unweighted matchings.


texts: What information can a program give about the Kolmogorov Complexity of its accepting Language

texts:
Suppose we have a program(algorithm) that solves some decision problem $(\Sigma,L)$.

Given the program, can we always say something about the Kolmogorov complexity of the words in $L$ ?


texts: Why is linearizability a safety property and why are safety properties closed sets?

texts:
In Chapter 13 "Atomic Objects" of the book "Distributed Algorithms" by Nancy Lynch, linearizability (also known as atomicity) is proved to be a safety property. That is to say, its corresponding trace property is nonempty, prefix-closed, and limit-closed, as defined in Section 8.5.3. Informally, a safety property is often interpreted as saying that some particular "bad" thing never happens.

Based on this, my first problem is as follows:

  What are the advantages of linearizability as a safety property? Are there some results based on this fact in the literature?

In the study of the classification of safety property and liveness property, it is well-known that safety property can be characterized as the closed set in an appropriate topology. In the paper "The Safety-Progress Classification" @1993 by Amir Pnueli et al., a metric topology is adopted. More specifically, a property $\Phi$ is a set of (finite or infinite) words over the alphabet $\Sigma$. The property $A(\Phi)$ consists of all infinite words $\sigma$ such that all prefixes of $\sigma$ belong to $\Phi$. For example, if $\Phi = a^{+}b^{\ast}$, then $A(\Phi) = a^{\omega} + a^{+}b^{\omega}$. An infinitary property $\Pi$ is defined to be a safety property if $\Pi = A(\Phi)$ for some finitary property $\Phi$. The metric $d(\sigma, \sigma')$ between infinite words $\sigma$ and $\sigma'$ is defined to be 0 if they are identical, and $d(\sigma, \sigma') = 2^{-j}$ otherwise, where $j$ is the length of the longest common prefix on which they agree. With this metric, the safety property can be characterized as closed sets topologically.

Here comes my second problem:

  How to characterize linearizablity as closed sets topologically? In particular, what is the underlying set and what is the topology?


texts: Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

texts:
I believe the answer to this question is well-known; but, unfortunately, I don't know.

In quantum computing, we know that mixed states are represented by density matrices. And the trace norm of the difference of two density matrices characterizes the distinguishability of the two corresponding mixed states. Here, the definition of trace norm is the sum of all eigenvalues of the density matrix, with an extra multiplicative factor 1/2 (in accordance with statistical difference of two distributions). It is well-known that, when the the difference of two density matrices is one, then the corresponding two mixed states are totally distinguishable, while when the difference is zero, the two mixed states are totally indistinguishable.

My question is, does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable? If this is the case, then taking the optimal measurement to distinguish these two mixed states will behave like to distinguish two distributions over the same domain with disjoint support.


texts: Abstract machine or algorithm for line solving a Nonogram

texts:
I am currently working on a little project where I would like to write an efficient solver for three-dimensional Nonograms.

http://en.wikipedia.org/wiki/Nonogram

So I wanted to ask whether anybody of you know a good way on how to solve a line in a normal 2D Nonogram. The problem is NP-complete btw so finding a robust algorithm that always does it will be quite hard ;-)

But does anybody of you have an idea? It doesn't need to solve everything possible but should do basic checks on a line and see if it can fill out something.

Would be  great if anybody could give me tips on how I could achieve this... thanks!


texts: Grover's algorithm, M out of N, when M is large

texts:
The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries.

I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to find one of the $M$ matching entries, with good probability.
(e.g. on wikipedia )

Is this still valid when $M$ is large, say $M=N/2$ ?  In that case we get $O(1)$ iterations?


texts: Efficient algorithm for existence of permutation with differences sequence?

texts:
This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations.

A differences sequence $a_1, a_2, \ldots a_n$  of a permutation $\pi$ of numbers $1, 2, \ldots n+1$ is formed by finding the difference between every two adjacent numbers in the permutation $\pi$. In other words, $a_i= |\pi(i+1)-\pi(i)|$ for $1 \le i \le n$

For example, sequence $1, 1, 3$  is the differences sequence of permutation $2 3 4 1$.  While, sequences $2, 2, 3$ and $ 3, 1, 2$ are not the differences sequence of any permutation of numbers $1, 2, 3, 4$.

  Is there an efficient algorithm to determine whether a given sequence is the differences sequence for some permutation $\pi$, or is it NP-hard?

EDIT: We get computationally equivalent problem if we formulate the problem using circular permutations.

EDIT2: Cross posted on MathOverflow, How hard is reconstructing a permutation from its differences sequence?

EDIT3 Awarded the bounty to the proof sketch and I would accept the answer after getting the complete formal proof.

EDIT 4: Marzio's nice $NP$-completeness proof has been published in the Electronic Journal of Combinatorics.


texts:
I have a DAG like this

$G_1 = \lbrace A \to B \to C \rbrace$

My algorithm modify $G_1$ so it will be like this

$ G_2 = \lbrace A \to C, B \to C \rbrace $

I now that $G_2$ is not a transitive reduction of $G_1$. How it is called this operation?

Thanks in advance

EDIT: basically, $G_2$ contains the edge $(a, b)$ of $G_1$ if and only if $b$ is a sink node and exist a path between $a$ and $b$.


texts: Particle collisions for universal computation

texts:
Proof of universality of Game of Life is straightforward  (CAFAQ):

  (two annihilating glider streams with gaps (ie. 0s) are colliding, one is "data" and the second is all glider filled, ie.: 111111...)
  For every 0 in the input
  byte, the missing glider in the input stream allows a glider from the
  glider gun to pass, whereas for every 1 in the input byte, a glider in
  the input stream annihilates the corresponding glider coming from the
  glider gun. Thus, looking at the output stream from the glider-gun
  DOWNSTREAM of the collision site, there is a glider (a 1) for every
  "hole" in the input stream (a 0) and there is a hole (a 0) for every
  glider (1) in the input stream. Thus, the filtered output of the
  glider-gun is the logical NOT of the encoded input stream.

  And not a universal computer in sight!

  By colliding this output stream (call it NOT A if the input steam is
  A) with another input stream, B, one gets A AND B in the continuation
  of the input stream B after the collision site.

So what is sufficient for universality is a particle $\alpha$ such that after collision with itself complete annihilation occurs $\alpha + \alpha = 0$. This seems to be an easy requirement. However, ECA 110 (or Rule 110) was proved via simulating cyclic tag system. And ECA 54 was not yet proven to be universal.

Both ECA 110 and ECA 54 have rich glider/particle sets. I did not yet dig deep into the glider sets. I first want to ask:

Was the contrast between simplicity of $\alpha + \alpha = 0$ and problems with proving universality of ECA examined somehow? Are the particle systems categorized in some way, to explain why rich particle systems are not necessary universal, while system as simple as $\alpha + \alpha = 0$ can be universal?


texts: Proof of Nullstellensatz certificate degree

texts:
Discalimer:

The approach below may be usefull to prove P=NP. I would understand down-voting.

Many NP-complete problems can be encoded in the system of polynomial equations. Some examples are in the introduction here. Basically the idea is to encode binary variables in the equations $f_k= x_k^2-1= 0$, or $f_k = x_k^2-x_k=0$, and add one or more equations ($g_k=0 $) encoding satisfiability problem. Since the system can have exponentially many solutions finding them is hard. On the other hand, we can try to figure out if the system has solutions at all. One of the approaches is to use Nulstellensatz certificate, e.g. find the set of polynomials $P_k, P'_k  \in \mathbb{K}[x_1,...x_n]$, where $\mathbb{K} $ is an algebraically closed field, for example $\mathbb{C} $ such that the following equation is satisfied $1= \sum_k P_k f_k +\sum_m P'_m g_m$. The problem with this approach is that one need very high degree polynomials $P_k, P'_k $ and the certificate has exponentially many monomials. The intuition here is following. The problem is hard since all variables are influencing other variables, otherwise the problem can be split into independent subproblems. Since all of them are important the term with monomial $x_1 ... x_n$ has to appear in the certificate. That lead to the certificate of degree $n$, which has too many monomials.There is no clear way of selecting right monomials, and we need to use all of them. So the problem is that by increasing the degree of certificate the "mixing" of variables is too slow - we introduce too much noise - too many problem irrelevant tautologies!!! And we need a way to speed-up mixing of the variables.

We do usual trick of linearizing quadratic equations in terms of quadratic monomials (for 3-SAT we need cubic monomials), e.g. $y_{x_k,x_m}= x_k x_m,\ k, m = 0..n,\ x_0=1 $. This linear system has $\approx n^2$ linear variables (monomials), and $\approx n$ equations, e.g. highly under-complete. The solution of this (homogenised) linear system is $\approx n^2 $ dimensional projective space. The original system has a solution iff there is a point $c \in \mathbb{C}^{\approx n^2}$ in this projective space such that all corresponding equations on $y_{x_k,x_m} = y_{x_0,x_k} y_{x_0, x_m}, y_{0,0}=1$  are satisfied. These are quadratic equations on $c$, so we can write all the quadratic in $c$ constraints $y_{x_k,x_m} y_{x_p,x_q}= y_{x_k,x_p} y_{x_m,x_q}= y_{x_k,x_q} y_{x_p,x_m}$ (tautologies). Therefore, we have $\approx \frac{2}{3} n^4 $ quadratic equations with $\approx n^2 $ indeterminates $c_k$. Now we have equivalent, in terms of satisfiability, system of quadratic equations with $O(n^4)$ equations and $O(n^2)$ variables $c_k$, In other words, now we have $O(1)$ equations in terms of the number of quadratic in monomials, and the system is almost complete.

Now we can write Nulstellensatz certificate for the new system of tautologies in terms of $c_k$.

Q1. Does anyone see a simple way of proving fixed certificate degree for the new "almost complete" system?

Any relevant references are appreciated.


texts: What are some examples of secret sharing schemes actually being used in real-world applications?

texts:
The concept of a secret sharing scheme is often attributed to Shamir (A. Shamir, How to share a secret, Comm. ACM, 22 (1979), pp. 612-613.) and Blakey (G. R. Blakey, Safeguarding cryptographic keys, in Proc. NCC, vol. 48, 1979, pp. 313-317.).

The overall idea is that some secret S is hidden from the participants who instead each receive a share si.  If every participant decides to cooperate, they each submit their share to a combiner, who reconstructs S from the shares si.

Papers on secret sharing schemes often refer to real-world applications (such as bank safes).  But I suspect, these are hypothetical "real-world" applications (i.e. the next floor down in the ivory tower) and very much doubt that they could actually name a bank (or any other company) that actually uses a secret sharing scheme.  Question:  What are some actual real-world examples?

Ideally, I would like an answer to contain:  At company X they use secret sharing scheme Y to safeguard Z (see ABC for more details).


texts: What is the complexity of this weighted b-edge matching problem?

texts:
I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:

Input: An undirected multigraph $G = (V, E)$ without
loops, an edge partition $(E_1,E_2)$ such that $E_1 \cup E_2 = E$, capacity functions $b_l , b_u : V \to \mathbb{N}_0$,
a weight function $w : E \to  \mathbb{N}_0$ and target integers $r_1,r_2$.

Question: Are there subsets of edges $E_1' \subseteq E_1$ and $E_2' \subseteq E_2$ such that

$\sum_{e\in E_1'} w(e) \geq r_1$ and $\sum_{e\in E_2'} w(e) \geq r_2$; and
$b_l (v) \leq | (E_1' \cup E_2') \cap \delta (v)| \leq b_u(v)$ holds for each vertex $v \in V$ ($\delta (v)$ is the set of edges incident to vertex $v$)?

Is this problem solvable in polynomial-time or NP-hard?

Without the edge partition we have the standard problem which is solvable in
polynomial-time (see Gabow [1] or Anstee [2]). This variant seems to be similar to
the Directed Two-Commodity Integral Flow problem which is NP-hard but I couldn't figure out a reduction to this variant.

[1] Gabow, H. N.   1983.   An efficient reduction technique for degree-constrained subgraph and  bidirected  network  flow problems.  In Proceedings of the fifteenth annual ACM symposium on Theory of computing, 448–456.

[2] Anstee, Richard P. "A polynomial algorithm for b-matchings: an alternative approach." Information Processing Letters 24.3 (1987): 153-157.


texts: Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

texts:
Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties:

The size of $\psi$ is polynomial in $|\phi|$
$\psi$ has an odd number of satisfying assignments if and only if $\phi$ has an odd number of satisfying assignments
The number of satisfying assignments of $\psi$ is polynomial in $|\psi|$.

Unless I'm wrong, that would mean that having a $\mathbf{NP}$ oracle allowed to formulate polynomially many queries would somehow be equivalent in power to having a $\oplus \mathbf{P}$ oracle.

Question
What would be the consequences of the existence of such reduction? Which surprising collapses would happen, if any? Would any widely believed conjecture be disproven?


texts: Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space

texts:
A dynamic predecessor data structure supporting findPredecessor, insert, and delete over unique ordered keys in an unbounded universe in $O(\lg n)$ worst-case time can be stored contiguously using only $O(1)$ extra words of storage in addition to the storage for the keys themselves:

"Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees", Franceschini and Grossi

The structure is complex (IMHO).

Storing $n$ keys in an array that can grow dynamically requires at space for at least $\Theta(\sqrt{n})$ additional keys:

"Resizable Arrays in Optimal Time and Space", Brodnik et al.

Given the latter constraint, is there a simpler dynamic predecessor data structure that uses contiguous space for $n + O(\sqrt{n})$ keys?

There were many implicit ($O(1)$ extra words) dynamic predecessor data structures that predate the result of Franceschini and Grossi:

"Implicit Data Structures for the Dictionary Problem", Frederickson

"Searchability in merging and implicit data structures", Munro and Poblete (does not support delete)

"Developing Implicit Data Structures", Munro

I'm wondering if it is possible to simplify even these structures by using $\Theta(\sqrt{n})$ extra space. I am hoping to find a structure supporting all three operations in $o(n^\varepsilon)$ time.


texts: Bound on the number of hidden nodes for multilayer perceptron with a single hidden layer

texts:
The universal approximation theorem states that:

Let $\phi(·)$ be a nonconstant, bounded, and monotonically-increasing continuous function. Let $I_m$ denote the m-dimensional unit hypercube $[0,1]^m$. The space of continuous functions on $I_m$ is denoted by $C(I_m)$. Then, given any function $f ∈ C(I_m)$ and $\epsilon > 0$, there exist an integer $N$ and real constants $\alpha_i,b_i \in \Re$, $w_i ∈ \Re^m$, where $i = 1, \dots , N$ such that we may define:

$$
    F( x ) = \sum_{i=1}^{N} \alpha_i \phi \left( w_i^T x + b_i\right)
$$

as an approximate realization of the function f where f is independent of $\phi$; that is,

$$
    | F( x ) - f ( x ) | < \epsilon
$$

for all $x \in I_m$. In other words, functions of the form $F(x)$ are dense in $C(I_m)$.

Is there a bound on $\epsilon$ in terms of $N$?


texts: Time complexity for multiplying two lower triangular matrices

texts:
I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
 A & 0\\
 C & D
\end{bmatrix}
\begin{bmatrix}
 P & 0\\
 R & S
\end{bmatrix}
=
\begin{bmatrix}
 AP & 0\\
 CP + DR & DS
\end{bmatrix}
$$
Initially, I thought the above block decomposition yields an $O(n^2)$ time algorithm since there are 4 recursive instances of multiplication of $n/2 \times n/2$ matrices. However, I quickly realized that we cannot recurse since the lower left blocks are not triangular ($C$ and $R$ above).


texts: The number of edges in the ith shortest path in a directed graph

texts:
$G$ - directed graph,
$n$ - count of nodes

According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges.

Anybody can explain how this estimate is taken?


texts: Advice for Graduate School in Computer Science

texts:
I am looking for some advice and feedback.

Background: I am an undergraduate mathematics student, with an interest in theoretical computer science (computational complexity, graph theory, combinatorics). I want to pursue a PhD in Computer Science and focus on theory.

My background is in mathematically intensive areas of computer science, but I lack a more applied background in computer science. Specifically I need to complete courses in Programming, Algorithms, Operating Systems, & Databases as prerequisite work for a PhD program. I cannot fit these courses in before graduation. To remedy this I plan to enter the work force and complete a MS part time (so I can pay for the MS), then upon completion of the MS degree enter a full time PhD program.

Question: Would I be at a disadvantage by completing a MS degree part time, prior to entering a PhD program, as opposed to CS students that enter a PhD program immediately upon the completion of their undergraduate degree? The position I work in would be related to CS and would give me transferable skills to a CS program & may help lead me to better focused research. I am just hoping this path does not put me at any kind of disadvantage (in terms of acceptance to a PhD program). I am interested in doing the MS thesis track, and realize that it may take me a little longer to complete the MS degree (since it would be part time). Upon completion of the MS, as stated, I would enter a full time PhD program.

I am just looking for some feedback and advice. Thanks for your help!


texts: Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges

texts:
Let $G( n, m )$ be the set of all possible connected graphs of $n$ nodes and $m$ edges such that, for each $g_1 \in G( n, m )$, $g_2 \in G( n, m )$, if $g_1 \neq g_2$ then $g_1$ and $g_2$ are non-isomorphic.

  Question

  How large can $|G( n, m )|$ be? Is it polynomial in both $n$ and $m$? Or is it superpolynomial in either $n$ or $m$?


texts: Is there an equivalent to VC-dimension for density estimation as opposed to classification?

texts:
VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute the capacity of a mixture of N Gaussians, etc?  And if so, are there corresponding theorems showing that this capacity-measure can be used to bound the generalization error for density estimation, or used for structural risk minimization (analogous to the classification setting)?
I did find this article which seems like it might come pretty close to answering my question, since they apply structural risk minimization (SRM) to gaussian mixture models, and it looks like they estimate the capacity using "annealed entropy" applied to a class of threshold-based indicator functions associated with the log-likelihood function. However, they don't provide references to theorems/bounds to show whether this is a principled way to assess the capacity of a probability density, but perhaps there is some known theorem that justifies this approach which they assume the reader already knows about?  They reference Vapnik's book for more details on annealed entropy.
Also, my understanding is that fat-shattering or pseudo-dimension can be used as a generalization of VC-dimension to the regression context, but I'm unclear whether these are applicable to density estimation.  And it looks like the paper linked above used annealed entropy rather than these regression-based capacity measures.


texts: VNP = VP versus complexity classes in Arithmetic Geometry

texts:
What is the implication of $VNP = VP$ to cryptography schemes such as Elliptic curve/Abelian Variety/Arithmetic Geometry based cryptography? Are there any papers or books that talk about sophisticated encryption techniques and the possible complexity classes they belong to?

There seems to be a negative implication for RSA if $VNP = VP$. On the other hand no OWF should exist if $VNP = VP$. However relatively nothing is known about frailty of candidate OWF from Arithmetic Geometry if $VNP = VP$. Will these be safe?


texts: Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones

texts:
We have a sorted list of $n$ numbers and we shall create a BST for these numbers.
We create a random sequence of zeroes and ones of length $n$.
We shall make use of this random binary sequence to form a BST in the following way.
Let's illustrate using an example.
Suppose we have the input to be  $[a,b,c,d,e]$
& the random binary sequence is $[1,0,0,1,0]$
Then we form the tree in the following way.
Since $a$'s random bit is 1, its successor will be below it in the BST.
Since $b$'s random bit is 0, its successor will be above it in the BST.
and so on...

The random bit of the last value $e$, does not matter because it has no successor.
Which gives us the BST as follows
$d$ is root, its left child is $c$ and right child is $e$.
$c$ has a left child $a$ and $a$ has right child to be $b$.
This seems to be random, but I am not convinced.
A random BST should have height to be $O(\lg n)$.
But the random binary sequence will have roughly $O(n)$ zeroes and $O(n)$ ones with high probability.
Everytime we encounter a zero, the successor of a node lies above the node and so if on average there $O(n)$ zeroes, the height of the tree on average is also $O(n)$.
What is the correct answer?
Does this strategy create a random tree or not?


texts: How to use a -coin so a TM can decide an undecidable language in polynomial time?

texts:
In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm a new power. Then he  states: "The exercises show that if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power."

Lemma 7.12: A coin with Pr[Heads] = ρ can be simulated by a PTM in expected time O(1) provided the ith bit of ρ is computable in poly(i) time.

The exercise that supposed to show, if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power is the following:

Exercise: Describe a real number ρ such that given a random coin that comes up “Heads” with probability ρ, a Turing machine can decide an undecidable language in polynomial time.

Now, how can we show that if ρ is not efficiently computable, then a ρ-coin can indeed provide an additional power for a probabilistic algorithm to decide some undeniable language in polynomial time?

*I removed the hint because it made me more confused but you can find it at the end of the book.

I strongly believe that this is a research level problem and proper to be discussed in theoretical computer science society because this is a high level question about computational complexity and this question has not been discussed anywhere else.


texts: Examples of nontrivial non-discriminatory functions

texts:
I am reading Cybenko's "Approximation by Superpositions of a Sigmoidal Function".
The paper defines a discriminatory function as:

$\sigma$ is discriminatory if for a measure $\mu$,
\begin{align}
\int \sigma (y^\top x + \theta) d \mu(x) = 0
\end{align}
for all $y \in R^n$ and $\theta \in R$, then $\mu=0$.

What is an example (with proof) of a non-discriminatory function? (besides 0)


texts: Some problems about arrow's theorem and social choice

texts:
I'm just started lecture myself about arrow's theorem. There are some problems which make me confused.

ARROW'S THEOREM: Any constitution that respects transitivity, independence of irrelevant alternatives, and unanimity is a dictatorship.

This is a kind of statement from john Geanakoplos' paper.

I think unanimity+transitivity and independence of irrelevant alternatives are equivalent. For example:

voter A: a>b>c>d
voter B: a>c>b>d
voter C: a>d>c>b

So we can conclude that everybody prefers a to b just according to unanimity and transitivity. And I think this conclusion implies independence of irrelevant alternatives. So if I drop the constraint of independence of irrelevant alternatives, Is this still right?


texts: Comparison-based data structure for finding items

texts:
Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$?

I really think there isn't, so a proof that there is none is also welcomed.


texts: Church-Rosser property for dependently typed lambda calculus?

texts:
It is well-known that the Church-Rosser property holds for $\beta \eta$-reduction in simply-typed lambda calculus. This implies that the calculus is consistent, in the sense that not all equations involving $\lambda$-terms are derivable: for example, K$\neq$I, since they don't share the same normal form.

It is also known that one can extend the result to pairs which correspond to product types.

But I wonder if one can further extend the result for dependently typed lambda calculus (perhaps) with polymorphic types, e.g. the Calculus of Constructions?

Any references would also be great!

Thanks


texts: Do Higher-Order Functions provide more power to Functional Programming?

texts:
My original question was: Is Kappa calculus less powerful than Lambda calculus?

Does the lack of Higher-Order functions on a programming language excludes some programs that could only be written in functional programming (and therefore in a turing machine)?

By "powerful" I mean a Turing Complete programming language. For example, a language that can not contain infinite recursive expressions, ie infinite recursion or an infinite while loop, is not as powerful as Lambda-Calculus and Turiung Machines, since it would otherwise be a contradiction to the Halting Problem.

I can't find the reference right now, byt I remember something about an algorithm that on a non-lazy functional programming language has an $\Omega( n \log n )$ complexity, while the same algorithm in imperative programming is $\Omega( n )$


texts: Is there an ambiguity test for CFGs faster than trying all strings?

texts:
It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in \mathbb{N}$ contains any strings that have more than one derivation wrt $G$: just parse all these strings with some general parsing algorithm and check if any of them have more than one derivation. However, this approach has a running time of $\Omega(2^n)$.

  Can we decide whether $L_n(G)$ contains any strings that have more than one derivation wrt $G$ in $poly(n)$?

The application of such a fast algorithm would be that one could run the algorithm on your grammar for a while, after which you can be fairly confident that your grammar is unambiguous: most grammars in practice, if they are ambiguous, have a relatively short string that exhibits this ambiguity, so one expects the algorithm to find it quickly.

I know that there has been quite a bit of work on ambiguity tests, but as far as I know most of these tests aim to approximate the ambiguity of a grammar (so it can misclassify grammars) rather than to exactly determine grammar ambiguity. The other approach I know of is fuzzers (test lots of random sentences on ambiguity).

The above question arose when I observed that a certain noncanonical LR algorithm could be used to solve the above problem as a side effect (though I have no idea what its running time would be if used for this purpose).


texts: Fixed point theorems for constructive metric spaces?

texts:
Banach's fixed point theorem says that if we have a nonempty complete metric space $A$, then any uniformly contractive function $f : A \to A$ it has a unique fixed point $\mu(f)$. However, the proof of this theorem requires the axiom of choice -- we need to choose an arbitrary element $a \in A$ to start iterating $f$ from, to get the Cauchy sequence $a, f(a), f^2(a), f^3(a), \ldots$.

How are fixed point theorems stated in constructive analysis?
Also, are there any concise references to constructive metric spaces?

The reason I ask is that I want to construct a model of System F in which the types additionally carry metric structure (among other things). It's rather useful that in constructive set theory, we can cook up a family of sets $U$, such that $U$ is closed under products, exponentials, and $U$-indexed families, which makes it easy to give a model of System F.

It would be very nice if I could cook up a similar family of constructive ultrametric spaces. But since adding choice to constructive set theory makes it classical, obviously I need to be more careful about fixed point theorems, and probably other stuff too.


texts: Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?

texts: Since both proofs make use of the diagonal argument, I’m wondering whether there is an obscure link between the existence of uncountable infinite sets and the undecidability of the halting problem. Would the halting problem be decidable if all sets were countable?


texts: How to charactorize computational complexity based on finding solution to algebraic equations?

texts: The Matiyasevich/MRDP Theorem relates two notions:one from computability theory, the other from number theory, thus Turing Machine and algorithms finding integral solution to algebraic equations can be regarded as equal. Therefore, the hardness for finding integral solution to algebraic equations and computational complexity are related, we can charactorize computational complexity based on finding solution to algebraic equations, any reference for this idea?


texts: The simple proof of uniqueness of solution for The tower of Hanoi problem

texts:
The problem of Tower of Hanoi is a typical example of recursion method.
Could anyone show me the (simple) proof of

(1) the smallest number of moves of the solution is 2^n-1

(2) the uniqeness of the optimal solution (the solution with the smallest number of moves)

(I found (1) in the Concrete Math of Knuth, is there any other proof ?)


texts: Basic property of boolean functions with restrictions

texts:
For $f:\{\pm1\}^n\to\mathbb{R}$, $I\subset\{1,\dots,n\}$ and $x\in\{\pm1\}^{\{1,\dots,n\}\setminus I}$ we define $f_I[x]:\{\pm1\}^I\to\mathbb{R}$ by $f_I[x](y)=f(x,y)$. (We denote by ($x,y$) the assignment to all $n$ variables given by $x$ and $y$.)

Let $S\subseteq I$. I have proved that $\mathbb{E}_x\left[\widehat{f_I[x]}(S)\right]=\widehat{f}(S)$, where $\widehat{f}(S)$ is the Fourier coefficient of $f$ corresponding to $S$. Now I want to show (possibly using the first result) that
$$\mathbb{E}_x\left[\widehat{f_I[x]}^2(S)\right]=\sum\limits_{T:T\cap I=S}\widehat{f}^2(T).$$

Any useful ideas would be greatly appreciated.


texts: Fundamental assumptions in complexity analysis

texts:
I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as RAM. The assumption is that the primary storage  already has the capacity to store and address the input, so it should be feasible to expect rapid performance on the words that encode the address space. This is reasonable, yet I think that the model may give equal footing to algorithms that perform inherently different amounts of work - such as returning a constant and mapping numbers (the latter is obviously more demanding in a non-Neumann architecture). Similarly, on a tangent topic, the development of parallel algorithms assumes infinitely parallel hardware, which does not take into account the spatial factors involved in a circuit design.

Furthermore, while contemporary machines provide integer-based addressing and while I see this as an arbitrary beneficial phenomenon, I don't think that there is fundamental need for our addresses to be effective quantities, with the corresponding constant-time arithmetic operations on them. So this may also influence the analysis of algorithms towards disbalance.

In view of the above, I have the following questions:

Are there operations, to our understanding, that we expect to be implemented efficiently in our fully featured (i.e. for practical evaluation) models of computation and why - arithmetic, or any polylogarithmic complexity operation (assuming the standard encodings), or any function that maps words, even finding the n-th prime number if it fits in a word. Why we choose particular operations, and could we choose others? Can we use a different encoding, not based on positional numerals as the medium of computation and gain some comparative benefits throughout?
Is it conceivable that data structures and algorithms may be improved asymptotically if they were implemented directly as VLSI circuit designs? For example, is it theoretically conceivable that sorting and dynamic indexing (single-, multi-dimensional) of sets with variably-sized lexicographically ordered keys can be implemented more efficiently if we don't use RAM as our point of reference? Is there counterproof to that, proof, or conjecture?
If improvements appear to be possible under 2, how the relationship between the model and the problem enable such improvements? For example, given a universe of keys for an indexing problem, how can we decide if a given model of computation (restricted by faithful correspondence to the VLSI design economics) is optimal, or a better model of computation exists (again feasible and faithful to VLSI economics, but different operations and implementation)?

Thanks

PS:
A similar issue with lock-free algorithms in my opinion is that they assume the underlying architecture provides atomic operations that scale perfectly with the number of cores and cpus. The interconnects and coherency protocols can not scale perfectly, so essentially the algorithms remain blocking. The algorithmic design optimally solves the problem with the resources provided by the model, but this does not answer which is the most optimal practically feasible hardware architecture for solving the original problem, and whether from this point of view the algorithm is actually optimal.


texts: Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?

texts:
As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others).  Is there any evidence against this bound being tight?

The factorization norm bound (also called the $\gamma_2$ bound) I speak of is Theorem 13 of Linial, Shraibman 2008.  In fact, this bound follows from a reduction from quantum communication complexity to the bias in a 2-player XOR game Degorre, et al. 2008.  For this reason it could be expected to be a lousy bound since the XOR game doesn't even have anything to do with communication.  For the impatient, a brief overview is given in some slides by Troy Lee.

The introduction text of Jain, Klauck 2010 says that information theoretic techniques may offer some competition but it is not known whether these beat the $\gamma_2$ bound.  So it would seem that, at least as of a few years ago, $\gamma_2$ was the best technique.  But I would like to know if there is even a specific example of a function that is believed to have quantum communication complexity much greater than the $\gamma_2$ bound.


texts: Required mathematics for computational geometry research career

texts:
I have a computer engineering degree and i am very interested in theoretical and combinatorial aspects of computational geometry .

I want to build the mathematical foundation for this area so i can apply for a decent research based postgraduate program .

My question is :
What topics in math should I study to prepare for this goal?

thank you


texts: Complexity of 3SAT where each pair of 3-clauses share at most one variable

texts:
Consider the variant of the 3SAT problem with the following restrictions:

Each clause has 2 or 3 literals.
Each pair of 3-literal clauses have at most one common variable.

What is the complexity of this SAT problem?


texts:
Recently, Dana Scott proposed stochastic lambda calculus, an attempt to introduce probabilistic elements into (untyped) lambda calculus based on a semantics called graph model.  You can find his slides on line for example here and his paper in Journal of Applied
Logic, vol. 12 (2014).

However, by a quick search on the Web, I found similar previous research, for example, that for Hindley-Milner type system.  The way they introduce probabilistic semantics is similar to Scott's (in the former, they use monads while in the latter Scott uses continuation-passing style).

In which way is the Scott's work different from previous work available, in terms of theories themselves or their possible applications?


texts: What is the proof-theoretic significance of the existence of a Brown-Palsberg self-interpreter for system $F_\omega$?

texts:
In A Self-Interpreter for F-omega, Brown and Palsberg construct for each term of each type $x:T$ a representation $\bar x : \Box T$ (a metatheoretical function which can't be represented in the language), and an interpretation function $u_T : \Box T \to T$. This is reminiscent of GL provability logic, which in particular abstracts how PA can represent its own proof theory. But while the representation looks like the axiom $\vdash T \implies \vdash \Box T$, the second $\vdash \Box T \to T$ is inconsistent with GL.

So what sort of gadget is this, in logical terms?

Can it be used at all to talk about the metatheory of F-omega?

What would a representation operation that satisfies the axioms of GL look like?


texts: Among an infinite variety of n x n board games, why are some interesting?

texts:
Suitably generalized to $n \times n$ boards,
Checkers, Chess, and Go are each EXPTIME-Complete.
(See the Wikipedia
Game Complexity table.)
Each of these two-person games of perfect information
has a simple, finite set of move / capture / promotion / win rules.
Presumably there are an infinite number of sets of rules that lead
to games of complexity (at least) EXPTIME-Complete.

  Q. Are the rules of
  {Checkers, Chess, Go} historical accidents among
  an infinite variety of similarly difficult but potentially interesting games
  that just haven't been explored or 'caught on'?
  Or do the rule sets of popular games have special properties that make them
  especially attractive for human play?

I realize this is not a sharp cstheory question, and perhaps has no definitive answer.


texts: About the correspondence of left introduction and elimination of implication in Sequent Calculus and in Natural Deduction resp.

texts: Could anyone give an intuitive (not intutionistic) explanation of the correspondence of left introduction and elimination of implication in Sequent Calculus (SC) and Natural Deduction (ND) respectively? I know they should by the symmetry of SC but I don't see how they correspond to each other. More generally, I don't understand how left introduction of a connective in SC renders exactly the elimination of it in ND intuitively.


texts: NP-complete problems related to Minimizing Variance

texts:
I am interested in references to NP-complete problems that involve some non-linear terms (e.g. quadratic terms). So far I am aware of the "Quadratic Assignment problem" and "Quadratic Programming". The non-linear terms can be part of e.g. the constraints or the objective function. My motivation is to get some ideas for the following problem:

Let $k>0$ be an integer and $G=(V,E)$ an undirected graph such that the degree of each vertex is at least $k$. Each node of $G$ picks $k$ of its neighbors as its mates. For each node $v$ let $m(v)$ be the number of neighbors that selected $v$ as a mate. Then $\sum_{v\in V} m(v) = |V|k$. Given a number $C>0$. The mate-problem is to decide whether there exists a selection of mates such that the variance of this selection is less than $C$. In other words
$\sum_{v\in V} (m(v) - \mu)^2 < C$
where $\mu$ is the mean value, i.e. $\mu = \frac{1}{|V|}\sum_{v\in V}m(v)$.

Is this decision problem NP-complete? The case $C=0$ can be solved by a max-flow problem.


texts: Can we efficiently distinguish between P and BPP?

texts:
Let's say algorithm $D$ distinguishes $BPP$ from $P$ if
there exists a language $L \in BPP$ such that for all $A \in PTM$,
$$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$

Can we show this statement is false for all polynomial time algorithms $D$?

The question can be phrase in another way.
$BPP \neq P$ iff
there is a function $D$ such that
for some language $L\in BPP$ and
for all $A \in P$ we have
$$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$

Most researchers seem to lean towards $P=BPP$,
so we don't expect there is any such $D$.

Can we at least prove that
there is no polynomial time computable function $D$
separating $P$ from $BPP$?


texts: Escaping references in Eff and resources

texts:
In the paper "Programming with Algebraic Effects and Handlers" there is the issue where references (dynamic instances of a state effect, defined using algebraic effects) can propagate outside the scope of the handler. I assume the problem here is that calling an operation on the reference would result in an "unhandled operation" run-time error. "Resources" are introduced to remedy this problem, they seem like implicit handlers around the whole program.

What I was wondering is, if one had an effect system that tracked called operations then would references propagating outside the handler scope still be a problem? The unhandled operations called on the reference would be known statically in the effect system and so these problems can be ruled out, run-time errors of this kind wouldn't appear.

Resources would still be useful to reduce verbosity and to fully emulate ML-style references, but they would no longer be needed to avoid run-time errors if one had a sufficient effect system. Am I right in thinking this?


texts: How to make the Lambda Calculus strong normalizing without a type system?

texts: Is there any system similar to the lambda calculus that is strong normalizing, without the need to add a type system on top of it?


texts: A categorized (?) list of functional pearls in JFP and ICFP

texts:
Is there a list of (categorized preferred) functional pearls ever published in ICFP and JFP? I could go to the ICFP proceedings and JFP issues and find all of them, but this would be time-consuming.

Haskell Wiki apparently has a list, but it only includes functional pearls that use Haskell as the language of presentation, and that excludes many beautiful functional pearls (e.g. the ICFP 2016 functional pearl on contracts).


texts: Data processing inequality for interaction information

texts: The interaction information is defined as $I(X;Y)-I(X;Y|Z)$. Let $Z-(X, Y) -(X', Y')$  be a Markov chain. Is there an inequality similar to the data processing inequality, relating $I(X';Y')-I(X';Y'|Z)$ to $I(X;Y)-I(X;Y|Z)$? Thanks in advance.


texts:
Consider a function $f:\mathbb{N} \to \{0,1\}$ whose is defined in terms of some universal Turing machine $U$. If $U$ halts when given $x$ as input then $f(x)=1$, otherwise $f(x)=0$.

Clearly the function $f$ is undecidable. Now consider a new function $g:\mathbb{N}\to \{0,1\}$, defined by
$$
g(x) = \begin{cases} f(x/10^{6}) & \text{if $x \mathop{\%} 10^{6}=0$} \\
0 & \text{otherwise.} \end{cases}
$$

It's equally clear that $g$ is undecidable. However, informally it seems that there should be some sense in which $g$ is less undecidable than $f$, since, informally speaking, it looks like the value of $g$ can be determined for $99.999\%$ of its inputs just by checking if they're divisible by a million.

My first question is whether there's any sense in which the intuitive claim that $f$ is more undecidable than $g$ can be made into a rigorous one.

If there is, I'm interested in whether there are any functions that are particularly "densely" undecidable. I have in mind something like a universal Turing machine that not only halts for about 50% of possible inputs, but also when it fails to halt it does so for a wide variety of different non-trivial reasons. (If this were not the case one could generate a second Turing machine to spot the majority of non-halting cases, so it wouldn't be densely undecidable.)

To ask more or less the same question in a different way: the vast majority of randomly-generated strings will halt immediately (with a compile error) if fed to a C compiler. The probability that randomly generated C code will fail to halt is very low, and the probability that it will fail to halt for some non-trivial reason is much lower still.  I'm interested in whether one can define a language (or model of computation) that, when given random input, is quite likely to do something strange and non-trivial that makes its output difficult to predict.


texts: Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?

texts:
An elaboration on this question, but with more constraints.

The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions.  The bucketing grid seems to work nicely if you can find a grid size that will suitably partition your data.  However, what if the data is not uniformly distributed, but has areas with both very high and very low density (for example, the US population), so that no fixed grid size could guarantee both enough neighbors and efficiency?  Can this method still be salvaged?

If not, other suggestions would be helpful.


texts: compact context free expression for permutation

texts:
This may sound like theoretically void question, because certainly permutation is expressible even on the lowest level of Chomsky hierarchy:

P -> a b c
  |  a c b
  |  b a c
  |  b c a
  |  c a b
  |  c b a

In practice, however, proposition that the only way to describe SQL syntax is permuting "where", "group by", "having" (and many more similar clauses in some SQL dialects) is silly.

Boolean grammars allow succinct expression for permutation

X -> a
   | b
   | c

Y ->
   | X

P -> X X X & - Y a Y a Y & - Y b Y b Y & - Y c Y c Y

but perhaps there is a way to do it in the context free realm too?


texts: Are there descriptive complexity representations of quantum complexity classes?

texts:
The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in.

Descriptive complexity theorists, such as Immerman and Fagin, have characterized many of the most well-known complexity classes using logic.  For example, NP can be characterized with second-order existential queries; P can be characterized with first-order queries with a least-fixed point operator added.

My question is:  Have there been any attempts, especially successful ones, at coming up with such representations for quantum complexity classes, such as BQP or NQP?  If not, why not?

Thank you.

Update(moderator): this question is completely answered by this post on mathoverflow.


texts: Newman's lemma for distributional communication complexity

texts:
This may be obvious — sorry if it is.

Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be converted to one that uses only $O(\log(n/\delta^2))$ public random bits, while preserving the communication complexity and at the price of an additional $\delta$ probability of error.

Adapting the proof, this generalizes readily to $k$-party protocols $f\colon (\{0,1\}^n)^k\to\{0,1\}$, using $O(\log(kn/\delta^2))$ public random bits.

What I couldn't find is the same result for distributional communication complexity (more precisely, for public-coin randomized distributional communication complexity, which may be a rather niche notion (?)). For the worst-case setting, the $n$ factor in the number of public random bits comes from a union bound over all possible $2^{2n}$ joint inputs. In the case of distributional communication complexity, where the input $x,y)$ (or even $(x^{(1)},\dots,x^{(k)})$ comes from a distribution $\mu$ over inputs, does that mean that one can avoid this union bound, and get the conclusion of Newman's lemma with only  $O(1/\delta^2)$ public random bits?

(This seems a bit too good to be true — what am I missing?)

Here is the proof I have in mind:

Let $\mu$ a distribution over $\{0,1\}^n\times\{0,1\}^n$, and $f\colon \{0,1\}^n\times\{0,1\}^n \to \{0,1\}$ the function to compute. Let $\Pi$ be a public-coin protocol computing $f$ with probability at least $1-\varepsilon$ over $\mu$, i.e.,
$$
\mathbb{P}_{(x,y)\sim \mu, r}\{ \Pi(x,y; r) \neq f(x,y) \} \leq \varepsilon
$$
where the probability is taken over the choice of input (drawn from $\mu$) and the public randomness $r$ of $\Pi$.

As in the proof of Newman's lemma, we can assume wlog that $\Pi$ is a uniform distribution over deterministic protocols $\Pi_1,\dots,\Pi_R$ for some $R\geq 0$. Thus,
$$
\mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon
$$
and, if we select uniformly and independently $t = O(1/\delta^2)$ indices $r_1,\dots, r_t\in[R]$, we have with probability at least $9/10$ that
$$
\frac{1}{t}\sum_{i=1}^t \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r_i) \neq f(x,y)} \leq \varepsilon + \delta
$$
so that in particular there exists a choice of $t$ indices $r^*_1,\dots, r^*_t\in[R]$ such that
$$
\mathbb{P}_{(x,y)\sim \mu, i\sim[t]}\{ \Pi(x,y; r) \neq f(x,y) \}
= \mathbb{E}_{i\sim [t]} \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r^\ast_i) \neq f(x,y)} \leq \varepsilon+\delta
$$
which yields a public-coin protocol $\Pi^\ast$ with same communication complexity as $\Pi$, using only $O(\log t) = O(\log(1/\delta))$ random bits.


texts: Which complexity class does this number theory problem belong to?

texts:
'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete.

Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?


texts:
Adleman and  McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz)

Problem 18 of this list of open problems is about testing if an element of $\mathbb{Z}/p\mathbb{Z}$, where $p$ is a prime, generates the group. It is  known that this problem can be reduced to factorization and to discrete log (this reduction requires ERH).

Shoup 1990 (http://www.shoup.net/papers/primroots.pdf) gives a method that generates a subset of a finite field that contains at least one primitive root.

But what is known about checking if a element is a primitive root?
What are the best algorithms for this?
What do we know about the complexity classes in which this problem lies?


texts: Examples of Universe inconsistency in normal use of dependent types

texts:
In dependent types, Type : Type results in inconsistency (Girard's or Hurken's paradox).

Are there examples of universe inconsistency (where assuming Type : Type would result something that is false) showing up "accidentally" when not deliberately trying to prove it (when proving unrelated things)?


texts: Is there any NC-complete problem with respect to logspace reduction?

texts:
The question is on the title.

We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, is there any $k \ge 2$ and any $\text{NC}^k$-complete problem with respect to logspace reduction? For $k = 1$, Barrington's theorem already gives a logspace complete problem.

It seems that if $\text{NC}$ has a logspace complete problem, the $\text{NC}$ hierarchy collapses. So, the title question is open, but the other question still stands.

Edit: Fixed so that the original (title) question is OPEN, and there is one question left so far.


texts: machine learning for code and compiler optimization?

texts:
I am looking into ML for generating more efficient code (i.e. compile time and run time heuristics). I have a phd (compilers, hpc), but very little ML experience.

I would appreciate any references to existing work.

More importantly, which Machine Learning techniques should i be exploring ?

each data sample is a code + test run + performance data
large number of data samples, with correct labeling
large number of parameters to modify
any sample can be rerun with any parameters (and get correct labeling)
large amount of cpu to run and re run samples

And also some of my very suspect assumptions...

much of the code is already locally-optimal (basic compiler optimization)
some of the parameters are "high level concepts" e.g. replace array with linked list. (so a small parameter change will have varied effects)
the desired improvement is bounded (a xK improvement is "good enough", K is well known)
the parameters are sparse i.e. mostly zero (i suspect that most code is basically good, and there are relatively few beneficial changes)

Any pointers to set me on my way would be appreciated


texts: 2 partition problem with equal cardinality

texts:
Possible Duplicate:
  Faster pseudo-polynomial time algorithms for PARTITION

I want to partition N given numbers( may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal ( if n is even ) or differ only by 1 ( if n is odd)

I think we can do this in pseudo polynomial time O(n^2 * Sum of set)

Can I do better than this?

Thanks in advance!


texts: Is set packing easier when the sets are squares?

texts:
I am interested in the following problem:

There are n collections of M axis-parallel squares (not necessarily disjoint).
Pick a single square from each collection,
     such that the n selected squares are pairwise interior-disjoint.

One way to approach the problem is to discretize the squares such that each square becomes a set of small squares. This makes the problem an instance of the following set packing problem:

There are n collections of sets (not necessarily disjoint).
Pick a single set from each collection,
     such that the n selected sets are pairwise disjoint.

The set packing problem is equivalent to the independent set problem, and both are known to be NP-complete.

My question is: does the fact that the sets in this case are discretizations of axis-parallel squares make the problem any easier?

Particularly, is it possible to solve the problem, or at least approximate it to a constant factor, in time polynomial in $n$ (the number of collections), assuming $M$ is constant?


texts: Applications of metric structures on posets/lattices in theoryCS

texts:
Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper bound in $X$, and similarly define $x \wedge y$ (meet)(join)as a greatest lower bound.

  A lattice is a poset in which any two
  elements have a unique meet and a
  unique join.

Lattices (in this form) show up in theoryCS in (briefly) the theory of submodularity (with the subset lattice) and clustering (the partition lattice), as well as in domain theory (which I don't understand too well) and static analysis.

But I'm interested in applications which use metric structures on lattices. A simple example comes from clustering, where any antimonotone submodular function $f : X \rightarrow R$ (antimonotone means that if $x \le y, f(x) \le f(y)$) induces a metric
$$d(x,y) = 2f(x \wedge y) - f(x) - f(y)$$

This metric has been used extensively as a way to compare two different clusterings of a data set.

Are there other applications of lattices that care about metric structures ? I've been interested in the domain theory/static analysis application, but so far I've not seen any need for metrics.


texts: Largest set allowing one-step unstructured quantum search

texts:
What is the largest set admitting a deterministic quantum search algorithm, for a single marked element, that operates with only a single call to the oracle?

The question is interesting since Grover's algorithm, which for unstructured search on an $N$-element set requires $O(\sqrt{N})$ calls to the oracle, can in fact search a 4-element set using only a single call.

In general, it is interesting to ask for the minimum number of calls to a quantum oracle required to deterministically search an unstructured set of size $N$ for a single marked element.

Note that Grover's algorithm is optimal up to a constant factor in the limit of large $N$, although of course that does not mean it is optimal for any given finite set.


texts: What is the most powerful kind of parser?

texts:
As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of grammar, and I'm not interested in hacking up my language because of an impedance mismatch with the tool. Therefore, I'm not averse to writing my own.

So what's the most powerful type of parser? Citations to papers (as well as more introductory articles) would be welcome.

(I know that 'powerful' is not precisely defined, but let's be a little loose with it and see where the answers go)


texts:
Q. What is the complexity of finding the largest volume bounded cell in an arrangment of
  $n$ hyperplanes in dimension $d$?

I feel I should know this... But I am not finding a definitive reference.

Is it $\Omega(n^d)$?
How about the $d{=}2$ specialization:
The largest area bounded cell in an arrangement of lines?


texts: Is intersection of $k \ge 3$ graphic matroids in P?

texts:
It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.

A special case of a problem I am working on can be solved by intersection multiple graphic matroids, but I haven't been able to find, whether this problem is in P.

Question: Is it known? Can someone please refer me to a paper or something?

(Note: I have asked this question on Computer Science and was referred here.)


texts: Has what I am calling "helpfulness" here been studied?

texts:
We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'm curious about questions like "What is the probability that $f$ is helpful for $g$ given that $g$ is helpful for $f$, where $f, g$ are distributed uniformly randomly?" Another way to phrase this question is "Is the helpful relation mostly directed?"

Just to get the intuition across, one simple example of this is parity, where if you're computing the parity of the bits indexed by elements of some set $S$, $\chi_S$, then $\chi_T$ will only be helpful when the set of extra indices you have to compute parity on to correct this to $\chi_S$ is less than  $|S|$. Specifically, we have to compute parity on $S - T$, $T - S$, then add these to $\chi_T(x)$, so if $|S \triangle T| < |S|$, $\chi_T$ is helpful for $\chi_S$.

I'm sure this has been looked at before, so I'm mostly looking for references here. One can define a similar, stronger notion, where you define $Inner(f)$ to be the set of functions computed by an internal node to a size-optimal circuit for $f$. For parity it seems that most of the internal functions are parity functions on less inputs. What other functions, which are not some easily recoverable distortion of parity on a subset of the bits, are helpful for parity?


texts: Base-k representations of the co-domain of a polynomial - is it context-free?

texts:
In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open:

Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for all $n \in \mathbb{N}$. Prove or disprove that the language of the base-k representations of all integers in $\{p(n) \mid n \geqslant 0\}$ is context-free if and only if the degree of $p$ is $\leqslant 1$.

What's its status now (as for Oct 2018)? Is it proven? What about some special cases?


texts: Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?

texts:
Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, but some others get easier. A superclass of cubic graphs is the class of graphs with maximum degree $\Delta \leq 3$.

  Is there any problem that can be solve in polynomial time for cubic graphs but that is NP-hard for graphs with maximum degree $\Delta \leq 3$?


texts: Complexity class for Optimization problems over #P functions

texts:
Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e:

$$\tilde{f}(x) = \text{Max}_{f \in F}f(x)$$

where $f\in\# P$.

Moreover, if I can reduce a #P-Complete function to this, by means of a polynomial time Turing reduction, am I allowed to say formally that:

$$\tilde{f} \in \#P-\text{Complete}$$

OR

$$FP^{\tilde{f}} \in FP^{\#P} $$

The latter seems more plausible to me than the former, but could anyone please tell me if I could use the former claim.


texts: Logspace algorithms on graphs with bounded tree width

texts:
Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor.

Courcelle's theorem states that any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree width. A recent paper showed that Courcelle's theorem still holds when "linear time" is replaced with "logspace". However, this does not settle the space complexity of Graph Isomorphism on graphs with bounded tree width. The best known result puts it in LogCFL.

Are there other problems that are :

NP-hard (or not known to be in P) on general graphs, and
known to be solvable in linear/polynomial time on graphs with bounded tree width, and
NOT known to be in LogSpace ?


texts: Application of Yao's Minmax Principle for Adaptive Randomized Algorithms

texts: Reference Request: I am interested in references where Yao's Minimax Principle is applied for adaptive randomized algorithms if any. More generally, I am interested in minimax lower bound results for adaptive randomized algorithms.


texts:
I have a problem which is in NEXP$^{\text{NP}}$ and can also be solved by an alternating TM using exponential time and just one alternation (starting in an existential state).

Is there anything known about NEXP$^{\text{NP}}$? Is it equal to NEXP or some other class? Are there complete problems other than the generic one (given an NEXP$^{\text{NP}}$ machine and a word, does it accept?).


texts: Does “Second X is NP-complete” imply “X is NP-complete”?

texts:
"Second $X$" problem is the problem of deciding the existence of another solution different from some given solution for problem instance.

For some $NP$-complete problems, the second solution version is $NP$-complete (deciding the existence of another solution for the partial Latin square completion problem) while for others it is either trivial (Second NAE SAT) or it can not be $NP$-complete (Second Hamiltonian cycle in cubic graphs) under widely believed complexity conjecture. I am interested in the opposite direction.

We assume a natural $NP$ problem $X$ where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier and it does not have any knowledge of any correct witness ( both examples in the comments are solutions by definition).

  Does “Second $X$ is NP-complete” imply “$X$ is NP-complete” for all "natural" problems $X$?

In other words, Are there any "natural" problem $X$ where this implication fails?. Or equivalently,

  Is there any "natural" problem $X$ in $NP$ and not known to be $NP$-complete but its Second $X$ problem is $NP$-complete?

EDIT: Thanks to Marzio's comments, I am not interested in contrived counter-examples. I am only interested in natural and interesting counter-examples for NP-complete problems $X$ similar to the ones above. An acceptable answer is either a proof of the above implication or a counter-example "Second X problem" which is defined for natural, interesting, and well known $NP$ problem $X$.

EDIT 2: Thanks to the fruitful discussion with David Richerby, I have edited the question to emphasis that my interest is only in natural problems $X$.

EDIT 3: Motivation: First, the existence of such implication may simplify the $NP$-completeness proofs of many $NP$ problems. Secondly, the existence of the implication links the complexity of deciding the uniqueness of solution to the problem of deciding existence of a solution for $NP$ problems.


texts: Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

texts:
Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids.

To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of recognizable and regular languages and invoke Kleene's theorem. Can anyone think of a direct algebraic proof of this closure property on the level of monoids?


texts: Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

texts:
In this paper by Tishby, Pereira and Bialek they mention on page 4 in the Relevant quantization chapter the setting is the following; Given some signal space $X \sim p(x)$ and a quantized codebook $\hat{X}$. They seek a possibly stochastic mapping characterized by the pdf $p(\hat{x}|x)$ from every value $x \in X$ to a codeword $\hat{x} \in \hat{X}$.

This has made me wonder about the following:

1) They mention that the average volume of the elements of $X$ that are mapped to the same codeword is $2^{H(X|\hat{X})}$ - why is this?

2) They mention that for ease of exposition both $X$ and $\hat{X}$ are finite, so howcome $p(\hat{x}|x)$ is a p.d.f and not a p.m.f?


texts: Extension of a partial order to a total of partitions of a weak alternating automaton

texts:
My problem is this: given a weak alternating automaton and its partitions, and given a partial order on these partitions, how do we extend the partial order to a total order?

The partitions of weak alternating automaton are defined as follows: Let $A(\Sigma,Q,q_0,\delta,\alpha)$ where $\alpha$ represents the acceptance condition, $Q$ is the set of states, and $q_0$ is the initial state. A weak alternating automaton is an alternating Buchi tree automaton in which exists a partition of the set $Q$ into disjoint sets $Q_1,\dotsc,Q_n$, such that for each set $Q_i$, either $Q_i\subseteq\alpha$ (in which case $Q_i$ is an accepting set) or $Q_i\cap\alpha=\varnothing$ (in which case $Q_i$ is a rejecting set). In addition exists a partial order $\leq$ on the collection of $Q_i$, such that for every $s \in Q_i$ and $s' \in Q_j$ for which $s'\in\delta(s,a)$ we have $Q_j \leq Q_i$. Thus, transition from the state in $Q_i$ lead to states in either the same $Q_i$ or lower one.Hence , given the partial order defined above, how to turn this order in a total order $Q_1 \leq Q_2 \leq ... \leq Q_n$


texts: Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?

texts:
I'm wondering which is the approximation class of Minimum 0-1 Integer Programming if only non-negative integers are used. That is:

minimize $c^T \cdot x$,
with $x\in \{0,1\}^n$ and $c\in (\mathbb{Z}^*)^n$,
subject to $Ax \geq b$, where $A\in (\mathbb{Z}^*)^{m * n}$ and $b\in (\mathbb{Z}^*)^m$.

where $c^T$ is the transpose of vector $c$ and $\mathbb{Z}^*$ is the set of non-negative integers. Alternatively, $\mathbb{Z}^*$ could be replaced by the set of non-negative rationals, and we could force $b=(1,...,1)$ (it would be the same problem up to normalization).

If negative integers were allowed in $A$ and $b$, then this problem would be Minimum 0-1 Integer Programming, which is NPO-complete.

If $x$ were a vector of integers, rather than a vector of bits, then it would be Cover Integer Program (CIP), which can be approximated logarithmically according to "Improved approximations of packing and covering problems" by A. Srinivasan (1995).

There are many other known related problems with different variations, e.g. all elements in $A$ must be bits, $\geq$ is $\leq$ and min is max, there is a single inequation (i.e. $m = 1$), etc. I had some hope when I found this: https://www.nada.kth.se/~viggo/wwwcompendium/node199.html#7105, comments section, last sentence. However, $A$ is a matrix of bits in that work.

It is trivial to build an S-reduction from Minimum Set Cover, so at least it is Log-APX-hard. But at a first glance it looks too "simple" for Poly-APX- or Exp-APX-hardness, I don't know... Has this problem ever been studied?

EDIT: In the last two weeks I have developed an approximation to the problem (not based on linear programming) and, if my maths are right, it is logarithmic. Since it looks like this variant of  Minimum 0-1 Integer Programming has not been studied yet in the literature, it could be publishable (?). I promise I'll get back here and report it, as soon as some reviewers check out its correctness (also if it's wrong, so that nobody else wastes his time trying the same!). (And, of course, if this problem has already been tackled in the literature, I would really appreciate it if you let me know!!)

EDIT2: As Chandra's answer says below, Kolloiopoulos and Young gave a logarithmic approximation to a generalization of this problem. They define $x$ as a vector of non-negative integers but, simultaneously, include constraints of the form $x \leq d$. By setting $d=(1,...,1)$, $x$ must be a vector of bits.


texts: Do buyers bidding for sellers and sellers bidding for buyers produce equivalent outcomes?

texts:
Google adwords is a well known application of algorithmic game theory. It has a system wherein  buyers of ad placements bid to put their ads up on various sellers websites, then pay the second bid below them.

If this system were turned on its head, and sellers of ad placements (websites, in other words) bid to be the cheapest space (relative to their quality) for buyers of ads and were paid the second cheapest price instead, would this result in the same prices being paid for ad placements?

If these two scenarios are not equivalent, where is the breakdown?

In general, is there any duality between these problems?


texts: Is there a randomized algorithm for set-cover?

texts: Is there a well-known randomized algorithm for the set cover problem in the literature - such that it has an approximation ratio of $O(\log n)$ or $f$ - where $f$ is the max frequency of an element. please don't mention the randomized rounding method with LP (or any other method depending on LP) ?


texts:
Disclaimer: I know very little about complexity theory.

I'm sorry but there is really no way to ask this question without being (terribly) concise:

  What should be the morphisms in "the" category of Turing machines?

This is obviously subjective and depends upon one's interpretation of the theory, so an answer to this question should ideally give some evidence and reasoning supporting the answer as well.

I'd like to emphasis the point that i'm looking for a category of Turing machines and not of formal languages for example. In particular I think my morphisms should contain finer information then reductions or anything like that (I'm not sure though).

Of course if there's already a well known and used category in the literature i'd like to know what it is.


texts:
Coq has a type Prop of proof irrelevant propositions which are discarded during extraction. What are the reason for having this if we use Coq only for proofs. Prop is impredicative, so Prop : Prop, however, Coq automatically infers universe indexes and we can use Type(i) instead everywhere. It seems Prop complicates everything a lot.

I read that there're philosophical reasons for separating Set and Prop in Luo's book, however, I didn't find them in the book. What are they?


texts:
I have the following thoughts so I'd like to hear are there any straightforward implications which might support or undermine them.

You have a class BPP where problems have a TM with bounded two side error and constant ratio of correct leaves in your computational tree.

You have a class NP, which you can think of there is a TM with computational tree which is correct for no instances , but for yes instance $x$ you can have the correct leaves ration as small as $\frac{1}{2^{p(|x|)}}$.

If you kind of combine this you get for no instances all leaves correct for yes instances only the constant ratio, and this is class RP.

So the conjecture is $RP = NP \cap BPP$. What are the important implications? Is there a 1-line proof?

From me, I can add that the widely believed conjecture $BPP = P$ definitely supports the claim.

Thank you.


texts: Laying paths on a network using minimum number of links/edges

texts:
Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$.  Also given is a traffic matrix $T_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$.  The goal is to minimize the number of links required to support all traffic in $T_{ij}$ such that the total traffic traversing each link $e$ is less than $c(e)$.

Is there an equivalent problem in the literature?

thanks,
kwan


texts: Capacitated multiple vehicle routing problem with handovers

texts:
I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e. the ability to drop off an item from a vehicle and let another one pick it up.

Put otherwise, we could say we are allowing an item to be transported (sequentially) by more than one vehicle, e.g.:

at time $T^u$ vehicle $V_1$ takes the item from the pick-up location $P^u$
at time $T^d_1 \geq T^u$ vehicle $V_1$ drops it off at an intermediate point $P_1$
at time $T^u_1 \geq T^d_1$ vehicle $V_2$ picks it up from the intermediate point $P_1$
at time $T^d_2 \geq T^u_1$ vehicle $V_2$ drops it off at the intermediate point $P_2$
...
at time $T^u_{n-1} \geq T^d_{n-1}$ vehicle $V_n$ picks it up from intermediate point $P_{n-1}$
at time $T^d \geq T^u_{n-1}$ vehicle $V_n$ delivers it to the final destination $P^d$.

In the VRP overviews I found this variant is not mentioned so I was wondering if anybody knew if it has been investigated at all.

note: the term handover is something I came up with to describe the problem: it may not be the one commonly used to denote this kind of variant. The intended meaning, w.r.t. the example above is that e.g. when vehicle $V_1$ drops off the object $O_1$ at $P_1$ and $V_2$ picks it up we could say that "$V_1$ hands over object $O_1$ to $V_2$ in $P_1$".

update: Reworded to clarify that I'm talking about multiple vehicles (it was just kind-of implicit in the original wording).


texts: Bipartite maximum matching size from eigenvalues

texts: Supposing we know the adjacency matrix $\mathcal{A}_{G}$ of a given regular (or irregular) bipartite graph $G$. Are there good lower and upper bounds to the size of maximum matching from the graph's adjacency matrix's or its Laplacian's eigenvalues (without using an algorithm to calculate explicitly a maximum matching)?


texts: What's known about basing one-way function on the $P \neq NP$ assumption?

texts: Is there a conditional impossibility result or the question is completely open?


texts:
Ive read some articles about deep learning but I found its hard to provide a clear definition of deep learning.

For me its like an intelligent feature selection method.

But it seems that its not precise enough.


texts:
My problem is related to the standard bin packing problem, but in my case each item has a value, and the objective is to minimise the number of bins used to pack all the items PLUS the sum of the maximum value in each bucket.

Formally, given a bin $S$ of size $V$ and a list of $n$ items with sizes $a_1,\dots,a_n$ and values $v_1,\dots,v_n$ to pack, find an integer number of bins $B$ and a $B$-Partition of a set $S_1 \cup \dots \cup S_B$ of the set $\{1,\dots,n\}$ such that $\sum_{i \in S_k} a_i \leq V$ for all $k=1,\dots,B$.
Such partition shoud be the one that minimises the quantity $B+\sum max_{i\in S_k}v_i$ for all $k=1,\dots,B$.

Do you know if this particular version has been studied before and if it has a good approximate solution algorithm?


texts: Dependent eliminator for empty type in intensional Martin-Löf type theory

texts:
In calculus of inductive constructions you can just say that the empty type is the type with no constructors and it automatically builds the dependent eliminator.
But let's say I'm setting up intensional Martin-Löf type theory with the primitives $0$, $1$, $2$, $\Pi$, $\Sigma$, $\mathrm{Id}$, $W$ and the universes (like in this pdf).
Do I have to make the eliminator for $0$ dependent or can it just be $\mathrm{absurd}_C$ for each fixed type $C$? Does this choice make any difference (e.g. some type is inhabited if the dependent eliminator is allowed and not otherwise)?
Intuitively it doesn't make sense that the eliminator must be dependent as there is nothing to depend on.


texts: Why hidden subgroup problem is easy for very large subgroup?

texts:
I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE
NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the hidden subgroup is very large:

  Our lower bound on the runtime of the standard method, for subgroups of a group $G$, depends upon two parameters: the size of the hidden subgroup $H$ (naturally the problem becomes easy if $H$ is very large), and $c(G)$, the number of conjugacy classes in $G$. We give a lower bound showing that approximately $\left(\frac{\sqrt{|G|}}{|H|\sqrt{c(G)}}\right)^{1/3}$ rounds of Fourier sampling are required before the standard method can identify $H$.

My questions:

Why is it easy?
How large is 'very large'?

My effort:
Let the group be $G$ and the subgroup be $H$. One could argue that If any $g \in G$ is found to be in $H$ we know that all $g^n$ are in $H$ for $n \in \mathbb{Z}$. So we can skip them and check other group elements of $G$. But how do we know that determining $g^n$'s is cheaper than feeding them to the quantum circuit?


texts:
The study of Succinct representation of graphs was initiated by Galperin and Wigderson in a paper from 1983, where they prove that for many simple problems like finding a triangle in a graph, the corresponding succinct version in $\mathsf{NP}$-complete. Papadimitriou and Yanakkakis further this line of research, and prove that for a problem $\Pi$ which is $\mathsf{NP}$-complete/$\mathsf{P}$-complete, the corresponding Succinct version, namely Succinct $\Pi$ is respectively, $\mathsf{NEXP}$-complete and $\mathsf{EXP}$-complete. (They also show that if $\Pi$ is $\mathsf{NL}$-complete, then Succinct $\Pi$ is $\mathsf{PSPACE}$-complete.

Now my question is, are there any problems $\Pi$ known for which, the corresponding Succinct version is in $\mathsf{P}$? I'd be interested in knowing about any other related results(both positive and impossibility results, if any) which I might have missed above. (I couldn't locate anything of interest by a google search, since search words like succinct, representation, problems, graphs
lead to just almost any complexity result! :))


texts: Treewidth of deep Sierpiński Sieve Graph

texts:
Note $S_n$ the Sierpiński sieve graph of order $n$, which is obtained from the connectivity of the Sierpiński sieve.

For $n$ high enough, what is the treewidth of $S_n$?

I think that I can show that it is at least $4$ (by obtaining $K_5$ as a graph minor), and that it is at most $5$ (by obtained a tree-decomposition scheme involving bags of size $6$). My gut feeling is that it should be $5$, but I cannot find a proper database for forbidden minors at treewidth $4$ (and I can't access Sanders' thesis mentioned here).


texts: What are the consequences of a ${\bf O}$(m) algorithm for SAT

texts:
We are given a Boolean formula $F$ in conjunctive normal form with $n$ variables and $m$ clauses and we would like to know if there exists at least one assignment to the $n$ variables that makes $F$ evaluate to True. As we all know this is the famous NP-Complete SAT problem. I would like to know the consequences of being able to solve this problem in time ${\bf O}$($m$). Would this contradict the Phase transition phenomenon that has been shown to exists for the SAT problem? Thank You

PS:If you do not allow repetition of variables in a clause nor repetition of clauses in a formula then you can have up to 3$^{n}$-1 unique clauses.


texts: Does this graph problem have a formal name?

texts: Given an undirected weighted graph where an edge exists between every pair of nodes (n1,n2) with cost C(n1,n2), find the shortest path (possibly revisiting nodes, possibly revisiting edges) through the graph that visits each node.  Algo can pick any source node it wants.  No need for the path to terminate back at the source node.  Path cost is cumulative over all edge visits, so, if you traverse an edge with cost 5 and then traverse it again later it costs you 10 (i.e. re-traversing an already explored edge isn't free!)


texts:
I have a quite big graph which has millions of nodes and edges. I modify the graph using an algorithm which only changes small portion of edges. At then end, I'd like to investigate how the algorithm affects the graph. There are a couple of options I have considered, but neither are appropriate.

1) compare the graph metrics (e.g. avg nodes degree, avg. coefficient clustering) for two graphs. The problem is as the algorithm only affects small portion of edges, and as there are great number of nodes and edges, the reported values are almost the same.

2) sample portion of each graph and find graph metrics on the sampled graphs. Again, the reported numbers are quire similar.

Is there any metric or technique to compare only subgraphs of two graphs? That is, I would like to consider only the modified nodes in the comparison.


texts: Tiling a rectangle with the fewest squares

texts:
Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares.

Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best known algorithm?


texts: Notions of Computability at Higher Type III

texts:
I've recently found a very nice survey paper called "Notions of Computability at Higher Type" by John R. Longley.

The paper says it is part of a 3-part series, with the 3rd concerning non-extensional notions of computability, corresponding to computability in languages with effects.

This part might be relevant to my own research so I'm very interested in finding it.
However, I can't find a version of part III anywhere. Was it ever completed? If not is there another good resource on the subject you would recommend?


texts: Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

texts:
Inspired by the questions Nondeterministic communication complexity of set disjointness?, I was wondering about the following:

  Is there an example of a function $f$ where the nondeterministic communication complexity $N(f)$ is asymptotically smaller than the deterministic communication complexity $D(f)$.

When $f$ is the Equality problem or the Set Disjointness problem, we seem to have $D(f) = N(f)$ and, as far as I can tell, the common techniques for showing lower bounds for deterministic protocols (fooling sets and the rank method) work just as well for nondeterministic protocols.

  Are there any known techniques that yield stronger lower bounds for deterministic protocols compared to nondeterministic protocols?


texts: Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

texts:
I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph.

Input: Given a graph G with non-negative vertex weights and valid but not important to be optimal coloring of G.
Task: Find the Maximum weight Independent Set.

Note that this problem is NP-hard (for k>2 where k is the number of coloring) [see here]

in Hochbaum's paper in 1996 "Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and related problems" in Theorem 3.2 he give an (2/k)-approximation algorithm for this problem.
Now, my question is: Is there any new results regarding this problem? Is there any lower bound for this problem? Of course in general for simple graph without coloring to find Independent Set, there is no constant factor unless P=NP. Now, Is it true that we cannot have a constant factor for this coloring case? anything related to this problem, it would be nice to mention it here.
Thank you!


texts: Minimizing the maximum dot product among k unit vectors in an n-dimensional space

texts:
Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,

$$\alpha = \max_{1 \le i <j \le k} \{v_i \cdot v_j\}.$$

What is the minimum possible value of $\alpha$?


texts: Complexity of determining unique elements of each cycle in a permutation

texts:
It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation.

But suppose that we know that the number of cycles in the permutation is less than a fixed number $k$. Can we find $k$ distinct elements belonging to the $k$ cycles in less than $O(n)$ time? Clearly, if $k=1$ this is true. But is it true for all $k$?

More specifically, suppose we know that $k$ is $O(log{\text{ n}})$, does this information help in anyway? I'm interested in understanding the time complexity of this problem, but if it's possible to give an efficient randomized algorithm for this problem, that will also be interesting in itself.

I have tried to find papers on this topic without any luck so any relevant paper or material will be greatly appreciated.


texts: Functional Completeness of 3-valued logic

texts:
In the context of some recent work, we have been defining a language based on a three-valued logic à la Kleene, where $1$ stands for true, $0$ for false, and $\bot$ for error or don't-know. In order to show that our language was expressive, we wanted to prove that we could build a set of operators functionally complete.

It was quite hard to find existing results in the literature. We found one paper written in 1962 by Jobe, which states the following theorem:

  Jobe 1962 Theorem Paper (restricted access).

  The three-valued logic $E$ expressed over the set $\{1, 2, 3\}$ and defined by the operators $\bullet, E_1$ and $E_2$, given below, is functionally complete.

  $$
    \begin{array}{c|ccc|c|c}
        ~\bullet~ & ~3~ & ~2~ & ~1~ & ~E_1~ & ~E_2~ \\ \hline
        3     & 3 & 2 & 1 & 3   & 1 \\
        2     & 2 & 2 & 1 & 1   & 2 \\
        1     & 1 & 1 & 1 & 2   & 3
    \end{array}
$$

In our paper, we have used this result by showing a correspondance between our operators and those defined by Jobe (roughly speaking, we use the strong conjunction, the negation, and an operator that transforms don't-know in false).

My main concern is that I'm actually not able to understand the proof of functional completeness of Jobe, and we haven't been able to find any other result (positive or negative) after this date, which is somehow a bit surprising.

So my question is the following: are there some more known results about the functional completeness of 3-valued logics? Any info in this direction would be helpful.


texts: Concise introduction to algorithms for mathematicians

texts:
I am looking for a concise introductory text on algorithms with a high ratio $$\frac{\mbox{theory covered}}{\mbox{total number of pages}}.$$ It should begin at the beginning but then progress quickly without spending too much time on real world examples, elementary proof techniques, etc. As a research mathematician I have a solid background in mathematics which I happily employ to understand formalisms and condensed proofs, for example.

Do there exist such texts? Any recommendations?


texts:
I'm not sure this question is appropriate for this site, but it might have some connections with computational algebra.

Consider a fixed "category" $\sf{Cat}$ (in the sense of category theory, but the precise notion is not important), e.g. groups or fields. Given an object $\mathbb{S}$ of $\sf{Cat}$, we say that a "composition series" for $\mathbb{S}$ is a chain of objects $C = (\mathbb{S}_{\alpha})_{\alpha}$ indexed by some ordinal $\lambda$, such that $\mathbb{S}_0$ is an initial object and for every $\alpha < \beta$, $\mathbb{S}_{\alpha}$ is a subobject of $\mathbb{S}_{\beta}$. We may then define the length of $C$ as the ordinal $\lambda$.

We say that the structure $\mathbb{S}$ is isogenic if all maximal composition series have the same length. For instance, this is true for finite groups ordered by the normal subgroup relation (according to the Jordan-Hölder theorem). My question is: what are the structures known to have this property?


texts: What data structures exist for fast calculation of distances between multi-dimensional points

texts:
I'm writing a program that receives data over a network connection. Every data point is simply a 4 dimensional vertex, lets call the dimensions X,Y,Z,W.  The values of each dimension are exponentially distributed.

I'm currently saving the data and plotting the data, in real time, as a 2D scatter plot.  Here is an example of such a plot:

One thing is obvious in the picture is there are most of the points are near the origin. Any two points that overlap are redundant as they carry the identical information. This means that the majority of the points near the origin can be discarded where as very few points far from the origin can be discarded. I'd like to come up with an intelligent way to filter out redundant points.

I've thought of a few way of doing this. One of which would use an intelligent data structure that when insertNewPoint is called the structure first checks to see if any points in the data structure are within a predefined distance of the new point. If this is true than the new point is discarded otherwise it is added to the data structure.

Here is some pseudo code that illustrates the idea:

Structure Points{
    list storedPoints;
    distance threshold;

    insertNewPoint(newPoint){
        for each point in storedPoints
            if calculateDistance(newPoint, point) < threshold
                return false

        storedPoints.add(newPoint)
        return true
    }

}

I anticipate that these data structures will eventually contain upwards of 50K+ points, and each second between 10-100 new points will be received by my program.

Are there data structures that are designed for these kind of operations? If not, what would be the most efficient way implement a structure like this for 4 dimensions?


texts: Lower bound on independence number in terms of clique number and order of graph

texts:
In the paper "On Multi-dimensional Packing Problems" by Chekuri and Khanna there is the following lemma:

Lemma 4.3.(p. 191 of the paper) Let $G$ be a graph on $n$ vertices with $\omega(G) ≤ k$. Then $\alpha(G) ≥ n^{1/k}$.

If we substitute $G$ by a complete graph, then we get:
$\omega(G) = n$, then $\alpha(G) ≥ n^{1/n}>1$.

However, if I correctly understand the notion of an independence number, then $\alpha(K_n)=1,\forall n$. A contradiction to the lemma.

I have checked for several cases and it seems that this is the only one where the lemma doesn't hold.

Could someone explain what is wrong with my reasoning?

P.S. I sent this question to one of the authors before posting it here, but haven't received any answer.


texts:
This question is inspired by the great answer given by Jeffrey Shallit on my question about proper CSG for $a^n b^n c^n$ language.

Disclaimer:: I'm not arguing about correctness of this grammar. This grammar is absolutely correct. My question is about classification.

In his version of grammar which is

$S \rightarrow ABSc$
$S \rightarrow Abc$
$BA \rightarrow XA$
$XA \rightarrow XY$
$XY \rightarrow AY$
$AY \rightarrow AB$
$A \rightarrow a$
$Bb \rightarrow bb$,

there is possibility of "dead" derivations which doesn't give us a string, e.g.: $\Rightarrow_1 ABSc\Rightarrow_2 ABAbcc\Rightarrow_7 ABabcc\Rightarrow_7aBabcc\Rightarrow_? ?$.

I know that it doesn't prevent grammar to generate proper language $a^n b^n c^n$.

What I'm troubling about is classification of such kind of grammars. Because there is obvious difference between weakly equivalent grammars (which produce same language), where one of them contains such kind of "dead end" derivations, and another one doesn't (see my 10-ruled version of this grammar).

I thought that this difference should be classified somehow, because at least it influences on complexity of full language generation process or on brute-force parsing process (generators which deal with "dead" generation chains have to make more backtracking steps or produce more parallel derivations). For instance, JFLAP tool produces string $aaabbbccc$ using 20 levels and 792 nodes on Jeffrey Shallit's 8-ruled grammar, and using 16 levels and 194 nodes for my 10-rules case. But I didn't find any kind of such classification.

It possibly could be relation to the efficiency of constructed linear-bounded automaton using algorithm given by Kuroda, but I'm still wondering are any known classification for such cases?