NDLI: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC '05)

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

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors

Approximation techniques for utilitarian mechanism design

On lattices, learning with errors, random linear codes, and cryptography

On dynamic range reporting in one dimension

Beyond NP: the work and legacy of Larry Stockmeyer

Every monotone graph property is testable

Approximation algorithms for network design with metric costs

Optimal approximations of the frequency moments of data streams

Tree-walking automata do not recognize all regular languages

Simple PCPs with poly-log rate and query complexity

Computing the first Betti number and the connected components of semi-algebraic sets

The round complexity of two-party random selection

Learning with attribute costs

Undirected ST-connectivity in log-space

Universal approximations for TSP, Steiner tree, and set cover

Spectral norm of random matrices

Tensor norms and the classical communication complexity of nonlocal quantum measurement

Quadratic forms on graphs

Covert two-party computation

Euclidean distortion and the sparsest cut

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits

Approximation algorithms for combinatorial auctions with complement-free bidders

An O(log n log log n) space algorithm for undirected st-connectivity

The complexity of agreement

A new strategy for querying priced information

From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement

Every 2-CSP allows nontrivial approximation

Extractors with weak random seeds

Computing correlated equilibria in multi-player games

Representing hard lattices with O(n log n) bits

Worst-case update times for fully-dynamic all-pairs shortest paths

Testing versus estimation of graph properties

On non-uniform multicommodity buy-at-bulk network design

Coresets in dynamic geometric data streams

Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read

Hardness of the undirected edge-disjoint paths problem

Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities

Hierarchies for semantic classes

Learning nonsingular phylogenies and hidden Markov models

Saving an epsilon: a 2-approximation for the k-MST problem in graphs

On random pm 1 matrices: singularity and determinant

Fast quantum algorithms for computing the unit group and class group of a number field

Lower-stretch spanning trees

On obfuscating point functions

Improved approximation algorithms for minimum-weight vertex separators

Limits to list decoding Reed-Solomon codes

Derandomization of auctions

Concurrent general composition of secure protocols in the timing model

Aggregating inconsistent information: ranking and clustering

An optimal multi-writer snapshot algorithm

Tensor decomposition and approximation schemes for constraint satisfaction problems

Pseudorandom generators for low degree polynomials

The Price of Routing Unsplittable Flow

Testing monotone high-dimensional distributions

Multicommodity flow, well-linked terminals, and routing problems

Low distortion embeddings for edit distance

Lower bounds for k-DNF resolution on random 3-CNFs

Hardness of the undirected congestion minimization problem

On algorithms for discrete and approximate brouwer fixed points

The mixing time of the thorp shuffle

On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem

Polynomial time quantum algorithm for the computation of the unit group of a number field

Edge partition of planar sraphs into two outerplanar graphs

New and improved constructions of non-malleable cryptographic protocols

O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

Correcting errors without leaking partial information

On the bias of traceroute sampling: or, power-law degree distributions in regular graphs

Cooperative asynchronous update of shared memory

On strip packing With rotations

On uniform amplification of hardness in NP

The price of anarchy of finite congestion games

Efficient testing of groups

Oblivious routing in directed graphs with random demands

Low-distortion embeddings of general metrics into the line

Bounded-depth circuits: separating wires from gates

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Convex programming for scheduling unrelated parallel machines

Approximately counting integral flows and cell-bounded contingency tables

Towards asymptotic optimality in probabilistic packet marking

Fast quantum byzantine agreement

Collusion-free protocols

Balanced metric labeling

Key agreement from weak bit agreement

How to spread adversarial nodes?: rotate!

Market equilibrium via the excess demand function

Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC '05)

Content Provider	ACM Digital Library
Editor	Kumar, Ravi Gupta, Anupam Kalai, Adam Tauman Impagliazzo, Russell Fagin, Ronald O'Donnell, Ryan Jain, Kanal Ta-Shma, Amnon Gabow, Hal Dwork, Cynthia Cai, Jin-Yi Khot, Subhash Kenyon, Claire Sinclair, Alistair Har-Peled, Sariel Karger, David Roughgarden, Tim
Copyright Year	2005
Abstract	The papers in this volume were presented at the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2005), held in Baltimore, Maryland, May 22-24, 2005. The Symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT).On May 21, the day before STOC, there was a commemoration of Larry Stockmeyer, who died on July 31, 2004. For this tribute, which was organized by Tutorials Chair Cynthia Dwork, there was a tutorial by Nicholas Pippenger on some of Stockmeyer's fundamental results in complexity theory, followed by lectures by Miklos Ajtai, Anne Condon, Cynthia Dwork, Richard Karp, Albert Meyer, and Christopher Umans. On the following day, Lance Fortnow continued the tribute with an invited talk and paper, which appears in these proceedings, on the work and legacy of Larry Stockmeyer.In response to a Call for Papers, 290 submissions were received by the submission deadline of November 4, 2004, 5:59pm EST. All were submitted electronically on the ACM SIGACT server website. One paper was a duplicate, and four papers were eventually withdrawn.The Program Committee began its deliberations electronically on January 4, and continued in that medium until its meeting at the IBM Almaden Research Center, San Jose, California, on January 21-22, where all final decisions were made. Of the 21 Program Committee members, 19 attended the Program Committee meeting in San Jose, and the other two participated through a full-time conference call.The Program Committee selected 84 papers for presentation. The paper "Undirected ST-Connectivity in Log-Space", by Omer Reingold, was selected for the STOC Best Paper Award. The paper "A O(log n log log n) Space Algorithm for Undirected Connectivity", by Vladimir Trifonov, was selected for the Danny Lewin Best Student Paper Award.The submissions were not refereed, and many of these papers represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals.
ISBN	1581139608
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-05-22
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