texts: The flaw in Bellare-Rogaway (1995) model on authenticated key exchange

texts:
Background:
In their 1995 paper, Bellare and Rogaway describe a formal model for authenticated key exchange in a tripartite setting. In this setting, each client has a shared key with a central server, which is willing to help in key distribution between any two mutually distrustful clients. This model is reminiscent of the security settings for Needham-Schroeder protocol, Kerberos and Active Directory.
For brevity, let's denote the Bellare-Rogaway-1995 model by "BR95."
The adversary in the BR95 model is a probabilistic polynomial-time algorithm, which has total control over the communication between each pair of parties. Moreover, the adversary
can mount a number of attacks on any single party. The attacks include revealing the session key, corrupting a party, and a special "TEST" attack, which is described next.
When the adversary has finished with experimenting different attacks on the parties, it makes a final TEST attack. The attack is restricted in several ways; for instance, the adversary cannot mount the TEST attack on a corrupted party, or on a party whose session key is already revealed. (Nor can the adversary mount the test attack on the partner of such party.)
On issuing the TEST attack, the adversary is given either of the following, each with probability 1/2:

The session key of the party on which the TEST attack is mounted; or
A random string of the same length as the session key.

The idea is that the adversary must be unable to distinguish the above two cases with advantage more than negligibly over 1/2.

The Flaw
In another paper, Bellare, Pointcheval, and Rogaway write:

Soon after the appearance of [BR95], Rackoff came up with an example showing how the definition given in that paper was not strong enough to
guarantee security for certain applications using the distributed session key. The
authors of [BR95] traced the problem to a simple issue: they had wrongly made the
restriction that the TEST query be the adversary's last. Removal of this restriction
solved the problem. This minor but important change in the definition of [BR95],
made in 1995, has since been folklore in the community of researchers in this
area, and is explicitly incorporated into our current work.

Along the same lines, Shoup explains:

We have taken the opportunity here to correct a serious flaw that appears in [BR95,...] that was pointed out to the authors of [BR95] by Charles Rackoff. In the formulation in [BR95, ...], the TEST operation is only allowed to be performed at the very end of the adversary's execution, whereas we have allowed it to occur at any time.

Shoup then tries to pinpoint the flaw on a contrived version of a protocol called "DHKE-1" (designed by himself). However, the contrived version is too "non-standard" for me to understand. Specifically, it includes the operation (or attack) core dump, which is not compatible with the attacks listed in the BR95 model.

Question
Could you please illustrate the flaw in the BR95 via an example, where disallowing the TEST attack in the middle of execution can result in a false proof of security?


texts: What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

texts:
Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" complexity aims to refine this qualitative distinction into a quantitative guide as to the exact time required to solve problems. More details can be found here: http://simons.berkeley.edu/programs/complexity2015

Here are some important hypotheses:

ETH: $3$-$SAT$ requires $2^{\delta n}$ time for some $ \delta > 0$.

SETH: for every $\varepsilon > 0$, there is a $k$ such that $k$-$SAT$ on $n$ variables, $m$ clauses cannot be solved in $2^{(1-\varepsilon)n}~poly~m$ time.

It is known that SETH is stronger than ETH and they both are stronger than $P \neq NP$,and both stronger than $FTP\neq W[1]$.

Four other important conjectures:

3SUM Conjecture: 3SUM on $n$ integers in $\{-n^3,…,n^3\}$ requires $n^{2-o(1)}$ time
OV Conjecture: Orthogonal vectors on $n$ vectors requires $n^{2-o(1)}$ time.
APSP Conjecture: All Pairs Shortest Path on $n$ nodes and $O(\log n)$ bit weights requires $n^{3-o(1)}$ time.
BMM Conjecture: Any "combinatorial" algorithm for Boolean matrix multiplication requires $n^{3-o(1)}$ time.

It is known that SETH implies the OV Conjecture (Ryan Willams, 2004). Besides Ryan’s proof that SETH $\implies$ OV Conjecture, there are no other reductions relating the conjectures known.

My question: Do you know other related hypotheses or conjectures in this area? What are the relationships between them?

Acknowledgement: results listed are from the slides of  Virginia Vassilevska Williams, she also gave me partial answers to this question.

Link to slides: http://theory.stanford.edu/~virgi/overview.pdf


texts: Can we infer the next player in chess from the current board configuration?

texts:
Presume that a program memory only includes the current state for instance of a chess board. Does it need the variable which player, black or white, has the next turn to move or is it redundant recognizing the state?
Clearly its redundant during the first moves and then chess has so many combinations that there are combinations that can't guarantee that its deducible from just the state whether white or black has the next move, it needs that variable that wasn't needed during the first moves. How can I know the existence or non-existence of an algorithm in this case to know how the state went from deterministically knowable whether white or black has the next move to a state later in the game where the only possibility appears to keep a side variable to know whether white or black has the next move?
Is the logical consequence that I can't find a method to predict something like "making this move must activate a new boolean variable."
I'm trying to answer whether there is a method to know or just practically using the boolean variable blackHasNextMove to also include the information who is next to move for a chess game and there might be no method but in that case how do I prove that there is no method?.
Edit:
I'm asking how to know if changing a state from computable to unknown has an algorithm and I'm very thankful you even brought up the idea of time bounds for a solution using ordo notation.


texts: Minimum Number of Adjacent Swaps to Sort Numbers on a 2D Grid

texts:
Assume that we have $N$ numbers (labeled from $1$ to $N$) that are placed on a 1D (linear) array. For example, for $N=5$:

If we want to sort these numbers with the minimum number of adjacent swaps (i.e., by only swapping adjacent numbers), then we can use bubble sort to find the solution. For instance, the aforementioned placement can be sorted with 5 adjacent swaps:

     Initial placement:   3 - 1 - 5 - 4 - 2
After swapping 3 and 1:   1 - 3 - 5 - 4 - 2
After swapping 5 and 4:   1 - 3 - 4 - 5 - 2
After swapping 5 and 2:   1 - 3 - 4 - 2 - 5
After swapping 4 and 2:   1 - 3 - 2 - 4 - 5
After swapping 3 and 2:   1 - 2 - 3 - 4 - 5

The question, however, is if the numbers are placed on a two dimensional grid, how we can find the minimum number of adjacent swaps in order to sort the numbers? Please assume that the ordering of numbers on the 2D grid is based on the snake-like indexing (as shown below).


texts: Is the concept of the Turing Machine derived from automata?

texts:
I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?

I didn't know the answer of course, but I'm curious to find out. The Turing Machine is basically a slightly more sophisticated version of a Push-Down Automata. From that I would assume that the Turing Machine was derived from automata, however I have no definitive proof or explanation. I might just be plain wrong... perhaps they were developed in isolation.

Please! Free this mind from everlasting tangents of entanglement.


texts: Problems that reduce to or are abstracted by the learning juntas problem

texts:
What problems are either abstracted by or reduce to the learning juntas problem?

(An example of a real-world problem abstracted by the learning juntas problem is the Identification of genetic loci participating in disease penetrance.)

Bonus points if the total number of attributes is very large, the number of juntas is small, and the problem permits active queries.

I'm asking because I have reason to believe that this algorithm, or one like it, may be of service.


texts: What is the fastest algorithm for calculating nth term of Fibonacci sequence?

texts:
If we exclude methods that include precalculating of all Fibonacci numbers up to a sufficiently large number of n what would be the fastest  algorithm for calculating nth term of Fibonacci sequence ?

I guess that Iterative and Matrix algorithms should be faster than Analytic and Recursive algorithms , ( see this paper ) .

On this page I have found five different algorithms . According to author the fastest is a Matrix algorithm that uses  O(log n) arithmetic operations .


texts: I have seen that there exists $d$-left regular bipartite graphs. My question is do there exists $d$-regular bipartite expander graphs in which both the degree of the left and the right vertices is exactly equal to $d$? If yes, is there any constructive proof for such graphs and what is the expansion factor? Kindly provide a reference as well.


texts: Face-splitting product of two Vandermonde matrices: When is is invertible?

