| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Ashish Goel, Michael Kapralov, Sanjeev Khanna |
On the communication and streaming complexity of maximum bipartite matching.  |
SODA  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ran Duan, Hsin-Hao Su |
A scaling algorithm for maximum weight matching in bipartite graphs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Martin Cadek, Marek Krcál, Jirí Matousek, Francis Sergeraert, Lukás Vokrínek, Uli Wagner |
Computing all maps into a sphere. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke |
An O(log k)-competitive algorithm for generalized caching. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu |
Bypassing UGC from some optimal geometric inapproximability results. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Yuval Rabani (eds.) |
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Andreas Björklund |
Counting perfect matchings as fast as Ryser. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Daniel M. Kane, Jelani Nelson |
Sparser Johnson-Lindenstrauss transforms. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Hsien-Chih Chang, Hsueh-I Lu |
A faster algorithm to recognize even-hole-free graphs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Martin Grohe |
Structural and logical approaches to the graph isomorphism problem. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Sourav Chakraborty, Oded Lachish |
Improved competitive ratio for the matroid secretary problem. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Petr Kolman, Christian Scheideler |
Approximate duality of multicommodity multiroute flows and cuts: single source case. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie |
Space-efficient local computation algorithms. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Liam Roditty, Virginia Vassilevska Williams |
Subquadratic time approximation algorithms for the girth. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Surender Baswana, Utkarsh Lath, Anuradha S. Mehta |
Single source distance oracle for planar digraphs avoiding a failed node or link. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | François Le Gall |
Improved output-sensitive quantum algorithms for Boolean matrix multiplication. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal |
Towards robust and efficient computation in dynamic peer-to-peer networks. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio |
Learning k-modal distributions via testing. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Gonzalo Navarro, Yakov Nekrich |
Top-k document retrieval in optimal time and linear space. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Stefan Kratsch, Magnus Wahlström |
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Daniel Dadush, Santosh Vempala |
Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Daniel Johannsen, Michael Krivelevich, Wojciech Samotij |
Expanders are universal for the class of all spanning trees. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Konstantin Makarychev, Warren Schudy, Maxim Sviridenko |
Concentration inequalities for nonlinear matroid intersection. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Preyas Popat, Yi Wu |
On the hardness of pricing loss-leaders. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Chien-Chung Huang, Telikepalli Kavitha |
Efficient algorithms for maximum weight matchings in general graphs with small edge weights. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ely Porat, Martin J. Strauss |
Sublinear time, measurement-optimal, sparse recovery for all. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price |
Simple and practical algorithm for sparse Fourier transform. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | S. Anand, Naveen Garg, Amit Kumar |
Resource augmentation for weighted flow-time explained by dual fitting. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis |
Approximating fixation probabilities in the generalized Moran process. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Shuchi Chawla, Jason D. Hartline, Balasubramanian Sivan |
Optimal crowdsourcing contests. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta |
Approximating rooted Steiner networks. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ravishankar Krishnaswamy, Maxim Sviridenko |
Inapproximability of the multi-level uncapacitated facility location problem. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Gabriel Moruz, Andrei Negoescu |
Outperforming LRU via competitive analysis on parametrized inputs for paging. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Konstantinos Georgiou, Chaitanya Swamy |
Black-box reductions for cost-sharing mechanism design. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Michael Drmota, Omer Giménez, Marc Noy, Konstantinos Panagiotou, Angelika Steger |
The maximum degree of random planar graphs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Frans Schalekamp, David P. Williamson, Anke van Zuylen |
A proof of the Boyd-Carr conjecture. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Nikolaos Fountoulakis, Konstantinos Panagiotou, Thomas Sauerwald |
Ultra-fast rumor spreading in social networks. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Prasad Raghavendra, Ning Tan |
Approximating CSPs with global cardinality constraints using SDP hierarchies. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld |
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Telikepalli Kavitha |
Popularity vs maximum cardinality in the stable marriage setting. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky |
On the (in)security of hash-based oblivious RAM and a new balancing scheme. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Timothy M. Chan, Elyot Grant, Jochen Könemann, Malcolm Sharpe |
Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Bach Q. Ha, Jason D. Hartline |
Mechanism design via consensus estimates, cross checking, and profit extraction. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Russell Impagliazzo, William Matthews, Ramamohan Paturi |
A satisfiability algorithm for AC0. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou |
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Sébastien Collette, John Iacono, Stefan Langerman |
Confluent persistence revisited. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Renato Paes Leme, Vasilis Syrgkanis, Éva Tardos |
Sequential auctions and externalities. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Aaron Bernstein |
Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Vijay V. Vazirani |
The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Thomas Rothvoß |
The entropy rounding method in approximation algorithms. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Danny Hermelin, Xi Wu |
Weak compositions and their applications to polynomial lower bounds for kernelization. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Siddharth Barman, Shuchi Chawla |
Traffic-redundancy aware network design. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Louigi Addario-Berry, Tao Lei |
The mixing time of the Newman: Watts small world. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Frank Kammer, Torsten Tholey |
Approximate tree decompositions of planar graphs in linear time. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin K. Lee |
Submodular functions are noise stable. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ho-Lin Chen, David Doty |
Parallelism and time in hierarchical self-assembly. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi |
Approximation algorithms for stochastic orienteering. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Kasper Green Larsen, Rasmus Pagh |
I/O-efficient data structures for colored range and prefix reporting. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir |
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot |
Competitive routing in the half-θ6-graph. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Kasturi Varadarajan, Xin Xiao |
A near-linear algorithm for projective clustering integer points. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Berthold Vöcking |
A universally-truthful approximation scheme for multi-unit auctions. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi |
Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Marc Lelarge |
A new approach to the orientation of random hypergraphs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Magnús M. Halldórsson, Pradipta Mitra |
Wireless connectivity and capacity. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | James R. Lee, Arnaud de Mesmay, Mohammad Moharrami |
Dimension reduction for finite trees in l1. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Charilaos Efthymiou |
A simple algorithm for random colouring G(n, d/n) using (2 + ε)d colours. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Paul Bendich, Bei Wang, Sayan Mukherjee |
Local homology transfer and stratification learning. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Susanne Albers, Antonios Antoniadis |
Race to idle: new algorithms for speed scaling with a sleep state. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
SINR diagram with interference cancellation. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Ali Kemal Sinop |
Optimal column-based low-rank matrix reconstruction. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Rico Zenklusen |
Matroidal degree-bounded minimum spanning trees. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Po-Shen Loh, Eyal Lubetzky |
Stochastic coalescence in logarithmic time. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Morteza Ibrahimi, Yashodhan Kanoria, Matt Kraning, Andrea Montanari |
The set of solutions of random XORSAT formulae. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Arman Yousefi, Neal E. Young |
On a linear program for minimum-weight triangulation. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos |
Linear kernels for (connected) dominating set on H-minor-free graphs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, Vlady Ravelomanana |
The MAX-CUT of sparse random graphs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | R. Sharathkumar, Pankaj K. Agarwal |
Algorithms for the transportation problem in geometric settings. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Sungjin Im, Benjamin Moseley, Kirk Pruhs |
Online scheduling with general cost functions. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Warren Schudy, Maxim Sviridenko |
Concentration and moment inequalities for polynomials of independent random variables. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Adrian Dumitrescu, Csaba D. Tóth |
Packing anchored rectangles. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Fedor V. Fomin, Yngve Villanger |
Subexponential parameterized algorithm for minimum fill-in. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Vladimir Kolmogorov, Stanislav Zivny |
The complexity of conservative valued CSPs. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Silvio Frischknecht, Stephan Holzer, Roger Wattenhofer |
Networks cannot compute their diameter in sublinear time. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Yoann Dieudonné, Andrzej Pelc, David Peleg |
Gathering despite mischief. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Andrew McGregor, Paul Valiant |
The shifting sands algorithm. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Yusuke Kobayashi |
List-coloring graphs without subdivisions and without immersions. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | John Iacono, Mihai Patrascu |
Using hashing to solve the dictionary problem. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Dan Feldman, Leonard J. Schulman |
Data reduction for weighted and outlier-resistant clustering. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira |
Testing odd-cycle-freeness in Boolean functions. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Alexandr Andoni, Huy L. Nguyen |
Width of points in the streaming model. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Stefan Kratsch |
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Menelaos I. Karavelas, Eleni Tzanaki |
The maximum number of faces of the Minkowski sum of two convex polytopes. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Nicolas Broutin, Ralph Neininger, Henning Sulzbach |
Partial match queries in random quadtrees. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs |
Scheduling heterogeneous processors isn't as easy as you think. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
Polytope approximation and the Mahler volume. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Anne Driemel, Sariel Har-Peled |
Jaywalking your dog: computing the Fréchet distance with shortcuts. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Amin Coja-Oghlan, Lenka Zdeborová |
The condensation transition in random hypergraph 2-coloring. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Krishnendu Chatterjee, Monika Henzinger |
An O(n2) time algorithm for alternating Büchi games. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio |
Private data release via learning thresholds. |
SODA |
2012 |
DBLP BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")