texts: Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded

texts:
Let $G$ be a graph with $n$ vertices and $m$ edges, such that for every two vertices $u$ and $v$, the number of shortest paths from $u$ to $v$ is bounded by some polynomial $poly(n,m)$ in $n$ and $m$. A class of graphs which have this property are block graphs (https://en.wikipedia.org/wiki/Block_graph), for example.

Is there a name for this class of graphs? Is anything known about it?


texts:
The general aproach presented by Craig Gentry in 2009 to create a fully-homomorphic encryption system is roughly the follow:

Create a scheme that can evaluate some functions (increasing the noise in the ciphertext)
Change you decryption function to be one of these functions that can be evaluated
Use a function Recrypt to somehow decript and encrypt again the ciphertext to eliminate the noise introduced by the homomorphic operations.

The idea seems wonderfull, but, I don't understand well how and why this Recrypt function work...

For example, in the section 4.3 of the paper Computing Arbitrary Functions of Encrypted Data, he explains it like that:

Imagine that we have a list of public keys $p_1, p_2, .. $ and a private key $s_1$, then, we encrypt $m$ using $p_1$ generating $c_1$.

Then, we encrypt each bit of $s_1$ using $p_2$ generating a vector of ciphertexts $\overline{s_1}$.

Then, Recrypt  encrypts each bit of $c_1$ using $p_2$ generating the array $\overline{c_1}$ and evaluate the decryption citcuit $D$ in $\overline{c_1}$, $\overline{s_1}$ and $p_2$.

It seems like recrypt tries to decrypt the $\overline{c_1}$ with a wrong key (since it was encrypted with $p_2$, I was expecting something like $s_2$...).

Could someone here just try to explain how this Recrypt works? I don't know what I'm missing...

If my question is unclear, please, let me know.

Thanks.


texts: SAT in some DTIME always via a constructive proof?

texts:
Why can the statement $SAT \in DTIME(n^3)$ not be proven through a non-constructive proof? Intuitively a proof would be a turing machine, which solves this problem in $DTIME(n^3)$, but there are non-constructive proofs like the following:
https://cs.stackexchange.com/questions/367/how-can-it-be-decidable-whether-pi-has-some-sequence-of-digits


texts:
Regularly in a Hamming hypercube, the vertices are labelled so that edge difference equals path difference. That is greater the edge difference, greater the hamming distance of the labelled vertices will be.

Can we label the cube so that lower the edge difference, higher will the Hamming distance be? Not all pairs of words will satisfy this property (for instance try labeling the 2-cube). However, is there a lower bound on how many close vertices any vertex can have and still have the property? Any references for this would help. This does sound like anticodes. However I am unsure.


texts: Density of answers for NP complete problems?

texts:
There is a result which goes along the lines of:

  Definition: For every language $L$, define $L_n = \{ w \in L \mid \text{length}(w) = n \}$, i.e. the subset of $L$ of words whose length is $n$.

  Theorem: If $\mathbf{P} = \mathbf{NP}$, then for every $\mathbf{NP}$-complete language $L$ there exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every integer $n$ it is the case that $|L_n| \leq p(n)$.

The intuition of the theorem is that if $\mathbf{P} = \mathbf{NP}$, then $\mathbf{NP}$-complete languages have a polynomial density of solutions.

As we believe that $\mathbf{P} \neq \mathbf{NP}$, we should tend to believe the contrary, i.e. that $\mathbf{NP}$-complete problems do not have a polynomial density of solutions.

Example: For the case of 3-coloring, for large $n$ there are many 3-colorable graphs with $n$ nodes; in any case, the number of 3-colorable graphs is not bounded by a polynomial.

Does anyone recognise this result? What is the actual statement of the theorem? Any reference would be welcome!


texts: How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

texts:
I am trying to motivate, define, and implement $K$-atomic snapshot object. To this aim, I first give some basic definitions on atomic snapshot object and $K$-atomic object. Then, I will give my understanding of $K$-atomic snapshot object and present my problems.

Atomic Snapshot Object:

In the paper "Atomic Snapshots of Shared Memory", the authors consider atomic snapshot objects —— shared objects partitioned into segments. For the single-writer atomic snapshot object, each segment belongs to a different processor and is written separately, but all segments can be read at once by any processor.

  The sequence specification of an atomic snapshot object provides two kinds of operations for each user $i, 0 \le i \le n-1$:

  A $scan_i$ invocation whose response is $return_i(V)$, where $V$ is an $n$-element vector called a view with a value for each segment, and
  An $update_i(d)$ invocation whose response is $ack_i$, where $d$ is the data to be written to $p_i's$ segment.

  A sequence of $scan$ and $update$ operations satisfies the atomic snapshot semantics means that, for each $V$ returned by a $scan$ operation, $V[i]$ equals the value written by the latest preceding $update_i$ operation, for all $i$.

$K$-Atomic Object:

In the paper On the Availability of Non-strict Quorum Systems, $K$-atomic object is introduced. Different from the classical atomic object (see Sharing Memory Robustly in Message-Passing Systems), in a system with $K$-atomic semantics,

  there exists an order of the operations that is consistent with real time order and such that the values returned by a read operation is equal to one of the values written by the last $K$ preceding writes in the order.

Problem 1: How to Define $K$-Atomic Snapshot Object?

$K$-atomic object is a relaxation (or a generalization) of classical atomic object, which is actually $1$-atomic object.

So based on the two concepts of $K$-atomic object and atomic snapshot object, can we define, in a reasonable manner, the $K$-atomic snapshot object?

One possible trial is to relax the timeliness of the snapshot:

  A sequence of $scan$ and $update$ operations satisfies the $K$-atomic snapshot semantics means that, for each $V$ returned by a $scan$ operation,

  $V[i]$ equals one of the values written by the last $K$ preceding $update_{i}$s, for all $i$, and
  there exists some time before the $scan$ operation at which $V[i]$ equals the value written by its latest preceding $update_{i}$, for all $i$.

Problem 2: Do you know or can you figure out some other reasonable definitions of $K$-atomic snapshot object?

Any comments, any suggestions, and any related literature references are welcomed.
Also, I appreciate the idea of implementation of the $K$-atomic snapshot object defined above myself (if you think it is OK).


texts:
Say you have a set of numbers {1,2,3,4,5,6,7,8,9,10} of which you have all different permutations.

You place each permutation into a BST and then compare all the shapes of the BSTs.  How many different (unique) shapes are there for trees of height 6 for example?

The question does not need to be answered directly, instead maybe an algorithm to help determine the shape instead and compare.


texts: Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm

texts:
In the quantum adiabatic algorithm, one prepares the ground state of a Hamiltonian $H_{i}$, and then evolves the Hamiltonian slowly over time to a target Hamiltonian $H_{f}$ via the interpolation $H(s)=(1-s)H_{i}+sH_{f}$.

Let $\Delta(s)$ denote the gap between the two smallest eigenvalues of $H(s)$. The Adiabatic Theorem states that if $s$ changes at a rate proportional to $\frac{1}{\Delta(s)^2}$, then the system will remain in the ground state of $H(s)$ at all times with high probability. Thus proving a lower bound on $\Delta(s)$ implies an upper bound on the runtime of the adiabatic algorithm.

My question is:

  What proof techniques are know to place lower bounds on the size of the spectral gap $\Delta(s)$?

I'm aware of two results in this area:

In some cases the gap can be found analytically, as is the case for adiabatic Grover search. Reference: http://arxiv.org/abs/quant-ph/0206003
In some cases the gap can be be bounded using results from the mixing times of Markov chains, as is the case when preparing the Kitaev clock state for a poly-size quantum circuit. Reference: http://arxiv.org/abs/quant-ph/0405098

I'd appreciate pointers to any other results in this area.


texts:
In this question, I am trying to understand the equivalence between the following two definitions of the complexity class QMA.

In Quantum Computational Complexity, John Watrous defines the class QMA as follows.

  Let $A = (A_{yes}, A_{no})$ be a promise problem, let $p$ be a
  polynomial-bounded function, and let $a, b: \mathbb{N} \to [0, 1]$ be
  functions. Then $A \in \text{QMA}_p (a, b)$ if and only if there
  exists a polynomial-time generated family of circuits $Q = \left\{Q_n
 : n \in \mathbb{N}\right\}$, where each circuit $Q_n$ takes $n + p
 (n)$ input qubits and produces one output qubit, with the following
  properties:

  Completeness. For all $x \in A_{yes}$, there exists a $p (|x|)$-qubit quantum state $\rho$ such that $Pr[Q \text{ accepts } (x,
 \rho)] \ge a (|x|)$.
  Soundness. For all $x \in A_{no}$ and all $p(|x|)$-qubit quantum states $\rho$ it holds that $Pr[Q \text{ accepts } (x, \rho)] \le
 b(|x|)$.

  Also define $\text{QMA} = \bigcup_p \text{QMA}_p (2/3, 1/3)$, where
  the union is over all polynomial-bounded functions $p$.

In Classical and Quantum Computation, Kitaev et al defined the same class (named as BQNP) as follows.

  A function $F:\mathbb{B}^n \to \left\{0, 1,
 \text{"undefined"}\right\}$ belongs to the class BQNP if there
  exits a polynomial class algorithm that computes a function $x \mapsto
 Z(x)$, where $Z(x)$ is a description of a quantum circuit, realizing
  an operator $U_x : \mathcal{B}^{\otimes N_x} \to \mathcal{B}^{\otimes
 N_x}$ such that

  $$ F(x) = 1 \Longrightarrow \exists |\xi\rangle  \in
 \mathcal{B}^{\otimes m_x} \mathbf{P} \left(U_x |\xi\rangle \otimes
 |0^{N_x - m_x}\rangle, \mathcal{M}\right) \ge p_1,\\ F(x) = 0
 \Longrightarrow \forall |\xi\rangle  \in \mathcal{B}^{\otimes m_x}
 \mathbf{P} \left(U_x |\xi\rangle \otimes |0^{N_x - m_x}\rangle,
 \mathcal{M}\right) \le p_0. $$

  Here $\mathcal{M} = \mathbb{C}\left(|1\rangle\right) \otimes
 \mathcal{B}^{\otimes (N_x - 1)}$, and  $p_0, p_1$ satisfy the
  condition $p_1 - p_0 \ge \Omega (n^{-\alpha})$ for some constant
  $\alpha > 0$. The quantifiers of $|\xi\rangle$ include only vectors of
  unit length. The quantum probability $\mathbf{P}(\cdot, \cdot)$ is
  defined as follows.

  For a quantum state given by a density matrix $\rho$ and a subspace
  $\mathcal{M}$, the probability of the event $\mathcal{M}$ equals
  $\mathbf{P}(\rho, \mathcal{M}) = Tr(\rho\Pi_\mathcal{M})$. Here,
  $\Pi_{\mathcal{M}}$ denotes the operator of orthogonal projection onto
  the subspace $\mathcal{M}$.

My question:

With $F:\mathbb{B}^n \to \left\{0, 1,
 \text{"undefined"}\right\}$ i.e. not having a promise problem, do Kitaev et al define a broader class of problems?


texts: Is the Set of all Primitive Words a Prime Language?

texts:
A word $w$ is called primitive, if there is no word $v$ and $k > 1$ so that $w = v^k$.
The set $Q$ of all primitive words over an alphabet $\Sigma$ is a well known language. WLOG we can choose $\Sigma = \{ a,b \}$.

A language $L$ is prime, if for every language $A$ and $B$ with $L = A \cdot B$ we have $A = \{\epsilon\}$ or $B = \{ \epsilon \}$.

Is Q prime?

With the help of a SAT solver I could show that we either have $\{a,b\} \subseteq A$ or $\{a,b\} \subseteq B$ as otherwise $\{ ababa, babab \} \subset Q$ cannot be factorized into $A$ and $B$, but have been stuck since then.


texts: Partitioning graph for Graph Isomorphism

texts:
Motivation: I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases .

Partition method:
$G$ is an $r$ regular graph, $k$ connected (not a complete, cycle graph).  A vertex of $G$ is $x_1$.
All vertices which are not adjacent to $x_1$ create a sub-graph $C_1$.
  All vertices adjacent to $x_1$ create a sub-graph, $ D_1 $.
A vertex of $D_1$ is $x_2$.

Using same method, based on adjacency of $x_2$ , $D_1$ can be divided.

All vertices which are not adjacent to $x_2$ create a sub-graph $C_2$.

All vertices adjacent to $x_2$ create a sub-graph, $ D_2 $.
    In general, $ D_{y-1} $ is a graph and can be divided/partitioned  into 2 sub-graphs $C_y,  D_y $.

At this stage, let me restrict the problem for simplicity of computation. Restrictions are:

$C_y,  D_y $  are $s_y , t_y>0 $ regular graphs respectively for all iteration $y$
$C_y,  D_y $  cannot be complete bipartite graph (utility graph), complete graph or disjoint union of complete graphs.

So, $ D_{y-1} $ is a $t_{y-1}$ regular graph and can be divided/partitioned  into 2 sub-graphs $C_y,  D_y $. $C_y,  D_y $  are $s_y , t_y $ regular graphs respectively (given condition).

$G$ can be divided/partitioned a maximum of $\log_2(|G|)$ times, using  this dividing process recursively.

Matrix representation :
 $A$ is an adjacency matrix of an $r$-regular graph $G$.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x_1 \in G$.
$A_x$ is the adjacency matrix of the graph $(G-x_1)$, where $C_1$ is the adjacency  matrix of the graph created by vertices which are not adjacent to $x_1$, and $D_1$ is the adjacency matrix of the graph created by vertices which are adjacent to $x_1$. $C_1,D_1$ are sub-graphs (regular) of graph $G$, $|C_1|>|D_1|$ where $|C_1|,|D_1|$ are total vertices number of graphs $C_1,D_1$ respectively.
$$ A_x
=
\left( \begin{array}{ccc}
C_1 & E_1  \\
E_1^{T} & D_1 \\
\end{array} \right)
$$

Again, this process can be done recursively, where $A_{y+1}=D_y$, $y=$ iteration number of the recursive process.
$$ A_yx
=
\left( \begin{array}{ccc}
C_y & E_y  \\
E_y^{T} & D_{y} \\
\end{array} \right)
$$

$A_x$(=$A_1x$) is the matrix of 1st iteration, for 2nd iteration, $A_x$ matrix would be $A_2x$.

Claim:
 It is not possible to have an $E_y$ matrix as a zero matrix, i.e., it is not  possible to have disconnected sub-graphs $C_y,D_y$ under the given conditions  that $G$ is $k$ connected $r$ regular and $C_y , D_y$ are always regular (which are not complete bipartite, complete graph  nor disjoint union of complete graphs)  graphs in this recursive process.

Question: how  a graph can be constructed  so that the graph has regular subgraph as described above?

Edition 1 : V.A.Taskinov, Regular subgraphs of regular graphs. Sov.Math.Dokl.26(1982), 37-38 .
In this paper he proved the following : Let $0<k<r$ be positive odd integers. Then every $r$-regular graph contains a $k$-regular subgraph (here, the graph need not be simple).


texts: Equivalence of feasibility checking and optimization for linear systems

texts:
One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the optimal solution and introduce it as a constraint via binary search.

Both of these reductions are polynomial, but not strongly polynomial (i.e they depend on the number of bits in the coefficients of the inequalities).

  Is there a strongly polynomial reduction from LP optimization to LP
  feasibility ?


texts: A separation between $QMA$ and $QCMA$ remains a notoriously difficult open problem. Even an oracle separation remains elusive. Have there been any recent efforts towards establishing such a separation, either oracular or non-oracular? The most recent I know is this paper which separates the two classes with respect to an "in-place oracle".


texts: Average Regret Bounds for Linear Stochastic Bandits

texts:
I am reading this paper on linear stochastic bandits :

http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf

All the results are stated in a high-probability setting, that is $\delta$ is a parameter to the algorithm , the regret at time $T$ is such that ,

\begin{align*}
\mathbb{P}(R_T > f(T) ) \geq 1 - \delta
\end{align*}

Is there any resource where the bounds are obtained in the form $\mathbb{E}[R_T] \leq f(T) $ ?

Trivially replacing $\delta = \frac{1}{T}$, does not give an anytime algorithm, that is the bounds don't hold for all $t > 0$.


texts: $\mathsf{P}$ is the closure of [finite set] under [operation between languages]

texts:
I am searching for statements of the above form, that is, asserting the existence of a finite set $F$ of languages and one or more operations $\otimes\colon \mathcal{P}(\Sigma^*) \times \mathcal{P}(\Sigma^*) \to \mathcal{P}(\Sigma^*)$ such that $\mathsf{P}$ is the smallest class containing $F$ and closed under $\otimes$.

Ideally, the operations should be computable and natural in some intuitive sense, and the languages in $F$ quite simple.  I'd like to avoid, say, that a language of $F$ encodes all polytime machines, or that one operation "runs" a Turing machine.


texts: Detecting circuit that's similar in functionality and implementation

texts:
Let $x=(x_1,\dots,x_n)$ be a vector of boolean variables.  Let $C,D$ be two boolean circuits on $x$.  Say that $C$ is similar to $D$ if:

$\Pr[C(x) \ne D(x)]$ is exponentially small, when $x$ is drawn uniformly at random from $\{0,1\}^n$ (in other words, they have almost-identical functionality); and,
$C,D$ differ in graph edit distance by a tiny amount (their edit distance is much smaller than the size of the circuit, say, $O(1)$ or some small constant), meaning that almost all of the gates and wires of $C$ match a corresponding gate and wire in $D$, with only a few gates added/deleted/changed.

My problem: I am given a circuit $C$, and I want to know whether there exists a circuit $D$ that is similar to $C$ but not identical to $C$ (i.e., where there exists $x$ such that $C(x)\ne D(x)$).

Can anyone suggest an algorithm to solve this problem?

If it helps, we can restrict attention to circuits $D$ that are smaller than the given circuit $C$ (i.e., we want to know whether there exists a circuit $D$ such that $D$ is smaller than $C$, $D$ is similar to $C$, and there exists $x$ such that $C(x)\ne D(x)$).

If it helps, you can additionally assume we are given known-good test cases $x^1,\dots,x^m,y^1,\dots,y^m$ such that $C(x^i)=y^i$ for all $i$, and we can further restrict attention to only circuits $D$ such that $D(x^i)=y^i$ for all $i$.

This arises from a practical application, so if you can't solve this problem, feel free to solve any variant or interesting special case.  For instance, feel free to instantiate any of the parameters or thresholds in any way that's convenient for you.  You can assume the circuits are not too large (polynomial sized, or something).  Feel free to replace graph edit distance by some other measure of near-match of implementation.  Also, in practice SAT solvers are often surprisingly effective on the structured circuits that arise in practice, so it's probably fine to invoke a SAT solver as a subroutine/oracle (at least, if you're invoking it on something like a SAT instance derived from a circuit like $C$).