texts:
Let $A$ and $B$ be two $n^2 \times n$ Vandermonde matrices with coefficients $\alpha_1,\ldots,\alpha_{n^2}$ and $\beta_1,\ldots,\beta_{n^2}$. Let $M$ be the face-splitting product of $A$ and $B$, that is, the $n^2 \times n^2$ matrix whose $(i,kn+l)$ entry is $A_{i,k+1} \times B_{i,l} = \alpha_i^{k} \beta_i^{l-1}$ for $0 \leq k \leq n-1$ and $1 \leq l \leq n$.
Question: When does $M$ have full rank? Or, alternatively, what is the determinant of $M$ as a function of the $\alpha$s and $\beta$s?
I have tried to compute the determinant as one usually does with a Vandermonde matrix but this quickly becomes very messy, and so I was wondering if there was a simpler way of obtaining that.
Edit: Actually the answer in the special case where $\beta_i = \alpha_i - 1$ for all $1 \leq i \leq n^2$ would be sufficient for my needs.
(Just to give some context, I am trying to show that a certain problem is #P-hard; I can do polynomial interpolation from counting the number of perfect matchings of a graph, but I end up on a matrix that is similar to $M$ and now I need it to be invertible.)


texts: Generalization of Dilworth's theorem for labeled DAGs

texts:
An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth's theorem in partial order theory, it is known that if DAG has no antichain of size $k \in \mathbb{N}$, then it can be decomposed in a union of at most $k-1$ disjoint chains, i.e., directed paths.

Now, I am interested in labeled DAGs, i.e., DAGs where each vertex $v$ carries a label $\lambda(v)$ in some fixed finite set $\Sigma$ of labels. Given an antichain $A \subseteq V$, I can define its labeled size as the minimal number of occurrences of the labels of $\Sigma$ in $A$, namely, $\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$. Is there an analogue of Dilworth's theorem in this context? In other words, if I assume that a DAG has no antichain of labeled size $k \in \mathbb{N}$, what can I assume about its structure? Can I decompose it in some special way? I am already puzzled by the case of $\Sigma = \{a, b\}$, but also interested in the case of a general finite label set.

To visualize this for $\Sigma = \{a, b\}$, saying that $G$ has no antichain of labeled size $k$ means that there is no antichain containing at least $k$ vertices labeled $a$ and $k$ vertices labeled $b$; there can be arbitrarily large antichains but they have to contain only $a$ elements or only $b$ elements, up to $k-1$ exceptions at most. It seems that disallowing large antichains should enforce that the DAG essentially "alternates" between parts of large width for $a$-labeled vertices, and large width for $b$-labeled vertices, but I have not been able to formalize this intuition. (Of course, a suitable structural characterization must talk about the labels of vertices in addition to the shape of the DAG, because already for $k \geq 1$ and on $\{a, b\}$ the condition is satisfied by completely arbitrary DAGs whenever all vertices carry the same label.)


texts: K-NN or matrix factorization for discovering correlated features?

texts:
I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature.  "Similar" users should be clustered together in a way that underlying strongly correlated features can be easily discovered.  A few other requirements:

The number of clusters is unknown
The runtime execution time is not a concern
The number of users can be on the order of 100,000 and number of features around 50

There are a number of clustering techniques, from KNN, k-means, matrix factorization, even PCA, but many seem to hide the underlying correlations that tie the users together.  Any advice?


texts:
In the wikipedia article on bin-packing it is stated that

  A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could occupy less space when packed together than the sum of their individual sizes. This variant is known as VM packing (Sindelar et al. 2011) since when virtual machines (VMs) are packed in a server, their total memory requirement could decrease due to pages shared by the VMs that need only be stored once. If items can share space in arbitrary ways, the bin packing problem is hard to even approximate.

I checked the article of Sindelar et al., where it is in fact shown that a variant of knapsack with overlapping items (called VM-maximization if several knapsacks are allowed, however, the reduction uses only one knapsack) cannot be approximated under complexity theoretic assumptions (Theorem 3.1.3). The complexity of approximating the aforementioned bin packing variant is stated as an open problem.

Question: Is there known more about the complexity of approximating the VM Packing Problem by now?


texts: Limits of parallel computing with local connections?

texts:
There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can only communicate locally with their neighbors (let's say on a hex grid in 2D - not arbitrary distance connections), how will time complexities of algorithms change and which algorithms will profit and which will never be fast enough?

Let's assume the number of processors is allowed to scale up as O(N). Probably many physics simulation can get a significant boost, however, some problems might require complex interaction between all parts of the data such that the time complexity cannot get below some limit. Are there results for this kind of problem?

PS: I have general math and computation knowledge, but I will try to understand technical details as much as possible :)


texts: Formal Representation of Haskell Data-Types

texts:
I come from Haskell programming and currently writing my (Diploma/Master) thesis. I'm having trouble finding a formal/mathematical notation for a Haskell data-type.

The Haskell data type is:

data ARE = ARE [(ARF, ARF)] [ARF]   -- Haskell form
type ARE = ( [(ARF, ARF)], [ARF] )  -- alternate form

An ARE is an affine randomized encoding and an ARF is an affine randomized function. You can think of an ARF just as an abstract entity, just like a field or group element. My problem is how to formally notate a definition for an ARE.

First, I'll try to describe what an ARE is in english: An ARE is a tuple (in the "alternate form", in my Haskell program it's represented as in the "Haskell form") containing:

a list (not a set since it could contain duplicates) containing tuples. Each of these tuples is just two ARFs
a list of ARFs

What I'm looking for is a formal notation of such an ARE.

(edit: removed nonsense notation proposal...)

About the expected audience (and their knowledge domain) of my thesis: I will provide Haskell code, but the entire thesis should be understandable by someone who is not a programmer (and in particular no Haskell programmer). The reader will need some knowledge in cryptography, computer science (but not programming) and basic mathematics (some field theory, especially the finite fields $\mathbb{F}_{2^n}$). In the text I simply want to tell the reader what AREs are and how I transform general expressions to AREs.


texts: Permutations with forbidden subsequences

texts:
Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition.
Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a permutation
$\pi:[n]\rightarrow [n]$ of the set $[n]$ avoids $p$ if there is no k-tuple
of integers $i_1<i_2<...<i_k$ such that
$$\pi(i_1) = p_1, \;\;\pi(i_2)=p_2,\;\;  ...,\;\;\pi(i_k) = p_k.$$

For instance, if $n=5$ then the permutation $12453$ avoids $134$ as a subsequence, while the permutation $\mathbf{1}2\mathbf{3}5\mathbf{4}$ does not.

Question: Let $k$ be a constant. Given a set $S\subset C(n,k)$ of $k$-tuples, find a permutation
$\pi:[n]\rightarrow [n]$ that avoids each $k$-tuple in $S$.

Is there an algorithm for this problem that is polynomial in $|P|$ and $n$? Here $n$ is given in unary. An algorithm running in time $n^{f(k)}|P|^{g(k)}$ would be fine.
Or is this problem NP-complete?

Any references for this problem, or suggestions of algorithms are welcome. Note that the notion of permutation avoiding subsequence defined above is not the same as the notion of permutation avoiding pattern  where only the relative order of elements is important, and which seems to be well studied in combinatorics.


texts: How to generate graphs with known optimal vertex cover

texts:
I'm looking for a way to generate graphs so that the optimal vertex cover is known. There are no restrictions on the number of nodes or edges, only that the graph is completely connected.

the idea is to generate a graph that's not easy to find the optimal vertex cover, to be able to test different heuristics on it

I found the paper Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, No. 2 (Feb., 1988), pp. 153-159 for generating TSP with known optimal, alas I cannot access it.

Is there a known algorithm?


texts: Why does Dinur's proof of the PCP theorem fail to work for unique games?

texts:
What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap amplification / alphabet reduction while preserving the fact that the problem is a unique label cover instance?
Obviously, the proof still holding essentially unchanged would contradict the fact that we know there is a subexponential time algorithm for unique games, unless all of NP has subexponential time algorithms. However, I'm trying to explicitly understand the critical step where the argument fails.
Since I'm trying to understand to the heart of the issue, I'd prefer to disregard "minor" technical assumptions like ensuring the graph is d-regular, an expander, etc. unless those are actually the main thing preventing the proof from going through.


texts: Extending Hindley-Milner to type mutable references

texts:
I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let is used to declare a variable as opposed to a bare assignment.

However, I'm now trying to add mutability into the language, specifically in the syntactical form

let mut x = 1

where x is now a rebindable variable. This is effectively the same as

let x = ref 1 in ...

in ML, but my type-checker inserts the dereference operator (!) automatically. So something like ref is never directly used. Any instance of x has a ! applied to it. So, if you do

let mut x = 1
let y = x
x = 2

Then x is still rebindable, and has the value of 2, but y is immutable and has the value 1.

I am having great difficulty extending my implementation of Hindley-Milner 's unification to support mutable references. The main paper I was reading was Standard ML-NJ Weak Polymorphism and Imperative Constructs by John Mitchell, as I was hoping to get an inference algorithm that had similar behavior to OCaml's weak polymorphism implementation.

This paper is pretty good and explains most things well enough, but it lacks a formal description of the type inference algorithm for its language. Are there any good resources on extending Hindley-Milners unification algorithm, that is, not the type system, with mutable references. I know the two go hand in hand, but I'm just having a really hard time jumping from the type inference rules from the paper I'm using to extending my implementation. I'm wondering if there is at least a description of an algorithm that unifies types in a language that supports mutable references.

Lastly, I saw this question here asking something similar. The asker states "I only find solutions for a language with mutable references but without genuine imperative control structures", I would like to see those references! I completely understand how to extend my language to have imperative control structures once I get my mutable references working, but this is where I am stuck now.


texts: Degree restriction for polynomials in $\mathsf{VP}$

texts: why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?


texts: Descriptive complexity characterization of TimeSpace classes

texts: Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?


texts: Partition graph into 2 or more claw-free subgraphs

texts: Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?


texts: Decomposition of safety and liveness properties

texts:
In Alpern,Schneider 86 is described how to extract the automata that recognize safety and liveness properties from a Buchi automaton $m$. This shows that any property rapresented by a Buchi automaton is equivalent to the intersection of these two automata.
In particular, the automata for the safety properties is represented by making all states of $m$ accepting. The question is: although it is a Buchi, can this automaton be determinized by using the subset construction?


texts: Process modeling with fine-grained notions of location

texts:
Is anyone aware of any process algebraic (or related) formalisms that capture fine-grained location information?  I'm familiar with ambients and bigraphs, which obviously have a location model, but what about attempts to model more concrete location information, such that the location of some agent is expressed within some (real or virtual) coordinate space?

It seems to me that it would be possible to take some existing formalism and enrich it with constructs to model location at some appropriate level of abstraction, but I would hate to reinvent the wheel needlessly if this is reminiscent of previous efforts.

As background, the application domain is essentially biological modeling where the traditional notions of location used in this domain to govern where interactions can occur are not fine-grained enough to capture the properties of interest.


texts: Variation of edge-disjoint spanning trees

texts: In a directed graph, I want to find 2 edge-disjoint spanning trees (arborescence), with the extra restrictions that edges in the 1st tree are not forward arcs in the 2nd tree. Are there existing algorithms I can use, or efficient modifications to existing algorithms?


texts: Finding of dimension of algebraic varieties

texts:
I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf).

Are there the similar results about dimensions of algebraic varieties over finite fields?


texts:
I would like to ask for help in compiling a list of as many TCS-related conferences and workshops as possible.  My main motivation for doing this is to plan possible blog coverage of more theory venues -- finding correspondents attending these events who would be willing to write either brief or in-depth blog entries about events they are attending.  Beyond that, I hope a list like this would give everyone a better sense of the lay of the theory land.

I'll seed the question with an answer containing a few "obvious" conferences.  Please feel free to edit my answer and/or post additional answers of your own.

  Standard abbreviation of conference, name of conference, subject matter, any additional notes.

Intended as community wiki.


texts: How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?

texts:
Note: This has been cross-posted to Quantum Computing SE.

