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

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

Robust pcps of proximity, shorter pcps and applications to coding

On the performance of greedy algorithms in packet buffering

Approximating the cut-norm via Grothendieck's inequality

Dictionary matching and indexing with errors and don't cares

Graph entropy and quantum sorting problems

Approximation algorithm for k-node connected subgraphs via critical graphs

Approximation algorithms for deadline-TSP and vehicle routing with time-windows

Using nondeterminism to amplify hardness

Bounded-concurrent secure multi-party computation with a dishonest majority

Low distortion maps between point sets

Hit-and-run from a corner

Collective asynchronous reading with polylogarithmic worst-case overhead

Typical properties of winners and losers in discrete optimization

Algorithms for dynamic geometric problems over data streams

An approximate König's theorem for edge-coloring weighted bipartite graphs

Derandomizing homomorphism testing in general groups

Counting complexity classes for numeric computations II: algebraic and semialgebraic sets

Auction algorithms for market equilibrium

Lower bounds for dynamic connectivity

A decentralized algorithm for spectral analysis

Sharp thresholds For monotone properties in random geometric graphs

The complexity of pure Nash equilibria

Quantum algorithms a decade after shor

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection

Adaptive routing with end-to-end feedback: distributed learning and geometric approaches

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

Sorting and searching in the presence of memory faults (without redundancy)

Multilinear formulas and skepticism of quantum computing

Solving fractional packing problems in $O^{ast}(1/ε)$ iterations

Estimating the weight of metric minimum spanning trees in sublinear-time

Visibly pushdown languages

New notions of security: achieving universal composability without trusted setup

Bypassing the embedding: algorithms for low dimensional metrics

A simple polynomial-time rescaling algorithm for solving linear programs

Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem

Primal-dual algorithms for deterministic inventory problems

Sublinear algorithms for testing monotone and unimodal distributions

Finding paths and cycles of superpolylogarithmic length

Better extractors for better codes?

A conjecture about polynomial time computable lattice-lattice functions

The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results

Lower bounds for linear degeneracy testing

Using mixture models for collaborative filtering

The two possible values of the chromatic number of a random graph

Computing Nash equilibria for scheduling on restricted parallel links

Expander flows, geometric embeddings and graph partitioning

Asymmetric k-center is $log^{*}$ n-hard to approximate

Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks

Exponential separation of quantum and classical one-way communication complexity

The all-or-nothing multicommodity flow problem

A fully dynamic reachability algorithm for directed graphs with an almost linear update time

Linear FPT reductions and computational lower bounds

Completeness in two-party secure computation: a computational view

On coresets for k-means and k-median clustering

Multi-processor scheduling to minimize flow time with ε resource augmentation

The difficulty of testing for isomorphism against a graph that is given in advance

Boosted sampling: approximation algorithms for stochastic optimization

A new family of Cayley expanders (?)

Quantum and classical query complexities of local search are polynomially related

(Almost) tight bounds and existence theorems for confluent flows

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph

Rational secret sharing and multiparty computation: extended abstract

New hardness results for congestion minimization and machine scheduling

The zero-one principle for switching networks

Batch codes and their applications

Isotopic implicit surface meshing

The quantum adiabatic optimization algorithm and local minima

Approximate max-integral-flow/min-multicut theorems

Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus

Lower bounds for local search by quantum arguments

Depth through breadth, or why should we attend talks in other areas?

Multi-linear formulas for permanent and determinant are of super-polynomial size

Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC '04)

Content Provider	ACM Digital Library
Editor	Babai, László
Copyright Year	2004
Abstract	The papers in this volume were presented at the Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2004), held in Chicago, Illinois, June 13-15, 2004. The Symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT).In response to a Call For Papers, posted at a University of Chicago website, 271 submissions were received by the submission deadline of November 5, 4:59pm EST. All were submitted electronically on the Microsoft Conference Management Toolkit (CMT) website.The Program Committee began its deliberations electronically on December 10, and continued in that medium until its meeting in New Orleans, Louisiana, on January 9 and 10. Electronic discussion of unresolved issues continued for some weeks after the meeting.The CMT website was used for paper submission and initial posting of reviews and comments; most of the discussion was conducted and coordinated on a University of Chicago website using software produced by Daniel Tefankovic and tailored to the needs of the PC.The Program Committee selected 71 papers for presentation; one was later withdrawn.The submissions were not refereed, and many of these papers represented reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals.The papers encompass a wide variety of areas of theoretical computer science, ranging from classical problems in algorithms and complexity theory (including lower bounds, graph algorithms, network flows, cryptography, random structures, inapproximabilty/PCPs), to heavily represented emerging areas and models such as quantum computing and algorithmic game theory. A number of additional areas of traditional or more recent interest to the SIGACT community are represented by one or two papers each; these include: distributed computing, computational geometry/topology, mathematical algorithms, metric spaces/embeddings, data mining, analysis of data streams, property testing.In addition to the contributed talks, the program included three invited plenary talks, represented by brief abstracts in this volume: Quantum Algorithms a Decade After Shor, by Andris Ambainis (see page 111); Network Games, by Eva Tardos (see page 341); and Depth Through Breadth, or Why Should We Attend Talks In Other Areas?, by Avi Wigderson (see page 579).The Program Committee would like to thank all authors who submitted papers for consideration. The PC also wishes to thank the large number of members of the community who assisted the PC in assessing the merits of the submissions (see "Reviewers," page xii).The PC is grateful to Microsoft Research and to the CMT Web Support staff for providing the web-site and assisting with its use.
ISBN	1581138520
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-06-13
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