Alternatively, lacking any algorithms, I would also be interested in the existence question: for an "average" circuit $C$, what's the probability that there exists some $D$ that meets all the criteria?  (I'm hoping this probability is very low, but I have no clue if that is the case.)

The practical application is to test whether a circuit $C$ might contain a malicious backdoor / hidden Easter egg.  The hypothesis of how such a thing might get inserted goes like this.  We start with a "golden" circuit $D$, that computes the desired functionality and has no hidden backdoor.  Then, the adversary makes a small change to $D$ to introduce the hidden backdoor, obtaining a modified circuit $C$.  The purpose of the backdoor is to change the function computed by $D$ in some way.  If $\Pr[C(x) \ne D(x)]$ is not too small, the change can plausibly be detected by random testing, so an adversary will probably try to keep $\Pr[C(x) \ne D(x)]$ very small.  Similarly, if $C$ differs from $D$ in too many places, this might be noticed by random inspection of the circuit, so an adversary will probably try to minimize the number of changes.  (And, there may be a test suite of $x^i,y^i$ pairs that represent instances of the desired functionality, so we know that whatever the "golden" circuit $D$ is, it satisfies $D(x^i)=y^i$ for all $i$.)  Ultimately, we are given the circuit $C$ (but not the "golden" circuit $D$), and we want to know whether $C$ might be a modified version of some $D$, where the modification was made to introduce a hidden backdoor of this sort.


texts: What's the difference between ADTs, GADTs, and inductive types?

texts:
Might anyone be able to explain the difference between:

Algebraic Datatypes (which I am fairly familiar with)
Generalized Algebraic Datatypes (what makes them generalized?)
Inductive Types (e.g. Coq)

(Especially inductive types.) Thank you.


texts: is Zero knowledge Proof same as commitment schemes?

texts:
I am studying about the zero knowledge proofs and I am looking for a practical (example based) approach to undrestand its process. I have studied the theory a little bit and I find it interesting yet confusing.

My exact question is given a prover A and verifier B. How can prover A prove that he is in the possession of some value 'X' without disclosing 'X' to B. 'X' could be A's last name or A's telephone number.

I am trying to compare this approach with commitment schemes (i.e. Hashing 'X' and comparing the hashes). I know that in the commitment schemes the value 'X' must be shared with B.


texts: Is there current research into the implemention of Randomness Extractors?

texts:
Has there been research into implementing randomness extractor constructions?

It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making programmatic implementations potentially unrealistic.

