Zero Knowledge with Efficient Provers (English)
- New search for: Nguyen, M.-H.
- New search for: Vadhan, S.
- New search for: ACM Special Interest Group for Algorithms and Computation Theory
- New search for: Nguyen, M.-H.
- New search for: Vadhan, S.
- New search for: ACM Special Interest Group for Algorithms and Computation Theory
In:
Theory of computing; STOC'06
;
287-295
;
2006
-
ISBN:
- Conference paper / Print
-
Title:Zero Knowledge with Efficient Provers
-
Contributors:Nguyen, M.-H. ( author ) / Vadhan, S. ( author ) / ACM Special Interest Group for Algorithms and Computation Theory
-
Conference:38th:; Annual ACM Symposium, Theory of computing; STOC'06 ; 2006 ; Seattle, WA
-
Published in:Theory of computing; STOC'06 ; 287-295
-
Publisher:
- New search for: ACM Press,
-
Publication date:2006-01-01
-
Size:9 pages
-
ISBN:
-
Type of media:Conference paper
-
Type of material:Print
-
Language:English
-
Keywords:
-
Source:
© Metadata Copyright the British Library Board and other contributors. All rights reserved.
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Explicit Capacity-Achieving List-Decodable Codes OR Decoding up to the Singleton Bound using Folded Reed-Solomon CodesGuruswami, V. / Rudra, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 11
-
Gowers Uniformity, Influence of Variables, and PCPsSamorodnitsky, A. / Trevisan, L. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 21
-
Sub-Constant Error Low Degree Test of Almost-Linear SizeMoshkovitz, D. / Raz, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 31
-
The Santa Claus ProblemBansal, N. / Sviridenko, M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 41
-
On Maximizing Welfare when Utility Functions are SubadditiveFeige, U. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 51
-
A Randomized Polynomial-Time Simplex Algorithm for Linear ProgrammingKelner, J. A. / Spielman, D. A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 61
-
Reducibility Among Equilibrium ProblemsGoldberg, P. W. / Papadimitriou, C. H. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 71
-
The Complexity of Computing a Nash EquilibriumDaskalakis, C. / Goldberg, P. W. / Papadimitriou, C. H. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 79
-
New Trade-Offs in Cost-Sharing MechanismsRoughgarden, T. / Sundararajan, M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 89
-
The Effect of Collusion in Congestion GamesHayrapetyan, A. / Tardos, E. / Wexler, T. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 99
-
Black-Box Constructions for Secure ComputationIshai, Y. / Kushilevitz, E. / Lindell, Y. / Petrank, E. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 109
-
Information-Theoretically Secure Protocols and Security Under CompositionKushilevitz, E. / Lindell, Y. / Rabin, T. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 119
-
Private Approximation of Search ProblemsBeimel, A. / Carmi, P. / Nissim, K. / Weinreb, E. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 129
-
Invited Talk: The Changing Face of Web Search: Algorithms, Auctions and AdvertisingRaghavan, P. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 130
-
On the Solution-Space Geometry of Random Constraint Satisfaction ProblemsAchlioptas, D. / Ricci-Tersenghi, F. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 140
-
Counting Independent Sets up to the Tree ThresholdWeitz, D. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 150
-
The DLT Priority Sampling is Essentially OptimalSzegedy, M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 159
-
Optimal Phylogenetic ReconstructionDaskalakis, C. / Mossel, E. / Roch, S. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 169
-
Time-Space Tradeoffs for Implementations of SnapshotsFatourou, P. / Fich, F. E. / Ruppert, E. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 179
-
Byzantine Agreement in the Full-Information Model in O(log n) RoundsBen-Or, M. / Pavlov, E. / Vaikuntanathan, V. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 187
-
Fast Leader-Election Protocols with Bounded Cheaters' EdgeAntonakopoulos, S. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 197
-
Pricing for Fairness: Distributed Resource Allocation for Multiple ObjectivesCho, S.-w. / Goel, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 205
-
Near-Optimal Algorithms for Unique GamesCharikar, M. / Makarychev, K. / Makarychev, Y. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 215
-
New Approximation Guarantee for Chromatic NumberArora, S. / Chlamtac, E. / Charikar, M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 225
-
Finding a Maximum Weight Triangle in n^3^-^d^e^l^t^a Time, With ApplicationsVassilevska, V. / Williams, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 232
-
Time-Space Trade-Offs for Predecessor SearchPatrascu, M. / Thorup, M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 241
-
The PCP Theorem by Gap AmplificationDinur, I. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 251
-
A Combinatorial Characterization of the Testable Graph Properties: It's All About RegularityAlon, N. / Fischer, E. / Newman, I. / Shapira, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 261
-
Graph Limits and Parameter TestingBorgs, C. / Chayes, J. / Lovasz, L. / Sos, V. T. / Szegedy, B. / Vesztergombi, K. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 271
-
Advances in Metric Embedding TheoryAbraham, I. / Bartal, Y. / Neiman, O. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 287
-
Zero Knowledge with Efficient ProversNguyen, M.-H. / Vadhan, S. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 296
-
Zero-Knowledge Against Quantum AttacksWatrous, J. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 306
-
Local Zero KnowledgeMicali, S. / Pass, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 316
-
A Quasi-Polynomial Time Approximation Scheme for Minimum Weight TriangulationRemy, J. / Steger, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 326
-
Building Triangulations Using epsilon-NetsClarkson, K. L. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 336
-
The Distance Trisector CurveAsano, T. / Matousek, J. / Tokuyama, T. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 344
-
Conditional Hardness for Approximate ColoringDinur, I. / Mossel, E. / Regev, O. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 354
-
Clique-width Minimization is NP-hardFellows, M. R. / Rosamond, F. A. / Rotics, U. / Szeider, S. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 363
-
Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership QueriesFeldman, V. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 373
-
Can Every Randomized Algorithm be Derandomized?Impagliazzo, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 375
-
Finding Small Balanced SeparatorsFeige, U. / Mahdian, M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 385
-
Graph Partitioning using Single Commodity FlowsKhandekar, R. / Rao, S. / Vazirani, U. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 391
-
Linear Time Low Tree-width Partitions and Algorithmic ConsequencesNesetril, J. / de Mendez, P. O. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 401
-
Approximating the List-Chromatic Number and the Chromatic Number in Minor-Closed and Odd-Minor-Closed Classes of GraphsKawarabayashi, K.-i. / Mohar, B. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 417
-
Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures: Sharper Bounds, Simpler Proofs and Algorithmic ApplicationsGurvits, L. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 427
-
A Polynomial Quantum Algorithm for Approximating the Jones PolynomialAharonov, D. / Jones, V. / Landau, Z. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 437
-
On the Fourier Tails of Bounded Functions over the Discrete CubeDinur, I. / Friedgut, E. / Kindler, G. / O Donnell, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 447
-
Lattice Problems and Norm EmbeddingsRegev, O. / Rosen, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 457
-
Pseudorandom Walks on Regular Digraphs and the RL vs. L ProblemReingold, O. / Trevisan, L. / Vadhan, S. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 467
-
An Efficient Algorithm for Solving Word EquationsPlandowski, W. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 477
-
Online Trading Algorithms and Robust Option PricingDeMarzo, P. / Kremer, I. / Mansour, Y. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 487
-
On Adequate Performance Measures for PagingPanagiotou, K. / Souza, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 497
-
Extractors for a Constant Number of Polynomially Small Min-Entropy Independent SourcesRao, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 507
-
Narrow Proofs May Be Spacious: Separating Space and Width in ResolutionNordstrom, J. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 517
-
Logarithmic Hardness of the Directed Congestion Minimization ProblemAndrews, M. / Zhang, L. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 527
-
Hardness of Cut Problems in Directed GraphsChuzhoy, J. / Khanna, S. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 537
-
Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement ProblemsDevanur, N. R. / Khot, S. A. / Saket, R. / Vishnoi, N. K. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 547
-
On Earthmover Distance, Metric Labeling, and 0-ExtensionKarloff, H. / Khot, S. / Mehta, A. / Rabani, Y. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 557
-
Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss TransformAilon, N. / Chazelle, B. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 564
-
On the Importance of IdempotenceArya, S. / Malamatos, T. / Mount, D. M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 574
-
Searching Dynamic Point Sets in Spaces with Bounded Doubling DimensionCole, R. / Gottlieb, L.-A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 584
-
Learning a Circuit by Injecting ValuesAngluin, D. / Aspnes, J. / Chen, J. / Wu, Y. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 594
-
Bounded-Error Quantum State Identification and Exponential Separations in Communication ComplexityGavinsky, D. / Kempe, J. / Regev, O. / de Wolf, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 604
-
Limitations of Quantum Coset States for Graph IsomorphismHallgren, S. / Moore, C. / Rotteler, M. / Russell, A. / Sen, P. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 618
-
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space TradeoffsAmbainis, A. / Spalek, R. / de Wolf, R. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 634
-
New Upper and Lower Bounds for Randomized and Quantum Local SearchZhang, S. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 644
-
Truthful Randomized Mechanisms for Combinatorial AuctionsDobzinski, S. / Nisan, N. / Schapira, M. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 653
-
Fast Convergence to Wardrop Equilibria by Adaptive Sampling MethodsFischer, S. / Racke, H. / Vocking, B. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 663
-
Simple Cost Sharing Schemes for Multicommodity Rent-or-Buy and Stochastic Steiner TreeFleischer, L. / Konemann, J. / Leonardi, S. / Schafer, G. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 671
-
2-Source Dispersers for Sub-Polynomial Entropy and Ramsey Graphs Beating the Frankl-Wilson ConstructionBarak, B. / Rao, A. / Shaltiel, R. / Wigderson, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 681
-
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic NumberZuckerman, D. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 691
-
Deterministic Extractors For Small-Space SourcesKamp, J. / Rao, A. / Vadhan, S. / Zuckerman, D. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 701
-
On Basing One-Way Functions on NP-HardnessAkavia, A. / Goldreich, O. / Goldwasser, S. / Moshkovitz, D. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 711
-
On the Randomness Complexity of Efficient SamplingDubrov, B. / Ishai, Y. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 721
-
A Quasi-PTAS for Unsplittable Flow on Line GraphsBansal, N. / Chakrabarti, A. / Epstein, A. / Schieber, B. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 730
-
Minimizing Average Flow Time on Related MachinesGarg, N. / Kumar, A. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 739
-
Provably Near-Optimal Sampling-Based Algorithms for Stochastic Inventory Control ModelsLevi, R. / Roundy, R. O. / Shmoys, D. B. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 749
-
A Subset Spanner for Planar Graphs, with Application to Subset TSPKlein, P. N. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006
- 757
-
Edge-Disjoint Paths in Planar Graphs with Constant CongestionChekuri, C. / Khanna, S. / Shepherd, F. B. / ACM Special Interest Group for Algorithms and Computation Theory et al. | 2006