texts: Status on circuit lower bounds for polylog-bounded depth circuits

texts:
Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ function is not computed by $AC^{0}[q]$", where $AC^0[q]$ is the class of languages decidable by non-uniform, constant depth, polynomial size, unbounded fan-in AND, OR, NOT and modulo $q$ gates, where $\gcd(p,q)=1$. However, getting concrete lower bounds results on polylogarithmic depth circuits seems to be out of reach by using classical methods like restricting inputs and approximating polynomials on finite fields.

I know a STOC'96 paper which leads to geometric complexity theory and which shows that efficient parallel computing using operations without bit-wise ones cannot compute the min-cost-flow problem.

This means that in certain limited settings, we can prove $NC$ lower bounds for some $P$-complete problem.

First, are there other methods or techniques that may be plausible approaches for proving polylogarithmic depth circuit lower bounds?

Second, how useful is the following statement for the theory community?

The size of an $NC$ circuit computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ is at least $l$, where $l$ is some mathematical quantity depending on the hardness of the target function $f$. The value of $l$ may be, for example, a combinatorial quantity like discrepancy, a linear algebraic quantity like the rank of certain type of matrix over a field, or some entirely new quantity which has not previously been used in complexity theory.


texts: Results/concepts that also proved useful outside of their "home areas"

texts:
There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used in many papers that are not about complexity theory. This is an indication of the general usefulness and importance of the concept.

Similarly, network flow algorithms, shortest path algorithms etc.,  have combinatorial optimization as their home area, but are also used in many papers that are not specifically about combinatorial optimization. Graphs have graph theory as their home area, but are used in many other fields, as well.

Question: What are some other, not so obvious or not so well known examples of methods/concepts that also proved useful outside of their home areas?


texts: Nonstandard dual parametrization of graph problems

texts:
One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when parameterized by the "dual parameter" $|V(G)|-k$, it becomes equivalent to INDEPENDENT SET parameterized by solution size (because any vertex cover is the complement of an independent set), and thus it is W[1]-hard.

Although this seems less natural, I am interested in the parameterized complexity of VERTEX COVER for the parameter $|E(G)|-k$. This is a larger parameter than $|V(G)|-k$. Is VERTEX COVER FPT for this parameter?

Note: I am also interested in similar parameterizations for other graph problems (e.g. DOMINATING SET). The only place where I have seen both kinds of dual parameters studied is for the hypergraph problem TEST COVER in the 2012 paper "Parameterized Study of the Test Cover Problem" by Crowston, Gutin, Jones, Saurabh and Yeo. (also on arXiv)

Edit (04/12/2016): This parameterization is also studied for the other hypergraph problem HITTING SET in the 2011 paper Kernels for below-upper-bound parameterizations of the hitting set and
directed dominating set problems by Gutin, Mones and Yeo (arXiv link).


texts: Implications of faster randomized $CIRCUIT SAT$ algorithm

texts:
In here on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'.

Can we have randomized $2^{n^{o(1)}}poly(m)$ time in above statement?
Is there a similar result that would give $E\not\subseteq SIZE(2^{\delta n})$ (this would give $P=BPP$)?
How large can $o(1)$ be in the statement above and in 1. if applicable (can it be as large as $1/\log\log n$)?


texts: how to define "correlation" between languages?

texts:
How does one define the concept of correlation between languages?
Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this setting?
Was thinking could use the algorithmic mutual information between their descriptions--maybe this works for languages with finite descriptions?


texts: Complexity of propositional LTL with past operators and freeze quantifier?

texts:
In "A Really Temporal Logic", by R.Alur and A.Henziger, they introduce an extension of Linear Temporal Logic with a freeze quantifier $x.\phi$, which allows to "give a name" to the current time point to later compare it with others. An example formula from the paper is

$$
\Box x.(p \to \Diamond y.(q \land y \le x + 10))
$$

which means that whenever $p$ holds, $q$ must eventually hold within 10 time points. This logic has been proved to be EXPSPACE-complete in the above paper.

Since the paper is very old, I'm wondering which developments have been done on this logic.
Specifically, I'm asking if it has been proved whether this logic augmented with LTL past operators is still EXPSPACE-complete, as is the case for classic LTL+past which remains PSPACE-complete as the future-only version.

I've found something by searching for "freeze quantifier" but recent works such as this paper talk about further extensions with registers that I'm not interested about (or maybe I am but I'm misunderstanding).

So is this logic augmented with past operators still EXPSPACE-complete?


texts:
By Circuit Minimization, I am referring to the following decision problem.

  Circuit Minimization

  Input: A bit string $x$ and a number $k$.

  Question: Does there exist a Boolean Circuit $C$ of size at most $k$ that prints $x$?

By $C$ prints $x$, I mean that the following are satisfied:

(1) The circuit $C$ has $\lceil \log_2(\vert x \vert)\rceil$ inputs.

(2) Consider lexicographically ordering bit strings of length $\lceil \log_2(\vert x \vert)\rceil$.  For each $0 \leq i < \vert x \vert$, let $w_i$ denote the $i$th bit string and $x_i$ denote the $i$th bit of $x$.  We have $C(w_i) = x_i$.

  My Question

  Is Circuit Minimization $P$-hard under logspace reductions?

I know that others have asked if this and related problems are $NP$-hard, but I am wondering if it is hard for any smaller complexity classes such as $P$ or $L$ under appropriate kinds of reductions.

If this is an open problem, then what are the implications if it is $P$-hard?


texts: It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?


texts: What are good books for learning grammar ( BNF )?

texts:
I'm taking a basic course on programming language theory, and we're covering context-free grammar (BNF). Personally, I'm really interested in how to design syntax for a programming language. I'm planning to write a simple compiler for my graduate project, so what books are good for this area? Any feedback would be greatly appreciated.

Thanks,
Chan


texts: Combining (block)-sensitivity and Lipschitz conditions?

texts:
If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a single bit of $w$ and changing the value of $f$. The sensitivity of $f, s(f)$ is then the maximum sensitivity with respect to any $w \in \{0,1\}^n$.

If on the other hand we're given a real-valued function $f : \mathbb{R}^n \rightarrow \mathbb{R}$, we can talk about its Lipschitz constants: specifically, the maximum value (wrt $x,\epsilon$) of the ratio $\frac{|f(x+\epsilon) - f(x)|}{\epsilon}$ as a kind of "smooth sensitivity".

What if we combine the two ? Suppose we have a function that takes parameters in a continuous domain, but whose output is discrete (one example might be a binary classifier, where the function is the sign of an appropriate hyperplane evaluation for example). Is there a natural notion that captures sensitivity in such a setting ? Boolean sensitivity doesn't work itself because you have to choose how much to perturb the inputs. Smooth perturbations don't quite work because the function is not continuous, and so any ratio would be rather unstable.

I suspect that either such a notion is very well known, or follows directly from the above, and so I'd be grateful for suggestions to reformulate the question/make it more precise.


texts: Complexity lower bound: the gap between decision trees and RAMs

texts:
I recently discovered a quadratic lower bound on the complexity of a problem in the decision tree model, and I wonder whether this result could be partially generalized to the random access machine model. By partially, I mean a generalization to RAM programs with a certain time/space tradeoff. For instance, I'd like to show that my problem cannot be solved by a linear-time and -space RAM program.

A.M. Ben-Amram and Z. Galil proved in this paper that a RAM program running in time $t$ and space $s$ can be simulated in $O(t \, \log s)$ time on a pointer machine. Do we know similar results which could be applied to decision trees?

Alternatively, is it possible to simulate a RAM program running in space $s$ with a decision tree of degree $s$? (intuitively, indirect addressing could be simulated using nodes of degree $\leq s$)


texts: Size of Independent set of sparse graphs with few triangles

texts:
Notations

$\alpha(G) = $  Max sized independent set of graph $G$.
$n(G) = $ Number of vertex in graph $G$.

Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$,

$$\alpha(G) \geq \frac{n(G)}{8\Delta}\log_2\Delta.$$

For a general graph, $\alpha(G) \geq n(G)/(\Delta+1)$, hence the above result is an improvement by a factor of $\log_2\Delta$. The proof of the above theorem is solely based on the triangle-free property of the graph.

My question: Can one obtain $\alpha(G)$ better than $n(G)/(\Delta+1)$ for graphs with only few triangles?

EDIT 1 - I am looking for solutions where number of triangles, $t=O(n)$.

EDIT 2

In the paper, lemma 6 has the following result.

Theorem : For a graph $G$ having maximum degree $\Delta$ and having at most T triangles,
$$\alpha(G) \geq \frac{n(G)}{10\Delta}\Bigg(\log_2\Delta - \frac{1}{2}\log_2\Big(\frac{T}{n(G)}\Big)\Bigg)$$

But I am not able to find the proof for the above theorem.

EDIT3: Thje proof can be found in "Random Graphs , 2nd edition", pg 332.


texts:
I'm experimenting with optimizing reduction strategies for the untyped lambda calculus.  Is there any (publicly available) dataset of (terminating) lambda terms I could use?

Maybe it would be possible to scrape code from commonly used programming languages and compile it down to LC...

Best,
Paul Gustafson

P.S. Please let me know if there's a better forum for this question.


texts: Is there a counting complexity class for succint problems?

texts:
Encoding NP-complete problems succintly often makes them NEXP-complete. I am wondering if counting the number of solutions to such a problem with a succint encoding would be any harder than solving the original succint problem.

For instance, if we use a circuit encoding to represent a 3CNF formula, we obtain SUCCINCT 3SAT, which is NEXP-complete. What is the complexity of counting the number of satisfying assignments to a 3CNF formula represented as a circuit?

#NEXP would be a natural name for the resulting class, but I cannot find any reference to such a class. Can it be easily shown to be equivalent to NEXP?

The following question is related, but maybe focussing on NEXP which exhibits non-determinism would make it easier to find an appropriate answer.
What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?


texts:
I was trying to understand these classes but always got confused ... the questions are :

What is the relation between $FNP$ and $\#P$ , in particular is it an open question ?

What is the relation of $\oplus P$ and $NP$ ? is this question open ?

What about the relationship between $PH$ and $P^{FNP}$ ? is this question open ?


texts: Looking for an exposition of the proof of the LMN theorem

texts:
Is there any lecture note or review paper which gives a self-contained proof of the Linial-Mansour-Nisan theorem?

The exposition of that in Ryan O'Donnel's book seems to use terminology and notation which isn't easy to parse unless one reads many pages before that. Most lecture notes I found only at best mention it in the passing.


texts: Minimal information needed for determine some function

texts:
From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of information" is sufficient to describe a continuous function completely.
Is there a similar notion for computable functions (or Turing machines)? i.e.:
Let $T : \{0,1\}^* \rightarrow \{0,1\}$ be a Turing machine and let $\{0,1\}^{n_0}$ be the set of all binary string of lengh $n_0$. Describing $T$ on $\{0,1\}^{n_0}$ trivially requires $2^{n_0}$ values. Can we impose conditions on $T$, which will reduce $2^{n_0}$ (like continuity in the continuous domain)? Can we hope for non-trivial such conditions?


texts: For median is it optimal to compare in pairs first?

texts:
Median can be done in linear time and is now down to (I think) $2.97n$.
The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small.

The following theorem, if true, may help improve lower bounds in general and
upper bounds for particular small values of $n$:

  If MEDIAN of $n$ elements can be found
  in $f(n)$ comparisons (worst case)
  then there is an algorithm taking
  $f(n)$ (perhaps $f(n) + O(1)$) that
  initially compares all of the elements
  in pairs.

One can also look at other selection problems, element distinctness, sorting,
and other such problems.

(Meta Question - I couldn't find a good tag for this so I used lower-bounds.
Is there a better one that I missed?)


texts: Lower bound on the element distinctness problem

texts:
The element distinctness problem asks whether any two elements of the input
sequence $<x_1,\ldots,x_n>$ are equal? This problem has a lower bound of
$\Omega(n \log n)$ in the algebraic decision tree model when the $x_i$'s are
real numbers. My question is what is the lower bound if we restrict the $x_i$'s
to positive integers?


texts: What is the complexity of the set of closed boolean tautologies assuming well formed formulae?

texts:
Let's define two CFGs:

S  ::= 0 | 1 | (S+S) | (S*S)
S' ::= 0 | 1 |  S+S  |  S*S  | (S)

And two languages:

M  = { w | S  generates w, and w evaluates to 1 }
M' = { w | S' generates w, and w evaluates to 1 }