Some context:
I'm interested in using randomness extractors as a fast source of (provably?) random numbers for use in Monte Carlo simulations. We (an ETHZ Computational Physics group) have biased high-entropy sources from quantum random number generators that we would like to extract randomness from. A previous student attempted to implement a Trevisan construction and ran into spacial complexity problems. Aside from that student, I have not found any reference to people trying to implement extractors.

Note:
I'm a CS undergrad who is very new to the area of Theoretical CS and Randomness Extractors.


texts:
Counting the number of solutions is harder than judging the existence of solutions.

Counting independent sets of a graph is notably #P-complete, and so is of a hypergraph.

Two similiar questions in TCS Stack Exchange are here: counting independent sets and does faster exact algorithm for counting independent sets in comparability graph

Moreover, counting independent sets of a given bipartite graph(it is also a comparability graph) is also #P-complete, it doesn't mean counting these is always hard, actually, there are polynomial time (some are linear time)
algorithms for cocomparability graphs, trees, permutation graphs, chordal graphs, distance-hereditary graphs, tree convex bipartite graphs, graphs with bounded bipartite pathwidth and so on. There are also some polynomial time approximation algorithms for some types of graphs.

A benign exact exponential algorithm for counting independent sets generally is in fact a direct application of a #2SAT exact algorithm because any undirected graph can be viewed as a special 2CNF where each literal is a pure literal.

How is the progress on counting independent sets of various graphs? Without the help of #2SAT algorithms, it seems hard to design a fast exact algorithms on counting independent sets from a general case of graphs or general bipartite graphs.

There are some surveys telling the progress, but what I can find from papers are all no newer than 2004, which is at least 16 years ago. How is the progress recently? Increasing number of types of graphs have been shown easy for counting, but it is too many and I tend to miss some.


texts: How do continuations represent negations (under the Curry–Howard correspondence)?

texts:
Under the Curry–Howard correspondence, types can be thought of as propositions, and values inhabiting a type can be thought of as proofs that the corresponding proposition is true. (E.g., the Cartesian product is logical conjunction.)

Negation is represented as $A \to \bot$, where $\bot$ is the empty type. This works because if a type is inhabited, there can't be any function $A \to \bot$ (if you do you have such a function and the type is inhabited, feed the value into it and you get an element of the empty type, hence a contradiction), and vice versa (if $A$ is empty, the empty function $A \to \bot$ exists).

But once you add continuations to your language, an $A$-continuation can also be given the type $A \to \bot$. (see e.g. the symmetric lambda calculus). This apparently provides computational meaning to classical theorems; for example, the $\mathcal{C}$-operator (a basic operator for manipulating continuations), has type $\neg\neg A \to A$.

But can't you have continuations for non-empty types? If you add continuations, does $\neg A$ no longer express "$A$ is-empty/is-false/has-no-proofs"? It can't, right? This formulation makes an inhabitant of $\mathbb{N} \to \bot$ axiomatic, and $\mathbb{N}$ certainly isn't uninhabited. So what does "$\neg A$" actually express, if not "$A$ is-empty/is-false/has-no-proof"? And how do you actually express "$A$ is-empty/is-false/has-no-proof" when continuations exist?


texts:
Short summary: The problem is to assign people to meetings at different days while respecting the capacities and (inter-day) constraints of the meetings. Each person can only attend at most one meeting at a day.

I don't know if this problem has a common name - therefore the weird title question, sorry. If I overcomplicated any part of the problem definition, let me know.

People P = $\{p_1, .., p_n\}$, Meeting days D = $\{d_1, .., d_m\}$,

Meetings for each day: $M_{d_1} = \{m_{d_1,1}, .., m_{d_1,a}\}, M_{d_2} = \{m_{d_2,1}, .., m_{d_2,b}\}, .., M_{d_m} = \{m_{d_m,1}, .., m_{d_m,z}\}$
The $M_{d_i}$'s are pairwise disjoint.
Each meeting $m$ can hold a maximum number of people of $\text{cap}_{m}$ (capacity),

A person must not attend two (or more) meetings at different days that are "similar". (These conflicts are only between different days ("inter-day conflicts"). There are no conflicts within a day.)
Therefore define meeting constraints $C=\{c_1,..c_q\}$. Every meeting $m$ has exactly one corresponding constraint $c_i = \text{const}(m)$, s.t. [$\text{const}(m_i) = \text{const}(m_j)$] iff. [$m_i$ is "similar" to $m_j$] for all meetings.

There are preferences which person wants to attend which meeting at a particular day, e.g.:
(here 2 preferences are specified - if we generalize it to a fixed $K$ does the problem get any harder with regards to NP-hardness etc?)
$\text{Prefs} = \{$
$(p_1, \color{red}{d_1}, m_{\color{red}{d_1}, \color{green}{2}}, m_{\color{red}{d_1}, \color{green}{4}}),$ // Person 1 wants to attend the $\color{green}{2nd}$ or $\color{green}{4th}$ meeting at $\color{red}{day 1}$
$(p_1, d_3, m_{d_3, 1}, m_{d_3, 2}),$
$(p_3, d_2, m_{d_2, 2}, m_{d_2, 3}),$
$..$
$\}$, where:
a) every person-day combination $(p_i, d_j, ..)$ appears at most once.
b) every tuple has the form: $(p_i, \color{red}{d_j}, m_{\color{red}{d_j}, a}, m_{\color{red}{d_j}, b})$, with $a \neq b$ ($\widehat{=}$ valid preferences only)
(Note: The meeting preferences for each person-day combination are not supposed to be in any order, so (.., .., $x$, $y$) does not mean $x$ is preferred over $y$.)

A valid solution to the problem is:
Assign each person-day combination $(p_i, d_j, X, Y) \in \text{Prefs} $ to the meeting X or the meeting Y or no meeting at all, s.t.:
a) for every meeting $m$: we don't assign more people to $m$ than its capacity.
b) for every person $p$: for every constraint $c$: the person $p$ is assigned to (at most) one meeting with constraint $c$. (Otherwise, $p$ would attend two meetings at different days that are "similar".)

We want to maximize the number of person-day combinations that are assigned to a meeting. (So minimize the number of person-day combinations that are assigned to no meeting at all.)

Is this problem in $P$? (If yes, what is the idea for a polynomial-time algorithm?)
Is this problem NP-hard? (I tried a reduction from Bin-Packing $\leq_p$ ThisProblem, but without success. I think it's NP-hard and would appreciate any helpful ideas for reductions.)


texts:
I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas.

Consider the random graph model $G_{n,p}$ where its a random graph on n vertices and each edge is selected with probability $p$. I want to prove that a certain property $P$ is satisfied by graphs in this model with high probability ($\rightarrow 1$ as $n \rightarrow \infty$). I know/can prove the following two facts

Conditioned on the event that the graph obtained from the sample is regular, the probability of the property being satisfied is very high (something like $1 - 1/n^c$)
Given any graph G and any other graph G' that can be obtained by removing edges from G. If G satisfies the property then so does G'.

Can the above two statements be enough to make a general statement about the probability of the satisfaction of the property in $G_{n,p}$

Any references would be very helpful?


texts: What kind of string is produced by successive application of argmax M

texts:
Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$.

Start with some $\omega_0$. Each subsequent element is given by $\omega_n=\arg \max_a\mathbf M(a|\omega_{1:n-1})$.

What are the properties of $\omega$? For example, is it necessarily computable? Does the answer depend on the choice of $\mathbf M$?

UPDATE

The equivalent formulation is the following but it does not really help me advance with the problem.

Is there a universal lower semicomputable $\lambda$-supermartingale $t$ and a binary sequence $\tilde\omega$ such that $t$ always "goes up" along $\tilde\omega$ but never succeeds?

This type of problem arises when a player plays against a reactive environment and the sequence the player observes is not exogenous. A more general question is what is the short-run behavior of $\mathbf M$ since asymptotic results do not seem to help here.


texts: Mathematical background needed for pursuing a PhD in TCS

texts:
Possible Duplicate:
  What kind of mathematical background is needed for complexity theory?

I'm a final year undergrad and I'm looking to pursue a PhD in theoretical computer science in the long term. I've been admitted to some great schools to do theory, I'm looking to defer all my admits to study math for a year in the university.

I'd very much appreciate your thoughts on the following couple of questions.

So, given that I'm not really sure what sort of theory I want to be doing at grad school (as of now, algorithms and combinatorics) what sort of things should I be looking to study there?
As someone who has studied computer science and not pure mathematics for the last few years, I want to take the next few months to prepare myself for the course. Can anyone recommend areas (and/or books) to bone up on before going there?
(Since for instance, I never formally studied abstract algebra or complex analysis)

Thanks.


texts: Is it right to call $2^{\sqrt{n}}$ "exponential"?

texts:
In his answer to a previous question, Sadeq Dousti recalled the following terminology:

$f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.)
$f(n) = 2^{n^{\Theta(1)}}$ is called exponential. (e.g. $2^n, 3^{n^4}$.)
$f(n) = 2^{n^{o(1)}}$ is called sub-exponential. (e.g. $2^{n^{1/n}}, n^{\log n}$.)

Is this standard terminology?

In particular, I am interested to know whether it is OK to call $2^{\sqrt{n}}$ and other functions in $2^{n^{\Theta(1)}}$ exponential or not.

Edited after 1st answer: Yes! The issue is when you have a $2^{\sqrt{n}}$ lower bound. Can you say that this is an "exponential" lower bound?

I am thinking here of a lower bound for a combinatorial value, not for some time complexity where one has standard definitions for $\mathsf{E}$ and $\mathsf{EXPTIME}$. I now realize I probably picked the wrong keywords.


texts: Are edge-vertex graphs of polytopes (decent) expanders?

texts:
This question is inspired by the polynomial Hirsch conjecture (PHC). Given a $n$-facet polytope $P$ in $\mathbb R^d$, is the spectral gap of its edge-vertex graph (call it $G$) lower bounded by $\Omega(1/\mathrm{poly}(n))$? Note that the cycle graph on $n$ vertices shows that, even for $d=2$, the spectral gap could be as small as $O(1/\mathrm{poly}(n))$; so the conjectured bound--if true--would be almost tight.

A yes answer would imply the PHC. In fact, it would also imply that linear programs can be solved efficiently by just a random walk on the polytope vertices, and this algorithm is not even paying much attention to the objective function! This seems too good to be true.

So, what is the status of this problem: open (like PHC), or false? If false, are there simple counterexamples?

Note: I just realized about the usual complications involved in defining expanders: $G$ need not be regular or bipartite. I hope that both of these technical issues can be overcome using standard ways, and that, in particular, they do not make my question trivial. (Please correct me if I am wrong!)


texts: Example of logarithmic length witness being easier to verify than find

texts:
An easy observation is that if a problem $A$ is decidable by a polynomial-time nondeterministic program using $O(\log n)$ nondeterministic bits (i.e., all witnesses are logarithmic in length), then $A \in \mathsf{P}$.

