texts:
Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are broadly the general techniques.

For showing $P=BPP$ or $P\neq BPP$ what strategies can be used or used? It is not like there is one problem in BPP that can either be shown to be derandomized or not be derandomized that solves the question.


texts: Is there a Time Hierarchy theorem for PH?

texts:
Is it true that there are problems in the polynomial hierarchy solvable in time $O(n^k)$ (by an alternating Turing machine in some level of the polynomial hierarchy) that are not solvable in $O(n^{k-1})$ in any level of the polynomial hierarchy?
In other words - does there exist a time hierarchy theorem for the polynomial hierarchy like there does for P and NP?
If there does - a reference would be great.

The difficulty I ran into is that the simulating machine, when simulating machines from all levels of the hierarchy, is not in any distinct level of the hierarchy. Which leads to a related question - what is the smallest class such a simulating machine belongs to? Is there any sense in defining a class with $O(n)$ alternations (or $O(\log n)$ / $O(\log \log n)$)?


texts: How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

texts:
Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once.

For a subset $S$ of nodes and a node $i\in S$, let $D[S][i]$ denote the length of the shortest path within $S$ that ends at $i$.

A common solution to the SHP problem is using dynamic programming for computing $D[S][i]$ for all subsets $S$ and all nodes $i$. If $n$ is the number of nodes then the time and memory complexities of this solution are respectively $\mathcal{O}(2^nn^2)$ and $\mathcal{O}(2^nn)$, which is not feasible for large graphs (having $100$ nodes for example).

However, if the graph is very sparse (e.g. a node has only a few neighbors), then one would expect these complexities to drop significantly would expect the above solution to be practical. I would appreciate a lot if somebody can give me some insights on how to solve/implement the SHP for very sparse graphs. I am looking for practical algorithms/implementations that do not necessarily have lower theoretical complexities and if they can also check if a Hamiltonian path exists before finding the shortest one (and still remaining practical), then that would be great.

Thank you in advance for your help!


texts: Algorithm for K-best NON perfect bipartite matchings

texts:
I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf

It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best.
However, it only looks at perfect matchings. I'm am especially interested in bipartite matchings.

In particular, for the bipartite graphs, the Theorem 1 p. 161 uses the fact that the matchings are considered perfect.

How can I solve the k-best assignment problem for general bipartite graphs?


texts: Complexity of counting graph endomorphisms

texts:
A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An endomorphism of a graph $G$ is a homomorphism from $G$ to itself; it is fixed-point-free if there is no $x$ such that $f(x) = x$ and it is non-trivial if it is not the identity.

I have recently asked a question related to poset (and graph) automorphisms, that is, bijective endomorphisms whose converse are also an endomorphism. I found related work about counting (and deciding the existence of) automorphisms, but searching I couldn't find any results related to endomorphisms.

Hence my question: What is the complexity, given a graph $G$, of deciding the existence of a non-trivial endomorphism of $G$, or of counting the number of endomorphisms? Same question with fixed-point-free endomorphisms.

I think the argument given in this answer extends to endomorphisms and justifies that the case of directed bipartite graphs, or posets, is no easier than the problem for general graphs (the problem for general graphs reduces to this case), but its complexity do not seem straightforward to determine. It is known that deciding the existence of an homomorphism from one graph to another is NP-hard (this is clear as it generalizes graph coloring), but it seems like restricting the search to homomorphisms from a graph to itself might make the problem easier, so this doesn't help me determine the complexity of these problems.


texts:
How can I show that zero-one programming is not in APX?

Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the
zero-one programming problem to Vertex Cover and show that there is no reduction
between these problems?
Where to begin with?
Does someone maybe know a paper with a similar topic?

I would be grateful for any advice.


texts: Non-tomographical certification of projectors, using product states?

texts:
I'm interested in operational ways of demonstrating (with high probability of confidence, in an error-free setting) that a POVM operator on n-qubit states is a projector. Specifically, I'm interested in ways in which one can do so using product states. (I'm more interested in describing it as an analytic characterization of projectors, but I find it easier to describe roughly what sort of characterization I'm looking for in terms of a protocol.) I'm not interested in poly-time approaches per se; just ones which are much better than process tomography.

Preamble.

One way to characterize a projector is process tomography. Given a POVM P, represented as a CPTP map of the form
$$
P(\rho) \;=\; \sum_{j = 1}^m \;\;\mathrm{Tr}(\rho E_j) \;\;|j\rangle\!\langle j|\;,
$$
one may determine whether any particular Er is a projector by collecting statistics on measurement results, e.g. on all n-fold tensor products of the eigenstates of the Pauli X, Y, and Z operators, using these to compute matrix coefficients for Er, and then determine whether that matrix is idempotent. If we are given a promise that Er is either a projector or bounded away from being a projector in some suitable norm, the probability of correctly deducing whether it is a projector then amounts to the confidence in the estimates of the matrix coefficients.

However, if you know in advance that Er is a projector, and you would like to convince someone else that it is, you can certify this somewhat more efficiently if you are able to prepare a complete basis of eigenstates of Er. The outcome Er will never arise for 0-eigenstates, and always will for +1-eigenstates. These eigenstates aren't necessarily product states, of course, but having them as a resource makes it in principle less laborious to give evidence that Er is a projector: it suffices to collect enough statistics to show that it is quite likely that any one eigenstate is indeed an eigenstate (made easier by the extremality of the measurement probabilities). There are only 2n such eigenstates, and the confidence in your estimates converges (and quickly) despite "sampling" fewer states, because of the extremality of the eigenvalues.

Question.

Is there a characterization of projectors, which one may (statistically, as with the eigenstates) verify more succinctly than tomography — and which can be performed with only (input-dependent) product states? If this cannot be done for all projectors in a way which is clearly better than tomography, what are the classes of operators (apart from the class of product projectors) for which there are better approaches?

For instance, this is easy for rank-1 projectors in the case n = 2 (even if we consider qudits of arbitrary dimension rather than qubits), just by using the Schmidt decomposition; we can find a (not necessarily orthogonal) basis for the kernel, and then complete this basis to allow us to estimate the trace of Er and show that its other eigenvalue must be close to 1. But it's not clear how to extend even this simple case to n = 3.


texts: What is the intuition behind "hardness of approximation"?

texts:
I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem.

To my surprise, some closely related NP-hard problems are quite different in terms of approximation.

Can anyone give me some intuition behind this phenomenon?

Thanks in advance!


texts: What are the popular science books that inspire TCS?

texts:
There is a reputation, that in computer science, we do not have popular science books. Of course that's not really true!

(In the same spirit of list of What Books Should Everyone Read?, What papers should everyone read?, What videos should everybody watch? and inspired from Favorite popular math book)

What are the popular science books or resources that inspire CS Theory?

Please have some description about why the book would be nice.


texts: Is there a $c>1$ (maybe $c=2$) such that every lower than rank $n^{1/c}$ graphs on $n$ vertices can be tested to be in polynomial time?


texts: "Divide and conquer" data stream algorithms

texts:
What useful algorithms do there exist that work on huge data streams and also their results are fairly small and one can compute the result for a mixture of two streams by somehow merging their results?

I can name a few:

The obvious things like sum, min, max, count, top-K etc.
Approximate so called "sketch-based" stream algorithms for histograms, counting distinct items or computing quantiles

What others are there?

(I'm interested because I'm writing a hobby project for monitoring distributed systems whose usefulness is directly determined by the usefulness of such algorithms)


texts: Pseudorandom object yielding shrinkage in $\ell_p$ norm?

texts:
Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-U\|_1\leq \epsilon$ where $U$ is the uniform distribution. View the distribution of $X$ as an vector where the value of an entry indexed by $x$ equals $\Pr[X=x]$, then the vector has $\ell_1$ norm $1$. And $\mathrm{Ext}(X,Y)-U$ as a vector, has $\ell_1$ norm at most $\epsilon$.

Expanders have a similar property but for $\ell_2$ norm: Let $A$ be the normalized adjacent matrix of an expander with $\lambda$ the second largest eigenvalue in absolute value. Then $\|Af-f^\parallel\|_2\leq \lambda$ for a vector $f$ of $\ell_2$ norm 1. Here $f^\parallel$ denotes the component of $f$ parallel to $\vec{1}$.

My question is: are there explicit pseudorandom objects with analogous properties (i.e., shrinking the "non-uniformly-distributed" component) for $\ell_p$ norms where $p>2$? More specifically, I am looking for such a property: given a vector $f$ of $\ell_p$ norm 1 as the input, the $\ell_p$-distance between $f^\parallel$ and the output of such objects should be bounded.


texts: Independent set size of a large girth graphs

texts:
For triangle-free (girth $\geq 4$) graph $G$. The following theorem holds true

