texts: Is ALogTime != PH hard to prove (and unknown)?

texts:
Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP:

  Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization (Section 3) though none have panned out. Should be much easier than separating P from NP.

Section 3 in the linked survey claims that there are no meaningful oracle collapse results:

  While the P != NP question remains quite formidable, the L != NP question seems much more tractable. We have no reason to think this question is difficult. The lack of good relativization models for space means we have no meaningful oracle model where L and NP collapse. Also since L is a uniform class, the Razborov-Rudich [RR97] limitations do not apply.

A question about known relativization barriers to L != NP on this site got an answer pointing out that the PSPACE-complete problem TQBF can be used as oracle to get such a collapse. An objection about whether this was a meaningful oracle model seems to be answered too.

But even if I would understand why "we have no meaningful oracle model where L and NP collapse" should be considered to be a correct statement, I would still have my doubts whether proving L != NP is any more feasible than proving P != NP. If proving L != NP should really be easier than proving P != NP, then proving ALogTime != PH should definitively be within reach. (The survey article hints at the possibility to separate $\Sigma_2^p$ from $L$.) I guess ALogTime != PH is still open, and I would like to know whether there are good reasons to expect that it will be hard to prove.


texts: What are some real world applications for genetic algorithms?

texts: What are some real world problems that have been solved using a genetic algorithm?   What is the problem?  What is the fitness test used to solve this problem?


texts: Number of edge induced subgraphs with given vertex parity

texts:
Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.

  Questions

  How hard is to compute $O$?
  How hard is to compute the parity of $O$?

Related questions:

Number of (vertex induced) subgraphs with given edge parity Answer: Tractable.
Number of (edge induced) subgraphs with a given number of nodes Answer: #P-hard.

Update 11/05/2013 18:00

By a reasoning similar to the one in the answer to the first question referenced above, we can create a Holant by placing on each vertex $v$ a constraint $f_v$ which returns $1$ when all the edges incident to $v$ have been assigned $0$, and $-1$ otherwise. For a specific assignment to the edges ($0$ means not selected, $1$ means selected) we get an edge induced subgraph such that the number of its vertices is odd if and only if the product of the Holant returned $-1$. The summation of the Holant is thus equal to the difference $E - O$ between the number of edge induced subgraphs having an even number of vertices and the number of edge induced subgraphs having an odd number of vertices: as $E + O$ is known, we can determine $E$ and $O$.

Now, if I correctly understand the paper A Dichotomy for Real Weighted Holant Problems, the constraint $f_v$ is symmetric (obviously) and affine: by Theorem 3.2 this means that we can compute $E-O$ in polynomial time.

Am I right?


texts: SAT - Hardness of determining backbone literals

texts:
Let $F$ be a CNF formula. Let $l$ be one of $F$'s literals.

  Question
  Which is the complexity of determining whether $l$ is a backbone literal or not? The obvious way to do that is to propagate $\lnot l$ on $F$, obtaining $F'$: $l$ is then a backbone literal of $F$ if and only if $F'$ is unsatisfiable. I'm asking if there is another way.


texts: What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

texts: I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.


texts: Is this algorithm similar to any none in the literature?

texts:
I thought of the following algorithm for game AI, which is kind of a mashup of miniMax and Monte Carlo Tree Search. We assume that we have a heuristic function that assigns game states a value in the range $[0,1]$. (The heuristic is from the point of view of the player who just moved.)

The algorithm works as follows:

Start with a tree whose only node is the root. Assign it a heuristic value.
Traverse down the tree using UCT.

That is, when at a expanded node $n$, we select a child $c$ such that $\operatorname {value}(c) + E \sqrt{\frac{\ln d_n}{d_c}}$ is maximized, where $d_x$ is the total number of descendants of node $x$ (including itself). ($E$ is a tuneable constant corresponding to exploration.)

When we reach a leaf node, we add each of its children in the game tree to this algorithm's tree. We assign each of the children a heuristic value, and forget the parent's heuristic value.
Next, we assign each node in the tree its minimax value, according to the nodes currently in the tree and the heuristic values of the leaf nodes. Note that only the ancestors of the expanded leaf node should be affected, so this should be a quite update.

In particular, a node's value is equal to $\max_{c\in\text{children}}(1-\operatorname{value}(c))$, so it is kind of like negaMax.

If time and space is left, go back to step 2. Otherwise, continue to step 6.
Choose the child with the highest value, since this will give the moving player the best value.

The idea is that we are searching down the search tree progressively, using UCT to focus on good nodes that haven't been explored much yet. Unlike MCTS though, we use the minimax values instead of statistics to evaluate nodes.

Is there an algorithm similar to this already? I found SSS* which seems kinda similar, but I'm not sure, since I haven't found a good description of SSS*.


texts: How do you call a subsequence of consecutive elements ?

texts:
I wrote a function that returns the position of a given subsequence in a sequence. However, I just realized that I used the term "subsequence" incorrectly: according to Wikipedia, the elements of a subsequence don't need to be consecutive. But my function is actually looking for a "subsequence of consecutive elements"... is there a name for this notion? I thought of substring, but it seems to imply a sequence of characters, and my function is not specific to character strings..

I realize it isn't a very critical issue, but I'd like to give my function an accurate name...

Any idea would be appreciated !


texts: Fixed-parameter tractability of SCS: finding the missing proof(s)

texts:
I am interested in two "super-objects" problems from computational biology.

The first problem, dubbed Shortest Common Supersequence ($SCSy$), takes a family of sequences $s_1,\ldots,s_k$, and seeks a common supersequence of minimum length.
The second problem, dubbed Shortest Common Supertree ($SCSx$, introduced here), takes a family of p-trees $t_1,\ldots,t_k$, and seeks a common supertree of minimum length.

I have some issues ascertaining the fixed-parameter tractability or $\mathsf{W[1]}$-hardness of the following parameterizations:

(i) $SCSy$ parameterized by the number of sequences $k$: the problem is claimed to be $\mathsf{W[1]}$-hard in M. Hallett's thesis without proof;

(ii) $SCSx$ and $SCSy$ parameterized by the number of duplications of the super-object: in the above mentioned paper, the first problem is claimed to be FPT and the second is claimed to be $\mathsf{W[1]}$-hard, but I couldn't convince myself whether this is correct.

Any people from the FPT scene willing to help?


texts:
Let a quantum channel $\Phi(\cdot)$ between two Hilbert spaces $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$.
What is the quantum channel $\Phi_{inv}(\cdot)$ that best reverses $\Phi(\cdot)$ ?

$\forall $ states $\rho$, the state $\widetilde{\rho} \equiv \Phi_{inv}(\Phi(\rho))$ should be the best approximation of $\rho$ (according to some appropriate distance measure).

If we assume that the input state comes from a known probability distribution, according to the quantum data processing inequality there are cases, depending on the source entropy and the channel properties that allow for perfect decoding.

However, how do you perform decoding in cases where perfect decoding is not possible, and in particular if no source distribution is known (so you can't assume that the state has been encoded with an error-correcting code)? I presume somebody has already thought about this, but I can't find it in the literature.


texts: Bibliography needed: How many "good" solutions for Knapsack?

texts:
I am trying to find some related bibliography in the field. If, by chance, my question is easy enough though, a direct answer is more than welcome.

The problem is: Given that the best possible solution for our instance has value $v$, how many solutions have value at least (1 - ε)v? Of course, they should satisfy the constraint of the weight.

I face some difficulties finding the related bibliography in particular, because it seems it is quite often to consider the problem without trying to maximize an associated value but just trying to find the number of solutions in the corresponding linear Diophantine's equation.

Knapsack as in:

maximize $\sum_{i=1}^{n}u_ix_i$,

subject to $\sum_{i=1}^{n}w_ix_i \le W$, $x_i = {0, 1}$

Although, it does not really matter whether it is the 0-1, bounded or the unbounded problem.

What I have found so far and is somewhat related is:

Counting Solutions of CSPs: A Structural Approach
Upper Bounds on the Number of Solutions of Binary Integer Programs


texts: if I were to define a new complexity class how should I start?

texts: If I wanted to define my own complexity class would you first define it as a set of problems with reductions to those problems? How would one go about doing this?


texts: Understanding performance of QFBV SMT solvers

texts:
SMT solvers such as Z3 or Boolector use a complex set of heuristics to solve problems. However, this also makes predicting the performance of such a solver for a given problem very hard. My question is thus:

Question

Is there a way to understand or gain insights into the performance of a SMT solver for a specific in the theory of quantifier-free bitvectors (QFBV)?

This also includes any visualization tools that would help to understand where the solver is "stuck" / does not make progress.

Applications

Understand in advance how different encodings of the same problem affect solver performance (the state of the art here can't be "just try a few different encodings and hope one is fast enough", right?)
If a given problem is not solveable by an SMT solver due to time constraints, find a way to express the problem differently so that it can be solved.
Avoid wasting time on domain-specific problem simplifications that won't affect solver performance at all or even negatively affect solver performance.

Existing research

I tried to find research on this topic, but I have not been able to find much. I do not have much experience in the field of SAT/SMT solvers yet, so apologies if I have missed something.

SATzilla: predicts best performing solver based on features extracted from the problem using machine-learning techniques.

This applies only with SAT instead of SMT, and does not explain the reasons for solvers performance.
Z3 axiom profiler A visualization of Z3 instantiation graph and analysis of matching loops

Looks like this focuses only on the quantified theories.


texts: Sufficient condition for termination of an orthogonal first-order rewriting system?

texts:
I have a terminating orthogonal first-order rewriting system with finite rule set $R$.

Question: What would be an algorithmically verifiable sufficient condition on a new rule $l\to r$ such that for the rule set $R\cup \left\{l\to r\right\}$ the system also terminates? (How to extend the rule set maintaining the termination property?)


texts: List of papers on Runtime and Statistical Tradeoffs on Machine Learning

texts:
I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having more data actually help the algorithms run faster? Or maybe not run faster but yield better results.

Let me give you two papers with such examples:

“SVM Optimization: Inverse Dependence on Training Set Size”, Shalev-Shwartz,
Srebro.

This first example discusses how the runtime of SVM optimization should decrease as the training data increases in a theoretical (and empirical) framework.

A second example:

“More Data Speeds up Training Time in Learning Halfspaces over Sparse Vectors”,
Daniely, Linial, Shalev-Shwartz.

On how we get computational speed ups as data increases when learning halfspaces over sparse vectors.

I was wondering if there were other interesting papers on the same or similar spirit as the two above.


texts:
I wonder, what is (currently) the largest number $k$, such that a natural problem is known with the following properties:

An $O(n^k)$ algorithm has been already found for the problem.
For any fixed $\epsilon>0$ no $O(n^{k-\epsilon})$ algorithm is known for the same problem. (Note that a faster algorithm $may$ exist, just it is not known yet, so I am not looking for a proven lower bound.)
The problem description itself does not depend on $k$. (This condition is needed to exclude parametrized cases like "find a clique of size $k$ in an input graph, for a constant $k$.")

In a sense, such a problem might qualify as the hardest, known, natural, problem in $\bf P$ (regarding the exponent of the fastest known algorithm).


texts: What progress is being made on $NP \cap coNP$ having complete problems?

texts: I'm very curious about this and have a proof sketch that it does not in the answers below. The reasons I'm currently thinking about this is because of the new paper on the class $PTFNP$ which can be downloaded here.


texts:
Have partition trees ever been implemented?

Here, I'm talking about the partition trees from computational geometry.  The earliest (near-)optimal versions of which were due to Matousek and others, and most recently Timothy Chan:

https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf

It sounds crazy to me that these have never been implemented, but googling turned up no implementations that anyone has ever reported on.


texts: Has anyone mixed linear algebra with formal language theory in this way?

texts:
Let $G$ be the grammar:
$$
S \rightarrow aAb \\
A \rightarrow aA + a + \epsilon
$$

where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol.  Consider vectors of grammar rule RHS's, for instance the basic one $\nu = \begin{pmatrix} S\\A\\a\\b\\\epsilon\end{pmatrix}$.  Then $\nu$ is an eigenvector of some matrix that transforms vectors of grammar rule RHS's into the same.

Let $T =
\begin{pmatrix}
0 & 0 & 0 & aA & 0\\
0 & a & \epsilon & 0 & \epsilon \\
0 & 0 & \epsilon & 0 & 0 \\
0 & 0  & 0 & \epsilon & 0 \\
0 & 0 & 0 & 0 & \epsilon
\end{pmatrix} $

Then if we let $0$ represent the empty set and concatenation by it equals $0$, then $\nu \rightarrow T\nu$ is an eigenvector with eigenvalue $\epsilon$.

Unrelated, but a regular language is represented by $T$ with only terminals and $\epsilon$ in the matrix.

Edit

I'm interested in any ideas.  Thanks.


texts:
Coq, Agda, and Idris have an infinite type hierarchy (Type 1 : Type 2 : Type 3 : ...). But why not do it instead like λC, the system in the lambda cube that's closest to the calculus of constructions, which has only two sorts, $*$ and $◽$, and these rules?

$$\frac {} {∅ ⊢ * : ◽}$$

$$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ t : T _ 2} {Γ ⊢ (λ \: x : T _ 1, \: t) : (Π \: x : T _ 1, \: T _ 2)}$$

$$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ T _ 2 : s _ 2} {Γ ⊢ (Π \: x : T _ 1, \: T _ 2) : s _ 2}$$

