Theoretical Computer Science Stack Exchange Community Digest

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  
asked by M.Monet 12 votes

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  
asked by William Hoza 7 votes

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  
asked by Akash Agrawal 5 votes

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  
asked by CSSTUDENT 3 votes
answered by user3483902 0 votes

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  
asked by Nift 3 votes

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  
asked by Rodrigo 3 votes
answered by Denis 9 votes

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  
asked by Neel Krishnaswami 2 votes

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  
asked by Felipe 18 votes
answered by Christian Komusiewicz 26 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 25 votes
answered by Andrej Bauer 61 votes

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  
asked by jkff 586 votes
answered by jbapple 576 votes

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  
asked by PhD 19 votes
answered by Mike Spivey 19 votes

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  
asked by László Kozma 45 votes

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  
asked by Rahab 101 votes
answered by M.S. Dousti 45 votes

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  
asked by Ryan Williams 477 votes
answered by Grigory Yaroslavtsev 170 votes

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  
asked by templatetypedef 1 vote

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

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

<3