## 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

### 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 ...

context-free

### 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

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

### 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 ds.data-structures time-complexity

### 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

### 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

### 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

### 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

### 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

### 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

### 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

## 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