Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

NP complete problem help

I'm currently trying to find a reduction to this problem: Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...

cc.complexity-theory np-hardness complexity-classes cg.comp-geom  
asked by Andres Fuentes 9 votes

Context weakening as an explicit rule for languages of the the lambda cube?

I'm trying to formalize the syntax and typing judgments of the Calculus of Constructions in Coq. I'm choosing to use the Pure Type Systems presentation of CoC; however, I've seen mild variations in ...

type-theory calculus-of-constructions  
asked by NJay 4 votes
answered by Andrej Bauer 3 votes

Why should we believe that $NEXP \not \subset P/poly$

I am sorry if this is not an advanced question. Most computer scientists believed that $Nexp \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...

circuit-complexity derandomization nexp  
asked by Mohsen Ghorbani 3 votes
answered by 1.. 3 votes

Tableau method for two-variable first-order logic

$FO^2$, i.e. two-variable first-order logic, has a NEXPTIME-complete satisfiability problem (see Grädel, Kolaitis and Vardi '97). However, the decidability and complexity of this fragment is proved by ...

asked by gigabytes 2 votes
answered by Bartosz Bednarczyk 1 vote

Energy-Based Modeling vs Deep Learning

I am doing some research on machine learning algorithms in the context of a seminar, which focuses on Energy-Based Modeling vs Deep Learning specifically in working with images Modeling. Now I know ...

asked by dohm 2 votes

Hardness of Approximation of Continuous Metric k-Median

First let me describe the metric $k$-median problem. Definition (Metric $k$-Median): Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ ...

approximation-algorithms approximation-hardness set-cover clustering  
asked by Inuyasha yagami 1 vote

Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...

cc.complexity-theory lo.logic terminology descriptive-complexity finite-model-theory  
asked by Erfan Khaniki 1 vote

Greatest hits from previous weeks:

Applications of Hamiltonian Cycle Problem

The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively. I am looking for applications of the HamCycle and TSP. What are ...

graph-theory application-of-theory hamiltonian-paths  
asked by user136457 7 votes
answered by David Eppstein 8 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

Major unsolved problems in theoretical computer science?

Wikipedia only lists two problems under "unsolved problems in computer science": P = NP? The existence of one-way functions What are other major problems that should be added to this list? Rules: ...

big-list open-problem  
asked by Shane 224 votes
answered by András Salamon 144 votes

Which is the limit of lossless compression data? (if there exists such a limit)

Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression. So far, the only source I ...

it.information-theory data-streams  
asked by Auron 15 votes
answered by Jukka Suomela 28 votes

What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/...

soft-question big-picture lambda-calculus ho.history-overview  
asked by PhD 89 votes
answered by Martin Berger 100 votes

Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct? Also on topic: where else (on the internet) is its correctness being discussed? Note: the focus of this question text has ...

cc.complexity-theory np-hardness complexity-classes  
asked by Warren Schudy 232 votes
answered by idolvon 97 votes

Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...

cc.complexity-theory np-hardness big-list np-intermediate  
asked by Lev Reyzin 134 votes
answered by Lev Reyzin 107 votes
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