首页>外文会议>Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on

Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on

召开年：
召开地：
出版时间：-

会议文集：-

会议论文

热门论文

全部论文

全选（0）

1.Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents

机译：固定数量的商品或代理商在多项式时间内的市场均衡
- 作者：Devanur Nikhil R.;Kannan Ravi
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- algorithm;
- economics;
- equilibrium;
- exact;
- market;
2.Inapproximability for Metric Embeddings into R^d

机译：度量嵌入R ^ d的不可逼近
- 作者：Matousek Jiri;Sidiropoulos Anastasios
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- embeddings;
- hardness;
- inapproximability;
3.Near-Optimal Sparse Recovery in the L1 Norm

机译：L1范数中的近最佳稀疏恢复
- 作者：Indyk Piotr;Ruzic Milan
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- compressed sensing;
- expanders;
- l1 norm;
- sparse recovery;
- streaming algorithms;
4.Matrix Sparsification for Rank and Determinant Computations via Nested Dissection

机译：通过嵌套解剖对矩阵和稀疏度进行行列式和行列式计算
- 作者：Yuster Raphael
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- determinant;
- matrix;
- nested-dissection;
- rank;
5.Succincter

机译：琥珀色
- 作者：Patrascu Mihai
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- arithmetic coding;
- locally decodable;
- succinct data structures;
6.Kakeya Sets, New Mergers and Old Extractors

机译：Kakeya集，新合并和旧提取器
- 作者：Dvir Zeev;Wigderson Avi
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- extractors;
- kakeya;
- mergers;
7.Arithmetic Circuits: A Chasm at Depth Four

机译：算术电路：深度四的鸿沟
- 作者：Agrawal Manindra;Vinay V.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Arithmetic Circuits;
- Circuit Complexity;
- Computational Complexity;
- Depth Reduction;
- Identity Testing;
- Lower Bounds;
8.Lower Bounds for Noisy Wireless Networks using Sampling Algorithms

机译：使用采样算法的嘈杂无线网络的下界
- 作者：Dutta Chinmoy;Radhakrishnan Jaikumar
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- average case lower bound;
- broadcast protocols;
- lower bounds;
- noisy decision tree;
- sampling algorithms;
- wireless networks;
9.A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems

机译：随机约束满足问题的解决复杂性的二分定理
- 作者：Chan Siu On;Molloy Michael
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Davis-Putnam algorithms;
- random constraint satisfaction problems;
- random walks;
- resolution complexity;
10.A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

机译：矩阵值函数的超压缩不等式及其在量子计算和最不发达国家中的应用
- 作者：Ben-Aroya Avraham;Regev Oded;Wolf Ronald de
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Fourier analysis;
- communication complexity;
- hypercontractive inequality;
- locally decodable codes;
- quantum computing;
11.A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

机译：欧氏Steiner森林的多项式时间近似方案
- 作者：Borradaile Glencora;Klein Philip N.;Mathieu Claire
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Euclidean plane;
- Steiner forest;
- approximation algorithm;
- approximation scheme;
12.A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match

机译：近似下邻搜索和部分匹配的下界几何方法
- 作者：Panigrahy Rina;Talwar Kunal;Wieder Udi
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Cell Probe Lower Bounds;
- Geometry;
- Near Neighbor Search;
- Partial Match;
13.A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width

机译：一种将图嵌入任意曲面的简单线性时间算法和有界树宽的图属
- 作者：Kawarabayashi Ken-ichi;Mohar Bojan;Reed Bruce
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Embedding;
- Genus of a graph;
- Linear time algorithm;
- Surface;
- Tree-width;
14.Dynamic Connectivity: Connecting to Networks and Geometry

机译：动态连接：连接到网络和几何
- 作者：Chan Timothy M.;Patrascu Mihai;Roditty Liam
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- dynamic connectivity;
- geometric connectivity;
- intersection graphs;
- range queries;
15.Algorithms for Single-Source Vertex Connectivity

