texts: what is the equivalence class of a given polytree representing a directed graphical model?

texts:
Let $T$ be a binary tree, where the internal nodes are $Y_1,...,Y_n$ and the leafs are $X_1,...,X_m$. (The $Y$s and the $X$s will eventuall represent a random variable in a Bayesian network.)

We can turn this binary tree into a polytree by directing all the edges downward toward the leafs from the root. What we get is a graphical model or a Bayesian network.

My main question - what other polytrees over the $Y$s and the $X$s can we have such that the marginal distribution $p(X_1,...,X_m)$ is the same like the marginal distribution in the original polytree I just described?

I am guessing we may be able to redirect some edges such that they point to a different node, and still get the same independence assumptions (and hence the same marginal distribution), but I am not sure what would be the permitted inversions.

Thanks!


texts: Sampling Functions Efficiently vs Pseudorandom Generators

texts:
Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions computable by circuits of size $s$, or the set of n-bit Boolean functions computable by branching programs of width $w$, etc.

What are the implications of an efficient algorithm that samples a function from $X$ uniformly at random? Examples of concrete questions are the following.

Does sampling functions from $X$ uniformly at random in time $n^{O(1)}$, implies the existence of pseudorandom generators of small seed-length that fool all functions in $X$?
I remember of having read somewhere that the natural proofs method does not encompass Razborov lower bounds for monotone Boolean circuits because one does not know how to sample n-bit monotone Boolean functions efficiently. Why would such a sampling algorithm imply lower bounds based on cryptographic assumptions?

Obs: Note that sampling uniformly from X is not the same as sampling uniformly from the circuits representing function from X, since many circuits may represent to the same function.


texts: Gaussian Elimination in terms of Group Action

