Lev Reyzin

Chicago, IL

levreyzin.com

Assistant Professor at UIC's math department

@lreyzin

google+

top accounts reputation activity favorites subscriptions

Problems Between P and NPC

cc.complexity-theory np-hardness big-list np-intermediate asked Aug 17 '10 at 2:07

cstheory.stackexchange.com

31 votes

Complexity of Finding the Eigendecomposition of a Matrix

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis asked Nov 1 '10 at 13:28

cstheory.stackexchange.com

27 votes

Surprising Results in Complexity (Not on the Complexity Blog List)

cc.complexity-theory big-list asked Aug 18 '10 at 18:14

cstheory.stackexchange.com

23 votes

Alan Turing's Contributions to Computer Science

soft-question ho.history-overview asked Jun 24 '12 at 2:47

cstheory.stackexchange.com

21 votes

Natural, untestable graph properties

cc.complexity-theory machine-learning query-complexity property-testing asked Sep 25 '12 at 1:33

cstheory.stackexchange.com

15 votes

Randomize or Not?

randomness big-picture randomized-algorithms asked Oct 15 '10 at 22:11

cstheory.stackexchange.com

14 votes

Properties of Random Directed Graphs with Fixed Out-Degree

graph-theory co.combinatorics automata-theory random-walks asked Sep 13 '10 at 15:19

cstheory.stackexchange.com

11 votes

The Cost of an Equivalence Query for DFA

automata-theory lg.learning regular-expressions dfa asked Jan 3 at 22:44

cstheory.stackexchange.com

11 votes

Teaching Loads by Field at Research Universities

professors asked May 10 '12 at 17:01

academia.stackexchange.com

9 votes

Complexity of Localization in Wireless Networks

cg.comp-geom asked Aug 19 '10 at 15:35

cstheory.stackexchange.com

Top Answers

Problems Between P and NPC

cstheory.stackexchange.com

Complexity of simplex algorithm

cstheory.stackexchange.com

Algorithms from the Book.

cstheory.stackexchange.com

What papers should everyone read?

cstheory.stackexchange.com

Is finding the minimum regular expression an NP-complete problem?

cstheory.stackexchange.com

Can one return to a TCS research job after an excursion to a non-research industry job?

cstheory.stackexchange.com

What is the enlightenment I'm supposed to attain after studying finite automata?

cstheory.stackexchange.com

Grid $k$-coloring without monochromatic rectangles

cstheory.stackexchange.com

Major unsolved problems in theoretical computer science?

cstheory.stackexchange.com

Why is CNF used for SAT and not DNF?

cstheory.stackexchange.com

Great algorithms, machine learning and no linear algebra

cstheory.stackexchange.com

What kind of mathematical background is needed for complexity theory?

cstheory.stackexchange.com

How intensive is the process of interviewing people for faculty openings?

academia.stackexchange.com

Should I worry about a referee who recommended rejection being offended if my paper is accepted?

academia.stackexchange.com

Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

cstheory.stackexchange.com

Grid $k$-coloring without monochromatic rectangles

cstheory.stackexchange.com

Does an infinitely long tape make any difference when proving theorems about Turing Machines?

cstheory.stackexchange.com

Why go to theoretical computer science/research?

cstheory.stackexchange.com

Proper PAC learning of 2-DNF under uniform distribution

cstheory.stackexchange.com

Open problems on the frontiers of TCS

cstheory.stackexchange.com

Reference for fundamental theorem on tree rotations

cstheory.stackexchange.com

The Warren Buffett Problem

cstheory.stackexchange.com

Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

cstheory.stackexchange.com

Multi-armed bandit problems where more than one arm can be selected?

cstheory.stackexchange.com

Is a PhD in TCS the best way towards achieving a career in industrial research?

cstheory.stackexchange.com

complexity of randomized gossiping

cstheory.stackexchange.com

Learning with “taciturn” oracles

cstheory.stackexchange.com

Can a non-competitive deterministic algorithm be k-competitive if randomized?

cstheory.stackexchange.com

A lottery that you can be convinced that it is fair

cstheory.stackexchange.com

Sorting algorithm in < n log n ?

cstheory.stackexchange.com