If one then asks the question, "Is it easier to verify a witness than to find one?" for such problems, and one considers all polynomial running times equivalent, then the answer is no, since one can find such witnesses in polynomial time by searching through all potential witnesses.

But what if we consider fine-grained distinctions between polynomial running times? I'm wondering if there is a concrete example of a natural problem in $\mathsf{P}$ that has logarithmic-length witnesses that are easier to verify than to find, where "easier" means a smaller polynomial running time.

For example, known algorithms for perfect matching in graphs take polynomial time, but more than $O(n)$ time on a graph with $n$ nodes. But given a set of $n/2$ pairs of nodes (a witness), it is easy to verify in time $O(n)$ that it is a matching. However, the matching itself requires at $\Omega(n)$ bits to encode.

Is there some natural problem that achieves a similar (apparent) speedup in verification versus finding, in which the witness has logarithmic length?


texts: Resources for complexity results for optimization problems in restricted graph classes

texts:
I am specifically interested in optimization problems in graphs (minimum coloring, maximum clique, maximum matching etc.) and I need a resource (database) which contains complexity results on different graph classes. The best resource that I know is the following:

http://graphclasses.org/

I think this web site is great because it covers all the graph classes, however the results presented (recognition, independent set, domination) in the site and my interests do not match.

I am looking for similar resources.

Thanks.


texts:
A matching in a graph is a set of edges that are pair-wise non-adjacent. IOW, each node involved in the matching appears in only one edge.

Now I am wondering is there a ``generalized'' concept of matching, such that it still refers to an edge-set, and each vertex involved can appear in at most $k$ edges in this edge-set, where $k \ge 2$ is a pre-specified positive integer.

If such concept does exist, what are some interesting and representative problems studied for that?


texts: Is there an analogy of a vertex separator for hypergraphs?

texts:
Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs.

Is there some survey or book or lecture notes about various hypergraph parameters such as independent set, matching, separator, cut, and so on?

In particular, I am interested in an analogy of separator. For a graph $G=(V,E)$, a separator $S$ is a subset of vertices such that removing all elements in $S$ we can obtain two or more separated components $G_{1},G_{2},...$. I am interested in minimum size of separator for hypergraphs.


texts: Is there a normalizing (or perpetual) reduction strategy for untyped combinators?

texts:
Inspired by this question, I was curious whether there was a reduction strategy for untyped SKI combinators that was known to be either normalizing or perpetual.

As described here (Twelfed here), the nondeterminstic rules of the combinator calculus are these:

$Ix \rightarrow x$

$Kxy \rightarrow x$

$Sxyz \rightarrow xz(yz)$

$xy \rightarrow x'y$ if $x \rightarrow x'$

$xy \rightarrow xy'$ if $y \rightarrow y'$


texts: Lower bounds for randomized frequency estimation algorithms

texts:
Consider a stream of elements $s_1s_2\ldots s_N$.
A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"?

It is well known that answering such queries to within a one-sided additive error of $N/(k+1)$ requires at least $k$ counters by any deterministic algorithm (see here).

Assume we allow randomized algorithms for the task.

  Which lower bounds (on the number of counters required) can we derive on a randomized algorithm which satisfies $$ f_x -N\epsilon\le\mathbb E(\text{query}(x))\le f_x,$$ where the expectancy is over the algorithm internal randomness?

In particular, the Majority algorithm (see 1 and [2]) is able to find a majority item in the stream using a single counter.

  Is there a randomized algorithm which is able to identify, using a single counter, an element arriving at least $N(0.5-c)$ of the time for some fixed $c>0$ (with probability larger than 1/2)?

1]  R. Boyer and J. Moore. A Fast Majority Vote Algorithm.
Technical Report 1981-32, Institute for Computing
Science, University of Texas, Austin, 1981.

2] M. Fischer and S. Salzberg. Finding a Majority
Among N Votes: Solution to Problem 81-5. Journal
of Algorithms, 3:376–379, 1982.


texts: Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

texts:
In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| \in o(m^2)$ is found, that would refute ETH.

There is a reduction from $\oplus k$-SAT with $n$ variables and $m$ clauses to $\oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| \in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.

Question
Can the same line of reasoning made within the linked question be applied here in order to refute $\oplus$ETH, or am I missing some important detail?


texts:
I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied.

For example, i would like to shuffle 4 decks of cards, and make sure:

Any consecutive 4 cards won't come from the same deck.