texts:
Gaussian elimination makes determinant of a matrix polynomial-time computable.   The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence of alternate negative signs (lack of which makes computing permanent is $ \#P\mbox{-}hard$ ie. harder then $NP\mbox{-}C$ problems). This leads to some sort of symmetry in determinant, eg exchange of a pair of rows or columns just reverses the signs. I read somewhere, probably in connections with holographic algorithms introduced by Valiant, that Gaussian elimination could be explained in terms of group action and this in turns leads to generic techniques in complexity reduction.

Also, i feel that almost all source of complexity reduction for any computational problem is some sort of symmetry present. Is it true? Can we rigorously formalize this in terms of group theory?

Edit

I found the reference. (pg 2, last line of second paragraph). I did not understand the paper properly, If my question is based on wrong understanding of the paper, please correct me.


texts:
Minimum Vertex Cover problem

Input: $G=(V,E)$ and Parameter $k$

Output: Decide whether there exists minimum vertex cover of size at most $k$.

Question:-
Can we bound the number of minimum vertex covers of size at most $k$ on general graphs?

C=number of minimum vertex covers of size at most $k$

Is C bounded by $f(k)$? If not can you provide example? If yes what is $f(k)$


texts:
Suppose I have a #P-hard function $f(S,x)$ where $x\in T$. Is the problem of $\arg\max_x f(S,x)$ guaranteed to be intractable?

If so, I want to see some references on this topic. If not, is there a general approach to prove such intractability for some typical problems?

For example, we know that S-Set Connectedness is #P-complete 1. Is finding the node with maximum connectedness with a particular set also intractable?

Thank you very much!


texts: clustering algorithm for non-dimensional data

texts:
i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this dataset. i imagine that because the data has no dimensions, a cluster center might consist of several data points and a tolerance, and membership within the cluster might be determined by the average of the distance of a data point to every data point in the cluster center.

please forgive me if this question has a well known solution, i know very little about this kind of problem! my (very limited) research has only turned up clustering algorithms for dimensional data, but i apologize in advance if i've missed something obvious.

thank you!


texts: Analogues of different complexity classes in various models

texts:
We suspect following relation:
$$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit complexity model.

What are analogous complexity classes in BSS model and Valiant's arithmetic complexity model?

What are known relations and implications among complexity classes in these models?

What surprise would counter intuitive results such as $P=NP$ have on these hierachies and vice versa?


texts: Combinatorial object for a rational generating function

texts:
The is a well-established connection between generating functions and the specification of combinatorial objects via symbolic and/or analytic combinatorics.
A number of packages (e.g. SAGE) allow the generating function to be obtained from a combinatorial specification.
Do any packages support the inverse mapping, i.e. from a generating function to a specification of the corresponding combinatorial object?
If not, is there some paper that describes a specific algorithmic approach?
If it helps, I am interested in the particular case when the generating function is a rational function.


texts:
Hej guys,

I'm working on customizing a Vehicle Routing Problem for a practical case, which is characterized as follows:

The set of customers does not change over time, but their respective prizes are degressing in a  non-linear fashion (deterministic).
Traveling costs do not change.
Need to visit every customer exactly once.

So I've been digging through tons of papers and such, but I can't find anything similar to the given case .. The Dynamic VRP goes way too far, with stochastics and redefining the routes in an ongoing fashion, which I do not need in this special case, because the degression of prizes is deterministic. I thought about the Traveling Repairman Problem, but I can't come up with a way to use it .. The VRP with Time Windows seems to be a completely different case as I have no opening or closing times.

Maybe someone got any hints for me ? I'm pretty sure this case has been dealt with, as it seems to be practically relevant.

Any help is appreciated !

Edit: as mentioned in the comments I should provide a sufficient version of the VRP:

Input:
N: given set of customers,
D: given set of demands of said customers,
C: given set of traveling costs, where c_ij is the weight of the arc (i,j),
M: maximum number of vehicles that may be used,
V: fixed costs of using a vehicle,
Q: capacity of a vehicle,
P: set of prizes for every customer,
f(t): a function describing the degression of the prizes,
(I'm not sure yet whether I want to visit every customer or not)

Output:
Optimal routes with the following objective:

minimize total costs of travel,
minimize number of vehicles used,
maximize sum of prizes.

Whether finding the optimal solution is possible or not is not really of interest in the first place.

[As I looked for questions related to the VRP, TSP and similar models, these were posted in theoretical CS, but now I see that this section is definitely not the right one for me ..]


texts: "Almost sorting" integers in linear time

texts:
I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but arithmetic operations on them are assumed to take unit time). Of course, this is impossible with comparison-based sorting algorithms, so I am interested in computing an "approximate" sort, i.e., computing some permutation $v_{\sigma(1)}, \ldots, v_{\sigma(n)}$ of $L$ which is not really sorted in general but a "good approximation" of the sorted version of $L$. I will assume that we are sorting the integers in decreasing order because it makes the sequel a bit more pleasant to state, but of course one could phrase the problem the other way round.

One possible criterion for an approximate sort is the following (*): letting $N$ be $\sum_i v_i$, for every $1 \leq i \leq n$, we require that $v_{\sigma(i)} \leq N/i$ (i.e., the "quasi-sorted" list is bounded from above by the decreasing function $i \mapsto N/i$). It is easy to see that the actual sort satisfies this: $v_{\sigma(2)}$ must be no greater than $v_{\sigma(1)}$ so it is at most $(v_{\sigma(1)} + v_{\sigma(2)})/2$ which is $\leq N/2$, and in general $v_{\sigma(i)}$ must be no greater than $(\sum_{j \leq i} v_{\sigma(i)})/i$ which is $\leq N/i$.

For instance, requirement (*) can be achieved by the algorithm below (suggested by @Louis). My question is: Is there existing work on this task of "almost sorting" integers in linear time, by imposing some requirement like (*) that the real sort would satisfy? Does the algorithm below, or some variant of it, have an established name?

Edit: fixed the algorithm and added more explanations

Algorithm:

INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i<n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+

This algorithm works as intended for the following reasons:

If an element $v$ is in the bucket $j$ then $v ≤ N/j$.

  $v$ is put into the bucket $j=\min(N/v,n)$, thus $j ≤ \lfloor N/v\rfloor ≤ N/v$

If an element $v$ is in the bucket $j$ then either $N/(j+1) < v$ or $j=n$.

  $v$ is put into the bucket $j=\min(N/v,n)$, thus $j = \lfloor N/v \rfloor$ or $j=n$. In the first case $j=\lfloor N/v\rfloor$ which means $j ≤ N/v < j+1$ and thus $N/(j+1) < v$.

For $j<n$, there are, at most, $j$ elements in the buckets from 1 to $j$.

  Let $j<n$ and let $k$ be the total number of elements in one of the
  buckets 1..j. By 2. we have that every element $v$ in a bucket $i$ (with $i ≤ j$) is such that $N/(j+1)≤N/(i+1)<v$. Therefore the sum $K$ of all elements in the buckets from $1$ to $j$ is greater than $k×N/(J+1)$. But this sum $K$ is also less than $N$ thus $k×N/(j+1) < K ≤ N$ and thus  $k/(j+1) < 1$ which gives us $k<j+1$ or $k≤j$.

$T$ satisfies (*) i.e. the $j$-th element of $T$ is such that $T[j] ≤ N/j$

  By 3. we have that $T[j]$, the $j$-th element of $T$, comes from a bucket $i$ with $i ≥ j$ therefore $T[j] ≤ N/i ≤ N/j$.

This algorithm takes linear time.

  The computation of $N$ takes linear time. Buckets can be implemented with a linked-list which has $O(1)$ insertion and iteration. The nested loop runs as many times as there are elements (i.e. $n$ times).


texts: How to measure programming language succinctness?

texts:
I want to explore the notion of quantifying the amount of succinctness a programming language provides.  That is, the amount a high-level language reduces the complex.

This idea of "simplification" is a factor of text-wise reduction (fewer characters needed to express a complex concept, à la Algorithmic Information Theory) and another, less easy-to-quantify concept of maintainability. Fleshing out this latter concept, it is clear it has to do with how easily one can establish programmer consensus for the given task (i.e. how many programmers of the language would put it back the same way you've expressed it or otherwise agree on the best implementation between different implementations of the same problem?).

I will define the "Kolmogorov Quotient" so that higher numbers for a given language denote a reduction in the complexity of solving the problem in the given language.

The metric for "text-wise reduction" should incorporate a constant factor based on (non-identifier) symbols used in the language and source text.  These factors will be the same across all languages implemented (i.e. designed) for a given architecture (e.g. VonNeumann architecture vs. Symbolics) and will be a measure of the significance of the symbol; i.e. the topology of the language tokens.  (These terms, alas, will also need to be fleshed out and defined.)

Once the basic premise and a methodology above is agreed to, it is only a matter of a rough constant of difference for any specific implementation/architecture. (That is, as long as the architecture is the same across all measurements, the number should be valid and comparable between languages.)

But it could go something like this: Pick a language "close to the machine", like C or Assembly, and measure the amount of bytes of machine code it used to implement a standard suite(*) of common, non-threaded programming tasks (base_language_count). Then code the exact same functionality in the language you are wanting to measure (without using external libraries) and count the number of bytes of source code (test_language_count).

KQuotient = (base_language_count / test_language_count) / number_of_equal_programs.

"number_of_equal_programs" is the number of programs fluent programmers of the language agree that are the best and equal solutions to the problem. (I will define "equal programs" as those who's output is the same for every input.)

The first ratio should always be greater than 1.0.  My only concern is that for each programming language, one could reduce the KQuotient number simply by changing each keyword to a single character.

(*) "standard suite of common programming tasks...":  I see two main categories:

Data-processing suite, limited to simple text I/O (computation towards the machine)
GUI suite (computation towards the user)

The purpose of this idea is to end the tiring "language wars" about whose language is the best.  By giving a quantitative metric, people can at least argue better.


texts: Storage system for large quantities of unique key value pairs optimized for insert

texts:
Background

I'm in the process of attempting to improve part of our data storage and analysis architecture. Without getting into a lot of details, at a certain part of our data analysis process we have a need to store large quantities (~100s of millions) of small pieces of unique data. The data looks like this:

ID, 20 bytes (immutable)
Hits, unsigned 64bit int (mutable)
Value1, arbitrary length byte array (immutable)
Value2, arbitrary length byte array (immutable)

I currently have this data stored in two parts, a B+Tree index which maps the keys to unsigned 64bit integer values. Those values are file offsets in a data file which contains a structure like:

[Hits] UInt64
[LengthOfValue1] UInt32
[Value1DataBlob] N-bytes
[LengthOfValue2] UInt32
[Value2DataBlob] N-bytes

As new values are posted to this data store, the code performs a lookup in the B+Tree. If the tree contains the value, the hit count is incremented in the data file. If the value is not there, a new entry is appended to the end of the data file, it's start offset the inserted into the B+Tree.

Later, after this process is complete, we will enumerate the data performing more processing on it. What is important here though is that, if the key is already in our system, we are incrementing the hits on that key. This is essentially a cache, which is tracking hits on each piece of data as it's encountered.

What we are finding is that as the B+Tree grows larger, insert times become VERY slow. Lookup remains very fast (as you might expect).

Question

So -- Does anyone know of another way to do this, where unique checks are lightening fast, and so are inserts? We really don't care about later search performance, because once we go through the initial build of this dataset, all we will use it for is to enumerate the results. We're not going to be doing random searches against the dataset, in a long term manner.

Please do not suggest any kind of off-the-shelve database system. We've tried a lot of them, and this custom solution is faster than any of them, with a smaller data storage footprint.

We're just trying to improve our custom solution, and have hit a wall with our collective CS knowledge. Maybe this is the fastest way to do this, or maybe a different structure would perform better than the B+Tree for inserts at this scale?


texts: totally-mixed 2SAT with exact cardinality?

texts:
Given a 2HornSAT problem, it’s possible in linear time to find the minimum solution to the problem, i.e., a solution that minimizes the number of variables set to 1.

Now let us consider the following restricted variant of that problem:

  Input: A positive integer $K$ and a 2SAT instance in which all clauses are mixed, i.e., have a positive literal and a negative literal.

  Output: Is there a satisfying assignment such that exactly $K$ variables are set to 1?

Is this problem NP-complete? I am struggling with its reduction but it seems this might be difficult.


texts: Can reversible computations alone be used to create a computer?

texts:
We are able to perform universal computations with the reversible model. Basically, during the computations, no information should be erased, so that no involved entropy increase would occur.

Are reversible computations alone sufficient to create a complete computer? The machine should be able to:

load programs,
handle user input,
provide an output.

I suspect that, for example reading user's input requires information deletion which cannot be avoided.


texts: On the Proof Technique of Boneh-Lynn-Shacham Gap Signatures

texts:
In paper "Short signatures from the Weil pairing" by Boneh, Lynn and Shacham, I was going through the security proof just like any other signature.

But the technique used in this paper is quite unique. Rather than using the normal challenger and adversary interaction, they have divided the proof into 6 games where each game is extended sequentially from the previous games.

I am not sure why they have used this approach instead of the normal game. Does this kind of security proof aid in reducing the probability easier or have they just given it from an "easy to read and understand" point of view?

Thanks!


texts: Dividing a complete graph into two cliques with maximal sum of edge weights

texts:
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\frac n2\in\mathbb Z$ vertices, and the sum of all weights is maximized.

Example:

$\begin{bmatrix}
&A  &  B &   C &   D\\
A   &0    &1    &0.66 &0.5\\
    B   &1    &0    &0.01 &0.5\\
    C   &0.66 &0.01 &0    &0.33\\
    D   &0.5  &0.5  &0.33 &0
\end{bmatrix}$

The above adjacency matrix of graph $G$ is an instance of the problem with $A$, $B$, $C$ and $D$ being the vertices of the graph. In this instance, the solution to the problem is pairing $A$ with $B$ $(1)$ and $C$ with $D$ $(0.33)$, with the resulting weight sum $1.33$ being the maximum achievable value.

What would be the exact algorithm for solving this problem, or maybe there is a problem which it can be reduced to?


texts: Function that maps non-linear distribution to normal distribution while maintaining distance

texts:
I have a collection $X$ of 10 million $(x,y,z)$ 3-tuples, where $x$, $y$, and $z$ are all numbers between 0 and 1.  The distribution of $x$, $y$, and $z$ values are complex, and the distributions of $x$ vs. $y$ vs. $z$ are not independent.

I want to find some function $f$ that maps each $(x,y,z)$ pair to another $n$-tuple (I don't care about the final arity, let's assume mapping 3-tuples to 3-tuples for now) such that:

$|f(x_i) - f(x_j)| + |f(y_i) - f(y_j)| + |f(z_i) - f(z_j)|$ is a valid distance metric according to the usual rules on any pair of 3-tuples $(x_i, y_i, z_i)$ and $(x_j, y_j, z_j)$
When I take the distribution of the 10 million pairs $\{f(x)\}_{x\in X}$, it is as close as possible to Uniform(0,1) x Uniform(0,1) x Uniform(0,1).

How would I go about this?  The closest thing I can think of is a variational autoencoder, but I don't know if that maintains distance properties, and results in a normal and not uniform distribution.

(I don't even know what tags this would fit under - suggestions in comments are welcome!)


texts: Problems in NP but not in Average-P/poly

texts:
The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\mathsf{\Sigma^P_3}$, no $\mathsf{NP}$-complete problem will belong to $\mathsf{P/poly}$.

I'm interested in the following question:

  Assuming that $\mathsf{PH}$ does not collapse, or assuming any other reasonable assumption in structural complexity, what hard-on-average $\mathsf{NP}$ problems are proven not to lie in $\mathsf{Average\mbox{-}P/poly}$ (if any)?

A definition of $\mathsf{Average\mbox{-}P/poly}$ can be found in Relations between Average-case and Worst-case Complexity. Thanks to Tsuyoshi for pointing out that I actually need to use $\mathsf{Average\mbox{-}P/poly}$ instead of $\mathsf{P/poly}$.

I think there are problems such as (the decision versions of) FACTORING or DLOG which are conjectured to lie in $\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$, but the conjecture is not proven based on separations between complexity classes. (Please correct me if I'm wrong.)


texts: Graph Isomorphism of Strongly Regular Graph with fixed parameter

texts:
$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant.

Here,
$n$  is the number of total vertices. Each graph is $r$ regular. Every two adjacent vertices of $G$ and $H$ have $\lambda$ common neighbours. Every two non-adjacent vertices of $G$ and $H$ have $\mu$ common neighbours.

What is the computational complexity of Graph Isomorphism Algorithm of Strongly Regular Graph  where $\lambda$ is constant?


texts: Hardness of Covering Arrays with $v=t=6$

texts:
A covering array is an $N \times k$ array with each entry as one of $v$ symbols, where for every $t$ columns all possible $v^t$ tuples appears at least once. The covering array number (CAN) is the smallest $N$ for which a covering array exists, given $t, k, v$. Many known CANs are here.

I have been looking at "optimality" of covering arrays in the following sense: for known values of $N$, and given $v$ and $t$, compute $\frac{N}{v^t}$: call this the "ratio" of the covering array (code is here). From the code, I ordered all of the covering arrays by descending ratio. Surprisingly, the first 229 were covering arrays with $v=t=6$ (the highest ratio is ~829, and the 229th is ~549).

Is there a combinatorial aspect as to why this case is more difficult than any other one? There are several reasons as to why I believe this is so:

There are known constructions of covering arrays from perfect hash families for $v$ a prime power, and $6$ is not a prime power.
With higher values of $t$, computation time to reduce redundant rows (or general metaheuristics such as tabu search, simulated annealing, etc.) grows very large (not to mention the space needed).
Most studied cases are for lower values of $v,t$ (and only when $v=t=2$ are the optimal cases known).


texts: Can we have more than one Deterministic Finite Automata diagrams for a set of strings?

texts:
Much like many math equations can be simplified. I am wondering if Deterministic Finite Automata diagrams can equal each other while some may be more simplified than others. I am following the youtube video and I am wondering if the graph that I drew with pencil and paper would also be correct. Given the Prompt:

Construct a DFA that accepts any strings over {a,b} that does not contain the string aabb in it.


texts: Pattern matching with don't cares: multiple patterns

texts:
Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution.

But what happens if we are searching for multiple patterns with don't cares? Can we still somehow solve it with e.g. FFT-based techniques?


texts: Exact arithmetic complexity of Ryser's formula for computing permanent

texts:
What is the exact number of multiplication operations and addition operations needed to calculate the permanent in Ryser's formula (both original and the Gray coded version)?

I am looking reference for an exact count. It seems Cramer rule always is inferior or just par with the Gray coded version. Also Scott Aaronson has a calculation for $4 \times 4$ determinant where he uses Gaussian elimination. He mentions estimating the precise gap between permanent and determinant calculation for $4 \times 4$ is already a notorious open problem.

I am also looking for counts for other calculations/formulas of Permanent.


texts: Simulation of every physical quantum system on quantum computer

texts:
Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi.

  With high confidence, we may claim that every physical quantum system
  can be efficiently simulated on a quantum computer, but we can never
  prove this statement.

Why can't we ever prove this statement?


texts:
Suppose I have $n+1$-dimensional vectors $a$ and $b$. For each $i = 0, \dots, n$, I also have integers $0 \leq j_0(i) \leq j_1(i) \leq i$. I want to compute the following variant of a convolution:

$$
c_i = \sum_{j_0(i) \leq j \leq j_1(i)} a_j b_{i-j}
$$

If $j_0(i) = 0, j_1(i) = i$ for all $i$ this is a standard convolution, so you can do this via FFT in time $O(n \log n)$.

Are there any good algorithms for this when $j_0, j_1$ are arbitrary?


texts: Is there a program for theory of incompleteness in $NP$?

texts:
Motivated by Suresh's post, Techniques for showing that problem is in hardness limbo, it seems that there might be an underlying theory that explains why some of these problems can not be complete for $NP$.

For instance, the theory should explain why problems with polynomially bounded solutions (FewP) can not be complete. Also, it should explain why problems solvable by bounded nondeterminism (log-clique) can not be complete.

  Is there a research program that tries to link the apparent incompleteness of at least two candidate problems in Suresh's post? What are the obstacles to such program?

EDIT: I am also interested in published research studying the connection between incomplete sets for $NP$ and finite versions of Godel's 2nd incompleteness theorem in the context of proof complexity.
Posted on MathOverflow.

EDIT 2:

Some of the results in Suresh's post can be interpreted as (conjectured) necessary conditions for the NP-completeness of a given problem B:

1- Problem B must be exponentially dense.

2- Problem B can have exponential number of solutions.

3- Problem B must require linear nondeterministic bits to solve.


texts: Computational hardness of "real" computer programs

texts:
I have often heard it said that you cannot write a program to catch bugs in a web browser, or word-processor, or operating system, because of Rice's Theorem: any semantical property for a Turing-complete language is undecidable.

However, I am not sure to what extent this applies to real-world program likes operating systems. Do these types of programs need the full strength of Turing completeness? Are there simpler models of computation (such as PR) in which these applications could be written? If so, to what extent does this allow decidability of program correctness?


texts: Do "One Way Functions" have any applications outside crypto ?

texts:
A function $f \colon \{0, 1\}^* \to \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm $A$,

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

for every polynomial $p(n)$ and sufficiently large $n$, assuming that $x$ is chosen uniformly from $\{ 0, 1 \}^n$. The probability is taken over the choice of $x$ and the randomness of $A$.

So... do "One Way Functions" have any applications outside cryptography? If yes, what are they?


texts: Classification of randomized approximation algorithms

texts:
Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently different randomized complexity classes for optimization problems, as $\mathsf{RP}$, $\mathsf{BPP}$, $\mathsf{ZPP}$, etc. for decision problems.)

One could for instance classify randomized $\alpha$-approximation algorithms in the following three classes (for say polytime algorithms):

Las Vegas: Algorithm with expected polynomial time complexity, which always returns an $\alpha$-approximation of the optimal result ;
Monte Carlo type I: Polynomial-time algorithm which returns a result that is an $\alpha$-approximation of the optimal result with probability $p$ (for some $p>1/2$ say) ;
Monte Carlo type II: Polynomial-time algorithm which returns a result whose expected approximation factor is $\alpha$.

Questions:

Is my classification (sort of) exhaustive, or do I forget one (or more!) important possibility?
Is such a classification made in some reference, with links between the different cases, and some (better) names?

The link between Monte Carlo type I and type II is for instance given in exercise 1.10 of Approximation algorithms by Vazirani (whose definition of a randomized approximation algorithm is btw "my" Monte Carlo type I).


texts: Low-depth arithmetic complexity of the product of $k$ matrices

texts:
Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?

Trivial upper bounds (up to small factors) are:

if $k=2$, then there are $\Sigma\Pi\Sigma$ circuits of size
$n^{\omega}$ (where $\omega$ is the matrix multiplication exponent.)
if $k>2$, then  there are $\Sigma\Pi\Sigma$ circuits of size
$n^{k+1}$.
if $k>2$, then  there are $O(log(k))$-depth circuits of size
$n^{\omega}$.

Is it possible to construct circuits of size $n^{\omega}$ for every $k$, for some fixed depth? Is it even possible to beat the trivial construction?


texts: Bipartite matching with degree domination

texts:
Given an unweighted bipartite graph $G=(V, E)$. Is it true that there always exists a nonempty matching $M\subseteq E$ (not necessarily maximal), such that for every $(i,j)\in E$ with $i$ matched and $j$ unmatched, it holds $\deg(i)>\deg(j)$? Here $(i,j)$ is not ordered, i.e., $i$ can be on either side.

My intuition on why this is true is, when every vertex in $V$ has the same degree, there is always a perfect matching which is the matching we required. For some simple graph structures like trees or unicyclic graphs a maximal matching is desired since the degree of a leaf is always smaller than its parent.

I tried to prove it from Hall's theorem but failed. Part of the complexity of this problem is that the solution is not always a maximal matching. For instance, considering a graph consisting of two 4-cycles $abcd$ and $defg$. Then $M=\{ab,cd\}$ and its symmetrical matchings are the only solutions, which are not maximal.


texts: Structural equality of Pi Types with heterogeneous equality?

texts:
I'm trying to implement a proof of the following type:

(X X' : Type0) -> (Y : (X -> Type0)) (Y' : (X' -> Type0) -> (X Type0~=~Type0 X')
-> ( Y (X -> Type0)~=~(X' -> Type0) Y' )
-> ((x : X) -> Y x) Type0~=~Type0 ((x' : X') -> Y' x')

i.e. if we have two function types with equal domain and codomain, then the pi types are themselves equal.

I'm using (z Z~=~W w) to denote McBride's Heterogeneous equality between (z : Z) and (w : W).

I'm wondering, can we prove this:

with dependent pattern matching?
using just the J axiom for heterogeneous equality?
Using J and K for heterogeneous equality?

I can see how I can start with a proof that ((x : X) -> Y x) ~=~ ((x : X) -> Y x), but if I use J to rewrite X to X', then (Y x') is ill typed.

I think I can see how to do it with dependent pattern matching, because matching on the proof of (X ~=~ X') rewrites X' to X both in the goal type and in the context for the goal. And I know that dependent pattern matching can be decomposed to eliminators + Axiom K a la Goguen et al. But it's not immediately clear to me how to do the proof directly, and whether it relies on K.


texts: What are some problems where we know we have an optimal algorithm?

texts:
What are some non-trivial problems where we know the current algorithm we have is the asymptotically optimal one? (For turing machines)

And how is this proved?


texts: I understand that it is a naive and very general question. I would like to know when does a theorem of theoretical computer science become interesting to professional philosophers? I understand that the question whether P != NP is pretty interesting to philosophers. Now let's take the conjecture about the existence of one way functions. Is there any philosophical implications of the existence of one way functions?


texts: Notation for scheduling problems with multiple release times/deadline intervals

texts:
I am interested in the classical scheduling problems where we are given jobs with a release time and a deadline, we must find a schedule for all jobs. Specifically, I am interested in the variant introduced by Simons and Sipser in 1984 in On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals, where the jobs can have not one but multiple feasible intervals.
In scheduling, there is a common three-field notation to systematically denote the different variants of scheduling problems. Hence my question is just to know if there is a way in this notation to indicate that jobs have a set of release-deadline pairs and not just one single release date and deadline. The problem variant in question seems natural and was introduced a long time ago, but I wasn't able to find a way to write it in this notation, either on this page or by searching in the literature.


texts: Are all problems in the same time hierarchy related to each other?

texts:
In this problem, "runtimes" refer to worst-case complexity compared up to constant factor.
Say you have two problems, A and B, in the same time hierarchy, and it is clear that algorithm P solves A with that time complexity.
Suppose an oracle spits out the result of problem A using algorithm P. Then does problem B, with the help of this oracle (call this B^P), necessarily have an algorithm running in less time than problem B without the oracle?


texts: Automata Theory / Formal Language Thesis Topic

texts:
Hey All,
  I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an acceptable topic would be, something ambitious but something doable at the same time.

Any suggestions would be very much appreciated!


texts: Church-Rosser equivalent for concatenative languages?

texts: Looking at the striking parallels between combinatory logic and concatenative languages makes me wonder how many theorems of the former hold in the latter. The Church-Rosser theorem is particularly interesting because it would justify the use of transparent quotations. Is there any concatenative programming language proven to be Church-Rosser?


texts: Can this randomized greedy algorithm be made online? Or being proved impossible?

texts:
I am going to edge color an undirected simple graph. The following randomized offline algorithm is showed at Online Algorithms for Edge Coloring.

Offline: The potential colors are ordered 1, 2, . . . , 2$\Delta$−1. The edges are ordered at random, and we greedily assign color 1 until a
maximal matching is colored 1, then we start over with a random order of the remaining uncolored edges and we greedily assign color 2 until a maximal matching of the remaining edges is colored 2, and so on with the remaining edges and maximal matchings for colors 3, 4, . . .

In paper Online Algorithms for Edge Coloring, the authors claimed the offline algorithm is the same as the online algorithm as follows.

Online: The edges are ordered at random only once, and each edge in turn is
colored with the least valid color out of 1, 2, . . . , 2$\Delta$ − 1.

The "same" means, for a given graph. If the first algorithm needs $c$ colors with probability $p$, then the second algorithm uses needs $c$ colors with probability $p$. So there is not clear justification that the given two algorithms are same.

The paper claims "For the second algorithm, if we consider sequentially when colors 1, 2, . . . are assigned, the same bound holds.".

In fact, they turn out to be different (see the examle below). So my question is: can the offline algorithm be made onlne? I cannot handle the multi-times random ordering ( after each maximal matching is removed, the order of the remaining edges is shuffled).

Example.

Let $E_r=\{e_0, e_1, e_2\}$, $X_i$ be the indicator random variable that whether color $i$ is assigned to one edge from $E_r$.  $X_i=1$ iff the i-th color is not assigned to the edges e_0, e_1, e_2. We calulate the expected number of colors from clolrs $\{1, 2\}$ which are not assinged to any of $\{e_0, e_1, e_2\}$.

For the "first algorithm":
$E[X_1+X_2] = Pr(X_1=1)+Pr(X_2=1) $
$=Pr(X_1=1)+Pr(X_2=1|X_1=1)\cdot Pr(X_1=1) + Pr(X_2=1|X_1=0)\cdot Pr(X_1=0)$
$=(\frac{2}{3})^3 + (\frac{1}{2})^3 \cdot (\frac{2}{3})^3 + (\frac{1}{2})^2 \cdot (1- (\frac{2}{3})^3 )$
$=\frac{1}{2}$

For the "second algorithm": We list all the $9!$ orderings, and get $E[X_1+X_2]=12/27=0.44444$.

The follwoing is responce for @vzn, thanks very much.

In fact, the paper was not published as far as I know. I have contacted the first author, he have not respond it in detail. The key is that, it does not "fit" clearly.
Why I only concern the first two colors in the example. If $x$ edges from $\{e_0, e_1, e_2\}$ are not assigned to colors in $\{1,2\}$, then the algorithms needs exactly $2+(3-x)=5-x$ colors. Because for the remaining $(3-x)$ edges incident to the root not colored, $(3-x)$ new colors have to be used. While the other edges will be colored in the third color definitely. Put another way, if the two algorithms were the same, all the characterizations of them should be the same? (For example, $E[X_1+X_2]$ here. Am I right? I am not sure.)


texts: Tolerance parameter of statistical query model and adaptivity

texts:
It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of Statistical Algorithms and a Lower Bound for Detecting Planted Cliques, http://arxiv.org/pdf/1201.1214v5.pdf).

My question is why this is a reasonable choice. The rationale of this choice seems to come from the argument that the oracle can return the average of the query function over $n$ data points. However, since the query function is adaptively chosen, the $1/\sqrt{n}$ rate of concentration does not always hold. This is because the query function itself also depends on data and thus the independence is ruined. For example, this paper (Section A, Preserving Statistical Validity in Adaptive Data Analysis http://arxiv.org/pdf/1411.2664v2.pdf) gives an example in which the concentration fails due to adaptive choice of the query.


texts:
I am re-opening this question as i have the following question.
I was going through the paper by Farrugia which was mentioned in an answer in that post. Initially i beleived that the follwoing problem is NP-Complete.

Suppose there is a graph $G=(V,E)$. I want to test if V can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs.

But in the paper,there is a theorem which says

  Let $A$ and $B$ be additive induced-hereditary properties. Then there
  is a polynomial-time transformation from the $A$-recognition problem
  to the $(A◦B)$-recognition problem.

So, my question is that :- is it possible that because of the above theorem the problem might be solvable in polynomial time ??


texts: A decomposition theorem for maximum weight matchings

texts:
The following paper presents a way to solve the maximum weight matching of a bipartite graph by reducing it to computing maximum weight matchings of two lighter bipartite graphs:

M.-Y. Kao, T. W. Lam, W.-K. Sung, and H.-F. Ting. A decomposition theorem
for maximum weight bipartite matchings with applications to evolutionary
trees. In Proc. of the 7th Annual European Symposium on Algorithms (ESA’99),
pages 438–449, 1999.

Is there a generalization of the result which also holds for non-bipartite weighted graphs?

Thank you.


texts: random sampling DAGs via nilpotent matrix sampling

texts:
The adjacency matrix of an acyclic graph is known to be a nilpotent matrix (all eigenvalues are zero). I am interested in sampling DAG adjacency matrices or equivalently sample random nilpotent matrices (the equivalence is a question in fact) and so far I have simplified the process to the following:

step 1. randomly permute the nodes
step 2. sample a strictly upper triangular matrix (zero diagonal)

the first step is required to make sure we shuffle the topological ordering roots and step 2 is constructing a random topological ordering. The matrix is nilpotent as by construction the eigenvalues are zero.
I'm interested in an answer to either question 1 or 2.

Would this process generate all possible DAGs with positive probability?
Are all nilpotent matrices adjacency matrices of DAGs AND would the process above generate with positive probability every nilpotent matrix?

Any pointers or hints will be greatly appreciated,
Best regards


texts: Separating Logspace from Polynomial time

texts:
It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$, $LogCFL$, $NC^i$, $SAC^i$, $AC^i$, $SC^i$. It is widely believed that $L \neq P$.

In one of my blog posts I mentioned two approaches (along with the corresponding conjectures) towards proving $L \neq P$. Both these approaches are based on branching programs and are 20 years apart !! Are there other approaches and/or conjectures towards separating $L$ from $P$ (or) separating any intermediate classes between $L$ and $P$.


texts: Complexity class of efficient streaming algorithms

texts:
Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:

$L \in \mathsf{StreamL}$ if there exists a Turing machine $M$ which decides $L$, where:

There are two tapes, the read-only input tape and the working tape

$M$ moves only to the left on the input tape, and uses at most $O(\log n)$ space on the working tape.

Has this class been studied?

My assumption is that the answer is yes, but I'm not yet aware of a definition of the class in the literature.
Most literature on streaming algorithms that I am aware of considers the complexity of solving specific algorithmic problems, and does not tackle structural complexity i.e. defining classes such as the above and determining their relationships.
There is also a large body of work on communication complexity classes. In this domain there is a relevant class called $\mathsf{P}^{cc}$ (see Babai, Frankl, and Simon 1986: Complexity classes in communication
complexity theory), which contains functions of two variables $f(x,y)$ where they can be solved using a small amount of communication between $x$ and $y$. This is related to $\mathsf{StreamL}$ above (for functions of two variables, $\mathsf{StreamL}$ is contained in $\mathsf{P}^{cc}$), but the class above is not limited to functions of two variables and enforces a stricter computational requirement.
The obvious inclusions are $\mathsf{REG} \subseteq \mathsf{StreamL} \subseteq \mathsf{L}$, and no apparent inclusion either way between $\mathsf{StreamL}$ and $\mathsf{NC}^1$.


texts:
I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of pivot determines its efficiency. We usually (Quicksort 3, and choosing a random element aside) select the first or last element as the pivot in an array. Therefore, since a good pivot is one that splits the array in half symmetrically, a more disordered array will make selecting a good pivot easier; or at least reduce the likely hood of running into the pathological case.

My program gradually randomises this array by swapping some elements each time. When I started to plot the graph of this using gnuplot I notice the trend I expected; a exponential distribution, branching off to a uniform distribution.

My question is, how do I quantify a level of disorder in a array? Is their a better way to gradually make an array of values more disordered?


texts:
Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time.
Help!

Related paper: On the structure of one-tape nondeterministic turing machine time hierarchy by Kobayashi.

Related question: Why do we use single tape Turing machines for time complexity? by Kaveh.


texts: An efficient Beta-Equivalence algorithm?

texts:
Is there an efficient algorithm to determine if two terms are beta-equivalent? I'm specifically curious about simply-typed-lambda-calculus, so you can assume both terms are strongly normalizing.
I know a simple algorithm:

Compute the beta normal form for each term.
Confirm that the two BNFs are alpha-equivalent.

But it is possible for BNFs to be exponentially larger than the original Term. Is it possible check the equivalence of Terms S and T in O(|S| + |T|) time?


texts: Chomsky Schützenberger enumeration theorem

texts:
In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some other books the formulation is given, that the structure describing function $$f_L(x)=\sum_{n \in \mathbb N}l_nx^n$$ is algebraic over $\mathbb Q$ iff the grammar is unambigious, where $l_n = \vert \Sigma^n \cap L \vert$.
I understand that by replacing every terminal by the same terminal in the system of equations associated with a grammar $G$ it is possible, to obtain the structure describing function, but I couldn't find a proof anywhere,(and don't know how I could construct one)  that then the (analytical) power series $f_L(x)$ is not transcendental.


texts: Predicting the growth of a social network

texts:
I am building a predictive model for the growth of the amount of users of a new p2p protocol inspired by bitcoin and I would like to use historical data collected from the growth of major social networks in my model. My specific questions are the following:

Does a public database exist containing growth data for major social networks?
Does there exist a generally accepted method for estimating contagion given specific network characteristics/assumptions?
I need to account for the loss of users over time and thus I need a proper way of measuring node death and its impact upon connected nodes in the model. Is there a generally accepted method to estimate this given some set of parameters?

As a side note, I am uncertain, which stack exchange to post this question in or the best way to format the question for this channel. If there is a forum one could recommend in the comments that is better suited, then I would appreciate the advice.


texts: I have a graph. I need visualise it with nodes arranged in a circle. How can I know whether it is possible arrange the nodes on a circle so that there no edges intersect in the visualised graph?


texts: Hardness result or reference for optimal Gaussian elimination process

texts:
I'm wondering if the following problem is NP-Complete or has any hardness result.
References on related problem are also welcome.

Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\mathbb F_2^{n\times n}$.
Accept iff: with at most $k$ row elimination, $M$ can be reduced to identity.

Here, one row elimination is simply adding one row to another (just like Gaussian elimination algorithm).
By Method of Four Russians, we know for any $n$, it suffices to have $k=O\left(\frac{n^2}{\log n}\right)$. But I'm curious about the minimum number of row eliminations required.


texts: Are there any good resources (descriptions, explanations, examples) regarding Jablon's protocol for password authentication using multiple servers, aside from this paper?


texts:
Savitch's theorem shows that NSPACE($S(n)$) $\subseteq$ SPACE($S(n)^2$), which means that nondeterminism can be replaced by more spaces in this situation. Is it known whether nondeterminism can be replaced by advice strings in a similar situation?

Especially, I would like to ask about "L/quasipoly vs NL/poly". If L/quasipoly $\supset$ NL/poly is proved, is this a new result?

(Here, L/quasipoly means (informally) L with quasipolynomial size advice strings.)

[Supplementary explanations]

Currently, I think that I may be able to prove that polynomial-size nondeterministic branching programs can be simulated by quasipolynomial-size $O(\log n)$-width boolean circuits.


texts: Finding max of two elements in linear time with restriction

texts:
I have a matrix in the following form:

ID | # Counts for ID | ID's Within Range.
1  | 5               | 1,2,3
2  | 3               | 1,2
3  | 2               | 1,3
....

The idea is that I want to find the 2 id's that when you sum the have the highest count. However, you must first exclude the pairs that overlap. For instance, id's 1 and 2 have the highest count but you can't use them since 1 has 2 within range and 2 has 1 within range. Thus from the table above you would use 2,3 as the sum since they don't overlap.

I would like to do this in O(n) or O(nlogn) time and O(n) storage. It's trivial to do if I first make all ID pairs but that gives me O(n^2). I can also do 2 forloops after sorting the list but that would also be at worst O(n^2) although usually much faster... Any help would be greatly appreciated! THanks!


texts: Are there any non-relativized separations between $L$ and $PH$?

texts:
In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the other. Is anything known about this question, whether $L \stackrel{?}{=} PH$?

There is this separation guaranteed by $L \neq PSPACE$, and so the weakest unanswered questions are when you circumvent the time- and space-hierarchy theorems by either asking to strengthen the lower side into a time-bound class (giving $P \stackrel{?}{=} PSPACE$), or by weakening the harder side into a time-bound class (giving $L \stackrel{?}{=} PH$).

It seems that I only ever hear about the first question though, and not the latter. Besides the question of the actual relation between the two classes, is there a reason why one question is so much more popular than the other?


texts: TSP in bounded tree-width (or bounded branch width) graphs

texts:
I see there are some papers/thesis which says TSP is solvable in $O(n)$ in bounded tree-width graphs and some of them implicitly refer to Cook and Seymour (not exact paper just said that they solve it), but I can't find any paper about it.

All the things I can find is branch-decomposition based algorithms with merging techniques, which are all heuristic (e.g very nice heuristic) but non of them are exact algorithm. Does anyone know the related papers for linear time solution? Or paper which says is impossible? or probably impossible? (any good news bad news, its not 3in1 question:).


texts: Complexity classes for proofs of knowledge

texts:
Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge.  Classes like SZK and NISZK are extremely natural from a complexity standpoint, even if we forgot entirely about zero knowledge and just defined them in terms of their complete promise problems.  By contrast, on googling 'proofs of knowledge,' I was surprised not to find any papers or lecture notes discussing this lovely concept in terms of complexity classes.

To give some examples: what can one say about the subclass of SZK∩MA∩coMA consisting of all languages L that admit statistical zero-knowledge proofs for x∈L or x∉L, that are also proofs of knowledge of a witness proving x∈L or x∉L?  Certainly this class contains things like discrete log, but we couldn't prove that it contains graph isomorphism without putting GI in coMA.  Does the class encompass all of SZK∩MA∩coMA?  One could also ask: if one-way functions exist, then does every language L∈MA∩coMA admit a computational zero-knowledge proof, that's also a proof of knowledge of a witness proving x∈L or x∉L?  (My apologies if one or both of these have trivial answers---I'm just trying to illustrate the sort of thing one could ask, once one decided to look at PoK in complexity-theoretic terms.)


texts:
After reading Daniel Apon's question, I started thinking that it might be useful (especially to junior researchers and graduate students like me) to ask a broader and more general question so we can learn from the experience of more senior researchers.

So here is the question:

  What practices have you found most useful in your research?

I don't want to restrict it to any particular type of advice, so any advice on research practice is welcome.


texts: Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

texts:
In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his factorization algorithm. The standard algorithm outputs $r'$, a divisor of the order $r$ of $x$ modulo $N$. Instead of checking if $r'=r$ by checking if $x^{r'}\equiv 1 \mod N$, the improvement is the following :

  [F]or a candidate $r$ one should consider not
  only $r ′$ but also its small multiples $2r ′ , 3r ′ , \dots$ , to see if these are the actual order of $x$. [... This] technique will reduce the expected number of
  trials for the hardest $n$ from $O(\log \log n)$ to $O(1)$ if the first ($\log n)^{1+\epsilon}$ multiples of $r ′$ are
  considered [Odylzko 1995].

The reference to [Odylzko 1995] is a “personal communication”, but I was not present when Peter Shor and Andrew Odlyzko discussed this... I perfectly understand why it is an improvement, but I don't know how to show the number of trials is reduced to $O(1)$. Do you know any proof of this?


texts: How do you initialize your seed in the preferential attachment model?

texts:
Suppose that we seed our network with $m$ vertices. Suppose that at each step we add a vertex and c edges adjacent to that vertex.

Should these initial $m$ vertices have no edges at the start of the growth procedure? Should they be an $m$-clique? Should they form a cycle?

It seems that in Barabasi and Albert's model, there are no edges. The problem here is that each vertex in the seed will have probability 0 of being selected as an endpoint of a new edge.


texts:
I'm curious if someone could recommend some supplementary material for gaining a deeper understanding of the paper : "Some Results and Problems on Quantum Bell-Type Inequalities - Tsirelson".

Specifically something that may elaborate a tad more on the geometric interpretation of Bell-Type inequalities. Perhaps a primer paper or relevant textbook that goes into more detail on these matters. I'd appreciate any/all feedback. Thanks again.


texts:
Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity between $0$ and $n^2$ (via Gaussian elemination). The notion makes sense over any field.

This problem certainly seems very basic and it must have been studied. Surprisingly, I don't know of any references. So, I'll be happy with any reference there is. But, of course, the main question is:

Are there any non-trivial explicit lower bounds known?

By nontrivial I mean superlinear. Just to be clear: Over finite fields a counting argument shows that a random matrix has complexity order n^2 (a similar claim should be true over infinite fields). Hence, what we're looking for is an explicit family of matrices, e.g., Hadmard matrices. This is the same as with Boolean circuit complexity where we know that a random function has high complexity, but we're looking for explicit functions with this property.


texts: Why does the transformation in the proof for SL=L preserve connectedness of s and t?

texts:
I'm currently working on this paper showing that $\mathcal{SL} = \mathcal{L}$.
But I keep wondering how the transformation $\tau$ in definition 3.1 preserves the connectivity of $s$ and $t$. $\tau$ consists of several applications of the zig-zag-product and powering.

They show in Lemma 3.2 that if $s$ and $t$ aren't connected in $G$, then all nodes induced by $s$ arent't connected to any node induced by $t$.
But they don't show that if $s$ and $t$ were connected in $G$ that $s'$ and $t'$, as defined in the proof of the theorems 4.1 and 4.2, are connected in $\tau(G,H)$ for some expander graph $H$.

One can easily find examples were the zig-zag-product or powering destroys connectivity of nodes. So why is here no argumentation needed on why $s'$ and $t'$ will be connected if $s$ and $t$ were? Am I missing something?

I assume that the proof itself is correct since the first versions of the paper were published more than ten years ago.

PS: I'm not 100% sure whether this is a research level question. But I think that it will be hard to get an answer in one of the other forums since it is kind of special question.

EDIT:

I think I found the trick. Proposition 2.2 states that if $\lambda < 1$ is achieved there is a path of some length for every pair of verticies $s$ and $t$. Thus by showing that the spectral expansion of the nodes induced by the connected component of s
is smaller than $1/2$ it is also shown, that the connection isn't lost (if there was one).


texts: Type, operation and function, and their limits

texts:
First of all, sorry for my English.

I would like to know, when I want to define a new type (I'm currently developing a computer interpreted language), how can I determine which "functions" are fundamental operations for a particular type, and which "function" are external, in the sense that, I don't need this function to define the characterization of the type?.

Let me call "operations" to the "essential functions" of the type and "functions" to anything else that simply uses the type.

For example, we all agree (I suspect), that the sum, difference, product and division are good examples of "operations" that defines the type integer for example, or number in general, but an operation like factorial is more a function.

The question is, in a more general or theoretical point of view, where is the line between "function" and "operation" for the intended purpose? For example, for more abstract types like domain-specifics data structures, auxiliary classes or something more difficult than a "number", how or which test can I perform to say: that's a good as operation, or that's better being a function.


texts: Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?

texts:
A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to produce two answers $(a,b) \in O^2$ such that $V(x,y,a,b) = 1$ - in which case they are said to win the game $G$. The maximum probability that Alice and Bob can win the game $G$, over the randomness of the inputs and their strategies, is called the value of the game. The value of the game can change depending on the resources allowed: if Alice and Bob are purely classical players, then the classical value is denoted $\omega(G)$. If Alice and Bob can share quantum entanglement and employ quantum strategies, they can achieve a quantum value $\omega^*(G)$. If Alice and Bob can share general no-signalling strategies, they can achieve a no-signalling value $\omega^{ns}(G)$. It is known that $\omega(G) \leq \omega^*(G) \leq \omega^{ns}(G) \leq 1$. Are there games for which all three inequalities are strict?

For example, the famed CHSH game is an example of which two of the inequalities are strict: $\omega(G) < \omega^*(G) < \omega^{ns}(G)$, but $\omega^{ns}(G) = 1$.


texts: Is [2-party d3-rolling with maximum probability 1/2] known to imply one-way functions?

texts:
Most things in complexity-based cryptography (for examples, see page 4) are known to imply

the existence of one-way functions, especially after this paper proved that implication for weak coin-flipping with any constant bias.  However, this paper shows a relativized world with non-trivial 2-round argument systems but no one-way functions, which makes we wonder about the

possibility of complexity-based cryptography, beyond ideal SNARKs, without one-way functions.

With that in mind, I initially thought about multi-party versions of honest-majority coin-flipping

with negligible bias, but discovered that there were too many possible specifications

for me to decide which of them to ask about.  (For example, are there secret channels,

is broadcast available, what are the requirements in case of abort?)

Accordingly, I'm instead asking about 2 parties choosing an element from {0,1,2}.

  Consider the 2-party functionality:

  If the parties are both corrupt or both honest then choose y uniformly from {0,1,2}.

  Otherwise, receive an element x of  {0,1,2}  from the

  adversary and choose y uniformly from  {0,1,2} - {x} .

  In either case, output y to both parties.

  Is it known that if there is a secure 2-party implementation

  of that functionality then one-way functions exist?

(Obviously, one doesn't need to care about what happens when both parties are corrupt.

Slightly less obviously, when both parties are honest, it suffices to make sure they get the same value, since the protocol could be modified to start with one party choosing an element of {0,1,2} uniformly at random and then at the end, adding that to the inner protocol's output mod 3.)


texts: Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence?

texts:
In the well studied problem of Hamiltonicity, several papers/theorems gave sufficient "degree conditions" for the existence of Hamiltonian path in a graph.

These include:

Dirac's theorem , 1952, which states that "A simple (undirected) graph with $n$ vertices ($n \geq 3$) is Hamiltonian if every vertex has degree $\frac{n}{2}$ or greater".
Ghouila-Houiri 's theorem, ("Une condition suffisante d’existence d'un circuit hamiltonien",1960), which generalized Dirac's result to directed graphs, showing that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian, where $\delta^+(G)$ is the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.
A theorem from Bang-Jensen and Gutin's book gave a stronger result, which imply that if $\forall v\in V: d_{in}(v)+d_{out}(v)\geq n$ then the graph is Hamiltonian.

The $k$-path problem is a simple generalization of Hamiltonicity asking whether a simple path on $k$ nodes exist in a graph.

  What would be the weakest sufficient "degree conditions" from a graph such that it is bound to contain a $k$-path?


texts: Most of the applications of Finite Model Theory I have seen are in graphs, using FMT one can prove that certain properties of finite graphs are not FO definable. I am interested in similar kind of applications of FMT in finite algebraic structures, namely in finite fields or finite groups? Are their properties of finite fields or groups which are not FO definable and can be proved using FMT? Reference to any book or research paper would be highly appreciated.


texts: There is theoretical evidence that the naive cartesian-product construction for the intersection of DFAs is "the best we can do". What about the concatenation of two DFAs? The trivial construction involves converting each DFA into an NFA, adding an epsilon-transition and determinizing the resulting NFA. Can we do better? Is there a known bound on the size of the minimal concatenation DFA (in terms of the sizes of the "prefix" and "suffix" DFAs)?


texts: Do good PCPs for NP give us good PCPs for the entire polynomial hierarchy?

texts:
The PCP Theorem states that every decision problem in NP has probabilistically checkable proofs (or equivalently, that there exists a complete and quasi-sound proof system for theorems in NP using constant query complexity and logarithmically many random bits).

The “folk wisdom” surrounding the PCP Theorem (ignoring for a moment PCP’s importance to the theory of approximation) is that this means proofs written up in strict mathematical language can be checked efficiently to any desired degree of accuracy without the requirement of reading the entire proof (or much of the proof at all).

I am not able to quite see this. Consider the second-order extension to propositional logic with unrestricted use of quantifiers (which I am told is already weaker than ZFC, but I am no logician). We can already start to express theorems which are not accessible to NP by alternating quantifiers.

My question is whether there is a simple, known way of ‘unrolling’ quantifiers in higher order propositional statements so that PCPs for theorems in NP apply equally well to any level of PH. It could be that this cannot be done – that unrolling a quantifier costs, in the worst case, some a constant part of the soundness or correctness of our proof system.


texts: Maximize Covering Minimizing the Overlap

texts:
I have this problem:

Given a collection of sets $S:\{S_{1},...,S_{k}\}$ where each set $S_{j}$ is a subset of $U:\{e_{1},...,e_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ such that I maximize the function $f(C)=|\cup_{\forall C_{j} \in C} C_{j}|$ and minimize the function $g(C)=\sum_{\forall C_{j},C_{i} \in C}|C_{i} \cap C_{j}|$.

I have found out a Integer Linear Programming formulation for this problem, now I'm wondering is this problem NP-Hard?  Does exist in literature a similar problem?

My formulation:

$max(\sum_{\forall e}e_{j} - k \sum_{\forall z}z_{j})$

$\forall e_{j} \in U: \;\;e_{j} \leq \sum_{\forall S_{i}\;s.t.\; e_{j} \in S_{i}}s_{i}$

$\forall e_{j} \in S_{j} \;s.t.\; e_{j} \in S_{k} \cap S_{t}:\;\;  z_{j} \geq s_{k}+s_{t}-1$

all variable in ${0,1}$, k is a constant to specify the malus for adding an overlap.

The problem formulated in this way can solve Maximum Set Packing. So it is NP-Hard.
Now I'm wondering what can be a good heuristic to find some solutions?
I'm trying a greedy algorithm that put at each step the elements with the maximum ratio of new covered elements over new intersections.


texts:
It is a major open problem whether $NL \subseteq SC$, or equivalently, whether directed reachability can be solved (simultaneously) in poly-logarithmic space and polynomial time. What is known regarding $SC \subseteq NL$?
It would show $L\subseteq SC \subseteq NL \subseteq P\cap polyL \subseteq P$, but can we anything else?


texts: Quantum PCP and hardness of simulating of Hamiltonians

texts:
I have a few questions about Quantum PCP conjecture:

What is the statement of the quantum PCP conjecture?
What implications would Quantum PCP theorem have for simulating of Hamiltonians?
Is it believed adopting Irit Dinur's proof of the classical PCP theorem is likely to lead to a proof of Quantum PCP conjecture?
What background is needed to read articles about the problem?

The copy of the question on MO


texts: Shortest paths when randomly scrambling a Rubik's cube

texts:
I saw a previous question about local maxima for the number of moves in a Rubik's cube solution, and I wondered what is known about the distribution of shortest paths when randomly scrambling a Rubik's cube.

  If I were to pick a (solvable) configuration at random, how far is it
  to the solved state?
  How many random moves does it take to sufficiently scramble the cube?

For the second question, I'm thinking of it as the mixing time, like for the Diaconis 7 shuffle result for a deck of cards. (Perhaps this is the wrong terminology?)

This is related to another question of mine about adversarially scrambling a Rubik's cube.

Edit: I accepted Marzio's answer, though I still wonder about the mixing time. Google revealed some results for particular finite groups, but I didn't see anything about Rubik's cube. Maybe one of these is applicable / can be ported over?


texts: Ordering of a DAG minimizing some definition of cost

texts:
Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k>i: (v_j,v_k)\in A\}|$.
The problem is: given a DAG, find a topological ordering with minimum cost.

In other words, for each $i$, I consider that a vertex that appeared before $i$ is pending if it still has one or more out-neighbours that did not appear yet, and I want to minimize the maximum number of pending vertices at any time.

It looks like some graph measures (say treewidth, etc.), but I didn't manage to find this in the literature. Has it been studied before?

I'd say it's almost-certainly NP-hard (although I don't have a proof)... would there be any approximation algorithm, or at least some smart heuristic?

Edit: for a little bit of context. This came up while I was trying to program a tool solving a completely unrelated string problem. To make things short: the graph models my input, and I need to compute a set of strings $\mathcal S(v)$ for each node $v$. To compute each $\mathcal S(v)$, I need to know $\mathcal S(u)$ for each node $u$ with an arc $u\rightarrow v$. In the end I'm only interested in $\mathcal S(v)$ for the targets of the graph. Now I want to improve the memory needs: the sets $\mathcal S$ are huge, so I want to keep only a minimum number of them in memory at any time: they correspond to the "pending vertices" defined above.


texts:
I have convinced myself of the following:

For every $(k,\epsilon^2\hspace{.005 in})$-strong extractor Ext, for every distribution $X$,
if $\;\; k\leq$ $\:H_{\infty}$$(\hspace{.01 in}X\hspace{.015 in}) \;\;$ then the probability over the seed $U$ that
the distribution of $\: \text{Ext}\hspace{.01 in}(\hspace{.01 in}X,U\hspace{.015 in}) \:$ is not $\epsilon$-close to uniform
is at most $\epsilon$.

  Are there any known
  explicit
  strong extractors that are known to handle seed reuse better than can
  be shown by using the above on a standard strong extractor?

What if each instance of "extractor" in the rest of this post was replaced with "blender"$\hspace{.01 in}$?


texts: Hard-looking algorithmic problems made easy by theorems

texts:
I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only.
(2) On the other hand,  it becomes easy, if you know some (not so standard) theorems.

The goal of this is to illustrate for students that learning more theorems can be  useful, even for those  who are outside of the theory field (such as software engineers, computer engineers etc). Here is an  example:

   Question:  Given integers $n, k, l, d$, does there exist an $n$-vertex graph (and if so, find one), such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?

Note that we require that the parameters are exactly equal to the given numbers, they are not just bounds. If you want to solve this from scratch, it might appear rather hard. On the other hand, if you are familiar with the following theorem (see  Extremal Graph Theory  by B. Bollobas), the situation becomes quite different.

  Theorem:  Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree  $d$, if and only if one of the following conditions is satisfied:
    $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,
   $1\leq 2d+2-n\leq k\leq l = d< n-1$
   $k=l=d=n-1.$

These conditions are very easy to check, being simple  inequalities among the input parameters, so the existence question can be answered effortlessly. Furthermore, the proof of the theorem is constructive, resolving the construction issue, as well. On the other hand, this result does not appear standard enough, so that you can expect everybody to know about it.

Can you provide further examples in this spirit, where knowing a (not so standard) theorem greatly simplifies a task?


texts: Identifying useless edges for shortest path

texts:
Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex $j$ in $G$ for a certain fixed aggregation function (for instance $+$ or $\max$).

I say that a subgraph $G'$ of $G$ (with same vertex set) is sp-equivalent to $G$ if $M_G = M_{G'}$. In other words, removing edges to go from $G$ to $G'$ does not change the length of shortest paths; the removed edges are not required for any shortest path.

In general there is no single sp-equivalent subgraph of $G$ that is minimal for inclusion. For instance, if $G$ is undirected and all edges have weight $0$, any spanning tree of $G$ is a minimal sp-equivalent subgraph (indeed, any edge in a cycle could be removed, but disconnecting a vertex pair obviously changes the distance). However I can still call edges of $G$ useless if they are in no minimal sp-equivalent subgraph, necessary if they are in all minimal sp-equivalent subgraphs (i.e., in their intersection), and optional if they are in some of them (i.e., in their union).

My first question is: Do these notions have a standard name?

My second question is: What is the complexity of classifying the edges of $G$ in this fashion, depending on whether $G$ is undirected or directed, and on the aggregation function?

(For instance, for $G$ undirected and for $\max$, the minimal sp-equivalent subgraphs are spanning trees of minimum weight, so at least if all edge weights are different the classification is easily computed by computing the unique minimum spanning tree, but in general I do not know how things work.)


texts: The implication of $ S(SAT)=2^{\Omega{(n)}} $ Conjecture (5.7 in Wigderson Book)

texts:
I started to read Avi Wigderson book Math and Computation, which get me excited about the following:

Conjecture 5.7. $
S(SAT)=2^{\Omega{(n)}}
$,
where $S$ denotes the size of the smallest Boolean circuits computing it's input, e.g. $SAT$ in the conjecture case.

I didn't find Theorem, Lemma, or anything related to the implication of this conjecture, so my questions are:

If Conjecture 5.7. is true, does it imply $P \neq NP$? since its circuits need at least $2^{\Omega(n)}$ to be constructed, which leads to exponential time algorithm, which means $SAT \not\in P$, recalling that $P = NP \iff SAT \in P$, right? any other implications? — SEE UPDATE.
If Conjecture 5.7. is false, what its implications?

UPDATE: I found the following theorem:

Theorem 7.7. If $SAT$ cannot be solved by circuits of size $2^{o(n)}$, then $P=BPP$.

An equivalent and more general result here Impagliazzo, Wigderson 1997. If the conjecture is true that implies $P=BPP$.


texts: Heuristics for the minimum-weight $k$-clique problem

texts:
Hello
Does someone have an idea for heuristics for the problem:

  Given undirected weighted(weights on edges) complete
  graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of nodes) having
  the minimum weight.

I have searched for minclique problem but it doesn't really answer my question.
Thank you in advance.


texts: Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

texts:
Let $k$ be fixed, and let $G$ be a (connected) graph. If I'm not mistaken, it follows from the work of Bodlaender [1, Theorem 3.11] that if the treewidth of $G$ is roughly at least $2k^3$, then $G$ contains a star $K_{1,k}$ as a minor.

Can we make the term $2k^3$ smaller? That is, does say treewidth at least $k$ already imply the existence of a $K_{1,k}$-minor? Is there a proof somewhere?

[1] Bodlaender, H. L. (1993). On linear time minor tests with depth-first search. Journal of Algorithms, 14(1), 1-23.


texts: Variant of Subset Sum Problem with Changing Bound

texts:
Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that
$$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$
$$s.t., \sum_{i\in S/\{t\}} a_i \leq k \cdot a_t,$$
where $a_t$ represents the smallest one of subset $S$.

Note that $a_t$ is the smallest of set $S$ and may be different for different set $S$. I am wondering whether this problem is still NP-complete. Any comments or suggestions will be very appreciated.


texts: Shortest string in the intersection of regular languages

texts:
Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string

Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ending states) that uses a 4-letter alphabet.

Each maze hence directly corresponds to a regular language. The intersection of all the regular languages is also a regular language with each string in it representing a valid "universal exit string". And we now have to find the shortest such string.

So is there any algorithm, construction, etc that can help us find the shortest such string?

I found this paper by Thomas Ang on googling but couldn't find anything in it I could use in the problem (I could be mistaken).

I'm just making this post to find out if any already existing results/approaches in theoretical CS can be used to solve the problem.

Thanks

P.S. There's an unofficial bounty on the question if it tempts anyone.


texts: Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

texts:
Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The family of recognizable subsets $\operatorname{REC}(M)$ as the family of subsets $L \subseteq M$ such that $L = \varphi^{-1}(\varphi(L))$ for some monoid morphism $\varphi : M \to N$ with $N$ finite.

Now, a McKnight's Theorem says that $M$ is finitely generated iff $\operatorname{REC}(M) \subseteq \operatorname{RAT}(M)$. And by the famous theorem of Kleene, if $M = \Sigma^{\ast}$ for some finite set $\Sigma$, then $\operatorname{REC}(M) = \operatorname{RAT}(M)$. But what about the inclusion $\operatorname{RAT}(M) \subseteq \operatorname{REC}(M)$?

Do you know any example of a  monoid such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$?


texts: Can Polar Codes (or any other efficient codes) reach the second order capacity?

texts:
In channel coding, it is known (e.g. Yury Polyanskiy's thesis, and the arxiv article A Tight Upper Bound for the Third-Order Asymptotics of Discrete Memoryless Channels) that certain codes, for example polar codes, can reach the Shannon limit for large enough block lengths $n$. However, for finite $n$, the best theoretically possible codes are known to satisfy

$$\log M \leq n C - \sqrt{n V}\, \Phi^{-1}(1-ε) + \frac{1}{2} \log n + O(1),$$

where $M$ is the size of the code, $C$ the capacity of the channel, $V$ the dispersion of the channel, and $ε$ the required (average or maximum) error.

Is it known how Polar codes (or any other codes) compare to this fundamental bound? The bound can be achieved using random codes, but I was wondering if there are any efficient codes that come close.


texts: What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

texts:
It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.

There is also a parameterized algorithm for computing a $\alpha$-approximation of VC (for $\alpha\in[1,2]$).

Considering the standard (non-parameterized) problem and non-polynomial algorithms:

What is the fastest known algorithm for computing a $1.99$-approximation?


texts: About properties of adjacency matrix when a graph is planar

texts:
1- Is there any specific properties for adjacency matrix when a graph is planar?
2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?


texts: Example of an context-sensitive language with a specific number of words of length $n$

texts:
Let $s_L(n)$ denote the number of words of length $n$ in $L$.
For context-free languages it is known that $s_L(n)$ is either polynomial or exponential.
For context-sensitive languages this is probably not true and I would like to study counterexamples.
I am interested in an example of a context-sensitive language that has $s_L(n)=\Theta(r^{(n^\delta)})$ for a real $r>1$ and $\delta<1$ or $s_L(n)=\Theta(r^{(log^c(n))})$ for $c>1$.


texts: VC dimension of polynomials (in one variable) of degree d

texts:
Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$.

I am searching for ideas that can prove the above claim (and perhaps generalize to many variables as well, though that seems too much to hope for).

Any approach, even an incomplete one, will be appreciated.

To define the problem properly: Given a plane (2D, x and y coordinates) what is the size of maximum set that can be shattered if you can use classifying functions that are polynomial ($y=p(x)$) of degree at mode $d$, and you are free to choose which side of the curve you want to label positive.

For example, label (x,y) as positive iff $y > x^2 +5x +9$.


texts: Problem of graph bi-partition (related to graph isomorphism)

texts:
I am considering the following problem:

  Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$
  Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, and $G[V\backslash V_1]$ is isomorphic to $H_2$?

It is clearly at least as hard as Graph Isomorphism (take the empty graph for $H_2$), and in NP (certificate: $V_1$ and the isomorphisms). Intuitively, it should be easier than subgraph isomorphism, since here we know what the "complement" looks like.

I have several questions regarding this:

Has it been studied / does it have a name?
If yes, is it NP-hard?
If still yes, has it been studied on restricted graph classes?


texts: closure properties of IP(2pfa) and AM(2pfa)

texts:
IP(2pfa) and AM(2pfa) are the classes of languages recognized with bounded error by private and public coin versions, respectively, of interactive proof systems with verifiers that are probabilistic finite automata with a two-way input head.

Are any closure properties of these classes known?


texts: Measuring the connectedness of a graph, and applying it to NP problems

texts:
I'm looking for a way to measure how interconnected a graph is.  It's well known that graphs can be broken down into connected components.  It seems, though, that even in the cases where the graph is made of only one connected component, we can measure how interconnected that component is.  Is it "almost" two components (if we would remove a small number of edges)? What is the correlation between edges (that is, if vertices A and B are each connected to C, is there a higher probability that A and B are themselves connected).  I don't know how to define this measure properly, but I'm sure there are existing measures already defined.

It would seem to me that this would be a great way to measure the difficulty of an instance of the SAT problem.  Representing variables as nodes and being in the same clause as edges, it would seem the difficulty of the problem is related to the interconnectedness of the graph.


texts: Regarding Pfaffian Methods in Counting and Combinatorics

texts:
Recently, I was going over an introduction to Holographic Algorithms. I came across some combinatorial objects called Pfaffians. I do not really know much about those at the moment and came across some surprising uses they can be put to.

For instance, I came to know that they can be used to efficiently count the number of perfect matchings in planar graphs. Also, they can be used to count the number of possible tilings of a chessboard using 2*1 tiles. The tiling connection seemed very curious to me and I tried searching for more relevant materials on the web but in most places I merely found just one statement or two about the connection and nothing else.

I just meant to ask if someone could suggest some reference to relevant literature as that would be really great and I am looking forward to study some related materials.


texts: Separations between testing and tolerant testing for (natural) classes of functions?

texts:
Note: I am considering here property testing in the query model, with regard to Hamming distance. (So, for instance, of Boolean functions—I'm phrasing it that way below.) I am in particular not interested in separations in distribution testing.

The property testing model (for Boolean functions) asks for algorithms that, for a fixed property $\mathcal{P}\subseteq 2^{2^n}$, are provided with a proximity parameter $\varepsilon \in (0,1)$ and query access to an arbitrary function $f\colon \{0,1\}^n \to \{0,1\}$, return either $\textsf{accept}$ or $\textsf{reject}$, such that:

if $f\in \mathcal{P}$, then the algorithm returns $\textsf{accept}$ with probability at least $2/3$;
if $d(f,\mathcal{P}) > \varepsilon$, then the algorithm returns $\textsf{reject}$ with probability at least $2/3$;

where $d(f,\mathcal{P}) \stackrel{\rm def}{=} \inf_{g\in \mathcal{P}} d_H(f,g)$ is the minimum (Hamming) distance between $f$ and a function satisfying the property.

Tolerant testing (as introduced by Parnas, Ron, and Rubinfeld) relaxes the first (completeness) guarantee from $d(f,\mathcal{P}) = 0$ to $d(f,\mathcal{P})\leq \varepsilon'$, where $0\leq \epsilon' < \varepsilon$ is another input to the algorithm. In particular, tolerant testing is at least as hard as testing, by choosing $\varepsilon' = 0$.

However, I am aware of only very few separations between testing and tolerant testing which show the latter to be actually harder, for "natural" properties of functions $\mathcal{P}$. (Of course, here the word "natural" is fuzzily defined; I guess we recognize what it means when we see it.)

An example (for contrived properties) was given by Fischer and Fortnow [1], where they provide a property with $O_{\varepsilon,\varepsilon'}(1)$-query testers, while every tolerant tester requires $n^{\Omega(1)}$ queries. This is the extent of my knowledge regarding published or available results.

  Is there any such separation known for an (arguably) natural property of Boolean functions? If not, of functions $f\colon \{0,1\}^n \to \mathbb{R}$, or $f\colon [n]^d \to \mathbb{R}$?

[1] Tolerant Versus Intolerant Testing for Boolean Properties, Eldar Fischer and Lance Fortnow. Theory of Computing, 2006. http://theoryofcomputing.org/articles/v002a009/


texts: Local Hamiltonian and combinatorial search problems

texts:
I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination search problem. I am not getting the intuition behind this. Let me quote from the second paragraph of the chapter.

  There is hope that there may be combinatorial search problems, defined
  on $n$ bits so that $N = 2^n$ , where for certain “interesting” subsets of
  the instances the run time of the Quantum Adiabatic Algorithm grows
  sub-exponentially in $n$. A positive result of this kind would greatly
  expand the known power of quantum computers.

I understand that it is possible to implement the Grover's algorithm as an adiabatic quantum algorithm. What I don't understand is the special relation between local Hamiltonian and combinatorial search problems. Any clue?


texts: Algebraic dependence of roots of irreducibles over a finite field

texts:
I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math.stackexchange.com/questions/1844975/dependence-of-algebraic-elements-in-a-finite-field

Lets work over the finite field $\mathbb{F}_p$ for a prime $p$. Consider a monic irreducible polynomial $f(X)=X^3+aX^2+bX+c$ in $\mathbb{F}_p[X]$. Let $x$ be a root of $f(X)=0$ (say, in the closure of $\mathbb{F}_p$). Consider another different monic irreducible polynomial $g(Y)=Y^3+AY^2+BY+C$ in $\mathbb{F}_p[Y]$. Let $y$ be a root of $g(Y)=0$ again in the same closure.

Now we know that the field $\mathbb{F}_{p^3}$, realized explicitly as the extension $\mathbb{F}_p[X]/<f(X)>$ or $\mathbb{F}_p(x)$ contains a root (all three distinct roots, actually) of the irreducible $g(Y)$. This is because $\mathbb{F}_p(x)$ is the splitting field of $X^{p^3}-X$ which includes $g(X)$ as a factor.
So we know that the root $y$ can be expressed as
$$y=\alpha x^2+ \beta x +\gamma$$
for some $\alpha, \beta, \gamma \in \mathbb{F}_p$.

My question is: Is there an efficient algorithm that given as input the prime $p$ and the irreducible polynomials $f$ and $g$, computes $(\alpha,\beta,\gamma)$ as output?
Though in my question, I am first interested in degree $3$, the same problem arises for higher degree too. This is easy to do when $f$ and $g$ are quadratic, as we can use specific properties of quadratic residues.

Of course, since we know that such a solution $(\alpha,\beta,\gamma)$ exists, we can simply substitute $\alpha x^2+ \beta x +\gamma$ for $Y$ in $g(Y)=0$ and solve the equation. But is there a better way?

The converse problem, of finding the irreducible which has $\alpha x^2+ \beta x +\gamma$ as a root can be solved simply by elimination, and the answer is simply a resultant polynomial. So considering that this converse problem has a neat construction, I was hoping that the above problem also has some neat algebraic formulation or efficient algorithmic solution.


texts: Boolean functions computed approximately by k-CNFs and l-DNFs and the depth of trees

texts: A well-known fact is that if a function f is computable by a k-CNF and an l-DNF then it can be computed by a tree of depth at most kl. Long time ago I heard the problem what happens if the CNF and DNF only compute f with some small error $\epsilon>0$. Is there a shallow tree computing f with a small error? (I am not sure that the problem was posed in this way, but this is the question I am interested in.)


texts: What is the Quantum Cheshire Cat experiments' import to Quantum Computing?

texts: What is the significance of the Quantum Cheshire Cat to Quantum Computing? To recap, the Quantum Cheshire Cat experiment proved it was possible to separate a neutrons' spin from the neutron. Or, in other words a particle could lose its properties in special circumstances. What would the implications be to quantum computing? Does it mean measurements to the system be more accurate, as the properties of the system are isolated from external influences? When reasoning about this experiment by way of Quantum Computing, would one look at the results of the experiment with Quantum Communication (one could always look the fidelity, or even capacity of the quantum channel as enhanced) as a model or any other models would be apt to study the experiments' effects?


texts: Simplification of Presburger formulas in practice

texts:
I have formulas in Presburger arithmetic (with initial ∀, but I can apply quantifier elimination so they are quantifier-free) that are fairly complicated, yet, in many useful cases, are equivalent to very simple formulas such as conjunctions of simple arithmetic constrains (e.g. p>=-1, p<q, y>=q, y<n, n>=2 for a quantified formula taking up a whole screen page).

Is there any good simplification method for such formulas? (preferably in an off-the-shelf implementation)


texts: $\ell_\infty$ partially enclosing ball problem

texts: Suppose I have $n$ points in $\mathbb{R}^d$ endowed with the $\ell_\infty$ metric, and I wish to find a minimum-diameter ball that contains some $k$ of these points. What is known about this problem? Easy/hard? Approximations? Heuristics?


texts:
As far as I know, it is not known whether $ \mathsf{NP} \subseteq \mathsf{IP(2pfa)} $, where $ \mathsf{IP(2pfa)} $ is the class of languages having interactive proof systems with some two-way probabilistic finite automata verifiers (Finite state verifiers I: the power of interaction by Dwork and Stockmeyer).

Does anybody know any progress on this issue?

I know the following results:

$ \mathsf{IP(2pfa)} $ contains some NP-complete languages, where the verifier runs in poly-time.
$ \mathsf{P} \subseteq \mathsf{IP(2pfa)} $, where the verifier runs in exp-time.
$ \mathsf{DTIME(2^{O(n)})} \subseteq \mathsf{IP(2pfa)} $, where the verifier runs in double-exp-time.


texts: What is the most efficient algorithm for deciding if an element is the least in its orbit?

texts:
Given a group $G$ acting on a set $X$ with a total order $\leq$ and an $x\in X$, what is the most efficient algorithm for deciding whether or not x is the least element in its orbit, in other words, deciding if $ min(Gx) = x$?

My motivation comes from SMT solving where there has been some interest in automatically breaking symmetries. Adding symmetry breaking predicates often result in a large clause set therefore I am interested in the possibility of handling this as a lazy theory propagation.

The above description is perhaps too general, and as noted by sid, NP-hard. A possible simpler task is, given a group of permutations of strings of length $n$ encoded as a set of generators and a string $x$ of length $n$. What is the most efficient algorithm for deciding if that string is the lexicographically smallest in its orbit?


texts: From edge-disjoint paths to independent paths

texts:
Let $\mathcal{G}_k$ denote the set of all graphs that contain two vertices $x,y$
and $k$ edge-disjoint $x-y$ paths.

Define $f(k)$ to be the maximum such that for every graph $G\in \mathcal{G}_k$
there are two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths in $G$.

Here, a set of paths is independent if none contains an internal vertex of another.

Are any lower bounds for $f(k)$ known in the literature?

In particular, I need $f(3)=3$ in an algorithm where I need to find some obstructions in a graph.
This is not hard to prove, but I'm wondering whether it is known in the literature, maybe as a special case of a more general theorem.

As a different formulation, how large can you make $f(k)$ in the following statement?

  If $G$ is an undirected graph containing two vertices $x,y$ and $k$ edge-disjoint $x-y$ paths, then $G$ contains two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths.


texts: Giving a finite collection of infinite words "complex" enough with respect to automata measure

texts:
We consider acceptance by Büchi automata. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ of infinite words, such that for every other infinite word $\eta$ there exists some $\xi_i$ such that for every Büchi automaton $\mathcal A$ with
$$
 |L(\mathcal A) \cap \{\xi_i, \eta\}| = 1
$$
(i.e. the automaton separates both words: accepts one, but not the other) then $\mathcal A$ must have at least $n$ states?

Observation. One neccessary condition on the collection of infinite words $\{\xi_1, \ldots, \xi_k\}$: for a given $n$ we must have at least $2^{n-2}$ of them ($k \ge 2^{n-2}$), i.e. one for each prefix of length $n-2$, for otherwise if some prefix $u \in X^{n-2}$ is not among the finite collection, then we can separate $u1^{\omega}$ easily by an automaton having fewer then $n$ states from every word in $\xi_1, \ldots, \xi_k$, simply read upon the first position $i \le n-2$ where it differs from a given $\xi_j$ and then reject or accept according to the sign there, which could be achieved by a Büchi automaton with $i+2$ states.

But besides this observation, I do not see if this is possible?

Motivation: If we define
$$
 d(\xi, \eta) = 1/2^n
$$
where $n := \min\{ |\mathcal A| \mid |L(\mathcal A) \cap \{\xi,\eta\}| = 1 \}$ for $\xi \ne \eta$, and $d(\xi,\xi) := 0$, then this gives a metric, and the above question asks if the resulting metric space is totally bounded.


texts: Is there a general theory for why certain algorithms are inefficient in high-level languages?

texts:
First of all, I apologise off the bat for my mangling of CompSci language. I have no real training or background in computer science or mathematics.

I've been wondering lately whether there's a 'general' explanation for the inefficiency of high-level languages in performing certain kinds of algorithms - from simple cases like the massive performance improvement in C over, say, Python, when looping over a set, up to complex mathematical algorithms.

Is it purely a quantitative matter - C is more efficient because it's not doing weird magic behind the scenes and the programmer directly interacts with main memory? And because it's not doing things like interrupts for garbage collection and other general housekeeping like a high-level language might?

Or is there some deeper ontological explanation for this? Is there some qualitative property of a low-level procedural language (or, at times, of a functional language) that makes it possible to express and compute a problem efficiently? Or is it simply a matter of brute resource and CPU cycle efficiency?