texts: Euclidean TSP in NP and square root complexity

texts:
In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP:

  The reason being that we do not know how to calculate
  square roots efficiently.

On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although he doesn't prove it in the paper, I think he consider the membership in NP trivial, as is usually the case with such problems.

I am confused by this. Honestly, the claim that we don't know if Euclidian TSP is in NP shocked me, since I just assumed it is trivial -- taking the TSP tour as a certificat, we can easily check it is valid tour. But the problem is that there can be some square roots. So the lecture notes basically claim that we cannot in polynomial time solve the following problem:

Given rational number $q_1,\ldots,q_n,A\in\mathbb{Q}$, decide if $\sqrt{q_1}+\cdots+\sqrt{q_n}\leq A$.

Question 1: What do we know about this problem?

This begs the following simplification, which I was unable to find:

Question 2: Is this reducible to the special case when $n=1$? Is this special case polynomial-time solvable?

Thinking about it for a while, I came to this. We want polynomial time complexity with respect to the number of bits of the input, i.e., not the size of the numbers themselves. We can easily work out the sum to a polynomial number of decimal digits. To get a bad case, we need an instance of $q_{1,k},\ldots,q_{n,k},A_k\in\mathbb{Q}$ for $k=1,2,\ldots$ such that for every polynomial $p$, there exist an integer $k$ such that $\sqrt{q_{1,k}}+\cdots+\sqrt{q_{n,k}}$ and $A_k$ agree on the first $p(\text{input-size})$ digits of decimal expansion.

Question 3: Is there such an instance of reational number?

But what is $\text{input-size}$? This depends on the way the rational numbers are represented! Now I am curious about this:

Question 4: Is is algorithmically important if rational number are given as ratio of two integer (such as $24/13$) or in the decimal expansion (such as $2.5334\overline{567}$)? In other words, is there a family of rational numbers such that the size of decimal expansion is not polynomially bounded in the size of ratio representation or the other way around?


texts: Why is computing pure Nash equilibria NP-complete?

texts:
In this paper, it is claimed that computing pure-strategy Nash equilibria of games in standard normal form is NP-complete.

This confuses me, because I do not understand why it is hard to guess the right strategy profile (the authors call this the "global strategy") for a game.  Surely if the Nash equilibrium of a game is written out in normal form, where every strategy profile is assigned its own cell, then it should take only linear time to run through every possible strategy profile that is a candidate for being a Nash equilibrium.

I do not understand what I am missing; please explain why Nash equilibrium computation is hard for standard normal form games.  Thank you.


texts: Time complexity for solving linear congruences?

texts:
What is the best known algorithm to solve linear congruences of the form below?
$$a x + b \equiv 0 \space (n)$$

And what is the time complexity of it?


texts: Is this partition problem strongly NP-complete?

texts:
Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the fixed-point free GA problem is NP-complete.

Partition problem is weakly NP-complete problem since it has pseudo-polynomial time algorithm. I am interested in variants that are strongly NP-complete.

Here is a variant of partition problem:

Restricted partition problem

Input: Set $S$ of $2N$ integers, and a collection $P$ of pairs from $S$, $0 \lt |P| \lt N$

Query: Is there a partition of $S$ into two equal cardinality parts $A$ and $S-A$ such that both parts have the same sum and no pair in $P$ has both elements in one side of the partition?

  Is this variant of partition problem NP-complete in the strong sense?

This was posted first on Math overflow (I believe the posted answer is incorrect since the proposed dynamic programming algorithm does not take into consideration the cardinality of $P$).


texts: Is there computable function to compute each computable real number?

texts:
Recall that a computable real number is one which can be calculated to any precision, like $\pi$ or $e$. It does not matter that these numbers are irrational, computability is about being able to compute rational approximations.

Is there a computable function which outputs an (infinite) sequence of Turing machines, each of which computes a real number, and such that all real numbers are so included?


texts:
Let $x_1,x_2,\dots x_n$ be literals.

Let $P(x_1,x_2,\dots,x_n)$ be the parity function.

What is the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $f(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$)?

What is the smallest degree of $r(x_1,x_2,\dots,x_n)\in \mathbb R(x_1,x_2,\dots,x_n)$ (sum of degrees of numerator and denominator) that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $R(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$)?

Note that $f(x_1,x_2,\dots,x_n)$ and the numerator and denominator of $r(x_1,x_2,\dots,x_n)$ can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.


texts: Determining if transducer automaton has two states with intersecting images, without minimizing?

texts:
I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)$\to$(new state,output letter). Thus every state gives a transformation {words}$\to${words}.

I want to determine whether there exist two states which act identically on arbitrarily long words. Formally, consider the coarsest relation $\sim$ on the stateset such that $x\sim y$ iff there are letters $a,b$ and transitions $(x,a)\to(x',b)$ and $(y,a)\to(y',b)$ with $x'\sim y'$. I want to know if there is $x\neq y$ with $x\sim y$.

I can do this by composing the transducer with its transpose (switching input and output), minimizing, intersecting with the diagonal on the alphabet, and detecting whether a state $(x,y)$ in the product of states survives with $x\neq y$.

However, I'd very much like a faster algorithm, say of complexity $O(n\log n)$ with $n=$ number of states (the alphabet size can be assumed small).

I thought about adapting Hopcroft's (1971) algorithm, by constructing a partition of the stateset in which, initially, two states $x,y$ are in the same part iff there exists a letter $a$ with $(x,a)\to(x',b)$ and $(y,a)\to(y',b)$ for some $x',y'$, and then refining the partition; however it doesn't seem to work straight off the bat.

EDIT: here is more explicitly the relation I am interested in. Say two states $x,y$ in a transducer are weakly equivalent, $x\sim y$, if there is at least one letter $a$ such that $x,y$ have the same output on input $a$, and lead to weakly equivalent respective states. This defines uniquely weak equivalence if one asks for $\sim$ to be maximal with this property. (Beware that it is not, in general, and equivalence relation).

It may be computed as follows: start by $x\sim_0 y$ for all $x,y$; then define $x\sim_n y$ if there is a letter $a$ and transitions $(x,a)\to(x',b)$ and $(y,a)\to(y',b)$ with $x'\sim_{n-1}y'$. These are a descending sequence of relations, so must stabilize, and they stabilize to weak equivalence.

The real question I'm interested in is not how to compute $\sim$, but merely to determine whether it is non-trivial; and I want to do that in subquadratic time, ideally linear up to logarithmic terms.


texts:
[Timeline]

This question has the same spirit of what papers should everyone read and what videos should everybody watch. It asks for remarkable books in different areas of theoretical computer science.

The books can be math-oriented, yet you may find it great for a computer scientist.
Examples:

Probability
Inequalities
Logic
Graph Theory
Combinatorics
Design & Analysis of Algorithm
Theory of Computation / Computational Complexity Theory

Please devote each answer to books of the same subject (e.g. books on combinatorics).

Note: The title might be misleading. Here's a clarification: Let X and Y be two fields in computer science. There are books that everyone

in field X should read.
in field Y should read.
in both fields should read.

This question seeks all 3 cases. In other words, it is NOT specific to the latter case.

Edit: As suggested by Dai Le, please highlight the reason(s) you like the book as well.

Related topics:

References for TCS proof techniques
Books on automata theory for self-study
Books for probability
Favorite popular math book
Beginner's guide to derandomization
References on circuit lower bounds
Survey article on the theory of recursive functions
Books on Programming Language Semantics
What are the recent TCS books whose drafts are available online
Books on probability


texts: Time complexity of standard semidefinite programming solvers

texts:
I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs.

(I am not interested in algorithms like multiplicative weights updates method.)


texts:
Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these processes on $k$ processors. Note that if process $p_i$ depends on process $p_j$ (which is denoted by $p_j \rightarrow p_i$), it cannot be executed until $p_j$ is finished so it can provide the necessary data that $p_i$ requires. Moreover, if processes $p_i$ and $p_j$ are assigned to different processors and $p_i \rightarrow p_j$, there is a delay associated for moving data from one processor to another. On the other hand, if processes $p_i$ and $p_j$ are assigned to one processor $p_i \rightarrow p_j$, the data can be provided to $p_i$ in zero time.

Now we want to divide these processes into $k$ partitions such that the overall execution time of them (i.e., their makespan) are minimized.

Please note that this problem is different from the standard graph partitioning problem since we are dealing with a DAG rather than an undirected graph. "Graph partitioning models for parallel computing" by Hendrickson and Kolda has pointed to the aforesaid problem but does not provide any solution to it.


texts: Generalization of the Hungarian algorithm to general undirected graphs?

texts:
The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important primal-dual method. The algorithm was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian algorithm" because the algorithm was based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. Munkres reviewed the algorithm in 1957 and observed that it is indeed polytime. Since then the algorithm is also known as Kuhn-Munkres algorithm.

Although the Hungarian contains the basic idea of the primal-dual method, it solves the maximum weight bipartite matching problem directly without using any linear programming (LP) machinery.
Thus, in answer of the following question, Jukka Suomela commented

  Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance. [...] You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.

In other words, you don't have to worry about how to round a rational/floating point solution from the LP solver to get back a maximum weight perfect matching of a given bipartite graph.

My question is the following:

  Is there a generalization of the Hungarian algorithm that works for general undirected graph without the use of LP machinery similarly to the spirit of the original Hungarian algorithm?

I would prefer modern and easy-to-read exposition instead of some original complicated paper. But any pointer will be very appreciated!

Many thanks in advance and Merry Christmas!!!

Update: The question is nicely answered by Arman below. I just want to point out that another nice source to study the Edmonds's Blossom Algorithm (for the  weighted case) is Chapter 11 of  Combinatorial Optimization by Korte and Vygen. Google book actually  shows nearly all the parts I need to understand the algorithm.


texts: Characterizing the ANF of Single-Cycle Boolean Permutations

texts:
Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We can represent $F$ as a collection $[F_1(x), F_2(x), \ldots, F_n(x)]$ of boolean functions (i.e. each $F_i$ is a mapping from $\{0,1\}^n$ to $\{0, 1\}$). Let $f_i(x)$ denote the algebraic normal form (ANF) of $F_i(x)$. I am interested in the following questions:

Is there a way to characterize when $F$ is a single-cycle permutation by saying something about the $f_i$'s? I am looking for a statement of the form: $F$ is a single-cycle permutation if and only if some property about the $f_i$'s hold. If this isn't known, what about a similar statement relating $F$ with its $F_i$'s? In other words, under what conditions do $n$ boolean function $F_1(x), \ldots, F_n(x)$ induce a single-cycle permutation? If we only require $F$ to be a permutation, then the following characterization is known (Boolean Function Representation of S-Boxes and Boolean Permutations): $F$ is a boolean permutation if and only if for any non-zero vector $c = (c_1, c_2, \ldots, c_n) \in \{0, 1\}^n$, the boolean function defined by $F_c(x) = c_1 F_1(x) \oplus c_2F_2(x) \oplus \ldots \oplus c_nF_n(x)$ produces a one for $2^{n-1}$ different values of $x$. Can something similar be said for single-cycle permutations?


texts:
I am re-posting the problem https://mathoverflow.net/questions/92783/random-task-scheduling-problem here because I think people here are more familiar with this topic.

Assume there are $m$ tasks, each task's working time conforms to some distribution, for instance an exponential distribution with mean $\lambda$.
So let the r.v. $X_i$ is the working time of the $i$th task, and $\{X_i\}$ are i.i.d. random variables.

There are $n$ machines to do these tasks, the scheduling police is, once a task is finished on some machine, if there are still pending tasks, one of the pending tasks (randomly selected) will be scheduled to the idle machine immediately (ignore the scheduling latency here).

The finishing time of the system is defined to be the last job's finishing time which is defined to be a random variable $Y$.
So my question is, what are the the distribution function of $Y$ and expectation of $\mathbb{E}(Y)$?

I am interested in the more general distribution of $X_i$, while the distribution of exponential is also welcomed. Papers about this problem is also very helpful to me.


texts: How do you get a "Physical Intuition" for results in TCS?

texts:
I'm sorry if this question is a little vague, but I am curious how successful researchers get a "feel" for the results in TCS.

For example, linear algebra can be understood geometrically, or in terms of its physical interpretations (eigenvectors can be thought of as "stable points" in a system), etc. It's also intuitive that there exists an IP protocol for TQBF (as the IP protocol can be visualized as a kind of a "game" between two entities of greatly differing computational power). However, I find that a lot of the results, even extremely basic ones in TCS do not have such simple intuitions (MA $\subseteq$ AM). Worse still, occasionally, unrefined intuitions go awfully wary (2-SAT is in P while 3-SAT is not believed to be in P (in fact, is NP-complete)). Are there any "general principles" for developing an intuition in TCS?


texts: Simulation of deterministic turing machines

texts:
What are the best known upper and lower bounds for simulating t steps of certain models of deterministic turing machines (1 tape, 1 tape with read only input tape, 2 tape, multi tape, with/without random access to memory)?

Edit: I am mainly interested in efficient simulations with the same or with weaker models. Simulations with stronger models are quite efficient in most of the cases.


texts: Embedding of "large" graphs into random graph

texts:
Let $G \sim G_{n,p}$ be a binomial random graph and consider a sequence of graphs $\{H_n\}_n$.
When $|H_n|=\mathcal{O}(1)$, then one knows the exact threshold $p_0$ for embeddabiliy of $H_n$ in $G$.

When $|H_n|\geq (1-o(1))n$, however, no general results are known, but only special cases (matchings, packings, Hamilton cycles).

I wonder what happens in between: Say for example that $|H_n|=\Theta(n)$ or $|H_n|=\log n$. Do we know the exact threshold for all such graphs of this size or only for special graphs $H_n$?

I would appreciate any information, link or even a "name" of the problem. Thank you very much.


texts: Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers are best.)