机译：单源顶点连通性算法
- 作者：Chuzhoy Julia;Khanna Sanjeev
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Network Design;
- Vertex Connectivity;
16.Leakage-Resilient Cryptography

机译：防漏密码术
- 作者：Dziembowski Stefan;Pietrzak Krzysztof
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- leakage-resilient;
- side-channel attack;
- stream-cipher;
17.Fast Modular Composition in any Characteristic

机译：任何特性的快速模块化组合
- 作者：Kedlaya Kiran S.;Umans Christopher
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- modular composition;
- multimodular reduction;
- multipoint evaluation;
- polynomial factorization;
18.On the Union of Cylinders in Three Dimensions

机译：关于三维圆柱的并集
- 作者：Ezra Esther
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- 1/r-cuttings;
- Geometric arrangements;
- lower envelope of algebraic surfaces.;
- onion of simply-shaped bodies;
19.Learning Geometric Concepts via Gaussian Surface Area

机译：通过高斯表面积学习几何概念
- 作者：Klivans Adam R.;ODonnell Ryan;Servedio Rocco A.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Agnostic Learning;
- Convex Sets;
- Gaussian Surface Area;
- Gaussians;
- Learning;
- Surface Area;
20.Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums

机译：拓扑图的嵌入：有损不变式，线性化和2和
- 作者：Chakrabarti Amit;Jaffe Alexander;Lee James R.;Vincent Justin
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
21.Computing the Tutte Polynomial in Vertex-Exponential Time

机译：在顶点指数时间内计算Tutte多项式
- 作者：Björklund Andreas;Husfeldt Thore;Kaski Petteri;Koivisto Mikko
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Exact algorithms;
- Potts model;
- Tutte polynomial;
- exponential-time algorithms;
22.Degree Bounded Network Design with Metric Costs

机译：具有度量成本的度界网络设计
- 作者：Chan Yuk Hei;Fung Wai Shing;Lau Lap Chi;Yung Chun Kong
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- approximation algorithm;
- degree bounded;
- edge splitting-off;
- graph connectivity;
- network design;
23.Worst Case to Average Case Reductions for Polynomials

机译：多项式从最坏情况到平均情况的约简
- 作者：Kaufman Tali;Lovett Shachar
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Approximation;
- Average case to Worst case reductions;
- Finite fields;
- Low degree polynomials;
24.Set Covering with our Eyes Closed

机译：闭眼设置遮挡
- 作者：Grandoni Fabrizio;Gupta Anupam;Leonardi Stefano;Miettinen Pauli;Sankowski Piotr;Singh Mohit
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- a-priori approiximation;
- online algorithms;
- stochastic algorithms;
- universal approximatiom;
25.Minimizing Movement in Mobile Facility Location Problems

机译：最大限度地减少移动设施位置问题中的移动
- 作者：Friggstad Zachary;Salavatipour Mohammad R.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
26.Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply

机译：有限供给的一心一意的无羡慕利润最大化问题的近似算法
- 作者：Cheung Maurice;Swamy Chaitanya
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Algorithmic game theory;
- Algorithms;
- Approximation algorithms;
- Envy-free profit-maximization;
- Linear programming;
- Pricing problems;
27.Multi-unit Auctions with Budget Limits

机译：有预算限制的多单位拍卖
- 作者：Dobzinski Shahar;Lavi Ron;Nisan Noam
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
28.Constant-Time Approximation Algorithms via Local Improvements

机译：通过局部改进的恒定时间近似算法
- 作者：Nguyen Huy N.;Onak Krzysztof
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
29.The Unbounded-Error Communication Complexity of Symmetric Functions

机译：对称函数的无界错误通信复杂度
- 作者：Sherstov Alexander A.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- approximation theory;
- communication complexity;
- lower bounds;
- symmetric functions;
30.Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games

机译：匿名游戏中的离散多项式分布和纳什均衡
- 作者：Daskalakis Constantinos;Papadimitriou Christos H.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Anonymous games;
- Multinomial Approximations;
- Nash equilibrium;
- PTAS;
- Stein's Method;
31.Spherical Cubes and Rounding in High Dimensions