If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the Extended Church Turing thesis. However, in a related thread, a user raised the objection that the random circuit sampling problem might not be a computation in the Church Turing sense:

  @glS: Decision problems, computable functions, etc. are equivalent, so whichever form you like. Sampling is not even a function, much less a computable one. It's a physical process outside the scope of computing/functions.

Could someone elaborate on this apparent discrepancy? Can the random circuit sampling problem indeed be framed in terms of computable functions and effective calculability or a decision problem, as the CT thesis requires?


texts: Is the following graph optimization problem approximable within a constant factor?

texts:
Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$.
For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of neighbors of $v$ that occur before $v$
(respectively after $v$) in the permutation $\pi$.

  Problem. For a given undirected graph $G=(V,E)$, find a
  permutation $\pi$ of the vertices that minimizes the objective value
  $$\sum_{v\in V} ~\left|\text{succ}_{\pi}(v)\right|\times
\left|\text{pred}_{\pi}(v)\right|.$$

Is there a polynomial time approximation algorithm for this problem, that approximates the optimal objective value within a constant factor?  The problem is known to be NP-hard.


texts: Computational Complexity of RESTRICTED primality testing

texts:
Input: Any number $n \in \mathbb{Z}^+$ that can be represented in the form of $n = 2^a + b,\ |b|= c $.
output: YES if $n$ is prime , else NO .

Now, length of binary input is $\log(a) + O(1)$ which otherwise would be order $a$.
What would be the complexity of such problem? If we use AKS algorithm  in straight forward way we would not get polynomial time algorithm, I think. Can we define new problems by tweaking the standard problems in  P to make them harder in this way i.e. by restricting the input in certain way.


texts: Notation for a Conditional Hamiltonian Evolution Operator

texts:
I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write

  Next we apply the conditional Hamiltonian evolution $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|^{C}\otimes e^{iA\tau t_{o}/T}$ on $\left|\Psi_{0}\right>^{C}\otimes\left|b\right>\dots$

For the life of me, I cannot figure out the meaning of the $C$. What is it doing there? How would $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|^{C}\otimes e^{iA\tau t_{o}/T}$ act on (say) $\left|0\right>\otimes \left|0\right>$ or $\left|1\right>\otimes \left|0\right>$?


texts:
The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its corresponding #MONOTONE-2SAT instance $F'$?

A second question is: let $K'$ be the number of solutions of $F'$, and let $K$ be the number of solutions of $F$. Does $K' = K$? Or we must use a back transformation that converts $K'$ to $K$?


texts:
I was reading the wikipedia article about the eight queens problem. It is stated that, there is  no known formula for the exact number of solutions. After some searching, I found a paper named "On the hardness of counting problems of complete mappings". In this paper there is a problem, shown to be at most as hard as #queens, which is beyond #P. Getting a glimpse at the numbers of the #queens counted exhaustively in the wikipedia article, they seem pretty much super exponential.

I want to ask, if there is a name for this class or if in general there are counting problems belonging to classes above #P (with decision not in PSPACE of course because it would be obvious).

Finally, I want to ask if there are any other known results for other search problems, like finding a three-colored point in Sperner's Lemma for example (PPAD complete).


texts: Grouping a set of rectangles in larger rectangular regions

texts:
I have a set of rectangles, which I want to cluster (group) as shown here(I can not post images yet, so please bear with me).

The approach I took was to consider central points of each rectangle as a data point in $R^2$ and cluster them using Euclidean distance (K-means, K-mediods approach or any other method). Traditional clustering approaches help you to discover shapes in data, but I am not trying to discover such shapes, as I know the best shape would be rectangles. I do not know the number of clusters (number of bounding rectangles) beforehand. However, given a clustering solution, an objective measure (BIC) can be calculated to measure clustering accuracy.

Given this situation, my question is, is there any algorithmic formulation of this or a similar problem?


texts: in SAT resolution proofs, are all DAGs possible?

texts:
these are some probably very hard but possibly significant and deep questions related to an unusual but intriguing possible "recursive" construction/formulation in SAT, with some important "structure" or "dynamics" not previously considered. do not expect definitive answers in the short term but am sharing in a preliminary/sketchy form & maybe somebody in cyberspace/TCS will find it interesting also.

consider a resolution based proof for a set of SAT clauses. that resolution proof is in the form of a 2-indegree DAG (or in special cases, a tree) where the leaf nodes are clauses, and every node has 2 "ancestors". (this is potentially very interesting though because circuits are usually/often represented as DAGs and can be and are also converted to 2-indegree.)

  can arbitrary/all 2-indegree DAGs be represented by SAT resolution proofs based on selecting particular/specially constructed/contrived SAT instances? in other words, given an arbitrary 2-indegree DAG, are there clauses that "generate" it in the corresponding resolution (refutation?) proof, and if so, what are they? and also what are the minimal clauses that do so?

(of course a resolution DAG could be either for a proof or a refutation proof. am not specifying/fixing that for this above question. also minimal is not yet/further defined. it could be either "length" (number) or "width" (number of variables) of the SAT instance, or some combination or maybe some other meaningful/natural measure.)

it feels like it could be used in a (important?) proof, eg possibly for complexity class separation via diagonalization, somehow, someday. am working on a further/related possibly remarkable construction that requires a "yes" answer ie that all 2-indegree DAGs are possible. (hope to post further on that later.)

these do seem to be fundamental yet novel, not-previously considered questions based on the literature. "nearby" refs could be useful. my intention will be to upvote and/or accept any partial but intelligent answers & encourage others to follow.


texts: Finding small sets of integers in which every element is a sum of two others

texts:
This is a follow-up to this question on math.stackexchange.

Let us say that a non-empty set S ⊆ ℤ is self-supporting if for every a ∈ S, there exist distinct elements b,c ∈ S such that a = b + c. For positive integers n, simple examples include the ideal S = nℤ, or (for n>3) the integer interval [−n, n].

We'll say that S is strongly self-supporting if S is disjoint from −S: that is, if a ∈ S, then −a ∉ S. Neither of the above examples are strongly self-supporting, because they are in fact closed under negation.
There exist finite sets which are strongly self-supporting: for instance, the sets
{−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23} and  {−10, −8, −6, −2, 1, 3, 4, 5}.

Question #1. For a positive integer N>0, does there exist a poly(N)-time [or polylog(N)-time] algorithm to either (i) produce a strongly self-supporting set whose maximum absolute value is N, or (ii) determine that no such set exists? [Edit: as pointed out in the oldest answer + my comment on it, there always exists such a set for N ≥ 10.]

Question #2. For N>0, can you construct the strongly self-supporting set with maximum absolute value N, and which has the fewest possible elements?


texts: Complexity of digraph homomorphism to an oriented cycle

texts:
Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $V(D)$ that preserves the arcs, that is, if $uv$ is an arc of $G$, then $f(u)f(v)$ is an arc of $D$.)

The class of $D$-COLORING problems is strongly connected to the Dichotomy Conjecture for CSPs stated by Feder and Vardi (accessible on citeseer).

In this 2001 paper (accessible on the author's page, here), Feder proves a dichotomy theorem when $D$ is an oriented cycle (by oriented cycle I mean an undirected cycle where each edge is replaced by a single arc, that can be oriented arbitrarily), in other words, he shows that for any oriented cycle $D$, $D$-COLORING is either polynomial-time solvable or NP-complete.

Unfortunately, Feder's classification is highly nontrivial and not explicit, as the complexity of many cases is related to the complexity of certain restricted variants of SAT that depend on the orientation. By looking at the paper, I have not been able to determine the answer to my question:

  Question: What is the smallest size of an oriented cycle $D$ such that $D$-COLORING is NP-complete?

The answer might be stated somewhere in the literature, but I could not find it.

Edit: Let me give more details on Feder's classification. Feder shows that any NP-complete oriented cycle must be balanced, that is, have the same number of arcs in both directions (hence it has even order). Then, consider the "levels" induced by the orientation (start to go around the cycle at an arbitrary vertex; if an arc goes right, you go up by 1, if an arc goes left, you go down by 1). Then, if there is at most one "top-bottom run", it is polynomial. If there are at least 3 such "runs" and the cycle is a core, it is NP-complete. (In András' example from the comments, there are three such "runs", but the cycle is not a core.) The most tricky cases are those with two "top-bottom runs". Some are hard, some polynomial, and Feder relates them to special SAT problems to obtain a dichotomy. I guess one could make a case-by-case analysis and see what kind of SAT problem it corresponds to...

As an intermediate question: What is the smallest oriented cycle that has three "top-bottom" runs and is a core? Such an example would be NP-complete by the above discussion.


texts:
The clique graph $C$ of a given graph $G$ has the maximal cliques of $G$ as vertices and their is an edge between two vertices in $C$ iff the corresponding cliques share some vertices.

Now for chordal graphs, this clique graph is a tree and for proper interval graphs it is a path. Incidentally for both these graphs the max-clique recognition algorithm runs in polynomial time.

My question is are there other class of graphs who has characterization in terms of its clique graph. ? I am specially looking for such characterisations for bipartite graphs.

Any link to paper/journal is welcome.


texts: Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

texts:
Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $L$ iff there exists a morphism $\varphi : A^{\ast} \to M$ such that $L = \varphi^{-1}(\varphi(L)))$.

Then we have the nice result:

A monoid $M$ recognizes $L \subseteq A^{\ast}$ if $M(L)$ is a homomorphic image of a submonoid of $M$ (writen as $M(L) \prec M$).

The above is usually states in the context of regular languages, and then the above monoids are all finite.

Now suppose we substitute $A^{\ast}$ with an arbitrary monoid $N$, and we say that a subset $L \subseteq N$ is recognized by $M$ if there exists a morphism $\varphi : N \to M$ such that $L = \varphi^{-1}(\varphi(L))$. Then we still have that if $M$ recognizes $L$, then $M(L) \prec M$ (see S. Eilenberg,  Automata, Machines and Languages, Volume B), but does the converse hold?

