texts: What do we call a type system where any term of any type ultimately parses down to $*:\mathbf{1}$?

texts:
If a type system allows inductive types (as in e.g. Coq) then we can coin new primitive constants that inhabit types. For example $0:\mathbb{N}$ is constructed when defining $\mathbb{N}$ and does not reduce to anything else.
But if we are in a pure Martin-Löf type theory then any inhabitant of any type ultimately refers to $*:\mathbf{1}$. Is there a name for this property (akin to normalization/canonicity)?


texts: Modern tools deterministic communication applications

texts:
Partition number, Fooling-set method along with rank method provide important tools to identify deterministic communication complexity of a function. These techniques were identified some decades before. What other modern techniques have been invented to identify deterministic complexity of a function? Which functions have these been utilized to solve?

Could tools from information theory, pattern matrix be useful in saying anything about deterministic complexity both in single user, multi user situations?


texts: Where to find the latest book releases on theoretical computer science?

texts:
I was wondering if there is an online source where I can find the latest book releases on theoretical computer science issues?

And I mean quality books and papers on new and upcoming issues from famous authors. The amazon and other mainstream pages seem not to tend to those insider tip books I am searching for. Although I know there are famous best books out there as well.

They can also be written in a not so scientific and educational way as well. The specification is, so to say, to present the knowledge in the best known way.

You are also invited to comment this question with titles of the latest or "best" books on algorithms which you would recommend (I am looking for them at the moment).

I hope this question belongs to this board somehow - sorry if not.


texts: Why are these two definitions of PPAD equivalent?

texts:
The complexity class PPAD is usually defined by stating that End-Of-The-Line is PPAD-complete.

  End-Of-The-Line is a search problem. The input consists of a directed graph in which each node has in-degree and out-degree at most 1. The graph is given by a polynomial-time computable function $f(x)$ that returns the predecessor and successor of $x$. In addition, one is given a node $v$ with a successor but no predecessor. Find a node $t\ne v$ that has no successor or no predecessor.

Recently, I heard a different definition of PPAD. As far as I recall, it was based on the following problem.

  A directed graph (again specified by a polynomial-time computable function) and a node whose in-degree is not equal its out-degree is given. Find another node with this property.

Clearly, End-Of-The-Line is a special case of the latter problem but is the latter problem really more difficult to solve? My question is this:

  Are both problems complete for the same complexity class PPAD? If yes, why? If not, what is the complexity class resulting from the second problem?


texts: Completeness of the extension of first order logic with least fixed point order operator

texts: Is there any result about the extension of first order logic with least fixed point operator, being complete (as logic in general on infinite structures too) or not? In other words does the Goedel completeness theorem of first order logic extent to such FO-LFP logic ?


texts: Major unsolved problems in distributed systems?

texts:
Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain.

Something like membership protocols, data consistency?


texts: Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D

texts:
I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if you know anyone who could answer this question, please send it to them. I really need the solution as I have been trying to figure it out for quite long time :| Many thanks!

As can be seen in the picture, I have more than 200 lines in 3D. They consist of 3 different groups of lines, and the common property of the lines in each group is that they pass close to the same point. However, in this problem, we don't know which line belongs to which group. What is given are only the 3D coordinates $(x,y,z)$ of the 2 ends of all the lines.

My job is to find an algorithm to match/fit/register a triangle (a rigid body) to those lines such that the sum of the sum of distances between 3 vertexes of the triangle and their corresponding lines is minimized. In some cases, one vertex may be the closest point in a group, but the other vertexes would be dragged further away from their corresponding lines (because they are in a rigid body), thus this sum will not be minimal. What I need is the best positions of the 3 vertexes (the best fit of the triangle) to minimize the global sum.

In conclusion, given more than 200 sets of $(x_1,y_1,z_1,x_2,y_2,z_2)$ (which are coordinates of 2 ends of a line), I need to find the best positions of 3 vertexes of a triangle to fit in those lines (given the relative distance between the 3 vertexes).

Without the rigid-body condition, I have successfully determined the positions of the 3 independent points using the Expectation-Maximization (EM) clustering algorithm. However, sometimes 2 or 3 points are assigned to the same position. Then, I realized I had forgotten the "rigid-body" condition. With this added condition, this error will not occur. In the EM algorithm, I can derive the formula for each repositioning step for each point. But when it comes to a rigid-body, I don't know how to figure out the translation and rotation matrix to fit the triangle to the lines.

Thank you for reading this post. Your help would be greatly appreciated!


texts: Ordered routing problem which is NP-hard

texts:
All the np-hard routing problems I know are of the form, minimize some quantity while visiting the verticies in an unordered way.

Are there problems which are still np-hard, if one has to visit the vertices in a given odering?

The only problem I can think of which partially falls into this is the
"Vehicle routing problem with time windows problem" where the time window kind of dictates an order.


texts: Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

texts: If it is unknown, are there reasons to believe that they might not be equal?


texts: NP-Hardness of 4-cycle packing problem in complete bipartite digraph?

texts:
A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a complete bipartite graph.

Given a directed complete bipartite graph, we are asked to find the largest set of edge-disjoint 4-cycles. Note that these 4-cycles can share node(s).

Is this problem NP-Hard? I tried to reduce from 2P2N-3SAT to this problem, but failed. On the other hand, I found no polynomial algorithm could solve it  optimally.


texts: Complexity of Edge Coloring Regular Graphs With Large Degrees

texts:
There is an interesting series of papers on edge colorability / $1$-factorization of regular graphs with large degrees, which over the years have shown better and better lower bounds for the degree $\Delta$ depending on $n$, from which a regular graph guarantees an edge coloring with $\Delta$ colors / a $1$-factorization.
Finally, in 2016, Csaba et al. showed the optimal bound of $\Delta \geq 2 \lceil n / 4 \rceil - 1$ for sufficiently large $n$, which is is in line with Dirac's Conjecture.
These results show that the decision problem concerning the edge colorability with $\Delta$ colors, or the question of the existence of a $1$-factorization, is in P, if the input is restricted to the respective regular graphs with large degrees meeting the bounds.
Question: However, when looking at the proofs, I ask myself if one of the proofs also provides a polynomial-time construction scheme for an edge coloring / $1$-factorization solving the respective search problem?
Relevant literature:

Chetwynd, A. G., & Hilton, A. J. (1985). Regular graphs of high degree are 1‐factorizable. Proceedings of the London Mathematical Society, 3(2), 193-206.
Chetwynd, A. G., & Hilton, A. J. (1989). 1-factorizing regular graphs of high degree—an improved bound. Discrete Mathematics, 75(1-3), 103-112.
Perkovic, L., & Reed, B. (1997). Edge coloring regular graphs of high degree. Discrete Mathematics, 165, 567-578.
De Simone, C., & Galluccio, A. (2007). Edge-colouring of regular graphs of large degree. Theoretical computer science, 389(1-2), 91-99.
Csaba, B., Kühn, D., Lo, A., Osthus, D., & Treglown, A. (2016). Proof of the 1-factorization and Hamilton decomposition conjectures (Vol. 244, No. 1154). American Mathematical Society.


texts:
Robin Gandy was a student of Alan Turing.

Gandy did an analysis of Babbage's Analytical Engine (see 'Gandy
- The Confluence of Ideas in 1936' quoted in 'Herken, Rolf - The Universal Turing Machine—A Half-Century Survey. Springer Verlag') - and said it did (cf. p. 52–53):

The arithmetic functions +, −, ×, where − indicates "proper" subtraction x − y = 0 if y ≥ x.
Any sequence of operations is an operation.
Iteration of an operation (repeating n times an operation P).
Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
Conditional transfer (i.e., conditional "goto").

Then he states

  the functions which can be calculated by (1), (2), and (4) are precisely those which are Turing computable.

(p. 53).

Then he states:

  … the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized…

Gandy p. 55

I'm assessing the scope of Gandy's claim here. (Whether it is right or wrong). He seems to be stating that although Babbage seems to have stumbled onto a notion of Turing Completeness (can express any program using (1), (2) and (4) - he didn't have a notion of a Computable Function. (Perhaps Gandy was saying that since the work of Babbage was prior to the work of Hilbert and Godel, he didn't have the mathematical tools to tie down the definition of a universal computing machine.)

My question is: Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?


texts: Motivating Talk on Foundations of Cryptography

texts:
This question is in the same vein as inspirational talk for final year high school pupils. My Ph.D. advisor asked me to give an inspirational talk for new M.Sc. students. The subject is foundations of cryptography, which is best illustrated by Goldreich's book. The talk will take about one hour, and I want to familiarize the students to the main constructs (like one-way functions/permutations, pseudor-random generators, zero-knowledge proofs, encryption/signature schemes, etc.), and solved and unsolved problems in the field.

I want to keep the talk very motivating.
The main problem is two-fold:

Foundations of cryptography needs a very good understanding of the computational-complexity theory. Alas, the M.Sc. students have not passed any course related to this theory.
I need to present some problems as possible topics for an M.Sc. thesis. While there are a lot of unsolved problems in the field, most of them are too hard for an M.Sc. student.

Suggestions are most welcome. In addition, I'm very interested in pointers to similar talks.

Edit: I found the list of Goldreich's students extremely inspiring. I'll be searching for other such lists, but you can help me if you know any similar lists. See also: Demystifying the Master Thesis and Research in General: The Story of Some Master Theses.


texts: Computing the existence of a path in a code execution graph

texts:
I have a need for an algorithm which I can express as a reachability problem in a graph.

Note that I'd appreciate any advices with respect to better wording this question. Also please tell me if this question does not fit this site (I considered posting it to "Computer Science" instead).

Problem Statement

Consider an directed, connected, possibly cyclic graph $G=(V,E)$.

Consider also a finite set of "indicators" $I$, of a finite size. They are numbered $I_0 .. I_n$.

Each indicator $I_i$ can take an integer value in the range $[0..v(i)]$.

Each vertex can be labelled with one or more "assignations" of the form $I_i := v$, with $v \in [0..v(i)]$.