机译：高尺寸球形立方体和倒圆角
- 作者：Kindler Guy;ODonnell Ryan;Rao Anup;Wigderson Avi
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Foams;
- Parallel Repetition;
- Rounding;
- Tiling;
32.Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness

机译：斐波那契门的全息算法和硬度的全息降低
- 作者：Cai Jin-Yi;Lu Pinyan;Xia Mingji
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
33.Rounding Parallel Repetitions of Unique Games

机译：舍入唯一游戏的平行重复
- 作者：Barak Boaz;Hardt Moritz;Haviv Ishay;Rao Anup;Regev Oded;Steurer David
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Hellinger distance;
- correlated sampling;
- parallel repetition;
- semidefinite programming;
- unique games;
34.Two Query PCP with Sub-Constant Error

机译：具有次常量错误的两个查询PCP
- 作者：Moshkovitz Dana;Raz Ran
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Label-Cover;
- Probabilistically Checkable Proofs (PCP);
- hardness of approximation;
35.Locally Testing Direct Product in the Low Error Range

机译：在低误差范围内本地测试直接产品
- 作者：Dinur Irit;Goldenberg Elazar
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- direct product;
- list decoding;
- low error;
- property testing;
36.Network Extractor Protocols

机译：网络提取器协议
- 作者：Kalai Yael Tauman;Li Xin;Rao Anup;Zuckerman David
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Extractor;
- Network;
37.On the Hardness of Being Truthful

机译：论诚实的艰辛
- 作者：Papadimitriou Christos;Schapira Michael;Singer Yaron
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
38.Sketching and Streaming Entropy via Approximation Theory

机译：通过近似理论绘制和流熵
- 作者：Harvey Nicholas J.A.;Nelson Jelani;Onak Krzysztof
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Chebyshev polynomials;
- entropy;
- sketching;
- streaming;
39.Submodular Approximation: Sampling-based Algorithms and Lower Bounds

机译：次模逼近：基于采样的算法和下界
- 作者：Svitkina Zoya;Fleischer Lisa
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
40.k-Wise Independent Random Graphs

机译：k明智独立随机图
- 作者：Alon Noga;Nussboim Asaf
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- k-wise independence;
- random graphs;
41.Clock Synchronization with Bounded Global and Local Skew

机译：具有受限全局和局部偏斜的时钟同步
- 作者：Lenzen Christoph;Locher Thomas;Wattenhofer Roger
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- clock synchronization;
- gradient property;
- upper bound;
42.Isotropic PCA and Affine-Invariant Clustering

机译：各向同性PCA和仿射不变聚类
- 作者：Brubaker Spencer Charles;Vempala Santosh
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- clustering;
- mixture models;
- principal components analysis;
43.Mixing Time of Exponential Random Graphs

机译：指数随机图的混合时间
- 作者：Bhamidi Shankar;Bresler Guy;Sly Allan
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- exponential random graphs;
- mixing times;
- path coupling;
- pseudo-random graphs;
44.Hardness of Nearest Neighbor under L-infinity

机译：L无限近邻的硬度
- 作者：Andoni Alexandr;Croitoru Dorian;Patrascu Mihai
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
45.(Data) STRUCTURES

机译：（数据结构
- 作者：Patrascu Mihai
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- cell probe;
- data structures;
- lower bounds;
- range queries;
46.Entangled Games are Hard to Approximate

机译：纠结的游戏很难估计
- 作者：Kempe Julia;Kobayashi Hirotada;Matsumoto Keiji;Toner Ben;Vidick Thomas
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- entanglement;
- hardness;
- quantum games;
- quantum interactive proofs;
47.(Acyclic) Job Shops are Hard to Approximate

机译：（非周期性）作业车间很难估算
- 作者：Mastrolilli Monaldo;Svensson Ola
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Approximation;
- Hardness;
- Scheduling;
48.Linear Level Lasserre Lower Bounds for Certain k-CSPs