In the proof for $A^{\ast}$ the converse is proven by exploiting the property that if $N = \varphi(M)$ for some morphism $\varphi : M \to N$ and $\psi : A^{\ast} \to N$ is also a morphism, then we can find $\rho : A^{\ast} \to M$ such that $\varphi(\rho(u)) = \psi(u)$ holds, simply by choosing some $\rho(x) \in \varphi^{-1}(\psi(x))$ for each $x \in A$ and extending this to a morphism from $A^{\ast}$ to $M$. But this does not work for arbitrary monoids $N$ so I expect the above converse to be false then. And if it is false, for what kind of monoid beside $A^{\ast}$ is it still true, and did those monoids have received any attention in the research literature?


texts: Graph Isomorphism Algorithm of Vertex Transistive Graphs and other

texts:
What are the best known Graph-Isomorphism algorithms for  below graph classes-
1.vertex-transitive,  2. edge-transitive,  3.arc-transitive (or symmetric) 4.distance-transitive.
Are they GI Complete?
Provide run-times/time complexity of algorithm, if possible.
Related post: This question was asked on MSE.


texts: Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$

texts:
In the following, we will describe what seems to be a parameterized version of the minimum circuit size problem (MCSP).

Before we get started, we need the following concepts:

For every natural number $n$, consider a function $B_n: [n] \rightarrow \{0,1\}^{\lceil \log(n) \rceil}$ such that $B_n(i)$ is the $i$th bit string in $\{0,1\}^{\lceil \log(n) \rceil}$ according to the lexicographical ordering.  (Example: $B_7(5) = 100$)

Now, let a bit string $x$ of length $n$ be given.  Let a boolean circuit $C$ with $\lceil \log(n) \rceil$ inputs and $1$ output be given.  We say that $C$ computes $x$ if for every $i \in [n]$, $C(B_n(i)) = x_i$.  In other words, $C$ computes $x$ one bit at a time.

Now, consider the following parameterized problem:

Given a bit string $x$ of length $n$ and a natural number $k$, does there exist a boolean circuit $C$ of size at most $k \log(n)$ that computes $x$?

If there are only $g(n,k)$ circuits of size $k\log(n)$, then we can solve this problem in roughly $n * k\log(n) * g(n,k)$ time by trying every possible circuit and evaluating each one on all $n$ inputs.

  Question: What is the parameterized complexity of this problem?

This question has several parts:

Are any more efficient algorithms known?
Is this problem related to any standard parameterized complexity
classes?  For example, the problem could be $FPT$.  Or, it could be
$W[1]$-hard or harder.
Are there any known parameterized complexity results or conditional lower bounds for the minimum circuit size problem?


texts: are there approximation algorithms that use primal-dual with LP values and/or rounding?

texts:
Are there approximation algorithms that use primal-dual with LP values and/or rounding?
e.g. An algorithm that during any iteration first tries to see an extreme point to the LP has any value above a given threshold and if so rounds that, otherwise following primal-dual, increments some set of dual variables until some primal variable becomes tight  ...
and applies a standard reverse deletion step at the end.
Alternatively are there algorithms that during any iteration first looks at the optimal primal/dual solution and then based on the optimal solution values the primal-dual algorithm increments some set of dual variables until some primal variable becomes tight  ...   and applies a standard reverse deletion step at the end.


texts: Triangulation with maximum greatest area

texts:
Given a point set $P$ and a triangulation $T$ of $P$ with $d$ triangles, let's define

$$\alpha(T) = (\alpha_1, \alpha_2, \ldots, \alpha_{3d})$$