Exactly one vertex $V_0 \in V$ is distinguished as the "graph entry".

It is also considered that $V_0$ is labelled by $I_j := 0, \forall j \in [0..n]$ (i.e. the "value" of all indicators is $0$ at the graph entry).

Some vertices are such that all outbound edges from them are labelled by a "guard" of the form $I_k = v_p$, for a fixed value $k$ and all possible $p \in [0..m(k)]$ (i.e. there are "switches" at some vertexes where an edge is "chosen" based on the "current" value of an indicator).

We define (somewhat informally) a "valid" path in the graph as:

being finite,
respecting the topology constraints in the graph,
and being such that, if is is crossed from its beginning to its end, while collecting the "current" (i.e., latest encountered) value of indicators in the process, then the equality associated to each guard is verified.

Informally, the graph represents all possible execution flows in a piece of code, with indicator variables being set and branching decisions being taken with respect to those indicators.

Now my problem is the following: given a vertex $V_q \in V$, does a valid path (in the sense defined above) exists from $V_0$ to $V_q$?

Note that I only need an algorithm efficiently answering if such path exists; I do not need it to construct one.

What I Did so Far

Empirically, I had quite good results so far with a brute-force execution simulation strategy enumerating all possible paths (with some memoization to limit memory consumption and ensure termination in the presence of cycles). But some larger graphs are proving a challenge, since most probably my current enumeration approach is of an exponential complexity.

Mostly I'd like to express my problem in a domain where I could benefit from existing complexity proofs and (hopefully!) solvers. I tried my hands at classical graph theory problems, considered SAT and Petri Nets too, but did not see a match so far. I also tried some classic and more recent data flow algorithms at first, but they fail short since I need an exact result.


texts: What are the theoretical limits of the Stratego Programming Language?

texts:
Stratego is a programming transformation language/Rewriting DSL.

Anthony Sloane has done some work doing an implementation that runs on Scala.

What are the theoretical limits of Stratego as a functional language? (regardless of implementation). Could one write an applicative order ycombinator in Stratego?


texts:
I don't know if CS theory is the best place for this, sorry if it's not.

I'm not a computer scientist so I don't know complex maths, but I have a theoretical problem in an application I'm working on that I can't wrap my head around. I would appreciate any help.

I need to find the best or correct string to fit between two other strings.

Given the strings strA and strB the function should analyse a database and return a string that looks like:

strA strC strD strE strB The number of strings in between can vary in number.

I have a database in place that looks something like this:

strA strC
strA strD
strA strB

strB strA
strB strC

strC strA

This basically says that in the final string strC can come after strB but strD cannot come after strB.

I also have a secondary database which describes which strings can come before which strings. So for example...

strA strC
strA strD
strA strB

strB strA
strB strC

strC strA

But this database states that strC can come before strB, but not strD.

I have a function which, only given the beginning string can find all the strings which would fit after it in the correct order. But I need to also include an ending string and have it find the correct path between the start and finish.

I've thought about it over and over again and I don't even know where to start with this. I hope my explanation is not too convoluted. I would greatly appreciate any ideas.


texts: Graph recovery from pairwise-common neighborhoods

texts:
Define the common neighborhood of two vertices $u$ and $v$ of a simple undirected graph as the set $N(u,v)=N(u)\cap N(v)$. For a simple bipartite graph $G=(U,V,E)$, define the pairwise-common neighborhoods set as $\{N(u_1,u_2):u_1\not=u_2\in U∧N(u_1,u_2)≠∅\}$.

Is it possible to recover a bipartite $G$ if given only its pairwise-common neighborhoods set? Assume $G$ connected and degree greater or equal than 2 for all vertices.
Is there an efficient algorithm that constructs some bipartite graph with a given pairwise-common neighborhoods set, or halts if one does not exist?


texts: NP Complete Problems - Book References - Reductions and Use Cases?

texts:
What are the best self contained Books that mainly serve the purpose of:

Demonstrating NP Complete Reductions (other than Garey and Johnson, which mainly lists the problems as NP complete, and provided pointers).
Practical application of NP Complete Problems and use cases in industry.


texts: On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$

texts:
I am trying to prove the following

  Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$

where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group of prime order $p$ and $r∈ \mathbb{Z}^*_p -\{0\} $ and $r \neq a$.

I don't have a clear (far from elegant) proof that, if there exists an algorithm $\mathcal{A}$ that can solve this, then we can solve *some*  hard problem..

The best sketch I can think of is reducing this to a the Okamato's Conference Key Sharing Scheme. However, again, I don't have a clear proof idea here...

Also, I argue, the adversary can submit the following,$(g^a)^t, (g^{ab})^t$,  $t∈_R Z$, however in that case, the adversary has no clue about the value of the exponent


texts:
We all know showing $P\ne NP$ has barriers. We all have studied these barriers because we believe $P\ne NP$.

However assume $P=NP$ and there are wise people who believe that possibility exists. If this is indeed the case then the very fact that we have not seen any good algorithms indicates there might be barriers in this alternate universe as well. Provability of $P\ne NP$ is barrier ridden and we do not know for sure $P\ne NP$ is the truth. We do not know for sure $P= NP$ is the truth either and so is provability of $P=NP$ also barrier ridden?


texts:
Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative entries in $C$. My goal is to flip one bit in $A$ from $0$ to $1$ to create a new matrix $B$ such that $C' = B B^\top$ is the BMM result and if $c'$ is the number of non-negative entries in $C'$, we wish to maximize $c' - c$. In other words, by flipping one entry, we wish to $\it maximize$ the incremental output generated by BMM of the resulting matrix. Has this problem been studied in literature and if yes, is this problem as hard as BMM itself?
I am also interested in the decremental analogue of the problem where we can flip one bit in A from $1$ to $0$ to maximize the decrease in the output between BMM of the original matrix with its transpose and the new matrix with its transpose.


texts: Perfect hashing family variation - injectivity on $r$ disjoint sets

texts:
We denote by $[t]$ the set $\{1,2,\ldots,t\}$.

A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $h_S$ is injective on $S$.

There are known (deterministic) builds of such family of size $O(e^{k+log^2k}log n)$, while there is a $\Omega(e^k \cdot \frac{log n}{\sqrt k})$ lower bound , which is almost tight.

We define an extension of such families as follows:

A family of functions $\mathcal F=\{f_i:[n]\to [k]\}$ is a $(n,r,k)$-perfect hashing family if for every set of sets, $\mathcal S=\{S_1,S_2,\ldots,S_r\subseteq [n]\}$, such that $$|\mathcal S|=r,\ \forall i:|S_i|=k,\ \forall j\neq i:S_i\cap S_j = \emptyset$$

There exists a function $f\in \mathcal F$ which is injective on all $S_i\in \mathcal S$.

That is, every set of $r$ disjoint sets of indices of size $k$ there exists a single function which is injective on all of them.

  What is the smallest $(n,r,k)$-perfect hashing family we can build?

Specifially, I'm mainly interested in the $r=2$ case, but this might be useful to others for general $r$ values.


texts: Approximating set cover when it is known that an exact set cover exists

texts:
Suppose $U = \{1, 2, \cdots, n\}$ is a universe and $\mathcal S = \{S_1, S_2, \cdots, S_m\}$ is a collection of sets such that each set contains exactly $c$ elements, where $c$ is a constant.

In this case, a $c$-approximation is easy. It is also possible to improve that to $\ln c + 1$-approximation.

My question is following:
Suppose along with this special set cover instance, you are told that an exact cover (of size $n/c$) exists. Is it possible to get a better approximation factor? What is known about hardness of approximation in this case?


texts: Hardness of approximation - additive error

texts:
There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for vertex cover is optimal assuming UGC).  This also includes well understood approximation complexity classes such as APX, PTAS and so on.

What is known when additive error is to be considered?  A literature search shows a few upper bound type results, most notably for bin packing (see for example http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps), but is there a more comprehensive complexity class classification or is there a reason why it is not so interesting or relevant?

As a further comment, for bin packing, for example, there is as far as I know no theoretical reason why a poly time algorithm which is always within an additive distance from optimal of 1 couldn't be found (although I stand to be corrected).  Would such an algorithm collapse any complexity classes or have any other significant theoretical knock-on effect?

EDIT: The key phrase I didn't use is "asymptotic approximation class" (thanks Oleksandr). It seems that there is some work in this area but it hasn't got to the same stage of maturity yet as the theory of classic approximation classes.


texts: Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1

texts:
Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\mathbb{Z}$).  Is this problem NP-hard?

It is clearly in NP as you can give two vectors as witnesses.

Equivalently: Given $M$, is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

Equivalently: Given $n$ vectors $X=\{x_1,\dots,x_n\}$ over $\{0,1\}^m$, are there two different subsets $A,B \subseteq X$ such that $\sum_{x \in A} x = \sum_{x \in B} x$?


texts:
Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs.  I'm excluding results such as, say, Savitch's theorem; a good entry would focus on a single problem and its bounds.  An example would be :
"Let T and S be the running time and space bound of any SAT algorithm. Then we must have T⋅S≥n2cos(π/7)−o(1) infinitely often." (Given in [1] by Ryan Williams.)
or
"SAT cannot be solved simultaneously in n1+0(1) time and
n1-ε space for any ε>0 on general
random-access nondeterministic Turing machines." (Lance Fortnow in 10.1109/CCC.1997.612300)
Further, I'm including definitions of natural space-time tradeoff complexity classes (excluding circuit classes).


texts:
Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among deterministic polynomial class problems (P, FP, BPP).

For instance, solving a system of linear equations in n variables (by Gaussian elimination) has time complexity $C_s=O(n^3)$. However, verifying a solution obviously requires only $C_v=O(n^2)$.
Similarly for linear programming problems: $C_s=O(n^{3.5})$ for solving, $C_v=O(n^2)$ for verifying.

What are other polynomial problems with this property with respect to the best known solving and verifying algorithms? Are there any problems with much larger gap, e.g. $C_s=\Theta(C_v^2)$ or more?