In both cases, evaluating is done by interpreting + as logical or, * as logical and, and in the case of M' by being careful about * having higher precedence than +.

Suppose w is in S, and u is in S'. My questions are:

Is there a finite automaton (or a regex) that can decide wheter w is in M?
Is there a finite automaton (or a regex) that can decide wheter u is in M'?
Suppose S ::= 0 | 1 | +SS | *SS. (Prefix notation) Does this change the answer to question 1?

I'm aware that without knowing whether w is in S, deciding if w is in M isn't solvable by finite automata due to pumping lemma (we'd have an issue with parentheses), similarly for u, S' and M'. However, knowing that w is in S (and u is in S') might make the problem significantly easier.

Note: if the answer is yes, please write the grammar/regex/proof sketch/explanation in spoiler tags. :)


texts: Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

texts:
Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such polynomials?

Assume $GCD$ of coefficients is $1$ after removing denominator.

  Is there an algorithm that is polynomial time in complexity in degree, variables and logarithm of number of bits in coefficients?


texts: Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs

texts:
Let $G=(V, E)$ be an undirected simple graph.

Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space complexity ?

(by polynomial time delay it is meant that the time spent between the outputting of any two subsequent maximal bipartite subgraphs is polynomial in $|V|$)


texts: Generating "infinite" randomness from a constant number of sources

texts:
I recently came across a paper by Coudron and Yuen on randomness expansion using quantum devices. The main result of the work is that it is possible to generate "infinite" randomness from a constant number of sources (that is, the number of random bits generated depends only on the number of rounds of the protocol and not on the number of sources).

Naively, this sounds to me like the result allows derandomization of any randomized algorithm with quantum sources, and would imply some kind of containment of randomized complexity classes inside a corresponding quantum class.

But I don't really understand quantum information theory, and am sure there are many subtleties I'm missing. Not to mention that if such claims were possible, the authors would have made it. So my question is:

  Does the existence of "infinite randomness expansion" as described in the paper (and all the related work) imply some kind of derandomization statements for randomized complexity classes ? And if not, why not ?

Update: I was pointed to this excellent high level overview of the area and of the above paper by Scott Aaronson. Unfortunately I'm still confused :).


texts: Complexity of finite-state partial information games

texts:
Given a deterministic partial-information zero-sum game with only finitely many states,

  whose possible outcomes are [lose,draw,win] with values [-1,0,+1] respectively,

  what is the complexity of approximating the value of such a game additively within $\epsilon$?

In particular, I can't come up any algorithm whatsoever for doing that.
The rest of this post is devoted entirely to giving a more thorough description

of the problem, so if you can already figure out what the question at the top

of this post means, then there's no reason for you to read the rest of this post.

Given a referee machine with states $\{1,2,3,...,S\}$, with a designated initial state $s_0$, a state $s_a$
whose score pair is $[-1,+1]$, a state $s_b$ whose score pair is $[+1,-1]$, and states of the form

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ where:

$\mbox{player_to_move} \in \{1,2\}$
$\mbox{next_state_table}$ is a function from $\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
$\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

When the machine is in a state of that form:

sends $\mbox{p1_info}$ to Player_1 and sends  $\mbox{p2_info}$ to Player_2,
sends $\mbox{num_of_choices}$ to the indicated player, waits for an element of $\{1,2,3,...,\mbox{num_of_choices}\}$
as input from that player,
then goes to the state indicated by $\mbox{next_state_table}$

When the machine enters one of the other two states $s_a$ or $s_b$,

halts with that state's score pair as its output

There is a natural two-player game: the referee machine is started in state $s_0 = 1$,

the players provide the inputs that the referee machine waits for, if the referee machine

halts then Player 1 scores the first value of the machine's output pair and Player 2

scores the second value of the machine's output pair, otherwise both players score 0.

  What is the complexity of the following problem?

  Given such a referee machine and a positive integer N, output a rational number

  that is (additively) within 1/N of the value of the natural game for Player 1.

As mentioned earlier in this question, I can't come

up with any algorithm whatsoever for doing that.


texts: Does anyone know of a direct quantum algorithm for computing GCD, - There could be quantum gates for addition subtraction constructed explicitly, using CNOT, etc. - the construction can be done in some poly(n) of input, (this is just a guess), but is there any algorithm, scheme for computing GCD, using quantum algorithms, gauss sums, QFT, quantum approximation, anything(!!) thanks,


texts: deterministic randomness extractor and privacy

texts:
Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over  the channel $P_{Y|X}$ which outputs $Y$ taking values on finite alphabet $\mathcal{Y}$. Suppose we take $n$ independent samples from channel output; namely, $Y^n=(Y_1, Y_2, \dots, Y_n)$ with distribution $\prod_{i=1}^nP_{Y|X}(y_k|x)$ where $x$ is the message sent over the channel.

Hence, we have $m$ distributions $\{P_{Y^n|X}(\cdot|x_1), \dots, P_{Y^n|X}(\cdot|x_m)\}$. I am looking for a deterministic randomness extractor which works for all of these $m$ distributions, that is, a randomness $Ext:\mathcal{Y^n}$ such that for given $Y^n$ distributed as one of these $m$ distribution $Ext(Y^n)$ is $\epsilon-$close to uniform distribution over $\{0,1\}^r$ (in total variation distance sense).

What is the largest random bits that we can extract, i.e., the largest $r$?
Is that $\min_{x}H_{\infty}(P_{Y^n|X}(\cdot|x))$?

The motivation of this comes from privacy.


texts: Concentration of Stationary Distribution on Random Directed Graphs

texts:
We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. This corresponds to a model of random automata over an alphabet of size $d$.

Denote by $n$ the number of vertices in the graph, which is finite. Thus there must exist a stationary distribution $\pi$ of the random walk on the graph, regardless of whether it converges. For symmetry, the expectation of $\pi(i)$ is $1/n$ for all $i$.

I want to show that with high probability, $\min_i\{\pi(i)\}$ is not too small, i.e., at least polynomially large w.r.t. $n$. Since the graph is not necessarily strongly connected, we only consider the strongly connected component. More strictly, I want to show that with high probability, $\min_i\{\pi(i) \mid \pi(i)>0\}$ won't be too small. Any literature on this?

By "high probability", I mean the probability goes to $1$ when $n \to +\infty $.

A most recent related work could be [Kenter 2013]. However, their model is different from mine and more like the Erdős–Rényi model.

Thank you.


texts: Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?

texts:
It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$.

This can easily be understood inductively using oracle machines.
The question is - why can't we continue the inductive process beyond a constant level of alternations and prove $\mathbf{P}=\mathbf{AltTime}(n^{O(1)})$ (aka $\mathbf{AP}=\mathbf{PSPACE}$)?

I am looking for an intuitive answer.


texts:
Can the following all hold simultaneously?

$L_s$ is contained in $L_{s+1}$ for all positive integers $s$.
$L = \bigcup_s L_s$ is the language of all finite words over $\{0,1\}$.
There is some complexity class $C$ and a notion of reduction appropriate for $C$ such that for each $s$, $L_s$ is hard for $C$.


texts: Why isn't the decrease key operation in a pairing heap $O(1)$

texts:
According to the paper (1986)

Decrease-key is implemented by first by removing the node from the tree $O(1)$, decreasing the key $O(1)$, then linking it with the root node $O(1)$. The paper admits this as well.

I must be missing something since this paper shows that it is $\Omega(\log \log n)$ amortized.


texts: How can I optimize my brute-force solution to this problem?

texts:
I am working on a solution to the problem explained below. I am using brute force, I have reached the point where solutions are prohibitive, so I need to optimize more (if possible).
Of course, it will be even better if there is a better way to solve the problem (not brute force).
Is there anything I can do to improve my solution, or reference I can look into (similar problems, etc)?
The problem
We start with a rectangular board. Each cell can be in N states, and the initial state for each cell is random (0 <= state < N) for each cell.
We also have a number of shapes, all fit inside the board. Every shape is continuous.

Each shape must be placed once (and only once) in the board.
When a shape is placed, each cell that belongs to the shape will have its value increased by 1. If the board value in any cell reaches N, it is changed to 0.
The goal is to find the positions each shape must be placed so that the final board has all cells with value 0. There is always at least one solution. Let's suppose the problem is generated by starting from the finished board and applying random shapes in random positions.