Theorem (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$,

$$\alpha(G) \geq \frac{n(G)}{8d}\log_2d.$$

Where $n(G)$ is the vertex size of the graph, $d$ is the avg degree and $\alpha(G)$ is the size of maximum independent set.

My Question : Are there extensions of above result for graphs with girth $\geq l$ ?


texts:
Given a graph $G$, what is the minimum number of edges of $G$ that we need to delete to make the graph triangle free? To my untrained eye, this appears to be a difficult problem.

Is this problem known to be NP-complete? What about the analogue for oriented graphs (i.e., digraphs with no parallel edges) and directed 3-cycles? References would be greatly appreciated!

EDIT: David has very helpfully answered my question, in the undirected case, below. Any information on the directed/oriented version would be much appreciated.


texts: Computational Complexity of Ramsey Numbers

texts:
What is the computational complexity of computing Ramsey numbers $(n,m) \mapsto R(n,m)$? Is it inside PH?
Would it be easier to compute $R$ if PH=P?


texts:
It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words acceptance is just a particular case of equational reasoning in term rewriting systems.

My question is, has this approach been developed before? In particular, it would be  interesting to see  if Turing machines can be modelled in this language.

Comments

Someone has suggested regular grammars do model deterministic automata. Maybe it is useful to recall the difference between abstract reduction system and term rewriting system. From "Term rewriting and all that":

  A rewrite rule is an identity $l \approx r$ such that l i not a variable and $Var(l) \supseteq Var(r)$. In this case we may write $l \to r$. A term rewriting system is a set of rewrite rules.

It seems that formal gramars fit better the definition of abstract reduction system:

  An abstract reduction system is a pair $(A,\to)$ where the reduction $\to$ is a binary relation on the set $A$, i.e. $\to \subseteq A \times A$.

For the future I note:

Relationship between Turing Machine and Lambda calculus?


texts: Emptiness of complement of subspace arrangement

texts:
Given $k$ affine subspaces in $\{0,1\}^n$, consider the problem of testing whether their union covers all of $\{0,1\}^n$. What's the complexity of this problem?

P.S.: It seems that this can be reduced to the computation of a characteristic polynomial, which looks like a hard problem. Is there another route?


texts:
Given a directed graph with n nodes such that each vertex has exactly two outgoing edges, and a natural number N encoded in binary, two vertices s and t,

I want to count the number of (not necessarily simple) paths from s to t within N steps.

Is this a #P-hard problem? Or generally, what's the complexity of this problem?


texts: Reduction from SAT to 0,1 integer linear program with zero or one solutions

texts:
Probably this is well known. There is probabilistic reduction
from SAT to Unique SAT (0 or 1 solutions).

According to answer and comments derandomizing the reduction would imply $PH \subseteq \oplus P$.

There is simple reduction from SAT to 0,1 integer linear program with
zero or one solutions.

Given SAT formula $\phi$ on variables $x_1,\ldots x_n$,
introduce binary variables $b_i \in \{0,1\}$.

Define map literals to linear polynomials $f(x_i)=b_i$ and
$f(\lnot x_i)=1-b_i$.

For a clause $l_1 \lor \cdots \lor l_k$ add
constraint $\sum_{i=1}^k f(l_i) \ge 1$.

So far the solutions of the constraints are in one
to one correspondence with the solutions of $\phi$.

To make the solution unique, add the optimization

$$\text{maximize} \sum_{i=1}^n 2^{(i-1)}b_i$$

Two sets of distinct powers of two have equal sums
iff the sets are equal, so the objective function
have unique maximum if the constraints are satisfied.
The ordering of $x_i$ doesn't matter.
So the 0,1 ILP has zero or one solutions and it is
not easier than NP-complete and coNP-complete.

  In what complexity class is solving the 0,1 ILP?

As far as I know ILP are not a complexity class.

$\log_2(n)$ calls to NP oracle would solve it via
binary search, though I don't see a direct reduction to
SAT.

This appears close to UP though there is no certificate.


texts: Adversarial distributions for PAC lower bounds

texts:
The various PAC lower bounds (realizable, agnostic, bounded noise) construct distributions supported on $d$ points, where $d$ is the VC-dimension of the hypothesis class in question.

Does anyone know of any adversarial distributions with support of size greater than $d$ that achieve sharper (i.e., larger) lower bounds than the support-$d$ distributions? We're only talking about constants here, since for agnostic PAC, the excess risk rate is known up to constants (i.e., $\Theta(\sqrt{d/n})$).


texts:
Inspired by suggestion in this question, I've implemented predicative Church encoding of Peano arithmetic. Exponentiation works fine, unfortunately tetration requires the level of one of the arguments to he higher, rendering pentation's type unclear.

This is the code:

module Church where
open import Agda.Primitive

Church : {l : Level} -> Set l -> Set l
Church A = (A -> A) -> (A -> A)

Nat = {A : Set} -> Church A
Nat₁ = {A : Set₁} -> Church A
Nat₂ = {A : Set₂} -> Church A

c0 : Nat
c0 = \s z -> z

c1 : Nat
c1 = \s z -> s z

c2 : Nat
c2 = \s z -> s (s z)

add : Nat -> Nat -> Nat
add a b s z = b s (a s z)

mul : Nat -> Nat -> Nat
mul a b s z = b (a s) z

-- First signs of the type growing:
-- exp : {A : Set} -> Church A -> Church (A -> A) -> Church A
exp : Nat -> Nat -> Nat
exp a b = b a

tetr : Nat -> Nat₁ -> Nat
tetr k n = n (exp k) c1

-- does not type-check
-- pent : Nat -> Nat₁ -> Nat
-- pent k n = n (tetr k) c1

Is Church-pentation implementable in Agda?

This paper: Finitely stratified polymorphism might be relevant.

I learned Agda for this task, so perhaps I don't know how to exploit its power.


texts: Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density

texts:
Say I sample a set of points $(p_1,p_2,...) \in P$ from a probability distribution $f(x,y)$, e.g. a bivariate normal distribution, such that my sampling process chooses a point in the distribution with a probability proportional to the value $f(x,y)$ at that point.  In particular, let's say we use the Metropolitan-Hastings algorithm to sample the set of points $P$ via a biased random walk.

Now, I take $P$, and I apply some arbitrary geometric rotational and translational geometric transform that acts uniformly on all points $p_i \in P$.  I provide this transformed set of points $P^*$ to you, and your job is to reverse the geometric transform and map the coordinates back to their original positions to the best of your ability.

What is the optimal way to proceed?

A thought is that we can sample a new set of points $P_2$ from the distribution $f(x,y)$, and then use something like the RANSAC algorithm (http://en.wikipedia.org/wiki/RANSAC) to find a geometric transform to align the $P^*$ and $P_2$.  This, however, seems to be a bit wasteful?

Motivation - Say we know that the maxima of the distribution $f(x,y)$ occurs at some $(x_k,y_k)$.  What is $(x_k,y_k)^*$, i.e. where is this point after applying the geometric transform that mapped $P$ to $P^*$?  We could also ask about other "distinct" points of interest in $f(x,y)$ so that it isn't simply a matter of computing something like a geometric mean (or perhaps geometric median) of the point set $P^*$ to calculate $(x_k,y_k)^*$.  Can we figure this out without the kind of silly solution I propose the employs the RANSAC algorithm?

(In response to R. B.'s comments): I mean "up to symmetry" here - apologies for the confusion.


texts: Is there an oracle separating Parity-P from PSPACE?

texts: Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?


texts: Question on size of words in Vandermonde Matrix - Vector multiplication complexity

texts:
I am trying to understand how word sizes in a problem affects complexity. The question could be a simple technicality I am trying to clarify since I am not from mainstream CS. Let $V$ be an $n \times n$ fixed Vandermonde matrix and $A$ an $n \times 1$ arbitrary vector. Both $V$ and $ A$ have entries in $\mathbb{Z}$. Both $VA$ and $V^{T}A$ can be calculated in $O(n\log^{a}n)$ multiplications and additions on a fixed word machine ($a$ is a positive constant).

http://www2.cs.uh.edu/~ooo00a/reading/fast_algorithms_with_preprocessing_for_matrix-vector_multiplication_problems.pdf

Does the above complexity result hold when $V$ is generated by a number of size $O(\log^{b}{n})$ bits where $b$ is a positive constant? In this case, the highest number in $V$ is of size $O(n\log^{b}{n})$ bits. Shouldn't this have an impact?


texts: Survey Article on the Theory of Recursive Functions?

texts: Could you recommend a survey article or textbook chapter that introduces the theory of recursive functions? Thanks


texts: Density of black cells in rule 110 cellular automata

texts:
Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell.

Simulation of first 120000 rows of rule 110 shows a quite stable total density of 0.592..., and row-density 0.592...


texts: What is the shape of cost function of weighted graph matching problem?

texts:
According to Umeyama, the weighted graph matching problem can be formulated as

$min_P || PA_GP^T - A_H ||$

s.t. $P$ is a permutation matrix.

where $A_G$ and $A_H$ are n-by-n matrices

If we relax $P$ to be doubly stochastic matrix, how will the cost function looks like?

Concave? Non-convex with multiple local minimums? Or any other shape?


texts: What is a term of the type $\bot\rightarrow A$?

texts:
The sentence $\bot\rightarrow A$ is provable in intuitionistic logic for any type $A$. The proof is trivial:

\begin{align}
\bot&\vdash\bot \\
\hline
\bot&\vdash A \\
\hline
&\vdash\bot\rightarrow A
\end{align}
It means there has to be a lambda term with this type (the type has to be inhabited). What is it?


texts: What is considered significant when applying for a TCS PhD with major changed

texts:
I am a Master student on CS. Actually in theory.
I have a BE in polymer (Chemical Eng stuff), and I struggled somehow to get enrolled in this program.

I want to apply a TCS  PhD in US. So, what do you people think is important that I get to apply to a PhD ?

Perhaps you may value these following options:

published paper ( I am writing a paper on combinatorics )
strong recommend letter
a high score on GRE or GRE sub(math or CS ,U Chig  recommends a math sub as far as I know)
Meet some guys who doing recruiting.

Note that I have 2.0/5 GPA on my BE, so this  really upsets me much.

Hope that this problem could help others desiring to do a PhD in TCS.


texts: Finding optimal subset for quadratic function

texts:
Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a  set $S$ of elements such that $(\lambda - \sum_{e_i \in S}\alpha_i)^2 + \sum_{e_i \in S}\beta_i$ is minimize (for $\sum_{e_i \in S}\alpha_i < \lambda, a_i >0, b_i >0$).
i'm looking for an exact or an approximate polynomial solution (my tries shows that a greedy solution (with respect to $\beta$ or the additional cost does not yield good approximation).


texts: Is there a Quantum equivalent of the Time hierarchy theorem ?

texts:
My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965.

I wanted to know then if there was anything similar for Quantum Computing.

Also, if not what are the people / groups working in this direction!


texts: 2D Cutting Stock Problem for Glass - Details mentioned

texts:
I am trying to work on Cutting Stock Problem. I have seen some algorithm. Can anybody suggest the best 2D cutting stock problem algorithm?

I am looking for kind of best acceptable solution for 2D Glass Cutting problem. The constraints/features for this are as follows: Input to this problem is a set of Large Rectengular Glass Sheets (say approximately 100) with varied Length and Breaths called stocks. Requirement is cut Rectengular Glass pieces out of them (say approximately 200) with varied length and breadth. All (stocks & output sheets) are rectangular. Also,cuts has to be guillotine cuts that mean each cut has to be end to end.

Example of input:Stock (200 X 100 X 10, 200 X 90 X 5, etc), Required Glasses (50 X 50 X 8, 50 X 40 X 8, etc) in format of (Length X Width X No of sheets)

Here is small history of my approach for the problem:
I wrote algorithm which would in following 4 passes:

Pass1: Take One Stock. Create a tree with all cuts possible for all the public required glasses. Also, I could rotate the glass. This step created a huge tree and is exponential.

Pass2: Iterate Pass2 for all the stocks.

Pass3: Iterate each of the tree and covert the problem into ILP problem, as is done for 1D-CSP.

Pass4: Solve the ILP to get the best solution.

The problem with this approach is that at the first step itself the tree becomes so huge for big number of required glasses that it could not be completed in desired amount of time.

Hope this helps, please let me know if extra information is required.

Regards Sandeep Jindal


texts: Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?

texts:
I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different types of edges (hierarchical, non-hierarchical).

I'm new to graph theory and algorithms in general, and I hope that this question doesn't collide e.g. with the research-level requirements of this site. It should however generally be in the scope of cstheory.

The graph would have to be drawn bottom-up (I think), as all tokens should be displayed with the same y-coordinate, and the y-coordinates of nodes grouping tokens and/or nodes into constituents will have to be calculated dynamically, e.g., via their longest path to a token.

Hierarchical edges (used for grouping tokens/nodes into constituents) should have a minimum number of bendpoints (ideally 0), but there should also be a minimum number of crossings, overwriting the former requirement if needs be.

Non-hierarchical edges (used for dependencies) should have a minimum number of crossings, and be drawn as Bézier curves.

The next best thing I have come across is the algorithm described by Buchheim et al., improving Walker's algorithm to run in linear time.

Please do let me know should there be any need to improve my question, and thanks a lot in advance for any pointers.

EDIT:

As pointed out in a comment, I should mention that I basically want a default graph layout by an algorithm, which I - in the long run - want to edit and revise within the Eclipse GEF possibilities. I have previously looked into options to get Graphviz to work with GEF, but there seems to be no working solution that preserves all editing functionality inherited from GEF.


texts: Complexity reductions to Hamiltonian Path?

texts:
I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path.

Do you know such a reduction? Or does there exist a list of reductions to Hamiltonian Path somewhere?


texts: A complexity-class of problems that cannot be solved in finite time

texts:
Is there a complexity class for problems such as the following?
Problem FindSum(s), where $s\in[0,1]$ is a real parameter:
Input: $g: [0,1]\to [0,1]$, a continuous monotone-increasing bijective function, specified by oracles that can answer queries of two kinds:

Given $x\in[0,1]$, what is $g(x)$?
Given $\alpha\in[0,1]$, what is $g^{-1}(\alpha)$?

Output: A point $x_0\in[0,1-s]$ for which $g(x_0) +g(x_0+s)=1$.
The problem definition is somewhat similar to definition of PPAD problems: in PPAD problems, too, the input is given by two complementary oracles ("previous node" and "next node"), and a solution is guaranteed to exist.
However, the problem above considers arbitrary real numbers, as in the Real RAM model. Moreover, it can be proved that the problem cannot be solved by finitely many queries.
One can think of many similar problems. Is there a complexity class for them?


texts: In quantum money schemes, how is the list of serial numbers provided?

texts:
Public key quantum currency generally includes $k$ pairs ($S_\psi,\vert \psi\rangle)$ of classical information (bits) $S_\psi$ and quantum information (qubits) $\vert \psi\rangle$.

In many examples, $\vert \psi\rangle$ is an eigenstate of some publicly known verification procedure $M$, and $S_\psi$ is some (efficiently computable) invariant of $M$.  A bank mints $k$ different coins by initially preparing qubits in a uniform superposition over the entire vector space of $M$, calculating (in ancillas) the invariant $S$, and measuring and recording the ancilla qubits as the serial number $S_\psi$.  That is, the eigenstates $\vert\psi\rangle$ are indexed by the serial number $S_\psi$.

The answer given in this question provides examples of quantum currencies, where not even the bank can produce counterfeit quantum money qubit states $\vert\psi\rangle$.  However, it's not been clear to me how the serial numbers themselves are stored - were they originally meant to be digitally signed?

  Is there a risk in having the bank publish a distributed list amongst users of the currency, in plaintext, of each of the $k$ serial numbers?

There might be an advantage in having a distributed database of plaintext serial numbers.  Users of the currency would know, or at least upper bound, precisely how much currency has been produced, and I don't think that the bank could overproduce without causing a devaluation.  If the bank were to mint more money, they would have to update their plaintext database, and users of the currency would recognize that the money they hold is deprecated.


texts: The number of clauses in an unsatisfiable CNF

texts:
I am interested in generalisations of the following observation:
An unsatisfiable $k$-CNF has at least $2^k$ clauses.
A special case of the observation is when $k=n$, where $n$ is the number of variables. In this case, the clause-variable incidence graph is a complete bipartite graph.
I am particularly interested in the question:
Is there a lower bound on the number of clauses in a CNF $\phi$, in terms of the number of variables of $\phi$, when the clause-variable incidence graph of $\phi$ is $2K_2$-free (i.e. is a bipartite chain graph)?
But I am also interested in any generalisation of that question, or references to papers on questions about CNFs with this extremal flavour.
EDIT: Thanks to Christian Komusiewicz for highlighting that my question was ambiguous. The lower bound I'm after should be a function of the number of variables.


texts:
Consider two paranoid parties Alice and Bob. Say Alice owns a secret vector $x=(x_1,\ldots,x_n) \in \mathbb R^n$ and Bob owns a secret vector $y=(y_1,\ldots,y_n) \in \mathbb R^n$.

Question. How can both parties compute the dot product $x\cdot y$ in time $\mathcal O(n)$ without leaking their respective secrets ?


texts:
Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway.

We have a script as part of an application at work which is responsible for sorting items into bins.  (Sounds simple, right?)

There are X items and Y bins.  Each Item has a Primary, Secondary and Tertiary preferential bin.  It also has an overall rating which corresponds to the item's overall quality, as well as the bin preference (rating is adjusted by -0.5, -1 for decreasing bin preference).

All item's ratings are probably different, and this affects the rating of each bin, and also an overall rating of all bins.

The ordering of items and their preferences into according bins is also important, i.e. Bin A containing Item1 and Item2, may have a different rating overall to Bin B containing Item1 and Item2.

Rules:

Each bin can contain between 1 and 3 items.
Any one item can only appear once in each bin, and can only appear in one bin.

Initially, we thought it was a knapsack problem, or possibly a multiple knapsack problem, but after researching each, we're not sure that any of the common algorithms for that problem fits our task.

We currently brute force it, but given that the Item pool contains 50 items, and the number of Bins is about 10, the runtime for a single bruteforce run is in the order of tens of seconds.  We'd like to get this down to 0.5s

So basically, has anyone come across this problem before, and does it have a name (that we can search academic papers with)?


texts:
Let $P$ be a length-preserving (i.e. $|P(x)|=|x|$)
polynomial-time computable program.

I.
Given two strings $x$ and $y$,
we want to decide if $y$ can be obtained by
repeated applications of $P$ to $x$.
In other words,
is there a $k$ such that $P^k(x)=y$?

II. Given a string $x$,
find the number strings of length $|x|$
which cannot be obtained by repeated applications of $P$ to $x$?

I am looking for PTAS algorithms for these problems.

The first problem is PSpace-complete, see this answer on MO.


texts: Does Descriptive Complexity techniques have the naturalisation barrier?

texts:
I wished to know if the proof attempts at separation of complexity classes via the methods outlined by Descriptive Complexity theorists naturalise?
By naturalise I'm talking about the Idea of Natural Proofs set forth by Razborov and Rudich to set in stone the futility of many of the current approaches to prove lower bounds for boolean circuits.
If one reads up Kolaitis, Vardi, Libkin et al's book on Finite Model Theory and its applications there are intriguing statements like TFAE :

NP $\not=$ coNP

and

For every $s_1$,$\ldots$, $s_k$, $r$, there are finite graphs G and H such that

G is not 3-Colourable and H is 3-Colourable
the Duplicator wins the (⟨$s_1$,$\ldots$,$s_k$⟩,$r$) EF game on G and H.

This is after setting up the logic characterising the class NP and then coming up with the inexpressibility techniques of the EF games.
Problem becomes that this reduces to another hard combinatorial problem, and I was wondering if there is any follow up work that either shows why work along these lines is hard, like say if it could be showed that solving this problem was a natural proof. Then it would be clear to theorists to abandon that line of attack.


texts:
Assume that $C$ is an arithmetic circuit of size $s$ that computes function $f(\vec{x},\vec{y})\in C[x_1,x_2,\ldots,x_d,y_1\ldots y_n]$.

Does it always possible to find a basis $\vec{x}_1,\vec{x}_2,\ldots, \vec{x}_d$ for $C^d$ such that there exists a circuit of size $o(d)s$ which computes $d$ polynomials $f(\vec{x}_1),f(\vec{x}_2),\ldots f(\vec{x}_d)$ in $y_1,y_2,\ldots y_n$?


texts:
I had this question when looking at problem C on this morning's code jam:

Suppose you have a set $S$ and $N$ pairs of subsets $\{S_i^0, S_i^1\}$, $S_i^j\subset S.$

Does there exist a cover of $S$ consisting of (at most) one subset from each pair? Ie, does there exist an $\alpha \in \{0,1\}^N$ with $S=\cup_i S_i^{\alpha_i}$?

Is there a polynomial time algorithm for answering this question? It has a network flow "smell" to it and seems like it's probably a standard problem, but I couldn't find it looking at lists of problems related to set cover.


texts: Average-case randomized communication complexity in the small-advantage regime

texts:
Let $f\colon \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$. I'm interested in randomized communication protocols $\pi$ that compute $f$ in the weak sense that
$$
\Pr_{x, y}\left[\Pr_r[\pi(x, y, r) = f(x, y)]\geq 1/2 + \varepsilon\right] \geq 1/2 + \varepsilon,
$$
where $r$ is the internal randomness of $\pi$ and the inputs $x, y$ are sampled independently and uniformly at random from $\{0, 1\}^n$. What upper/lower bounds are known in this setting? E.g., for the inner product mod 2 function $f(x, y) = \langle x, y\rangle$, are $\Omega(n - \log(1/\varepsilon))$ bits of communication required?


texts: Low-degree testing in PCP Theorem using bivariate polynomials

texts:
I read about modifications of the low-degree test used in the (first) proof of the PCP theorem. The test used in the proof works over randomly chosen lines while modifications allow choosing random planes (or affine subspaces in general). Is it possible to use these modifications in the framework (low-degree extensions and sum-checking) of the proof of the PCP theorem? Does this involve major changes?

EDIT: In the paper [1] by Raz and Safra it is stated that the scheme of the old proof is insufficient when one wants to achieve a sub-constant error. So what if one is satisfied by the "old" constant error? Does the (Hyper-)Plane-Point Test work for that? I have seen proofs using this test to show $NP \subseteq PCP[log(n), polylog(n)]$ but I have never seen the final argument for $NP = PCP[log(n), 1]$ via proof composition.

[1] A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP


texts: Random restrictions and the connection to total influence of Boolean functions

texts: Say we have a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$ and  we apply $\delta$-random restriction on $f$. In addition, say that the decision tree $T$ that computes $f$ shrinks to size $O(1)$ as a result of the random restriction. Does this imply that $f$ has a very low total-influence?


texts: Initial conditions for universal Rule 110

texts:
In A New Kind of Science, Wolfram proves that the Rule 110 cellular automaton can emulate a cyclic tag system, and is therefore a universal computer.

I was wondering what specific initial conditions are used to model basic computations.  For the sake of specificity, my question is--what initial conditions do I have to give Rule 110 if I want to simulate $1 + 1$?

Note:  On page 681, Wolfram provides pictures of "black elements" and "white elements" in Rule 110, but it is hard to tell which initial conditions created them.  On page 1116 (in the "Notes" section), he gives Mathematica code to set up the cyclic tag system.  But I want to know specifically which initial conditions will simulate the computation $1 + 1$.


texts:
Possible Duplicate:
  Do you use any article organizers?

As part of my Ph.D. studies I need to create an overview of recently (since 2000) published papers with impact on my study field.

Creating a list of articles isn't a problem, but what I also want to do is to follow the most cited articles and authors (after I'm done with this).

Is there some tool, that would allow me to store the articles and then simplify the most cited authors/articles search?


texts:
Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete.  What are some other (sufficiently different) natural problems that share this property?  Artificial examples coming directly from the proof of Ladner's theorem do not count.

Are any of these example provably NP-intermediate, assuming only some "reasonable" hypothesis?


texts: Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

texts:
Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, i.e., $p_{ij}\rightarrow 0$ as $n\rightarrow \infty$, if it makes things simpler). We define Bernoulli r.v. $X_{ij}$ such that $X_{ij}=1$ iff edge $(i,j)$ exists. We also assume that $X_{ij}$'s are independent r.v.'s (so the existence of edges are independent events).

We consider a random instance of the graph and define $Z_d=$ number of nodes that are reachable from node 1 via paths of length at most $d$ (we can assume $d=O(\log n)$). Then

$Z_d \leq H_d = \sum_{i\neq 1}X_{1i}+\sum_{i,j\neq 1}X_{1i}X_{ij}+\sum_{i,j,k\neq 1}X_{1i}X_{ij}X_{jk}+\ldots$ (till $d$ levels).

I wanted to know if it is possible to get a concentration inequality for $Z_d$, like

$P(Z_d>cE[H_d]\log n)\leq P(H_d>cE[H_d]\log n)\leq c'n^{-1}$,

where $c,c'$ are constants? ($\exp(-c''n)$ in place of $c'n^{-1}$ would be desirable)