More generally, which problems have the best known polynomial-time algorithms with complexity $\Theta(n^6)$ or more, where $n$ is the input size?


texts: Is MALL + unrestricted recursive types Turing-complete?

texts:
If you look at the recursive combinators in the untyped lambda-calculus, such as the Y combinator or the omega combinator:
$$
\begin{array}{lcl}
\omega & = & (\lambda x.\,x\;x)\;(\lambda x.\,x\;x)\\
Y & = & \lambda f.\,(\lambda x.\,f\;(x\;x))\; (\lambda x.\,f\;(x\;x)) \\
\end{array}
$$
It's clear that all of these combinators end up duplicating a variable somewhere in their definition.

Furthermore, all of these combinators are typeable in the simply-typed lambda calculus, if you extend it with recursive types $\mu\alpha.\,A(\alpha)$, where $\alpha$ is allowed to occur negatively in the recursive type.

However, what happens if you add full (negative-occurence) recursive types to the exponential-free fragment of linear logic (i.e., MALL)?

Then you don't have an exponential $!A$ to give you contraction. You can encode the type of exponentials using something like
$$
!A \triangleq \mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)
$$
but I don't see how to define the introduction rule for it, since that seems to require a fixed point combinator to define. And I was trying to define exponentials, to get contraction, to get a fixed-point combinator!

Is it the case that MALL plus unrestricted recursive types is still normalizing‽


texts: Complexity of $\{0,\pm1\}$ determinant in sparse cases?

texts:
If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?

Assume that the matrix is given in form a list where $1,-1$ locations are and so the presentation is only $O(n)$ sized.


texts: Does $NP=PP$ collapse the counting hierarchy?

texts:
Suppose $NP=PP$. Then a simple argument shows that $PH^{PP}=NP$. Can we go one step further and get $PP^{PP}=NP$? The simple argument is

Theorem If $NP=PP$ then $PH^{PP}=NP$.

Proof $PP$ is closed under complement (due to Gill), so $NP=coNP=PH$. Take any level of $PH^{PP}$: then $\Sigma_i^{P^{PP}}=\Sigma_i^{P^{NP}}=\Sigma_{i+1}^{P}=NP$. $\square$