The board size, number of states N and number of shapes are the setup of the game, and keep increasing (at different rates) for each 'level'.
What I am doing currently
I am able to solve the problem up to a certain size by just using brute force. I have a few optimisations in place. I have reached a point where the solution is prohibitive, so I would like to improve my logic.
First thing I am doing is order the shape from larger to smaller, the smaller will be moved in the internal iterations. The assumption (which I haven't proved, but tested to be faster) is that it's better to move the smaller shapes more, since they have a higher chance to generate a solution.
Secondly, for repeated shapes, I avoid checking all the permutations, since they yield the same result. I also only check one set of positions when a pair of same shapes overlap (since all overlaps yield the same result).
One final optimisation that I think will help a lot, but I am still implementing is: at each shape in the sequence, count the total of cells in the shapes that remain to be moved. This number, minus the total cell flips needed to get a finished board, must be a multiple of N. If not, it's no point brute forcing the remaining shapes positions, and we must re-position a shape in an external loop.
Extra details
I am interested in any other tips on how to optimize this. Known algorithms, even a good naming for this set of problem, that I can use to research more would be great.


texts: the type system does not tell the whole story due to "exception"

texts:
I am wondering whether it is a bad style to use "exception". For example, in Ocaml, the exception does not appear as the .mli file. So it appears to me that "exception" is something that cannot be tracked by a type system.

So my question in general is, is using exception a bad style because it hides information against the type system?

Concretely, I am trying to implement a type checker for an imperative language, say, Pascal. The essential judgment should have been of this signature,

well-typed_1: environment -> statement -> unit

But this seems to be insufficient because the environment would be modified due to a local variable declaration, thus a more reasonable interface for typechecker would be

well-typed_2: environment -> statement -> environment

An alternative would be use the former one, well-typed_1, dealing with local variables declaration through an exception Var_declaration (e : environment) which returns the updated environment to the type checker for its other recursion.

So, my question for this concrete example is , should I use the well-typed_1 + exception for variable declaration, or well-typed_2?

The disadvantage of well-typed_2 seems to be that, for most statement there are no side effect with regard to environment of types, thus that signature of well-typed_2 seems to be a bit redundant. The disadvantage of well_typed_2 + exception seems to reveal a general issue: the the signature of well-typed_1 in does not tell the whole story. (it does not tell the potential exception)


texts: A random ensemble of sparse boundary operators

texts:
The following question arises from the study of quantum error correction, and high-dimensional expanders:

Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear operator $:\partial: F_2^n \to F_2^n$ , such that $\partial^2 = 0$, and each row/column of ∂ has Hamming weight at most d, and rank(∂)=r?

Note, that for d = n, i.e. boundary operators that are not sparse, the question can be solved in a straightforward manner as outlined in a paper of Bravyi and Hastings [Homological Product Codes]: one considers some fixed matrix Q - such that dim(im(Q))=r, and im(Q)⊆ker(Q) - and then the distribution is the set of matrices $A Q A^{-1}$ where A is a random invertible matrix over $F_2^n$.

Hence, the question is, whether the extra sparsity condition makes the problem intractable or not.

The importance of the question relates to the quantum LDPC conjecture: ideally, we would want to find such a procedure for $d=O_n(1)$. A solution to this question would at least imply that there exists some candidate ensemble where we can find good quantum LDPC codes - specifically of a type called CSS codes.


texts:
Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-assisted and quite intimidating.

There are several conjectures in graph theory that imply 4CT. Resolution of these conjectures probably requires a better understanding of the proofs of 4CT. Here is one such conjecture :

Conjecture : Let $G$ be a planar graph, let $C$ be a set of colors and $f : C \rightarrow C$ a fixed-point free involution. Let $L = (L_v : v \in V(G))$ be such that

$|L_v| \geq 4$ for all $v \in V$ and
if $\alpha \in L_v$ then $f(\alpha) \in L_v$ for all $v \in V$, for all $\alpha \in C$.

Then there exists an $L$-coloring of the graph $G$.

If you know such conjectures implying 4CT, please list them one in each answer. I could not find a comprehensive list of such conjectures.


texts: NP algorithm for an optimization problem

texts:
Consider the following optimization problem

INSTANCE: vectors $\vec{a}, \vec{b}, \vec{c}$, matrices $A, B$, threshold $\theta$.
PROBLEM:
Let $f={\displaystyle \max_{\vec{x}, \vec{y}}} (\vec{x}+\vec{c}) \cdot \vec{y}$
subject to $A\vec{x}\leq \vec{a}$ and $B\vec{y}\leq \vec{b}$
Is $f \le \theta$ ?

This problem is in co-NP (provide a witness that $f > \theta$).

Is this problem in NP ?


texts: Density of distinct satisfying assignments for uniquely satisfiable formulas

texts:
Motivated by the NP-completeness of Another-SAT problem, Another-3SAT={$(\phi, m)$: 3CNF formula $\phi$ has a satisfying assignment different from $m$ }, Let us consider a function from all uniquely satisfiable Horn 3SAT formulas on $n$ variables to binary strings of length $n$ (representing unique solutions). I'm interested in the density of the range of this function. A set is sparse if the number of strings in the set of length $n$ is bounded by a polynomial in $n$ otherwise it is dense.

What is the best known lower-bound for the asymptotic growth rate of the number of distinct satisfying assignments for uniquely satisfiable Horn 3SAT formulas on $n$ variables? Is this set dense?

EDIT: Thanks to Tsuyoshi,I realized that the original question had a mistake. So I changed the question to be about uniquely satisfiable Horn 3SAT.


texts: Time complexity of clustering based on random walk

texts:
What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph?

Can I use the complexity of eigen vector computation for this purpose?

The Algorithm:

Given a directed graph $G = (V,E)$, it may be partitioned into two parts as follows:

Define a random walk over $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution. In this part I need to compute the eigen vectror transition matrix $P$.
Let $\Pi$ denote the diagonal matrix with its diagonal elements being the stationary distribution of the random walk. Form the matrix $£ = \frac{(\Pi^{1/2}P\Pi^{-1/2} + \Pi^{-1/2}P{T}\Pi^{1/2})}{2}$.
Compute an eigenvector $\phi$ of $\theta$ corresponding to the second largest eigenvalue, and then partition the vertex set $V$ of $G$ into the two parts.


texts: SVM - running time for detecting if data is linearly separable?

texts:
If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the data is linearly separable if and only if such a hyperplane exists.

If the data consists of $m$ pairs $(x_1, y_1), \ldots, (x_m,y_m)$, with $x_i \in \{0,1\}^n$ and $y_i \in \{0,1\}$, do we know what the worst case running time is for finding whether or not a maximum margin hyperlane exists?

I can't seem to find a straightforward answer to this. Section 1.4.2 of this says something about complexity and the number of support vectors, but the section also begins by mentioning a lower bound.

Also, this seems to cite a running time of $O(max(m, n) \times min(m, n)^2)$, at least for the running time of the optimization part of the problem.

These texts are not clear to me. Can someone break down the running time for this algorithm? Is the worst case running time known? Can SVMs detect if the $m$ points are linearly separable in polynomial time?

p.s. I am aware that linear programming can solve this in polynomial time ($\text{poly}(mn)$ I think?), but I would like to know how support vector machines behave here.

Edit: The Bottou, Lin chapter seems to come from this book.


texts: Does the following 2-rounds distributed algorithm approximates a maximal matching well?

texts:
Let $G$ be an undirected graph.

I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible.

Consider the following protocol for vertex $v$.

Use a fair coin to choose a ``status'' $s_v\in\{\mathit{active},\mathit{passive}\}$.

2.a. If $s_v=\mathit{active}$ send request to a random neighbor.

2.b. If $s_v=\mathit{passive}$ and you have received at least one request, respond with accept to a single requestor, chosen at random.

Each request paired with accept adds an edge to the resulting matching.

Let $M$ be a minimum maximal matching (i.e., the maximal matching with the smallest cardinality) of $G$, and let $M'$ be the matching generated by the above algorithm.

  What can we say about $\mathbb E[|M'|] / |M|$? is the generated matching expected to be a good approximation for a maximal matching? e.g., do we have $\mathbb E[|M'|] / |M|=\Omega(1)$ for any graph $G$?


texts:
Let $S$ be a multisorted algebraic signature with function symbols $f_0, f_1, \ldots$. For every $i$, I partially know “constantness” of $f_i$. (I have no precise definition of constantness yet.) Examples:

Let $\cdot$ denote multiplication of numbers. If $x_0=0$, then $x_0\cdot x_1$ is constant.
Conditional operation. If $x_0=0$ and $x_2$ is constant, then  $\operatorname{if}x_0\operatorname{then}x_1\operatorname{else}x_2$ is constant.

I need to find a strongest constantness judgement for any term over $S$ given constantness of its variables. Is there an established way of reasoning about constantness?

A purpose is that every term in $S$ defines a function from program states to a pixel on a screen. Variables of the term are components of a state, i.e. the set of states is a Cartesian product. For every pixel $p$, if its term is found to be non-constant then I need to redraw $p$.


texts: Approximation algorithms for Maximum Independent Set on special classes of graphs

texts:
We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better approximation algorithms are known?

What are the graphs for which polynomial-time algorithms are known? I know for perfect graphs this is known, but are there other interesting classes of graphs?


texts: Can a tractable sequence distribution prefer satisfying to unsatisfying assignments?

texts:
Let $p(x)$ be a Boolean circuit on $n$ bits $x \in \{0,1\}^n$.  Consider a program that computes a probability distribution over all sequences $x$, autoregressively factored as
$$\pi(x | p) = \prod_{0 \le k \lt n} \pi(x_k | p, x_{<k})$$
That is, each $\pi(x_k | p, x_{<k})$ is the output of a program which takes as input $p$ and $x_{<k}$ and produces two probabilities summing to 1 for whether $x_k$ is 0 or 1.  I believe the following is true:
Conjecture: There is no polynomial time $\pi$ s.t. for all circuits $p$ and all satisfying assignments $x$ and unsatisfying assignments $y$ of  $p$, $\pi(x | p) > \pi(y | p)$.
Intuitively, the reason I believe this is that since conditional probabilities sum to 1 and the policy is causal (probabilities depend only the past), ensuring that satisfying assignments get high probabilities will require us to predict in advance whether a partial  assignment  is  likely  to  be  satisfying,  and  these  partial  predictions  are hard.  In particular, if one partial sequence $x_{<k}$ gets at least as much probability as another $y_{<k}$, but all completions of $x_{<k}$ are sat while all completions of $y_{<k}$ are unsat, at least one pair of completions will violate the claim.
However, I haven't managed to turn this intuition into a proof, and regardless the claim has to be "very close", since the uniform distribution satisfies the condition with $>$ replaced with $\ge$.  Moreover, the extreme case mentioned in the intuition is easy to rule out, simply by checking one particular completion.
I'm happy to assume a strong complexity class separation statement such as ETH or SETH to get the result if assuming $P \ne NP$ is insufficient.


texts: Complexity of multi-linear polynomial computing Boolean function

texts:
Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual,
let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest
Boolean circuit computing $f$.

As we know that every Boolean function
can be computed by polynomials in $\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$.
Let $P(f)$ be the size of the smallest arithmetic circuit(over
$\mathbb{F}_{2}$) which computes
a polynomial $P_{f}$ such that $P_{f}$ computes the same function
as $f$ on $\mathbb{F}_{2}^{n}$(correspondingly $\{0,1\}^{n}$).

It is known that $P(f)\leq\textrm{poly}(C(f))$ and $C(f)\leq\textrm{poly}(P(f))$.

We also know that there is a unique multi-linear polynomial $M_f\in\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$ such that $M_{f}$ computes the same function as $f$ on $\mathbb{F}_{2}^{n}$(correspondingly
$\{0,1\}^{n}$). Let $M(f)$ be the size of the smallest arithmetic circuit(over
$\mathbb{F}_{2}$) computing $M_{f}$.

It is clear that $C(f)\leq\textrm{poly}(M(f))$.
How about other direction?

  Can we bound $M(f)$ polynomially in terms of $C(f)$?

Anything is known about this or something related?


texts:
What is the upper bound on the simplex algorithm for finding a solution to a Linear Program?

How would I go about finding a proof for such a case?
It seems as though the worst case is if each vertex has to be visited that is it $O(2^n)$. However in practice the simplex algorithm will run significantly faster than this for more standard problems.

How can I reason about the average complexity of a problem being solved using this method?

Any information or references are greatly appreciated!


texts: Definition of Rabin acceptance condition for omega automatons

texts:
I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left set in a pair must not be empty, but I cannot figure out why. Since the condition requires that at least one of the pairs will have none of the states on the left being visited infinitely often, and at least one of the state on the right be visited infinitely often, an empty left set seems to mean just that for every pair in the condition it is true that none of it's states is being visited infinitely often.
So my question is: why can't the left side of the pair be empty?


texts: Algorithm for permuting elements using constant work space

texts:
I'm searching for an algorithm to do the following:

A 1->3
B 2->6
C 4->5
D 5->2
E 6->4
F 3->7
G 8->9
H 10->11

Elements A-H are stored on locations 1 to 11 (some locations are vacant).
We need to move the elements from their original position to the new position.
What order requires the least amount of steps?

possible solution:

G 8->9   in step 1
F 3->7   in step 1
E 6->11  in step 1
A 1->3   in step 2
B 2->6   in step 2
C 4->5   in step 3
E 11->4  in step 4
D 5->2   in step 4
E 1->4   in step 5
H 10->11 in step 5

Notice that E is moved twice because of a loop: C->D->B->E->C

Edit

this is more complex then it seams:
the longest time that you'll need is:

the longest cycle + the shortest chain + 1

or

the longest chain (if that is longer then the one above)

right?

not:

suppose we have the first case:

long cycle + short chain

in step 1 we break the cycle by moving element Z start fixing other chains

in step x we have finished some of the shorter chains.
meaning: we have some extra free places.
so we can use those to move element Z to.
with element Z out of the way we can fix the shortest chain before the longest cycle is finished:

making the least possible steps:

the longest cycle + 1

but if we only have cycles and they are equally long then the minimal number of steps becomes:

1 + one cycle + last cycle

any ideas of an approach to this problem?


texts:
This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind.

I have a set of real vectors:

$$
S = \lbrace v_1, \dots, v_n \rbrace
$$
$v_i \in \mathbb{R}^d$ where $d \approx 100$. Typically the size of this set, $n$ is around 20,000,000:

In practice if I have $v_1$ and $v_2$, I can find the distances between them (say using Euclidean distance).
Consider a different problem: I have $v_i \in S$ and I want to find all of the $k$ ($\approx 20$) closest vectors to $v_i$ in the $S$.

Any efficient algorithm/technique/datastructure for this purpose?

I am interested in either piratical solutions and theoretical results.
Even if you have approximate solutions I am interested in.

Update: Here is a similar question I came across but I think they are different: Calculating the distance to the kth nearest neighbor for all points in the set


texts: Graph classes in which CLIQUE is known to be NP-hard?

texts:
Given a graph $G$ and a positive integer $k$, the CLIQUE problem asks if $G$ contains a clique (complete subgraph) on at least $k$ vertices. This problem is long known to be NP-complete --- in fact, it was one of Karp's list of 21 NP-complete problems. My question is:

  For what restricted families of graphs is CLIQUE known to be NP-complete?

I could find one such graph class with Google's help: the class of $t$-interval graphs for any $t\ge 3$ (Butman et al., TALG 2010) [1].

Do you know of other graph classes where this problem has been shown to be NP-complete?

[1] Butman, Hermelin, Lewenstein, Rawitz. Optimization problems in multiple-interval graphs. ACM Transactions on Algorithms 6(2), 2010


texts: What would signify hierarchy collapse to first level?

texts:
We know that
$$\mathsf{NP\subseteq P/Poly \iff coNP\subseteq P/Poly\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P}$$
$$\mathsf{NP\subseteq P/Log\iff coNP\subseteq P/Log\implies PH=\Sigma_0^P=\Pi_0^P}$$

  Is there any circuit result that could imply
  $$\mathsf{PH=\Sigma_1^P=\Pi_1^P}$$ but still $$\mathsf{PH\neq\Sigma_0^P=\Pi_0^P}$$ is a possibility?

  Is there a possible similar collapse result from non-circuit containment?

Conjecture:

  Such result does not exist.


texts: Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

texts:
In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. Clearly, the brute-force algorithm enumerates all possible vertex orderings and runs in $O(n!)$.

There is a elegant D&C (divide & conquer) style algorithm in Gurevich1987 which is stated to run in $O(2^{2n}\times2^{O(l)})$ with $l=\log_2 n$. But after checking several times the proof and performing an analysis in a different way, I would believe that the correct running time is rather $O(2^{2n}\times n^{O(l)})$. Interestingly, in that paper, this expression also appeared once, perhaps it's a typo, but it makes things really confusing for me.

In the following, I first provide some pointers then put the main idea of D&C and my own analysis.

The paper: expected computation time for hamiltonian path problem
The algorithm is called HPA3 on page 499 and 500.
P499, 3rd line from the bottom: ...run-time...$2^{2n}$ times a polynomial in $n$
P500, point (b), $T(n)=2^{2n}\times n^{O(l)}$ (which is a contradiction)
P500, ...choose a $c$ such that $T(n)=2^{2n+cl}$....

Main idea of D&C
Very simple, guess the middle vertex (note $m$) in the path $(s,t)$, then try all possible subset $A\subset V$, $|A|=(n-3)/2$, assuming the the path is somehow like $s,A,m,(V-A),t$. This divides the input instance into two half-size instances, and it yields a recurrence relation: $T(n)\leq (n-2)2^{n-3}T((n-3)/2)$, with $b$ some unknown constant.

My analysis
To be simpler, note $n$ as the number of vertices except $\{s,t\}$. Then $T(n)\leq n2^nT(n/2)\\ = 2^{n(1+1/2+1/4...1/n)}\times (n*n/2*n/4*...*1)\\
\leq 2^{2n}\times n^{\log n} \ (2^{1+2+...+\log n}) \\
= 2^{2n}\times n^{(\log n)/2}$

The author uses induction to prove, but for me it's wrong. Could anyone make a judgement?

[edit 07/19]: I realized that asymptotically $n^{\log n}<2^n$ but the lhs is greater than a polynomial in $n$ anyway no?

[edit 07/20]:as the comments and answers stated, we can basically conclude that there exists some issue in that paper and the correct complexity is $O(4^nn^{log n})$. However this can be also viewed as "$O((4\times\epsilon)^n)$ for any $\epsilon>1$", so let's say the complexity is infinitely close to $4^n$ from above.

P.S. for any constant positive $c>1$, $n^{\log n}=c^{(\log_c n)\log n}\leq \max(c^{\log^2 n},c^{\log_c^2 n})<c^n$ (asymptotically)


texts: History and status of the graph matching problem

texts:
Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from it when using search engines.

Given two graphs $G=(V,E)$ and $G'=(V',E')$ such that $|V| = |V'|$, the task is to find a bijection $\pi : V \rightarrow V'$ such that this bijection establishes as much correspondences between edges of $G$ and $G'$ as possible.

In other words, if $M$ and $M'$ are the adjascency matrices, then we want to maximize

$\sum_{v,w \in V} M_{v,w} \cdot M'_{\pi(v),\pi(w)}$

This problem clearly contains graph isomorphism as a special case, and can be reduced to bipartite matching under a (non-polynomial!) reduction.

What kind of algorithms do exist, and what is known about its complexity?


texts: A mathematical problem in software watermarking

texts:
I am wondering if there are any existing works/ideas that are related to the following problem. A solution of this problem can be probably useful in software watermarking.

Given,

Two sets $\mathcal{W}$ and $\mathcal{H}$ (whose sizes are typically between 10 and 50)
A bijection $f: \mathcal{W} \rightarrow \mathcal{H}$

The problem is to construct a function $\mathcal{F}$. The domain of $\mathcal{F}$ is the set of sequences of elements of $\mathcal{W}$, and the codomain is the set of sequences of elements of $\mathcal{H}$. The desired properties of $\mathcal{F}$ are given below.

Notation:
$S_i$ represent the $i^{th}$ element of sequence $S$.

Definition:
$\mathcal{F}$ behaves normally $\ $for a sequence $WS$ of length $N$ iff $\mathcal{F}(WS) = HS$, length of $HS$ is $N$, and $HS_i = f(WS_i)$ for $1 \leq i \leq N$.

Construct $\mathcal{F}$ and compute a sequence $P$ (of elements of $W$) of length $N$ such that:

1) $\mathcal{F}$ behaves normally for almost all sequences of elements of $W$

