vzn

3,144 reputation

2620

cyber study group/research program on (monotone) circuit theory in a chat room... with a NP vs P/Poly attack, via a recent/fresh/novel outline for a NP vs P/poly proof based on monotone circuits, hypergraphs, factoring, and slice functions. any takers?

^{The algorithm designer who does not run experiments risks becoming lost in abstraction.}
^—Sedgewick

	3,144 reputation	bio	website	vzn1.wordpress.com	visits	member for	1 year, 4 months
2620 badges		location	U.S.		seen	10 hours ago

143 Answers

votes activity newest

23	Probabilistic (randomized) algorithms before “modern” computer science appeared
16	Implications of proof of abc conjecture for cs theory
13	Why are perfect graphs called perfect?
10	NTIME(n^k) ≠ DTIME(n^k) ?
9	Probabilistic (randomized) algorithms before “modern” computer science appeared

+5	loop invariants in proving program termination
-10	Wikipedia-style explanation of Geometric Complexity Theory
+8	Universal Approximation Theorem — Neural Networks
-2	Why economists should care about computational complexity

votes activity newest

7	Is adiabatic quantum computing as powerful as qubit computing?
7	What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?
7	computing the minimal NFA for a DFA
6	Are there applications of modular graph decomposition in TCS/complexity theory?
6	Examples of non-CSLs not created through diagonalization

	Theoretical Computer Science	3,144 rep	2620
	Computer Science	1,074 rep	411
	Cross Validated	196 rep	4
	Area 51	145 rep	2
$Mathematics Stack Exchange$	Mathematics	108 rep	4