This seems simpler. Does this system have important limitations?


texts:
Suppose we're given a graph $G$ and parameters $k,\epsilon$. Are there ranges of values for $k$ (or is it doable for all $k$) for which it is possible to test whether $G$ is $\epsilon$-far from having an independent set of size at least $k$ in time $O(n + \text{poly}(1/\epsilon))$ ?

If we use the usual notion of $\epsilon$-far (i.e at most $\epsilon n^2$ edges would need to be changed in order to obtain such a set), then the problem is trivial for $k = O(n\sqrt{\epsilon})$.  So

It seems that if $k$ is larger, some sampling ideas should work to solve the problem. Is that true ?
Are there other notions of $\epsilon$-far (i.e maybe $\epsilon |E|$ edges instead) under which there are nontrivial results ?

I'm basically looking for references at this point.


texts:
I'm studying proof theory and I've seen that linear logic can be used as a way to control resource usage, since by the propositions-as-types it is equivalent to the linear lambda calculus.

Is there a logic that allows resource control (like linear logic) and can express properties that vary over a notion of time like linear time temporal logics (LTL)?

Any reference or point to literature is highly appreciated.


texts: About the small set expansion conjecture

texts:
Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \vert S\vert \}  }$) The ``small-set expansion conjecture" states that it is NP-Hard to determine if this is below $\epsilon$ or above $1-\epsilon$ for $\epsilon = 1/O(log(\frac{1}{\delta} ) )$

For context one notes that $h(G,\delta = \frac{1}{2})$ is the Cheeger constant which is known to be NP-hard to bound. But there does seem to exist values of $\delta$ (which ones?) for which $\phi(G,\delta)$ can be computed in polynomial time?

Towards understanding the small-set expansion conjecture one seems to prove this statement,

If $W$ is the span of the Laplacian eigenvectors of $G$ such that their eigenvalues are less than some $\lambda \in [0,1]$ and if every $w \in W$ satisfies $\mathbb{E}_i[w_i^4 ] \leq C ( E_i [w_i ^2 ]  )^2$ then for every set $S$ such that $\vert S \vert \leq \delta \vert V \vert$ we have $\phi(S) \geq \lambda(1 - \sqrt{C \delta}  )$