(whether $P(H_d>cE[H_d]\log n)\leq c'n^{-1}$ is possible or not is the concentration inequality for function of independent Bernoulli r.v.'s that I am interested in)


texts: Voronoi diagrams applications where the input order has some known properties?

texts:
Are there applications of Voronoi diagrams or Delaunay triangulations where the order in which the points are generated (and given to the algorithm) have some known properties (e.g. concatenation of points belonging to distinct entities, such as when a data set is the union of several pre-existing data sets)?

More specifically:

Snoeyink and van Kreveld showed that the Delaunay triangulation could be encoded in a "good" order of the points, in such a way that it could be reconstructed in linear time from the coordinates given in this order (and many equivalent orders).
Many other algorithms are known to compute the Voronoi diagram in linear time if the points are "randomly distributed".
I am wondering if in some practical applications, the order in which the points are generated is close to those "good" orders (as in, the concatenation or shuffling of several subsequences in a "good" order).


texts: Efficient verification of Kemeny-optimal rankings

texts:
The problem of finding a Kemeny optimal aggregation is as follows: Given items $1 \ldots n$ and a list of partial rankings $q_i$ (i.e. permutations of subsets) of these items, find a ranking $r$ of $1\ldots n$ that minimizes $\sum_i d(r, q_i)$. Where $d(r, q)$ is defined as a count of the number of pairs on which $r$ and $q$ agree, scaled so that complete agreement is 1 (i.e. scaled by $k(k-1)/2$ where $k = |q|$).