One plausible-looking way to get to the desired consequence is by observing that in this world, the interactive proof protocol for the $\textsf{Permanent}$ has been derandomized and de-Merlinized to the point where one message to Arthur has perfect completeness and soundness (as $NP=P^{\#P}$ under the hypothesis). If you can exploit this fact and compute the Permanent in some class that's low for $PP$, such as $UP$ or $BQP$ or $SPP$, we're done. That would give us $NP=PP\implies PP=UP$ (for example), which would immediately give $PP^{PP}=PP^{UP}=PP=NP$.

(This came up in my thesis, where I investigate the hypothesis $QMA=PP$, and it also came up when trying to fix Scott Aaronson's broken theorem $PP\subset BQP_{/qpoly}\implies CH=PP=QMA$, Theorem 5 in Oracles are Subtle but not Malicious).


texts: Are there analogues of Specker sequences for other complexity classes?

texts:
Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \mapsto a_i$ is recursive and (2) there exists a recursive function $\xi$ such that, for all $j,k,n \in \mathbb{N}$, if $j,k<\xi(n)$, then $\vert a_j - a_k \vert < n^{-1}$.

Specker (1949) showed that there exist sequences of recursive reals that converge to a nonrecursive real.

Given any complexity class $\mathsf{C}$, however, we can define a notion of $\mathsf{C}$-computable real number by uniformly replacing 'recursive function' in the definition above with 'function in $\mathsf{C}$'.

Do analogues of Specker's result hold for the most obvious such notions? I.e., do there exist sequences of $\mathsf{C}$-computable reals that converge to non-$\mathsf{C}$-computable limits when $\mathsf{C} = \mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXP}$, etc.?

I have not been able to find any discussions of this question in the literature; if some exist, I'd be very grateful for any pointers. I don't think there's any trivial way to generalize Specker's proof since it relies on the existence of a recursive enumeration of a nonrecursive set.


texts: Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST

texts: I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum spanning tree). Also if anyone of you can post some lecture note or paper links so that i can study these graphs.


texts: What's the "real" reason that IP=PSPACE is non-relativizing?

texts:
IP=PSPACE is listed as the canonical example of a non-relativizing result, and the proof for this is that there exists an oracle $O$ such that ${\sf coNP}^O \not\subseteq {\sf IP}^O$, while ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ for all oracles $O$.

However, I've seen only a few people give a "direct" explanation for why the ${\sf IP} = {\sf PSPACE}$ result does not relativize, and the usual answer is "arithmetization". Upon inspection of the proof of IP=PSPACE, that answer isn't false, but it isn't satisfactory to me. It seems that the "real" reason traces itself back to the proof that the problem TQBF - true quantified boolean formula - is complete for PSPACE; to prove that, you need to show that you can encode configurations of a PSPACE machine in a polynomial-sized format, and (this seems to be the non-relativizing part) you can encode "correct" transitions between configurations in a polynomial-sized boolean formula - this uses a Cook-Levin-style step.

The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines, and the step where TQBF is shown to be complete for PSPACE is where this poking around happens - and the arithmetization step could've only happened because you had an explicit boolean formula to arithmetize.

This appears to me to be the fundamental reason that IP=PSPACE is non-relativizing; and the folklore mantra that arithmetization techniques don't relativize seems to be a byproduct of that: the only way to arithmetize something is if you have a boolean formula that encodes something about TMs in the first place!

Is there something I'm missing? As a subquestion - does this mean all results that use TQBF in some way also do not relativize?


texts: Mathematical implications of complexity theory conjectures outside TCS

texts:
Do you know interesting consequences of (standard) conjectures in complexity theory in other fields of mathematics (i.e. outside of theoretical computer science)?

I would prefer answers where:

the complexity theory conjecture is as general and standard as possible; I am ok with consequences of the hardness of specific problems too, but it would be nice if the problems are widely believed to be hard (or at least have been studied in more than a couple of papers)
the implication is a statement that is not known to be true unconditionally, or other known proofs are considerably more difficult
the more surprising the connection the better; in particular, the implication should not be a statement explicitly about algorithms

"If pigs could fly, horses would sing" type of connections are ok, too, as long as the flying pigs come from complexity theory, and the singing horses from some field of math outside of computer science.

This question is in some sense "the converse" of a question we had about surprising uses of mathematics in computer science. Dick Lipton had a blog post exactly along these lines: he writes about consequences of the conjecture that factoring has large circuit complexity. The consequences are that certain diophantine equations have no solutions, a kind of statement that can very hard to prove unconditionally. The post is based on work with Dan Boneh, but I cannot locate a paper.

EDIT: As Josh Grochow notes in the comments, his question about applications of TCS to classical math is closely related. My question is, on one hand, more permissive, because I do not insist on the "classical math" restriction. I think the more important difference is that I insist on a proven implication from a complexity conjecture to a statement in a field of math outside TCS. Most of the answers to Josh's question are not of this type, but instead give techniques and concepts useful in classical math that were developed or inspired by TCS. Nevertheless, at least one answer to Josh's question is a perfect answer to my question: Michael Freedman's paper which is motivated by a question identical to mine, and proves a theorem in knot theory, conditional on $\mathsf{P}^{\#P} \ne \mathsf{NP}$. He argues the theorem seems out of reach of current techniques in knot theory. By Toda's theorem, if $\mathsf{P}^{\#P} = \mathsf{NP}$ then the polynomial hierarchy collapses, so the assumption is quite plausible. I am interested in other similar results.


texts: how is time complexity defined in computational learning theory

texts:
In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$.

Now how is the hypothesis output? In the sense, should the learner write down the truth table/ circuit description? Is the time in describing the hypothesis included in $t$? Or does one only worry about how long it takes to evaluate $h$? If the output is a truth table, can't every hypothesis be evaluated in time $1$ already?


texts: Homoiconic languages which are not Turing complete

texts:
Does there exist a programming language which is homoiconic (in the sense that any code can be represented as a data structure, can be altered, and can be run after being altered) but not Turing complete?

For instance, one may avoid "for loops" by preventing data (which could represent code) from being copied.


texts: How are lower bounds for computational complexity proved?

texts:
As the title says, how are lower bounds for computational complexity proved?  I'm interested why it is possible to say that a certain algorithm cannot run in faster time than some lower bound.

General-level explanations and proofs are both welcome. I assume that proofs can be very different for different classes of problems, but I'm looking for just few examples to have a good grab on the basics.


texts: Information theory and Tsfasman-Manin's problem

texts:
Yuri Manin recently posted an interesting paper on computability of boundary regions of distance-rate trade-offs for error correction codes.
http://arxiv.org/PS_cache/arxiv/pdf/1107/1107.4246v1.pdf

I am curious if information theory provides any clues to this problem in asymptotic coding theory?


texts: What is the best place to get BibTeX entries for computer science articles ?

texts: Other than ACM, IEEE computer Society, Google Scholar which is the best site to get bibtex entries for computer science related articles ?


texts: Is this node permutation optimization NP-Hard?

texts:
Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in the permutation $\pi$.
Is the following optimization problem NP-hard?

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

Motivation: The following algorithm lists all triangles in the input graph in linear memory and in time $O(\sum_\limits{u\in V} ~\left| \text{succ}_{\pi}(u) \right|^2+m+n)$ where $m$ is the number of edges and $n$ is the number of nodes.

For each node u:
  For each pair of successors v,w of node u:
    If edge v,w is in the input undirected graph:
      output triangle u,v,w

Implementation details: the graph should be stored in a CSR-like format and, in addition, the edges should be put in a hashtable.
Finding the ordering that minimizes the quantity should lead to a faster algorithm.


texts: What is the Kolmogorov complexity of arithmetic?

texts:
Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(n) > L$ where $K(n)$ is the Kolmogorov complexity of the number $n$ and $L$ is a sufficiently large constant. The size of $L$ depends on the theory.

Some people have suggested since the minimum value of $L$ depends on the theory, $T$, the minimum value of $L(T)$ can be used as a measure of the complexity of theory $T$. Other people have argued this is a very bad idea. At least one person has speculated the complexity of Peano arithmetic is less than $10^9$.

Assume we define $K(x)$ using n-state, 2-symbol busy beavers(BB). $K(x)=n$ where $n$ is the number of states of the smallest BB that writes exactly $x$ 1's and halts. We don't really need a strong theory to write a computer program so assume our theory, $T$, is primitive recursive arithmetic. One way to define $L(PRA)$ is to define it as the size of a computer program that can determine the truth of any statement of the form $K(n) > m$ for any positive integers $n,m$. Assume the programming language is x86 assembly. The size of the program is the size in bits of a compiled executable running on a 64-bit processor.

What is a reasonable value for $L(PRA)$? Are there any papers with upper bounds on $L(T)$ for some $T$?


texts: Counting solutions of Monotone-2CNF formulas

texts:
A Monotone-2CNF formula is a CNF formula where each clause is composed by exactly 2 positive literals.

Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I also have an oracle $O$ which is able to give the following information:

The cardinality of the set $S$ (i.e. the number of solutions of $F$).

Given a variable $x$:

The number of solutions in $S$ containing the positive literal $x$.
The number of solutions in $S$ containing the negative literal $\lnot x$.

Given 2 variables $x_1$ and $x_2$:

The number of solutions in $S$ containing $x_1 \land x_2$.
The number of solutions in $S$ containing $x_1 \land \lnot x_2$.
The number of solutions in $S$ containing $\lnot x_1 \land x_2$.
The number of solutions in $S$ containing $\lnot x_1 \land \lnot x_2$.

Note that the oracle $O$ is "limited": it works only on $F$, it can't be used on a formula $F' \neq F$.

  Question:

  Given 3 variables $x_1$, $x_2$, $x_3$
  is it possible to determine the number
  of solutions in $S$ containing $\lnot
  x_1 \land \lnot x_2 \land \lnot x_3$ in
  polynomial time, using $F$ and
  the information provided by $O$?

  Note:

  You can replace $\lnot
  x_1 \land \lnot x_2 \land \lnot x_3$ in the
  question with whatever else of the 8 possible
  combinations of $x_1$, $x_2$, $x_3$. The problem
  would remain the same.

  Empirical fact:

  I came across the following empirical fact one
  week ago. Let $S_{\lnot x_1 \land \lnot x_2} \subset S$
  be the set of those solutions containing $\lnot x_1 \land \lnot x_2$,
  and let $S_{\lnot x_1 \land \lnot x_2 \land x_3} \subset S$ be the set
  of those solutions containing $\lnot x_1 \land \lnot x_2 \land x_3$. Now, it
  seems to be the case that, if condition $C$ holds, this relationship also holds:
  $\frac{|S_{\lnot x_1 \land \lnot x_2}|}{|S_{\lnot x_1 \land \lnot x_2 \land x_3}|} \simeq \phi$
  where $\phi = 1.618033...$ is the golden ratio. Condition $C$ seems to be the following: "$x_1$, $x_2$, $x_3$ are mentioned in $F$ almost the same number of times".


texts: Finding the longest sub-permutation with bounded inversion number

texts:
Given a permutation $\sigma\in S_n$ and a positive integer $k$, find the largest integer $0\le m\le n$ such that there exist a subset $I\subseteq [n], |I|=m$, satisfying that the restriction of $\sigma$ on $I$ has inversion number bounded by $k$. (Here the restriction of a permutation is defined in the very natural way that you can imagine.)

I wonder if the above problem was studied before? Any ideas/previous results on algorithm/approximation algorithm/hardness result are appreciated.


texts: Matrix rigidity and uses of matrices with low rigidity

texts:
Roughly a matrix of rank $n$ is said to be rigid, if to bring its rank down to $\frac{n}{2}$, one has to change at least $n^{1+\epsilon}$ of its entries, for some $\epsilon > 0$.

If an $n \times n$ matrix $A$ is rigid, then the smallest straight line program computing $Ax$  ($x$ is a vector of size $n$) is either super-linear size, or has super logarithmic depth.

Is there a converse to the above statement?

In other words are there uses to non-trivial and non-obvious low rigidity matrices of full rank in TCS?

Is there a notion of rigidity for matrices with lower ranks (say $\frac{n}{c}$ for some constant $c$)?


texts: Are there known "completion" operations over languages ?

texts:
Assume that $P \neq NP$ and let $NPI = NP \setminus (P \cup NPC)$.

Let $L \in NPI$ be a language over an alphabet $\mathcal{A}$.

Does there always exist $S \subset \mathcal{A}^*$ such as $(L \cup S) \in NPC$ ?

On the removal side, Ladner showed that for each $L \in NPI$, there exists $S \subset L$, $S \neq L$ such as $S \in NPI$.

What are known theorems around those kind of operations ?


texts:
What kind of hierarchy theorems are there for circuit depth?

Statements like

  if $g(n) \in o(f(n))$ and $f(n) \in n^{O(1)}$ then
  $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq \mathsf{SizeDepth}(n^{O(1)}, f(n))$.


texts: If P=NP, could we obtain proofs of Goldbach's Conjecture etc.?

texts:
This is a naive question, out of my expertise; apologies in advance.

Goldbach's Conjecture and many other unsolved questions in mathematics can be written
as short formulas in predicate calculus.
For example, Cook's paper "Can Computers Routinely Discover Mathematical Proofs?" formulates
that conjecture as

$$\forall n [( n > 2 \wedge 2 | n) \supset \exists r \exists s (P(r) \wedge P(s) \wedge n = r + s) ]$$

If we restrict attention to polynomially-long proofs, then theorems with such proofs are in NP.
So if P=NP, we could determine whether e.g. Goldbach's Conjecture is true in polynomial time.

My question is: Would we also be able to exhibit a proof in polynomial time?

Edit. As per the comments of Peter Shor and Kaveh,
I should have qualified my claim that we could
determine if Goldbach's conjecture is true if it indeed is one of the theorems with a short proof.  Which of course we do not know!


texts:
Updated below

We all know the critical importance of peer-review.  It is the main form of quality control and feedback on research.  However, to an early-stage researcher (like me), it can sometimes be a confusing system/process.

Accordingly, there are several treatises on the scientific refereeing process that give guidance.  Two (very different) examples from computer science -- this 1994 article by Parberry and a more recent one by Cormode -- offer great advice (though the latter might be a shade mischievous).

Here, I'd like to solicit broader advice from the more experienced members of this community about the review process, with particular regard to the peculiarities of theoretical computer science.

What are the main criteria for determining the significance of a paper's results?  How do I judge whether a paper should be accepted to the conference/journal? Is it important to verify correctness?
What are the main elements of a referee report, and which parts are most important? Is it always necessary to give a recommendation of (non)acceptance? What goes in the report and what goes solely to the editor?
How does assessment for conferences differ from that in journals?  How do reports for conferences differ from those in journals? (How on earth do I rate my "confidence" in my recommendation?) Should the journal version be significantly different from the conference paper?
What if I don't understand the paper? ...the proof?  (Is it my fault or theirs?)
What about typographical/grammatical mistakes? What if there are a lot of them?
How much time should I spend on a report?
How many reports a year am I expected to write? When is it acceptable to refuse a request to referee?

Of course, any other relevant questions and answers on this topic are encouraged, since this is CW.

This question is inspired by (stolen from) a similar post at MathOverflow.

Update 15/02/2011:

I am still very interested in getting more input on this question especially with regard to reviewing conference papers and program committee membership. (These two roles are themselves different beasts, and both very unlike being a referee for a journal article, IMO.)  Granted, program committee membership is rarer than refereeing or reviewing (and it hasn't been my privilege yet), but is a responsibility that every researcher in theoretical computer science must take on eventually.

Time.  How much time am I expected to spend as a committee member or conference reviewer?  Given the probability that I could get ten or perhaps many more to handle in the space of a few weeks, how do I avoid running out of time?  What are the most important things to spend time on?
Confidence.  What if the paper is too far from my area of expertise?  What factors should go into nominating/asking someone else to review a submission?  If it is not too far from my area of expertise and I elect to review it, when is it permissible to give a confidence rating of 1?
Criteria.  There are critical differences between journals and conferences.  Some very important papers are not published in journals.  Some very important papers did not previously appear in conferences.  What are the most significant distinctions in criteria on which to assess papers in these settings?
Recommendations.  Inherently, there are fewer recommendations that can be offered to the authors of a conference paper, primarily due to space and time constraints.  Also, there is usually only one round of review.  Another consideration is that my report becomes public to the entire strong committee.  What is the scope of suggestions/directives that I can offer?

As before, if you think I've missed out on asking any particular questions, do let me know, or edit directly.  This is CW, after all.

These new thoughts are partly motivated by reading a paper that Suresh mentioned on his blog.


texts: Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?

texts:
It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable  i.e. NC.

I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by Johannes Köbler   (see this)

My question : Luks has given an algorithm for trivalent GI (degree at most three ) (see section 2). Is that algorithm also not parallelizable ? If yes provide the reference.


texts: Consequences of Unique Games being a NPI problem

texts: Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so UGC is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover, for example? If not, where does the new threshold of NP-hardness move in $(1,2-\epsilon]$?


texts: Existence of graphs of every order related to Barnette’s conjecture

texts:
Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s  conjecture is based. My interest in C3CBP graphs is somewhat orthogonal to this:

My questions are:

Does there exist a C3CBP graph on $n$ vertices for every even $n > n_0$ where $n_0$ is some small constant?
Does there exist a C3CBP graph without any non trivial automorphisms on $n$ vertices for every even $n > n_1$ where $n_1$ is some small constant?

Notice that $3$-connected planar graphs have only at most linear sized automorphism groups so the second question is natural.

I need the existence and explicit construction of such graphs in an algorithmic problem apparently unrelated to Barnette’s conjecture.


texts: Quantum advantage beyond the black-box model

texts:
Question

Aaronson wrote in his thesis that

  “essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic algorithm, to the algorithms of Hallgren and van Dam, Hallgren, and Ip—are oracle algorithms at their core. We do not know of any non-relativizing quantum algorithm technique analogous to the arithmetization technique that was used to prove PSPACE ⊆ IP. If such a technique is ever discovered, I will be one of the first to want to learn it.”

The common quantum algorithms I know of can be all explained using black-box model (i.e., query model):

Grover's search. An $O(\sqrt{n})$-query algorithm that computes the OR of $n$ bits.

Shor's algorithm. The kernel, Shor's period finding algorithm, is an $O({\rm poly} \log n)$-query algorithm that computes the period of a function, given its truth table as an $n$-bit input.

There are more examples like quantum local search and quantum-walk-based algorithms.

  Do we have any problem that admits a quantum speedup, which cannot be explained using black-box model at present?

Meaning of this question

The quantum query complexity of any partial Boolean function is completely characterized by the general adversary bound (see e.g. [LMR+11]), which is a natural method, in the sense of Razborov and Rudich.
If it turns out that every quantum technique relativizes, I think we will have some very interesting insight on quantum computing, from a computational complexity aspect.


texts: Distributed Consistency using Quorum approach

texts:
I'm stuck at distributed consistency when using a quorum. In this case we use N servers - 2/3N+1 for the read quorum (Nr), and N/3+1 for the write quorum (Nw).

Now, two conditions have to be satisfied to achieve consistency.

Nr + Nw > N (implies at least one server that performs read was updated)
Nw > N/2

And the second condition is what isn't clear to me. According to wikipedia this ensures that two write operations don't concurrently occur at the same data item. Can somebody evaluate on that?


texts: Comparing the Kolmogorov complexity of theories

texts:
Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(s) > L$ where $K(s)$ is the Kolmogorov complexity of string $s$ and $L$ is a sufficiently large constant. $L$ is sufficiently large if it is larger than the size in bits of a proof checking machine (PCM). A PCM for theory $T$ takes a string encoded as an integer as input and outputs a 1 if the string is a valid proof in the language of $T$.

Assume that $L(T) > |PCM_T|$ for theory $T$ is an upper bound for the complexity of $T$. Consider the following hierarchy of theories: Let the base theory be Robinson arithmetic ($Q$). Augment $Q$ with increasingly stronger axioms of polynomial bounded induction. Let $Q^*$ be the theory of theorems provable with $Q$ and any of these bounded induction axioms. Assume we can define $L(Q)$ and $L({Q^*})$ by defining PCM's for each theory.

I want to consider an enhanced proof checking machine (EPCM) for $Q^*$. This EPCM takes a string as input just like an ECM and has a second input which defines the rank and level of a sub-theory of $Q^*$. If the input string is a valid proof in $Q^*$ the EPCM then goes through the steps of the proof to determine the highest rank and level of induction used. This EPCM then writes a 1 if the input sentence is a valid proof in the specified sub-theory of $Q^*$.

Is the enhanced proof checker I describe feasible? If so, would the size of this EPCM be an upper bound not just for the complexity of $Q^*$, but also an upper bound on the complexity of any sub-theory of $Q^*$?

Is it reasonable to say there is a constant upper bound on the complexity of $Q^*$ and all of its sub-theories?

This question was inpired by Nelson's failed proof of the inconsistency of arithmetic. I didn't point this out earlier because some people find that proof disturbing. My motivation is to ask an interesting question. CSTheory seems to be the right forum for this question. The complexity of $Q^*$ and all of its sub-theories is either bounded by a constant or unbounded. Either answer leads to more questions.

If the complexity of the sub-theories is unbounded we can ask questions like what is the weakest sub-theory of $Q^*$ more complex than $Q^*$? Or more complex than PA and ZFC? Thinking about this question has already shown me there is a severe limit on how much a theory can prove about the Kolmogorov complexity of strings. If $Q^*$ is consistent then none of its sub-theories can prove $K(s) > L(Q^*)$ for any string. This means even really strong sub-theories can't prove there are more complex strings than some much weaker sub-theory where the weaker theory is more complex than $Q^*$.


texts:
I have some graph-data which I would like to analyze. If the software could automatically determine some characteristics (Is the graph planar, clique number or any other graph property) it would be great, but if I could move the vertexes per drag and drop it would be good enough.

I know that I can visualize graphs with Graphviz, but I can't interact with the graph.


texts: What is the complexity of decision tree complexity?

texts:
Given a boolean function $f$ on $n$ bits, how hard is it to determine its decision tree complexity?
(I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.)

If $f$ is given by an oracle, then this is surely exponential in $n$, still I wonder if it ever has been studied, if there are algorithms that run in $2^{O(n)}$.
I am even more interested in results about when $f$ is given in another way, by a polynomial over some field, or by a Turing-machine computing it.
Is there anything known about this?
Are there any hardness results?


texts: Complexity of checking $a > br^m + cr^n$, with $r$ rational

texts:
I'm wondering if the following problem is decidable in P-time (or even NP):

Given $a, b, c \in \mathbb{Z}$ and $m, n, p, q \in \mathbb{N}$ all in binary, decide if $a > br^m + cr^n$, where $r = {p \over q}$.

Remarks:

If $c = 0$, this is a very special case of the following problem, which is in P for any fixed $n$ (Etessami et al.):

       Given $\vec{a}, \vec{b}, \vec{c}, \vec{d} \in \mathbb{N}^n$ all in binary, decide if $a_1^{b_1}\cdots a_n^{b_n} > c_1^{d_1}\cdots c_n^{d_n}$.

An upper bound for the above problem is given by the fact that numerical analysis is in the counting hierarchy (Allender et al.)
I'm particularly interested in values of $r$ very close to 1.


texts: Boolean error correcting code over $\mathbb{F}_q$

texts:
Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, it also returns a Boolean vector w.h.p.? (although it is over $\mathbb{F}_q$)

(that is, $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$, where the probability is taken over uniformly choosing $v\in \{0,1\}^n$, and $\epsilon$ is arbitrarily small)

If not, what if we relax the condition to
$$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$$
Where $\mathsf{ECC}_i$ returns the $i$'th coordinate of $\mathsf{ECC}$, $\epsilon$ is arbitrarily small, and the probability is taken both over uniformly choosing $v\in \{0,1\}^n$ and uniformly choosing a coordinate $i\in[m]$.


texts: Has this bipartite graph problem been studied?

texts:
I have a directed bipartite graph with vertex sets $U$ and $V$, directed edge sets $E(U,V)$ and $E(V,U)$, and a demand function $d \colon U \rightarrow \mathbb{Z}$. I want to find a function $f \colon V \rightarrow \mathbb{Z}$ that "meets the demand" in the following way. Extend $f$ to a function on the edges $f' \colon E \rightarrow \mathbb{Z}$ defined by
\begin{equation}
f'(x, y) = \begin{cases}f(x) & (x,y) \in E(V,U)  \\
             -f(v) & (x,y) \in E(U,V)
\end{cases}.
\end{equation}
So, $f'(e) = f(u)$ when $e=(v,u)$ is directed from $V$ to $U$, and $f'(e) = -f(u)$ otherwise. Now I want to $f$ to satisfy the demand such that for each $u \in U$ the edges incident to $u$ sum up to the demand on $u$. That is,
\begin{equation}
\sum_{e \in E(V,U)} f'(e) - \sum_{e \in E(U,V)} f'(e) = d(u).
\end{equation}
My initial thought was that this could be reduced to some kind of flow problem, but I don't know how to deal with the fact that for each vertex the amount of flow on each edge incident to that vertex must be equal.


texts: Enumerate all solutions of a SAT problem

texts:
All the #SAT solvers I know, e.g RelSat, C2D, only return the number of satisfiable instances. But I want to know each of those instances?

Is there such a #SAT solver or how I should modify an available #SAT solver to do this?

Thank you.


texts:
The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand.

In Diffie-Hellman Alice and Bob choose numbers $x$ and $y$ in a fine representation and publish $x$ and $y$ in a coarser form from which they can both determine $xy$ in coarse form. A form is considered coarse if the product of two numbers in the coarse form is (practically) uncomputable, but the product of a number in the coarse form and another number in the fine form is computable.

So is there an information-theoretic analogue? My thoughts are that a number $x \in [0,1] \subset \Bbb R$ can be represented:

In a fine way using an upper-bound and lower-bound oracle.
In one coarse form by using an upper-bound oracle.
In another coarse form by using a lower-bound oracle.

Is there any literature on this?

Cheers


texts: Count satisfying assignments of CNF formulas over all possible negation assignments

texts:
Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the sum of the counts of satisfying assignments for the set?

More formally, consider a CNF formula over a boolean variable set $V$ described by $\phi = C_1 \wedge C_2 \wedge \dots \wedge C_m $, where each clause $C_j$ is a disjunction over a subset of $V$, and let $|\phi|$ denote the count of the satisfying assignments of $\phi$. Let $l_j$ denote the length of $C_j$. From each $C_j$ one can create $2^{l_j}-1$ other clauses by negating one or more of the literals that appear in it. One can therefore generate formulas $\phi_k$ where $k=1,\dots,2^{\sum_jl_j}$ with the same "structure" (i.e., the same factor graph topology) as $\phi$. How hard is it to compute $\sum_k |\phi_k|$?

Naively, one might expect that this should be as hard as counting the satisfying assignments of the hardest instance in the set. Is this correct? Or are there any interesting special cases where this intuition may be wrong? What about the restricted problem of getting the total count modulo some integer greater than 1? Does this problem have a name?

For example, if $\phi$ is a 3SAT formula, I would expect the problem to be #P-hard. On the other hand, if $\phi$ is an XORSAT formula, each $|\phi_k|$ is easy to evaluate, but there is an exponentially large number of them.


texts: Finding output with unique witness in matrix multiplication

texts: Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication but the entries store the count of how many $y$ generate a given output entry). My goal is to find only the output entries in $C$ which are generated by exactly one value of $y$ (i.e. a unique witness). In other words, I want to find all $(i,j)$ such that $C(i,j) = 1$. Clearly, I can simply perform the matrix multiplication and iterate over $C$ to identify the output with unique witnesses but can we do better? Is this problem as hard as matrix multiplication itself? Are there are any known reductions that consider the problem of finding output that is generated by a unique $y$ value? I am interested in deterministic algorithms but even something probabilistic may be insightful.


texts:
Deciding Graph Homomorphism is in general NP-Complete.

Are there any results which study this problem when the underlying graphs have algebraic structure (such as deciding homomorphisms from Cayley or Cayley coset graphs to other graphs with some definite structure as well)? In addition complexity results I am also interested in helpful algebraic and/or spectral techniques.


texts:
I'm a physicist who works on inverse problems; I'll explain what these are by means of an example. Consider an object whose refractive index is known; then, the problem of computing scattered electromagnetic fields (also called the forward problem) has a unique solution (whose complexity is essentially that of solving a system of linear equations). The inverse problem is one where one estimates the refractive index of an object given the measurements of the scattered electromagnetic fields.

The inverse problem is nonlinear, ill-posed, and ill-conditioned. Such a problem has no unique solution, and shows several local minima if attacked by local optimization techniques. Further more, if I am given a solution, I have no way of checking whether it is the best solution (say in a least squares sense) or not. How would I go about trying to find out, or even start to think, whether this problem is in NP?

I'd appreciate any pointers to appropriate resources if you think the question is too basic for this forum. Thanks!


texts: Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?

texts:
Assume we want to refute an unsatisfiable CNF.  We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear relaxation until the polytope is empty.

For a polytope $P$ we consider $N_{+}(P)$ to be the polytope where all possible $LS_{+}$ cuts have been further applied.  We can always iterate the operator $N_{+}$ until the resulting polytope is empty.  The number of iterations required to reach the empty polytope is called the rank of the polytope.

Since each iteration increases the number of facet of a polynomial factor, a non constant number of iterations is out of question.

In the case of Gomory-Chvátal cuts, the usual PHP formula requires rank $\Omega(\log n)$, but there exists a refutation of polynomial size.  Such refutation essentially produces the empty polytope using only a small number of the facets from each iteration.

My question is: does there exist a similar example for $LS_{+}$ cuts, i.e. a case where an short refutation exists but the rank is large?

Update: The following paper shows (among other things) that a tautology with short refutation and linear rank would separate Tree-Like LS+ from general LS+ refutations.

Toniann Pitassi and Nathan Segerlind, "Exponential Lower Bounds and Integrality Gaps for Tree-like Lovasz-Schrijver Procedures", SODA, 2009.


texts: Functionality of a hierarchy of definable functions over $\mathbb{N}$

texts:
Let $T$ be the complete hierarchy of functions over $\mathbb{N}$.  That is: $T$ = $\bigcup T_{\tau}$ for all simple types $\tau$ built up from the basic type $\mathbb{N}$, with $T_{\mathbb{N}} = \mathbb{N}$ and $T_{\alpha→\beta} = {T_\beta}^{T_\alpha}$.  For a given signature $\Sigma$ consisting of some members of $T$, there is an obvious way of interpreting the closed terms of type $\tau$ in a simply typed $\lambda$-language $\mathcal{L}_\Sigma$ with constants from $\Sigma$ as denoting functions in $T_\tau$.  Let ${T^\Sigma}$ contain just those members of $T$ that are denoted by closed terms in $\mathcal{L}_\Sigma$.  Say that $T^\Sigma$ is functional just in case, for any distinct $f, g ∈ {T^\Sigma}_{\alpha→\beta}$, there is some $x ∈ {T^\Sigma}_\alpha$ such that $f(x) \ne g(x)$.

Specific question: let $\Sigma$ consist in all members of $\mathbb{N}$ (of type $\mathbb{N}$) together with the addition function (of type $\mathbb{N}→\mathbb{N}→\mathbb{N}$).  Is this $T^\Sigma$ functional?

More general question: is there any useful general condition on $\Sigma$ that is sufficient for $T^\Sigma$ to be functional?


texts: Hardness of constrained star system problem?

texts:
A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-complete to decide whether a given star system is graphical.

  What is the minimum occurrence of each element such that the problem remains $NP$-complete?

EDIT 12-12-2010: I added another question:

  What is the most restricted class of graphs for which the problem remains $NP$-complete?

For instance, Is the star system problem $NP$-complete if the target graph is cubic? If not, What is the minimum $k$ such that the problem remains $NP$-complete for $k$-regular target graphs?

 F.Lalonde, Le probleme d'etoiles pour graphes est NP-complet, Discrete Math.
33(3), 1981, 271-280.


texts:
Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant formula we know that $$|n\cdot\mathsf{det}(A)|=\Big|{\mathsf{Tr}(A^n)}\Big|.$$

We can use a non-monotone formula for determinant from work of S. J. Berkowitz in On computing the determinant in small parallel time using a small number of processors. Inf. Prod. Letters 18, pp. 147–150, 1984 to compute $|n\cdot\mathsf{det}(A)|$.

1. Does Berkowitz formula actually reduce to $\big|{\mathsf{Tr}(A^n)}\big|$ which is actually a monotone formula ($A$ having only non-negative entries is no issue here)?

2. With these matrix types, is complexity of computing $|n\cdot\mathsf{det}(A)|$ the same whether with monotone or with non-monotone formula, or is there a more succint non-monotone formula?


texts: Subspace-evasive set performance in the random case

texts:
A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough dimension.

Formally, for parameters $k$ and $\epsilon > 0$, a $(k,c)$-subspace evasive set $S \in \mathbb{F}_q^n$ is such that $|S| > |\mathbb{F}_q^{n}|^{1-\epsilon}$ and $|S \cap H| < c$ for all $k$-dimensional affine subspaces $H \in \mathbb{F}_q^n$.

The goal is to make the intersection $c$ as small as possible.

It is claimed (as trivial in most references) that a random set $S \in \mathbb{F}_q^n$ of size $|\mathbb{F}_q^{n}|^{1-\epsilon}$ has (whp) intersection $c = O(k/\epsilon)$.

Is there a way of showing this? It is supposed to be a simple application of a probabilistic method, but I am stuck and clueless.


texts: Primitive Recursive Definition : Binary numbers

texts:
Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion.

But you obtain algorithms that works with unary numbers. For example, the addition $x+y$ has complexity $O(y)$, whereas usually, it has complexity $O(|x|+|y|)$. Is there a canonical definition of recursive functions that consider integers as binary string ? Any references are welcomed.


texts: Powerful Algorithms too complex to implement

texts:
What are some algorithms of legitimate utility that are simply too complex to implement?

Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm (Coppersmith-Winograd), which is reasonable to implement but has a constant that makes it useless in practice. I'm looking for algorithms that could plausibly have practical value, but are so difficult to code that they have never been implemented, only implemented in extremely artificial settings, or only implemented for remarkably special-purpose applications.

Also welcome are near-impossible-to-implement algorithms that have good asymptotics but would likely have poor real performance.


texts: Sums of products of bernoulli random variables

texts:
Let $x_1 \ldots x_a,y_1 \ldots y_b$ be independent random variables taking values +1 or -1. Consider the sum
$$S = \sum_{i,j} x_iy_j.$$
I wish to upper bound the probability $P(|S| > t)$.

The best bound I have right now is
$$2\exp(-\frac{ct}{\max(a,b)})$$
where $c$ is a universal constant.
This is achieved by lower bounding the probability $Pr(|x_1 + \dots + x_n|<\sqrt{t})$ and $Pr(|y_1 + \dots + y_n|<\sqrt{t})$ by application of simple chernoff bounds.

Can I hope to get something that is significantly better than this bound?
For starters, can I at least get
$$\exp({-\frac{ct}{\sqrt{ab}}})?$$

If I can get sub-Gaussian tails that would probably be the best but can we expect that? (I don't think so but can't think of an argument.)


texts: Dynamic programming  and shortest path problem

texts:
Several months back, I asked in math.SE the following question

  I wonder if any dynamic programming problem can always be converted to
  a source-sink shortest path problem in a network with source and sink
  nodes given?

The reason I asked is because I always pictured the type of problems that could be solved by dynamic programming method as source-sink shortest path problems. In other words, the type of problems seemed to always have the interpretation as source-sink shortest path problems, but I was not sure if it was correct.

The only answer I have got so far is

  The answer is no. The simplest example off the top of my head is the
  longest substring of ones in a 0,1 string. The typical DP solution
  would be to use a 1D array and store the length of the longest
  substring up that includes the i-th character in the i-th coordinate.

When I further asked:

  why is the example not able to be formulated into a source-sink
  shortest path problem in a network?

The reply is:

  I don't really see an easy way of doing it as a source-sink SPP. For
  the DP solution, the answer is obtained by scanning the array for the
  largest number.

I am now still not sure how DP solves the longest substring of ones in a 0,1 string, and whether this problem can be interpreted as a source-sink shortest path problem. Also I feel the answerer may run out of idea from his reply. Since my question may also be relevant to algorithm theory, I hope there will be some reply from this site.

Thanks and regards!


texts: Minimum offset while measuring TSP paths

texts:
I have Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

I am trying to solve TSP with brute algorithm, and I want to know how to calculate the smallest possible difference between the paths that I find during the run.

Edit:
I want to know this, to proper round my distances. May be I can use integers, may be I need floats, or maybe I need 1,000,000 floating point number. When I am comparing two distances and I coming to the conclusion that they are equal I want to be 100% sure they are.

Edit 2 Another interesting example for the possibilities is: If you are taking a graph that all the weights are 1 or 2. The minimum offset will be exactly 1.


texts: What is the quantum computational model?

texts: I have occasionally heard people talk about quantum algorithms and about states and the ability to consider multiple possibilities at once, but I have never managed to get someone to explain the computational model behind this. To be clear, I am not asking about how quantum computers are physically constructed, but rather how to view them from a computational point of view.


texts: Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise

texts:
There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we weaken our notion of security from "impossible" to "it would take exponentially long to break" we get some other results. In How to Fool an Unbounded Adversary with a Short Key Russel and Wang show how to encrypt high entropy messages using a small symmetric key such that we can safely conclude that an adversary would have to perform an exponential number of steps to decide anything about our message. This is a problem because most of the messages I send are quite predictable. This caveat is always mentioned when I see entropic-security mentioned. It seems to me that there exists a way to encrypt messages of low entropy using this method, however.

Solution:
  Alice wants to send $M \in \{0, 1\}^n$ to Bob. Alice and Bob have agreed on $K_\mbox{rw} \in \{0, 1\}^{\ell + 128}$ as a key to be used in Russel ang Wang's entropically secure encryption algorithm. Alice generates a one-time pad $K \in \{0, 1\}^n$ by sampling from a uniform distribution. Alice encrypts $K$ using $K_\mbox{rw}$ and sends the results Bob. Bob now knows $K$. Alice now encrypts $M$ using $K$ and sends it to bob. Bob uses $K$ to decrypt the message and now Bob knows $M$.

$K$ would have maximal entropy and thus would meet Russel and Wang's requirement. The second message gives no information about $K$, $M$, or $K_rw$ and thus can't be used to attack the original message (At least that's how I understand it).

The only downside I can see to it is that it requires sending twice the amount of information you'd otherwise have to send but for many applications that's quite acceptable. This would seem to imply that Russel and Wang's method is far more widely applicable. You likely wouldn't use this method for video streaming but you might very well use it for sending information to your bank or you might use it for browsing the web.

The lack of mention of this a) In their paper, b) on Wikipedia and c) in a couple other papers that cite Russel and Wang that I've skimmed leaves me thinking that I've overlooked something. Is there a security issue that I've overlooked? Is this method or something equivalent/better mentioned somewhere else? Are there any other drawbacks that I'm not seeing? Even if I've done something wrong here then is something like this still possible? Specifically, can we use Russel and Wang's algorithm to encrypt low entropy messages by sending some extra information drawn from a high entropy source (as I believe my "solution" does)?


texts: I'm new to the CS field and I have noticed that in many of the papers that I read, there are no empirical results (no code, just lemmas and proofs). Why is that? Considering that Computer Science is a science, shouldn't it follow the scientific method?


texts:
Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges $(v_1, v_2) \in E$ such that $(f(v_1), f(v_2)) \notin E'$. This is a generalization of the subgraph isomorphism problem where we allow the subgraphs to be isomorphic up to a few missing edges and want to find the way to minimize the number of missing edges.

I would also be interested in the weighted version of this problem, where vertex couples $(v_1, v_2) \in V^2$ carry a weight $w(v_1, v_2)$ (which must be zero if $(v_1, v_2) \notin E)$, and likewise for $G'$, and we wish to minimize $\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$ (the $\max$ is there to only penalize weights from the query graph being larger than those of the reference graph).

My question are: Has this problem already been studied? Does it have a well-known name? Are there any efficient approximation algorithms known?

The motivation of this problem (apart from the fact that it seems like a natural generalization of the subgraph isomorphism problem) is that it is a nice way to make a table plan for a party: the query graph is the graph of guests with edge weights representing the extent to which two people want to interact, the reference graph has the table seats as vertices and edge weights indicating to what extent communication is possible, the solution of the problem is a mapping from people to table seats which respects the social structure to the fullest possible extent.


texts: Lower bound on the worst-case unbiased coin flips to sample a distribution?

texts:
Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:
$$
\Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i},\quad k_i\in\{0,1\}
$$
Say that this is a non-trivial $p$-bit distribution if at least one element $k$ truly takes all $p$ bits to represent, meaning $\exists k\in\mathsf{supp}(\mathcal{D})$ such that $k_p = 1$