which denotes the series of interior angles of $T$, sorted in ascending order. We can compare two such series (of the same length) easily in lexicographical order. We know that $T$ is a Delaunay-Triangulation iff $\alpha(T) \geq \alpha(T')$ for all possible triangulations $T'$ of $P$. This is also called the "maximum smallest angle" characteristic of the Delaunay Triangulation.

My question is now, is there a "maximum greatest area" triangulation? (Yes, not "maximum smallest area"!) More formally, define

$$A(T) = (A_1, A_2, \ldots, A_d)$$

which denotes the series of triangle areas of $T$, sorted in descending order, and I hope to find a triangulation $T$, so that
$A(T) \geq A(T')$
for all possible triangulations $T'$ of $P$.

Does anyone know such an algorithm, or is it even trivially computable (i.e. with a greedy algorithm)?


texts: Efficiently representing sets of $n$-dimensional rectangles orthogonal an axis

texts:
Is there a data structure that allows one to represent sets of $n$ dimensional rectangles, all orthogonal or parallel to the $x$ axis. efficiently. Allowing all common set operations (union, difference etc) to be done efficiently as well?

Let me explain what I mean by a 2D example.

Given this two set of rectangles * is the first set % is the second set

*************
*           *
*       %%%%o%%%%%%
*       %   *     %
********o ***     %
        %         %
        %%%%%%%%%%%

If I'll do * union %, I can get

*************
*           *
*******************
*                 *
*******************
        *         *
        ***********

or

*************
*           *
*******************
*       *   *     *
*******************
        *         *
        ***********

If I'll do * difference %, I can get

*************
*           *
*************
*       *
*********

Can you refer me to a relevant paper?


texts: $\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$

texts:
I know that $\mathsf{P}^{\mathsf{NP}[\log n]}$ (logarithmically many calls to the NP oracle) is equivalent to $\mathsf{P}^{\mathsf{NP}||}$ (polynomial number of parallel queries to the NP oracle). I was wondering wether the "function" version of these classes are also equivalent, that is, whether

$$ \mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$$
If it is known to be true, a pointer would be really helpful.


texts:
What is the maximum number of colors that can be used for coloring the vertices of a given graph, with no isolated vertices, such that each vertex should share its color with at least one of its neighbour vertices?

Is there anything in literature about this variant of coloring?


texts: Information about algorithm to generate sequences

texts:
I want to make an application for generating a sequence (called S) of items (I), based on conditions (called C).

The Conditions are defined as a property with a 'bonus/reduction'. The total score (T) is defined by summing up al condition scores.

Some conditions are based on a specific item, some not.

Example (where Ix and Iy are different items)
- Ix on first 5 places in S has a score of +20.
- Ix directly after Iy has a score of -10.

However, I was wondering if there is an algorithm or principle for this problem (to find the highest total score)? It seems reasonably generic (except for the condition specification).

Finding the top score by trying all possibilities might end up in a lot of checks (like about 30! for 30 items).

Not all items have to be used in the sequence, but each item has a length, and there is a bonus for having the sum of length equal (as good as possible) to the requested length.

Each item can be used only once (at max).


texts:
Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.

Let $[n]=\{1,2,\dots,n\}$.

If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.

If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.

If  $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

If  $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that  $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$

Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$

Given $f$ in $n$-variables, would it be reasonable to ask the complexity class of deciding $S(f)>c$ and $BS(f)>c$ for a fixed $c>0$? I understand that describing a Boolean function takes $2^n$ bits fully.

Does computing $BS(f)$ also take $O(2^{n+\epsilon})$ time as in answers below?


texts: Reduction from k-Almost Independent Set to Independent Set

texts: The problem of $k$-Almost Independent Set is to decide whether or not $(G,m)$ where $G$ is a graph and $m \in \mathbb{N}$ has a subset of $m$ vertices that induces a subgraph with at most $k$ edges. I know that Independent Set reduces to $k$-Almost Independent Set in a natural way (adding k pairs of vertices each joined by an edge). Is there a natural reduction in the reverse direction?


texts: How to use induction without Fixpoint definition in Coq?

texts:
I want to verify a program written in C. I am using Jessie to translate the (pre/post)conditions of the program to Coq. In Coq I will make a proof. Sometimes I need recursive definitions.

Unfortunately Jessie generates no fixpoint definitions and unfortunately I must use these generated definitions to verify a program.

For example the power function:

Require Export ZArith.
Open Scope Z_scope.

  (*Generated by Jessie from my C program*)
Definition pow : Z->Z->Z.
Admitted.

Definition eq_int_bool : Z -> Z -> bool.
Admitted.

Lemma eq_int_bool_axiom :
  (forall (x:Z), (forall (y:Z), ((eq_int_bool x y) = true <-> x = y))).
Admitted.

Lemma _jc_axiom_sum :
    forall (b:Z),
    forall (e:Z), (pow b e) =
    if (eq_int_bool e 0) then (1)
    else (b * pow b (e-1)).
Admitted.

How can I use the inductive tactics provided in Coq, if I want to prove some features? What can I do in this situation to prove the features? Is it even possible to perform some “complicated” proofs with this sort of definition?
In my Coq proofs I can use all I want, including fixpoint definitions.


texts: checking isomorphism between K regular graph

texts:
Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that given graph G is constructed from a p-dimension hypercube graph Hp of 2n vertices [ so n is a power of 2 ] as ...

Since hypercube is always bipartite.[ Hp = (L,R),V ]
G has n nodes corresponding to the left set L of Hp.
For any 2 nodes in L which have a path of length 2 in Hp, there is an edge between the corresponding nodes in G.

It is easy to see that G is regular and highly symmetric [in term diameter,no of diameters etc due to properties of hypergraph ].

My problem is how to detect whether the input graph can be constructed from a hypercube graph as shown or not . i.e. efficiently check for isomorphism.

Note For a given (n,k) there can be many regular graph as shown in http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html


texts: Counting reversibly using few FullAdders and little work space

texts:
Given N bits on a reversible computer, I want to compute their Hamming weight (into a binary register) while using a minimal number of FullAdder circuits (takes 3 bits, outputs their sum as 2 bits) and while minimizing work space.

For reference, this is what a reversible FullAdder looks like:

The important thing to notice is that you need an ancilla bit to hold the carry output, and this ancilla bit sticks around until you uncompute the FullAdder. There tends to be a tradeoff between the amount of uncomputation work you do and the maximum number of ancilla you have at any time (see: Pebble Games).

I'm looking for strategies that have interesting tradeoffs between the maximum number of ancillae and the number of FullAdder computations/uncomputations performed, in the context of popcounting a bunch of bits.

Here are three example strategies:

If you simply iteratively merge bits using FullAdders until you're left with a binary register, without ever doing any uncomputation, you compute the total weight using a linear number of FullAdders and ancillae (specifically, between N-lg(N) and N of each).
Divide the input into $\sqrt{N}$ groups of size $\sqrt{N}$. Prepare a result register with $\lg N$ bits. For each group: compute the group's weight using strategy #1, add the group's weight into the result register, then uncompute the group. This uses $\sqrt N + \lg N$ ancillae, but increases the number of FullAdder computations and uncomputations from $N$ to $4N$.
Same as strategy #2, except instead of falling back to strategy #1 when computing the group totals you recurse using the same method. This increases the FullAdder applications to $O(N (\lg N) (\lg \lg N))$, but reduces the ancilla usage to $2 \lg N$.

I am especially interested in whether or not it is possible to reduce the ancilla usage without increasing the number of FullAdder applications by such a large amount. The underlying context is quantum computation, where error corrected FullAdders are billions of times more expensive than classical ones, so I care about the constant factors.


texts: Covering only one of two types of objects in a cartesian space using minimum number of rectangles

texts:
There is a side problem in my research that I believe should be a known problem. I do not want to spend lots of time on a problem that already has been studied, but I do not have a name for the problem to search for it. I hope someone can help. The precise definition can be found on http://imgur.com/goKKuSQ. Here I explain it in an informal language.

Problem definition:

There are two types of objects (say red and blue pieces) on a finite discrete 2-D space (the space is a closed subset of ZxZ). Number and locations of the pieces are arbitrary. Two pieces on the same coordinate are considered as one. It is not possible for a red piece and a blue piece to co-exist at the same coordinate.

In this space, we can define a rectangle by the coordinate of its upper-left and lower-right corners. The size and location of a rectangle can be anything but it is always parallel to X and Y axis.

I am looking for an algorithm to find the minimum number of rectangles that cover one type of the objects (say the blue pieces) only. Every and each blue piece should be inside or at the border of one or more rectangles, and no red piece can be on the border or inside any rectangle. The algorithm should return the coordinates of all such rectangles.

So, have you heard of this problem before? The first correct answer(s) will surely be acknowledged in my thesis.

Edit: I am searching for an algorithm of complexity smaller than exponential. The exhaustive search took forever to run and I had to stop the program. Also Evolutionary methods are not a good choice because of their long running time.


texts:
Background:

In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels:
A quantum channel is a linear, completely positive, trace preserving map
$\Phi:\Theta(\mathcal{H}_{in}) \to \Theta(\mathcal{H}_{out})$
where $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$ are respectively the input and output Hilbert spaces, and $\Theta(\mathcal{H})$ is the set of density operators (i.e. stochastic states) over the Hilbert space of pure states $\mathcal{H}$.

In particular, if the input and output spaces are finte dimensional, and they concide, then $\mathcal{H}_{in} \equiv \mathcal{H}_{out} \equiv \mathcal{H} \equiv \mathbb{C}^n$, and $\Theta(\mathcal{H})$ is the set of $\mathbb{C}^{n\times n}$ Hermitian, positive semi-definite matrices of trace one.

Various standard representations exist for any quantum channel. For instance, the Kraus representation, also known as operator-sum representation:
$\Phi(\rho) = \sum_{k}V_{k}\rho V_{k}^{\dagger}$
where $V_{k}$ are the Kraus operators of the channel, subject to the constraint:
$\sum_{k}V_{k}^{\dagger} V_{k}=I$.

Given two quantum channels $\Phi_1,\,\Phi_2$ defined on the same space, various distance measures $d(\Phi_1,\,\Phi_2)$ can be defined. See, for instance, arXiv:quant-ph/0408063, or this question by Joe Fitzsimons.

Question:

I would like to know how to define a low-dimension approximation of a finite-dimension channel. More specifically:

Let $C_{n}$ the set of all channels of finite-dimension $n$:
$C_{n}\equiv \left \{ \Phi | \Phi:\Theta(\mathbb{C}^n) \right \}$

Given two space dimensionalities $n$ and $m < n$, define an Abstraction operator:
$\mathcal{A}:C_{n} \to C_{m}$

and a Concretization operator:
$\mathcal{A}^{inv}:C_{m} \to C_{n}$.

such that their compositions yields an optimal approximation of any channel:
$\forall \Phi \in C_{n},$
Let $\Phi_{\mathcal{B},\,\mathcal{B}^{inv}} \equiv \mathcal{B}^{inv}(\mathcal{B}(\Phi))$
Let $\widetilde{\Phi} \equiv \Phi_{\mathcal{A},\,\mathcal{A}^{inv}}$
then $d(\Phi\,\widetilde{\Phi}) = \min_{\mathcal{B}\,\mathcal{B}^{inv}}(d(\Phi\,\Phi_{\mathcal{B}\,\mathcal{B}^{inv}}))$
where $\mathcal{B},\,\mathcal{B}^{inv}$ are arbitrary operators between channels of suitable dimension:
$\mathcal{B}:C_{n} \to C_{m}\,\ \mathcal{B}^{inv}:C_{m} \to C_{n}$.

I'm not sure what distance measure $d(.,\,.)$ is the most appropriate to use here. I was thinking of the diamond distance.

Also, it would be very nice if the Abstraction operator was defined compositionally with respect to the Kraus representation. That is, given the channel:
$\Phi(\rho) = \sum_{k}V_{k}\rho V_{k}^{\dagger}$

It should hold that:
$\mathcal{A}(\Phi)(\rho) = \sum_{k}\hat{A}(V_{k})\rho \hat{A}(V_{k})^{\dagger}$
for some function $\hat{A}(.)$. (Of course this representation would not be minimal in the number of Kraus operators).


texts: QPIP minimal client quantum capabilities

texts:
It is conjectured that classical (BPP) client blind quantum computing is implausible according to Aaronson et al:

https://www.researchgate.net/publication/316538667_On_the_implausibility_of_classical_client_blind_quantum_computing

What are the minimal quantum capabilities that a classical client must have in order to verify a single BQP quantum prover with the following requirements?

Information-secure communication (no cryptographic assumptions)
Only the size of the input is revealed to the quantum prover
Single prover server

My understanding is that the paper above leaves this as an open problem.


texts: A conjecture related to the Cerny conjecture - counterexample/reference request

texts:
The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a synchronizing word is $O(n^3)$. Let's say that two states are merged by a word if that word takes the two states to the same state. A pumping lemma type argument shows that in a synchronizing automaton, any two states can be merged by a word of length at most $n^2$. Suppose that the following conjecture is true.

Conjecture. Any subset of $k$ states contains two states that can be merged by a word of length (say) at most $n^2/k$. Or more generally, any large set of states contains two that can be merged by a word of length $o(n^2)$.

Then we can consider the following strategy for constructing a synchronizing word. We start with all $n$ states. By the conjecture above, there is a short word merging two states, and we make this the beginning of our synchronizing word. We can run the DFA with this word starting from all states, and we get a set of at most $n-1$ final states. We repeat this with these final states as our new start states. After repeating this a sufficient number of times, we only end up with one final state. Clearly, given the above conjecture, we would have a better bound than $O(n^3)$ for the length of the shortest synchronizing word.

The above motivates the following questions:

Are there any known counterexamples to this conjecture? Cerny's original construction (see page 18) satisfies the statement of the conjecture.
Could you provide a reference where similar ideas are investigated?


texts: Two way deterministic multihead counter automata or logspace TM with counter

texts: Is that known something about languages recognized by two-way deterministic multihead counter automaton or logspace TM with counter (equivalent model)? This class called Aux2DC in my advisor's paper. Or about such nondeterministic class? I've obtained that class of languages recognized by such nondeterministic maschines includes NL and it seems to be included in LOGCFL. Are there any papers on this subject? Is that result trivial?


texts: Isomorphism preserving transformation to graph of logarithmic boolean-width

texts:
In short we found isomorphism preserving graph to graph of logarithmic
boolean-width.
The paper On graph classes with logarithmic boolean-width
claims that some graph problems are fixed parameter tractable with parameter
the boolean-width.
In particular, boolean-width of the complement of $k$-degenerate graph
is at most $k\log(n)$.
Define the $m$-th subdivision of $G$ to be the graph with each edge
subdivided $m$ times. The $m$-th subdivision is $2$ degenerate for all
$m$, so its boolean-width is at most $2 m \log(n)$ and it preserves
graph isomorphism.
Maximum clique is NP-hard and FPT on
co-2-subdivision
and graph isomorphism is GI complete.

Q1 Can we solve max clique on co-2-subdivision in time $\exp(o(n))$?

Q2 Can we solve graph isomorphism on co-$m$-subdivision in time
$\exp(o(n))$?

Another paper claims:

Given any graph G and a decomposition of G of boolean-width k, we give algorithms solving a large class of vertex subset and vertex partitioning problems 2
in time $O^*2^{O(k^2)}$.

Positive answer to Q1 will break ETH.
We tried to contact the authors via email.


texts: Any fundamental papers in TCS which were found to be incorrect/wrong later?

texts:
I am asking this question out of curiosity.

I recently encountered this well-known paper on (published in 2009):
the hardness_of_Euclidean_kmeans

The paper showed that the previous NP-hardness result (link) for the Euclidean k-means (discovered in 2004 and a preliminary version appeared in 1999) was wrong. Note that after around 5 years somebody pointed out that the previously known result was incorrect.
They also mention that many of the well-known papers (like kmeans++ paper) cited the incorrect hardness result till then.

Even when I read a paper, I find some minor mistakes. However, they are easily fixable and do not change the main result very much.

I want to ask if there had been any fundamental or highly cited paper, which was later found to be incorrect, and due to which the entire understanding of the field changed.

Edit: After reading some of the answers, I want to point out another issue that, why these incorrect papers are not updated after being pointed out wrong. I mean some kind of notice must be provided by the governing body who shares the link. In my case (for the example I gave above), it took me two years to figure out why people in the year 2002 were designing the PTAS for the k-means problem(for fixed k) if the result of hardness came later in the year 2009. It can be quite frustrating for a person who is not familiar with that field.


texts: Questions about regular languages and their sublanguages

texts:
I am interested in the following questions and would be grateful if anyone could give me hints or point me to articles:

1) Given a regular language $L$, what are its regular sublanguages $L'\subseteq L$, i.e. how to enumerate all regular $L' \subseteq L$ for a given regular language $L$.

2) Could every regular sublanguage $L'$ of a regular language $L$ be written as $L' = L''\cap L$ with $L''$ regular