Surely I can do the fisher-yates-Knuth shuffling first and then filter out bad permutations, but if the restrictions are strong (e.g. any consecutive 2 cards won't come from the same deck), there will be too many failures.

If i don't mind that if it is slightly unbiased, (of course the less bias the better), how should I do?


texts: Is the traditional analysis of Bloom filters wrong?

texts:
This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was published in 2010, yet I've seen the traditional analysis of Bloom filters continued to be taught in various algorithms and data structures courses.

Is the traditional analysis of Bloom filters indeed incorrect?

Thanks!


texts: Is finding the optimal ordering of predicates NP?

texts:
Assume we want to find the elements from a set of elements $\mathscr{E}$ for which all predicates from a set of $n$ predicates $\mathscr{P}$ evaluate to true.
In programming terms, we want to compute filter(E, P).
For each predicate $p_i$, let $P(p_i)$ be the probability of it evaluating to true on a random element from $\mathscr{E}$ and $C(p_i)$ as the constant cost of its evaluation.
Assume there is no correlation between the predicate probabilities.
After a predicate fails for an element, no subsequent predicates are going to be evaluated for that element.
To me, it seems that ordering the predicates by nonincreasing $C(p_i)/(1 - P(p_i))$ and evaluating them in that order will be optimal, as it would be using the most efficient predicates first. Semantically, $C(p_i)/(1 - P(p_i))$ can be interpreted as the cost per element removed.
However, I not only don't know whether or not this assessment is correct (and the problem is $O(n \log n)$), but I also don't know how one would rigorously prove that this ordering is an optimal ordering for minimizing the overall evaluation cost.

As requested in the comments, I came across this problem when thinking about the optimal order of filters over a collection of elements. I wondered if I could compute the optimal order if I knew fairly well the probability of the predicates being true and the cost of evaluating each one of them in order to write a more efficient combined filter.
My question already has a good answer in the CS SE. I didn't know we had two SEs for CS, so I assumed, wrongfully, that TCS (cstheory) was the right board to search for and post my question.


texts: Approximately sampling from convex polyhedrons with quantum computers

texts:
Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that can be computed in polynomial time then with quantum computers we can efficiently sample according to the distribution described by the Fourier expansion of $f$. (We do not know how to do it with classical computers.)

  Can we use quantum computers to sample or approximately sample a random point  in a polyhedron described by a system of $n$ inequalities in $d$ variables?

Moving from the inequalities to the points looks to me somewhat similar to a "transform". Moreover, I would be happy to see a quantum algorithm even if you modify the distribution, e.g. consider product of Gaussian distribution described by the hyperplanes of the polyhedron or some other things.

A few remarks: Dyer, Frieze and Kannan found a famous classical polynomial time algorithm to approximately sample and approximately compute the volume of a polyhedron. The algorithm is based on random walks and rapid mixing. So we want to find a different quantum algorithm for the same purpose. (OK, we can hope that a quantum algorithm may lead also to things in this context we do not know to do classically. But to start, all we want is a different algorithm, this must be possible.)

Second, we don't even insist on approximately sampling the uniform distribution. We will be happy to approximately sample some other nice distribution which is roughly supported on our polyhedron. There is an argument by Santosh Vampala (and also by me in another context) leading from sampling to optimization: if you want to optimize $f(x)$ sample to find a point $y$ where $f(x)$ is typical. Add the constraint $\lbrace f(x) \ge f(y)\rbrace$ and repeat.


texts: Weighted vertex-connectivity; global min vertex-cut

texts:
I am interested in the following problem:

Input: a connected undirected graph $G=(V,E)$; a positive weight for each vertex.
Output: a minimum weight subset of $V$ whose removal disconnects $G$.

When each vertex has the same weight this is equivalent to determining the vertex-connectivity. Intuitively, it is the vertex version of the global minimum cut problem.
I can think of an $O(mn^3)$ algorithm that solves $O(n^2)$ minimum $s$-$t$ cut problems, but I expect that there should be a faster approach. Does this problem have a name? What is the fastest known algorithm?


texts: Resource tradeoffs in interactive proofs

texts:
In an interactive proof, there are a number of resources that can be traded off against each other. For example, verifier time, verifier space (as per this question), amount of randomness used, number of bits of proof probed (for PCPs), the number of rounds, and so on.

Is there any survey of the known tradeoffs between the different resources used in an interactive proof ?


texts: Is there a useful notion of pathwidth-treewidth for posets?

texts:
Consider a poset $P = (V,A)$. We may define a path structuring of $P$ as a chain $\Sigma$ of the form $X_0 \subset X_1 \subset \ldots \subset X_n$ where :

(i) for every $x \in V$, the set $\{ i \in [n] : x \in V_i \}$ is an interval,

(ii) for every $i$ we have $X_{i+1}$ of the form $X_i + \{x\}$ or $X_i - \{x\}$,

(iii) for every $i < j$, $P$ contains no backward arcs joining $X_j - X_i$ to $X_i - X_j$.

The width of $\Sigma$ is defined as $w(\Sigma) = \max_i |X_i|$, and the path-width of $P$ is defined as the minimum width of a path structuring of $P$. In particular, the path-width is always smaller than the width (defined as the size of a largest antichain).

The following questions seem natural in this respect:

is it possible to define a corresponding notion of tree-width that is well-behaved? E.g. we would expect forest posets to have tw at most 1, and series-parallel posets to have tw at most 2.
is it possible to get a width measure that is algorithmically useful? A possible application would be the counting of linear extensions: it is feasible in $n^{O(w)}$ for a poset of width $w$, but the extension to path-width / tree-width seems unlikely at this point.


texts: What's the difference between term rewriting and pattern matching?

texts:
As there was no response at Lambda the Ultimate I try it here again: term rewriting systems are used for instance in automated theorem proving a symbolic calculation, and of course to define formal grammars. There are some programming languages based in term rewriting, but as far as I understand the concept is more known as pattern matching. Pattern matching is used a lot in
functional languages. Barry Jay has created a whole theory called pattern calculus, but he only mentions term rewriting in brief. I have the feeling that they all refer to the same basic idea, so can you use term rewriting and pattern matching synonymously?


texts: Is there a series of algorithms for approximating TSP polynomially?

texts:
I've began studying some CS recently, and I've faced the TSP.
The decision problem version of the TSP is NP-complete, right?
I've noticed (and elaborated myself) that there exists several polynomial time
approximations for the TSP. Combined with the decision problem, this "lowers"
the complexity of the algorithm for some values given for the decision, because
those values may lie outside of the estimation: say the decision asks for a path no longer
than 50 and we find a path of 150 which is at most 2x the minimum path, then we would
only need polynomial time for evaluating it.

So my question is as follows: is it
possible to assemble algorithms with polynomial time (with any polynomial order) that
 approximate the TSP to a given ratio? Because then, I could be able to add a series
of algorithms before the actual non-polynomial time algorithm to progressively lower it's
complexity. Assembling this series of algorithms to find the exact solution would probably require an infinite series of polynomial time, which cannot have polynomial time as a whole. But I think it is possible to use tricks to limit this to a finite number, which would result in a total polynomial time for any given decision value. Think about it: the
worst case of this problem is when the decision parameter is exactly the TSP solution -
we thus have some information about it. Since P probably differs from NP, I guess there are no such algorithms?

Sorry If I sound a bit confusing, I don't know If my thoughts make much sense
mathematically.


texts: Algorithm: Find the first k longest substrings between two similar strings

texts: Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.


texts: Names for the left- and right-hand sides of a grammar production?

texts:
Problem

I'm writing a document where I have to describe some of the properties of a type system as they relate to a particular formal grammar.

I was trying to refer to the right-hand-sides of the last two productions in the grammar when it struck me that it's very strange that I've pretty much always heard the left- and right-hand sides describes as such.
In particular it seems like an artifact of our notation having its roots in languages which are read from left-to-right.

It would make sense for there to be terms like in logic, where the left-hand-side of an implication is the antecedent and the right-hand-side is the consequent.
These words don't refer to the notation properties, but actually describe the meaning of the implication from each side (although I suppose you could make the argument that they are artifacts of our conception of causality, but at least this provides some insight into the interpretation of the terms rather than the notation).

What I've tried so far:

I thought about it for a little while and the most natural words I could come up with were source and destination (obviously for the left- and right-hand-sides of the production, respectively.)

Sources I've checked:

Looked through a couple of my textbooks on formal languages and compilers;
Checked some likely Wikipedia pages;
Skimmed/ctrl+f'd some online teaching resources, and of course;
Checked math.stackexchange and also cstheory.stackexchange

Are there alternative names which are in colloquial use among computer scientists for referring to these components?


texts: Improving the approximation in Stockmeyer's counting theorem

texts:
Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that
\begin{equation}
    \left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(1 + \frac{1}{\text{poly}(n)} \right) f(x),
\end{equation}
using a $\text{BPP}^{\text{NP}}$ algorithm. How much better of an approximation can we get if we go higher up in the polynomial hierarchy? Is there a no-go result saying this is very close to the best approximation that we can hope for?


texts: Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?

texts:
I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the internet.
Clarification: I don't care about deciding if the language is deterministic, just whether a specific grammar is deterministic.


texts: Weight enumerator and levels of polynomial hierarchy

texts:
Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that:

$A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$.
$A_{n}$ is in $\#P-Complete$, equivalently, computing $A_{n}$ is hard for $PH$, under polytime Turing reductions. See here and here.

What about the computational hardness of $A_{i}$ where $i = polylog(n)$ ? Are there results of the type: $A_{\lceil \log_{2}^{k}n \rceil} \in \Sigma^{P}_{k-1}$ ?

This question may be related to this stack exchange question.


texts: Weight enumerator of a binary linear code

texts:
The weight enumerator polynomial of a $(n,k)$ binary linear code $\mathcal{C}$ is defined as

$$WE(\mathcal{C}) = \sum_{i=0}^{n}WE_{i}(\mathcal{C}) x^{i}$$

where $$WE_{i}(\mathcal{C}) = \#\{c\in\mathcal{C} : |c| = i\}$$

is the number of codewords in $\mathcal{C}$ of Hamming weight (denoted by $|c|$) $i$.

It is known from:

Complexity issues in counting, polynomial evaluation and zero finding
The Complexity of Weighted Boolean #CSP

That computing the weight enumerator polynomial for a binary linear code is a problem in $\mathsf{\#P}$-complete.

I wish to know if anything is known about the case of:

computing the $i^\text{th}$ coefficient of the weight enumerator polynomial where $i = \text{polylog}(n)$ (otherwise a naive enumeration of all binary sequences of weight $i$ and verification of those in the code would be possible).
Computing the weight enumerator, given the promise $WE_{i}(\mathcal{C}) \leq n^\lambda$, for $\lambda$ any constant, independent of $n$.

Does the complexity of the problem remain $\mathsf{\#P}$-hard in both cases ?


texts: Is there a "lambda cube" for interaction nets?

texts: The lambda calculus is an untyped language that is often extended with logical frameworks such as the vertices of the λ-cube. Is there something similar to it, but for interaction nets? What about interaction combinators?


texts: Can Bencodes Be Described With a Context-Free Grammar?

texts:
Bencoding is the encoding scheme used by Bittorrent applications. You’re probably most familiar with bencoding via the .torrent file format used by Bittorrent applications. It’s a simple encoding scheme, so I am wondering if a context-free grammar could be constructed for it. There are a couple of reasons I think  it cannot:

The location of terminals depends on the ‘interpreted’ value of certain length-prefixed values.
Terminals can be present inside of non-terminal sequences, but in principal (i.e., in well-formed Bencodes) are not ever encountered by a parser except for verification maybe. In fact, entire Bencodes (in theory) could be present as values of, let’s say, a list element of a Bencode, but in such a way that they’re meant to be interpreted as “data” and not as something to be parsed or transformed by a rule. It’s ever-so-slightly more subtle than normal recursion as far as I can tell…

Update: When thinking about this I realized something odd whereby one could convert a context-dependent grammar into a context-free grammar; i.e., consider the problem of length-prefixed values such as appear in Bencode. For convenience I will use Bencode’s syntax; so let’s consider the string 5:hello. If you have a trivial function that converts the ASCII “5” into a unary value and all the other ASCII characters into a character then you have an equivalent structure.

Viz. 5:hello becomes olleh:hello; I like the idea of reversing the string because then you could easily construct another function to map the string back onto the ASCII numeral (after appropriate checks have been made that the string is in fact the length reported as to not skew semantics; I am not considering non-conforming strings, since we are talking about grammar...).

This is of course a very simple case of dependent grammar, but I wonder 1.) if anybody else has noticed this (I am sure), and 2.) if this could resolve some other context-dependent situations.


texts: On the paper "Quantum Computing Hamiltonian cycles"

texts:
The paper Quantum Computing Hamiltonian cycles claims:

An algorithm for quantum computing Hamiltonian cycles of simple,
cubic, bipartite graphs is discussed. It is shown that it is possible to
evolve a quantum computer into an entanglement of states which map
onto the set of all possible paths initiating from a chosen vertex, and
furthermore to subsequently project out all states not corresponding to
Hamiltonian cycles.

The algorithm requires polynomial in $n$ qubits and gives
example with a quantum "gadget".
According to graphclasses
on bipartite ∩ maximum degree 3 graphs hamiltonian cycle is NP-complete.
cstheory claims

Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem

Since cubic planar bipartite graphs are subset of cubic bipartite
graphs, hamiltonicity of cubic bipartite graphs must be NP-hard too.
Doesn't the above arguments show that quantum computer can solve
NP-complete problem, including SAT, which appears to be open problem?
Can the paper be extended to other subclasses of graphs for which
hamiltonicity is NP-hard?
Bugs me the date of the paper is 29th February 1995 and this date
doesn't exist, since odd year can't be leap year.


texts:
Is the evaluation problem for $\mathsf{AC}^0_d$ circuits in $\mathsf{AC}^0_{d+1}$? What is the least depth $k(d)$ such that the evaluation of an $\mathsf{AC}^0_d$ circuits can be computed in $\mathsf{AC}^0_{k(d)}$?
How about the evaluation problem for $\mathsf{TC}^0_d$ circuits?
By evaluation problem for a complexity class $C$ I mean the following promise problem:

Given a circuit $c\in C$ and an input $x$ for $c$,
Output the value of $c(x)$.

Clarification
I don't need any particular input format, I can change other parts to use a similar encoding of circuits. So as long as the encoding is something reasonable it is good for me. By reasonable I mean it should be easy to do simple manipulations of circuits, e.g. given the code for two circuits it should be easy to determine the number of nodes in the circuits, given a circuit and $i$ determine the type of gate $i$ and its parents, etc.
For example, any of the following would work for me:

circuit is encoded as the adjacency matrix of the connection graphs where gates are numbered from $1$ to $n$, there is no wire from $g_i$ to $g_j$ then $i>j$, and the list of gate types. You can also assume that the number of gates and the size of the input are also provided (in unary).

the direct connection language of the circuit (which is used in the definition of $\mathsf{DLogTime}$-uniformity of circuits),

the extended connection language of the circuit (which is used in the definition of $\mathsf{DLogTime}$-uniformity for $\mathsf{NC^1}$).


texts: Graph with minimum number of edges having given sets of nodes as its paths

texts:
Consider the following problem:

Input: a list of subsets $P_1, P_2, \ldots, P_k \subseteq V = \{1, \ldots, n\}$
Output: a graph $G = (V,E)$ with minimum number of edges such that

for every $P_i$ there is a path in $G$ which has $P_i$ as its set of vertices.

Has this problem been studied?
Does it have a name?
What is the fastest known algorithm for solving it?


texts: Computational complexity of finding paths with specified product in a (group-labeled) directed graph

texts:
This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $G$ where each edge of the graph is labeled with an element of a group $\mathcal{G}$ (in this case, $D_4$, but the question obviously makes sense for any group), is there a vertex $v\in G$ and a simple cycle in the graph starting at vertex $v$ where the product of the edges in the cycle is the identity of $\mathcal{G}$ (or some specified element $g\in\mathcal{G}$)?
The problem is obviously in NP, but I don't immediately see a reduction from anything like 3-SAT, or a dynamic programming approach to the problem that would solve it in polynomial time. What's the complexity of this problem?


texts:
(I am in the middle of my first theoretical cs course, so I apologize in advance for what is probably a stupid question.)

So, we say that some language L is in P, which means that a Turing machine can be constructed which outputs a 1 if x is in L and 0 otherwise; in addition, the machine runs in polynomial time. I understand this.

But many people say that there are certain problems in P which do not appear to me to be decision problems; for example, maximizing a function subject to linear constraints. What does it mean that "linear programming" is in P? Surely "find the maximal value" is not a decision problem?


texts:
This is not my area, so apologizes if I am asking nonsense!

I know that there are very good solver/theorem provers for solving 1st order logic.

Now I have a problem, using 3-valued logic, but I am not sure if there are some practical ways of solving 3-valued logic (or converting it to a bigger 2-valued logic problem?)

EDIT1: Is it possible to translated (~reduce?) any 3-valued logic to 2-valued logic? Can this be generalized to K-valued logic, where K is any arbitrary integer? (What about the case when K is infinity?)

Any idea or reference is appreciated.


texts: Sampling from the binomial distribution with limited randomness and time

texts:
This is a basic question that I can't answer (it's not a homework assignment).  A reference would be perfectly acceptable.

