Theoretical Computer Science Weekly Newsletter - Tuesday, March 31, 2015

Top new questions this week: s-t connectivity on infinite planar graphs with finite description I would like to know if the following problem is known and has been studied: Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, more ... reference-request planar-graphs undecidability   asked by Marzio De Biasi 7 votes Are there sparsifiers that approximate vertices rather than edges? Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph ... graph-algorithms spectral-graph-theory sparse-matrix   asked by Dana Moshkovitz 7 votes Learning read-once branching programs with membership queries Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes ... machine-learning pac-learning   asked by Holden Lee 6 votes Why it's impossible to declare an induction principle for Church numerals Imagine, we defined natural numbers in dependently typed lambda calculus as Church numerals. They might be defined in the following way: SimpleNat = (R : Set) → R → (R → R) → R zero : SimpleNat zero ... type-theory lambda-calculus church-numerals   asked by Konstantin Solomatov 5 votes answered by Andrej Bauer 11 votes Applications of small Kakeya sets over finite fields It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$. For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ... co.combinatorics coding-theory extractors finite-fields   asked by Anurag 4 votes Sample complexity of distinguishing two Gaussian distributions? Below is a description of the problem: Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$. And I can get $n$ samples ... reference-request machine-learning lg.learning sample-complexity   asked by Tianyang Li 4 votes answered by D.W. 5 votes Numerical precision in sum-of-squares method? I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the ... optimization sum-of-squares   asked by Jeremy Kun 3 votes answered by Joe Bebel 0 votes Greatest hits from previous weeks: Are research papers hard to read? This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO). I find research papers on computer science hard to understand. Of course the subjects are ... soft-question research-practice   asked by nimcap 61 votes answered by David Eppstein 126 votes To what extent is "advanced mathematics" needed/useful in A.I. research? I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in ... soft-question machine-learning ai.artificial-intel   asked by Max Muller 2 votes answered by Andrej Bauer 19 votes Can you answer this? How to simulate sequential registers from causal ones? Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For ... ds.algorithms reference-request dc.distributed-comp concurrency   asked by hengxin 2 votes

Subscribe to more Stack Exchange newsletters Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on stackexchange.com. Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all stackexchange.com emails. Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3