1,540 reputation
112
bio website
location
age
visits member for 1 year, 9 months
seen 13 hours ago

I'm a first year computer science graduate student. My research interests are mathematical logic, complexity theory, algorithms, spectral graph theory, lower bounds, computational economics, algorithmic game theory, and probability.


Apr
6
comment Pure vs mixed strategy Nash Equilibria
@BalazsRau : Let's say you're playing a game where the players can pick between $n$ different strategies. In general, there might be mixed equilibria that only mix over $k$ of those $n$ strategies. In this case, there will be some linear combination of my $k$ strategies that will make you like some $k$ of your strategies equally well (and the other $n-k$ strategies less than that). In the pure case ($k=1$), this statement is uninteresting: it just says that you like $1$ of your strategies at least as well as all the others, which is obvious.
Apr
6
comment Pure vs mixed strategy Nash Equilibria
This is off on a bit of a tangent from your original post, though =) the answer to your original question is "a pure strategy is just a mixed strategy over exactly 1 strategy."
Apr
6
comment Pure vs mixed strategy Nash Equilibria
I agree with your NE analysis. The "equally happy with anything" bit of my post referred specifically to mixed equilibria, sorry if that was unclear. It turns out that if $A$ plays a mixed-strategy equilibrium where he has nonzero chance of playing $k$ different strategies, then there is some set of $k$ strategies for $B$ that are all equally good (and therefore $B$ can randomize among them however he likes). In the special case of $k=1$ ("pure strategy equilibrium"), that means there is (at least) $1$ strategy for $B$ that stands up to scrutiny, which is not so informative.
Apr
6
answered Pure vs mixed strategy Nash Equilibria
Mar
25
comment Questions on “simple-connectedness-like” property
One problem with your definition: some disconnected sets will not be "non-simply connected" (because, for example, there do not exist open connected subsets $U, V \subset X$ eith $U \cup V = X$) and therefore it will be defined as "simply connected." I doubt that's what you want.
Mar
25
comment The next number in the series: $1,3,10,33,109\dots$
Or rather, it's $t_n = 3t_{n-1} + t_{n-2}$.
Mar
25
comment The next number in the series: $1,3,10,33,109\dots$
Yup, I think that checks out. No problem!
Mar
25
answered The next number in the series: $1,3,10,33,109\dots$
Mar
24
comment Tradeoff between graph diameter and graph connectivity
Sure, you could. I used powers in an effort to emphasize that I don't care about constant factors in the diameter lower bound, but a straightforward $b, d, a$ relationship would be equally interesting.
Mar
24
asked Tradeoff between graph diameter and graph connectivity
Mar
17
asked What are the current lower bounds for $NTIME$ vs $DTIME$?
Mar
17
comment Build a deterministic turing machine to decide L = { ww }
Are you interested in finding a determistic algorithm to solve the problem? Or do you really need to know a Turing machine specification, with states and transition functions and the like?
Mar
15
comment Relationship between graph edge count and coverability
This diameter approximation is only true of random graphs, yes? I think I can imagine a $k$-regular graph of diameter $O(n)$ (looks approximately like a chain of $k$-cliques).
Mar
14
asked Relationship between graph edge count and coverability
Mar
13
comment Finding probability of 2 cards summing to an odd number
Yes, nice observation. Another way to see that $\frac{25}{45} = \frac{5}{9}$ is the right answer is to notice that, after the first card is drawn, regardless of the outcome exactly $5$ of the remaining $9$ cards will make the sum odd. Maybe you can use the same concept to solve part (c).
Mar
12
comment Polytime implementation of Discrete Log using primitive recursive functions
I don't think that algorithm can be translated to primitive recursives in a nice way. If you want to run a search over possible $k$, you will need a Primitive Recursion index function that is either $O(1)$ (making the search unsound) or $O(n)$ (making the search exponential time). The ideal loop index is $O(\log n)$, but we can't create an $O(\log n)$ expression without the use of discrete log itself!
Mar
12
answered How to show that if $G$ is a graph with $\delta (G) \geq 2$ then $G$ contains a cycle?
Mar
11
revised Polytime implementation of Discrete Log using primitive recursive functions
deleted 366 characters in body
Mar
11
asked Polytime implementation of Discrete Log using primitive recursive functions
Mar
1
comment What parameter settings make this expression $\Omega(1)$?
What is $M$? $\textbf{}$