机译：某些k-CSP的线性水平Lasserre下界
- 作者：Schoenebeck Grant
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Lasserre;
- semidefinite program hierarchies;
49.Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

机译：简短的证明可能很宽敞：分辨率上空间和长度的最佳分离
- 作者：Ben-Sasson Eli;Nordström Jakob
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Proof complexity;
- pebbling games;
- resolution;
- space complexity;
50.Hardness of Minimizing and Learning DNF Expressions

机译：最小化和学习DNF表达的难度
- 作者：Khot Subhash;Saket Rishi
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Approximation;
- DNF;
- Hardness;
- Learning;
51.On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations

机译：基于身份的加密在活板门置换中的不可能
- 作者：Boneh Dan;Papakonstantinou Periklis;Rackoff Charles;Vahlis Yevgeniy;Waters Brent
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
52.Approximate Kernel Clustering

机译：近似内核聚类
- 作者：Khot Subhash;Naor Assaf
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Approximation algorithm;
- clustering;
- inapproximability;
53.Broadcasting with Side Information

机译：附带信息广播
- 作者：Alon Noga;Lubetzky Eyal;Stav Uri;Weinstein Amit;Hassidim Avinatan
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Index coding;
- Network coding;
- Source coding on demand;
54.The Sign-Rank of AC^O

机译：AC ^ O的符号等级
- 作者：Razborov Alexander A.;Sherstov Alexander A.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
55.On Basing Lower-Bounds for Learning on Worst-Case Assumptions

机译：基于最坏情况假设的下界学习
- 作者：Applebaum Benny;Barak Boaz;Xiao David
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
56.Some Results on Greedy Embeddings in Metric Spaces

机译：度量空间中贪婪嵌入的一些结果
- 作者：Moitra Ankur;Leighton Tom
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- circuit graph;
- excluded minor;
- greedy routing;
57.On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

机译：关于近似频率矩的多个读/写流的值
- 作者：Beame Paul;Huynh-Ngoc Dang-Trinh
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Communication Complexity;
- Data Streams;
- Frequency Moments;
- Lower Bounds;
58.Nearly Tight Low Stretch Spanning Trees

机译：几乎紧的低伸跨度树木
- 作者：Abraham Ittai;Bartal Yair;Neiman Ofer
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- spanning tree low stretch;
59.The Power of Reordering for Online Minimum Makespan Scheduling

机译：在线最小订货量计划的重新排序功能
- 作者：Englert Matthias;Özmen Deniz;Westermann Matthias
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- competitive analysis;
- minimum makespan scheduling;
- online algorithms;
- reordering buffers;
60.Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes

机译：函数噪声相关的高斯界和长码的紧密分析
- 作者：Mossel Elchanan
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Condorcet voting;
- long codes;
- majority;
- predictability;
- unique games;
- invariance;
61.On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

机译：亚模块化福利最大化和GAP的预算分配和改进的下界的近似性
- 作者：Chakrabarty Deeparnab;Goel Gagan
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Allocation;
- Approximation Algorithms;
62.Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time

机译：中等指数时间内低秩超图的同构
- 作者：Babai Laszlo;Codenotti Paolo
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- algorithm;
- graph isomorphism;
- hypergraph;
- moderately exponential;
- permutation groups;
63.What Can We Learn Privately?

机译：我们可以私下学习什么？
- 作者：Kasiviswanathan Shiva Prasad;Lee Homin K.;Nissim Kobbi;Raskhodnikova Sofya;Smith Adam
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Database Privacy;
- Learning Theory;
- PAC Learning;
64.Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

机译：多线性公式，最大分区差异和混合源提取器
- 作者：Raz Ran;Yehudayoff Amir
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Discrepancy;
- Extractors;
- Lower Bounds;
65.Dense Subsets of Pseudorandom Sets