3) Given a arbitrary language, is it decidable if it is regular (of course one could compute it's syntactic monoid, but this computation could take on forever if the language is not regular)


texts: Minimum Clique edge cover to cilque vertex cover

texts: Suppose, there is an algorithm for enumerating minimum clique edge cover. Is it always possible to convert the algorithm to enumerate clique vertex cover ?


texts: Local updates in weight-balanced search trees

texts:
In Kurt Mehlhorn's monograph "Data Structures and Algorithms 1: Sorting and Searching", he poses the following question  (III.9.22):

  Design a balanced tree scheme where the worst case rebalancing cost after an insertion or deletion is $O(\log \log n)$. Hint: Use weight-balanced trees. If $n$ elements are stored then rebalance up to height  $O(\log \log n)$ as described in the text. With every node $v$ of height $\log \log n$ associate a pointer which points to an ancestor $p(v)$ of $v$ in the tree. If a transaction goes through $v$ then we also rebalance $p(v)$, if necessary, and advance $p$ one step towards the root. Show that the root balance of nodes of height $\log \log n$ or more cannot deteriorate too much.

It is not obvious to me how a slowly-moving $p(v)$ can keep nodes of height $\Omega(\log \log n)$ but $o(\log n)$ balanced. My intuition is that these nodes must be cared to more frequently than I can manage with the "one ancestor pointer" system.

Any ideas on how to maintain $p(v)$?

There has been some work on reducing the cost of updates at a known location in weight-balanced trees, but I'm not aware of any weight-balanced tree with $o(\lg n)$ worst-case updates. (Treaps are weight balanced and have $O(1)$ expected-time updates.)

Mehlhorn's monograph is available electronically in an updated form that unfortunately leaves out III.9.


texts: Techniques for proving bounds on integrality gap in LP(SDP)

texts: A reference to techniques for proving that the size of an integrality gap is bounded by some expression for a particular LP(or SDP, but less important) is needed. Also it would be nice to have a reference to a place where techniques for minimizing integrality gaps are described. I am new in the area of integrality gaps, which looks rather huge, so description of classical results is more preferable than that of something hot.


texts: Commutativity of addition in polymorphic lambda calculus

texts:
In the article "Extensional models of polymorphism" by Breazu-Tannen and Coquand, natural numbers are presented using a Church-like encoding:

$polyint = \forall t . (t \to t) \to t \to t$

Addition for this encoding is introduced as:

$\mathsf{Add} = \lambda u,v : polyint . \Lambda t . \lambda f : t \to t . \lambda x : t . u t f (v t f x)$

Then they say that commutativity of addition cannot be proved, and they say that $\mathsf{Add} u v = \mathsf{Add} v u$ does not follow from polymorphic lambda calculus theory by a simple Church-Rosser argument. What's this Church-Rosser argument? Is it related to the Church-rosser property? How can I prove it?

EDIT: the exact statement is:

"However, the pure $\lambda^{\forall}$ is not sufficient for that, as it cannot even prove, for example, that the operation of addition is commutative:

$\mathsf{Add}\ u\  v = \mathsf{Add}\ v\ u$

with arbitrary $u, v : polyint$ is not provable in $\lambda^{\forall}$ (by a simple Church-Rosser argument)".


texts:
I am working on a project that requires me to learn about logic (specially first order and second order).

Looking for a good book or online reference that can help me with questions such as:

A. What is the difference between Logic, Language and Calculus?

B. How to define operators and their semantics?

etc.

As a beginner, it would be great to read a step by step like instructions with easy examples that helps me understand and build on.

Thanks in advance
Karl


texts: How many negations do we need to compute monotone functions?

texts: Razborov proved that the monotone function matching is not in mP. But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ negations that computes matching? What is the trade-off between the number of negations and the size for matching?


texts:
According to this paper, which discusses a nondeterministic extension of the Strong Exponential Time Hypothesis (SETH), "[…] Williams has recently shown related hypotheses about Merlin-Arthur complexity of k-TAUT are false". However, that paper only cites a personal communication.

How is the MA version of SETH proven to be false?

I suspect that it involves algebrizing the formula, but do not have any further idea.


texts:
Given two trees A and B, each of their nodes except some leaves have a "type" (which also determines the number of children, the node has, having that type). The leaves which don't have a type are identified by letters (variables) (a,b,c,...). Each letter may occur multiple times in a tree.

The task is to devise an algorithm to 'solve' the 'equation' A=B, i.e. assign trees to the variables (possibly containing other variables). One tree (x) equals to an other (y) iff x and y are the same variables or the root of both have the same type and their respective children are equal.

In the following the "types" are numbers.

Example 1:

A tree is

1
|-2
|-a

B tree is

1
|-2
|-3

The solution is a->3

Example 2:

A tree is

1
|-2
|-a

B tree is

1
|-3
|-3

This does not have a solution.

Example 3:

A tree is

1
|-2
|-a

B tree is

1
|-2
|-b

The solution is a=b (the equation is underdetermined so to say)


texts: Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?

texts: Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} x_i < \sum_{j \in J} x_j$? What about the special case of inequalities that form a total order over the sums of the members of the power set of $\{x_i, \ldots, x_k\}$?


texts: An NP-complete variant of factoring and relation to factoring

texts:
After reading this post An NP-complete variant of factoring. I come up with a question.

To summerize the post, we have the factoring problem (F) which ask for a number $p$ that is prime and divides an given number n and $p$ is between a given interval $l \leq $p$ \leq u$. The variant of the factoring problem (VF) ask for a number $p$ that divides an given number n and $p$ is in the interval $l \leq $p$ \leq u$, but not necessarily needs to be prime. So while (F) is not believed to be NP-complete, (VF) is.

But couldn't you solve (VF) with polynominal many oracle calls to (F), by first getting all prime divisors of n. (This list, lets call it l, has at most $log_2(n)$ many entries)
Then calculate all subset products of $l$. An upper bound for how many this could be, would be given by the number of ways of choosing $i$ many elements from $l$, for $i = 0$ to $log_2(n)$. So $\sum_{i = 0}^{log_2(n)} \binom{log_2(n)}{i} =  2^{log_2(n)} = n$. So there also polynominal many products, which needs to be checked if they are between $l$ and $u$.

Wouldn't this make Factoring also NP-complete?


texts: Strong Normalization of Extended Calculus of Constructions (CC with cumulative universes)

texts:
There are some proofs around to prove the strong normalization of the calculus of constructions (i.e. that all type systems in the lambda cube are strongly normalizing). I have analyzed the proof available from Herman Geuvers which is not an easy read, but understandable.

I am interested in proof of strong normalization of calculi like CC which have cumulative universes i.e. which have sorts
$$
 \text{sort} ::= * \mid \Box_i \quad 0 \le i,
$$
allow subtyping
$$
\begin{array}{c}
\Gamma \vdash t : T
\\
T \le U
\\ \hline
\Gamma \vdash t : U
\end{array}
$$
where $\le$ is based on the ordering of sorts
$$ * < \Box_0 < \Box_1 \ldots$$

and the typing rules are practically the same as for pure type systems where $*$ is impredicative and all $\Box_i$ are predicative.

A simple generalization of the proof of Herman Geuvers does not work because it heavily depends on a distinction between kinds and types and objects and type constructors (based on having only two sorts $*$ and $\Box$ and no cumulativity).

I have searched a lot but I cannot find a comprehensible proof of strong normalization. This is strange because this type system is a subset of the type system of Coq which is in use for several decades now and supposedly strongly normalizing.

Can anybody give hints to understandable proofs of such type systems?

Thanks for any hint.

Addendum:

From the first comment of Cody I conclude that there might be no easier to grasp proofs than the proof in Zhaohui Luo's Phd thesis which I already have but it is a big bullet to bite.

I don't need the full power of cumulative universes, but the calculus of constructions is not sufficient for me, because I have to make a Coq like split between propositions and "normal" types. Is there a way to generalize the proof of strong normalization of CoC to such a type system?

Furthermore a proof of strong normalization would be nice, but a proof of weak normalization would be sufficient at least to make type checking decidable. Is there a simpler proof for weak normalization for systems with cumulative universes?. But, of course, this does not prove that the system is sound (i.e. free of contradictions) which is a major drawback.


texts: What can I say about the Parikh map of a CSL?

texts:
Write $\Psi$ as the Parikh map--i.e., $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$, where $\#_\sigma(w)$ is the number of times $\sigma$ appears in $w$. It's well-known that, for a CFL $L$, $\Psi(L)$ is a semilinear set (this is Parikh's theorem). Some other interesting things are known, but I have found nothing about the Parikh map of a context-sensitive language. In particular,

  what can I say about $\Psi(L_2 - L_1)$
  or $\Psi(\bar{L}_1)$ if $L_1, L_2$ are
  context-free? For instance, if I let
  $\phi(L) = \{\sum_\sigma \#_\sigma(w)\vert w\in L\} = \{|w|
 \vert w\in L\}$, is it possible that
  there is a CFL $L$ such that
  $\phi(\bar{L}) = \{n!\vert n\in
 \mathbb{N}\}$? (or any other
  'increasing' sequence converging in
  $\hat{\mathbb{Z}}$, for that matter.)


texts:
How easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete.

Any help would be appreciated. Thanks.


texts: Is there a name for this Assignment definition

texts:
The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks.

Now consider the following generalization: Instead of specifying a  cost of a single agent-task pair, assume that you can specify a cost of an arbitrary set of agent-task pairs. The problem is then defined by a set of constraints, where each constraint is a cost c and a set S of task-agent pairs. Meaning of a such constraint is that a cost c occurs when all pairs in S are "satisfied", and the overall cost is the sum of costs of all satisfied constraints.

