Top new questions this week:
|
|
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 ...
|
|
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
...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
Greatest hits from previous weeks:
|
|
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 ...
|
|
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
...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
