Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

Is there a simplex-like algorithm that can be used with a separation oracle?

Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...

linear-programming oracles simplex smoothed-analysis  
asked by Erel Segal-Halevi 6 votes
answered by Neal Young 3 votes

Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

For a non-empty $3-SAT$ with $n\geq3$ variables and $T\geq1$ non-identical non-degenerate clauses $C_i$: $$S=C_1 \wedge \ldots \wedge C_T$$ where a non-degenerate clause is one containing $3$ unique ...

sat upper-bounds  
asked by Craig 5 votes
answered by Lieuwe Vinkhuijzen 5 votes

Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$ $\begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size $...

randomness np-complete hard-instances complexity-assumptions  
asked by Punga 4 votes
answered by Andras Farago 1 vote

Induction-recursion in models other than $\mathbf{Set}$

It is well-known that various flavors of induction-recursion are consistent*. Typically, this is proven by showing that the standard model of type theory in sets can be extended to include induction-...

type-theory ct.category-theory denotational-semantics  
asked by Daniel Gratzer 4 votes
answered by Neel Krishnaswami 1 vote

Hardness of computing entropy of a function on uniform input distribution

Let $p \geq q \in \mathbb{N}_+$, and let $L_\mathsf{max-entropy} := \{(f,k) \in \{0,1\}^{\lambda^p} \times \{0,1\}^{\log\lambda} | \lambda \in \mathbb{N} \wedge \mathrm{H}(\underbrace{C_f(\mathcal{U}_{...

cc.complexity-theory shannon-entropy  
asked by Nicholas Brandt 2 votes

Evaluating multidimensional polynomials

Are there efficient algorithms to construct optimal evaluators of multivariable polynomials? Here, an 'evaluator' can be thought of as an algorithm or description of how to evaluate a specific ...

asked by TLDR 1 vote

How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?

I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...

computational-geometry shortest-path convex-geometry  
asked by user49404 1 vote

Greatest hits from previous weeks:

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 67 votes
answered by Mark Reitblatt 33 votes

Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...

soft-question open-problem dfa  
asked by Canadian goose 67 votes
answered by Hsien-Chih Chang 張顯之 63 votes

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...

soft-question quantum-computing big-list quantum-information  
asked by Vincent Russo 21 votes
answered by Joe Fitzsimons 21 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 35 votes
answered by Martin Berger 26 votes

Why is 2SAT in P?

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...

cc.complexity-theory np-hardness big-picture polynomial-time  
asked by Guy 69 votes
answered by Giorgio Camerani 97 votes

Alan Turing's Contributions to Computer Science

Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, ...

soft-question ho.history-overview  
asked by Lev Reyzin 35 votes
answered by Scott Aaronson 17 votes

How does type theory change how one thinks about programming?

I have been dabbling in HoTT and I am convinced that dependent type theory is much more suitable than set theory for proof assistants. Now, this made me wonder - how fundamental is Type Theory ...

pl.programming-languages type-theory dependent-type  
asked by Alapan Chaudhuri 6 votes
answered by ice1000 5 votes

Can you answer this question?

Partition of multisets of polynomials

Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ...

np-complete polynomials partition-problem  
asked by luciano 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