Consider a $[0,k]$ valued random variable X distributed binomially so that:

$$\text{Pr}[X=i]=\binom{k}{i}/2^k$$

It's clear that we can sample from $X$ in poly($k$) time using $k$ random bits.  The basic question is if it's possible to do better if I'm only interested in approximate sampling.

For example, if I'm interested in sampling from any $Y$ so that $|X-Y|<\epsilon$ (in statistical distance), can I do this in randomized time poly($1/\epsilon$) (i.e., with $1/\epsilon$ random bits)?


texts: What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?


texts: Is this proof of $LP$ being in $coNP$ correct?

texts:
I am referring to the natural decision version of the Linear Programming problem: given $A \in \mathbb{Q}^{m \times n}, \ b \in \mathbb{Q}^m, \ c \in \mathbb{Q}^n, \ \alpha \in \mathbb{Q}$, does there exist $x \in \mathbb{Q}^n$, s.t. $Ax=b, \ x \geq 0, \ c^T x \geq \alpha \ ?$
Most ressources I know justify that $LP$ is in $coNP$ by referring to the dual problem: a certificate that such an $x$ does not exist consists of an optimal basis for the dual problem. A verifier can then check in polynomial time that the associated dual solution fulfills all dual constraints and that it has cost $<\alpha$.
However, I'm wondering: why couldn't we certify that such an $x$ does not exist by providing an optimal basis $B$ for the primal problem? It is well known from the revised simplex algorithm (see e.g. here for explanation of notations) that $x$ is optimal for the primal iff $(c_N - N^T (B^{-1})^T c_B) \leq 0$, and this can be verified in polynomial time. Therefore, we just need to check this condition and also that $c^T x < \alpha$. This gives an argument for $LP \in coNP$ that does not require knowing duality theory.
I am aware that if $x$ is optimal for the primal, then the vector $(c_N - N^T (B^{-1})^T c_B)$ is actually a solution of the dual, which makes my argument in essence equivalent to the classical argument that explicitly uses duality theory. Still, I'm wondering 1. whether what I've written here is correct and 2. why no one mentions this simple way to show $LP \in coNP$ in the literature.


texts:
Consider $n$ variables $x_1, \cdots, x_n$ and
$f=\sum a_i x_1^{d_{i1}}\cdots x_n^{d_{in}}$ such that for each $i$, $d_{i1}+\cdots+d_{in}=d$ for some fixed $d$ and $a_i\geq 0$.

I am interested in the following question :- given $f$ and $\theta$ decide whether there exist $x_i$ such that $\sum_{i=1}^n x_i=1$ and $x_i\geq 0$, $f\geq \theta$.

Is this problem $NP_R$-hard? (I am referring the Blum–Shub–Smale model.)


texts: Average-case analysis of algorithms using the incompressibility method

texts:
I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li & Vitanyi showcases many examples, although only two of them are about average-case analysis (heapsort and shellsort). I also found a paper analyzing the average-case of quicksort using incompressibility.

This got me wondering: is there some reason exactly these algorithms were analyzed? More generally, is there something in the nature of an algorithm that makes it suitable (or not at all suitable) for analysis using the incompressibility method?

In addition, does anyone know of any other papers/resources that show even trivial average-analysis of different kind of algorithms, perhaps other than sorting algorithms using the method?


texts: Two Decision Problems About Graphs --- Original Results?

texts:
I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell?

I don't have easy access to any standard texts that would help me out here. Nor indeed do I work in the field (but it would still be advantageous as well as personally satisfying if I could get a note in some journal or other). Anyway, enough prolog, on with the results.

Consider these two closely related problems:

PROBLEM 1: A complete digraph has its edges labeled with numbers. The "average score" of a circuit (not necessarily a cycle) in the graph is defined as the sum of the numbers along the edges traversed divided by the number of edges in the circuit. Is there a non-self-intersecting circuit having an average score greater than a given number?

PROBLEM 2: The same problem, except with the additional constraint that the circuit must pass through a given vertex of the graph.

Problem 1 can be solved in polynomial time. Problem 2 is NP-complete.

Thank you for your comments.


texts: Extensions of Ramsey's theorem: monochromatic but diverse

texts:
As a follow-up of my previous question, which was resolved by Hsien-Chih Chang, here is another attempt to find an appropriate generalisation of Ramsey's theorem. (You don't need to read the previous question; this post is self-contained.)

Parameters: integers $1 \ll d \ll k \ll n$ are given, and then $N$ is chosen to be sufficiently large. Terminology: an $m$-subset is a subset of size $m$.

Let $B = \{1,2,...,N\}$. For each $k$-subset $S \subset B$, assign a colour $f(S) \in \{0,1\}$.

Definitions:

