User contributions
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 04:18, 17 November 2012 (diff | hist) . . (+212) . . Bibliography
- 04:14, 17 November 2012 (diff | hist) . . (+846) . . N Open Problems:46 (Created page with "{{Header |title=Fast JL Transform for Sparse Vectors |source=bertinoro11 |who=Jelani Nelson }} Consider a distribution over linear mappings $A$ from $R^d$ to $R^k$, $k=O(\log...")
- 04:13, 17 November 2012 (diff | hist) . . (+195) . . Bibliography
- 04:10, 17 November 2012 (diff | hist) . . (+1,033) . . N Open Problems:45 (Created page with "{{Header |title=Streaming Max-Cut/Max-CSP |source=bertinoro11 |who=Robert Krauthgamer }} The problem is defined as follows: given a stream of edges of an $n$-node graph $G$, e...")
- 04:09, 17 November 2012 (diff | hist) . . (+348) . . Bibliography
- 04:01, 17 November 2012 (diff | hist) . . (+983) . . N Open Problems:44 (Created page with "{{Header |title=Approximating LIS Length in the Streaming Model |source=bertinoro11 |who=Amit Chakrabarti }} The goal of LIS is to compute a $2$-approximation of the length of...")
- 04:00, 17 November 2012 (diff | hist) . . (+215) . . Bibliography
- 03:58, 17 November 2012 (diff | hist) . . (+669) . . Bibliography
- 03:49, 17 November 2012 (diff | hist) . . (+916) . . N Open Problems:43 (Created page with "{{Header |title=Rank Lower Bound |source=bertinoro11 |who=Madhu Sudan }} We want to prove that the following tall matrix has full column rank. The columns are indexed by $a_1,...")
- 03:48, 17 November 2012 (diff | hist) . . (+452) . . Bibliography
- 03:41, 17 November 2012 (diff | hist) . . (+1,036) . . N Open Problems:42 (Created page with "{{Header |title=Graph Frequency Vectors |source=bertinoro11 |who=Noga Alon }} For a graph $G$, a $k$-disc around a vertex $v$ is the subgraph induced by the vertices that are ...")
- 03:37, 17 November 2012 (diff | hist) . . (+704) . . N Open Problems:41 (Created page with "{{Header |title=Testing Acyclicity |source=bertinoro11 |who=Dana Ron }} Consider the problem of testing acyclicity in ''directed'' bounded-degree graphs (in the incidence list...")
- 03:36, 17 November 2012 (diff | hist) . . (+177) . . Bibliography
- 03:33, 17 November 2012 (diff | hist) . . (+1,499) . . N Open Problems:40 (Created page with "{{Header |title=Testing Monotonicity and the Lipschitz Property |source=bertinoro11 |who=Sofya Raskhodnikova }} Positive answers to the conjectures below would imply better te...")
- 03:32, 17 November 2012 (diff | hist) . . (+438) . . Bibliography
- 03:19, 17 November 2012 (diff | hist) . . (+2) . . m Open Problems:39
- 03:19, 17 November 2012 (diff | hist) . . (+514) . . N Open Problems:39 (Created page with "{{Header |title=Approximating Maximum Matching Size |source=bertinoro11 |who=Krzysztof Onak }} Consider graphs with maximum degree bounded by $d$. It is possible to approximat...")
- 03:19, 17 November 2012 (diff | hist) . . (+424) . . Bibliography
- 03:13, 17 November 2012 (diff | hist) . . (+1,126) . . N Open Problems:38 (Created page with "{{Header |title=Query Complexity of Local Partitioning Oracles |source=bertinoro11 |who=Krzysztof Onak }} A local partitioning oracle is defined in the paper of Hassidim, Keln...")
- 03:13, 17 November 2012 (diff | hist) . . (+607) . . Bibliography
- 05:29, 16 November 2012 (diff | hist) . . (-154) . . Open Problems:37
- 05:29, 16 November 2012 (diff | hist) . . (-154) . . Open Problems:36
- 05:27, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:35
- 05:27, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:34
- 05:27, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:33
- 05:25, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:32
- 05:25, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:31
- 05:25, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:30
- 05:24, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:29
- 05:24, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:28
- 05:22, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:27
- 05:22, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:26
- 05:21, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:25
- 05:21, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:24
- 05:20, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:23
- 05:17, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:22
- 05:16, 16 November 2012 (diff | hist) . . (+36) . . Open Problems:21
- 05:13, 16 November 2012 (diff | hist) . . (-187) . . Open Problems:21
- 05:13, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:20
- 05:12, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:19
- 05:12, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:18
- 05:11, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:17
- 05:11, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:16
- 05:10, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:15
- 05:08, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:14
- 05:08, 16 November 2012 (diff | hist) . . (-230) . . Open Problems:13
- 05:07, 16 November 2012 (diff | hist) . . (+79) . . Open Problems:13
- 05:07, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:12
- 05:05, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:11
- 05:04, 16 November 2012 (diff | hist) . . (-151) . . Open Problems:10
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