texts: Lower bound to agnostic learning with membership queries

texts:
Setting:

Let $X$ be a finite set and $C = \{0, 1\}^X$ a finite family of classifiers on $X$. Fix an $f \in \{0, 1\}^X$ not in $C$, a (possibly randomized and adaptive) learner $A$ has access to a membership query oracle $EX(f)$, that on input $x$ reply with $f(x)$. For any $h \in C$, define $R(h) = \frac{1}{|X|}\sum_{x \in X}\mathbb{I}(h(x) \neq f(x))$.

The learner goal is for any $f \notin C$ and any $\epsilon \in (0, 1)$ to output a classifier $h_A \in C$, such that $\mathbb{E}[R(h_A)] \le \min_{c \in C} R(c) + \epsilon$ provided that it can ask enough queries to $EX(f)$. Here  the randomization is with respect to the internal coind flip of $A$.

Question:
Is there any known lower bound to the number of queries needed by any algorithm to achive the above $\epsilon$ approximation? (Even a reference to such a similar results would be very helpful!)

This setting resembles classical agnostic PAC learning where there are lower bound of the form $\Omega(d/\epsilon^2)$ with $d$ beign the VC dimension of $C$, but it differs in not having a distribution on $X$ and in allowing the algorithms to freely choose the queries, even in an adaptive fashion. Another setting that came to my mind is that of exact learning with membership queries (e.g. Queries revisited by Angluin) but here the difference is in that $f\in C$.


texts:
A flow network is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the net incoming flow to every node balances with the net outcoming flux at that node. Two special nodes are exempted from this last restriction: the source (which can output a net non-zero flux) and the sink (which can receive a net non-zero flux).

There are algorithms to find the maximum net flow from source to sink in such a network (for example, Ford-Fulkerson algorithm).

I am looking for algorithms that generate pseudo-random admissible flows through such a network. Hopefully the space of admissible flows should be sampled as uniformly as possible. What methods are available here?


texts: Queueing Theory: How to estimate steady-state queue length for single queue, N servers?

texts:
I have a real-life situation that can be solved using Queueing Theory.
This should be easy for someone in the field.  Any pointers would be appreciated.

Scenario:
There is a single Queue and N Servers.
When a server becomes free, the Task at the front of the queue gets serviced.
The mean service time is T seconds.
The mean inter-Task arrival time is K * T (where K > 1)
(assume Poisson or Gaussian distributions, whichever is easier to analyze.)

Question:
At steady state, what is the length of the queue?  (in terms of N, K).

Related Question:
What is the expected delay for a Task to be completed?

Here is the real-life situation I am trying to model:
I have an Apache web server with 25 worker processes.
At steady-state there are 125 requests in the queue.
I want to have a theoretical basis to help me optimize resources
and understand quantitatively how adding more worker processes
affects the queue length and delay.

I know the single queue, single server, Poisson distribution is well analyzed.
I don't know the more general solution for N servers.

thanks in advance,


texts: Nonlinear optimization using parallel input/output

texts:
I have a system that accepts a vector and returns a function value. The goal is to change the elements of the vector such that the function value is minimized using a derivative-free solver, eg. using NOMAD. The structure of the problem allows to pass n vectors to the function at once and receive n function values in return within about the same computation time.

The solvers, which I have found so far, will only pass 1 vector to the function at a time and wait for the function value to be returned.

Is there a solver, which allows "parallel processing" on a single-cpu? Any idea is appreciated.


texts: Do Delaunay triangulations on the sphere maximize the minimum angle?

texts:
Delaunay triangulations in the plane maximize the minimum angle in a triangle. Does the same hold true for the Delaunay triangulation of points on the sphere ? (here the "angle" is the local angle in a neighborhood around the vertex at the apex).

Inspired by but unrelated to this question on Math.SE.


texts:
I've noted that both Martin-Lof type theory and [Weak] Monadic Second-Order logic (eg over trees) enjoy the ability to express basically any finite computer program, in a decidable manner. I was wondering how can one compare those two systems. I understand that MLTT lets you use dependent types and by that easily express quite complicated structures, but I'm more interested in the logical properties: for example, are there things that are decidable under MSOL over trees while their equivalent representation in MLTT will lead to undecidability, or vice versa?

reference for decidable MSOL over trees: http://www.cs.ox.ac.uk/people/luke.ong/personal/publications/lics06.pdf


texts: Shor's quantum error correction code with unknown basis