机译：伪随机集的密集子集
- 作者：Reingold Omer;Trevisan Luca;Tulsiani Madhur;Vadhan Salil
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- additive combinatorics;
- pseudoentropy;
- pseudorandomness;
- regularity lemmas;
66.Truthful Approximation Schemes for Single-Parameter Agents

机译：单参数智能体的真实逼近方案
- 作者：Dhangwatnotai Peerapong;Dobzinski Shahar;Dughmi Shaddin;Roughgarden Tim
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Algorithmic Mechanism Design;
- Approximation Algorithms;
- Monotone Algorithms;
- Scheduling;
- Single Parameter Agents;
67.Unique Games with Entangled Provers are Easy

机译：纠缠不清的独特游戏非常简单
- 作者：Kempe Julia;Regev Oded;Toner Ben
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
68.Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners

机译：浅低光树和欧氏扳手的紧下界
- 作者：Dinitz Yefim;Elkin Michael;Solomon Shay
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Computational Geometry;
- Euclidean Spanners;
- Low-Distortion Embeddings;
- Spanners;
69.Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph

机译：打破随机排序很难：最大无环子图的不可逼近性
- 作者：Guruswami Venkatesan;Manokaran Rajsekar;Raghavendra Prasad
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- feedback arc set;
- hardness of approximation;
- integrality gaps;
- maximum acyclic subgraph;
- unique games conjecture;
70.Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows

机译：特征值边界，谱分割和通过流的度量变形
- 作者：Biswal Punyashloka;Lee James R.;Rao Satish
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
71.The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)

机译：贝叶斯学习器对于嘈杂的二进制搜索是最佳的（对于量子也非常好）
- 作者：Ben-Or Michael;Hassidim Avinatan
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- algorithms;
- binary search;
- noise;
- quantum search;
- search;
72.Noise Tolerance of Expanders and Sublinear Expander Reconstruction

机译：扩展器的噪声容限和亚线性扩展器重构
- 作者：Kale Satyen;Peres Yuval;Seshadhri C.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Expander reconstruction;
- Random Walks;
- Sublinear algorithms;
73.Algorithmic Barriers from Phase Transitions

机译：相变带来的算法障碍
- 作者：Achlioptas Dimitris;Coja-Oghlan Amin
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Algorithms;
- Phase Transitions;
- Random Constraint Satisfaction Problems;
74.Size Bounds and Query Plans for Relational Joins

机译：关系联接的大小范围和查询计划
- 作者：Atserias Albert;Grohe Martin;Marx Dániel
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
75.Quantum Multi Prover Interactive Proofs with Communicating Provers

机译：具有通信证明的Quantum Multi Prover交互式证明
- 作者：Or Michael Ben;Hassidim Avinatan;Pilpel Haran
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- interactive proofs;
- multi prover;
- quantum;
76.Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier

机译：基于距离的系统发育重建的序列长度要求：打破多项式障碍
- 作者：Roch Sébastien
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
77.A Counterexample to Strong Parallel Repetition

机译：强并行重复的反例
- 作者：Raz Ran
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
78.Average-case Complexity

机译：平均情况复杂度
- 作者：Trevisan Luca
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
79.The Polynomial Method in Quantum and Classical Computing

机译：量子和经典计算中的多项式方法
- 作者：Aaronson Scott
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- polynomial method;
- quantum;
80.Elections Can be Manipulated Often

机译：经常可以操纵选举
- 作者：Friedgut Ehud;Kalai Gil;Nisan Noam
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- Computational game theory;
- elections;
- social choice;
81.Almost-Natural Proofs

机译：几乎自然的证明
- 作者：Chow Timothy Y.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》
- circuit complexity;
- natural proofs;
- naturalization barrier;
- pseudorandom number generators;
82.Theory of Sponsored Search Auctions

机译：赞助搜索拍卖理论
- 作者：Aggarwal Gagan;Muthukrishnan S.
- 会议名称：《Foundations of Computer Science, FOCS, 2008 IEEE 49th Annual Symposium on》