Note that this problem can be encoded as Weighted Partial MAX-SAT, where hard clauses encode one-to-one assignment between agents and tasks, and each constraint is a (weighted) soft clause.

However, I am interested if this can be reduced to something simpler or if this is a known problem, but so far wasn't able to find an answer.

Thanks for your help.


texts: Finding the perfomance ratio in a multicommodity-flow

texts:
I am reading the following paper about multicommodity-flows. I have not a very strong background in graph theory and hence most of my question regarding the paper are fundamental. My questions are about lemma 2 and its proof, which is needed to find an approximation algorithm for the maximum 2-splittable flow problem.

My first question is about the problem definition on page 102. A flow in a network has different values along the arcs. They define a k-splittable $s$-$t$ flow $F$ as $k$ pairs $(P_1,f_1),\dots,(P_k,f_k)$, where $P_i$ is a simple $s$-$t$ path. Does the value of such an $f_i$ change along $P_i$? Since they say $(P_i,f_i)\in \mathcal{P}_{s,t}\times\mathbb{R}_{\ge 0}$ this would imply it does not change along $P_i$. However since natural flows do change along the arcs, I want to be sure, if my interpretation is correct.
This question is about lemma $2$ on page 105. I have never heard the definition of a thickest $s$-$t$ path. Also a web search was not successful. What does thickest $s$-$t$ path mean in this context and how can we conclude in the proof that the bottleneck edge $e$ has strictly positive residual capacity using the value of a maximum $s$-$t$ flow in $G'$?
If this bottleneck edge $e$ is a forward edge of $P_1$, why do both $P^*_1$ and $P^*_2$ contain this edge?
What is meant by a $D/k$ integral $s$-$t$ flow?
the last question is about approximation algorithms. So far I have never been in touch with approximation algorithms. I know that a $\rho$ approximation algorithm yields a feasible solution whose value is at most a factor of $\rho$ away from the optimum. So how exactly does lemma 2 imply that using the maximum capacity augmenting path algorithm yields a $\frac{2}{3}$-approximation algorithm?

Thank you for your help


texts: On number of disjoint sets with small stack depth in a set of permutations

texts:
Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]),

What is the number N of disjoint sets of size 2 from [n] such that for each $\sigma_i$ , $i \in [k]$ the maximum stack depth is $O(n^{0.9})$ when processing following sequence of push and pops obtained from these sets and $\sigma_i$ (ie, upper bound on maximum number of elements in the stack at any time is $O(n^{0.9})$).

for each set $S_l= \{a,b\}, l\in [N]$,  if replace 'a' (let 'a' appears first when we scan the permutation $\sigma_i$ left to right, i.e, $\sigma_i(1),\sigma_i(2),...,\sigma_i(n)$) by push({a,b}) and 'b' (in the left to right scan 'b' appears after 'a') by pop({a,b}). We ignore all elements $e \in [n]$ which does not belong any of this disjoint sets.

When processing a pop({a,b}), if {a,b} is not top, then we pop all elements until we pop {a,b} and push back all popped elements except {a,b}.

Note that:
(1) Across permutations, disjoint sets $S_1,...,S_N$ are fixed.
(2) The stack depth condition should hold for each of the permutation $\sigma_i, i\in [k]$.

We may apply some process like choosing a permutation $\rho$ from set of all permutations (it can depend on the given permutations) and look for these N sets in $\rho.\sigma_1,\rho.\sigma_2,...,\rho.\sigma_k \in S_n$  instead of in the original permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$, but we are not allowed to use different processes for different permutations.

For any stack depth D, where $\sqrt{n} \leq D \leq  n^{1-\epsilon}$, where $0<\epsilon<1/2$ is a constant,
Is it possible to get N to be $\Omega(D.n^{\delta})$, where $\delta>0$ is a constant?


texts:
In polynomial algebra there is a powerful tool for treating system of polynomial equations. It is standard or Groebner Bases. It allows to verify if system is consistent, eliminate variables, reduce overdetermined systems. Algebraically it is a canonical basis for ideal, generated by finite system of polynomials. For differential system Groebner Bases of ideal (generated by finite system) is not always finite, but it is possible to characterize radical by Ritt-Wu method and consequently to have similar tool for differential case. From the point of view of algebra it could be also generalized to system of difference equations (because of similar properties, as it was shown by Cohn). But according to literature this work is still not finished. And I wonder why.

From the point of view of application is this topic interesting or not?


texts: Approximating BLEDP on restricted graph classes

texts:
In the edge-disjoint paths (EDP) problem, we are given an undirected graph $G$, and a set $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$ of $k$ source-sink pairs. The objective is to maximize the number of pairs connected via edge-disjoint paths. In the bounded length edge disjoint paths (BLEDP) problem, we wish to route the maximum number of source-sink pairs such that each of the paths used is of length at most $L$, for some length bounded $L$ that is part of the input.

Guruswami et al. [1] showed that BLEDP can be approximated in polynomial time within a factor of $O(\sqrt{m})$. They also showed this is optimal with a matching hardness result of $m^{1/2-\epsilon}$, for any $\epsilon > 0$.

Do we have algorithms achieving better approximation ratios for BLEDP for some restricted graphs? For example, how about (undirected) planar graphs?

[1] Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., & Yannakakis, M. (2003). Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Journal of Computer and System Sciences, 67(3), 473-496.


texts: Practical approaches to solving whether programs will halt

texts: What kinds of systems are available that accept a certain program $P$ and attempts to figure out "the program does terminate" or "the program does not terminate" and output a proof of one or the other?


texts: Is Locality preserving projections (LPP) method the same as Laplacian eigenmap method?

texts: Are "Locality Preserving projections(LPP)" and "Laplacian eigenmap" one method for dimension reduction, only under different names? I have not seen any article refer to them as the same method, in fact in LPP paper, they cite Laplacian eigenmap as a non-linear dimension reduction and say that LPP is a linear dim reduction method. But both algorithms have exactly same description. Are they a same method, or am I missing something?


texts: For which graph classes the fractional chromatic index rounded up equals the chromatic index?

texts:
Let $\chi'_f(G)$ be the fractional chromatic index.

For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$?

Since $\chi'_f(G)$ is computable in polynomial time,
 solving this gives tractable graph classes.

Experiments with Sage suggest this is true for
perfect graphs on up to $8$ vertices, though
Sage's implementation is not inefficient.


texts: Difference between Strict Consistency and Sequential Consistency

texts:
I understand strict and sequential consistency independently fairly well.

Strict C basically enforces the actual order in which the instructions ran on the global clock.

Sequential Consistency basically enforces the order only on one processor.

I'm having trouble putting together some literature though.
http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html describes sequential  consistency as allowing for memory 'lag'. It may take time for a write to propagate across all processors. But when it does, it reaches all of them at once which is fine. Thus, the following is valid under Sequential Consistency

P1:  W(x)1
-----------------------
P2:        R(x)0 R(x)1

What concerns me now is the following processes, which is something like Dekker's algorithm.

P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0

