bio | website | |
---|---|---|
location | ||
age | ||
visits | member for | 2 years, 1 month |
seen | Jun 24 '13 at 6:03 | |
stats | profile views | 143 |
I'm an undergraduate who's pretty into math. Heading to computer science grad school in Fall 2013.
Jun 19 |
accepted | Can we efficiently compute a third Nash Equilibrium, given two? |
Jun 19 |
comment |
What new primitive recursive functions are needed to reconcile Turing time complexity with Godel time complexity?
@JoelDavidHamkins: I want the following statement to be true -- For every function $f(|n|)$ and for every recursive function, there exists a recursive definition that is $O(f(|n|))$ in Godel complexity if and only if there exists a Turing machine that computes the function in $O(f(|n|))$ steps. I am not restricting my attention to Turing machines of a particular notation alphabet -- If there is a recursive definition in $O(|n|)$ then I'd like some Turing machine of any input alphabet that runs in $O(|n|)$ steps. |
Jun 19 |
comment |
What new primitive recursive functions are needed to reconcile Turing time complexity with Godel time complexity?
Yes, by "best-case" I mean "optimal worst-case," thank you. By "equal to," I mean "asymptotically equal to" - I would like it such that (for example) if a function can be implemented in $O(|n|)$ time on a Turing machine, then it can necessarily be implemented in $O(|n|)$ time via primitive recursive functions (and vice versa). |
Jun 19 |
asked | What new primitive recursive functions are needed to reconcile Turing time complexity with Godel time complexity? |
Apr 27 |
awarded | Commentator |
Apr 27 |
comment |
When does the finite union of convex sets have a hole in it?
Man, that is a cool answer you linked to. I do have a way to test intersections, so that will do perfectly. |
Apr 27 |
revised |
When does the finite union of convex sets have a hole in it?
edited title |
Apr 27 |
revised |
When does the finite union of convex sets have a hole in it?
added 299 characters in body |
Apr 27 |
comment |
When does the finite union of convex sets have a hole in it?
1. Yes, it's the union, not the intersection of the sets (the intersection would be convex =) ). 2. Yes, I am attempting a floating-point algorithm. Rather than place restrictions on the sets, I'm hoping to use standard convex optimization techniques as a subroutine (the $\epsilon$-fudginess in these techniques is okay; I'd be fine with an algorithm that reports "the functions come within $\epsilon$ of being hole-less"). |
Apr 27 |
revised |
When does the finite union of convex sets have a hole in it?
deleted 16 characters in body; edited title; added 55 characters in body |
Apr 27 |
asked | When does the finite union of convex sets have a hole in it? |
Mar 1 |
awarded | Yearling |
Feb 5 |
asked | Geometric interpretations of matrix inverses |
Jan 23 |
accepted | Does this result exist in the literature? |
Jan 22 |
asked | Does this result exist in the literature? |
Jan 8 |
asked | Is there a general process for conditioning a stochastic process above a boundary? |
Jan 6 |
awarded | Critic |
Dec 20 |
accepted | Can we express a one-dimensional raised Bessel Bridge as a function of a single Brownian Motion? |
Dec 20 |
asked | Can we express a one-dimensional raised Bessel Bridge as a function of a single Brownian Motion? |
Nov 15 |
comment |
Largest subarray with average $\geq$ k
You can easily get down to $O(n \log n)$ by first sorting the array, then checking the subarray [0..0], then [0..1], then [0..2], etc. |