vzn

3,152 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,152 reputation	bio	website	vzn1.wordpress.com	visits	member for	1 year, 4 months
2620 badges		location	U.S.		seen	12 hours ago

145 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

+10	When does (or should) Theoretical CS care about intuitionistic proofs?
-2	Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?
+5	loop invariants in proving program termination
-2	Wikipedia-style explanation of Geometric Complexity Theory

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,152 rep	2620
	Computer Science	1,084 rep	411
	Cross Validated	196 rep	4
	Area 51	145 rep	2
$Mathematics Stack Exchange$	Mathematics	108 rep	4