This should surely NOT be possible under Sequential consistency ( http://portal.acm.org/citation.cfm?id=1787234.1787255 pg 2). There is no total order that can give this result.

But it makes sense from the idea that sequential consistency allows writes to propagate slowly and one thread may not have any idea as to what other processors are up to.

What am I missing here?


texts: finding smallest k elements in array in O(k)

texts:
This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 <= k <= n

I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!

quick notes:
-the order of the k smallest elements is not important
-the elements in the array are number , might be integers and might be not (so no radix sort)
-the number k is not know in the pre-processing stage.the preprocessing is O(n) time. the function ( find k smallest elements) on O(k) time .


texts:
Here's my attempt to explain the problem in mathematical language:

$$
\text{Given square matrix A}
$$
$$
\left(
\begin{array}{cccc}
 a_{1,1} & a_{1,2} & \cdots & a_{1,N} \\
 a_{2,1} & a_{2,2} & \cdots & a_{2,N} \\
 \vdots & \vdots & \ddots & \vdots \\
 a_{N,1} & a_{N,2} & \cdots & a_{N,N}
\end{array}
\right)
$$

Find a minimal sum of $N$ elements such that no two elements are in the same row or column. In other words, find $$\min_{\sigma\in S_N}\left\{\sum_{i=1}^Na_{i,\sigma(i)}\right\},$$ where $S_N$ is the set of permutations on $\{1,\ldots,N\}$.

Is there a standard name for this problem?


texts: Circuit lower bounds over arbitrary sets of gates

texts:
In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute.  However, the basis {AND,OR} over the Boolean domain {0,1} is just one example of an interesting gate set that falls short of being universal.  This leads to my question:

Is there any other set of gates, interestingly different from the monotone gates, for which exponential lower bounds on circuit size are known (with no depth or other restrictions on the circuit)?  If not, is there any other set of gates that's a plausible candidate for such lower bounds---bounds that wouldn't necessarily require breaking through the Natural Proofs barrier, as Razborov's monotone-circuits result didn't?

If such a gate set exists, then certainly it will be over a k-ary alphabet for k≥3.  The reason is that, over a binary alphabet, the

(1) monotone gates ({AND, OR}),

(2) linear gates ({NOT, XOR}), and

(3) universal gates ({AND, OR, NOT})

basically exhaust the interesting possibilities, as follows from Post's classification theorem.  (Note that I assume that constants---0 and 1 in the binary case---are always available for free.)  With the linear gates, every Boolean function f:{0,1}n→{0,1} that's computable at all is computable by a linear-size circuit; with a universal set, of course we're up against Natural Proofs and the other terrifying barriers.

On the other hand, if we consider gate sets over a 3- or 4-symbol alphabet (for example), then a wider set of possibilities opens up---and at least to my knowledge, those possibilities have never been fully mapped out from the standpoint of complexity theory (please correct me if I'm wrong).  I know that the possible gate sets are studied extensively under the name of "clones" in universal algebra; I wish I were more conversant with that literature so that I knew what if anything the results from that area mean for circuit complexity.

In any case, it doesn't seem out of the question that there are other dramatic circuit lower bounds ripe for the proving, if we simply expand the class of gate sets over finite alphabets that we're willing to consider.  If I'm wrong, please tell me why!


texts: Variation on partial Set Cover with penalties

texts:
I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem:

Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup B=U$. We're also given a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq U$ for all $i=1\ldots k$. The sets $S_1,S_2,\ldots,S_k$ may or may not be disjoint, and the union of all $S_i$ may or may not equal the universe.

Solution form: A collection $C' \subseteq C$.

Objective function: Maximize $\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| - \left|\left(\bigcup\limits_{c \in C'} c\right) \cap B\right|$

In English, the objective function rewards solutions that cover a large number of elements in $A$ and penalizes those that cover a large number of elements in $B$. The best solution would be one that covers $A$ fully and does not cover $B$ at all. The worst solution covers $B$ fully and does not cover $A$ at all. The cardinality of $C'$ is not important.

Example: Universe $U=\left\{1,2,3,4,5\right\}$. Susbsets $A=\left\{1,3,4,5\right\}$ and $B=\left\{2\right\}$. Sets $S_1=\left\{1,2,3,5\right\}$, $S_2=\left\{1,4\right\}$ and $S_3=\left\{2,5\right\}$. Here the best solution is to take $S_1$ and $S_2$, which gives a measure value of $3$.

It's relatively trivial to adapt the classical greedy heuristic to get an approximate solution. My questions are 1) is this problem studied in any literature, and 2) do you think it would be possible to prove an approximation ratio for the greedy heuristic on it?

I had a look at A compendium of NP optimization problems and questions like this one, but haven't been able to find anything similar yet.


texts:
Let FP be the class of functions $f : \{0,1\}^* \to \mathbb{N}$ that can be computed in polynomial time. Moreover, given two functions $f : \{0,1\}^* \to \mathbb{N}$ and $g : \{0,1\}^* \to \mathbb{N}$, we say that there exists a logspace parsimonious reduction from $f$ to $g$ if there exists a function $h :  \{0,1\}^* \to \{0,1\}^*$ such that $h$ can be computed in logspace and $f(x) = g(h(x))$ for every $x \in \{0,1\}^*$.

I would appreciate it if someone could give me some references for problems that are complete for FP under logspace parsimonious reductions (or logspace Turing reductions).


texts: Techniques for showing that problem is in hardness "limbo"

texts:
Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this is difficult:

Show that the problem is GI-complete (GI = Graph Isomorphism)
Show that the problem is in $\mathsf{co-AM}$. By known results, such a result implies that if the problem is NP-complete, then PH collapses to the second level. For example, the famous protocol for Graph Nonisomorphism does exactly this.

Are there any other methods (maybe with different "strengths of belief") that have been used ? For any answer, an example of where it has actually been used is required: obviously there are many ways one might try to show this, but examples make the argument more convincing.


texts: Fast algorithm to find a maximum connected subgraph of k vertices

texts:
Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)$ is maximum.

This problem is a generalization of the maximum connected subgraph of size $k$, which can be solved by means of integer linear programming. Unfortunately, my objective function $f$ is nonlinear. One can enumerate all connected subgraphs of size $k$ and take one with the largest objective value. However, I think this approach is very slow. I also tried the color-coding technique but it is slow too. Does anyone know any best/fast algorithms to solve this problem in a such general scheme? Thank you in advance!


texts: Generating interesting combinatorial optimization problems

texts:
I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$ and bigger. I tried of course to generate a graph with a cost matrix with values taken from a random $U(0,1)$, and found out that (as expected) the histogram for the path cost (drawn by sampling a lot of random paths) has a very narrow normal distribution ($\mu$ is $~100$ but $\sigma$ is around $4$). This means, in my opinion, that the problem is very easy, since most random paths will be below the average, and the minimum cost path is very close to a random path.

So I tried the following approach: After generating the $U(0,1)$-matrix, take a long random walk around the graph, and randomly (Bernoulli with $p=0.5$) double or halve the value of the edge. This tends to lower all values, eventually reaching zero, but if I take just the right number of steps, I can get a distribution with $\mu$ around $2$ and $\sigma$ around $1$.

My question is, first, is this even a good definition for an interesting problem? Ideally I would want an instance that is highly multi-modal (for the most common neighborhood functions), and that has very few paths near the minimum value, so that most random solutions will be very far from the optimum. The second question is, given this description, how can I generate instances with such characteristics?


texts: Damerau–Levenshtein distance with transposition of non-adjacent characters?

texts:
Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want this for an application where I am examining differences between sentences, and when whole words or substrings are transposed more than one character, they are doubly penalized (subtracted then added).
In my searching, I found this question, which recommended using backtracking branch and bound schema that I'm too dumb to implement well. However, I came up with a simple heuristic: calculate Levenshtein distance, keep track of lists of additions and subtractions separately, and remove instances of letters that appear in both lists (on the logic that any subtract-add pair could be better implemented as transposition).
Is this heuristic a) mathematically similar to what I am looking for above or b) close enough that the distances would be heavily correlated for a sample of similar sentences? Can provide test examples if needed. Thanks!


texts: Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover?

texts:
Where can I get the photo of “Introduction to automata theory, languages and computation” by Hopcroft and Ullman '79 (first edition) cover in order to be able to read all the phrases placed on the cover? Obviously the ones that gave me Google.Images (from Wikipedia, Amazon and others) do not allow this.

Solved:
http://mmcs.sfedu.ru/~ulysses/Pics/Hopcroft-Ullman-79-cover.jpg


texts: Maximum Treewidth of a Graphs with $m$ Edges

texts:
What is the maximum treewidth of a graph with $m$ edges? In other
words, what is the correct growth for the following function?

$\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has $m$ edges}\}$.

Clearly $\alpha(m) = \Omega(\sqrt{m})$, which is attained
by cliques with $\Omega(\sqrt{m})$ vertices and by
by $\Omega(\sqrt{m})\times \Omega(\sqrt{m})$ grids.

Is this also the maximum?


texts: Efficient algorithm for testing planarity of the union of two planar graphs

texts:
Let $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ both be planar graphs.

Is there an efficient algorithm to check whether the union $G = (V,E_1\cup E_2)$ is planar?
That is, an algorithm more efficient than the obvious one of running the standard linear planarity test on the union.


texts: Example where equivalence is easy but finding class representative is hard

texts:
Suppose we have a class of objects (say graphs, strings), and an equivalence relation on these objects. For graphs this could be graph isomorphism. For strings, we could declare two strings equivalent if they are anagrams of each other.

I am interested in computing a representative for an equivalence class. That is, I want a function f() such that for any two objects x, y,
f(x) = f(y) iff x and y are equivalent.  (*)

For the example of anagrams, f(s) could sort letters in the string, ie. f('cabac') = 'aabcc'. For graph isomorphism, we could take f(G) to be a graph G' that is isomorphic to G and is the lexicoraphically first graph to have this property.

Now the question: Is there an example where the problem of determining whether two elements are equivalent is "easy" (poly time solvable), while finding a representative is difficult (i.e. there is no poly time algorithm to compute f() that satisfies (*)).


texts: What is reversible automaton and how it works?

texts: I have not understood how reversibility works in case of an automaton. Kindly explain.


texts:
Two-prover one-round (2P1R) games are an essential tool for hardness of approximation.  Specifically, the parallel repetition of two-prover one-round games gives a way to increase the size of a gap in the decision version of an approximation problem.  See Ran Raz's survey talk at CCC 2010 for an overview of the subject.

The parallel repetition of a game has the astonishing property that while a randomized verifier operates independently, the two players can play the games in a non-independent way to achieve better success than playing each game independently.  The amount of success is bounded above by the parallel repetition theorem of Raz:

  Theorem: There exists a universal
  constant $c$ so that for every 2P1R
  game $G$ with value $1-\epsilon$ and
  answer size $s$, the value of the
  parallel repetition game $G^n$ is at
  most $(1-\epsilon^c)^{\Omega(n/s)}$.

Here is an outline on the work of identifying this constant $c$:

Raz's original paper proves $c \leq 32$.
Holenstein improved this to $c \leq 3$.
Rao showed that $c' \leq 2$ suffices (and the dependence on $s$ is removed) for the special case of projection games.
Raz gave a strategy for the odd-cycle game that showed Rao's result is sharp for projection games.

By this body of work, we know $2 \leq c\leq 3$.  My two questions are as follows:

  Question 1: Do experts in this area
  have a consensus for the exact value
  of $c$?

If it is thought that $c > 2$, are there specific games which are not projective, but also specifically violate the extra properties of projection games that Rao's proof requires.

  Question 2: If $c > 2$, which
  interesting games violate Rao's
  strategy and have a potential to be
  sharp examples?

From my own reading, it seems the most important property of projection games that Rao uses is that a good strategy for parallel repetition would not use many of the possible answers for certain questions.  This is somehow related to the locality of projection games.


texts: Partial soundness proofs for pragmatic static analyses

texts:
I was reflecting on a comment by Rob Simmons on unsound static analyses:

  An analysis that is neither sound nor complete is called pragmatic by Jaspan, as there aren't any theorems to be proved about such an analysis: they can be justified only by their utility in practice.

This is a pretty unsatisfying way to evaluate a static analysis; surely, we can make stronger claims than statistical correlations. Could we, perhaps, show that analyses are sound given some additional assumptions on the program?

Consider the classic example of determining if a variable in a C program is constant.  A sound analysis requires a points-to analysis; an unsound analysis requires only a syntactic scan. It seems that it would be straightforward to prove the soundness of this analysis if we also assume that, at every assignment through a pointer, that pointer does not refer to the variable of interest. Such a proof should easily turn into an analysis that also outputs a finite list of assumptions made about specific program points to guarantee its soundness. Indeed, I already see comments on unsound analyses such as "This system is unsound because it assumes the inputs are unaliased," which suggests the theorem that the system is sound if the inputs are unaliased.

A search for "partial soundness" turns up a type theory paper, but no analysis papers. Systems such as CCured that generate dynamic checks upon the failure of the analysis seem related, but I've not seen them interpreted this way. Is there prior work along these lines?