texts:
$\newcommand{\ket}[1]{\lvert #1 \rangle}$I've met a problem in quantum secret sharing which involves the use of a quantum error-correction code. (let's make it simple to be the 9-qubit Shor code)

In the Shor code, Alice encodes $\ket{0}$ as $(\ket{000}+\ket{111})^3$, and $\ket{1}$ as $(\ket{000}-\ket{111})^3$, so the code can fight against 1-qubit flip or phase error, and recover the original qubit.

However, what I'm wondering is:

What becomes of the 9 qubits after measurement? Do they become the original 1 logical qubit? Or do they stay as 9 entangled qubits?
What would happen if Bob, the one who decodes the code, actually has a slightly different orthogonal basis than the original one due to imperfect knowledge or experimental error, e.g. Bob is measuring with $\ket{0'}=\cos(x)\ket{0}+\sin(x)\ket{1}$ and $\ket{1'}=-\sin(x)\ket{0}+\cos(x)\ket{1}$ but $x$ is small? (Or, let's say he is really unlucky and mistook Alice's $\ket{0}$ and $\ket{1}$ basis entirely, so he uses $\ket{+}$ and $\ket{-}$ basis, then Bell basis for him would become $\ket{+++} + \ket{---}$

When $x$ is small, would he still be able to decode out the original qubit using the "wrong" Bell basis? And would there be some way to calculate the error probability?


texts: Crime prevention using graph theory and machine learning

texts:
I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic representation.

BACKGROUND EXAMPLE

Consider the following individuals forming nodes in the larger network of society.

John:

62 years old, clean criminal record
married and father of two
works as a psychologist
pays his taxes
gives to charity

Ted:

36 years old
convicted of a DUI three years ago, but otherwise clean criminal record
works in a convenience store
married and no children
once had an addiction problem to cocaine

Robert:

42 years old
freshly released from a 20-year sentence for homicide
high school dropout
unemployed
is looking into dealing illegal drugs and guns

As should be "obvious", one could run some kind of machine learning on the bullet points for each of the individuals and obtain a score of "criminality risk". (The machine learning model could have been trained over several such labeled observations in society.) John would score lowest, Robert highest, and Ted somehow in the middle because of his troubled history. So on a crude risk scale from 0 to 2, we would have John = 0, Ted = 1, and Robert = 2.

So far, we've only looked at the standalone nodes and their intrinsic data (i.e., the bullet points above). However, we can assume that all three individuals can somehow interact, and that's where graph theory comes in. Examples of such interactions (Ix) could be:

I1: Robert sells cocaine to Ted.
I2: John buys a soda from Ted's convenience store.
I3: Robert goes to John for psychological counseling on reintegrating society.
I4: Robert asks Ted if he could work in his store.
I5: John buys an illegal gun from Robert.

In light of these interactions, the scores inferred from the bullet points need to be adjusted, namely:

I1: Ted's risk goes up. Robert's risk stays the same.
I2: John's and Ted's risks stay the same.
I3: Robert's risk goes down. John's risk stays the same.
I4: Robert's risk goes down. Ted's risk stays the same.
I5: John's risk goes up. Roberts's risk stays the same.

It's therefore clear that the direction and nature of the interaction matters in inferring the risk scores. Any graph that represents these interactions should also allow for cycles, so traditional Bayesian networks aren't an option. One should also have a way to deal with the flow of risk in that network. (For example, what if I3 and I5 happen at the same time? Do their opposite effects cancel out?)

QUESTION

Which type of graph theoretic representation is best suited for this problem? Note the added complication that the belief propagation doesn't flow "smoothly" through the nodes since, as we saw above, each node runs it's own inference based on it's intrinsic data. At each node, one should therefore merge the inference from the neighboring nodes as well as the inference from the intrinsic data of the node.


texts: Linear programming - How to allow cycles with weight at most s?

texts:
Consider a graph $G=(V,E)$ with nonnegative weight function on the edges $w$.
How would you express in LP that you want to allow cycles in $G$ with total weight at most $s$ ?
I've found this while googling:
$\sum_{v\in S} (d_S(v) -1)x_v \geq b(S)  $ for all $S\subseteq V$

Where $d_S(v)$ is the degree of $v$ in the subgraph $G_s=(S,E[S])$ ($E[S]$ is the set of edges with both endpoints in $G$) and $b(S)=|E[S]|-|S|+1$ and $x_v$ is a boolean variable for all $v \in V$ describing if $x_v$ was picked by the LP. This constraint is for making sure we pick a set of vertices such that if we remove them from the graph it will be acyclic, however, I want to allow cycles of weight at most $s$.

(If anyone's interested, it's taken from page 16 here)


texts: When replacing an edge with a graph gadget preserves graph isomorphism?

texts:
The transformation replacing an edge by a graph gadget
is widely used in graph theory.

As an example, in an answer Marzio De Biasi subdivided
edges which increases the girth while preserving GI.

A gadget $GA$ is a graph with two distinguished vertices $u,v$.

The transformation $G,GA \to G'$ is:  replace edge $(x,y)$ in
$G$ by a copy of the gadget $GA$ and in the copy set $u=x,v=y$ so
$x,y$ from the original graph are the same in all copies.

  Which gadgets $GA$ preserve isomorphism:  $G \cong H \iff G' \cong H'$

Added to clarify

I am looking for an algorithm given $GA,u,v$ to decide if it preserves isomorphism or not (reductions to GI complete problems are allowed though better be avoided).

Added 2 I am interested when $GA$ is fixed (and possibly small).


texts: any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

texts:
small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big Data techniques/ datamining etc). they have since been found to be quite ubiquitous/ longstanding in many diverse graphs related to nature and human constructions (eg biology/genes, social networks, man-made networks eg WWW/ internet/ telecommunication/ electrical grids, airport connectivity, etc).

in contrast expander graphs are far older and were invented mainly as a theoretical device in math/(T)CS however have since found very broad/ widespread/ key application. am looking for eg refs/ surveys/ overviews on their interrelation.

  what are the relations between the following (eg is there any overlap for some parameters)

  small world networks
  scale free graphs
  expander graphs


texts: Unique factorization representation and complexity

texts:
Suppose that $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$ with $p_i$ prime and $a_i \geq 1$.

Given a representation of the factorization of $N$ and an integer $m$ (using alphabet $\Sigma = \{0,1,,\}$):

Input: $\quad m,p_1, a_1, ..., p_k, a_k$

What is the time and space complexity of calculating the $m$-th bit of the binary representation of $N$?

I asked a similar question on mathoverflow a few weeks ago, but didn't get a satisfactory answer.


texts: Maximize number of bins and minimize cost of elements chosen from a set

texts:
I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function assigning each element $e \in S$ a cost $c$. The problem is to maximize the number of different bins and minimize the total cost of the elements, subject to a cardinality constraint $K$. (I'm interested in both cases: either at most or exactly $K$ elements).

So the objective function would be: $f(S) = \lambda\sum_{i=1}^N \mathbb{1}_{|B_{i} \cap S| > 0} - \sum_{e \in S} c(e)$, where $N$ is the number of bins and $\lambda$ is a tradeoff parameter.

Maximizing the number of different bins is equivalent to maximizing the rank of a partition matroid.

In addition to partition matroid rank, I'm also interested in other types of coverage-like submodular functions.

This can also be seen as maximizing the difference between a sub modular function and a modular cost function; it is non monotone sub modular.

Is this - or a similar formulation - equivalent to any other known problem?


texts:
I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $j$ in $\Omega(\log j)$ airthmetic operations.

Easily we can compute set $A$ in $O(k \log k )$ airthmetic operations.

Question : How to compute set $A$ in $O(k)$ many arithmetic operations?


texts: What NP-complete problems are most similar to integer factoring?

texts:
The exact complexity of factoring integers (the decision problem) is a major open question in TCS (with important implications, especially in cryptography because of the RSA algorithm), and is widely conjectured to lie "between" P and NP-complete (see the AKS algorithm and Shor's algorithm for two other key aspects of its significance).

Yet, there is so much diversity among the NP-complete problems, including some relating to factoring types of objects and problems in number theory.

  What are some of the "closest" or "nearest" NP-complete problems to integer factoring?

Optionally, an answer might indicate why such problems are thought not to be equivalent to integer factoring under polynomial time reductions (even circumstantial evidence would be appreciated).


texts: What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

texts:
The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions.

Since $\mathsf{L}\subseteq\mathsf{NL}\subseteq\mathsf{NC^2}\subseteq\mathsf{NC}\subseteq\mathsf{P}$, an $\mathsf{NC}$ reduction should be at least as powerful as an $\mathsf{L}$ reduction. What separations or equivalences are known between these two types of reductions?


texts: Why do we need PAP (partial aplication) objects in heap?

texts: In the paper “Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages” by Simon Marlow and Simon Peyton Jones it is told that a PAP heap object may be created in the push/enter model (Figure 2. “The evaluation rules.” “Rules for push/enter.”). It is created “if there aren’t enough pending arguments on the stack.” I can't figure out an example of a type correct program which execution may lead to such a situation.


texts: How to evaluate and compare the performance of algorithms in practice?

texts:
Let $A$ be a heuristic algorithm for problem $Q$.
I want to evaluate the performance of my algorithm in a
specific practical environment and
compare it to other algorithms.
Is there a rigorous framework for comparison of algorithms in practice?

One method to evaluate the performance and compare it with other algorithms
is to run them on randomly generated inputs from a distribution
(based on actual inputs or a theoretical model of inputs) and
measure the average running time of the algorithms.
However I want to be able to express that one algorithm is better than other one
in stronger sense than just having better expected running time.

What do people use for to express stronger conditions?
Would standard deviation be a useful for this purpose?
What is the best way to measure the confidence level of the performance?

Are the any references (books/surveys/tutorials/...) on how to compare the performance of algorithms in practice?


texts: Maximal Clique partition of vertices with smallest number of cut edges

texts:
I am given a simple undirected graph $G(V, E)$. I want to partition $V$ into $b$ Maximal cliques: $\{C_1, C_2, ..., C_b\}$ such that the number of edges that cut across two cliques is the minimum. $b$ is arbitrary i.e. there is no restriction on $b$.

I think the decision version of this problem is NP-Complete. It may be reduced to a weighted independent set problem. My question is:

Is there any known approximate algorithm for this problem?

Thank you for your answers!


texts: Languages recognized by polynomial-size DFAs

texts:
For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$.

I am interested in languages that are "almost" regular in the sense that they can be recognized by automata families of size that grows only polynomially with the word length.

Formally, let me say that a formal language $L$ is recognized by a DFA family $(A_n)$ if for every word $w \in \Sigma^*$, letting $n = |w|$, $w$ is in $L$ iff $A_n$ accepts $w$ (no matter if the other $A_i$ accept it or not), and let me define p-regular languages as languages recognized by a PTIME-computable DFA family $(A_n)$ of polynomial size, namely, there is a polynomial $P$ such that $|A_n| \leq P(n)$ for all $n$. (This name, "p-regular", is something I made up, my question is to know if another name already exists for this. Note that this is not the same as p-regular languages in the sense of permutation automata.)

This class of p-regular languages includes of course regular languages (just take $A_n = A$ for all $n$, where $A$ is some DFA recognizing the regular language); but it is a strict superset of it: for instance, it is well-known that $\{a^n b^n \mid n \in \mathbb{N}\}$ is context-free but not regular, but it is p-regular ($A_n$ just has to count $n$ occurrences of $a$ and $n$ occurrences of $b$). However, because I require the automata to be polynomial-sized DFAs, some formal languages (actually some context-free languages) are not p-regular: for instance, the language of palindromes is not p-regular, because, intuitively, when you have read the first half of a word, you need to have as many different states as there are possible words, because you will need to match exactly this first half with the second.

So the class of p-regular languages is a strict superset of regular languages that is incomparable with context-free languages. In fact, it seems that you can even get a hierarchy of languages by distinguishing p-regular languages based on the smallest degree of the polynomial $P$ for which they are $P$-regular. It is not too hard to construct examples to show that this hierarchy is strict; though I do not understand well yet the interaction between this, and an alternative definition of the hierarchy which would also restrict the complexity of computing the $A_n$.

My question is: has this class that I call p-regular, and the associated hierarchy, been studied before? If yes, where and under which name?

(A possible link is with the field or streaming, or online algorithms. In the terminology of Streaming algorithms for language recognition problems, I am interested in the class (or hierarchy) of languages that can have a deterministic, one-pass recognition algorithms, using a polynomial number of states (so a logarithmic memory size), but I found no definition of this class in this paper or related papers. Note, however, that in my phrasing of the problem the length of the word is known in advance, which is less natural in a streaming context: in streaming you could see this as an infinite automaton, a special "end-of-word" symbol, and a constraint that the number of reachable states after reading $n$ characters is polynomial in $n$. I think that this distinction makes a difference, possible example: language of binary words whose value is divisible by their length, which is easy for a fixed length but (I conjecture) cannot be represented by an infinite automaton in the previous sense because no identifications can be made if the length is not known in advance.)

(The motivation for this p-regular class is that some problems, such as the probability of language membership for probabilistic words, seem to be PTIME not only when the language is regular, but also when it is p-regular, and I am trying to characterize exactly in which circumstances those problems are tractable.)


texts: Complexity of counting maximum number of co-linear points in Euclidean plane

texts:
The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points.

I already know that the problem can be solved in quadratic time using hashing or projective duality (as described here). I also know that checking whether three points are co-linear was proven to be 3SUM-hard under sub-quadratic reductions here.

There are a few issues however:

The 3SUM conjecture was proven false here, so it is no longer believed that the problem has a quadratic lower bound (unless it is strictly harder than 3SUM, see next point).
Unlike most problems in the 3SUM-conjecture paper, co-linearity was only proven to be at least as hard as 3SUM, a reduction in the other direction was not given. That is, it still may be the case that co-linearity is strictly harder than 3SUM. Therefore, the sub-quadratic algorithm for 3SUM cannot be immediately used for the co-linearity problem.
3SUM references only address the problem of checking whether at least 3 points are co-linear. It is not clear to me how to reduce the problem of counting the maximum number of co-linear points to that without a multiplicative linear factor.

My question is: is there any sub-quadratic algorithm known for the problem? If not, do we have a good reason to believe that such an algorithm does not exist?

It is known that finding an $O(n^{2-\epsilon})$ algorithm for 3SUM is still open. So I am, at best, hoping for a logarithmic improvement over the quadratic algorithm.

EDIT: I am also (but not exclusively) interested in the case when the coordinates are integral.


texts: Multiple-sources dominator trees: compact representation and fast algorithm?

texts:
I recently learnt about the concept of dominator trees and was fascinated by it.

I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in the graph as sources: can all-sources dominators be represented more compactly than in O(n^2) space and computed more efficiently than running the classic dominator tree algorithm from every vertex?

I tried searching for keywords like "multiple sources dominators" etc, but only found about "multiple-vertex dominators", which are a different thing (dominating sets of size > 1)

Does any of this become simpler if the graph is acyclic? (in fact, I work at Google and I think it'd be fun to apply this to the huge dependency graph of Google's build targets)


texts: Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

texts:
Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$.

A bitstring $B$ is generated by drawing 0s and 1s from a uniform distribution and is of length $n=\ell(B)$.

Kolmogorov complexity for a bitstring $B$ is the length of the shortest program $B^*$ that generates $B$, $K(B) = \ell(B^*)$.

A typical $B$ is difficult to define precisely.  Intuitively, it is the sort of bitstring that will be generated most of the time by randomly drawing 0s and 1s.  However, the concept can be clarified by examining properties.  A property $p$ applies to typical $B$s if the proportion of $B$s having that property approaches 1 as $\ell(B)$ is increased,
\begin{align*}
\underset{n\rightarrow \infty}{\lim} \frac{|\{B: p(B) \wedge \ell(B) \leq n\}|}{|\{B: \ell(B) \leq n\}|} \rightarrow 1.
\end{align*}

For instance, a typical $B$ has the property that $K(B) = \ell(B)$.  In other words, a typical $B$ is not compressible.  Note: this is not a sufficient condition for typicality.  It is possible for a $B$ to be atypical and incompressible.

There are atypical $B$s that can be compressed, and for these $K(B) < \ell(B)$.

Conditional Kolmogorov complexity, $K(B_2|B_1)$, is the length of the shortest program that generates $B_2$ when given $B_1$ as input.

Algorithmic mutual information is $I(B_1:B_2) = K(B_2) - K(B_2|B_1^*) = K(B_1) - K(B_1| B_2^*)$.  This expression is accurate to within a constant independent of $B_1$ and $B_2$.

A Kolmogorov structure function for a bitstring $B$ is the set generating program $P_B$ such that $B$ is in the set $S_B$ generated by $P_B$ when given $n$ as input.  The shortest $P_B$, such that $\ell(P_B) + \log_2(|S_B|) \leq K(B)$, is called the minimal Kolmogorov structure function, denoted by $P^*_B$.  $\log_2(|S_B|)$ is close to the "randomness" in $B$ that cannot be captured by $P^*_B$.

In the case of a typical $B$ the length of $P^*_B$ is minimal, since knowing $n$ we can enumerate all bitstrings of length $n$ with a constant size program $C$.  On the other hand, in the case of atypical $B$s, the length of $P^*_B$ may be significantly larger than $C$.

My question: is the algorithmic mutual information between a typical $B$ and a $P^*_{B'}$ for any bitstring $B'$ ever larger than $C$?  Although $\ell(B')$ is not constrained by $\ell(B)$, the $P^*_{B'}$ is provided with $n=\ell(B)$ in this case, since the goal is to generate $B$.  However, this does not mean that $B\in S_{B'}$, since $\ell(B)$ does not necessarily cause $P^*_{B'}$ to generate a set that contains $B$.

Note in the case of a typical $B$ that trivially $I(P^*_B:B)=\ell(C)$ since $\ell(P^*_B)=\ell(C)$.  However, this does not mean that there is not another $P^*_{B'}$ from an atypical $B'$ such that $K(B|P^*_{B'}) < K(B)-\ell(C)$, and thus $I(P^*_{B'}:B) > \ell(C)$.

I think the answer is always $I(B:P^*_{B'}) = \ell(C)$ for a typical $B$. If $K(P^*_{B'}|B) < K(P^*_{B'})-\ell(C)$, then part of the randomness of $B$ describes $P^*_{B'}$, so $P^*_{B'}$ is not a minimal structure function for $B'$. I don't know how to prove this formally.

To provide context for this question, I am trying to derive a law of minimal Kolmogorov sufficient statistic nongrowth, based on  Leonid Levin's conservation independence in "Randomness Conservation Inequalities;
Information and Independence in
Mathematical Theories".
Levin's law states
$I(z:y) > I(x:y)$
where $x$ is the result of applying a Turing machine $U$ to $z$, so $x=U(z)$.
I would like to similarly prove $\ell(P^*_z) > \ell(P^*_x)$, and am using $I(B:P^*_{B'})=\ell(C)$ for typical $B$ as one of the premises in my proof.


texts: Normal forms for intuitionistic formulas?

texts:
It is well-known that DNFs/CNFs and prenex normal forms generally do not exist for intuitionistic logic.

Are there any nice results about formula normalization for IL?  I've tried googling this but the results just end up being about normal forms for proofs.


texts: Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can it always be three colored? Ideally I'd like a small counterexample.


texts: Minimal context-free grammar for a regular language

texts:
Are there any algorithms for solving exactly the following question?
Given a regular language L, represented as a finite automaton say, what is a CFG with minimal number of nonterminals that generates the language L?


texts: Lower bounds for the size of nondeterministic circuits

texts:
It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method.

Recently, I noticed that the gate elimination method works well also for nondeterministic $U_2$-circuits, and we can prove a $3(n-1)$ lower bound for the size of nondeterministic $U_2$-circuits computing the parity function.

(It means that nondeterministic computation is useless to compute parity by $U_2$-circuits and cannot reduce the size from $3(n-1)$. Thus, the minimum circuits don't change from the deterministic case.)

My questions are the following two:

(1) Is this a new result or a known result?

(2) More generally, are there some known results of lower bounds for the size of nondeterministic circuits (including formulas, constant depth circuits, and so on) with unlimited nondeterministic input bits (or, in other words, unlimited nondeterminism) for an explicit function?

Additional explanation (Nov 27, 2014)

In the second question, I intended that I would like to know especially whether
this is the first nontrivial lower bound for the size of nondeterministic circuits
(including formulas, constant depth circuits, and so on) with unlimited nondeterminism
for an explicit function or not.
I know there are some results if nondeterminism is limited, as follows.

[1] Hartmut Klauck: Lower Bounds for Computation with Limited Nondeterminism.
    IEEE Conference on Computational Complexity 1998: 141-

[2] Vikraman Arvind, K. V. Subrahmanyam, N. V. Vinodchandran:
    The Query Complexity of Program Checking by Constant-Depth Circuits.
    ISAAC 1999: 123-132


texts:
I am writing on software that has to create matches between teams of bridge players. Each round a new series of matches is calculated. The algorithm has to meet these two criteria:

Each round every teams must meet a team against which it has not played before.
The teams that play against each other should have as close a total score as possible.

This method is known as "Swiss teams". Can someone point me in the right direction?

Read some more about the Swiss-tournament system


texts: Implementation of Wilf-Zeilberger and related methods

texts:
The book A=B by Petkovsek, Wilf and Zeilberger describes algorithms to compute different sums of binomials. AFAIK, these algorithms are still being improved by different authors.

Do you know where we can find the most up-to-date implementations of these algorithms? And do you know if there exist implementations in some free softwares such as Sage?


texts: Are there any open problems concerning decidability?

texts: I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.


texts: How does part 5 of the paper "computational complexity of Minesweeper" work?

texts:
Marzio De Biasi mentioned this paper in this answer, and that paper's claim in part 5 would appear to resolve my question. However, there seems to be a significant gap in the proof.

Even though one may be able to figure out what the gadgets on the border of the known whitespace component are, that doesn't obviously help to figure out what the rest of the whitespace components are.

How can one "reason through wires to uncover all whitespace components" when the wires go through other components (such as crossovers)?


texts: Finite automata that accept binary strings divisible by n

texts:
I'm working on a problem set for a class, and thought of a question related to what I was working on. Is there a minimum number of states that a finite automaton must have in order to accept binary strings that represent numbers divisible by an integer n? In an earlier problem set, I was able to construct a DFA that accepted binary strings divisible by 3 with 3 states. Is this a coincidence, or is there something inherent to the general problem of detecting strings divisible by n that suggests a minimum number of states?

I promise this will not answer a homework question for me! :)


texts:
Following problem is decidable:

Given a context-free grammar $G$, is $L(G) = \varnothing$?

Following problem is undecidable:

Given a context-free grammar $G$, is $L(G) = A^{\ast}$?

Is there a characterization of context-free languages $M$ with decidable equality $L(G) = M$?


texts: Deterministic Büchi + its complement covers LTL?

texts:
It is well known that deterministic Büchi automata (DBA) are less expressive than non-deterministic Büchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). However, the argument often used is that DBA are not closed under complementation - that is there is a language $\mathcal D$ recognized by DBA, but $\mathcal D^c$ is not recognized by any DBA. As an example, $\mathcal D = (b^*a)^\omega$ and $\mathcal D^c = (a+b)^*a^\omega$.

I wonder though, whether for any $\omega$-regular language $\mathcal L$ it holds either $\mathcal L$ is recognized by some DBA, or $\mathcal L^c$ is recognized by some DBA. If not, what is an example of a language which is not recognizable by DBA and which complement is not recognizable either?


texts: Do people look at loop nestness in boolean circuits?

texts:
While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought of as dags, but in real hardware cycles are common. Now, modulo some technicalities regarding what a loop is and what constitutes a nested loop, the claim was basically that in order to implement in hardware an automaton one needs two nested loops, and in order to implement a processor one needs three nested loops. (I might be off-by-one with these counts.)

Two things bother me:

There was nothing like a formal proof.
I didn't see this anywhere else.

Did anyone investigate precise statements of this kind?

Searching for the name of the professor I found a small webpage and book (Chapter 4) that discuss this taxonomy.

Sort of background: In case you wonder why are cycles useful at all in real hardware, here is a simple example. Connect two inverters in a cycle. (An inverter is a gate that computes the boolean function NOT.) This circuit has two stable equilibriums (and an unstable one). Absent any outside intervention, the circuit will simply stay in one of the two states. However, it is possible to force the circuit into one particular state by applying an external signal. The situation can be seen like this: While the cycle is connected to the outside signal "we read the input," and otherwise we simply "remember the last value we saw." So one loop helps us remember stuff.


texts: Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class?

texts:
Do languages decidable in deterministic $n^{O(\log n)}$ time form an interesting complexity class? If yes, is there a name for this class and are there some interesting properties about it that we know about? If not, why not (can we derive it properties easily from some other known complexity class)?

Thank you!


texts: Most important topics for a short introduction to Prolog

texts: Suppose you were teaching an introductory course on logic as part of a TCS curriculum. Furthermore, suppose that you had one week (= two 90 minute lectures) to spare for introducing Prolog on the basis of a theoretical discussion of predicate logic and (definite) logic programming. What would be the topics you'd pick apart from the syntax and procedural semantics of Prolog? Would you introduce SLDNF resolution first or by way of the cut-fail "construction" to implement negation in Prolog programs? What sort of examples would you choose for an audience made up of people who do not know automata and might not even know graphs? There has to be something better than "mere" logic puzzles for more elaborate examples.


texts: If you have a casual conversation with someone and it leads to a paper, what do you owe them?

texts:
What if you had a casual conversation with someone, and that conversation lead to your findings?

What do you owe them?  When is it plagiarism?  I read somewhere that "first to submit, wins" - so basically the first to publish owns the idea.  Is this true?


texts: Practical consequences of $Parity \notin AC^0$

texts:
Background
Circuit complexity $AC^0$ is defined as the set of circuit families (i.e. sequences of circuits, one for each input size) of bounded depth and polynomial size built using unbounded fan-in AND, OR, and NOT.
The parity function $\oplus$ with $n$-bit input is equal to the XOR of the bits in the input.
One of the first circuit lowerbound proven in circuit complexity is the following:

[FSS81], [Ajt83]: $\oplus \notin AC^0$.

Questions:
Let $EC^0$ be the class of functions that can be computed using electronic circuits of bounded depth and polynomial size using electronic parts like transistors. (I made up the name $EC^0$, let me know if you know a better name for this).

Can we compute $\oplus$ in practice using $EC^0$ circuits?

What about unbounded fan-in AND/OR? Can we compute them in $EC^0$?

Does $\oplus \notin AC^0$ have any practical consequences? Is $AC^0$ important in practice?

Why is $\oplus \notin AC^0$ important for (theoretical) computer scientists?

Note:
This post contains interesting questions but OP seems to refuse to make the post more readable and fix the misconception in it for some reason, so I am reposting questions from it. (It would be easier to edit the original post but currently there isn't an agreement if it is OK to heavily edit another user's post.)
Related:

Parity and $AC^0$

Why is parity not in $AC^0$ important? (Computational Complexity Blog)


texts: Continuous mathematics and formal language theory

texts:
Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.

For example, solving the intersection non-emptiness problem for a context-free language and a regular language.


texts: Computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$

texts:
This question is about computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$.
The computation model we are considering is the unit-cost RAM machine with linear preprocessing. In this model, the power of the machine increases polynomially with the maximal allowed integer in the set to maintain. Formally, we have a constant integer $k$ such that, when maintaining a subset of $0, \dots,  n$, each memory cell can store integers in the interval $-n^k, \dots, n^k$. Furthermore, operations on memory cells have unit cost, i.e., basic arithmetic operations (e.g., +, -, ×, /) on memory cells can be performed in constant time.
The goal of the problem is to maintain a set $S$ of integers, which is initially empty. The input to the problem is a sequence of operations that can be update operations (that modify the current set $S$) or query operations (asking a question about the current minimum of $S$); each operation must be processed before we receive the next operation. Formally, the possible updates are add($x$) to add $x$ to $S$ for $x\notin S$ (with $0 \leq x \leq n$), and remove($x$) to remove $x$ to $S$ for $x\in S$. The queries are defined below, and must always be posed at a point when $S$ is not empty. The complexity is measured in terms of the maximal time to process one operation. When measuring the complexity, we don't want to consider the special case where only few updates have been made, so we assume that at least $O(n)$ operations are updates and $O(n)$ operations are queries, where $n$ is the parameter of the machine (i.e., the largest number that the set $S$ can contain).
In problem 1, the queries simply ask for $min(S)$, the value of the minimal integer in $S$. It is easy to see that this version amounts to maintaining a priority queue, which we know from [1] to be equivalent to sorting integers. We have an $O( \log(\log(n)))$ algorithm (using a van Emde Boas tree) for this problem. But is a lower-bound known for this problem? Is it known that this cannot be maintained in constant time per operation?
In problem 2, the queries are Boolean: they have an input $t$ and the answer is either YES if $min(S)\leq t$ and NO otherwise. Clearly this variant is easier than problem 1, because knowning the value of the minimum allows us to compare it to any threshold given as input. Is anything known about the complexity of this problem (a better upper bound than problem 1, and/or a lower bound)? The problem seems to be the one dimension version of the dynamic half-space emptiness test, but we have not found any literature on this problem when the dimension is 1 (does it have a specific name?).
We would especially be interested in a lower bound showing that problem 1 cannot be maintained while spending (non-amortized) constant time on each operation, or an established complexity assumption claiming that this can't be done.
Reference

https://ieeexplore.ieee.org/abstract/document/1181889


texts: P vs. NP and Pseudorandom Bit Generators

texts: According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove that P!=NP. If it is considered impossible to prove mathematically that some bit sequence is random then it should be mathematically impossible to prove P!=NP, right? Are these two problems really equivalent? If they are then why all the hoopla over P vs NP, you can never prove it either way according to these definitions.


texts:
Computing the permanent $\bmod p$  of an $n\times n$ $0/1$-matrix is $\#P$-complete if $p$ is a prime $p>n$. We have an FPTAS for approximating the $0/1$ integer matrix permanent over the reals. Moreover we can compute the permanent of an $n\times n$ $0/1$-matrix in polynomial time if its value is bounded by $n^c$ for a fixed $c>0$.

Is it possible to compute the permanent $\bmod p$ of a $0/1$ $n\times n$ integer matrix in polynomial time if its value is bounded by $(\log p)^c$ for a fixed $c>0$, where $p>n$ holds.


texts: Is BPP vs. P a real problem after we know BPP lies in P/poly?

texts:
We know (for now about 40 years, thank  Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold.
The "/poly" means that we work non-uniformly (a separate circuit for each input length $n$), while P without this "/poly" means we have one Turing machine for all possible input lengths $n$, even longer than, say, $n$ = the number of seconds to the next "Big Bang".

Question 1: What new would a proof (or disproof) of BPP = P contribute to our knowledge after we know BPP $\subseteq$ P/poly?

Under "new" I mean any really surprising consequences, like collapse/separation of other complexity classes. Compare this with consequences the
proof/disproof of NP $\subseteq$ P/poly would deliver.

[ADDED 08.10.2017]: One really surprising consequence
of BPP $\not\subseteq$ P would be that, as shown by Impagliazzo and Wigderson,  all(!) problems in
E = DTIME$[2^{O(n)}]$ would have circuits of size $2^{o(n)}$.
Thanks to Ryan for recalling this result.

Question 2: Why we cannot prove  BPP = P
 along similar lines as the proof of BPP/poly $\subseteq$ P/poly?

One "obvious" obstacle is finite vs. infinite domain issue: boolean circuits work over finite domains, whereas Turing machines
work over entire set $\{0,1\}^*$ of $0$-$1$ strings of any length. So, to derandomize probabilistic boolean circuits, it
is enough to take the majority of independent copies of a probabilistic circuit, and to apply Chernoff's inequality, together with the union bound. Of course, over infinite domains, this simple majority rule won't work.

But is this (infinite domain) a real "obstacle"?
By using results from statistical learning theory (VC dimension), we already can prove that  BPP/poly $\subseteq$ P/poly
holds also for circuits working over infinite domains, like arithmetic circuits (working over all real numbers); see e.g. this paper of Cucker at al.
When using a similar approach, all we would need is to show that the VC dimension of poly-time Turing machines  cannot be too large. Has anybody seen any attempts to make this latter step?

NOTE [added 07.10.2017]:  In the context of derandomization, the VC dimension of a class $F$
of functions $f:X\to Y$ is defined as the maximum number $v$ for which
there are functions $f_1,\ldots,f_v$ in $F$ such that for every $S\subseteq\{1,\ldots,v\}$ there is a point $(x,y)\in X\times Y$ with
$f_i(x)=y$ iff $i\in S$. I.e. we shatter not the sets of points via functions but rather sets of functions via points. (The two resulting definitions of the VC dimension are related, but exponentially.)

The results (known as uniform convergence in probability)
then imply the following: if for each input $x\in X$, a randomly picked function $\mathbf{f}\in F$ (under some probability distribution on $F$)
satisfies $\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$
for a constant $c>0$,
then $f(x)$ can be computed on all inputs $x\in X$ as a majority of some $m=O(v)$ (fixed) functions from $F$.  See, e.g. Corollary 2 in Haussler's paper.
[For this to hold, there are some mild measurability conditions on $F$.]

For example, if $F$ is the set of all polynomials $f:\mathbb{R}^n\to\mathbb{R}$ computable by arithmetic circuits of size $\leq s$, then all polynomials in $F$ have degree at most $D=2^s$.
By using known upper bounds on the number of zero-patterns of polynomials (see, e.g. this paper),
one can show that the VC dimension of $F$ is $O(n\log D)=O(ns)$. This implies the inclusion BPP/poly $\subseteq$ P/poly for
arithmetic circuits.


texts: Placing color boxes on a colored image such that color consistency is maximized

texts:
I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem.

Given an image with black background that contains blobs whose colors are taken from a set C (that does not contain black). Suppose that we have an infinite number of rectangular bounding boxes such that:

Each bounding box has a color taken from C.
Every bounding box of color c has width w_c and height h_c.

Question: How to place these bounding boxes on the image such that there is no overlap between any two boxes, and that n_good - n_bad is maximized, where n_good is the total number of pixels that are inside a box of the same color (as the pixel's color), and n_bad is the total number of pixels that are inside a box of a different color?

Any suggestions on how to solve this problem would be very much appreciated!

Thank you very much in advance for your help!


texts: Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

texts:
Here is a problem with a similar flavor to learning juntas:

Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$.

Goal: Find a subcube $S$ of $\{0,1\}^n$ with volume $|S|=2^{n-k}$ such that $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.1$. We assume such a subcube exists.

It is easy to get an algorithm that runs in time $n^{O(k)}$ and returns a correct answer with probability $\ge 0.99$ by trying all $(2n)^k$ ways to choose a subcube and sampling the average in each one.

I'm interesting in finding an algorithm that runs in time $poly(n,2^k)$. Alternatively, a lower bound would be great. The problem has similar flavor to learning juntas, but I don't see an actual connection between their computational difficulty.

Update: @Thomas below proves that the sample complexity of this problem is $poly(2^k,\log n)$. The interesting issue is, still, the computational complexity of the problem.

Edit: you can assume for simplicity that there exists a subcube with $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.2$ (notice the gap: we're looking for a subcube with average $\ge 0.1$.) I'm pretty sure any solution to the problem with the gap will also solve the problem without the gap.


texts: How is real-time computing defined in theoretical computer science (e.g. complexity theory)? Are there complexity theoretic models designed to capture the real-time computation?


texts: Union/find structure implemented by bitvectors

texts:
I'm having trouble understanding a concept in my book which is about finding a good structure to represent a union-find datastructure. Here we define a structure -referred to as collection- $V$ as such a datastructure:

A collection $V$ is a bitvector (bitvector is an array of $l = (n/b) + 1$ longs) where bit $i$ ($0 \le i \lt b$) of word $j$ ($0 \le j \lt l$) is 1 only if the element $j * b + 1$ is in the collection $V$.

($n$ is the amount of elements, $b$ is how many bits are represented in a long)

So i was thinking of figuring this out with an example, let's say we have collection $V$:

[ 1 |  3  |  6  | ... | l  ]

And since:

1 = 001
3 = 011
6 = 110

Does that mean elements with the number (assuming we have given each element a number):

1 * 64 + 1 = 65
3 * 64 + 1 = 193
3 * 64 + 2 = 194
6 * 64 + 2 = 386
6 * 64 + 3 = 387

are in the collection $V$ ?

If this is completely wrong, could someone please give me a decent example of such a collection $V$, or point out where i'm wrong, or why my example can't be such a collection?

(also, i couldn't give this any sensible tag since i can't create tags yet)


texts: What is the optimal data structure for a tree of maps.

texts:
I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a programming map with keys and values, like map in the STL or dict in python.

For example, there might be a root node:

root = {'car':1, 'boat':2}

and 2 children, each adding an element to the parent map

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

I would like this to be as space efficient as possible, ie i don't want to store a complete copy of the resulting map at each node, but ideally the lookup would still be O(log N), N being the total number of elements at the node, not the entire tree.

I was thinking perhaps there is a smart hash function I might use for this, but couldn't come up with anything.

The naive approach would be storing the newly added entries in a map at each node and then move up the tree if nothing is found. I don't like this because it depends on the tree depth.


texts:
To quote wikipedia,

  The notion of institution has been created by Joseph Goguen and Rod Burstall in the late 1970s in order to deal with the "population explosion among the logical systems used in computer science". The notion tries to capture the essence of the concept of "logical system". With this, it is possible to develop concepts of specification languages (like structuring of specifications, parameterization, implementation, refinement, development), proof calculi and even tools in a way completely independent of the underlying logical system. There are also morphisms that allow to relate and translate logical systems. Important applications of this are re-use of logical structure (also called borrowing), heterogeneous specification and combination of logics. Recently, institutional model theory has generalized many notions and deep results of model theory.

From my cursory experience with institutions, I can't quite get past the impression that this is all abstraction for abstraction's sake. So I want to ask are there any solid applications of institution-independent model theory to, say specification; or perhaps the machinery solved some open problem in logic/CS?


texts: What are some careers in theoretical computer science that do not require a PhD?

texts: I am an undergraduate, and have recently come to terms with the fact that I may not have the intellect to do research in theoretical computer science, or be able to be admitted into and complete a PhD program.  However, I would still like to be involved with theoretical computer science as I find it very interesting.  So far, the only careers in theoretical computer science that do not require a PhD that I can think of would be being a secretary or administrative assistant for the theory group in some university.  Are there any others?


texts:
According to Wikipedia the Delaunay tesselation in $d$ dimensions can be viewed as a convex hull problem in $d+1$ dimensions. Given a countable set of points $S\subset \mathbb{R}^d$ and a point $p\in S$, find the largest subset $X\subset S\setminus\{p\}$ with the following properties:

Every point in $X$ is a vertex of the convex hull of $X$.
$p$ is the only point in $S$ that lies in the interior of the convex hull of $X$.

Is there a relationship between the $d$-dimensional Delaunay tesselation and the set of polytopes for each point $p\in S$ as described?


texts: Generalizations of the determinant/permanent problem?

texts:
A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with Gauss pivot, the second is $\# P$-hard by Valiant's result. There have been attempts to generalize the notions of determinant/permanent, but I was wondering if the following notion of subgroup-restricted determinant had been considered.

Fix a series $\Sigma$ of subgroups $G_1 \leq G_2 \leq \ldots \leq G_k$ of $S_n$, and for an index $p \leq k$ let $\Sigma_p$ denote the truncated series $G_1 \leq G_2 \leq \ldots \leq G_p$. Say that $\Sigma$ is normal if (i) $G_1$ is simple, (ii) for each $1 \leq i < k$, $G_i$ is a maximal normal subgroup of $G_{i+1}$. We may then define, for an $n \times n$ matrix $A$:

  Given $K \subseteq S_n$, let $Sum_{K}(A) = \sum_{\sigma \in K} a_{1,\sigma(1)} \ldots a_{n,\sigma(n)}$;

  Let $SgrDet_{\Sigma}(A) = Sum_{G_k}(A) - \sum_{i = 1}^{k-1} [G_i : G_k] SgrDet_{\Sigma_i}(A)$.

Observe that when $G_{k}$ is isomorphic to $Z_n$, any maximal series $\Sigma$ corresponds to a prime factorization of $n = p_1^{i_1} \ldots p_k^{i_k}$, and then $SgrDet_{\Sigma}(I_n)$ corresponds to the 'signed divisor function' $\zeta'(n) = [i_1]_{-p_1} \ldots [i_k]_{-p_k}$ where by convention $[n]_q = \sum_{i = 0}^{n-1} q^i$.

Observe that we can recover the permanent and determinant with the series $(S_n)$ and $(A_n \lhd S_n)$, respectively. Note that the second series is normal (by the simplicity of $A_n$) while the first is not. This leads to the following questions, probably difficult:

(1) does the formula always have exponential algebraic complexity when the series is not normal?

(2) are there other examples of a normal series for which the formula has polynomial complexity?

(NOTE: I updated the definition of $SgrDet$ to have a better-behaved operator, but it's still unclear whether it is the 'right' definition).


texts: Find shortest prefix to generate original string by overlapping

texts:
Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed).

For example, if $S = atgatgatatgat$, I want to find $P = atgat$; $P$ is the smallest prefix of $S$ that can be concatenated (in this case three times, starting at indices $\{0,3,8\}$ of $S$, where the first and second copies overlap but the second and third copies do not overlap) to equal $S$.

Obviously, there is an $\mathcal{O}(n^2)$ algorithm by checking each prefix of $S$, but a colleague mentioned it might be possible to do it in $\mathcal{O}(n \log n)$. I'm thinking of using suffix arrays for different prefixes of $S$ but haven't quite been able to proceed from there.


texts: Connection between diamond norm and output purity norm

texts:
Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register associated to the Hilbert space), we can define the following two types of norms:

Output purity norms: $\|\mathcal{E}\|_p := \text{max}_{\rho_A}\|\mathcal{E}(\rho_A)\|_p$,
Completely bounded norms (or diamond norm when $p=1$): $\||\mathcal{E}\||_p := \text{max}_{\rho_{AA'}}\|(\mathcal{E}\otimes I_{A'})(\rho_{AA'})\|_p$, where $A'$ is a register of same dimension as $A$.

Above, $\|X\|_p$ for a hermitian matrix $X$, is the standard norm: $\text{Tr}(|X|^p)^{\frac{1}{p}}$. All the maximization above is over quantum states. More details on output purity norms can be found at https://arxiv.org/pdf/quant-ph/0203003.pdf and on completely bounded norms can be found at https://cs.uwaterloo.ca/~watrous/CS766/LectureNotes/20.pdf

Question: It is easy to see that $\|\mathcal{E}\|_p \leq \||\mathcal{E}\||_p$, by restricting the maximization in the case of completely bounded norms to product quantum states $\rho_A\otimes \sigma_{A'}$ (with $\sigma_{A'}$ being pure) and then using the fact that $\|\sigma_{A'}\|_p = 1$. My question is how tight is above inequality. That is, if $\||\mathcal{E}\||_p \leq C\times\|\mathcal{E}\|_p$, then how small $C$ can be, in general?


texts: Efficient algorithm for updating a parse tree

texts:
Let's say I have a big block of code which I already have lexed and parsed.
Suppose that just one character changes; I would want to update my parsing, but since the modification is very small compared to the whole thing, I would like to know if it's possible not to parse the whole thing again, but if there are algorithms to determine the range to re-parse, and to properly deal with moving token boundaries.

Thanks in advance!


texts:
Background:
An instance of 3-SAT is called monotone if each clause consists only of positive literals or only of negative literals.
Given an instance $\phi$ of 3-SAT, we consider the bipartite graph $G_\phi$ that contains a vertex per each variable and per each clause, and has an edge between a variable-vertex
and a clause-vertex if and only if the variable appears in the clause. When $G_\phi$ is planar then $\phi$ is also said to be planar.
Planar Monotone 3-SAT (de Berg and Khosravi [1]) is an NP-hard SAT variant where instances are both monotone and planar.
Furthermore, it remains hard when the graph $G_\phi$ has the following rectilinear representation:
All variable-vertices lie on a horizontal line and all positive clause vertices are above it and all the negative clause vertices are below it. For example:
 (Figure adapted from [1])
In this representation, each clause has at most 3 vertical lines, called legs, that go up/down to each of the variables it contains. We say that two legs enclose a clause $C$ if $C$ is horizontally between the two legs (and is on the same side as the legs with respect to the variables).
A new definition: A clause (of size 3) is bi-enclosing if both its leftmost and rightmost pair of legs enclose some other clauses. For example, in the figure above $C_i$ is the only bi-enclosing clause (as all others clauses have a pair of legs with no clauses between them).
The SAT variant I'm asking about: All Planar Monotone 3-SAT instances in rectilinear representation where there are no bi-enclosing clauses. Is deciding satisfiability in this case NP-hard?
I haven't seen this version addressed explicitly before. Interestingly, the first example of the rectilinear representation for (the more general) planar 3-SAT problem, given in Knuth and Raghunatan [3], has no bi-enclosing clauses:

Edit following domotorp's answer: Here is an instance where we cannot change the order of the variables in order to prevent $(x_1 ∨ x_3 ∨ x_5)$ from being bi-enclosing:

(Note that in the variant in question we cannot move clauses to the other side of the variables. In Planar 3-SAT, however, we could easily do that to fix the bad clause above and so a more complex example would be required for a "non-fixable" instance in that case).


texts: Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?

texts:
This question is about subset problems (the solution is a subset of the instance, so trivially enumerable in $2^n \cdot n^c$ time), and the parameter is the solution size, so-called the standard parameterization.

The answer to the question in the title is obviously yes: the clique problem on sparse graph ($m = O(n)$) remains W[1]-hard but can be trivially solved in $2^{o(n)}$ time. The trick here is that the solution can never be $\omega(\sqrt n)$. So to make the question nontrivial, we have the requirement that

$f_k(n)$ is an unbounded function for any $k$, where $f_k(n)$ is the number of instances with instance size $n$ and optimal solution size $k$.

Informally speaking, the W[1]-hardness characterizes the hardness of instances with extremely small solutions, while the subexponentional solvability concerns with the solution being almost half of the instance size. So it seems perfectly fine that such a problem exists (?).


texts: "Guarded" negative occurrences in definition of inductive types, always bad?

texts:
I know how some negative occurrences can definitively be bad:

data False

data Bad a = C (Bad a -> a)

selfApp :: Bad a -> a
selfApp (x@(C x')) = x' x

yc :: (a -> a) -> a
yc f = selfApp $ C (\x -> f (selfApp x))

false :: False
false = yc id

However, I am not sure whether:

all inductive types with negative occurences can turn wrong ;
if so, there is a known mechanical way of doing so ;

For instance, I've been fighting trying to make this type go wrong:

type Not a = a -> False

data Bad2 a = C2 (Bad2 (Not a) -> a)

Any pointer to literature on this subject would be appreciated.


texts: Generalization bound for parameters rather than loss functions

texts:
I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and the estimated parameters for model classes such as that comprising of logistic regressions? As an example corresponding to linear regression, see below:

For the full proof of the aforementioned example see Thm. 2.2 on pgs 36 and 37 here: https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/lecture-notes/MIT18_S997S15_CourseNotes.pdf. I think this is a special case because they're able to make use of linearity and sub-gaussian assumptions. I was wondering if a similar bound could be obtained for Logistic Regression parameters, or alternatively, are there any other classification models for which similar results could be obtained?
I know learning theory gives us risk bounds. Are there certain settings wherein those risk bounds translate to bounds on the deviations in estimated and true parameters? Saw a similar (but more specific) question in math stackexchange without any answers: https://math.stackexchange.com/questions/3846492/generalization-error-in-logistic-regression. Is this simply impossible to ask for in the agnostic setting for general model classes? Can we hope to get such results for specific model classes, under specific assumptions (eg: the parameter space being compact)? Any related literature? Any insights would be appreciated.
P.S: I don't mean the number-of-iteration based bounds obtained in optimization settings, i.e. computation error, here I am referring to estimation error


texts:
I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope.

Formally,

INPUT: a polytope
$$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\vec{x}+\vec{b}_m)\mid C\vec{x}\leq d\}$$
and a subspace $span(E)$ where $E=\{e_1, \cdots, e_{\ell}\}$ is a given set of vectors

OUTPUT: a basis of the linear subspace spanned by
$$V(\Xi)\setminus span(E),$$ where $V(\Xi)$ denotes the set of vertices of $\Xi$.

(Note that here $\Xi$ is given as an affine mapping of a polytope, which might complicates the problem a little bit.)

One can solve the problem in a straightforward approach, but I am asking for an ideally polynomial-time algorithm, or any evidence that this is not possible (e.g., NP-hardness).


texts: Combinatorial method for computing the largest eigenvector of the adjacency matrix of a graph

texts:
Given a connected and non-bipartite graph $G=(V,E)$ with vertex set $V=\{1,\cdots, n\}$, let $A$ denote its adjacency matrix and let $deg(i)$ denote the degree of vertex $i$. Let $D$ be a diagonal matrix such that $D_{ii}=deg(i)$ and $D_{ij}=0$ if $i\neq j$. Let $W=D^{-1}A$ be the random walk matrix of $G$.

It's well known that the largest eigenvector (i.e., the eigenvector corresponding to the largest eigenvalue) of $W$ is the probability distribution $\pi$ such that $\pi_i=\frac{deg(i)}{2|E|}$. And there is a simple combinatorial method (in this case, by performing random walk) to approximately computing $\pi$:

perform m random walks of length $l$ from some vertex $i$.
for each vertex $j$, count the number $w_j$ of walks that ending at $j$.

It can be shown that $\frac{w_k}{m}$ is a good approximation to $\pi_k$ under some mild conditions (for example, if $\pi_k$ is 'large'). One merit of such an algorithm is that we can estimate $\pi$ without traversing the whole graph.

My question is:

  Is there a similar combinatorial method for approximately computing the laregest eigenvector of the adjacency matrix $A$, instead of the random walk matrix $W$?


texts:
In Types as Abstract Interpretations, Cousot seems to propose a method to derive various type systems by succesive abstract interpretation
of the denotational semantics of an untyped lambda-calculus. There is a key step missing from the paper. It is claimed that:

  For clarity of the presentation, the design of the Church/-Curry monotype semantics $T^C  ⟦\cdot⟧$ by abstract interpretation of the collecting semantics $C ⟦\cdot⟧$ is postponed to Section 7. Anyway the result is well-known:

However, in section 7 he rather addresses the polytype to monotype abstraction. In summary, what I'm looking for is an explanation on how one derives the type system of Church/Curry monotype semantics (which to me looks like the STLC + recursion + some integer constructs) by abstract interpretation of the semantics.


texts: Fast algorithm for composing Boolean polynomials

texts:
Question: Is there a practically fast algorithm to compose Boolean polynomials ($\mathbb{F}_2[x]$) modulo a fixed Boolean polynomial?

Background: I would like random access within Vigna's xorshift128+ random number generator.  Viewing xorshift128+ as a function $f : \mathbb{F}_2^{128} \to \mathbb{F}_2^{128}$, a fixed jump ahead $f^{\circ n}$ can be efficiently computed by precomputing a degree $\le 128$ polynomial $p_n(x) \in \mathbb{F}_2[x]$ modulo a fixed irreducible characteristic polynomial $q(x) \in \mathbb{F}_2[x]$ also of degree 128.

These polynomials compose: $p_n(p_m(x)) = p_{nm}(x) \mod q(x)$.  Thus, an arbitrary jump ahead polynomial can be formed from a set of fixed jump ahead polynomials by repeated composition mod $q(x)$.

Unfortunately, efficient composition of polynomials appears quite involved (see e.g., http://users.cms.caltech.edu/~umans/papers/U07.pdf which performs multipoint evaluation over extension fields for the small characteristic case).  Involved, unfortunately, means lots of cycles.  I am hoping there is something better in the characteristic 2 case.

Note: I wasn't sure where to put this question.  It might be a better fit for crypto, but it isn't specifically about crypto since xorshift128+ isn't crypto strength.

EDIT: Whoops, actually I can do what I want with only polynomial multiplication, which is much easier.  I'd still be interested in composition, but I'm also fine if the question is deleted.


texts: Generating a language from a given grammar

texts:
So I'm looking for a way of generating all words in language specified by a specific grammar and a alphabet. Is there an easy way to do this? The grammar is a stochastic context free grammar? Is there any software out there that does this? Or a library?

Many thanks in advance


texts:
We know under $ETH$ we cannot solve $K$-SUM in $f(K)poly(nK)$ time under any function $f(K)$ (usually $2^{O(K)}$).

Is there any conjecture that prevents a $(\log n)^{O(K)}$ complexity (this is entirely consistent with possibility as $K=\Omega(n)$ we need exponential time for subset sum) or is such possibility allowed?


texts: Has this online problem been studied before ?

texts:
Consider the following online problem:

  For $\sigma$ and $k$ fixed, given a string of symbols from alphabet
  $[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the
  next symbol belongs in $S$, in space independent of the length of the past
  string.

This problem is similar to online cache management in the sense that failing the guess is a miss, while guessing correctly is a catch. It is much more general than cache management in the sense that symbols can be added to (the cache) $S$ without having generated a miss, just based on correlations previously learned (e.g. $b$ always follows $a$). It presents the same problem of analysis (competitive analysis and the like) than other online problems in the sense that the worst case is intractable while some good performance can be expected on practical instances.

It could have application to caching with pre-fetching. I thought of it while thinking about the dream specs of a diary application on a smart phone (i.e. reduced screen and costly typing), which given the past submissions of the user (went to bed, woke up, ate eggs, took the bus, etc...) must suggest on the screen $k$ activities to be logged next, a menu for others and a field to enter a new one (using the menu is a miss, writing a new one is unavoidable for any solution).  In this case one should consider the space taken by the algorithm: remembering the whole section of previous queries is not an option, only a finite, lossy (ditching outliers) summary of it. One could give additional information to the guesser such as the time of the day, but I do not know how to fit it nicely in the theoretical model.

Was such a problem or a variant already studied? Under which name? Using which model (Dorrigiv and Lopez-Ortiz "cooperative" analysis comes to mind)?


texts: About some possible optimality properties of Ramanujan graphs

texts:
The Ramanujan graphs are optimal from the Alon-Bopanna point of view but..

Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : http://arxiv.org/pdf/0808.0163v3.pdf )

(..At least w.r.t $K_n$ can one say that given any $d$ and $n$, any $d-$regular Ramanujan graph on $n$ vertices, say $R_{(d,n)}$, gives the smallest $a$ s.t $x^T L_{K_{n}}x \leq \frac{n}{d} x^TL_{R_{(d,n)}}x \leq a x^TL_{K_{n} }x , \forall x \in \mathbb{R}^n$?..or some such similar inequality?.. )
Does the usual Cheeger's inequality become sharper if restricted to Ramanujan graphs? Or do we otherwise know of graphs which either saturate the Cheeger's inequality and/or maximize any of the combinatorial notions of expansion?

The only kind of connection I know of between the spectral gap of an expander to its combinatorial expansion are statements like Theorem 4 and 6 here in these notes, http://www.math.rutgers.edu/~sk1233/courses/graphtheory-F11/expander1.pdf. But even this is a lower bound and not an upperbound. One can put in $\lambda = 2\sqrt{d-1}$ in these two theorems but that somehow looks too weak and naive.

I wonder if something sharper can be said about the combinatorial expansion properties of a Ramanujan expander : may be some sense in which one can justify calling them optimal from this point of view too?

Lets say we use the definition of Ramanujan graph as those $d-$regular graphs all of whose  adjacency eigenvalues are of magnitude $\leq 2\sqrt{d-1}$ except the largest and the smallest.
For Cheeger's Inequality lets use the form as in these notes, http://www.eecs.berkeley.edu/~luca/books/expanders.pdf, i.e for a $d-$regular graph,

$$ \frac { \lambda_{1+min}(I - \frac{1}{d}A )}{2 } \leq \phi(G) = min _{ S \subset V, \vert S \vert \leq \frac{\vert V \vert}{2} } \frac {\vert \partial S \vert }{d \vert S \vert }  \leq \sqrt {2\lambda_{1+min}(I - \frac{1}{d}A )}$$


texts: Explaining monad transformers in categorical terms

texts:
Most resource regarding categorical notions in programming describe monads, but I've never seen a categorical description of monad transformers.

How could monad transformers be described in the terms of category theory?

In particular, I'd be interested in:

the relationship between monad transformers and their corresponding base monads;
the relationship between them and the monads they're transforming into new monads;
monad transformer stacks.


texts: Size of cuts in graphs drawn from $ G_{n,1/2}$

texts:
In Luca Trevisan's paper "Psuedorandomness and Combinatorial Constructions", he says that in a graph drawn from $G_{n,1/2}$, for every two disjoint sets A and B there are $(1/2 + o_n(1)) |A||B|$ edges between A and B.

I'm confused as to the exact meaning of this statement. Is it saying that given two disjoint subsets of n vertices selected at random, that's the expected value of the number of edges between them? If so, then doesn't linearity of expectation give |A||B|/2? What is this extra factor of o(1)?

Thanks!


texts: $ACC^0$ implementation of a boolean function

texts:
Consider the symmetric boolean function
$$F(x_1,\dots,x_n)=1\iff\sum_{i=1}^nx_i\mbox{ is a square}.$$
It is implementable in $TC^0$.
Is there an $ACC^0$ implementation?
The reason I ask is there seems to be few tricks which can be deployed.

Square is sum of consecutive odd numbers.

Square is $0$ or $1$ mod $4$ (checkable by $\oplus$ gates).

Squares are the set of the integers having odd number of divisors.

Few are available in https://proofwiki.org/wiki/Category:Square_Numbers.
But is there a finite number of tricks which capture the function and place it in $ACC^0$?


texts: An ETH-hardness sparsity transition for the permanent

texts:
Let $A$ be an $n \times n$ matrix with $0$ or $1$ as entries. Under ETH, the permanent of $A$ cannot be calculated in $exp(o(n))$ time.

Consider $A$ has $O(n^{r})$ entries as $0$ where $r \in [0,2]$. It is reasonable to assume ETH breaks down at $r=0$. Fix a $r_{o} \in (0,2)$. Is there an $s \in (0,1)$ such that $\forall r \le r_{o}$, $Perm(A)$ can be computed in $O(2^{n^{s}})$ time? If so, is there a formula for $s$ in terms of $n$ and $r_{o}$?


texts:
Is there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution.

We know that in the worst case, it is #P-complete, but what can we say about an average instance of #SAT?


texts: Reconstruction of a sequence generated by a Markov chain - reference request

texts:
Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols in the "gaps", is generated by a Markov chain on the alphabet's symbols with an unknown transition matrix, the problem is to design an efficient algorithm that will fill (almost) correctly the gaps , with high probability . More formally , the output sequence must be close (in edit distance , for example) to one of the most  probable sequences, given S and the model. The algorithm receive only the sequence S and must output a new sequence S' generated by filling the gaps in S .

Was this problem or a close variation of it solved ?

This seems to be an important and solvable problem, but I was not able to find any reference . I have some ideas on how to proceed , but I don't want to waste my time on some known result.

I'm imagining the problem can have occurred in bioinformatics or communication theory.


texts: $L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability

texts:
Suppose we have a hypothesis class $\mathcal{H}$ that is non-uniform learnable via sample compelxity function $m_{\text{NUL}}:[0,1]^2 \times \mathcal{H} \rightarrow \mathbb{N}$.
If we define $\mathcal{H}_n=\{h \in \mathcal{H}: m_{\text{NUL}}(0.1,0.1,h) \le n\}$, why is $\mathcal{H}_n$ PAC-learnable?

This argument is used in proof of theorem 7.2 in this book
http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

It is stated that, by assuming realizability, using the same learning algorithm $A$, with probability at least $0.9$ over sample $S \sim \mathcal{D}^n$, we have $L_{\mathcal{D}}(A(S)) \le 0.1$.
But I don't see immediately why this is PAC-learnable because we should be able to compress the error below any $\epsilon$ with arbitrarily high probability $1-\delta$. What is the trick?


texts:
Pumping Lemma essentially implies that for a NFA $N$ having $N_0$ states over a unary language $L_0$ any string belonging to $L_0$ can be obtained by 'pumping' one of the strings that have a length smaller than $N_0$. Thus, a string smaller than $N_0$ that is accepted by $N$ always exists.

Now, since a 2 Way unary NFA also accepts a regular language, for any 2 way unary NFA $M$ having $M_0$ states over a unary language $L_1$ can we state the same regarding smallest accepted string length (using the same pumping lemma) as above w.r.t. $M_0$?

I believe the answer is true, but please confirm?

The exact definition of acceptance we are using is the same as provided in the classic (Hopcroft and Ullman - Formal Languages and their relation to Automata, Section 3.7 - Two-Way Finite Automata):

"A two-way finite automaton will start in state q0 with its input head scanning the leftmost cell on the input tape. Should M ever move off either end of input word x, M halts. An input word will be accepted by M if and only if M eventually moves off the right end of x at the same time it enters a final state.

M can reject a word x by:

1. moving off the left end of x.

2. moving off the right end of x in a nonfinal state.

3. looping."


texts: references for optimal computation under memory constraint?

texts:
Can someone help me find some references for finding good execution schedule given memory constraint? Assuming computation graph is simple in some sense (ie, small tree-width)

There is this reference about the problem being hard in general: "Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems", https://arxiv.org/abs/1109.4910, but I'm interested in a practical algorithm


texts: The Relation between Babbage and von Neumann

texts:
It is well known that Charles Babbage's analytical machine had an architecture strongly ressembling the modern Von Neumann architecture.

Also, it's notable that the tables for representing a program for Babbage's analytical machine ( http://www.fourmilab.ch/babbage/figures/menat3.png ) and von Neumann's work (such as http://library.ias.edu/files/pdfs/ecp/planningcodingof0103inst.pdf ) are quite analogous.

Now I'm wondering if there's any indication to what extent von Neumann knew of the work done by Babbage, and if he used it as an inspiration for his own work.