Finding a Kemeny-optimal solution is known to be NP-hard in n (not surprising, it's an optimisation problem on a search space of size $n!$). What I'm wondering is if it's in fact NP-complete - if there's an (efficient?) polynomial time algorithm for verifying if a given ranking is in fact Kemeny optimal. I've seen a paper or two claiming it is, but I've not been able to find any papers which prove it. (Possibly because I live and work outside the academic firewall). Any references / ideas?


texts: Implications of proving NP=RP on complexity theory

texts:
Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, have benefited from them. It would probably be unfair to accept just one one answer in this case.
I apologise if this is off topic. In the paper just uploaded today (Edit: the paper is now withdrawn due to a flaw, see the comments below)
https://arxiv.org/abs/2008.00601
A. Farago claims to prove that NP=RP. From the abstract:
We (claim to) prove the extremely surprising fact that NP=RP. It is achieved by creating a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) for approximately counting the number of independent sets in bounded degree graphs, with any fixed degree bound, which is known to imply NP=RP. While our method is rooted in the well known Markov Chain Monte Carlo (MCMC) approach, we overcome the notorious problem of slow mixing by a new idea for generating a random sample from among the independent sets.
I am not an expert in the complexity hierarchies, why is this thought to be so surprising?
And what are the implications, if the claim is correct?


texts:
It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in exponential time (for example, less than $2^n$ steps with only polynomial space)?
E.g. in what time and space we can find a tour whose distance is at most $1.1\times OPT$?


texts:
We are given an array of variables $A$, along with a matrix $M$.  The elements of the matrix $M$ are composed of sums of the variables in $A$.  We are allowed to pre-process $A$ in order to find a quick way to obtain the entries of $M$ - in other words, the fastest way to obtain sums of the variables in $A$.  We do know which variables we must use for each sum in advance.  Also, the matrix rows follow the rule that each element of the array will be used in exactly one sum in each row of the matrix.

So, for example, we are given the array:

$$(x_1, x_2, x_3, x_4, x_5)$$

Then, we are given a matrix:

$$\begin{pmatrix}
x_2 + x_3 & x_1 + x_4 + x_5 \\
x_1 + x_2 + x_5 & x_3 + x_4 \\
\end{pmatrix}$$

We are allowed to pre-compute using as many resources as we like.  The goal is to get a circuit that computes the sums of the matrix using as little resources as possible (but with as much pre-computation as one wants).

The matrix will be an $n/\alpha \times \alpha$ sized matrix of non-negative integers less than $\alpha$, with $\alpha \approx \log \log \log n$.  The array will contain $n$ elements.

I'm wondering how well we can do in the worst case or in the average case.


texts:
On MathOverflow, Timothy Gowers asked a question titled "Demonstrating that rigour is important".  Most of the discussion there was about cases showing the importance of proof, which people on CSTheory probably do not need to be convinced about.  In my experience proofs need to be more rigorous in theoretical computer science than in many parts of continuous mathematics, because our intuition so often turns out to be wrong for discrete structures, and because the drive to create implementations encourages more detailed arguments.  A mathematician may be content with an existence proof, but a theoretical computer scientist will usually try to find a constructive proof.  The Lovász Local Lemma is a nice example [1].

I would therefore like to know

  are there specific examples in theoretical computer science where a rigorous proof of a believed-to-be-true statement has led to new insight into the nature of the underlying problem?

A recent example that is not directly from algorithms and complexity theory is proof-theoretic synthesis, the automatic derivation of correct and efficient algorithms from pre- and post-conditions [2].

[1] Robin A. Moser and Gábor Tardos, A Constructive Proof of the General Lovász Local Lemma, JACM 57, article 11, 2010. http://doi.acm.org/10.1145/1667053.1667060
[2] Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster, From program verification to program synthesis, ACM SIGPLAN Notices 45, 313–326, 2010. http://doi.acm.org/10.1145/1707801.1706337

