2.5k citations
- IBM Research - Thomas J. Watson Research CenterUS46 papers
- Massachusetts Institute of TechnologyUS22 papers
- Vassar CollegeUS16 papers
- California Institute of TechnologyUS13 papers
- Columbia UniversityUS12 papers
- Stanford UniversityUS11 papers
- Centre National de la Recherche ScientifiqueFR10 papers
- Carnegie Mellon UniversityUS9 papers
- University of Illinois Urbana-ChampaignUS9 papers
- University of MichiganUS9 papers
- IBM Research - ZurichCH8 papers
- Iowa State UniversityUS8 papers
5 papers · 1 filter
Bargaining for Revenue Shares on Tree Trading Networks
Arpita Ghosh, Satyen Kale, Kevin Lang +1
We study trade networks with a tree structure, where a seller with a single indivisible good is connected to buyers, each with some value for the good, via a unique path of interme…
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
Vitaly Feldman, Pravesh Kothari, Jan Vondrak
We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube . Our main result is th…
A New Approach to Updating Beliefs
Ronald Fagin, Joseph Y. Halpern
We define a new notion of conditional belief, which plays the same role for Dempster-Shafer belief functions as conditional probability does for probability functions. Our definiti…
Static and dynamic semantics of NoSQL languages
Véronique Benzaken, Giuseppe Castagna, Kim Nguy\~ên +1
We present a calculus for processing semistructured data that spans differences of application area among several novel query languages, broadly categorized as "NoSQL". This calcul…
Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization
Stefano Ermon, Carla P. Gomes, Ashish Sabharwal +1
Integration is affected by the curse of dimensionality and quickly becomes intractable as the dimensionality of the problem grows. We propose a randomized algorithm that, with high…