2) $\mathcal{F}$ and $P$ satisfy following constraints

$\ $  a) $\mathcal{F}(P) = Q$, length of $Q$ is $N$

$\ $  b) $Q_i = f(P_i)$ for $1 \leq i < N$  (i.e., $\mathcal{F}$ behaves normally for the $P$’s prefix of length $N-1$)

$\ $  c) $Q_N \neq f(P_N)$

$\ $  d) it is computationally hard to discover the sequence $P$ with the knowledge of $\mathcal{F}$'s implementation and the bijection $f$.


texts: Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?


texts: I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision problem? And is there a paper which shows that Shor's algorithm implies this decision problem is in BQP?


texts: Testing for positivity instead of equality

texts:
Alice and Bob have n-bit strings, and want to figure out if they're equal while doing little communication. The standard randomized solution is to treat the n-bit strings as polynomials of degree $n$ and then evaluate the polynomials over a few randomly chosen elements from a field of size larger than $n$. This takes $O(\log |F|)$ communication.

Suppose instead that we fix a lexicographic ordering over the strings and want instead to determine which string is "larger", which is equivalent to finding the leftmost bit where the strings differ.

  Is there a similar randomized protocol for doing this, or a known
  lower bound ? This seems to relate to testing positivity of
  polynomials.

p.s While lexicographic order seems like the most obvious, I'm fine with other orderings: for the purpose I'm interested in, all we need is some order.


