Search

Your search keyword '"O’Donnell, Ryan"' showing total 28 results
Start Over Author "O’Donnell, Ryan" Publisher springer berlin heidelberg

Refine your results

more »

more »

28 results on '"O’Donnell, Ryan"'

2. Algorithmic Signaling of Features in Auction Design

Author

Dughmi, Shaddin, Immorlica, Nicole, O’Donnell, Ryan, Tan, Li-Yang, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Hoefer, Martin, editor

Published
2015
Full Text
View/download PDF

3. Optimal Bounds for Estimating Entropy with PMF Queries

Author

Caferov, Cafer, Kaya, Barış, O’Donnell, Ryan, Say, A. C. Cem, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Italiano, Giuseppe F., editor, Pighizzini, Giovanni, editor, and Sannella, Donald T., editor

Published
2015
Full Text
View/download PDF

4. A Composition Theorem for the Fourier Entropy-Influence Conjecture

Author

O’Donnell, Ryan, Tan, Li-Yang, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fomin, Fedor V., editor, Freivalds, Rūsiņš, editor, Kwiatkowska, Marta, editor, and Peleg, David, editor

Published
2013
Full Text
View/download PDF

5. A New Point of NP-Hardness for 2-to-1 Label Cover

Author

Austrin, Per, O’Donnell, Ryan, Wright, John, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gupta, Anupam, editor, Jansen, Klaus, editor, Rolim, José, editor, and Servedio, Rocco, editor

Published
2012
Full Text
View/download PDF

6. The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions

Author

O’Donnell, Ryan, Wright, John, Zhou, Yuan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Henzinger, Monika, editor, and Sgall, Jiří, editor

Published
2011
Full Text
View/download PDF

7. k + Decision Trees : (Extended Abstract)

Author

Aspnes, James, Blais, Eric, Demirbas, Murat, O’Donnell, Ryan, Rudra, Atri, Uurtamo, Steve, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Scheideler, Christian, editor

Published
2010
Full Text
View/download PDF

8. Testing (Subclasses of) Halfspaces

Author

Matulef, Kevin, O’Donnell, Ryan, Rubinfeld, Ronitt, Servedio, Rocco, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Goldreich, Oded, editor

Published
2010
Full Text
View/download PDF

9. SDP Gaps for 2-to-1 and Other Label-Cover Variants

Author

Guruswami, Venkatesan, Khot, Subhash, O’Donnell, Ryan, Popat, Preyas, Tulsiani, Madhur, Wu, Yi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Abramsky, Samson, editor, Gavoille, Cyril, editor, Kirchner, Claude, editor, Meyer auf der Heide, Friedhelm, editor, and Spirakis, Paul G., editor

Published
2010
Full Text
View/download PDF

10. Testing ±1-weight halfspace

Author

Matulef, Kevin, O’Donnell, Ryan, Rubinfeld, Ronitt, Servedio, Rocco A., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dinur, Irit, editor, Jansen, Klaus, editor, Naor, Joseph, editor, and Rolim, José, editor

Published
2009
Full Text
View/download PDF

11. Testing Fourier Dimensionality and Sparsity

Author

Gopalan, Parikshit, O’Donnell, Ryan, Servedio, Rocco A., Shpilka, Amir, Wimmer, Karl, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Albers, Susanne, editor, Marchetti-Spaccamela, Alberto, editor, Matias, Yossi, editor, Nikoletseas, Sotiris, editor, and Thomas, Wolfgang, editor

Published
2009
Full Text
View/download PDF

12. Approximation by DNF: Examples and Counterexamples

Author

O’Donnell, Ryan, Wimmer, Karl, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arge, Lars, editor, Cachin, Christian, editor, Jurdziński, Tomasz, editor, and Tarlecki, Andrzej, editor

Published
2007
Full Text
View/download PDF

13. PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption

Author

Feldman, Jon, Servedio, Rocco A., O’Donnell, Ryan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Lugosi, Gábor, editor, and Simon, Hans Ulrich, editor

Published
2006
Full Text
View/download PDF

14. Eliminating Cycles in the Discrete Torus

Author

Bollobás, Béla, Kindler, Guy, Leader, Imre, O’Donnell, Ryan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Correa, José R., editor, Hevia, Alejandro, editor, and Kiwi, Marcos, editor

Published
2006
Full Text
View/download PDF

20. k + Decision Trees

Author

Aspnes, James, primary, Blais, Eric, additional, Demirbas, Murat, additional, O’Donnell, Ryan, additional, Rudra, Atri, additional, and Uurtamo, Steve, additional

Published
2010
Full Text
View/download PDF

26. Testing +/- 1-Weight Halfspaces

Author

Matulef, Kevin M., O'Donnell, Ryan, Rubinfeld, Ronitt, Sevedio, Rocco A., Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Rubinfeld, Ronitt, and Matulef, Kevin M.

Abstract

We consider the problem of testing whether a Boolean function f:{ − 1,1} [superscript n] →{ − 1,1} is a ±1-weight halfspace, i.e. a function of the form f(x) = sgn(w [subscript 1] x [subscript 1] + w [subscript 2] x [subscript 2 ]+ ⋯ + w [subscript n] x [subscript n] ) where the weights w i take values in { − 1,1}. We show that the complexity of this problem is markedly different from the problem of testing whether f is a general halfspace with arbitrary weights. While the latter can be done with a number of queries that is independent of n [7], to distinguish whether f is a ±-weight halfspace versus ε-far from all such halfspaces we prove that nonadaptive algorithms must make Ω(logn) queries. We complement this lower bound with a sublinear upper bound showing that $O(\sqrt{n}\cdot $poly$(\frac{1}{\epsilon}))$ queries suffice.

Published
2009

28. Testing +/- 1-Weight Halfspaces

Author

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Rubinfeld, Ronitt, Matulef, Kevin M., O'Donnell, Ryan, Sevedio, Rocco A., Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Rubinfeld, Ronitt, Matulef, Kevin M., O'Donnell, Ryan, and Sevedio, Rocco A.

Published
2010

Catalog

Books, media, physical & digital resources
See catalog results