[Reference, Lemma 8 here, http://www.boazbarak.org/sos/files/lec2d.pdf ]

My questions are,

How does the above theorem help understand the conjecture stated at the beginning? What is the relationship between the two?
Why should such vectors $w$ exists as demanded in the theorem? What is the intuition behind looking at such $w$?
What is the intuition behind choosing that specific value of $\epsilon$ as in the statement of the conjecture?


texts: How good is the Huffman code when there are no large probability letters?

texts:
The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a well-known theorem that the average length per symbol of the Huffman code is between $H(p)$ and $H(p)+1$, where $H(p) = -\sum_i \, p_i \log_2 p_i$ is the Shannon entropy of the probability distribution.

The canonical bad example, where the average length exceeds the Shannon entropy by almost 1, is a probability distribution such as $\{.999, .001\}$, where the entropy is nearly 0, and the average codeword length is 1. This gives a gap between the entropy and the codeword length of almost $1$.

But what happens when there is a bound on the largest probability in the probability distribution? Suppose, for example, that all the probabilities are less than $\frac{1}{2}$. The largest gap I could find in this case is for a probability distribution such as $\{.499, .499, .002\}$, where the entropy is slightly more than 1 and the average codeword length is slightly less than 1.5, giving a gap approaching $0.5$. Is this the best you can do? Can you give an upper bound on the gap that is strictly less than 1 for this case?

Now, let's consider the case where all the probabilities are very small. Suppose you choose a probability distribution over $M$ letters, each having probability $1/M$. In this case, the largest gap occurs if you choose $M \approx 2^k \ln 2$. Here, you get a gap of around
$$ \frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607. $$
Is this the best you can do in the situation where all the probabilities are small?

This question was inspired by this TCS Stackexchange question.


texts: Version control for collaboration (with word-level diffs)?

texts:
Most papers are now written collaboratively, and collaborators are often located in different places.  I have always used version control systems for my documents and code, and have also found version control critical for collaborative software projects, but it seems many researchers in theory avoid their use for writing joint papers.  To convince my collaborators that version control (revision control) is a good idea for working together, there seem to be some prerequisites.  It is not possible to force everyone to worry about a specific set of conventions for line breaks and paragraphs, or to avoid tab/space conversions.

  Does someone offer free hosting of small shared document repositories, with text-document-friendly version control that can handle word-level diffs (not line-based)?

If not, then I would welcome other suggestions that are based on experience (let's avoid speculation, please).

I was thinking of Git, Subversion, Mercurial, darcs, or Bazaar, set up to handle word-level differences with wdiff, together with a simple way of setting up access secured by public keys (for instance via ssh).  However, none of the version control providers that I looked at seem to offer anything like this.  For scientific collaboration the "enterprise" features stressed by many of these companies are not very important (lots of branches, integration with trac, auditing by third parties, hierarchical project teams).  But word-level diffs seem critical yet unsupported.  In my experience, with line-level diffs for text files, everyone has to avoid reformatting paragraphs and editors that change tabs to spaces or vice versa cause problems; there also seem to be many spurious edit conflicts.  I have used wdiff and latexdiff quite successfully to help with manual merging of changes previously, so I am hoping a word-level diff would reduce such problems.

See related question at MO about tools for collaboration, and related questions over at TeX.SE, about version control for LaTeX documents and LaTeX packages for version control.  See also the SVN Hosting Comparison Review Chart for a large list of hosting providers, for just one of the main version control systems.

Edit: Jukka Suomela's answer to the TeX.SE question "Best LaTeX-aware diff and merge tools for subversion" seems to be the best suggestion so far, covering how to interpret the deltas on a word level.  Moreover, Jukka has explained how the differences between successive versions on the repository end are separate from the user-level differences used for conflict detection and merging of changes.  Jukka's answer at TeX.SE explicitly excludes simultaneous edits and merging, relying instead on the traditional atomic edit token to avoid edit conflicts.  Clarifying (and modifying) my original question, is there a way to ensure that edit conflicts can be resolved on a word difference basis, rather than on a line difference basis?  In other words, can wdiff or similar tools be integrated into the conflict detection part of the version control tools, similar to the way end-of-line differences and differences in whitespace can be ignored?


texts: Is there an oracle such that SAT is not infinitely often in sub-exponential time?

texts:
Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all instances of length $n$. (That is, this is the class of languages which can be "solved infinitely often, in subexponential time".)

Is there an oracle $A$ such that $NP^A \not\subset io$-$SUBEXP^A$? If we equip SAT with the oracle $A$ in the usual way, can we say that $SAT^A$ is not in this class?

(I'm asking separate questions here, because we have to be careful with infinitely-often time classes: just because you have a reduction from problem $B$ to problem $C$ and $C$ is solvable infinitely often, you may not actually get that $B$ is solvable infinitely often without further assumptions on the reduction: what if your reduction from $B$ "misses" the input lengths that you can solve $C$ on?)


texts: Why do timeouts require synchronized clocks?

texts:
In Impossibility of distributed consensus with one faulty process @1985 by Fischer at al., the authors state (p375)

  We also assume that processes do not have access to synchronized clocks, so algorithms based on timeouts, for example, cannot be used.

Why do algorithms that employ timeouts require that clocks be synchronized across processes?


texts:
In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from having the property. (An algorithm can be asked to succeed with 1-sided or 2-sided error.)  A graph is $\epsilon$-far from having a property if no $\epsilon \binom{n}{2}$ edges can be added/subtracted to make it have the property.

A property is said to be testable if it can be tested in the manner specified above in a sub-linear number of queries, or better yet, in a number of queries independent of $n$ (but not $\epsilon$).  The notion of what properties are can also be formalized, but it should be clear.

There are many results characterizing what properties are testable, with many examples of natural testable properties.  However, I am not aware of many natural properties that are known to not be testable (say in a constant number of queries) -- one that I am familiar with is testing for isomorphism to a given graph.

So, my question is: what natural graph properties are known not to be testable?


texts: I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you


texts:
Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique?  Garey and Johnson do this for the various kinds of widget constructions needed for NP-completeness proofs (particularly in chapter 3 of their book), but I'm wondering if there's anything that treats proof techniques in TCS more broadly.

So for example, topics might include diagonalization, broken down further by the type of construction used; proofs by computation histories; tableau constructions; incompressibility arguments, etc.  I suppose I could just chop up a standard theory of computation text and rearrange the sections, but it would be great if there is something out there that also provides some additional commentary and shows where there are commonalities between the techniques being used.

Just to be clear, since any text is going to use proofs, what I'm really interested in finding is a reference where the proof techniques themselves are the actual subject matter.

In addition to chapter 3 of Garey and Johnson, here's another partial example that just occurred to me: in Li and Vitanyi, in chapter 6 they discuss the incompressibility method and give examples of how to apply the technique.


texts: What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

texts:
I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ripe for such problems"). It has been proven that a class of "Collatz-like" problems is undecidable. However, problems that are vaguely similar such as Hofstadter's MIU game (resolved, but admittedly more of a toy problem) are indeed decidable or have been solved.
Related questions
Collatz Conjecture & Grammars / Automata


texts:
it is well known that the modal $\mu$-calculus is one of the most expressive temporal logics for expressing properties of trees/graphs, and that CTL* is strictly less expressive than the $\mu$-calculus.

Here I would like to ask for an example of $\mu$-calculus formula, as simple as possible, that is not expressible in CTL*, and hopefully for an explaination of its meaning (fixed-point formulas quickly become unreadable).
Any good reference for a "concrete" simple example would also be great!

Thank you in advance


texts: Are finite state automata with one register storage equivalent to push down automata?

texts:
This is a very simple question, but I couldn't find a reference and I just wanted to check my facts. I was looking for a state machine similar to pushdown automata but where the stack is restricted to one element (i.e. a register).

It occurred to me that if the register has an infinite alphabet (of possible values) it will basically be equivalent to a PDA. Every configuration of the stack could be represented by a single element of the register's alphabet. (E.g. let's say that the register's alphabet is the set of natural numbers). Is this correct?

Furthermore, a DFSM is equivalent in strength to a NFSM. However, I assume that (DFSM + 1 register) would not be equivalent to a (NFSM + 1 register) since DPDA and NPDA are not equivalent?


texts: Implications of a recent negative result to geometric complexity

texts:
A paper was posted in arxiv http://arxiv.org/pdf/1512.03798.pdf titled 'Rectangular Kronecker coefficients and plethysms in geometric
complexity theory' by Christian Ikenmeyer and Greta Panova with first line in abstract stating 'We prove that in the geometric complexity theory program the vanishing of rectangular Kronecker coefficients cannot be used to prove superpolynomial determinantal complexity lower bounds for the permanent polynomial'.

If correct what is the implication of this result to the geometric complexity theory program for separating permanent from determinant?


texts:
Is there any paper which can be used to show that there can be no relativizing construction of a secret-coin Collision-Resistant Hash Family from a one-way function and unlike this paper, does not claim to show more than it actually shows?

The second link shows some result, and I believe that what it actually shows
is strong enough, but I'm quite hesitant to cite that paper because the author
 writes "we show that relative to an oracle non-interactive weakly-binding honest-receiver statistically-secret commitments schemes do not exist" despite his definition of "non-interactive weakly-binding honest-receiver statistically-secret bit commitment scheme"s corresponding to an otherwise semi-honest receiver that is allowed to choose its "random bits" maliciously, and requiring perfect completeness and gives a definition of a "black-box one-way permutation" that does not require injectivity.


texts: Assignment problem with multiple workers for each job

texts:
I am wondering if there are any results on the following version of the assignment problem.  We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given the expertise of the worker for the job $\omega(w,j)$.  The goal is to select a subset of jobs $S\subseteq J$ and assign exactly two workers to each job $j \in S$ while maximizing the total expertise.

That is, if $x_{w, j} = 1$ indicates that the worker $w$ has been assigned to job $j$, solve the following program:

$$
maximize \sum_{j \in S}  x_{w, j} \cdot \omega(w, j)
$$
s.t.
$$
\sum_{j\in S} x_{w, j} \leq 1,  \forall w\in W
$$
$$
\sum_{w\in W} x_{w, j} = 2, \forall j \in S
$$
$$
x_{w, j} \in \{0, 1\}
$$

Edit:

It seems like my explanation is not very clear so I am adding a simple example.  Consider the following graph where dotted edges have weight 0 and solid edges have weight 1.  Worker $i$ has expertise $1$ in job $i$ and expertise $0$ in the other job.

The two possible solutions both have value 1: either assign both workers to job 1, or assign both workers to job 2.  Observe that assigning worker 1 to job 1 and worker 2 to job 2 would result in a solution of value 2, but it is not a valid solution since a job must be assigned exactly 2 workers.


texts: can some one use a polynomial one-to-many reduction for NP-comp problems?

texts:
For proving a decision problem is NP-com, there are diffrent methods of reductions as parsimonious, like karp-reduction, or many-to-one reductions!
What about one-to-many map? is it possible to set a polynomial one-to-many reduction from NP-comp decision problem 'A' to a decision problem 'B' which we are looking for it's complexity?


texts: Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

texts:
May be this is trivial but I do not know the answer.

As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds.

As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ could hold. Am I correct in this?

If so is there a problem that is currently known to be in $$\mathsf{BPP}\backslash\mathsf{NP}\cup\mathsf{coNP}=\mathsf{BPP}\cap\overline{\mathsf{NP}}\cap\overline{\mathsf{coNP}}$$ but conjectured to be in $\mathsf{P}$ just because of our belief $$\mathsf{P}=\mathsf{BPP}$$ should be true essential verdict?

That is is there a natural problem (not amalgamated ones) with a randomized poly algorithm nevertheless does not have a short yes or no certificate? A problem that comes close is PIT which is not known to be in $\mathsf{NP}$ but is in $\mathsf{coNP}$ which is the basis of the amalgamated problem (non-natural) below by Ricky Demer.


texts: An explanation of Whirlpool C implementation - or the general algorithm

texts:
Note: Question originally asked on StackOverflow - was directed here

Anyone got a tutorial on the designers concept implementation of Whirlpool in C, or the Whirlpool algorithm in general? I find the source code hard to understand, mostly because I do not know anything about the algorithm. I am not a cryptographer, nor am I a good mathematician, so their documentation kind of went over my head...

The implementation and other documentation can be found here.

Initially I was just searching for a free (public domain) implementation to use in a project, but I figured I better know something about it as well... Currently I do not even know how to use it.


texts: Approximation algorithm for finding the maximum common subgraph in two DAGs

texts:
Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the subgraph that is common to both graphs and has the most number of vertices. That is to find the biggest graph which is a subgraph of both $A$ and $B$. The vertices are not labeled, but of course, the directions on edges do matter.

Noting that this solves the graph isomorphism, the problem is not known to be solvable in polynomial time. So I was looking for an approximation algorithm. Can you think of any?


texts: The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems

texts:
The completeness and soundness in interactive proof systems are informally defined as:

Completeness: If a statement is true, the honest prover can convince the honest verifier of this fact w.h.p.
Soundness: If a statement is false, the cheating prover cannot convince the honest verifier (of the validity of the false statement) w.h.p.

The term "w.h.p." is either interpreted as "with probability greater than (say) 2/3," or "with probability greater than the reciprocal of any polynomial." It seems immaterial to the following discussion as what interpretation of "w.h.p." to choose.

The tricky part is how the probability is computed: In some sources, the probability is taken over the random coins of both the prover and the verifier. In other sources, the probability is only computed over the random coins of the verifier. The latter is usually justified as: "whatever the random coins of the prover are, the verifier makes the right decision."

To me, both definitions of probability seem equivalent; yet I can't prove this. Am I right? Can you prove them equivalent?


texts: Continuation passing transform of binary functions

texts:
Recall the continuation passing transform (CPS transform) which takes $A$ to $\beta A \mathrel{{:}{=}} R^{R^A}$ (where $R$ is fixed) and $f : A \to B$ to $\beta f : \beta A \to \beta B$ defined by
$$\beta \, f \, \kappa \, r \mathrel{{:}{=}} \kappa (r \circ f).$$
In fact we have the continuation monad with the unit $\eta_A : A \to \beta A$ defined by
$$\eta_A x \mathrel{{:}{=}} \lambda r . r \, x$$
and the multiplication $\mu_A : \beta (\beta A) \to \beta A$ defined by
$$\mu_A \, K \, r \mathrel{{:}{=}} K (\lambda f . f \, r).$$

Now let us think about how we can transform a binary map $f : A \to B \to C$, i.e, we want $\gamma f : \beta A \to \beta B \to \beta C$. One quickly comes up with
$$\gamma \, f \, \kappa \, \nu \, r \mathrel{{:}{=}}
   \kappa (\lambda x . \beta (f x) \nu r).$$
This makes sense from a programming point of view as well.

Here is my question: is there a deeper reason for $\gamma$, other than the fact that it looks right from a programming point of view? For instance, is there a category-theoretic or other "theoretical" reason for thinking that $\gamma$ makes sense? For instance, can we cook up $\gamma$ from the monad in a systematic way?

I am looking for an insight into CPS transforms of $n$-ary functions.


texts: Hierarchical sorting strategies for pattern-avoiding permutations?

texts:
For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \mathcal{C} \cap S_n$.

In particular, when $\mathcal{C}$ is closed by subpatterns, it follows by Marcus-Tardos theorem (refined by J. Fox) that $|\mathcal{C}_n| \leq C^n$ where $C$ is the Stanley-Wilf constant of $\mathcal{C}$. This leads to the following question: is it possible to sort such a class using at most $O(n \log C)$ comparisons? This question is a strengthening of Question 1 in the paper 'Fast Sorting and Pattern-avoiding Permutations' by D. Arthur.

It seems possible to represent such a sorting strategy by a binary tree which would essentially mimic an 'unbalanced' merge-sort algorithm. Here is the idea: given a permutation $\pi$, we would look for a tree $T_{\pi}$ leaf-labeled by the points of $\pi$, such that for each node $u$ of $T_{\pi}$ the 'overlap' between the two child subtrees would be $O(\log C)$ (either worst-case or on average). However I suspect that a more involved structure is necessary to solve this problem; should it admit a positive solution.


texts: Post correspondence problem for finite monoids

texts:
The Post correspondence problem has the following version for finite monoids:

Input: a finite monoid $M$ and a finite list $(m_1,m_1'),\ldots, (m_n,m_n')$ of pairs of elements of $M$

Question: is there a natural number $k\geq 1$ and indices $i_1,\ldots, i_k\in \{ 1,\ldots, n\}$ such that $m_{i_1}\cdot\cdots \cdot m_{i_k} = m_{i_1}'\cdot\cdots \cdot m_{i_k}'$?

Is it known whether this problem is decidable?


texts: "Verifiable information": is this a known concept?

texts:
The following seems to me like a natural definition and I wonder whether it's been studied somewhere

Consider $\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}$ a set of languages.
Then $K \subset \lbrace 0, 1 \rbrace^\omega$ is called "$\mathsf{X}$-verifiable information" when there is $L \in \mathsf{X}$ s.t.

(i) Given $x \in L$, every prefix of $x$ is in $L$

(ii) Given $f \in K$, every prefix of $f$ is in $L$

(iii) Given $f \notin K$, the length $n$ prefix of $f$ is outside $L$ for $n >> 0$

For example $\lbrace f \rbrace$ is $\mathsf{R}$-verifiable information iff $f$ is computable. This can be seen by constructing an algorithm which runs the verification on all strings of length $n$ and collects the prefixes of length $m$ of those strings which passed the verification. For $n >> m$, the only prefix which remains is the correct one

However if $K$ is $\mathsf{R}$-verifiable information it doesn't mean every $f \in K$ is computable: for example consider $K = \lbrace 0, 1 \rbrace^\omega$

A non-trivial example of $\lbrace f \rbrace$ which is $\mathsf{P}$-verifiable is as follows. Consider $L \in \mathsf{NP} \cap \mathsf{coNP}$ and let $f$ be an encoding of $L$ together with the corresponding $\mathsf{NP}$ and $\mathsf{coNP}$ witnesses (i.e. for each $x \in \lbrace 0, 1 \rbrace^*$, $f$ encodes either an $\mathsf{NP}$-witness proving $x \in L$ or a $\mathsf{coNP}$-witness proving $x \notin L$)


texts: Why are folded Reed Solomon Codes considered non linear?

texts: This is for my understanding. What am I missing?


texts: Perfectly matchable edges in a bipartite graph

texts:
Consider the following problem:

Given a bipartite graph $G = (V, E)$, an unmatched edge is one that does not appear in any perfect matching. Design an algorithm to find all unmatched edges. (assume |V| = n and |E| = m)

There is an $O(m + T(m, n))$ algorithm to solve this problem [1, Web exercise 36]. Where $T(m, n)$ is the time complexity of the best algorithm for finding perfect matching in a bipartite graph $G$. I want to get a reference to the research paper/work where the algorithm was proposed, for citation.

[1] http://algs4.cs.princeton.edu/42directed/


texts: Growth rate of primitive recursive functions

texts:
Pardon me for asking a question whose answer is surely well-known, but
is beyond my expertise:

  Q. Is the growth rate of each primitive recursive function $f(n)$ bounded by some exponential $O(c^n)$, or $O(n^n)$, or ...?

I know Ackermann's function grows faster than exponential, but it is not primitive recursive.


texts:
The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable language L, the Kolmogorov Complexity of a Decidable Language (KCDL) $^2$ is the size of the smallest program that decides on L.

  Is it possible to reduce KC to KCDL? If so, is it possible to do the reverse?

Notes

I don't know if anyone has already defined this concept, so if you have any reference to that definition or even it doesn't make sense, I would be happy if someone commented.
we can generalize this concept to more classes of languages, but I prefer to keep it simple here.

Addendum: $f(w)$ is a computable function that decides $w$ is a word in the language $L$. And, KCDL is define as:
$$\text{KCDL}(f) = \min \{ \text{length}(p) : \forall p \in TM, p \text{ compute } f\}$$

And, note that there is a difference between:

the compressed version of a program that computes a function;
the smallest program that computes the same function.

If you want to think of the compressed version of a program as the program itself, you cannot forget to take into account the size of the smallest program that does the decompression. Because, first you need to unzip the program file to be able to use it.


texts:
Let $CC^0[m]$ be the class of constant-depth, polynomial-sized circuits consisting entirely of $MOD_m$ gates, which put out $1$ iff the sum of their inputs $\equiv 0~(\textrm{mod}~m)$. In the same way that $DLOGTIME$-uniform $AC^0$ is equivalent to $FO[<,bit] = FO[+,*]$, in multiple sources 1, 2 it's asserted that $DLOGTIME$-uniform $CC^0$ is equivalent to $MOD[+,*]$, the set of logical sentences using only the modular quantifier $\exists^{(m,k)}$ that evaluates to true iff the number of satisfying solutions is congruent to $k$ mod $m$.
However, all of the sources that are cited for these claims 3, [4], [5] only provide proofs for the classes $AC^0, ACC^0, TC^0, NC^1$ and rely on the usage of standard quantifiers $\forall, \exists$, which are not proven to be expressible in $CC^0$. Does anyone know of how to modify the original proofs of $DLOGTIME-AC^0 = FO[<,bit] = FO[+,*]$ to achieve $DLOGTIME-CC^0 = MOD[<,bit] = MOD[+,*]$ without using these quantifiers, or a source for such proofs?
[4]: Introduction to Circuit Complexity: A Uniform Approach by Heribert Vollmer
[5]: Descriptive Complexity by Neil Immerman
(These proofs mostly just follow the one laid out in 3)


texts: Is it NP-hard to _play_ minesweeper perfectly?

texts:
This paper shows that it is NP-hard "to determine if there is some pattern of mines in the blank squares that give rise to the numbers seen."

If there is a way to "lead a perfect player into" such positions, then it would easily follow that it is also NP-hard to play minesweeper perfectly. However, I do not see any way to rule out the possibility of an algorithm that plays minesweeper perfectly by never going into the sort of positions that would be produced by applying that paper's reduction to hard instances of SAT.

Is playing minesweeper perfectly known to be NP-hard?


texts: Are There Highly Symmetric NP- or P-complete Languages?

texts:
Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on sets $L_n = \{ l \in L \mid |l| = n  \}$ such that there are few orbits, i.e such that $|L_n / G_n| < n^c$ for big enough $n$ and some $c$, and such that $G_n$ can be generated given $n$ efficiently?

The point here is that if one finds a language/group such as this, and if one can find normal forms under polynomial time group actions in $\mathrm{FP}$, then one can reduce $L$ by a $\mathrm{PTIME}$ reduction  to a sparse language by computing the normal form for any given $N$, implying that $\mathrm{P = NP}$ or $\mathrm{L = P}$, depending on whether you chose an NP- or P-complete language initially, respectively. So it seems that either there are no such groups with sparse orbits or that computing normal forms is hard for all such groups or one of these results will hold which I think most of us don't believe. Also it would seem that if one can compute the equivalence relation over the orbits instead of the normal forms, one could still do this nonuniformly, in $\mathrm{P/poly}$. Hoping some other people have thoughts on this.


texts:
Update: A slightly different version of this question has been answered here.

As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
If the quantum computer would be powerful enough to solve problems in NP (like factoring, using Shor's algorithm), it would be easy to verify the results, however, this computational power is not available yet.
As an intermediate step,

  what could be a problem within reach of today's quantum computers whose output can be verified efficiently with a witness?

Here efficiently need not stand for the problem itself being in NP, but rather it would be sufficient that the correctness of the solution is in NP.
For example, consider a satisfiability task whose literals are $x_i$'s and $y_j$'s.
If the quantum computer can produce all the $x_i$ that are part of a solution, then a witness for its correctness would be finding the $y_j$'s that make $(x,y)$ into a solution.
The corresponding $y$ can be found with a classical algorithm, or set as a challenge, like in case of Bitcoin, to mint some quantum coin, with the computational power of all the miners looking for the witness.
In fact, miners can be also rewarded for finding another $(x',y')$ solution of the original problem, which would determine whether $x$ is useful or not.

So what could be such a problem?
Can Shor's algorithm or some other similar problem be broken into finding some $x$ with a quantum computer that can be extended into a witness with some (smaller) $y$?


texts: How powerful is $ACC^0$ circuit class in average case?

texts:
We know that $NEXP$ is not in $ACC^0$ .

Does the result that $NEXP$ is not in $ACC^0$ also hold in average case?

That is given a boolean function in $NEXP$ is it known that for every input length $n$ we cannot have $\frac1{n^c}$ ($c>0$) fraction of possible computable in $ACC^0$?

Tying up with communication complexity I think what I seek could be the following. Since $NEXP$ is not in $ACC^0$ is known could it be that any $NEXP$ complete function has superpolylogarithmic communication complexity in NOF model with superpolylogarithmic number of players?

Then the query is could the randomized complexity still be just logarithmic. Is this possible?

Generally speaking what is the smallest class $\mathcal C$ that is known such that given a boolean function in $\mathcal C$ it is known that for every input length $n$ we cannot have $\frac1{n^c}$ ($c>0$) fraction of possible inputs computable in $ACC^0$?


texts: compleixty of rational checking of eigenvalues

texts:
Given a matrix $A$ with rational entries, how to check whether all the eigenvalues of $A$ are  rational?

What's the complexity of this problem? It seems that this can be done in polynomial time, but is there a tighter upper bound?


texts: Does assigning missing literals after unit propagation keep a Boolean formula satisfiable?

texts:
Let's denote $F$ a Boolean formula (in CNF if you wish) and $F_{a}$ the same formula where literal $a$ was assigned and propagated (using unit propagation).

If $F_{a} \rightarrow b$ (b is propagated from a) and $F_{\neg a} \rightarrow b$ then I can imply $b$ ($\neg a \rightarrow b \land a \rightarrow b \Rightarrow b $). In other words, any satisfying assignment for $F$ must have $b$.

If $F_{a} \rightarrow b$ and $F_{\neg a}$ is independent of $b$, is there always a satisfying assignment for $F$ that has $b$ when $F$ can be satisfied?


texts: How to determine if a function is negligible?

texts:
In cryptography (and probably in many other areas) there is a huge usage of negligible functions when proving theorems.

Although I know what is a negligible function, every time I encounter a function that need to be determined as negligible or not I just don't know how to do that. I just say that the function is negligible if it seems like $c/2^n$ where $c$ is a constant (or known to be negligible).

Can you provide an efficient method to determine quickly if a function is negligible or not?


texts: Diving straight into "research" versus studying broadly as an undergrad (soft question)

texts:
I'm nearing the end of my first year as an undergraduate and am very confident that I want to pursue a PhD in TCS. Fortunately because I quickly realized what I'm interested in and have a solid background in math, I've been able to take multiple TCS classes early on so as to get exposure in the field. I've also been doing lot of study on my own as time allows (though of course it is difficult when taking classes).

It also so happens that I live very close to my university, and at my request one of my professors was nice enough to say that I could come in and work in the theory space every day during the summer. It is still really up in the air as to what I will actually focus on, but I'm just excited to have a space to study TCS all summer.

Since as I said I'm only a first-year, one thing my professor emphasized is I have a choice many undergrads don't have: I could spend the summer doing "research" or studying far more broadly. I put research in quotation marks because I don't think I have enough experience to actually collaborate with a graduate student, but I could devise my own project. I.e., try to find some very recent results in a topic that doesn't require too much advanced math and just go at it.

On the other hand, I found a lot online advising undergrads to (if possible) study broadly instead of narrowly since obviously you aren't going to be working on the same problem in 10 years. To me, studying broadly would look like spending the summer going through as many textbooks as possible and doing lots and lots of exercises. (I would still find this a lot of fun!) And also reading papers in different areas. That said, there is the ever-looming pressure of graduate admissions and the need for some kind of publication.

So my question is basically what would you recommend to do in my situation? (But more widely, should an early undergrad go for depth or breadth?) Some other thoughts I've had:

I could obviously come up with some kind of compromise. Instead of doing a "research" project I could read and present lots of papers. Since going through a paper is a mini project in itself for me at this point, this would give me some depth but obviously not at the level of a project.
Some comments I've read online suggest that one reason to emphasize breadth if possible is it will lead to a far smoother initial research experience down the road. However, one thing I've been told is that you will never be fully "ready" to dive into research. Meaning that everything is so specialized at this point that even grad students only understand 90% of their specialization, 70% of their subfield, and 30% of everything else. Someone told me that because this will always be the case, it is better that I dive in right away. (But of course it is hard to know what to dive into!)


texts: Is just one W-type enough for formalizing mathematics?

texts:
We work in intensional Martin-Löf type theory with $0$, $1$, $2$, $\Pi$, $\Sigma$, $W$ and a cumulative hierarchy of universes. Suppose our goal is to formalize constructive mathematics.
Now if we were to drop general $W$-types but keep just one $W$-type with infinitely many closed terms how much more difficult would our life become? Would it be much harder to express interesting theorems?


texts: Hardness of quantum circuit equivalence?

texts:
Given two poly-sized quantum circuits $C_1$ and $C_2$ on $n$ qubits with a universal gate set generated by some finite set of one and two qubit gates. I'm thinking of the gates $\langle H, T, CNOT\rangle$, but other universal gate sets should work as well. Notice that $C_1$ and $C_2$ each correspond to a $2^n \times 2^n$ unitary matrix, $U_1$ and $U_2$, respectively. How hard is it to determine if $U_1 == U_2$, given the circuits $C_1$ and $C_2$?

Clearly the problem is in coQMA since if $U_1$ and $U_2$ are different there exists an input state $r$ such that $C_1(r)$ not equal to $C_2(r)$ which can be checked with a quantum computer. Has this problem been studied? Is it complete for this class? Is this class known as something else in the literature, since I cannot find much about it?


texts:
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.

  Is there a graph construction in polynomial time to get a bipartite graph from  $G_1$ and $G_2$ with perfect matching count $P_1+P_2$ without knowing $P_1$ but knowing $P_2$?


texts: Is Isomorphism of bounded degree hyper-graphs in P?

texts:
Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices.

A hyper graph G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain subsets of the vertex set of $V$. An example of hyper-graph is given below and for example edge $e_3$ is a subset contain $v_3,v_5,v_6$ and similarly for other edges.

Isomorphism :
Two hyper graphs $G(V,E)$ and $H(V,E')$ are isomorphic if there is a permutation $g$ on $V$ such that,  $\forall $ $e \in E$, $$e\in E \iff g(e) \in E'$$

Reference: https://en.wikipedia.org/wiki/Hypergraph

Let me define the degree of a vertex in a hyper-graph:

$$D_v = |\{e_i \mid v\in e_i, e_i \in E\} |$$

Question : Is Isomorphism of bounded degree hyper-graphs in P ?


texts: How to define the formal and informal semantics of an algorithm as accurately as possible?

texts:
I am currently researching ways to define the semantics of programs for some ideas I have for a new programming language. Most ways to define semantics involve mapping the programming language syntax representation of a program to some semantic specification. I dislike this approach, because the syntax restricts what semantics you are able to express and it often results in the under and over specification of the semantics.

Instead of thinking of a programming language in terms of syntax constructs and their corresponding semantics, I want to focus on semantics first, syntax, although important to be able to best read and write programs and ultimately necessary to formulate the semantics, is of lesser importance. But in order to do so, I need a language that is capable of defining the semantics as accurately as possible. This semantic language should not be a programming language by itself, because its main purpose is defining semantics accurately, not computations. So I think most formal semantic specifications do not comply to these requirements, because they focus on extracting semantics out of existing programs instead of defining them as accurately as possible in the first place. Therefore I would like to ask the following question:

  "Are there any languages or methods that focus mainly on expressing formal and
  informal semantics of an algorithm as accurately as possible?"

During my research I was reading "Formal Syntax and Semantics of Programming Languages" by Kenneth Slonneger which include some chapters about the different ways to define the semantics for a programming language. In chapter 11 (Axiomatic Semantics), page 397, he states that "Extensive literature has dealt with the difficult problem of accurate specifications of algorithms.". But I have a difficult time finding literature that is specific about "accurate specifications of algorithms". Therefore my second question is as follows:

  "Do you know about any literature that specificly talks about how to
  define accurate specifications of algorithms?"

Edit: To make more clear what I mean by "expressing semantics of an algorithm as accurately as possible" I will give an example. If with axiomatic semantics the following pre and post conditions were given:

pre  = m >= 0 and n >= 0
post = minimum <= m and minimum <= n and minimum >= 0

Then the following function would comply:

minimum m n = 0

But this does not capture the intent the person writing the specification had.

  "Do you know of methods that could capture this intent more accurately?"


texts: Truly random number generator: Turing computable?

texts:
I am seeking a definitive answer to whether or not generation of "truly random" numbers
is Turing computable.  I don't know how to phrase this precisely.
This StackExchange question on "efficient algorithms for random number generation"
comes close to answering my question.
Charles Stewart says in his answer, "it [Martin-Löf randomness] cannot be generated by a machine." Ross Snider says, "any deterministic process (such as Turing/Register Machines) can not produce 'philosophical' or 'true' random numbers." Is there a clear and accepted notion of what constitutes a truly random number generator?
And if so, is it known that it cannot be computed by a Turing Machine?

Perhaps pointing me to the relevant literature would suffice.  Thanks for any help you can provide!

Edit. Thanks to Ian and Aaron for the knowledgeable answers!  I am relatively unschooled in this area, and I am grateful for the assistance. If I may extend the question a bit in this addendum: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?


texts: what is the meaning of "indicate substitution by priming metavariables"

texts:
This is a question about the usage of "indicate substitution by priming metavariables".
For example, in the separation logic(it is not important whether familiar to this logic), I can understand the allocation rule, i.e., from a state that the memory is empty, and execute the command $v:=cons(\overline{e})$, then the result is the momery is allocated. the rule is as following
$$\overline{\{emp\} ~~v:=con(\overline{e})~~\{v\mapsto \overline{e}\}}$$
where $v$ is not free in $\overline{e}$, abbreviate $e_1, ...,e_n$ by $\overline{e}$

Explanation:precondition $emp$,as a assertion, denotes the empty memory.
$v:=cons(\overline{e})$ denote allocate the a new block of memory consisting of $n$ cells, the $i$th cell has the content $e_i$ and give the block address to the variable $v$, then the postcondition is that the memory is  the block which is referenced by $v$.

The following is where "indicate substitution by priming metavariables" happens.

In the above rule, we indicate substitution by priming metavariables denoting expressions and assertions, e.g., we write $e_i'$ for $e_i/v\to v'$. we also abbreviate $e_1, ...,e_n$ by $\overline{e}$ and $e_1',...,e_n'$ by $\overline{e}'$

the above allocation rule turns to be
$$\overline{\{v=v'\land emp\} ~~v:=con(\overline{e}) ~~\{v\mapsto \overline{e}'\}}$$

My question is what's the meaning of "write $e_i'$ for $e_i/v\to v'$"?,

and what the meaning of $v=v'$, $v\mapsto \overline{e}'$  in above rule?


texts:
Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.

Let $G=(V,E)$ be a simple connected graph. Each edge is of length 1. In addition, we assign directions to edges. Note that the graph is undirected, as we can traverse each edge in either direction. The assigned direction only determines the weight of each edge (either +1 or -1) depending on the direction of the traverse.

For each pair $v,u \in V$ of vertices, we define anti-distance $d(u,v)=-d(v,u)$, as the weighted average length of all the paths from $u$ to $v$. Note that the weights are dependent on the path and can be negative. The goal is to find $d(u,v)$ for all the pairs.

The algorithm I currently use is to generate many random spanning trees of $G$ (say, using the Aldous-Broder Algorithm), find $d(u,v)$ for each spanning tree (which is unambiguous and easy to find), and then average them all.

For our signal processing application, the input graphs have few hundreds nodes and it takes $\approx 10^5$ spanning trees to get  reasonable values. It is practical, but not pretty! The question is whether there is a better way to do this that does not need what is essentially amount to a Monte-Carlo simulation.


texts:
Suppose I have a binary tree $G = (V, E)$ (with undirected edges) that is partitioned into sets of k vertices, where each set of vertices is a connected subgraph of $G$. Additionally, if there are sets that have less than k vertices, then at least one of these vertices must be a leaf.

Now suppose I wanted to increase the size of each set to be $k+1$ and hold all the above properties. I'm not entirely sure what tools I would use to construct such an algorithm. Any ideas or resources you can link me to?


texts: reference request: greedy algorithm for fractional interval covering

texts:
Reference Request
I've found a natural greedy algorithm for the problem below.  My question is: what is already known about fast algorithms for this problem (faster than general linear programming, especially greedy algorithms)?  An ideal answer would include citations to relevant publications (articles or texts).  Thanks.

Problem: Fractional Interval Covering
input: A positive integer $n$, and, for every pair of integers $(i, j)$ in $I=\{(i,j) : 1\le i \le j \le n\}$, a capacity $c_{ij} \in [0,1]$.
output: A minimum-size fractional interval covering $x$. That is, a solution to the following linear program:
$~~~~~$ minimize $\sum_{(i,j)\in I} x_{ij}$ subject to
$~~~~~$$\sum_{(i,j)\in I, t\in[i,j]} x_{ij} \ge 1$ for all $t\in\{1,2,\ldots,n\}$,
$~~~~~$and $x_{ij}\in [0, c_{ij}]$ for all $(i,j)\in I$.

Greedy algorithm. Briefly, the algorithm I've found starts with $x=\mathbf 0$, then repeatedly chooses some $t$ with unmet demand (subject to some restrictions on $t$), and increases $x_{ij}$ by some amount, for some $(i,j)\in I$ maximizing $j$ subject to $t\in [i,j]$ and $x_{ij} < c_{ij}$.
For the special case of $c_{ij}\in \{0,1\}$, giving a greedy algorithm for the problem is a common introductory algorithms exercise.  It can be solved by choosing an interval containing 1 with latest end-time $j$, then recursing on $[j+1,n]$.  The algorithm I have in mind is a generalization of this.
EDIT: To clarify, I am interested in algorithms that compute an exact optimum.  The algorithm I have in mind is a greedy algorithm that can be implemented in linear time.  The dual LP is
$~~~~$ maximize  $\sum_{t=1}^n \alpha_t - \sum_{ij} c_{ij}\beta_{ij}$ subject to
$~~~~~\alpha_t, \beta_{ij} \ge 0~~~(t, i, j)$
$~~~~~\sum_{t\in[i,j]} \alpha_t \le 1 + \beta_{ij}~~~((i,j)\in I)$
It always has an optimal solution with each $\alpha_t\in\{0,1\}$ and integer $\beta_{ij}$.  Thus, the dual problem is equivalent to the following:

input: As described above.
output: A subset $T\subseteq \{1,2,\ldots,n\}$ maximizing $|T|$ minus, for every integer interval $[i,j]\subseteq [1,n]$ such that $|[i,j]\cap T|$ is greater than 1, a penalty of $c_{ij}\times |[i,j]\cap T|$.


texts: Minimum Spanning tree on a complete "random" graph

texts:
Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)$ is an exponential distribution.

Problem

What is the distribution of weight of the minimum spanning tree of the above graph?

Note : If $ X_1 \sim exp(\lambda_1)$ and $X_2 \sim exp(\lambda_2)$, then $min(X_1, X_2) \sim exp(\lambda_1+\lambda_2)$


texts:
It is known that if $P=NP$ then $CoNP= PCP[O(log(n)),O(1)]$. Also, it is known that $NEXP=PCP[poly(n),poly(n)]$. It appears that PCP can't tell us which natural problems are not in $NP$. I wonder if it is possible to use PCP characterization to separate $CoNP$ from $NP$.

  What are the best bounds on randomness complexity $r(n)$ and query complexity $q(n)$ such that Tautology Problem is in $PCP[O(r(n)),O(q(n))]$?


texts: It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP certificates of GI. Any conjectures that imply $GI \in coNP$ ? What are some implications of $GI \in coNP$ ?


texts: Good reference about approximate methods for solving logic problems

texts:
It is known that many logic problems (e.g. satisfiability problems of several modal logics) are not decidable. There are also many undecidable problems in algorithm theory, e.g. in combinatorial optimization. But in practice heuristcs and approximate algorithms works well for practical algorithms.

So one can expect that approximate algorithms for logic problems can be suitable as well. However the only reseach trend along these lines I have managed to find is the max-SAT problem and its development was active in nineties.

Are there some other active research trends, workshops, keywords, good references for the use and development of approximate methods for modal logics, logic programming and so on?

If automated reasoning is expected to gain prominence in the future applications of computer science then one will have to be able to go beyond undecidability constraints of logics and approximate methods or heuristics can be natural path to follow, isn't it so?


texts: Since it does not allow nonterminating computation, Coq is necessarily not Turing-complete. What is the class of functions that Coq can compute? (is there an interesting characterization thereof?)


texts: How to develop an effective notation for a partially ordered logic?

texts:
I am developing a logic for reasoning about programs in a resource-constrained environment. My starting point is intuitionistic linear logic, but I made the following changes:

In intuitionistic linear logic, environments are sets of available resources. In my logic, environments are partially ordered sets: some resources have to be consumed before others.

Multiplicative conjunction splits into two connectives: parallel conjunction and sequential conjunction.
Linear implication can only consume a resource X, if there is no other resource Y that must be consumed before X.

Logical connectives are usually defined in terms of introduction and elimination rules. In my logic, I need a new kind of rule: usage rules, which describe how a resource can be used in a computation without destroying it.

I add a new unary operator, called borrowed pointer, which denotes a non-owning reference to an existing resource.
Creating a borrowed pointer uses but does not consume the resource being pointed. In particular, one may always create a borrowed pointer to an existing resource X, even if there is some resource Y that must be consumed before X.
No resource may be consumed until all borrowed pointers to it have been consumed. This is my main motivation for introducing the notion of sequential conjunction in the first place.

I want to give a formal presentation of the rules of inference of this logic using natural deduction and sequent calculus. However, I am having trouble coming up with a good notation that succinctly conveys ideas like:

The environment $\Gamma$ can be split into sub-environments $\Delta, \Sigma$, where there is no resource in $\Sigma$ that must be consumed before any resource in $\Delta$.
Given the environment $\Gamma$ and a resource $A \in \Gamma$, the result of adding a resource ${\rm ref} A$ to $\Gamma$, in such a way that ${\rm ref} A$ must be consumed before $A$.
The sequential conjunction of $A$ and $B$.
etc.

What guidelines should I follow in order to design a good notation for this logic?


texts:
Compaction is a particularly weak form of sorting. The problem can be phrased as follows:

Given an array $A$ of $N$ cells, with at most $R$ of the cells distinguished (say by a bit), produce an array $D$ of at most size $O(R)$ containing all of the marked cells

Compaction is said to be:

Tight: If the output array $D$ is of size exactly $R$
Order-preserving: If the relative ordering of marked elements of $A$ is the same as the relative ordering of elements of $D$ (i.e. if the compaction is "stable" in the sense of sorting)
Data-oblivious: If the algorithm which computes the compaction has access patterns independent of the data

One can construct tight, order-preserving, data-oblivious compaction from a sorting network. You have to use non-standard comparison function which:

Sets all marked elements as greater than unmarked elements
Within comparisons between marked elements (resp. unmarked elements), breaks ties by the element's initial ordering in the array.

But such a function is easy to specify, and can be computed in $O(\log N)$ time.
This means that one can construct tight, order-preserving, data-oblivious compaction from the AKS sorting network (giving an $O(N(\log N)^2)$ algorithm) or from a more practical sorting network like Batcher Odd-Even Mergesort (giving an $O(N(\log N)^3)$ algorithm).
Anyone who has worked for sorting networks before has heard that there are the asymptotically optimal algorithms (namely the AKS sorting network and ZigZag Sort, both using $O(N\log N)$ comparisons), and the practically efficient algorithms (Batcher's mentioned above is one example, but there are many which are $O(N(\log N)^2)$ comparisons).
I'm essentially curious if there is something similar for compaction --- I have seen papers such as this which give oblivious tight compaction in $O(N)$ time <1>.
This paper's improvement is lowering the implied constant from $2^{228}$ to ~$9000$. I imagine that for al "reasonably-sized arrays" it is still more efficient to pair Batcher's sorting network with the aforementioned non-standard comparison function.
So has been research done into practically-efficient compaction algorithms? While I eventually want something which is tight, order-preserving, and data-oblivious, the most important keyword by far is "data-oblivious". I'm willing to tolerate a negligible (meaning $N^{-\omega(1)}$) probability of failure, as long as it has "good constants".
Moreover the data to be compacted is "random" in a strong sense. In particular, each element of the array is marked/not marked according to the result of an i.i.d. $\mathsf{Bern}(1/2)$.
<1> The linked algorithm has a negligible probability of failure, which is fine for my purposes.


texts: What kind of mathematical background is needed for graph theory?

texts:
It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years?
Which subjects should be reviewed and is there any book that covers all of them?


texts: Which are the rewriting systems corresponding to the levels of the computatational hierarchy?

texts: The lambda calculus is a rewriting system and Turing complete. Which are the rewriting systems corresponding to the other levels of the Chomsky hierarchy? E.g. what is the functionally computing system for finite state machines and so on?


texts: Efficient and simple randomized algorithms where determinism is difficult

texts:
I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most prominently

Randomized Quicksort (and related geometric algorithms, e.g. for convex hulls)
Randomized Mincut
Polynomial Identity Testing
Klee's Measure problem

Among these, only polynomial identity testing seems to be really hard without the use of randomness.

Do you know more examples of problems where a randomized solution is very elegant or very efficient, but deterministic solutions are not? Ideally, the problems should be easy to motivate for laymen (unlike e.g. polynomial identity testing).


texts: Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint

texts:
Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$.

I am wondering if there are some references discussing approximation algorithms regarding this problem.

The reference I can find now discussed a similar problem: minimize a non-decreasing submodular function under (lower bound) cardinality constraint (i.e., $|S| \leq k$). But it is not obvious to me how to adapt the result to the previous problem.

Edit: the exact form of $f$ is known.


texts: Is there a natural restriction of VO logic which captures P or NP?

texts:
The paper

Lauri Hella and José María Turull-Torres,
Computing queries with higher-order logics,
TCS 355 197–214,
2006.
doi: 10.1016/j.tcs.2006.01.009

proposes logic VO, variable-order logic.  This allows quantification over orders over the variables.  VO is quite powerful and can express some non-computable queries.  (As pointed out by Arthur Milchior below, it actually captures the whole of the analytical hierarchy.)  The authors show that the fragment of VO obtained by allowing only bounded universal quantification over the order variables exactly expresses all c.e. queries.  VO allows the order variables to range over the natural numbers, so bounding the order variables is clearly a natural condition to impose.

  Is there a (nice) fragment of VO that captures P or NP?

As an analogy, in classical first-order logic allowing quantification over sets of objects gives a more powerful logic called second-order logic or SO.  SO captures the whole of the polynomial hierarchy; this is usually written as PH = SO.  There are restricted forms of SO capturing important complexity classes: NP = $\exists$SO, P = SO-Horn, and NL = SO-Krom.  These are obtained by imposing restrictions on the syntax of allowed formulas.

So there are straightforward ways to restrict SO to obtain interesting classes.  I would like to know if there are similar straightforward restrictions of VO that are roughly the right level of expressivity for P or NP.  If such restrictions are not known I would be interested in suggestions for likely candidates, or in some arguments why such restrictions are unlikely to exist.

I have checked the (few) papers that cite this one, and checked the obvious phrases on Google and Scholar, but found nothing obviously relevant.  Most of the papers dealing with logics more powerful than first-order don't seem to deal with restrictions to bring down the power into the realm of "reasonable" computations, but seem content to dwell in the c.e. universe of arithmetic and analytic classes.  I'd be happy with a pointer or a non-obvious phrase to search on; this might be well known to someone working in higher-order logics.


texts: For a language to be programmable, is it mandatory that it be based on a context free grammar

texts:
Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar?

ex: Are all programming/scripting languages context free grammars? Java is based on CFGs, but is it actually the case that all programming languages are based on CFGs?

It does not seem mandatory, but there are gaps in my understanding.

Some context for the question: I was looking at Java language specification, which also provides the grammar rules. This made me think about this question.


texts: Conductance and diameter in regular graphs

texts:
Given an undirected, regular graph $G=(V,E)$, what is the relationship between its diameter - defined as the largest distance between two nodes - and its conductance, defined as $$\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},$$ where $e(S,S^c)$ is the number of edges crossing between $S$ and $S^c$.

More concretely suppose I know the diameter is at least (or at most) $D$. What does this tell me about the conductance, if anything? And, conversely, suppose I know the conductance is at most (or at least) $\alpha$. What does this tell me about the diameter, if anything?


texts: Open problems related to Graph isomorphism

texts:
Presently I am doing literature survey on Graph isomorphism (GI) problem.

I would like to know some open questions related to the following

What are the graph parameters for which fixed parameter tractability of GI is an open problem.
What are the graph parameters, by fixing them polynomial time solvability of GI is not known.
Complexity of GI when restricted to many graph classes is equivalent to general GI (GI-Completeness). What are the graph classes for which GI-completeness is not known.

Thank you.


texts: Approaches for Theoretical Analysis of Estimates of Probability Distributions

texts:
Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers that theoretically analyze and bound the estimate?

As a more concrete example, consider this paper which designs a streaming algorithm to estimate the degree distribution of a graph and defines a new notion of closeness called Relative-Hausdorff Distance (RHD). The paper experimentally validates their estimate to be close (according to RHD) to the actual distribution for several real-world graphs. I want to know if there are methods/references in literature that one can use to give provable (theoretical) guarantees of their closeness.


texts:
I'm currently thinking about the following problem:

Given two strings $S,T$ over an alphabet $\Sigma$, return back a list $L$ of common substrings described by their length and positions within them.

I am interested only in maximal substrings as to not have redundancy. Meaning that for a substring of length $l$ with starting positions $i$ in $S$ and $j$ in $T$,  $S_{i–1} \neq T_{j–1}$ and $S_{i+l} \neq T_{j+l}$.

I am looking for a practical $O(|S|+|T|)$ solution. I wanted a bottom-up approach using hashing (a rolling hash?) that will build up the substrings as it runs. The Reputer algorithm advised to me in my previous post which is now linked gives a solution using suffix trees. I was wondering if any similar approaches have been made using hashing and if any papers exist describing them.


texts: What is the largest noise rate $\eta(n)$ for which learning parities with noise is easy?

texts:
Learning Parity with Noise (LPN) is usually stated with constant noise rate $\eta < 1/2$ on the labels, and it is believed to be hard to learn because of the high statistical dimension of the problem (they are not SQ-learnable even if the parity is assumed to be sparse).

I'm interested in a noise rate which decays with $n$, the number of features, and I want to know where the known easiness threshold is for this problem.

Specific notes:

LPN is easy with noise rate $\eta = O(1/n)$, because drawing $O(n)$ samples will with good probability produce $O(1)$ noisy examples.
It seems like it should still be hard for $\eta = O(1/\log n)$ and even $O(1/\sqrt{n})$.
Is it known to be easy for any $\eta = \omega(1/n)$?
LPN is equivalent to decoding random linear codes, but I have not heard of any work with sublinear noise rates for coding theory.


texts: Finite One-Way Permutation with Infinite Domain

texts:
Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s functionality. (As in Kolmogorov complexity.) See explanations below.

For instance, the NOT function is one such permutation:

function NOT(x)
    Let y = x
    For i=1 to |x|
        Flip the ith bit of y
    return y

$\pi_k(\cdot)$, defined below, is another case:

function pi_k(x)
    return x + k (mod 2^|x|)

My question is about a special class of permutations, called one-way permutations. Informally speaking, these are permutations which are easy to compute, but hard to invert (for a $\rm{BPP}$ machine). The mere existence of one-way permutations is a long-standing open problem in cryptography and complexity theory, yet in the remainder,  we will assume that they exist.

As an example of a conjectured one-way permutation, one can consider the RSA: Let $n = pq$ be a Blum integer, and let $e = 65537$.
The one-way permutation is defined by:
$\pi_n(x) = x^e \bmod n$.

Note that RSA is defined over the finite domain $\mathbb{Z}_n$. In fact, to obtain an infinite domain permutation, one has to consider a family of RSA permutations
$\{\pi_n\}_{n\in D}$, where $D$ is an infinite set of Blum integers. Note that $D$ is the description of the family, and by definition, it is infinite.

My question is (assuming the existence of one-way permutations):

  Does there exist finite-description one-way permutations over an infinite domain?

The answer may vary: It can be positive, negative, or open (either likely to be positive, or likely to be negative).

Background

The question arose when I was reading an ASIACRYPT 2009 paper. There, the author implicitly (and in the context of some proof) assumed that such one-way permutations exist.

I'll be happy if this is indeed the case, though I couldn't find a proof.


texts: Decidability/algorithm for checking universality of a quantum gate set

texts: Given a finite set of quantum gates $\mathcal{G} = \{G_1, \dots, G_n\}$, is it decidable (in computation theoretic sense) whether $\mathcal{G}$ is a universal gate set? On one hand, "almost all" gate sets are universal, on the other, non-universal gate sets are still not well understood (in particular, of course, it is not known whether every non-universal gate set is classically simulatable), so I imagine giving an explicit algorithm for checking universality could be nontrivial.


texts: Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals

texts: Looking for some lecture videos (introductory level) on  logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals


texts: Is it possible to encrypt quantum states under reasonable assumptions?

texts:
Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can recover the original state?

Assume (classical) one-way functions that are hard for quantum attackers to break exist (as is believed to be the case).


texts: Does L have a definition in terms of circuits?

texts:
Many complexity classes defined with Turing machines have definitions in terms of uniform circuits. For example, P can also be defined using uniform polynomial size circuits, and similarly BPP, NP, BQP, etc. can be defined with uniform circuits.

  So is there a circuit-based definition of L?

An obvious idea would be to allow polynomial size circuits with some depth limitation, but this turn out to define the NC hierarchy.

I was thinking about this question a long time ago, but didn't find an answer. If I remember correctly, my motivation was to understand what the quantum analog of L would look like.


texts: Easy interactive proofs for easy problems?

texts:
Motivation

Consider some $L \subseteq \{0,1\}^*$. Suppose Alice gives Bob a machine or oracle $M$ that purportedly decides $L$. If Bob has only polynomial time in their disposal, then they cannot directly test $M$ unless they already know a polynomial time algorithm for $L$. However, if $L \in \textsf{PSPACE}$ then Alice might be able to convince Bob via an interactive proof protocol. That is, Bob can generate random instances of the problem of size $n$, run $M$ and have Alice demonstrate the correctness of the answer. If they repeat the procedure sufficiently many times then Bob knows that, with high probability, $M$ gives the correct answer on most instances of size $n$, so it is at least "average-case" valid.

Now, if Alice is also limited to polynomial-time, then in general they won't be able to supply an interactive proof. Indeed, if it is possible for both the verifier and the prover to be polynomial-time, it follows that $L \in \textsf{BPP}$.

The motivation for the question is: what happens if $L$ is in $\textsf{BPP}$, but Bob doesn't know the algorithm for solving it? In this case, it is possible that Bob knows an interactive proof protocol for some class that is known to contain $L$ and Alice is able to fill in the role of prover. For example, if Alice tells Bob a polynomial-time algorithm for solving graph isomorphism then Bob can easily convince themselves of its validity (for given input size) because there is an interactive proof protocol where the prover can run in polynomial-time given oracle access to the problem. However, this example requires using a protocol specifically tailored to graph isomorphism, whereas I would like a protocol that can work for any problem in a large class (optimally all of $\textsf{PSPACE}$).

I am interested in all results that are relevant to the above discussion, but to make the question concrete, I will suggest a specific hypothesis.

Question

Given a polynomial-time computable mapping $f: \{0,1\}^* \rightarrow \{0,1\}^*$, we can consider the language $f^{-1}(\textsf{TQBF}) \in \textsf{PSPACE}$.

We say that such an $f$ is easy when there is a polynomial-time algorithm that implements an optimal strategy for the corresponding game. That is, given $x \in \{0,1\}^*$, $k \in \mathbb{N}$ and any assignment of the variables corresponding to the $k$ outermost quantifiers in the formula represented by $f(x)$, our algorithm can decide whether the resulting formula (with quantifiers over unassigned variables) is true. In particular, in this case $f^{-1}(\textsf{TQBF}) \in \textsf{P}$.

  Is there an interactive proof protocol for $\textsf{TQBF}$ s.t. for any easy $f$, there is some polynomial-time algorithm that, given input $x$, plays the role of the prover in the protocol for $f(x)$?

To understand the motivation for the easiness condition, note that if $f$ is s.t. the formulas it produces only have existential quantifiers (which implies $f^{-1}(\textsf{TQBF}) \in \textsf{NP}$) then the condition requires that not only $f^{-1}(\textsf{TQBF}) \in \textsf{P}$ but that the $\textsf{NP}$-witnesses can be produced in polynomial time (in fact it is even stronger: we should be able to complete any prefix to an $\textsf{NP}$-witness whenever possible).


texts: What is the *generally accepted* definition for the percolation threshold on finite-sized graphs?

texts:
For "regular" graphs (lattices, if you will), it's easy to define the percolation threshold $p_c$ as the critical probability beyond which the infinite graph will contain an infinitely large cluster with probability 1. (And below that, with probability 0).

In practice, you can measure that by doing a finite-size analysis and extrapolating.

But what if I'm interested in just the percolation properties of a single instance of a given finite graph?

In that case, I can personally think of a few ways to define a percolation threshold, but it wouldn't be unique. For example, you could say: "For a graph $G$ let $p_c$ be the probability such that the largest cluster will have size $n|G|$ with probability $p > 0.99$ or something like that.

But I wonder if there's one common definition that everyone in the research community uses?

I find it hard to nail down my literature search, probably because I'm using the wrong terms. All papers I could dig up so far talk about finite-size-scaling analysis but with the goal at arriving at $p_c$ for the infinite graph. Pointers in the right direction would be appreciated.


texts:
Is there any efficient algorithm for computing all semigroups of order n?

I found the following paper which solves a bit different problem.

Veronique Froidure and Jean-Eric Pin, "Algorithms for computing finite semigroups"


texts: OR-circuit complexity of a dense linear operator

texts:
Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?

More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee_{j=1}^{n}(A_{ij} \land x_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).

Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. Yao's algorithm for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)

In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)


texts: What is the significance of nominal techniques?

texts:
What is the significance of nominal techniques, as far as their application to the formal theory of bound variables is concerned?

I have been reading M. J. Gabbay's expository work on the topic that appeared in Bulletin of Symbolic Logic.  I understand that, the main contribution of nominal techniques to the nasty problem of $\alpha$-conversion is that they introduced new principles of induction and recursion, and a new quantifier.  However, I am not sure if the use of orbits instead of $\alpha$-equivalence classes is strictly necessary for these purposes - because orbits and equivalence classes are essentially the same thing.

I understand the theory of nominal sets are very fruitful in that it can be applied in many different areas - including infinite automata theory and domain theory, due mainly to its general nature.  I would like to know the relevance of the theory's generality - replacing $\alpha$-equivalence classes with orbits - in the very first problem that it is meant to solve, that is, $\alpha$-equivalence of syntactic objects.

EDIT: I knew how nominal techniques  could be applied to reasoning up to $\alpha$-equivalence;  my question was more about the theory's internal methodology, that is, the focus on the group action.

Here's an attempt to answer my question: automorphisms on the set-theoretic universe induced by permutations of atoms are crucial in proving the new recursion/induction principles, so is the reinterpretation of $\alpha$-equivalence as orbits.  However, this reinterpretation might or might not be relevant to the users of the recursion/induction principles.

Let me know if there is something in my answer to be added or corrected.

EDIT 2: My question might have been better phrased as:  do we really need to appeal to axiomatic set theory - something very powerful - to get a proper treatment of alpha-equivalence?


texts: What would you advise someone who wants to do research as a hobby?

texts:
I love doing TCS in my spare time. Lately I have been trying to do some research as a hobby.
I'm looking for some extra input from people who do this full-time:

Do you think it is possible to do this "just for fun"? I have no intention to ever get a PhD.
What resources would you recommend?


texts: When does a graph admit an orientation in which there is at most one s-t walk?

texts:
Consider the following problem:

Input: a simple (undirected) graph $G=(V,E)$.
Question: Is there an orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (directed) $s$-$t$ walk?

This can be equivalently phrased as:

Input: a simple (undirected) graph $G=(V,E)$.
Question: Is there an acyclic orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (directed) $s$-$t$ path?

What is the class of graphs for which the answer is "yes"? Can this problem be solved in polynomial time?

Some observations:

If the graph is bipartite, then the answer is "yes."
If the graph has a triangle, then the answer is "no."

The first observation follows by orienting the edges from one partition to the other. The second observation is easy to check. This led me to two incorrect guesses:

The answer is "yes" if and only if the graph is bipartite. (counterexample: the 5-cycle)
The answer is "yes" if and only if the graph is triangle-free (counterexample: the cartesian product of an edge with the 5-cycle)


texts: Can we replace deterministic part of alternative turing machine with some other equivalent machines?

texts:
I'm sorry if it is a low level question but I am so confusing.

If $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$ then $DTime(n) \subseteq \Sigma_2DTime(n^{0.2})$

Is this true that $\Sigma_2DTime(n^{0.2})\subseteq\Sigma_2\Sigma_2Time((n^{0.2})^{0.2})=\Sigma_4Time(n^{0.04})$

I picked up DTime in alternative machine and replaced it with $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$  and replacing  n with $n^{0.2}$.


texts: The problem of whether or not every function computable in time $T(n)$ is computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously

texts:
If a function is computable in time $T(n)$, is it computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously?

We won't be able to prove it, because it implies the open problems $\text{P} \neq \text{PSPACE}$ and $\text{EXPTIME} \neq \text{EXPSPACE}$.

I think we won't be able to disprove it either. A counterexample in the polynomial-time regime would imply the open problem $\text{P} \neq \text{L}$.  In the exponential-time regime, $\text{EXPTIME} \neq \text{PSPACE}$. But maybe there is a counterexample somewhere else.

My question is simply: is this statement or a similar one equivalent to any well-known conjecture?  Any references would also be appreciated.


texts: Complexity of best folding of a 2D set (or how to optimize a sandwich)

texts:
Motivation:
I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered by both halves, I need to find the optimal place to cut the bread.
I was wondering what the complexity of that is.
Formal problem:
Let $S\subseteq \mathbb{R}^2$ be either a polytope, or more generally a semialgebraic set.
For a line $\ell\in \mathbb{R}^2$, given by its normal $w\in \mathbb{R}^2$, we define the cut of $S$ by $\ell$ to be the two sets:
$$S_1=\{x\in S\ :\ x^Tw\ge  0\}\qquad S_2=\{x\in S\ :\ x^Tw<  0\}$$
Now, given an affine linear isometry $f(x)=Ax+b$, we can consider the area of $\Delta(S_1,f(S_2))$. That is, the area of the symmetric difference between $S_1$ and the isometry applied to $S_2$.
The problem is now the following:

Given $S\subseteq \mathbb{R}^2$, find a line $\ell$ and an affine isometry $f$ such that  $\Delta(S_1,f(S_2))$ is minimal.

If it helps, we can assume $S$ is convex (although homemade bread often isn't).


texts:
Let $G$ be a directed weighted graph. In addition each edge $e$ has a time-stamp $t(e)$.
A route $\pi$ from $s$ to $t$ is a directed walk from $s$ to $t$ with increasing time-stamps.
We are also given two sets of vertices $S$ (source) and $T$ (destination).
We associate with each route $\pi$ one of the edges $e$ with the following properties:

$e$ belongs to $\pi$,

There is no route to $e$'s head from any other source $s' \in S$ with time-stamps smaller than $t(e)$,

$e$ has minimum weight among the edges satisfying the conditions in 1 and 2.

Let's the edge corresponding to a route its bottleneck.
Given $G$, $S$, and $T$,
we want to compute the list of bottlenecks for all routes in $G$ from $S$ to $T$,
i.e. we want a least of the form $(s,t,e)$ where
$s\in S$, $t\in T$, and $e$ is the bottleneck edge for some route from $s$ to $t$.
We don't need all possible bottlenecks for a route but just one of them,
and it is better if the set of bottlenecks we get is minimal.
Questions
I am looking for references on algorithms for this or similar problems.
Does this problem have a name?