texts: How would I go about learning the underlying theory of the Coq proof assistant?

texts: I'm going over the course notes at CIS 500: Software Foundations and the exercises are a lot of fun. I'm only at the third exercise set but I would like to know more about what's happening when I use tactics to prove things like forall (n m : nat), n + n = m + m -> n = m.


texts: Min cut problem on unbalanced partitions for planar graphs with unit capacity edges

texts:
The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$ and $|B| = |V(G)|-k$?

I know that when $k=|V(G)|/2$, this is known as the minimum bisection problem, NP-hard for general graphs and unknown for planar graphs (https://www.sciencedirect.com/science/article/pii/S1571065315001134 and https://mediatum.ub.tum.de/doc/1338548/1338548.pdf)

For arbitrary fixed $k$, I'm not sure what the standard terminology for this question is, though Peng Zhang refers to it as the min E$k$-size cut problem: https://link.springer.com/article/10.1007/s11704-014-3289-1. In this paper, an $O(\log n)$ approximation algorithm is given for the min $Ek$-size cut problem, but this is not specific to planar graphs or graphs with unit capacity weight. Are there better approximation algorithms for graphs that are planar and have unit capacity weights?


texts:
In a paper by Raphael Pass, he writes (page 162):

  ... most natural problems that we believe are hard on average for polynomial
  time are also believed hard for quasi-polynomial time.

In another post by Turkistany, he mentioned that the log-CLIQUE problem is solvable in quasi-polynomial time.

What are some other natural problems which we believe are hard on average for polynomial time, but can be decided/solved in quasi-polynomial time?


texts: Coset state of $3$-node graph isomorphism problem

texts:
The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should start with constructing the state $|f\rangle$.

$$
|f\rangle = \frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle |f\left(g\right)\rangle
$$

I am trying to figure out the efficient way to construct $\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle$. For a $3$-node graph isomorphsim problem, $|G| = 720$. It means, if we map each permutation of $G$ to an unique basis state, we need $720$ basis states. It entails that $|g\rangle$ has to be at least a $10$ qubit register.

My questions are:

Is there a more efficient way to construct the state with lesser number of qubits?
If we need at least 10 qubits, which $720$ of the $2^{10}$  states should I choose?


texts: Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994

texts:
This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636

So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits mapping $\{0,1\}^n \rightarrow \{0,1\}$ and of size $s \geq n$ is $2^{O(n^2s)}$. I think I do understand the proof of this theorem but its not clear to me as to how the following two corollaries seem to be immediately following from this,

That for all $\epsilon >> \sqrt{\frac{n}{2^n}}$ with probability at least $1-\epsilon$ a uniformly at random chosen $n-$bit Boolean function is such that it cannot be matched on more than $(\frac{1}{2} + \epsilon)$ fraction of the inputs by a depth $2$ linear threshold circuit of size $s \leq o(\frac{\epsilon^2 2^n}{n^2})$
That for all $\epsilon >> \sqrt{\frac{\log n}{n}}$ there exists a constant $c$ small enough such that with probability at least $1-\frac{\epsilon}{3}$ a uniformly at random chosen $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function is such that on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs it is not matched by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^2 n }{\log ^2 n}$

Can someone kindly put in an explanatory proof for the above two statements?

Apparently the second of the above statements is either equivalent to or implies that if the $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function picked is such that it indeed cannot be matched on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^3 n^{\frac {3}{2}} }{\log ^3 n}$ then with probability at least $1-\frac {\epsilon}{3}$ this function's truth table is the same as an $\frac{n}{2}$-bit string picked uniformly at random. I don't understand why!


texts:
We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$.
Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$).
We want to compute the following expression:

$$ \sum_{A\in {S \choose k}} \prod_{x \in A} x$$

Is there an algorithm for this problem that works much better than the trivial one which goes over all subsets and computing and summing up all products?


texts: One-way randomized communication complexity of approximate Hamming distance

texts:
If Alice and Bob both have $n$ bit strings, consider a one-way randomized communication problem where Bob has to output with some good probability a number which is within a $(1+\epsilon)$ factor of the Hamming distance between their strings.

What is the one-way randomized communication complexity of this problem?

I have found a lot of literature on seemingly related problems (e.g. promise problems, threshold versions of Hamming distance) but I can't find a reference for this precise formulation.


texts:
Is there a linear-time reduction from the sorting problem to the max-flow problem?

If so, what would such a reduction look like?


texts: Complexity of comparing extended integer power towers

texts:
Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by power towers? Example:

$$(2^3)^{(4^{5^3})^5}$$

It seems to me like the accepted answer on that page requires a bound on the sizes of the numbers lower in the tower in order to work.


texts: Prime factorisation of decidable problems

texts:
Disclaimer: I am not a theoretical computer scientist.

The set of decidable problems $\mathbb{D}$ is countable so $\lvert \mathbb{D} \rvert = \lvert \mathbb{N} \rvert$ and this led me to the following idea.

Given two decision problems $p,q$ in $\mathbb{D}$ and $\mathcal{M}_p,\mathcal{M}_q$ the minimal-length Turing Machines deciding $p$ and $q$ we may say that $p$ and $q$ are relatively prime if:

\begin{equation}
K(\mathcal{M}_p|\mathcal{M}_q) = K(\mathcal{M}_p) \tag{1}
\end{equation}

and

\begin{equation}
K(\mathcal{M}_q|\mathcal{M}_p) = K(\mathcal{M}_q) \tag{2}
\end{equation}

where $K(\cdot)$ denotes Kolmogorov Complexity.

I think we should then be able to define $\mathbb{B} \subset \mathbb{D}$ such that $\lvert \mathbb{B} \rvert = \lvert \mathbb{D} \rvert$ and:

\begin{equation}
\forall b \in \mathbb{B} \forall d \in \mathbb{D} \setminus \{b\}, K(\mathcal{M}_b|\mathcal{M}_d)=K(\mathcal{M}_b)  \tag{3}
\end{equation}

where $\mathbb{B}$ is analogous to the set of primes in $\mathbb{N}$. Has this idea been explored?


texts: What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem)

texts:
This is a cross-post from MathOverflow.

The problem of testing whether a simplicial face lattice (informally, a poset of faces) is polytopal is sometimes called the Steinitz Problem.

Sturmfels and Bokowski advanced a set of methods in the late 80s to test whether the face lattice of a simplicial sphere was also realizable as a polytope.

The method uses oriented matroids. The problem is NP-hard, so their algorithm requires exponential time in the worst case, but they reported that the algorithm often converged quickly. Lars Schewe has recently shown that the same method can be adapted to make use of optimized SAT solvers, although the underlying technique seems to be the same.

I'm curious if newer approaches have been developed in the intervening decades since Sturmfels and Bokowski published their result. Is their method still the state of the art?   Further, are there any software implementations available that solve this problem -- even using the older approach?

In the MathOverflow discussion, Joe O'Rourke pointed out that Polymake has a feature that seems to compute geometric realizations of simplicial complexes [GEOMETRIC_REALIZATION], but this doesn't guarantee polytopality as far as I know.


texts:
Quoting from Wang and Botea 2011:

An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each unit $u \in U$ has an associated start-target pair $(s_u, t_u)$. All units have distinct starting and target positions.
The objective is to navigate all units from their start positions to the targets while avoiding all fixed and mobile obstacles.

The MAPP algorithm presented in this paper is complete for most instances of this (Multi-Agent Path Planning) problem.
After implementing MAPP myself (even using the suggested "replanning with counting" technique), it seemed that many of the solutions obtained were far from optimal in path length, having many units that went near their goals than back near their starts multiple times.
Specifically, I'm interested in the subset of this problem that has groups of units very near each other and groups of goals very near each other, as you might see in an RTS, for example. Are there better algorithms for these kinds of instances, or better repositioning strategies for MAPP?


texts: Given a network flow, are there bounds on the change in weight on nodes?

texts:
Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight around among nodes. This is expressed through a flow $f$ defined on the edges: $f(i,j)$ tells me how much weight I transfer from $i$ to $j$.

The flow cannot create new weight.
The flow must be integer.
$f(i,j)$ is allowed to be larger than $w_i$, but after the entire flow has been applied all the $w_i$ must be non-negative again.

Let $\Delta_i$ be the total change in the weight on node $i$, with the sign convention such that $\Delta_i$ is positive if more tasks leave node $i$ than arrive at $i$. An upper bound on $\Delta_i$ is $w_i$, by virtue of the third condition on the flow. My question now is: Is there also a lower bound?

A naive lower bound for each $\Delta_i$ would be given by the sum of the $\Delta_j$ for all neighbors of $i$, but I wonder if some network- and graph-theory can find better bounds?

If a good lower bound on the $\Delta_i$ is not possible, maybe there is a good \emph{upper} bound on the quantity
$$\sum_{i \in V} \Delta_i^2$$?


texts: How to go about finding the most "complex" function?

texts:
Intro

Hi, I'm a hobbyist, with no formal education, tinkering with SAT solving and boolean algebra minimization. So expect bad terminology. I hope you will forgive me I'm asking a wrong question in a wrong place. I'll give it a shot.

