Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper ...

cc.complexity-theory ds.algorithms time-complexity  
asked by kodlu 6 votes
answered by Laakeri 9 votes

Lengths of "all-accepted" words in Context Free languages

If $L$ is a Context Free language, it can happen that for some $n$, all words of length $n$ are in $L$. If we consider the set $A_L$ of such lengths represented in unary, we may guess that such set is ...

asked by Marzio De Biasi 4 votes
answered by Hermann Gruber 3 votes

Neighborly properties in a bipartite graph

Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors. Question: Decide whether there exists a subset ...

graph-theory graph-algorithms np-hardness  
asked by Xin Yuan Li 4 votes
answered by Laakeri 1 vote

Complexity of finding the mean of the subset with smallest variance

Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer. Let's consider the following problem $\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n ...

cc.complexity-theory optimization  
asked by Andrea 3 votes

Tail bounds for sum of weighted Poisson random variables

Let $X_1,X_2,\ldots,X_n$ be $n$ independent Poisson random variables with $\mu(X_i) = \lambda_i$. I am interested in upper tail bounds for the random variable $Z = \sum_{i} a_i X_i$ where $a_i \in ...

bounds tail poisson  
asked by Chandra Chekuri 2 votes

Complexity of Set Difference

Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes ...

ds.algorithms time-complexity  
asked by tamalet 1 vote

Uniquely 4-colorable Maximal Planar Graph Conjecture?

My question is on Uniquely 4-colorable Maximal Planar Graph Conjecture mentioned in On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and ...

graph-theory planar-graphs graph-colouring  
asked by Cyriac Antony 1 vote

Greatest hits from previous weeks:

What Books Should Everyone Read?

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

reference-request soft-question big-list books  
asked by M.S. Dousti 241 votes
answered by Mohammad Al-Turkistany 95 votes

Applications of topology to computer science

I'd like to write a survey on the applications of Topology in Computer Science. I plan to cover the history of topological ideas in Computer Science and also highlight a few current developments. It ...

reference-request ho.history-overview topology survey  
asked by Ben 63 votes
answered by Mark Reitblatt 33 votes

Finding the shortest path in the presence of negative cycles

Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...

ds.algorithms graph-algorithms shortest-path  
asked by jleahy 14 votes
answered by BlueRaja - Danny Pflughoeft 24 votes

What is the best place to get BibTeX entries for ICLR and other machine learning papers?

dblp seems the best i found so far (as also mentioned in the comments and in What is the best place to get BibTeX entries for computer science articles ?) but even there some papers from NIPS ...

machine-learning research-practice paper-review bibliography  
asked by user2160809 6 votes
answered by Clement C. 8 votes

Research and open challenges in Programming Language Theory

In the spirit of some general discussions like this one, I'm opening this thread with the intention to gather opinions on what are the open challenges and hot topics in research on programming ...

pl.programming-languages open-problem research-practice  
asked by bellpeace 32 votes
answered by Martin Berger 23 votes

Relationship between Turing Machine and Lambda calculus?

Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?

computability lambda-calculus turing-machines  
asked by hawkeye 50 votes
answered by Charles Stewart 32 votes

Universal Approximation Theorem — Neural Networks

I posted this earlier on MSE, but it was suggested that here may be a better place to ask. Universal approximation theorem states that "the standard multilayer feed-forward network with a single ...

approximation-algorithms ne.neural-evol na.numerical-analysis  
asked by Matt Munson 24 votes
answered by matus 27 votes

Can you answer this question?

Non-rigid isomorphic structures

In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...

cc.complexity-theory graph-theory quantum-computing query-complexity  
asked by Root 1 vote
You're receiving this message because you subscribed to the Theoretical Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038