I'm interested in the number of $\mathsf{Bern}(1/2)$ random variables required to sample a single sample from this in the worst-case.
From some discussions with others we think it's obvious that it's $p$, and that there should be a lower bound. It seems like a rather basic observation though, so I was wondering if I could find it in the literature anywhere so I could cite it.

Edit: To make the question slightly more specific, I have a ~1/2 page information theoretic argument showing this is true (it's really quite trivial), so I'm solely looking for a reference for who to cite regarding this lower bound.


texts: Constructivity in Natural Proof and Geometric Complexity

texts:
Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.

Constructivity in Natural Proof is a condition that all combinatorial proofs in circuit complexity satisfies and that we can decide whether the target function in $\mathsf{NEXP}$ (or another "hard" complexity classes) has a "hard" property by a algorithm that runs in poly-time in the length of target function's truth table.

The other two conditions are: useless condition that require "hard" property can not be computed by any circuits in $\mathsf{TC}^0$ and largeness condition that the hard property is easy to find.

My question is :

Does this result make the Geometric Complexity Theory (GCT) unavailable to resolve main separation problems such as $\mathsf{P}$ vs $\mathsf{NP}$, $\mathsf{P}$ vs $\mathsf{NC}$, or $\mathsf{NEXP}$ vs $\mathsf{TC}^0$?

References:

Ryan Williams, "Natural Proofs Versus Derandomization"


texts: "Interesting" categories whose internal logic is a dependent-linear type theory

texts:
Dependent-linear type theories may be a functional programmer's dream, but is it categorically interesting, i.e. is it the internal language of an "interesting" category? By "interesting", I mean a category that arises naturally in mathematics or computer science, similar to how intuitionistic type theory is the internal logic of toposes or linear logic is the internal logic of $\mathbf{PShMod}_X$, which is ubiquitous in algebraic geometry. In other words, can we give an interesting and "natural" categorical model of a dependent-linear type theory?
Any (reasonable) flavor of dependent-linear type theory is fine, as long as it has a linear layer and a dependent layer. Examples include Atkey's quantitative type theory and Krishnaswami, Pradic & Benton's dependent-linear calculus (POPL '15).
(Sorry, but I don't know whether this site or MathOverflow would be a better forum for this question. But it seems that I might attract more experts on this site...)


texts: Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

texts:
My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3).

MAX k VERTEX COVER (aka MAX k-COVERAGE)
INPUT: a graph $G$, an integer $k$
OUTPUT: a set $C\subseteq V(G)$ of vertices of size $k$
MEASURE: the number of edges of $G$ that have at least one endpoint in $C$

MAX k VERTEX COVER is proved to be APX-hard on subcubic graphs, by a reduction from MIN VERTEX COVER (itself well-known to be APX-hard on subcubic graphs), in this 1994 paper by Petrank (Theorem 5.4). However, the proof is very succinct and in a formalism that I do not know, hence I could not grasp the details of it. I would like to have a formal proof in a more standard language. (For example, a proof that this reduction is an L-reduction would be perfect!)

  Question: Can someone explain the proof of Petrank's reduction (for example in terms of standard L-reductions)? Alternatively, give (or point to) a different reduction with such a proof.

Note: in Lanberg's 1998 master thesis, a stronger result than Petrank's is proved (the hardness remains valid for a wide range of values of $k$), but only for graphs of maximum degree 30 (see Lemma 3.1). I do not know if other results of APX-hardness for the problem exist in the literature.


texts: Algorithm (parallel and serial) for Gram-Schmidt

texts:
Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the subspace perpendicular to $v_1, \dots, v_m$. I could do this by Gram-Schmidt but this would appear to take roughly $(m+n)^3$ time in serial, and cannot be done at all in parallel. Maybe we can assume $m = O(n)$ if this simplifies things.

Are there better algorithms for this? This seems closely related to matrix inversion so one should expect algorithms running in time $n^{\omega}$ (serial) or NC algorithms in time $\log^2 n$ (in parallel). Any references or key words would be greatly appreciated.


texts: Is there a special name for the following type of graphs?

texts: Weighted graphs such that if $x$ and $y$ are nodes in the graph, and $p$ and $p'$ are two paths in the graph between $x$ and $y$, then the weight of $p$ equals the weight of $p'$.


texts: Complexity of "destroying" the graph's minimum spanning tree weight

texts:
Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$.
Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\infty$ for graph $G'$ which is not connected.

Consider the following problem:

  Given an integer $k\in\mathbb N$, decide whether there exists an edge set $E'\subseteq E$ , such that $|E'|=k$ and $w((V,E\setminus E')) > w(G)$?

What is the complexity of the above problem?.


texts:
I want to define a category in simple MLTT (not in HoTT). I defined it with the help of setoids. I.e. category consists of:

a type of objects with equivalence relation (Obj : Set)
a type of arrows between two objects with equivalence relation on it (Hom : Obj -> Obj -> Set)
a set of category operations (i.e. id : (O : Obj) -> Hom O O, and composition)
a proof that these operations respect equivalence relations

I defined simple notions of category theory with such a definitions, i.e. terminal objects, functors and I feel that everything looks fine.

However, I feel that definitions like this isn't exactly what we want when we talk about a category. Consider objects A, B, A' and B'. Assume A is equivalent to A' and B is equivalent to B'. We assume that the structure of arrows between A and B is in some sense isomorphic to A' and B' but the foregoing definition doesn't say anything about this. As far as I understand, HoTT, would require these types of arrows to be "equivalent".

What's wrong with this? What should be added? Is there any name for such a structure?


texts: Why is regularity a problem in cubical type theory?

texts:
In my current understanding, regularity in cubical type theory is the following definitional equality (I'm using $A~\textbf{type}$ to emphasize the fact that $i \notin FV(A)$):
$$
\cfrac{A~\textbf{type} \quad a:A}
{\text{transport}(\langle i \rangle A, a) \mapsto a}
$$
I am not sure how is transport specified here (does it have a standard formulation?). I just assume it to be a special case of transp in de Morgan cubical type theory and a special case of coe in Cartesian cubical type theory.
In Cubical Agda, this definitional equality doesn't hold. It's proved as transportRefl in the cubical library. I'm not sure how it works in Cartesian cubical type theory, but I guess it is also a long-standing problem (Jon Sterling said he solved it a while ago, but it's on Twitter, which is not a reliable source of academic information).
I don't quite get the difficulty -- it seems like a problem in the model. In Arend's type theory, regularity is a part of the definition of coe, and it's implemented as "normalizing the path, reduce to $a$ if $i \notin FV(A)$". Why can't we do this in cubical type theory? We already have eta laws for functions where we need FV checks, so this is not a problem implementation-wise (or is it? Please tell me!).


texts: Does the first order theory of a finite structure have bounded quantifier rank?

texts:
Let $\mathfrak{A} $ be any finite structure.
Does its first order theory $ \mathfrak{T} := \mathfrak{TH}(\mathfrak{A}) $ have bounded quantifier rank, in the sense that there is a $ q\in\mathbb{N} $ such that for all $ \varphi\in\mathfrak{T} $ with $ qr(\varphi) > q $ there is a $ \varphi'\in\mathfrak{T} $ with $ qr(\varphi')\leq q $ and $ \varphi'\equiv\varphi $ ?


texts: Semantic definition of strict positivity for a functor

texts:
If we consider a definition of recursive type as:

F : Type -> Type;
T = fix F;

It is customary to talk about the functor F needing to be positive or strictly positive in order to avoid non-termination in the recursor.

I'm familiar with the usual syntactic definition of strict positivity, but I'm looking for corresponding semantic definitions, especially ones that can be expressed in the system (rather than being defined at the meta level).

The closest I have found is the work on containers (Abbott et.al., 2005), but it appears to require some "creativity" to come up with a container corresponding to a given functor and then prove equivalence between the two.  I'm looking for something that talks more directly about the properties of F.


texts: Reference request: Depth- (or Breadth-) first search with hints?

texts:
Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it.

Would it be possible to pre-process the graph and compute some "hints" among all nodes in the graph, such that given any node pair $s$ and $t$, the DFS or BFS procedure knows that some edges are more likely contributing to a path (if any) between $s$ and $t$? Therefore, the DFS or BFS will only traverse the "promising" edges to find the $s$-$t$ path. Is it a known problem?

Transitive closure could be one possible "hint". I am wondering if there is any cheaper solution, preferably in O(n) time.

Edits: "promising" means very likely. It appears that it's difficult to compute definitive promising edges (i.e., the edges will definitely be in an $s$-$t$ path). However, will it be possible to compute the promising edges by allowing some reasonable error?


texts: Iterative algorithms and Lyapunov functions

texts:
Consider an iterative algorithm of the form $x^{t+1} = x^t - \eta g(x^t)$. (..if necessary feel free to assume that a function $L$ is explicitly known such that $g = \frac{\partial L}{\partial x}$..). Suppose that now I want to show that there exists a point $x^*$ within some pre-determined ball which is a fixed point for this iterative algorithm.

I would like to know what methods are generally known to show such a thing in cases when the function $g$ is too complicated to solve for its roots?
Is there a way to argue for the existence of such fixed points starting from proving some Lyapunov-like properties for $L$?


texts: What is the descriptive complexity of the basic modal logic?

texts:
This is kind of multiple questions in one. Let's consider $\phi$ a formula in the basic modal language (that is, in propositional language based on a set of propositional variables $\Phi$, plus one of the basic modal operators, say, $\Diamond$)

1) Define the $\phi-\mathsf{MODEL}$ problem as: Given a finite structure $M = (W, R, V, w)$, where $W$ is a set, $R \subseteq W \times W$, $V : \Phi \rightarrow 2^W$ and $w \in W$, is $\phi$ satisfied in $M$, as per the usual modal logic definition of satisfiability?

2)  Define the $\phi-\mathsf{FRAME}$ problem as: Given a finite structure $F = (W, R)$, where $W$ is a set and $R \subseteq W \times W$ is $\phi$ valid in $F$, as per the usual modal logic definition of validity?

We could go on and define other variants, asking if there is a world in which the formula is satisfied (or valid), if there is a valuation such that the formula is satisfied, and so on.

Now consider, for example, the collection of $\phi-\mathsf{MODEL}$ problems, for all basic modal formulas $\phi$. My question could be formulated as thus: Is this class of problems equal to any well-known complexity class? Of course, the question could be formulated for any of the variants i just proposed, so it's as i said earlier, kind of multiple questions in one.

(It goes without saying, but for other logics, such as first and second-order logics, this is a much-studied subject with the name Descriptive Complexity, with classic results such as Fagin's Theorem relating the existential fragment of second-order logic to the complexity class NP)


texts:
Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP.  The proof uses the completeness of SAT under many-one reductions in NP.  The hierarchy contains complexity classes constructed by a kind of diagonalization, each containing some language to which the languages in the lower classes are not many-one reducible.

This motivates my question:

  Let C be a complexity class, and let D be a complexity class that strictly contains C.  If D contains languages that are complete for some notion of reduction, does there exist an infinite hierarchy of complexity classes between C and D, with respect to the reduction?

More specifically, I would like to know if there are results known for D = P and C = LOGCFL or C = NC, for an appropriate notion of reduction.

Ladner's paper already includes Theorem 7 for space-bounded classes C, as Kaveh pointed out in an answer.  In its strongest form this says: if NL ≠ NP then there is an infinite sequence of languages between NL and NP, of strictly increasing hardness.  This is slightly more general than the usual version (Theorem 1), which is conditional on P ≠ NP.  However, Ladner's paper only considers D = NP.


texts: What's the relationship between ASP-complete and #P-complete?

texts:
Given that ASP-reductions by definition are parsimonious and parsimonious reductions preserve #P-completeness, one might think that the counting version of all ASP-complete problems are also #P-complete (note that e.g. #3SAT is #P-complete and 3SAT is ASP-complete).

However, ASP-completeness implies that all solutions have polynomial length, whereas no such requirement is there for #P.

Is it the case that all ASP-complete problems are #P-complete?  Is there some kind of relationship in the other direction as well?


texts: Turing-complete computation models on graphs

texts:
There are many Turing complete computation models and new ones are devised all the time.

  I am looking for Turing-complete computation models based on graphs?


texts: Computational complexity of the 3-partition problem with distinct numbers

texts:
This question is related to an answer I posted in response to another question.

The 3-partition problem is the following problem:
Instance: Positive integers a1, …, an, where n=3m and the sum of the n integers is equal to mB, such that each ai satisfies B/4 < ai < B/2.
Question: Can the integers a1, …, an be partitioned into m multisets so that the sum of each multiset is equal to B?

It is well-known that the 3-partition problem is NP-complete in the strong sense that it remains NP-complete even if the numbers in the input are given in unary.  See Garey and Johnson for a proof.

Questions: Does the 3-partition problem remain NP-complete if the numbers a1, …, an are all distinct?  Does it remain NP-complete in the strong sense?

(My feeling is that the answers to both questions are probably yes because I do not see any reason why the problem should become easier if all numbers are distinct.)

It does not seem that the proof in Garey and Johnson establishes the NP-completeness of this restricted version.

In the answer to the other question linked above, I gave a proof that the 6-partition problem (defined analogously) with distinct numbers is NP-complete in the strong sense.


texts:
Suppose a graph with node weights only (no edge weights). For a given source-sink pair, how can I find a path with the minimal sum of node weights? Does this problem have a name? Is it possible to reformulate this to a shortest-path problem?

If both nodes and edges are weighted, is it still possible to find a min-weight path?


texts: Practical limits of big-O performance scaling

texts:
Lets imagine we have an algorithm made up of a set of operations. Let assume that it has three kind of operations and the time complexity is  $t(n) = An + Bn\log n + Cn^2$. This algorithm has asymptotic performance $O(n^2)$.

Now, on a real computer (or a more sophisticated abstract machine that doesn't assume infinite capacity, I guess), I eventually hit issues with the complexity of these operations (e.g. a garbage collector, memory paging, cache, ...) which cause $C$ which is a constant in the abstract model to become itself a function of $n$.

Is there a name for this? Is there a framework in which these kinds of issues can be placed?

Obviously from the question and the lack of jargon, I'm a practitioner, not a computer scientist (my PhD was in AI, not CompSci). But the issue is critically important for studying actual algorithm behavior, and so I'd appreciate any help in finding resources that put it into a less ad-hoc context.


texts: Reduction from planar bounded NCL to a static puzzle game

texts:
I call Fill3 the following simple game: the input is a $n \times n$ grid;

every cell of the grid has a type: OR, AND, CHOICE, FANOUT and FIXED and can be rotated 0, 90, 180 or 270 degrees;
every cell (except the FIXED) contains three green squares that according to the cell's type can be placed in several different valid configurations (see figure);

The aim of the game is to choose a valid configuration for each cell (the type and the rotation cannot be changed) in such a way that no two green squares are adjacent (vertically or horizontally). The game is NP-complete (a quick reduction is from planar 3SAT).

Valid configurations for each type of cell.

But the cell types are obviously a direct transposition of the four gadgets used in the bounded planar Nondetermnistic Constraint Logic (NCL) and the valid configurations match  the constraints of the corresponding vertices in a constraint graph (blue/red arrows in the figure).

I'm wondering if a direct quick reduction from NCL is possible. It is immediate to reduce a planar constraint graph to a Fill3 game (CHOICE cells with a "free" endpoint can be used to build straight links and 90° turns). But in a bounded planar NCL problem $P$ the edges are reversed dinamically (though an edge can be reversed at most once) and the aim is to reverse a single edge; on the contrary the game Fill3 is static. A possible approach is: build the corresponding Fill3 game from $P$; "break" the edge that must be reversed (eventually expanding the board) and force it in the final direction using FIXED cells. Then one way is easy: if $P$ is solvable, the corrisponding Fill3 game has a solution (represented by the final configuration of the constraint graph); but the other way is more problematic:

If Fill3 has a (static) solution $s$, can we say that a (dynamic) solution for the corresponding planar bounded NCL problem $P$ always exist (i.e. a sequence of valid edge reversals)? And how to prove it formally?