$X \subset B$ is monochromatic if $f(S) = f(S')$ for all $k$-subsets $S \subset X$ and $S' \subset X$.
$X \subset B$ is diverse if $X = \{ x_1, x_2, ..., x_n \}$ such that $x_i < x_{i+1}$ and $x_i\,\not\equiv x_{i+1} \text{ mod } d$ for all $i$.

For example, if $d = 10$, then $\{ 12, 15, 23, 32, 39 \}$ is diverse but $\{ 12, 15, 25, 32, 39 \}$ is not. Note that a subset of a diverse set is not necessarily diverse.

Now Ramsey's theorem says that no matter how we choose $f$, there is a monochromatic $n$-subset $X \subset B$. And obviously it is trivial to find a diverse $n$-subset $X \subset B$.

Question: is there always a diverse and monochromatic $n$-subset $X \subset B$?

Edit: Hsien-Chih Chang shows that the claim is false for a prime $d$, but what about composite $d$? In my applications, I will have a lot of freedom in choosing the exact values of $d \ll k \ll n$, as long as I can make them arbitrarily large. They can be powers of primes, products of prime numbers, or whatever is necessary to make the claim true.


texts: What is the run-time of the bin packing approximation algorithm?

texts: The best approximation algorithm that I found for the bin packing problem is by Hoberg and Rothvoss (SODA, 2017). In their Theorem 1.2, they mention that their algorithm finds a solution with at most $OPT + \log(OPT)$ bins,  and its expected run-time is polynomial in the total number of items. However, I could not understand from the paper, what is the exact polynomial? That is:  if there are $n$ items with different sizes, what is a number $k$ such that the run-time is in $O(n^k)$?


texts:
In Abstract DPLL and some other sources there is a high-level framework/ model explained using states and transitions. I need (to build) such a model for a #SAT algorithm. I do know that #SAT algorithms can be build on top of DPLL or other solvers but i could not find a high-level framework/ model for #SAT.

Question: Is there any such or similar model for a #SAT solving algorithm, or else which rules will have to be added to abstract DPLL to get a #SAT solver?


texts:
I was reading up proof of Ladner's Theorem and I found this :

$$\mathrm{SATH} = \{ (x,\mathrm{pad}) \mid x \in \mathrm{SAT} \text{ and } |\mathrm{pad}|=|x|^{H(|x|)}\}.$$

If SATH is NPC (which implies that SATH not in P) and $H(|x|)$ goes to inﬁnity,
then SAT in P!

Proof: Suppose $f(x) = (x',\mathrm{pad})$, such that $|(x',\mathrm{pad})| \leq c|x|^c$. If $|x'|>|x|/2$,
then $|\mathrm{pad}| = |x',|x|^{H(|x|)} > c|x|^c$ (for long enough $x$). So $|x'|$ is
at most $|x|/2$.

Repeat to solve SAT.

What does it mean to repeat and solve sat? How does this make SAT in P.


texts: Looking for an online community specializing in the Z specification language, where I can ask questions

texts: Where can I find an online community specializing in the Z specification language, where I can ask specific questions about the ISO standard for Z?


texts: Factorizing semiprime $n=pq$ with $p \mid q-1$

texts: Could we find a fast integer factorization algorithm for any large semiprime $n=pq$, if we know that $p \mid q-1$?


texts: The theoretical complexity of Go - The state of the art

texts:
What are the latest advances in theoretical complexity of Go?

I know some early works about the complexity of Go:

"Go is polynomial-space hard" proved that Go is PSPACE-hard.
"Ladders are PSPACE-complete" proved that ladders are PSPACE-complete.
"Go endgames are PSPACE-hard" proved that Go endgames (or yose) is PSPACE-hard.
"On the complexity of Tsume-Go" proved that the the complexity of Tsume-Go is NP-complete.
"Go Complexities" proved that Atari Go is PSPACE-complete.

Since there are several rules of Go (They are different but similar), it is a little complicated to analysis it. We only know that the lower bound of the complexity of Go is PSPACE-hard and the upper bound of it is EXPSPACE.


texts: Does Approx Carathéodory's theorem implies dimensionality reduction

texts:
Carathéodory's theorem says that if a point $x$ of $R^d$ lies in the convex hull of a point set $P$, then there is a subset $P′ \subseteq P$ consisting of $d + 1$ or fewer points such that $x$ can be expressed as a convex combination of $P′$.

A recent result by Barman (see paper) shows an approximate version of the above theorem.
More precisely,  given a set of points $P$ in the $p$-unit ball with norm $p \in [2,\infty)$, then for every point $x$ in the convex hull of $P$ there exists an $\epsilon$-close point $x'$ (under the $p$-norm distance) that can be expressed as a convex combination of $O\left(\frac{p}{\epsilon^2} \right)$ many points of P.

Now, my question is that does the above result implies (or have some connection with) some kind of dimensionality reduction for the points in the convex hull of $P$. It seems intuitive to me (however I don't have a formal proof of it) - as for any  point $x$ inside the $P$ there is a point (say) $x'$ in a close neighborhood of $x$ which can be written as convex combination of constant many points of $P$, which in some sense dimensionality reduction of $x'$.

Pls let me know if I am able put my question clearly.

Thanks.


texts: I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge Proofs?


texts: What does $\#P\subseteq FP^{PPAD}$ imply?

texts:
We know $\#P\subseteq {PPAD}\implies PH\subseteq P^{{PPAD}}\subseteq P^{{NP}}$ and the polynomial hierarchy collapses ($FP^{PPAD}=PPAD$ following Emil Jerabek's comment).

Can $\#P\subseteq {PPAD}$ give a stronger collapse such as $\oplus P=UP=NP=coNP=PP$ or $NP=coNP=P^{PPAD}$?

What other consequences follow in $\#P\subseteq {PPAD}$ holds?


texts: On Defining Probabilistic/Nondeterministic Circuits

texts:
Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit.

The standard way of defining probabilistic/nondeterministic circuits is to augment the input with inputs. Let's assume that the circuit is still of size $f(n)$. What is $n$ in this case?

 $n$ is the number of deterministic inputs.
 $n$ is the number of deterministic PLUS probabilistic/nondeterministic inputs.

My confusion is that some references consider case 1, while others consider case 2.


texts: Quantum error correction and graph codes

texts:
I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-contained.

Given a labeling $L$ (a map where each vertex is is assigned 1 or 0) we define two operations on this:

$X(v,L)$: you flip labeling of vertex v that is if it was zero make it 1 if it was 1 make it 0.
$Z(v,L)$: you flip labeling of every neighbor of vertex v

Then diagonal distance is defined as length of minimal non-trivial sequence of operation so that $L$ is taken back to itself.

How is this exactly related to the quantum error correction property?


texts:
According to XOR Satisfiability Solver Module for DPLL Integration by Tero Laitinen, we need $2^{n-1}$ CNF clauses to convert an $n$ literal XOR-SAT clause if we do not want to increase the number of literals. So, I understand that the computational cost for converting an XOR-SAT expression into a strictly CNF $k$-SAT is exponential.

My question: What is the computational cost if I want to reverse the process? What is the computational cost of converting a CNF $k$-SAT expression into an XOR-SAT one? I assume the promise that in this case only the $k$-SAT expressions with equivalent XOR-SAT expressions are considered.


texts:
I was wondering if there is any literature on the following problem:

Maintain a set $S$ where each element is a function from $\mathbb{R}$ to $\mathbb{R}$ supporting the following operations:

Insert a new function $f$
Given $k$, query the minimum value of $f(k)$ where $f \in S$
Given $k$, remove an element $f$ where $f(k)$ is equal to the minimum value of $g(k)$ where $g \in S$

Are there restricted classes of functions where we can query and update in $o(|S|)$ time? Are there faster solutions when we restrict to operations (1) and (2)?


texts: Can MONOTONE WSAT be in solved in polynomial time?

texts: In the weighted monotone satisfiability problem (MONOTONE WSAT), the input is an n-variable MONOTONE CNF Boolean formula (when there is no a clause with a negated variable) and an integer k, and the problem is to decide whether there exists a satisfying assignment in which at most k of the variables are true. Can MONOTONE WSAT be in solved in polynomial time or is also NP-complete?


texts:
I seek an algorithm to optimise the process of inlinling. Is there such an algorithm, or set of such algorithms? Is there an efficient functional algorithm?

To be specific assume we have an Algol like language with nested functions. There are two relevant graphs: the static nesting graph, and the call graph. Interestingly I was unable to find any description or papers regarding the relation of these (though such must exist).

The primary goal is to inline all functions, with recursions expanded once (except for self calls), with minimal rescanning.

I must add here one of the key problems. When a function is inlined into another you glue in the code with parameters replaced by arguments. But that is not enough, you must also clone all the children of the function being inlined, and their descendants, and add them as children of the function into which you're inlining. If you use simple renaming this makes it exceedingly difficult to prevent infinite expansion of recursive calls, since any trail you're keeping won't refer to these cloned children. The cloned children also have parameter replacement performed (including specialisation of type variables).

The algorithm I am using works and always terminates but is neither optimal, nor does it meet the design goal: I found it necessary to add a constraint that prevents sibling recursions being expanded (only recursions to children are expanded).


texts: Visualizing the parse structure of a range concatenation grammar

texts:
The above is a good visualization of a derivation for a specific sentence in a context free language. You can find many more on Google Images by searching "context free grammar."

Let's consider the language $\{a^nb^nc^n : n>0\}$ for which no CFG exists but a RCG does. What does the visualization for the parse structure of the sentence "aaaaabbbbbccccc" look like? You can draw the visualization in MS Paint: I don't care how ugly it is as long as it isn't confusing. But you must submit a picture for an answer.


texts: Maximum shortest word accepted by pushdown automata

texts:
Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic pushdown automaton with $n$ states (holding alphabet size constant)?

I found an example where the shortest word is $\Omega(n^2)$ and suspect that this bound is tight, but have been unable to prove it. Everything I found online talking about shortest words is talking about finite or two-way automata only, not pushdown automata.

As an example, choose two large prime numbers $p$ and $q$, and two input symbols $a$ and $b$. Create an automaton with a cycle of length $p$ that reads an $a$ and pushes onto the stack, with a transition to a cycle of length $q$ that reads a $b$ and pops from the stack.

By placing the initial and accept states at appropriate places on the first and second cycle, you force the automaton to go through the first cycle $q-1$ times and the second cycle $p-1$ times, so that the maximum stack length is the same modulo $p$ and $q$, and thus the shortest word has length $\Omega(pq)$. Since the automaton has $p+q$ states, this means the shortest word is $\Omega(n^2)$.


texts: Sketch of Razborov's paper "On the method of approximations"

texts:
(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely through the "method of approximations", which has also been refined/simplified over the years by many other researchers.

Then in 1989 he seemed to somewhat dramatically switch thinking & directions with the paper "on the method of approximations" showing that, roughly, in the form considered, at best it can prove $\Omega(n^2)$ lower bounds on any circuit computing a hard function. In some key ways this also foreshadows his important paper on Natural Proofs (eg in showing a barrier-type theorem on a technique instead of working to improve lower bounds).

However the ideas in the paper seem hard to follow, & they seem to be rarely cited. There is not any mention of this idea in the later famous paper Natural Proofs which is also a broad survey of techniques in the field. So the 1989 paper refers to a key barrier, of which there is much prominent consideration of in TCS, but it's an apparently more obscure barrier. And it doesn't seem to be much tied in with the other well-known barriers, e.g., it doesn't seem like it fits in with the framework of Natural Proofs (which is meant to be a comprehensive-as-possible framework).

  Looking for a proof sketch/outline of why the method of approximations can do no better than $\Omega(n^2)$ lower bounds, ideally tying it in with other known barriers/results.

[The bigger motivation here is that [barrier-type/"no-go"] theorems can be notoriously tricky & the idea that maybe some basic change on the idea of the method of approximations not envisioned by Razborov could achieve new lower bounds. Of course, understood, this is "a long shot".]


texts: What is the name of this partition-indexed key-value data structure?

texts:
Consider a data structure that holds N elements having M partitions each holding N/M elements where M divides N. Each element has a key that satisfies an equivalence relation so as to index into one of the partitions.

Assuming this data structure is implemented within an array insertions are performed by computing the beginning partition location corresponding to the key for the element in question and a linear search is performed until a sentinel empty-value is found (or the end of the partition). Searches are performed analogously.

What is the name of the data structure described above? Does it have any advantage over a hash-table?


texts: Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q

texts:
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q.  Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in principle to calculate a rational point of infinite order on the curve.  However, it is unclear to me what properties are feasible to obtain computationally.

So I would like to know, given an elliptic curve in minimal Weierstrass form, and assuming the factors of the discriminant and other invariants are known (to sidestep possible issues getting into the complexity of factoring), can we efficiently calculate a point of infinite order on the curve?  What is the time complexity of currently known methods?

Does the answer change if we restrict to some special subsets of elliptic curves, such as Mordell curves $y^2 = x^3 + k$? Or even restricted further to Mordell curves with $|k|>1$ and square-free, where it is known that all points are of infinite order?


texts: Can the halting problem be solved probabilistically?

texts:
Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random source.
$
\def\pp{\mathbb{P}}
$
Can a probabilistic program solve the halting problem with probability more than $1/2$ for each input? That is, is there a probabilistic program $G$ such that $\pp( \ G(P,X) = H(P,X) \ ) > 1/2$ for every $P,X$? (Note that this in particular requires $G$ to halt with probability more than $1/2$.)
If $G$ always halts, and the random source is a fair coin, then this is impossible, because $G$ can only access the random source a certain number of times that is determined by the inputs (by weak Konig lemma), and so we can translate $G$ to an ordinary (non-probabilistic program) that solves the halting problem.
But my question is about the case where $G$ is not required to always halt, and the above argument fails. Also, in this case we can assume that the random source is a fair coin, since any other random source whose $k$-th output is a string drawn from a distribution computable from its previous outputs can be simulated using a fair coin with halting probability $1$.
Note that the strict bound of "$> 1/2$" is necessary, otherwise there is the obvious trivial solution. And note that I do not require the probability of success to be bounded away from $1/2$. The cases in this post do not cover my question, and I am unable to find any answer on the internet.


texts: Reference for checking primitive recursiveness

texts:
There is a theorem that states a function $f$ can be computed with a Turing-machine in time $O(g)$ with primitive recursive $g$ (of the length of input) iff $f$ is primitive recursive.

Where can I find a reference for this theorem? Wikipedia seems to state it but gives no references, nor does my books.


texts: A search problem and no algorithm for it

texts:
I would like to learn about the following search problem, in particular, which kind of algorithms exist for it.

Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight function $w(s)$. We start at some element $s_0 \in S$ and want to find an element with very low $w$-value.

How can we traverse this search space? For each element $s_1 \in S$, there exists a set of keys $K_S$, and we have some function $a : S \times K_S \rightarrow S$, that computes a new element $s_2 = a(s_1,k)$ for some $k \in K_S$.

We can evaluate the weight of some element $s$ only once it is given. But computing the weight is expensive, and should be minimalized. In order to find a good choice how to traverse throughout this graph, we are given a heuristic $h(s)$, that is supposed to compute a "good" key.

We know for small changes of the key (say, in Hamming distance), the weight of $w(s)$ does not change to much.

Question: Is such a problem known in theoretical computer science, and does there exist theory for it? In particular I am looking for algorithms for problems like these, and conditions on the heuristic $h$ to provide a "good" heuristic.

The description is deliberately vague, in order to allow for wider range of answers. I think many search algorithms do not apply, because they are too generous with search space evaluation. Maybe the problem is even too ill-posed to be accessible to CST tools.

Thank you very much!


texts:
It is $NP$-hard to decide if a $4$-regular planar graph can be $3$-colored.

Is an exact algorithm possible that under uniform distribution is in average polynomial time?


texts: Problems with efficient solution except for a small fraction of inputs

texts:
The halting problem for Turing machines is perhaps the canonical undecidable
  set. Nevertheless, we prove that there is an algorithm deciding almost
  all instances of it. The halting problem is therefore among the growing collection
  of those exhibiting the “black hole” phenomenon of complexity theory,
  by which the difficulty of an unfeasible or undecidable problem is confined
  to a very small region, a black hole, outside of which the problem is easy.

  [Joel David Hamkins and Alexei Miasnikov, "The halting problem is decidable on a set of asymptotic probability one", 2005]

Can anyone provide references to other “black holes” in complexity theory, or another place where this or related concepts are discussed?


texts: Take a natural quotient of context-free grammars

texts:
Fix a finite alphabet.
Let $\mathrm{CFG}$ be the set of context-free grammars on this alphabet, $\mathrm{CFL}$ the set of context-free languages, $\mathrm{UG}$ the set of unrestricted grammars and $\mathrm{REL}$ the set of recursively enumerable languages.
Then we almost have a commutative square $\require{AMScd}$
\begin{CD}
\mathrm{CFG}\times\mathrm{CFG} @>{?}>> \mathrm{UG}\\
@V{\mathrm{generate}\times\mathrm{generate}}VV @VV{\mathrm{generate}}V\\
\mathrm{CFL}\times\mathrm{CFL} @>{\mathrm{quotient}}>> \mathrm{REL}
\end{CD}
except one map. Is there a natural choice for the missing map?


texts: How can I find tight asymptotic bounds for this half-history recurrence relation?

texts:
The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$.

Fairly simple tree analysis shows that $T(n)\in\Omega(n^3)$ and $T(n)\in O(n^{\log_2{n}})$.

But I want to find $f(n)$ for which $T(n)\in\Theta(f(n))$, or at least tighter lower and upper bounds.


texts: Linear programming solution in one pass with ordered variables

texts:
I have a family of linear programming problems:  maximise $c' x$ subject to $A x\le b$, $x\ge0$. The elements of $A$, $b$, and $c$ are nonnegative integers, $c$ strictly positive. ($x$ should also be integral but I will worry about that later.)

It often happens in my application that the coefficients $A$ and $c$ are such that a simplified one-pass algorithm gives the optimal solution for every choice of $b$: the one-pass algorithm determines the elements $x_1,\dots,x_n$ in sequence, choosing each $x_j$ to be the largest possible value consistent with the already-determined values $x_1,\dots,x_{j-1}$. In simplex language, the sequence of entering variables is just $x_1$ to $x_n$, and it terminates after $n$ steps. This saves a lot of time compared to full-on simplex.

This algorithm works when the columns of $A$ and the elements of $c$ have been sorted from "cheap" to "expensive". A "cheap" variable is a column of $A$ with generally small values, for which the corresponding element of $c$ is large:  for that element of $x$ you get a lot of output with not very much demand on the constraint $b$. So the algorithm just says "do the easy stuff first."

My question is: what property of $A$ and $c$ would assure us that this simplified algorithm works for all $b$? My initial conjecture was that the nonzero elements of $A$ should be increasing in each row, but that is not correct.

Here are some examples, all with $c=(1,1,1)$:
$A_1=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 0\end{pmatrix}$,
$A_2=\begin{pmatrix} 0 & 0 & 1 \\ 3 & 0 & 2 \\ 0 & 3 & 2 \end{pmatrix}$,
$A_3=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}$,
$A_4=\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$.
For all of these, the sequential algorithm gives the optimal solution for all values of $b$ (by numerical experimentation). $A_3$ is the only one for which all permutations of columns also work. $A_1$ and $A_3$ are especially baffling, since $(1,1,3)$ looks more expensive than $(1,3,0)$ and $(1,1,1)$ more expensive than $(1,0,0)$.

I would be tremendously grateful for any pointers to the literature, for any problems like this, or any suggestions at all. There must have been other cases where some variables can be determined to be "cheaper" than others and can safely be done first. With all the work that has been done on linear programming over the years, it seems that something similar must have come up, but I haven't been able to find it.


texts:
Edited
I want to read more about subexponential hardness assumption, but I didn't find any good survey on this. I just took a look at Heavy-tailed distribution and Some properties of subexponential distributions but I didn't get a good picture of it.

  Question: What is the subexponential hardness assumption? Is it a weaker hardness assumption in comparison with discrete logarithm? Do you know any good survey or article on this?

I saw this subject in this paper:
 Adaptive hardness and composable security in the plain model from standard assumptions


texts: When is a problem specified on a TM contained in non-uniform classes such as P/poly?

texts:
In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, they mention that the input to the TM they encode in the tiling problem must be an integer $N$ in binary rather than unary, otherwise each instance will have a different input size and hence the problem would "trivially be in P/poly" rather than NP. Hence instead they must prove the problem is NEXP-complete rather than NP-complete.

While I understand why the proof with a binary input gives NEXP-completeness, I don't understand why if $N$ is input in unary then the problem is trivially hard for P/poly? Unfortunately the model of computation they specify is in terms of TMs rather than circuits so it's not clear to me how this relates to non-uniform circuit families.


texts: Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? // Quantum automata

texts:
While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More details are sufficiently summarized in this Wikipedia article if requested.

So far, I found a proof in L19 (p.5, prop.1) which shows that, for any MO-1QFA and any input string w, there is an MM-1QFA accepting w with the same probability (only bounded error considered here). Therefore, $\mathcal{L}$(MO-1QFA) = $\mathcal{L}$(MM-1QFA). However, I have not been able to find a proof showing that $\mathcal{L}$(MM-1QFA) > $\mathcal{L}$(MO-1QFA) indeed.

There are informal arguments by Brodsky and Pippenger BP18 (p.9, start of sec.4), just saying that this is because MM-1QFA are allowed to terminate before reading the entire input string (due to their measurements after every transition). Furthermore, Ambainis and Freivalds AF98 (end of p.3) say that "any finite language can be recognized by MM-1QFA, but no finite non-empty language can be recognized by MO-1QFA".

Though these claims seemed reasonable to me at first, I have failed to construct an example (let alone an idea for a general proof) that would make them clear to me. One issue is that I do not see, how a MM-1QFA would know "when to stop".

Based on all this, I would be glad if someone could help me to see why MM-1QFA are actually strictly more powerful than MO-1QFA.


texts: Pair of vertex disjoint cycles in a directed graph

texts: What is the fastest known deterministic algorithm that can recognize directed graphs with a pair of vertex disjoint cycles? I know graphs with min outdegree three always have such a pair (Thomassen'83), but even so I cannot find an efficient algorithm in the general case. Does anyone know a reference for this?


texts: Explanation of definition of normalizing: 9.1.12 in Terese "Term Rewriting Systems"?

texts:
A strategy for a rewriting system is a sub-rewriting system with the same objects and same normal forms.

Definition (from Terese "Term Rewriting Systems").  Let N be a superset of the normal forms of a rewriting system $\to$.  A strategy S for $\to$ is normalizing if the restriction of S (as a relation) to steps which do not have their sources in N is terminating.

I understand that the authors want a more general notion of normalizing such as the strategy which finds a (weak) head normal form.  However, take N to be be exactly the set of normal forms.  Then the definition should express that the strategy always finds a normal form provided one exists.  I am having trouble bridging the gap here...  It seems that N should have to also include the terms which do not have a normal form.


texts: Asymptotic complexity of CDCL SAT solver that only selects negative literals

texts:
If a CDCL SAT solver only selects negative literals as decision literals (but can set positive literals through unit propogation) but has a perfect heuristic for determining which literal to select next, what kind of claims can be made about its running time?

Is it necessarily exponential on some infinite class of satisfiable instances?


texts: State of research on SHA-1 Collision Attacks

texts:
SHA-1 security has been discussed since an algorithm for finding collisions was  first published at CRYPTO 2004 and has been subsequently improved.

Wikipedia lists a couple of references, however it seems the latest research published (and later withdrawn) on this subject was in 2009 (Cameron McDonald, Philip Hawkes and Josef Pieprzyk "Differential Path for SHA-1 with complexity O(2^52)").

Since then, has any significant progress been made on reducing the effort for a hash collision attack on SHA-1?

A link to specific research accompanied with a short summary would be appreciated.


texts: Extensional type theory and function extensionality

texts:
Is the principle of function extensionality
$ (\forall x. f(x) = g(x)) \implies f = g$, derivable from ETT?
Most notably is this derivable in Agda with axiom K?


texts: Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

texts:
Complexity Zoology by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X}$ — but does not give a reference for this result.  Why does this hold?  Or where can a proof be found?

This question is partly motivated by my answer to the question “What is known about multi-prover interactive proofs with short messages?” by Joe Fitzsimons.

I posted this question on math.stackexchange.com on October 2, but I did not receive any answer and deleted the question on math following this post on meta.math.


texts: Problem with bitwise AND/OR on binary strings

texts:
Let $W = \{s_1, s_2, \ldots, s_n\}$ be a set of $m$-length binary strings and let $\land$ and $\lor$ be the binary operators of bitwise AND and OR. A bitwise formula $\phi$ is composed of operands in $A \subseteq W$, operators in $ \{(,),\land, \lor\}$, and computes a $m$-length binary string $x = \phi$. Then we say that $x$ can be expressed by $W$.

We say a set $W$ is expressive complete if for any $x \in W$, $x$ can be expressed by a bitwise formula using operands in $W \setminus \{x\}$.

  Question: Given $W$, determine the minimum number $n$ of $m$-length binary strings that need to be added to $W$ to make it expressive complete.

Example 1: Let $m = 2$ and $W = \{01, 10\}$. Then then both 00 and 11 need to be added to $W$ to make it expressive complete. Thus, $n = 2$.

Example 2: Let $m = 3$ and $W = \{001, 010, 100, 011, 110, 101\}$. $W$ is already expressive complete, so $n = 0$.

A Trivial Upperbound: $2m$ is an upperbound, because for vector space $\{0,1\}^m$, $\{ 0...01, 0...010,..., 10...0\}$ is a base and $\{1...10, 1...101,...,01...1\}$ is also a base. After adding these two bases to $W$, $W$ is certainly expressive complete.

Related result (might be helpful for the question) proved:
$x$ could be expressed from $A\subseteq W$ if and only if $\bigwedge_{i \in \mathsf{Zero}(x)} {t_i} = x$. Where $\mathsf{Zero}(x)$ is the set of 0 valued indicies of $x$. And $t_i$ is the $\lor$ opreated on all the binary strings in $A$ whose $i^{th}$ bit is 0.

Thank you very much for your comments and answers. :)


texts: Implications of an $\tilde{O}(n^{1.5})$ 3XORSUM algorithm

texts:
Assume one had a (randomised or deterministic) algorithm with asymptotic complexity $\tilde{O}(n^{1.5})$ for the problem of finding $x,y,z\in L$ where $L$ is a list with $n$ binary vectors of dimension $d$ so that $x\oplus y=z$ holds (assuming a solution exists in the list).

If you like you can assume $n$ is exponential in $d$, and that the vectors in the list are selected uniformly at random, meaning that one would need $n\geq c ~2^{d/3}$ or some positive constant $c$ before a solution is likely to exist.

What would be the implications of such a result?

Recently there have been sub $O(n^2)$ algorithms for the integer 3SUM problem but they are still not of complexity $O(n^{2-\varepsilon})$ for $\varepsilon>0.$

There is some discussion of the 3SUM problem in the answers to the question here