Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

The theoretical complexity of Go - The state of the art

What are the latest advances in theoretical complexity of Go? I know some early works about the complexity of Go: "Go is polynomial-space hard" proved that Go is PSPACE-hard. "Ladders are ...

complexity-classes complexity  
asked by TeamBright 7 votes
answered by Denis 6 votes

Applications of sunflower lemma in theoretical computer science

In one lecture by Kewen Wu who is one of the authors of paper Improved bounds for the sunflower lemma , it is said that sunflower lemma can be applied to many fields like circuit lower bound ...

asked by Bubble 6 votes

Subgraph isomorphism on graph sequences

I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences. Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...

ds.algorithms reference-request graph-algorithms graph-isomorphism parameterized-complexity  
asked by LeechLattice 4 votes

Proof systems induced by NP-complete problems

Satisfiability is the fundamental NP-complete problem. Cook-Reckhow theorem states that the existence of a propositional proof system that admits polynomial size proofs for all tautologies implies ...

cc.complexity-theory reference-request proof-complexity  
asked by Mohammad Al-Turkistany 2 votes

Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? // Quantum automata

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...

fl.formal-languages quantum-computing automata-theory  
asked by catalyst 2 votes

MWIS on the 2-section of a specific uniform linear hypergraph

My question concerns the maximum weight independent set (MWIS) problem on a certain (but "nice") graph. In particular, I am puzzled as to why I can seemingly solve the problem via its LP relaxation ...

graph-theory optimization linear-programming  
asked by axelniemeyer 1 vote

Relation between automorphism group of a linear code and its dual code

Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc. In ...

coding-theory algebra combinatorics  
asked by Root 1 vote

Greatest hits from previous weeks:

Why colon to denote that a value belongs to a type?

Pierce (2002) introduces the typing relation on page 92 by writing: The typing relation for arithmetic expressions, written "t : T", is defined by a set of inference rules assigning types to ...

type-theory notation  
asked by Björn Lindqvist 19 votes
answered by Gilles 'SO- stop being evil' 12 votes

What Lecture Notes Should Everyone Read?

There has been several questions with the same scheme as this one: What papers should everyone read What books should everyone read What are the recent TCS books whose drafts are available online ...

reference-request soft-question big-list  
asked by M.S. Dousti 114 votes
answered by Nikhil 32 votes

What kind of answer does TCS want to the question "Why do neural networks work so well?"

My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...

asked by Neuling 53 votes
answered by Aryeh 39 votes

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  
asked by Matt Munson 23 votes
answered by matus 26 votes

Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...

ds.algorithms big-list implementation  
asked by Elliot JJ 68 votes
answered by Yaroslav Bulatov 33 votes

Turing award papers

I was wondering if there are individual publications that have led their authors to win the Turing Prize or if the Turing Prize is the result of a lifetime's work and multiple publications and ...

asked by Yamar69 21 votes
answered by 6005 25 votes

How practical is Automata Theory?

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...

soft-question fl.formal-languages automata-theory teaching  
asked by Dark Templar 37 votes
answered by Anonymous 52 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