Edit: The kind of answer I had in mind is like those by Scott and matus.  As Kaveh suggested, this is a triple of something people wanted to prove (but which wasn't necessarily unexpected by "physics", "handwaving", or "intuitive" arguments), a proof, and consequences for the "underlying problem" that followed from that proof that weren't anticipated (perhaps creating a proof required unexpected new ideas, or naturally leads to an algorithm, or changed the way we think about the area).  Techniques developed while developing proofs are the building blocks of theoretical computer science, so to retain the value of this somewhat subjective question, it would be worth focusing on personal experience, such as provided by Scott, or an argument that is backed up by references, as matus did.  Moreover, I'm trying to avoid arguments about whether something qualifies or not; unfortunately the nature of the question may be intrinsically problematic.

We already have a question about "surprising" results in complexity: Surprising Results in Complexity (Not on the Complexity Blog List) so ideally I am looking for answers that focus on the value of rigorous proof, not necessarily the size of the breakthrough.


texts:
Let $L$ be a decidable language. Let $X^L$ be the set of deterministic Turing machines which decide $L$. Define two machines $A,B\in X^L$ to be time-equivalent if $t_A(w) = t_B(w)$ for all $w \in \Sigma^*$. Define a metric on the set of equivalence classes as folows:
Let $R>0$ be some big number. $d(A,B) = \sup_{w\in \Sigma^*} | t_A(w) -t_B(w)|$ If this number is bigger than $R$, set $d(A,B) = R$. This defines a complete metric space on the set of equivalence classes of $X^L$.  Let $f:X^L \rightarrow X^L$ be the function which to each equivalence class of dTM maps it to its "linear speedup-theorem"-Machine. Suppose that for each machine $M$ we have: $t_{f(M)}(w) = 1/2 t_M(w) + |w| + 2$. Then this map $f$ is a contraction. By the banach fix-point theorem there must exist an equivalence class $M$ such that $f(M) = M$ . But then $t_M(w) = t_{f(M)}(w) = 1/2 t_M(w) + |w| + 2$ and we get $t_M(w) = 2 |w| + 4$. However this seems very absurd. Does it contradict something known? The only assumption which I made is that we have equality instead of $\le$ in the linear speedup theorem.


texts: Min weight perfect matching with even number of red edges

texts:
Consider a weighted graph with some red edges.
We are interested in finding a perfect matching, such that the number of red edges is even, and under the previous constraints, the weight is minimized.

Is this problem solvable in polynomial time? Even for bipartite graphs?

What about a natural extension. The case where there is a constant number of colors, and the number of edges of each color in the matching must be even.


texts: What are the pros and cons for type cases in dependent type theories?

texts:
Pattern matching on $\cal U$ is allowed in XTT and Idris2 (for unerased types), and that implies the injectivity of type constructors (that's just my intuition, though -- I also wonder how do I prove that?).
I wonder how this feature work in the underlying model of type theories and how do they affect programming in dependent type systems. It seems that $\cal U$ will then become an inductive type, and formation rules are turned into introduction rules...


texts: Best algorithm for inversion of symmetric positive-definite matrices

texts:
As I know, the time complexity for usual inversion algorithm of general matrix is $O(n^3)$. In recent years, there is a improvement from $O(n^3)$ to $O(n^{2.8....})$. However, does there exists a faster inversion algorithm for symmetric positive-definite matrices? I have tried to search the answer but the best answer I have seen is to inverse the symmetric positive-definite matrix by using Cholesky decomposition. However, its complexity is also $O(n^3)$.

Could you provide me the fastest algorithm (even only the name) for inversion of symmetric positive-definite matrices?


texts:
I was researching about zero-knowledge proofs and in this link http://web.mit.edu/~ezyang/Public/graph/svg.html I've seen the exercise question:

Currently, you can only select adjacent pairs of nodes to check. Would the proof still be zero knowledge if you could pick arbitrary pairs of nodes to check?

I think it would still be "zero knowledge" because it shouldn't leak information to verifier, but there won't be a proof if you select non-adjacent pairs since the reveal phase doesn't prove anything. Is this a trick question?


texts: What characterizations exist for the grammars that can express subsets of the context-free languages?

texts:
It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$.

I'm wondering, what results are known about classes of grammars that can generate the languages accepted by other restricted versions of pushdown automata?

In particular, I'm interested in:

Pushdown Automata with a bound on the number of reversals the stack can make.
Pushdown Automata with a unary stack alphabet (i.e. counter machines)


texts: Efficiency of building orthogonal range search structures?

texts:
I've been reading up on data structures for 2D range searching. I've noticed that, in many of the papers I've read, there's close attention paid to the query cost and the space usage required, but often there isn't much discussion about the time required to build the data structure. For example, the paper Orthogonal Range Searching on the RAM, Revisited by Chan et al mentions these space/query time bounds:

Textbook description of range trees implies a solution with $O(n \log n)$ space and $O(\log n + k)$ query time, where $k$ denotes the output size of the query (i.e., the number of points reported). Surprisingly, the best space–query bound for this basic problem is still open. Chazelle gave an $O(n)$-space data structure with $O(\log n + k \log^\epsilon n)$ query time, which has been reduced slightly by Nekrich to $O(\frac{\log n}{\log \log n} + k \log^\epsilon n)$. (Throughout the paper, $\epsilon > 0$ denotes an arbitrarily small constant.) Overmars gave a method with $O(n \log n)$ space and $O(\log \log n + k)$ query time. This query time is optimal for $O(n \log^{O(1)} n)$-space structures in the cell probe model (even for range emptiness in the rank-space case), by reduction from colored predecessor search. Alstrup, Brodal and Rauhe presented two solutions, one achieving $O(n \log^\epsilon n)$ space and optimal $O(\log \log n + k)$ query time, and one with $O(n \log \log n)$ space and $O(\log^2 \log n + k \log \log n)$ query time, both improving Chazelle’s earlier data structures with the corresponding space bounds.

Here's another example from the recent paper New Data Structures for Orthogonal Range Reporting and Range Minima Queries by Nekrich:

According to the lower bound of Pătrașcu, any data structure that consumes $O(n \cdot polylog(n))$ space requires $\Omega(\frac{\log n}{\log \log n})$ time to answer four-dimensional
queries; this lower bound is also valid for emptiness queries.

I did notice, however, that in Chazelle's A Functional Approach to Data Structures and its use in Multidimensional Searching he mentioned that the data structures he proposes all take time $O(n \log n)$ to construct.
Based on what I'm reading, I'm assuming that one of the following is true:

The papers I'm reading are mostly in a vein of research that specifically is looking at cell-probe lower bounds for space usage with the goal of seeing whether it's possible to build any data structure at all, regardless of construction efficiency, that meets the given query times.
I'm skimming these papers too quickly and if I were to read more closely I would see that, indeed, the construction times are listed there plain as day.
I'm totally new to this field and am missing something obvious. :-)
There hasn't been much interest in data structure construction time, so people haven't been focusing too much on it.

My guess is that it's a mix of (1), (2), and (3) and that (4) is probably false. However, I figured it would be good to ask in case anyone had any advice or guidance to offer.


texts: Evaluating the expected value of negatively correlated random variables

texts:
A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, X_n) \in \mathbb{Z}(\mathcal{P})$, $(X_i \in \{0,1\})$:

   $\mathbb{E}[X_i]=x_i$, for all $i \in [n]$.

  For any $S \subseteq [n]$, $\mathbb{E}[\prod_{i\in S} X_i] \leq \prod_{i \in S} x_i$ and $\mathbb{E}[\prod_{i\in S} (1-X_i)] \leq \prod_{i \in S} (1-x_i)$ (negative correlation).

An example is the dependent randomized rounding by Chekuri, Vondrak, and Zenklusen (http://arxiv.org/pdf/0909.4348v2.pdf).

We focus on the dependent randomized rounding. Given a point $x \in \mathcal{P}$, where $\mathcal{P}$ is a matroid polytope, let us assume that $X$ is the outcome of the random process (the dependent randomized rounding). Can we evaluate the value of $Pr\Big(\displaystyle \bigwedge_{i \in S} X_i=1 \Big)$  for some $S \subseteq [n]$? Shall we use sampling for this purpose?

That would be great if you can comment on this.


texts: What algorithms exist for construction a DFA that recognizes the language described by a given regex?

texts: All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, convert the NFA into an equivalent DFA (optionally minimizing the DFA). I also once heard a professor allude to there being other algorithms. Does anyone know of any? Perhaps one that goes directly from the regex to a DFA without the intermediate NFA?


texts: Approximation results on scheduling under an uncommon constraint

texts:
I am looking for any approximation results for unrelated multiprocessor scheduling problem with precedence constraints (minimizing makespan), i.e. $R|prec|C_{max}$, with the constraint that some tasks need to run together on the same processor. I searched a lot and the closest constraint I could find was that some tasks have to run on certain processors. I need to group tasks in classes such that each class must run on the same processor. Note that the precedence constraints prevent collapsing each class into a single big task.

I would like to find any literature on the problem  (or any non-trivial relaxation, for example removing the precedence constraints will allow the classes of tasks to be treated as one task).


texts: Finding the closest pair between two sets of points on the hypercube

texts:
Given two subsets of the $d$-dimensional hypercube (i.e., $M, N \subseteq \{0,1\}^d$), I am looking for an algorithm which retrieves the points $m\in M, n\in N$ s.t. the hamming distance (or $L_1$-distance on the hypercube) $d_H(m,n)$ is minimal. The naive algorithm which checks just each pair needs $|M|\cdot |N| \cdot d$ time, is there any better result known?

For simplicity we may assume that $|M|=|N|=d$.


texts:
I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help.

My question is whether it is known that deciding whether a number is transcendental is undecidable.

Possibly, one assumes as input, say a program that returns the i^th bit of the number.
Thanks in advance for any pointers.


texts:
A string has $2^n$ subsequences, but they are usually not all distinct. What is the complexity of finding the maximum frequency of any subsequence?

For example, the string "subsequence" contains 7 copies of the subsequence "sue" and this is the maximum.

Sample brute-force code at http://ideone.com/UIp3t

Are there related structural theorems? Both of these turn out to be false:

the longest of the maximum-frequency subsequences is unique
the maximum frequency of any length-$k$ subsequence is unimodal in $k$

Possibly related links:

Counting # distinct subsequences $\in \mathbf{P}$ http://11011110.livejournal.com/254164.html
Related contest problem for multiple sources http://www.spoj.pl/problems/CSUBSEQS/
Related paper http://dx.doi.org/10.1016/j.tcs.2008.08.035

Edit 10 days later: thanks for taking a look! I had wondered if this would make a nice polynomial-time solvable programming contest problem. I guess not, but I hope to think about it again later.


texts: Minimal set of Hyperrectangles covering an n-dimensional binary matrix with row permutations

texts:
My input is a n-dimensional binary matrix.

My goal is to find the set of Hyperrectangles that covers every '1' at least once and covers not a single '0', which has minimal cardinality (the least amount of Hyperrectangles). The Hyperrectangles may overlap.

Before defining each next Hyperrectangle, I'm allowed to permute the 'rows' (along one or more dimensions) of the matrix.

An approximation algorithm will do, as long as it is always correct.

Is this problem reducible to some well-researched problem?


texts: Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?

texts:
Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so that
(1) G' is a DAG,
(2) all nodes are reachable from s in G', and
(3) the sum of the weigh of the arcs in E' is maximal.

Has anyone seen/studied this problem?


texts:
Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.

Is there a survey/lecture notes describing generalizations of LP that can be solved in poly time?

This is related to this question, but the questions in that post are quite different and most of the questions have not been answered.


texts: Determine the complexity class of a language

texts:
Let $L'$ be the language containing all the pairs $(G,v)$ where $G$ is a directed graph and $v$ is a vertex in $G$ such that $G$ contains a cycle (i.e. closed walk) that contains $v$ and the number of different vertices that appear in that cycle is odd.

What is the complexity class of $L'$? Can it be in $NL$?


texts:
A newbie question, if I may... Could you be so kind and explain to me in plain english meaning of 'denotational semantics' and 'operational semantics'? I'm familiar with the definitions and have read a lot of other material, but still struggling with these concepts. Probalby I need some use cases... or a practical exercise :)

How to define denotational and operational semantics for a given programming language? Can it be done for any language or there are any prereqs? What is the usual approach: if I have a description of a PL, for instance, how to build these two semantics for it? What should I start with? What should I get at the end of the exercise?

Many thanks...


texts:
Define $\Pi_k \text{SAT}$ by 'Given a quantified boolean formula $\varphi = \forall y_1\exists y_2\dots Q_ky_k\mbox{ }\phi(y_1, \dots, y_k)$,
where $\phi(y_1, \dots, y_k)$ is boolean predicate with each $y_i$ a vector of variables, $Q_{2j-1} = \forall$ and $Q_{2j} = \exists$ at every $j\in\mathbb N$, is $\varphi$ valid?' (page $99$ in Arora book).

$ETH$ says $\text{SAT}$ and so $\Pi_1\text{SAT}=\overline{\text{SAT}}$ needs $\Omega(2^{c\cdot n_1})$ time at some $c>0$ where $n_1$ is number of variables in $y_1$.

If there are $n=n_1+\dots+n_k$ variables where each $y_i$ has $n_i$ variables then

what is the best known algorithm for $\Pi_k \text{SAT}$ at each fixed $k$?
Is there a generalized $ETH$ that applies to $\Pi_k\text{SAT}$?


texts: Products of PSD matrices that equal an orthogonal matrix

texts:
You have k symmetric real n-by-n matrices A_1...A_k, each bounded by some parameter eps < 1/2 in spectral norm.

You know that the product (Id+A_1)(Id+A_2)...(Id+A_k) equals an orthogonal matrix Y.

What can you say about the norm of A_1+...+A_k?  (any norm - frobenius, spectral, something else).  note that if n=1 (the scalar case) then clearly it's bounded by O(k eps^2) (by passing from (1+A_i) to exp(A_i+O(A_i^2)), then solving a trivial equation).

what can you say about the distance of Y from being the identity matrix (e.g. how low can the trace of Y be?)


texts:
One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a symmetric matrix. However, to get it's shape, you'd need a collection of row/column permutations, which makes a matrix a little less suited. It's also a bit harder to 'see' the graph, once it's in that form.

My question is: Are there any 'graphical' algebras that can describe the 'shape' of graphs?

What I'm thinking of is what kinds of formal systems that algebraic topologists tend to come up with. In particular, things like the algebra for knot invariants, or notational systems like operads or polygraphs. These kind of 'doodle algebras' are not nearly as well developed, so perhaps there is a reason to believe that no such algebra exists for graphs, but I'd though I'd ask before assuming otherwise.

UPDATE:

My question is probably very narrow and not immediately answerable with a 'yes', so if the moderators don't mind, I'll broaden it by asking:

Are there any existing systems (the kind I describe above) that could be adapted (easily or otherwise) to create such a system? If there's more than one, feel free to mention all of them. And throw in the ones already mentioned as well.

Motivation

My motivation for such a question is actually about classifying asymmetric graphs. I'm only an undergrad, so my review of the current state of algebraic graph theory is pretty thin. But I've yet to see much, if any, work in trying to systematically describe all graphs in an algebraic way, and in particular, one that uses visual metaphors over symbolic ones.

Practical example where such a system would be useful

Suppose one wants to describe a proof that all Eulerian graphs must have vertices of even degree. A standard proof usually uses arguments about even and odd degrees, without mentioning the actual edges used. A typical student would find such a proof for the first time, and probably begin drawing graphs, attempting to convince himself of the argument. But perhaps a better tool than the pure 'logical' argument, would be to show that any collection of 'symbols' from such a language could not satisfy some 'completeness' condition.

Yeah, I know, I'm being hand-wavy at this last part.. If I wasn't, though I'd probably start creating such a system myself!

But ignoring my vagueness for a moment, I get a sense that many of the old and well known theorems in graph theory are not difficult but require some conceptualization that a really good framework could 'tie up' and 'package' into a unified view.


texts: The dependence of learning generalization bounds on the dimension of the instance space

texts:
Here is a popular generalization bound:

  If $X$ is the input space and
  $Y=\{0, 1\}$ is the output/label space, and
  there is a joint distribution $D$ defined on this space.
  We sample $m$ points from this joint distribution as observation/training data:
  $S = ((x_1, y_1)\ldots(x_m,y_m)) \in (X\times Y)^m$.
  Suppose $H$ is a class we (user) are choosing from, and $h \in H$.

  Define the risk (true expected error) as
  $$L_D(h) := \Pr_{(x,y)\sim D} [h(x)\neq y]$$
  the empirical risk as
  $$L_S(h) := \frac{1}{m}\sum_{i=1}^m l(h,z_i)$$
  where $z_i = (x_i, y_i)$.

  Then, with probability of at least $1 − \delta$ we have
  $$\forall h\in H, L_D(h) \leq L_S(h) +
c\sqrt{\frac{VCdim(H)+ \log(2/\delta)}{2m}} $$

Question:
Any intuition why the dimension of instance space $X$
and its size $|X|$ do not come into play in this inequality?
Intuitively the bigger the dimension is,
the harder the estimation problem should be.
(E.g. $X = \mathbb{R}^d$,
$|\mathbb{R}|=\infty$ should be harder than $|\{x\}|=1$.)


texts: Verifying the minimum degree of a geometric predicate

texts:
Let $F = (f_1, \ldots, f_n)$ be a sequence of multivariate polynomials $f_i : \mathbb{R}^d \to \mathbb{R}$, and $g : \{0,1\}^n \to \{0,1\}$ a boolean function.  Say the composition
$$h(x)=g(f_1(x)>0,\ldots,f_n(x)>0)$$
answers some useful geometric question (e.g., is the intersection of two circles inside a third?).  Let $\deg(F) = \max_i \deg(f_i)$ be the maximum degree of any of the polynomials.

Question: Is there an algorithm to check whether $\deg(F)$ can be reduced without changing $h(x)$?  Are there practical implementations of such (perhaps in Mathematica or Sage)?

I believe this is essentially a question of polynomial irreducibility, and the answer may be as simple as checking whether the highest degree $f_i$s factor.  However, since the answer may be simply be "yes, it's minimal", I want to be sure before I publish such a claim.


texts: Is there a rule-based implementation of weighted abduction other than the PTTP?

texts: Is there an implementation of weighted abduction other than the PT theorem prover? A Google search reveals the PTTP and a few statistical approaches but I'm interested in a rule-based approach. The PTTP is too slow with large knowledge bases. Since I couldn't google up anything useful I guess there's none (maybe statistics is the way to go as abduction is intractable) but maybe someone knows of an alternative in a different branch of logic programming (such as ASP).


texts: Is there a name for this concept in Communication Complexity?

texts:
Let Alice and Bob compute boolean function $f(x_1,\dots,x_{2n})$.

Select a random subset $\mathcal I\subseteq\{1,\dots,2n\}$ of cardinality $n$ and let $\mathcal J=\{1,\dots,2n\}\backslash\mathcal I$.

Let Alice get variables $x_i$ where $i\in\mathcal I$ and Bob get $x_j$ where $j\in\mathcal J$.

Let communication complexity of this function under this partition be $CC_{\mathcal I,\mathcal J}(f)$

Define $$cc_{min}(f)=\min_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$
$$cc_{max}(f)=\max_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$

Is there a term for $cc_{max}(f)-cc_{min}(f)$ and $\frac{cc_{max}(f)}{cc_{min}(f)}$?

Is the related concepts introduced and studied anywhere?

I am also interested in scenarios where $|\mathcal I|\neq\mathcal J|$ under condition $||\mathcal I|-\mathcal J||\leq \log n$.


texts: What is a "level-r pseudo expectation functional"?

texts:
In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction that expectation of a square of a function is guaranteed to be zero only when the function is a polynomial of degree $\leq \frac{r}{2}$

Is the above right?
So the polynomials on which one would take the "level-r pseudo expectation functional" are what are to be called "level-r fictitious random variable" ?
Conventionally in optimization questions one would say something like "maximize $P_0$ given that $P_i^2=0$ for $i =1,2,..,m$" but the ``r-round SOS SDP relaxation" of this same question would be to choose a "level-r pseudo expectation functional" say $\tilde{E}$ and say "maximize $\tilde{E}[P_0]$ given that $\tilde{E}[P_i^2]=0$ for $i =1,2,..,m$ for $deg(P_i) \leq \frac{r}{2}$"

Is the above right?
And if so then how is a specific $\tilde{E}$ chosen to do the relaxation?


texts: A self-contained proof that OrdHorn relations are tractable?

texts:
I'm currently investigating a family of temporal relations called 'Ordered Horn' ($OH$ for short). This class was introduced in 'Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra' by B. Nebel and H.J. Bürckert. Following this paper, we define an OH clause as a formula over $\mathbb{N}^k$ of the form:

  $F_{H,R}(x_1,\ldots,x_k) = \wedge_{(i,j) \in E(H)} (x_i = x_j) \Rightarrow (x_p R x_q)$,

  for a given graph $H$ on $[k]$ and a relation $R \in \{=,\leq,\neq\}$.

An OH relation is then a conjunction of OH clauses. The authors state in Theorem 5 of the paper that the satisfiability of an OH relation can be decided in polynomial time, but the algorithm doesn't seem 'self-contained' as it relies on a generic algorithm for propositional Horn theories.

In relation to a problem I'm currently studying, such a self-contained algorithm seems desirable but it's unclear to me whether it is possible. To tell the truth, I have an algorithm for a subclass called Restricted Ordered Horn (containing the relations expressible using clauses without $\neq$ in the rhs) but unfortunately it can't be adapted to the full $OH$ class.


texts: Papers on fault handling in distributed systems

texts: What papers on handling errors in distributed systems do you recommend?


texts: Decomposing Graph Flow (Solution exists?)

texts:
I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an "in-flow" and an "out-flow" from and to its neighbor nodes respectively.

Each edge $e_{i,j}$ represents a traffic out-flow from $i$ to $j$. For example, an edge weight of $50$ might mean that 50 cars traveled on that road (in the specific direction represented by the edge). Suppose that I know the flow for each road (in other words, I know all the edge weights). I am interested in calculating the following quantity:

I want to know the number of cars that traveled from $i \rightarrow j \rightarrow k$. So of all the cars that traveled from $i \rightarrow j$, I want to know the number of cars that also traveled from $j \rightarrow k$. Can this problem be solved?  Could we add certain assumptions to make the problem feasible?  For example, if I assume that the net flow at each node is 0, in other words, $\sum_j e_{i,j} = \sum_j e_{j,i}$ (a circulation).

Here's an example graph that my problem might have. Can I calculate the number of cars that traveled from $1$ to $2$ and then to $4$? What modifications can I possibly make to be able to do this? This graph is simplified and the general case is a little more complicated to describe here.

If we consider only the path $1 \rightarrow 2 \rightarrow 4$ then of the 10 cars that travel from $1 \rightarrow 2$, let $x_1$ go back from $2 \rightarrow 1$ and the remaining $x_2$ go from $2 \rightarrow 4$. Similarly, of the 3 cars going from $4 \rightarrow 2$, let $y_1$ go back from $2 \rightarrow 4$ and the remaining $y_2$ go from $2 \rightarrow 1$. The total flow from $2 \rightarrow 1$ and $2 \rightarrow 4$ is the sum of the constituent flows as contributed from node $1$ and node $4$. We can then setup the following equations:
$$ x_1 + x_2 = 10, \\ y_1 + y_2 = 3, \\ x_1 + y_2 = 5, \\ x_2 + y_1 = 8, \\ x_1, x_2, y_1, y_2 \geq 0.$$

This system of equations has many feasible points. Anybody see some constraints etc. that I can add to make the solution unique ?


texts:
Recently I have some dispute with my colleagues and would like to clarify the following question.

It is clear what are "ranked" trees. They are those, which produced by tree grammars, where each symbol in their finite alphabets (terminals and non-terminals resp.) has an arity or "rank", which specifies number of possible children. So for terminals it is always "0", while for non-terminals it is always $\geq 1$.

But what should we consider by "unranked" trees?

In my understanding, as some papers state (I don't have references right now), an unranked tree is produced by a tree grammar where there are no restrictions on the rank for non-terminals. I.e. alphabets are not ranked anymore. And that's all (I don't want to go deeper into the formal details and definitions).

Basically in my understanding, each XML document is generally an unranked tree.

So what my colleague states, is that the "unrankness" necessary implies a kind of "unboundness" of children inside each node. In other words, if a tree grammar specifies a certain finite set of "ranks" for each non-terminal, then trees produced by such a grammar are not unranked.

The difference between my understanding and my opponent's one, is that my definition seems to be more soft and general. So I can say that any XML document is an example of an unranked tree. My colleague's definition restricts it, so not each XML document will be unranked, but only that satisfying an XSD schema which contains some unbounded lists.

So, who is right?


texts: Dynamic planar exact k-nearest neighbors for pathological data

texts:
What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space:

$insert(x)$
$delete(x)$
$nearest(k,x)$ (where $k$ is an integer greater than 0) returns the $k$ closest points to $x$ that are in the set.

In this particular case, I'm not particularly interested in approximate nearest neighbor, Monte Carlo algorithms, or algorithms that assume the data is well-formed in some way.

I am not as prejudiced against Las Vegas algorithms, algorithms that assume the coordinates of the point have $O(\lg n)$ bits, or algorithms with running time depending on $k$.


texts: Classification of Typed/Untyped Lambda Calculi

texts:
Can anyone explain briefly (if thats possible!) or refer me to a reference, summarizing the differences between untyped lambda calculus and the more common typed lambda calculi?
I'm particularly looking for statements of their expressive power, equivalences to logic/arithmetic systems or computation methods, and analogies to programming languages if applicable.
While I certainly intend to read, something like a reference table outlining the calculi and their equivalences/differences/place in the hierarchy would be a HUGE reference for helping me sort them out.
Not saying the below is correct, just trying to sketch together some of the impressions i have to see if they at least serve as a starting point (or something to correct!)

Untyped lambda calculus - eq. to first order logic - cannot do X
Simply typed lambda calculus - eq to ... logic, related to Lisp?
'Polymorphic' lambda calc -
etc.
Calculus of Constructions - intutionist logic?
Combinatory Logic - comparable to ??? typed lambda calculus, related to APL/J kind of languages

If this ties into the lambda cube and its three axes all the better.
While I'm familiar with the basics of lambda calculus and programming with functional languages, I have never wrapped my head around, or made any significant connections to, the type systems involved and different flavors of lambda (and maybe pi?) calculi.
When I attempt to research this i cant help but find myself sidetracked, opening up many browser tabs and branching in so many directions I never get into any of them with any depth!
I'm not sure if what I'm asking for is reasonable, but hopefully at the very least I've painted enough of a picture to suggest some reading that can explain what im looking for?


texts: Is there a simple, intuitive explanation for why trees in Fibonacci heaps have the sizes they do?

texts:
Fibonacci heaps have a simple rule that ensures its tree sizes grow exponentially with their ranks:

  A node can lose at most one child. Once that child is lost, the node must be cut from its parent.

I'm comfortable with the proof that a tree in a Fibonacci heap of rank $r$ has at least $F_{r+2}$ nodes, and can prove it cleanly use induction.

However, I don't have any intuitive understanding as to why the above rule would give rise to Fibonacci numbers this way. The "default" shape of the trees in a Fibonacci heap is given by the binomial trees, which have lots of nice mathematical properties but none that (immediately) seem like they'd translate into Fibonacci numbers after nodes are lost this way. The best guess I have is that this somehow relates to writing Fibonacci numbers as sums of diagonal binomial coefficients, but I don't see a way to connect that sum to the trees produced this way.

Is there a simple, intuitive, and, most importantly, non-inductive explanation as to why the marking rule in Fibonacci heaps would give rise to Fibonacci-sized trees?


texts:
Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue of $H$ is either $\leq a$ or $\geq b$, with $b-a$ vanishing as an inverse polynomial in the size of the original problem. If the gap vanishes faster, the problem is not known to be in QMA, and if the gap is larger the problem is easier.
I read often, for example in wikipedia, that for constant gap QMA-hardness is a conjecture (equivalent to a quantum version of the PCP theorem). However, I sometimes read the opposite: for example Gharibian's phd thesis problem 1.7, or Gosset, Nagaj definition 4 for the qsat subcase.
Effectively, I don't understand why I cannot repeat each term in $H$ a polynomial number of times, and obtain an equivalent problem with constant gap. Is this reasoning naively wrong, or maybe I am not reading the PCP statement correctly. Maybe "constant gap" is just a fast way to say something more specific?
PS. I posted this on the quantum computing board too, where is probably more inherent. I noted the board after posting here, let me know if I have to cancel this.


texts: Important papers and open problems in Boolean functions

texts:
I am interested in Boolean function polynomial/rational exact/approximate/one sided approximate representation, relation to circuit/communication complexity, tools utilized to study Boolean functions (such as combinatorics, analysis, approximation theory, algebra etc).

What are some of the important references, lecture notes and key papers (including survey) in the field of Boolean functions for someone wanting to learn the growth of the area from 80s till today.

Even open problems in the area would be a good introduction as one can usually trace back the literature. One important open problem is sensitivity-block sensitivity conjecture.


texts: State transducers for generating permutations

texts:
Let a finite alphabet $\Sigma$.

Let $\mathcal{Reord_\Sigma}$ be the family of computable partial functions between the strings of this alphabet $r\,:\, \Sigma^*\, \rightarrow \Sigma^*$ with the restriction that the value must be a permutation of the argument.

I'm interested in a class of deterministic abstract machines with finite control that compute all and only the functions of this family. That is, given a string $s \in \Sigma^*$ as input, the machine either doesn't halt or halts returning a permutation of $s$, and every possible mapping of those is realized by some machine in the class.

All the transitions should be local (no random access on a tape), and possibly they should not explicitely name the symbols to be written (they should be 'copy' or 'swap' operations, not 'write symbol "A" ').

Does this class of transducers exist? Has it been researched?


texts: Finding the penumbra of a Constraint Satisfaction Problem

texts:
The following question has come up a number of times when testing the security of a system or model.

Motivation: Software security flaws often come not from bugs due to valid inputs, but bugs resulting from invalid inputs that are sufficiently close to valid inputs to get past many of the straightforward validity checks. The classic example is of course buffer overflows, where the input is reasonable, except that it is too large. Compilers and other tools can help address these problems by modifying the layout of the stack and heap and by other obfuscation techniques. An alternative is to remove the problems from the source code itself. One technique called fuzzing bombards the program with inputs are close to expected inputs, but are in some places unreasonable (large values for integer or string fields). I would like to understand fuzzing (as one example) from a more formal perspective.

Assume that the space of valid inputs is described by constraints $\Phi$. Let $M$ be the set of solutions of such constraints, namely  $M=\lbrace m\in\mathcal{M}~|~m\models\Phi\rbrace$, where $\mathcal{M}$ is the space of possible inputs.

I'm looking for work describing the following notions:

The penumbra of $M$ is a set $M'\subseteq \mathcal{M}$ such that for each
$m\in M'$ $m\not\models\Phi$ and in some sense the elements of $M'$ are close to the elements of $M$. One can think of the penumbra as the almost solutions. Of course, this notion will not be unique.
Ways of relaxing the constraints $\Phi$ to $\Phi'$ such that firstly $\Phi\Rightarrow\Phi'$ and $\Phi'\land\neg\Phi$ is, in a sense, the syntactic penumbra of $\Phi$.

"Penumbra" is a word I selected to describe the concept. It may well be called something else.

I found inspiration in
mathematical morphology, hence my visual metaphor, but the two worlds are parsecs apart. Is there any useful work there? Or perhaps in the world of rough sets?

Can anyone shed light?


texts: Outstanding conjectures and open problems in (algorithmic) game theory?

texts:
What sort of conjectures and major open problems are the most important in algorithmic game theory (or game theory in general as it relates to CS)? For example, the resolution of NASH as being PPAD-complete would, I think, have been the biggest one up until it was resolved.

(Added: resolving PPAD's relation to P and NP is one good open problem, but others not so deeply entrenched in computational complexity would be nice too.)


texts:
I would like to ask whether there is an already published result on that:

We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and number of nodes $n$) graphs and write down their lengths. Of course this number of distinct paths is exponential. My  question is, if we sort the lengths and compare them (the lists obtained by the two graphs) and they are exactly the same, can we say that the two graphs are isomorphic?

Of course, even if this is a result we cannot use it to reply for Graph Isomorphism, since the number of distinct paths is exponential, as said

By distinct paths, I refer to paths having at least one different node, obviously.

Thanks in priori for your help.


texts: Are there knot theoretic formulations of NP complete problems?

texts: Are there NP complete(or even NP-hard, or NP) problems that have good topological properties to study. Do NP problems have knot theoretic formulations? We know about #$P$ results about the Jones polynomial. Graph problems(embeddings?), specifically colourings of graphs can be seen to have nice knot theoretic properties. It is an open ended question, and any references for this topic appreciated.


texts: Formal representation of rings in computations

texts: While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not familiar with computations of algebraic objects, is there any good references or books on this topic? Particularity in representing a ring R on a Turing machine, and the complexity of deciding basic properties on R (say, the height of an prime ideal in R.)


texts: Natural candidate against the Isomorphism Conjecture?

texts:
The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is that it implies $P\neq NP$. It was published in 1977, and a piece of supporting evidence was that all $NP$-complete problems known at the time were indeed p-isomorphic. In fact, they were all paddable, which is a nice, natural property, and implies p-isomorphism in a nontrivial way.

Since then, the trust in the conjecture deteriorated, because candidate $NP$-complete languages have been discovered that are not likely to be p-isomorphic to $SAT$, although the problem is still open. As far as I know, however, none of these candidates represent  natural problems; they are constructed via diagonalization for the purpose of disproving the   Isomorphism Conjecture.

Is it still true, after nearly four decades,  that all known natural $NP$-complete problems are p-isomorphic to $SAT$? Or, is there any conjectured natural candidate to the contrary?


texts:
I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)$, gets a probability of $p^{|E|}\cdot (1-p)^{{{{|V|}\choose{2}}} - |E|}$. In particular, $G(n, \frac{1}{2})$ is the uniform distribution over simple undirected graphs of size $n$.

Now, given a finite alphabet $\Sigma$ and a natural number $n$. Do we have a random process that generates a deterministic automaton $A$ with:

$A$ has $n$ reachable states.
$A$ is defined over $\Sigma$.
$A$ has the same probability as any other deterministic automaton of size $n$ over $\Sigma$.

In words, do we have a way to generate a uniform distribution $D(\Sigma, n,\frac{1}{2})$ over deterministic automata?

I would be happy if you can direct me to a relevant reference.


texts: Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$

texts:
How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?
Use the L1 metric, so that in 4d
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + (1 - x_0)$
($x_0$ on the right) and so on.

For an alternate formulation,
first flip $x_i$ > 1/2 and sort,
so that $ 0 \leq x_{d-1} \leq \dots\  x_1 \leq x_0 \leq$ 1/2;
by symmetry, an algorithm for this case can do any $x$ in the cube.
Define $c \equiv 1 - 2x$, $ 1\geq c_{d-1} \geq \dots\  c_1 \geq c_0 \geq 0$.
Then we want the $d+1$ corners with smallest $c \cdot$ corner.

In 4d for example, with $x_i$ decreasing 1/2 .. 0 as above,
the 5 nearest corners can be

    0 0 0 0
    0 0 0 1
    0 0 1 0

    0 1 0 0  or  0 0 1 1
                 0 1 * *

    1 0 0 0
 or 0 1 0 1

However in 5d, 6d ... the trees of increasing corners look (to me)  increasingly messy.
Heuristics for approximate-nearest would be fine.


texts: Optimal greedy algorithms for NP-hard problems

texts:
Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive algorithms for many problems in P. More interestingly, for some NP-hard problems the obvious and natural greedy/local algorithm results in (provably) optimal approximation factor (under suitable complexity theoretic assumptions). A classic example is the Set Cover Problem. A natural greedy algorithm gives an O(ln n) approximation factor, which is optimal unless P = NP.

Name some natural greedy/local algorithms for NP-hard problems that are provably optimal under suitable complexity theoretic assumptions.


texts: Is cubic complexity still the state of the art for LP?

texts: According to D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ time. Has that been improved upon?


texts: Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane

texts:
Question summary: what are the known efficient algorithms to find the intersections of 1-dimensional curves living on a 2-dimensional plane?

Detail: I have a set of 1-dimensional curves on a 2-dimensional plane. Each curve in reality is a set of points connected by straight lines (therefore more like a polygon), and is the numerical solution of a given differential equation. I want to find all the intersection points of the 1-dim curves.

Here are what I tried so far.

Method 1. Use interpolating functions & root finding algorithms.

1.1 For each object C_n, cut it into subobjects C_(n, i) at inflection points of C_n, i.e. at dx/dy = 0 and at dy/dx = 0 when we consider the 2-dim plane as the x-y plane.

1.2 For any two subobjects C_(n, i) and C_(m, j) check if they have a common x- and y-domain. If they have, find interpolating function for each of them, y = f_(n, i)(x) and y = f_(m, j)(x), and find roots of f_(n, i)(x) - f_(m, j)(x) = 0.

Method 2. Use a hash table.

2.1 Consider the 2-dim plane as a hash table, where each element is a square bin of a small size, comparable to the resolution of the 1-dim curves.

2.2 Run along each C_n, and when it hits a bin at (i, j), record the hit in the table with (i, j) as a key and {n} as its element.

2.3 Retrieve keys with more than one element.

A Practical issue with Method 1 is there are many things to consider case-by-case when using interpolation and root-fiding algorithms, especially when there are nearly horizontal/vertical curves and when there are more than one root for a given pair of subobjects.

For Method 2, a big issue is that the physical size of the hash table gets big easily, for example I need about 10GB of RAM to deal with my current research project even at its elementary stage.

I suspect there should be previous studies for similar problems, but my background & research area is theoretical physics and I don't know much about such studies. I tried googling but was not successful so far.

On a side remark, I think that a generalization of this problem, i.e. finding intersections of numerically implemented n-dimensional objects in an m-dimensional space may be quite interesting, and I wonder if there is any previous study about such a problem.

Thank you very much in advance.


texts: Can the optimal minimum cost two-commodities flow be fractional on this special case?

texts:
Suppose that we have a two commodities flow network $N=<G=(V,E), s_1,s_2,t_1,t_2\in V>$.

The problem is to find a minimum cost two-commodity flow in which there a flow $f_1$ from $s_1$ to $t_1$ of 2 units and a flow $f_2$ from $s_2$ to $t_2$.

All edges has capacities 1 and cost 1.

(In two-commodity flow the two flows share the edges capacities, that is $\forall e\in E, f_1(e)+f_2(e)\leq 1$, and the cost is defined as $\Sigma_{_{e\in E}}f_1(e) + f_2(e)$ ).

In the general case, multi-commodity flow can have fractional optimum flow even if the capacities/costs are integers, but I was wondering if there's an example for it which doesn't use negative weights and only 2 commodities, so my question is: Is there be a network with my specifications that doesn't have an optimal integer solution?

The following example (taken from Idan Maor's presentation) shows that that 3-MCF can have only a fractional optimal flow:

I have two motivations here: if such network exists, it can be used to show a very simple example for which using LP for solving this problem can't work, and if there isn't such network, this might allow us to develop an efficient method for finding disjoint paths in a graph (if we can find the optimal solution in poly time).

Edit: as Suresh have mentioned, 2-commodity flow is NP-hard in the general case, so I'm only looking at the unit capacities/costs case, which I couldn't find a mentioning for it as being NP-hard (Intuitively, I believe an integer solution does exist for every such network)


texts:
In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other extendability problems transform an easy problem to hard one.

For instance, Konig-Hall theorem states that all cubic bipartite graphs
are 3-edge colorable but the extendability version becomes $NP$-complete if we are given the colors of some edges.

I'm looking for a survey paper of hard extendability problems where the the base problem is easy (or trivial as in the above example).


texts: Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

texts:
The only examples of $\sharp P_1$ complete problems I've seen are fairly abstract : e.g. here https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf

Valiant proves that there exists a $\sharp P_1$ complete sub-pattern matching type-problem, but he doesn't give it explicitly.

I know it was conjectured ( for example, it's mentioned here: https://www.sciencedirect.com/science/article/pii/S030439750300080X ) that the number of self avoiding walks of length $n$ might be a $\sharp P_1$ complete problem. Has there been any progress on this problem? Or are there similar counting problems (some explicit combinatorial family) which have been shown to be $\sharp P_1$ complete?


texts: Matrix multiplication in $O(n^2 \log n)$

texts:
I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read article but it's complicated and will takes too many time to read it, but if there is anyone who reads this article or knows about this algorithm, Is this true? and are you knowing about the base Idea of this to describe it a little.

Thanks in advance, I know it's a bit general question but, if I found it's good approach I'll going to learn details.


texts: Variants of Cluster-Vertex-Deletion problem

texts:
The Unweighted Cluster-Vertex-Deletion problem is the following:

Input: An undirected graph G = (V, E) and a nonnegative number k

Output: Is there a subset X ⊆ V with |X| ≤ k such that deleting all vertices in X from G results in a cluster graph (i. e., a graph where every connected component forms a complete graph)?

This problem is NP-Complete.
More information can be found here:
Fixed-Parameter Algorithms for Cluster Vertex Deletion where FPT algorithms are given for a more general problem.
In particular, for a weighted version of d-Cluster-Vertex-Deletion where $d$ is a parameter that limitates the number of cliques to be generated, they developed three algorithms with running times: $O(2^k \cdot k^9 + nm), O(1.40^k \cdot k^{3d} + nm)$ and $O(1.84^{k+d} + nm)$.

I was wondering if it there is some known result for the case where $G \setminus X$ is a disjoint union of exactly 2 cliques, or the case where $G \setminus X$ is a disjoint union of p-defective cliques (cliques that misses at most p edges) in both cases (exactly two p-defective cliques or any number of p-defective cliques). I am specially interested in algorithmic results such as FPT or approximation algorithms developed for any of these variants.

I couldn't found anything but I suspect there is some results on this or maybe can be mapped from some other very well studied problem.

Thanks in advance

Edit:
Adding to the useful answers, here is a paper that I've recently found and show NP-Hardness of the variant separating in exactly two cliques (but for a weighted case).
Approximating clique and biclique problems


texts: Is there any work relating type systems and Cook-Reckhow proof systems?

texts:
An important subfield of computational complexity is proof complexity, mostly due to Cook and Reckhow. E.g. one notable result is that a proof system that has efficient proofs (i.e., in length polynomial to the formula being proven) for all tautologies could be constructed iff $coNP$ = $NP$. Other results deal with specific propositional calculus proof systems, showing that they all have superpolynomial proof lower-bounds. Is there any work relating type systems and type inference rules to the proof systems as defined in this theory?

In general, a cursory examination reveals that most discussions of type systems discuss computability (decidability/undecidability) with little discussion of finer complexity bounds (which may well exist in many finite models). Is there a reason why this is so (if indeed it is so)?


texts: Nonmetric TSP and Functional Compleixty Classes

texts:
Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method.

Is this general TSP a complete problem in some functional complexity classes ?

I've read the zoo, but this problem is not mentioned.