NDLI: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC '12)

Please wait, while we are loading the content...

Faster approximate multicommodity flow using quadratically coupled flows

Quantum money from hidden subspaces

The cell probe complexity of dynamic range counting

Polyhedral clinching auctions and the adwords polytope

Computing a nonnegative matrix factorization -- provably

Short proofs for the determinant identities

Solution of the propeller conjecture in $R^{3}$

From irreducible representations to locally decodable codes

Approximation algorithms for semi-random partitioning problems

Prior-free auctions with ordered bidders

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

Fast matrix rank algorithms and applications

Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

Learning poisson binomial distributions

Competitive contagion in networks

Pseudorandom generators with long stretch and low locality from random local one-way functions

Routing in undirected graphs with constant congestion

Catching the k-NAESAT threshold

Tight bounds for distributed functional monitoring

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities

Monotone expansion

Multi-way spectral partitioning and higher-order cheeger inequalities

On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks

Certifiable quantum dice: or, true random number generation secure against quantum adversaries

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

Matroid prophet inequalities

On identity testing of tensors, low-rank recovery and compressed sensing

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space

2log1-ε n hardness for the closest vector problem with preprocessing

Folded codes from function field towers and improved optimal rate list decoding

A near-linear time ε-approximation algorithm for geometric bipartite matching

On the limits of black-box reductions in mechanism design

Tight bounds for monotone switching networks via fourier analysis

Nearly optimal sparse fourier transform

Separating multilinear branching programs and formulas

On vertex sparsifiers with Steiner nodes

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

Finding red balloons with split contracts: robustness to individuals' selfishness

Characterizing pseudoentropy and simplifying pseudorandom generator constructions

Improving christofides' algorithm for the s-t path TSP

Complexity of counting CSP with complex weights

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance

Rational proofs

Nearly complete graphs decomposable into large induced matchings and their applications

Many sparse cuts via higher eigenvalues

Multiparty computation secure against continual memory leakage

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Span programs for functions with constant-sized 1-certificates: extended abstract

Online matching with concave returns

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity

A new point of NP-hardness for unique games

Subspace evasive sets

Using petal-decompositions to build a low stretch spanning tree

Budget feasible mechanism design: from prior-free to bayesian

Interactive information complexity

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars

Reconstruction of depth-4 multilinear circuits with top fan-in 2

Approximation algorithms and hardness of integral concurrent flow

Making polynomials robust to noise

An analysis of one-dimensional schelling segregation

Design extractors, non-malleable condensers and privacy amplification

Multiplying matrices faster than coppersmith-winograd

The freezing threshold for k-colourings of a random graph

Tight time-space tradeoff for mutual exclusion

Minimax option pricing meets black-scholes in the limit

Probabilistic existence of rigid combinatorial structures

Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

Beating randomized response on incoherent matrices

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

Hypercontractivity, sum-of-squares proofs, and their applications

Edge transitive ramanujan graphs and symmetric LDPC good codes

Improved smoothed analysis of multiobjective optimization

An algorithmic characterization of multi-dimensional mechanisms

The multiparty communication complexity of set disjointness

Optimal online buffer scheduling for block devices

Affine projections of polynomials: extended abstract

Robust satisfiability of constraint satisfaction problems

A tight RMR lower bound for randomized mutual exclusion

A quantitative gibbard-satterthwaite theorem without neutrality

From query complexity to computational complexity

Matroids and integrality gaps for hypergraphic steiner tree relaxations

Unconditional differentially private mechanisms for linear queries

Strict fibonacci heaps

Optimal private halfspace counting via discrepancy

Tight lower bounds for the online labeling problem

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC '12)

Content Provider	ACM Digital Library
Editor	Pitassi, Toniann Karloff, Howard
Copyright Year	2012
Abstract	The papers in this volume were presented at the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), held in New York, NY, May 20-22, 2012. The Symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). The program committee met on January 27-28, 2012 in Toronto, Ontario, Canada, and selected 90 papers from 303 detailed abstracts submitted. One pair of papers was merged into a single talk, and one paper was withdrawn, resulting in a total of 88 talks presented at the conference, and 89 papers in this proceedings. The submissions were not formally refereed, and many of them represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals. In addition to the regular program, there were several other avenues for research presentations. The program committee invited Michael Kearns to present a tutorial in the morning of May 19, 2012, before the main conference, on the topic of Algorithmic Trading and Computational Finance. In the afternoon of May 19, 2012, STOC hosted four workshops, in the areas of: Computational Sustainability, Algorithms for Distributed and Streaming Data, Algorithms for Memory-Sensitive Computing, and the Unique Games Conjecture and Related Advances. Lastly, many additional papers were presented during a poster session held on the evening of May 20, 2012. From the many outstanding candidates, the STOC program committee selected the following two papers as recipients of the Best Paper Award: "Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds" by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj and Ronald de Wolf, and "The Cell Probe Complexity of Dynamic Range Counting," by Kasper Green Larsen. The latter of these two papers is also the recipient of the Danny Lewin Best Student Paper Award.
ISBN	9781450312455
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-19
Access Restriction	Subscribed
Content Type	Text
Resource Type	Conference Proceedings

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in