Question

Essentially I'm trying to find the most "complex"/"chaotic"/"highest entropy" truth tables of some sizes (>32 bits / >5 vars). I'm asking if it would be possible to find such functions without enumeration and how to go about getting there?

Complex in what context? Complexity would mean the size of some representation other than the truth table itself. So let's say the complexity of a function is the size of the function's optimal CNF/DNF or NNF representation with "temp vars"(to avoid the exponential growth in certain cases like XORs).

Number of clauses in case of CNF/DNF, number of temp vars in case of NNF. Don't know if those can be called CNF and NNF anymore but I hope you get what I mean.

I'm more used to a NNF-like representation without ORs. Where (a+b).(a'+b') would be described in the following way:

0 = a'.b'
1 = a.b
2 = 0'.1'

Application / Why I'm asking?

I'm looking for a way to find and analyse cases (preferably similar) where the optimal representation in the And-inverter graph structure would start to grow exponentially as the size of the truth table increases and it would get way bigger than the truth table itself. Just like it happens with XORs in CNF/DNF structure.


texts: Is this dense version of Kruskal's algorithm well-known?

texts:
About a year ago, a friend and I thought of a way to implement Kruskal's algorithm for dense graphs in better than the usual $O(m \log m)$ bound (without assuming pre-sorted edges). Specifically, we achieve $\Theta(n^2)$ in all cases, similar to Prim's when implemented using adjacency matrices.

I've posted a bit about the algorithm in my blog, including C++ code and benchmarks, but here's the general idea:

Maintain one representative node for each connected component. Initially, all nodes represent themselves.
Maintain a vector dist[i] such that, for every component i, has the lightest component-crossing edge incident to i.
When finding the lightest edge that crosses partitions, simply find i that minimizes the weight of dist[i], in linear time.
When joining two components $c_i$ and $c_j$, modify the adjacency matrix $A$, such that now $A_{i, k} = \min \{A_{i, k}, A_{j, k}\}$ for all components $k$, and mark $i$ as no longer representative of its connected component (only $j$ will now remain).

The contracting of the lightest edge and the finding of said edge can thus both be done in linear time. We do this $n - 1$ times to find the MST. A little bookkeeping is needed to actually find which edge we want to add to the MST, but does not increase the complexity. Thus the runtime is $\Theta(n^2)$. The implementation is just a couple of for loops.

Is this version of Kruskal well-known in the literature?


texts: Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size

texts:
I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.

It is known that the determinant of an $n\times n$ matrix can be computed in $\tilde{O}(M(n))$ time, where $M(n)$ is the minimum time required to multiply any two $n\times n$ matrices.  It is also known that the best circuit complexity of determinants is polynomial at depth $O(\log^{2}(n))$ and exponential at depth 3.  But the circuit complexity of matrix multiplication, for any constant depth, is only polynomial.

Why is there a difference in circuit complexity for determinants and matrix multiplication while it is known that from an algorithm perspective determinant calculation is similar to matrix multiplication? Specifically, why do the circuit complexities have an exponential gap at depth-$3$?

Probably, the explanation is simple but I do not see it. Is there an explanation with 'rigor'?

Also look in: Smallest known formula for the determinant


texts: General hardness results for convex problems

