## Top new questions this week:

### Is this problem on unambiguous finite automata NP-complete?

An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp....

automata-theory np-complete

### Where is Yao's original proof that distinguishers imply next-bit-predictors?

In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that ...

reference-request ho.history-overview pseudorandomness pseudorandom-generators

### How to find the second smallest cut in a graph?

For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, ...

ds.algorithms graph-theory max-flow-min-cut

### What are some "must-read" papers for someone getting into Quantum Cryptography?

I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography. I'm interested in Quantum Cryptography and would ...

quantum-computing cr.crypto-security quantum-information

### Abstract stone duality and cohesive homotopy type theory

I have been reading the real-cohesive homotopy type theory paper and one of the remarks has sparked an interest. In this paper a string of monadic and comonadic modalities is introduced together with ...

topology homotopy-type-theory stone-duality

### Proof and computational complexity

I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...

cc.complexity-theory reference-request lo.logic computability

### Boltzmann sampling for containers/dependent polynomials?

I’d like to randomly sample from dependently-typed data structures. Has anyone looked at extending Boltzmann sampling to containers or dependent polynomials?

co.combinatorics lo.logic type-theory dependent-type sampling

## Greatest hits from previous weeks:

### Has parameterized complexity led to better algorithms?

I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...

cc.complexity-theory ds.algorithms complexity-classes time-complexity parameterized-complexity

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

### What's new in purely functional data structures since Okasaki?

Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by ...

reference-request big-list ds.data-structures functional-programming

### An intuitive/informal proof for LP Duality?

What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of ...

linear-programming primal-dual

### Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...

np-hardness fl.formal-languages lg.learning regular-expressions

### What are the recent TCS books whose drafts are available online?

Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online. For instance, the Approximation Algorithms entry of the above post cites ...

reference-request big-list books

### What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...

big-list soft-question

## Can you answer these questions?

### Efficiency of building orthogonal range search structures?

I've been reading up on data structures for 2D range searching. I've noticed that, in many of the papers I've read, there's close attention paid to the query cost and the space usage required, but ...

ds.data-structures cg.comp-geom

### Complexity of counting 3-colourings of planar bounded degree graphs

The following are known: It is #P-complete to count the number of 3-colourings of a planar graph [1]. For all $k\geq 3$ and $d\geq 3$, it is #P-complete to count the number of $k$-colourings of a ...

graph-theory counting-complexity planar-graphs graph-colouring bounded-degree
 asked by Cyriac Antony 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, 110 William Street, 28th floor, New York, NY 10038

 <3