texts:
What are the hardness results that we know of for generally convex problems? In particular, I know of the result that every convex problem is in $P$ when we have an oracle for generating a separating functional and we can lose solvability in $P$ if we lack strong duality (but I'm not sure what the particular conditions are necessary for this to be the case).

Additionally, this plays into the next question: are there any hardness results for approximations of general convex problems? What are the canonical papers for reference? I think it would be great to have a collection of these results.


texts: How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?

texts:
Let $G=(V,E)$ be an undirected, random $r$-regular graph.

Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$.

I'm looking for the distribution of the number of neighbors of $t$ which are closest to $s$, that is, let
$$C = \text{argmin}_{u\in N(t)}d(s,u)$$

($d:V\times V\to \mathbb N$ is the unweighted distance function which counts the number of hops between the vertices, i.e., the length of the shortest path).

What is the distribution of $|C|$? (fixing $r$ and $n=|V|$)

I'm also interested in a few simpler questions:

What is $\mathbb E (|C|)$?
What is $\Pr(|C| > 1)$?
Can we find any of these quantities for $r=4$, which is especially interesting for me?

The motivation for the question comes from peer-to-peer routing networks (of a specific type, which can approximately be represented as regular graphs).
Assume that the source node $s$ broadcasts a message to all vertices such that every vertex propagates the message upon arrival. I'm interested in the number of nodes we need to query before we find a neighbor that received the message already.


texts: How much does treewidth changes after removal of a path?

texts:
Let $G$ be a graph such that $\mathrm{tw}(G)=t$. Let $t' = \min\limits_{u,v \in V(G)} \max\limits_{P \text{ is a path from } u \text{ to } v} \mathrm{tw}(G - P)$. Then how small $t'$ can be?

My observation is that $t' = \Omega(t^{1/10})$ because of grid minor theorem (https://arxiv.org/abs/1901.07944). Indeed, let $H$ be a grid minor of $G$ of size at least $t^{1/10}$. Then pick any shortest path from $u'$ to $v'$ in $H$ where $u'$ is the closest to $u$ vertex that was not removed during the construction of $H$, and $v'$ is the closest one to $v$. Then we can pick a shortest path from $u$ to $u'$ then the shortest path from $u'$ to $v'$ in $H$ and translate it to a path in $G$ reversing edge contractions and then take the shortest path from $v'$ to $v$. One may notice that after the removal of such path the resulting graph still has a grid minor of size $\Omega(t^{1/10})$ and thus treewidth of size $\Omega(t^{1/10})$.

Although the strategy of removing the shortest path between $u$ and $v$ doesn't always work. The counterexample is the following graph:

Black edges represent paths of $n^3$ edges, red edges represent single edge. That way red path is the shortest path between its ends and its removal turns the grid-like graph into a tree.

So my question is, is it possible to prove better lower bounds on $t'$ than $\Omega(t^{1/10})$?


texts: (Integer) Linear Program formulation of planarity?

texts:
Q: Is there an efficient (I)LP formulation of planarity?
More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on $n$ vertices, in order to optimize some linear objective function over these graphs, e.g. fractional chromatic number. (Actually, over graphs that are the union of two planar graphs, but this should be similar.)
My first approach was to use variables of the $x$ coordinate and the $y$ coordinate of each vertex,
and then use a geometric approach to determine whether two edges are crossing.
However, this requires roughly $O(n^4)$ constraints, which might become intractable very quickly.
My second approach was to use the fact that there are at most $3n-6$ edges in a planar graph.
We can then assign to each edge two variables corresponding to the vertices that are their endpoints.
Then, checking for pairwise intersection only requires $O(n^2)$ constraints.
The two approaches above are integer LP, however planarity can be checked in polynomial time, therefore
one could hope that there is a linear programming formulation, which might lead to a faster resolution.
Wagner's or Kuratowski's theorem may yield efficient formulations, but I wasn't able to come up with one.
Finally, I could not find articles that use a linear program formulation of planarity -- did I miss any?


texts: Complexity of testing for a value versus computing a function

texts:
In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input.  For example:

Evaluating the permanent of a nonnegative integer matrix is #P-hard, yet telling whether such a permanent is zero or nonzero is in P (bipartite matching)
There are n real numbers $a_1,...,a_n$, such that the polynomial $\prod_{i=1}^{n}(x - a_i)$ has the following properties (indeed most sets of $n$ real numbers will have these properties). For given input $x$, testing whether or not this polynomial is zero takes $\Theta(\log n)$ multiplications and comparisons (by Ben-Or's result, since the zero set has $n$ components), but evaluating the above polynomial takes at least $\Omega(\sqrt{n})$ steps, by Paterson-Stockmeyer.
Sorting requires $\Omega(n \log n)$ steps on a comparison tree (also $\Omega(n \log n)$ steps on a real algebraic decision tree, again by Ben-Or's result), but testing if a list is sorted only uses $n-1$ comparisons.

  Are there general conditions on a polynomial that are sufficient to imply that the (algebraic) complexity of testing whether or not the polynomial is zero is equivalent to the complexity of evaluating the polynomial?

I'm looking for conditions that do not depend on knowing the complexity of the problems beforehand.

(Clarification 10/27/2010) To be clear, the polynomial is not part of the input.  What that means is that, given a fixed family of functions $\{ f_n \}$ (one for each input size (either bitlength or number of inputs)), I want to compare the complexity of the language/decision problem $\{ X : f_n(X) = 0 \text{ where } n \text{ is the "size" of } X \}$ with the complexity of evaluating the functions $\{f_n\}$.

Clarification: I am asking about the asymptotic complexity of evaluating/testing families of polynomials.  For example, over a fixed field (or ring, such as $\mathbb{Z}$) "the permanent" is not a single polynomial, but an infinite family $\{perm_{n} : n \geq 0 \}$ where $perm_{n}$ is the permanent of an $n \times n$ matrix over that field (or ring).


texts:
Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known asymptotically if $G$ is non-bipartite but since it depends on the chromatic number of $G$, it is (at least) NP-hard to determine it. For some bipartite graphs the asymptotic/magnitude of $ex(n,G)$ is also known, but not for all. It is a conjecture that $ex(n,G)=\Theta(n^\alpha)$ for every $G$.

  Algorithmically, how hard is it to determine $ex(n,G)$ for an input $G$?

For example, is it decidable whether $ex(n,G)=O(n^\alpha)$?


texts: How hard is it to learn a linear modular function?

texts:
Let $k$ be a fixed number.
Consider the following task $Q$:

  We are given a sequence of numbers $(x_0,x_1,\cdots,x_k)$. We know they satisfy $x_{k+1}=f(x_k)$, and $f(x)=(ax+b \mod p) \mod m$ where $a,b,m,p \in [2^n]$ are some unknown values.
  The task is to find $f$.

I have a couple of questions about this problem:

How hard is this problem?
If we choose $a,b,p,m$ randomly but "wisely" will $f$ be a pseudorandom number generator secure against TC0 or AC0 circuits?
What is the smallest value of $k$ where $Q$ can be solved?
What is the fastest known algorithm for $Q$?


texts: Is getting post-doc difficult in theoretical computer science with few published papers?

texts:
I am a Ph.D student ( expected to graduate in few months ) works in computational mathematics. In my PhD, I have published just couple of research papers. I am willing to go for a post-doc( US, Europe, Australia ), but not sure that I will get one or not as I have not published anything in the top conference, but still want to take a chance. I have heard from my seniors that getting a post-doc is very difficulty especially in theoretical computer science as there are very few jobs. I am also hesitant to write emails to the top researcher in my field. I can get a faculty job in my local area but that will be a teaching job ( mostly ) and right now I am not that much interested in teaching. I know that if I would have research papers in top conferences then my chances of getting a post-doc would have high.

Question :  Is getting pos-doc difficult in theoretical computer science with few published papers?


texts: Mathematics degree for Theoretical Computer Science?

texts:
I want to go to grad school in theoretical computer science.
I don't like programming.
I am in France.

Should I pursue a bachelors in math or in computer science?


texts: Complexity of Approximating Vandermonde Determinant

texts:
Given an $n\times n$ Vandermonde integer matrix with structured integers (such as arithmetic or geometric progression).

Is complexity of approximately computing Vandermonde determinant upto multiplicative error $\epsilon_m$ and additive error $\epsilon_a$ studied in literature?


texts: Does the MIP* = RE proof work for limited provers?

texts:
MIP* = RE shows that two arbitrarily strong entangled provers can convince a verifier of instances of the halting problem.  Now assume that we have two entangled provers that are only capable of solving problems in some language $L$ (say a language complete for NEEXP, NEEEXP, etc.).

Question: What constraints on $L$ allow provers to convince a verifier of solutions to $L$?

The nonquantum analogy is that not only is IP = PSPACE, but IP' = PSPACE where IP' provers are only able to solve PSPACE level problems.  In particular, L = PSPACE works for the MIP* question.  Moreover, provers that are limited to any level of the polynomial hierarchy $\Sigma_k \textrm{P}$ can establish $\Sigma_k \textrm{P} \subset \textrm{PSPACE}$. (Unfortunately, looks like this doesn't work lower in the polynomial hierarchy.)

(I'm blurring over some definitional subtlety here about function problems vs. decision problems; in the above one probably needs the provers to be able to solve $\textrm{FP}^L$ rather than just L.)


texts: Minimum cost flow with Demand and Edge Capacity scaling

texts:
Consider a the splittable minimum cost flow problem on network $G(V,E,W,C)$ and a set of commodities $(s_i,t_i)$ with demand $d_i$ for $i=1,2,\dots,k$. Here, $w_e$ and $c_e$ is the weight of edge $e$ and the capacity of edge $e$, respectively. My question is what happens if we scale the demands and the capacities linearly but decrease the weights inversely.
Consider the same problem on $G(V,E,W/\lambda, \lambda C)$ for the commodities $(s_i,t_i)$ with demand $\lambda d_i$ for $i=1,2,\dots,k$, where $\lambda$ is a constant. For each $\lambda$ we get a solution $OPT(\lambda)$. I am interested in the minimization of $OPT(\lambda)$ over $\lambda> 0$.

If someone can point me to the existing literature it will be helpful.


texts:
Given a graph $G$, it is known independence number $\alpha(G)$ and Lovasz theta $\vartheta(G)$ satisfy the inequality, $\alpha(G^{\boxtimes n}) \leq \vartheta(G)^{n}$.

If $\alpha(G^{\boxtimes n}) < \vartheta(G)^{n}$, under plausible complexity theory conjectures, is it possible to have any other polynomial time computable function $\psi(G)$ that works for all graphs $G$ (or special family of graphs) and that produces numbers satisfying the inequality $\alpha(G^{\boxtimes n}) \leq \psi(G)^{n} \leq \psi(G^{\boxtimes n}) \leq \vartheta(G)^{n}$?


texts: what is known about efficient set intersections

texts:
Say you have a number of sets of integers ($S_1, S_2 ... S_n$), and you want to calculate intersections of some of them ($\cap S_1, S_3, S_7$ might be a query, but you want to support many such queries, or maybe even all possible queries)

There is an obvious way to do this in linear time. Are there data-structures that allow for sub-linear time ? (of course, that is not be possible in general: the answer itself might have linear size. But an algorithm might have some other useful properties, like being linear on the answer size, or running on sub-linear time and giving just part of the intersection)

In general, what is the state of the problem? What approaches are known, and what is known to be hard ?


texts:
If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations.

My course also says that if you search for a node and the node is not in the semi-splay tree, you still have to perform semi-play on the search path in the tree.
But isn't that basically pushing nodes to the root that aren't actually have been searched for?

So my question would be : why do you still have to perform semi-splay even if the node you search for is not in the tree?


texts: Why is the state of a FSM traditionally denoted $q$?

texts:
While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is typically denoted $q$ (and the state space $Q$). I first asked on EE.sx, but then while researching a bit this topic, I found that even Turing's original 1936 paper uses $q_1..q_n$ to denote the states of the Turing machine.

So I wonder: When does this convention go back to, and why would a "state" be denoted $q$ ?


texts:
could any one please let me know what is the relation between "lambda" and anonymous functions in programming?

in other words why we say lambda function to an anonymous function?

I am here trying to understand the reason for use of the term


texts: Assigning edge weights under shortest path constraints

texts:
We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{a,b}: R\times R \rightarrow \mathbb{R^+}$ where $\mathbb{R}^+$ is all positive ($> 0$) reals ($c_{a,b} = c_{b,a}$ for all $a,b$ and $c_{a,a} = 0$ for all $a$ ). Our edge weight assignment is constrained by the requirement that for all vertex pairs $(a,b)\in R\times R$, all paths from $a$ to $b$ need to have at least weight $c_{a,b}$  where the weight of the path is the sum of all edge weights on that path.

Now assume that there exists an assignment that satisfies all of the constraints and such that for all vertex pairs $(a,b)\in R \times R $ there exists at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$.

Now consider the assignment of edge weights (*) that satisfies the constraints and minimizes the total sum of edge weights. Is it true that for all vertex pairs $(a,b)\in R \times R$ there will exist at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$ ?


texts:
Is a local optimum value of a SDP always the global one?

If not, what are the conditions for that?


texts: Matching regular expressions using regular expressions

texts:
Is it possible to create a regular expression that matches regular expressions in any given notation?

Or, in other words, does there exist a unambiguous and full notation for regular expressions that can be parsed with regular expressions?


texts: Communicating a string of zeros and ones quantumly

texts:
Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate
in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and
transmits a qubit to the other side, until at the end Bob measures his state and tries to infer
x. The protocol is successful if for every $x \in \{0,1\}^n$ Bob succeeds with probability 1. Let
$n_A / n_B$ be the number of messages sent by Alice / Bob respectively.

Now I want to show that for any successful protocol we must have $n_A \geq  \lceil n/2 \rceil $, and $n_A+n_B \geq n$, and I need to show that the same argument above follows also for p-successful protocols, i.e if there's a p-successful protocol then the ineqaulities above should also follow for this protocol; a p-successful protocol is one in which Bob succeeds with probability p.

Any hints or prefereably bibliography where this or similar problem is disscused?

Thanks.


texts: Positivstellensatz and sum of squares method

texts:
This question comes from many online resources that introduce Sum-of-Squares method, such as the survey of Barak and Steurer (http://arxiv.org/abs/1404.5236). Let me focus on Theorem 2.1 of this survey and the paragraph just before that.

Starting point is "Positivstellensatz" which says that any non-negative polynomial over reals can be written as a sum of squares of rational functions. Corollary of this is the following statement, which is central to sum of squares proofs:

Given multivariate polynomials $P_1,P_2\ldots P_m$ over reals, the system of equations $\{P_1=0,P_2=0\ldots P_m=0\}$ has no solution over reals if and only if there exist polynomials $Q_1,Q_2\ldots Q_m$ and a sum of squares of polynomials $S$ such that $-1=S+\sum_i P_iQ_i$.

My question is how does this Corollary follow from "Positivstellensatz". This important implication constantly appears in various lecture notes/videos, but as far as I have noticed, the proof is always skipped.


texts: Relation between variance and mutual information

texts:
Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$

This bound may be useful to my research if correct. What I have tried to do in order to prove it is the following:
1. Define the probability space $\mu$ over pairs of possible values of $X$ and $Y$: $$\Pr_\mu [(\alpha,\beta)] = \Pr[X = \alpha \text{ and } Y = \beta].$$
2. Similarly, let $\eta$ be the following probability space:
$$\Pr_\eta[(\alpha,\beta)] = \Pr[X=\alpha] \Pr[Y = \beta].$$
3. It can be seen that $D_{KL} (\mu ||\eta) = \text{I}[X,Y]$ where $D_{KL} (\mu ||\eta)$ is the Kullback–Leibler divergence (https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence).
4. Now, using Pinsker's inequality (https://en.wikipedia.org/wiki/Pinsker%27s_inequality) we get that: $$\delta(\mu,\eta) \leq \sqrt{\frac{1}{2} D_{KL}(\mu || \eta)} = \sqrt{\frac{1}{2}\text{I}[X,Y]}. $$
where $\delta()$ is the total variation distance .
5. The last step I tried is to find any connection between $\delta(\mu,\eta)$ and $|\text{Cov}[X,Y]|$ - ideally $|\text{Cov}[X,Y]| \leq \delta(\mu, \eta)$ - the problem is that seems like there is no such connection, I can find distribution where $|\text{Cov}[X,Y]| > \delta(\mu, \eta)$ and other distribution where the opposite holds.
I strongly believe that if this claim is correct, the proof goes through Pinsker's inequality, since it is very similar. Any advice will be appreciated.
EDIT:
As I was told in the comments, it holds that if $|X|, |Y| \leq 1$, $|\text{Cov}[X,Y]| \leq \delta (\mu, \eta)$ - the proof is in the comments. I was wrong when I thought I had a counter example. I also believe that the accepted answer below is correct.


texts: VC dimension of intersection of half-spaces

texts:
Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$

for $i=1,...,n$, where $x \in \mathbb{R}^d$.

Then define the classifier

$$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$

which represents the intersection of $n$ linear functions and hence a convex polytope in $\mathbb{R}^d$ with $n$ facets.

What is the VC dimension of the family of all $g$ of this form?

I found that an upper bound is $2 (d+1) n \text{log}_2( (d+1)n ).$


texts: Constructing a bad sequence for counter algorithm

texts:
Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'.

The sequence is then feed to the following probabilistic algorithm:

Initialization: $c = \begin{cases}1&\text{if } s_1=a\\0&otherwise\end{cases}$, $id = s_1$
For $i=2,3,\ldots N$:

If ($id = a$ and $s_i = a$)

c += 1

Else if ($id\neq s_i$)

With probability $1/(c+1)$, replace $id$ with $s_i$ and increment $c$, or do nothing otherwise

Notice that the value of $c$ after processing the $N$ elements is a random variable. Denote its final value by $C$.

  How to construct a sequence which minimizes $\mathbb E(C)$?

The motivation for this question comes from a streaming algorithm for heavy hitters, where such sequence could be the worst-case scenario. $b$ here represents all "tail" items (assumed to appear no more than once) which interfere with the heavy hitter $a$ we are trying to count.

For example, consider $N=5, n=2$ and the sequence is $a,b,b,a,b$.

$c$ starts with $1$.
With probability $3/4$, the $id$ will be replaced by $b$ in $i=2,3$, so after seeing $a,b,b$ we have:

$id = a, c = 1$ with probability $1/4$
$id = b, c = 2$ with probability $3/4$

Now $a$ comes. If $id=a$, $c$ is incremented, otherwise, $id$ is replaced with probability $1/3$, so after seeing $a,b,b,a$ we get:

$id = a, c = 2$ with probability $1/4$
$id = a, c = 3$ with probability $1/4$
$id = b, c = 2$ with probability $1/2$

When the final $b$ arrives, it may increase the counters, depending on $id$, so overall we get:

$id = a, c = 2$ with probability $1/6$
$id = b, c = 3$ with probability $1/12$
$id = a, c = 3$ with probability $3/16$
$id = b, c = 4$ with probability $1/16$
$id = b, c = 2$ with probability $1/2$

So overall we get $\mathbb E(C)\approx 2.4$.

Which is worse than the sequence $b,b,b,a,a$, in which $C=2$ at the end with probability $1$.

  Is late arrival ($s=b^{N-n}a^n$) always the best sequence for minimizing $\mathbb E(C)$?

(In fact, we only "identify" $a$ if $id=a$ at the end, and we can show that in such cases, $\mathbb E(C) \le n$, so we are not concerned with overestimation here).


texts: Does the Law of Excluded Middle imply the Axiom K in Martin-Löf's Intensional Type Theory?

texts:
So I've been wondering if the Law of Excluded Middle (LEM) implies the so-called Axiom K in Martin-Löf's Intensional Type Theory. The Axiom K states that
$$\Pi_{A : Type} \Pi_{x : A} \Pi_{p : \text{Id}(x,x)}, \text{Id}(p,\text{refl}_x)$$
In fact, I've been trying to prove the more general statement that
$$\Pi_{A : Type} \Pi_{x, y : A} \Pi_{p,q : \text{Id}(x,y)}, \text{Id}(p,q)$$
but after reducing $q$ to $\text{refl}_x$ by equality-induction I am stuck into the first problem. I also tried to proceed by contradiction, but it doesn't seem to work..

Is this provable at all?


texts: Decomposing complete graphs into clique-free graphs of certain size

texts:
Modified in accordance with Tsuyoshi's comment which seems to generalize.

Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no cliques of size $k$ for some $k \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?

How about the case when $K_{n}$ is replaced by a bipartite $K_{m,n}$ where one seeks a partition such that there is no $K_{k,l}$ for some $k,l \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?


texts: What is the name of this type of directed graph problem?

texts:
Take a directed graph $G$ where the edges are decorated with a a natural  number. We want the set of all paths $P$ between two vertices $v_1$ and $v_2$ such that each successive edge in the path is decorated with a natural number that is greater than the natural number decorating the previous edge.

An application for this would be bus or train schedules. If you're trying to determine the different routes between two cities based on transfers between stations. (You can't take a second train scheduled to leave for before the first one arrives.)

I've informally been calling this a "scheduled graph". But I don't know what the name for this in the literature is.

Any references to algorithms related to this are of interest as well.


texts: Book recommendations for CompSci related math

texts:
Searching for good textbooks on math related to Computer Science I bought two german books yet, but found them not to be easily understandable and not suitable for self-study . German textbooks are always very academic and extremely based on cryptic formula. They're maybe good, if you want a reference, supplementary to your courses in college, but as pointed out above, I'm trying the self-teaching approach a.t.m. .

I am very interested in theoretical Computer Science, but I lack the needed math knowledge to dig further into the subject . Could you recommend me a book, best in english, which would provide me with the basics of discrete math and every other mathematical subject related to CompSci and is easily understandable ? If the book covers more topics, maybe not so essential for CompSci, but is nevertheless good for self-study, I would like to hear about it too.


texts: What are good references to understanding the proof of the PCP theorem?

texts:
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$).

What are good papers/books to read for that?


texts: Counting the number of vertex covers: when is it hard?

texts:
Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.

I'd like to know if there is any result showing how the hardness of such problem varies with some parameter of $G$ (for example, $d = \frac{|E|}{|V|}$).

My sensation is that the problem should be easier both when $G$ is sparse and when $G$ is dense, while it should be hard when $G$ is "in the middle". Is this really the case?


texts: Intuitionistic fragments of classical logic

texts: For what conditions on P and Q, does P ⊢ Q in classical logic imply P ⊢ Q in intuitonistic logic (for higher-order logic, though of course results for more restricted logics are relevant too)?


texts: Making feature vector from Gabor filters for classification using Neural Networks

texts:
My aim is to classify types of cars (Sedans,SUV,Hatchbacks) and earlier I was using corner features for classification but it didn't work out very well so now I am trying Gabor features.

code from here

Now the features are extracted and suppose when I give an image as input then for 5 scales and 8 orientations I get 2 [1x40] matrices.

1. 40 columns of squared Energy.

2. 40 colums of mean Amplitude.

Problem is I want to use these two matrices for classification and I have about 230 images of 3 classes (SUV,sedan,hatchback).

I do not know how to create a [N x 230] matrix which can be taken as vInputs by the neural netowrk in matlab.(where N be the total features of one image).

My question:

How to create a one dimensional image vector from the 2 [1x40] matrices for one image.(should I append the mean Amplitude to square energy matrix to get a [1x80] matrix or something else?)
Should I be using these gabor features for my purpose of classification in first place? if not then what?

Thanks in advance


texts:
Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution.

Is there a randomised reduction from SAT, as there is for UNAMBIGUOUS-SAT, so that a polynomial-time algorithm for UNAMBIGUOUS-3DM would imply NP=RP?
For example, it would suffice for there to be a parsimonious reduction from SAT to 3DM, but I haven't found one in the literature.

If so, does it still work when restricting to planar instances of 3DM, i.e. where the bipartite graph associated with the 3DM instance is planar?


texts: NBE for MiniTT: Why is labelled sum eliminator both a normal form and a neutral value?

texts:
I am studying A simple type-theoretic language: MiniTT, which introduces a dependently typed language with The language contains data types, mutual recursive/inductive definitions and a universe of small types. The type checking proceeds by a mostly-straightforward bidirectional type-checking, coupled with normalization-by-evaluation to compute normal forms. It is here that I am confused. First, some quick syntax:
A sum type is created using Sum(c1 A1, ..., cn An), which contains objects
of the form ci E : Sum(c1 A1, ..., cn An), where E: Ai. For example, booleans are encoded as Sum(true 1, false 1) where 1 is the unit type. The type of naturals is encoded as rec Nat : U = Sum (zero | succ Nat). Sum types are eliminated using case-analysis, written as fun(c1 M1, ..., cn Mn), where each constructor is ci and the associated handler is Mi. For example, the elimination rule for booleans can be encoded as:
Bool : U = Sum (true | false)
elimBool : Π C:Bool → U. C false → C true → Π b:Bool. C b
= λ C.λ h0.λ h1.fun (true → h1 | false → h0)

and the elimination for naturals can be written as:
rec natrec: ΠC : Nat → U. C zero → (Πn:Nat . C n → C (succ n)) → Π n:Nat. C n
= λ C.λ a.λ g. fun (zero → a | succ n1 → g n1 (natrec C a g n1))

Now, I had always assumed that when implementing normalization-by-evaluation (NBE), the normal forms always consist of constructors, while the neutral values consist of eliminators, since an eliminator can get stuck if it does not know enough about its argument, while a constructor can always freely construct.
However, in the paper's implementation of NBE (given in the appendix), it appears that Fun (labelled sum eliminators) are one of the normal forms:
data Val =
Lam Clos
 ...
| Fun SClos -- function is a normal form?!
...
| Nt Neut
deriving Show

Furthermore, the inductive data type of stuck/neutral values has yet another encoding of a stuck fun, called as NtFun:
data Neut = Gen Int
...
| NtFun SClos Neut -- Fun as a stuck term

I have not seen an explanation of NBE which allows one to encode a particular syntactic category (in this case, the labelled sum eliminator fun), as both a normal form and a neutral/stuck term.

What is going on here? Why can a fun be both a normal form and a stuck/neutral term?
How should I think about what my normal forms and stuck terms should be? I had previously imagined that constructors would be normal forms, and eliminators are stuck terms. What's the rule of thumb that's being followed here?


texts: Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

texts:
Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a lot of resources in the "initial phase." These results may be stored in reasonably small look-up tables.

At the end of the "initial phase", we will be given a small unknown polynomial q(x) (of, say, degree 5 or less).

Is there a fast way to compute p(x) mod q(x) given that we are allowed to do some complicated calculations in the "initial phase"? One obvious way is to calculate p(x) mod q(x) for all possible values of q(x). Is there a better way to do this?


texts: Minimal encoding of a set (unordered collection of elements)?

texts:
Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$.

If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are needed.

I'd like to be able to have a "Set" data structure, which take advantage of the fact that the set is unordered to save memory.

It seems that theoretically (information bound), we could only use $k\log \frac{|\mathcal{U}|}{k}$ bits for encoding the set, but I was wondering if such result is known.

I considered looking into implementations of current set structures in popular programming languages, but assumed they'll be more optimized for runtime rather than memory, so my questions are:

Is there a known data structure that allows storing $k$ elements set using $k\log \frac{|\mathcal{U}|}{k} + O(1)$ bits (supporting adding and deleting items of course)?
What is the best runtime of such structure?

I'm well aware we could probably save some memory by hashing (if $k << \mathcal{U}$), but I'm looking for a deterministic structure.