掌桥科研
一站式科研服务平台
科技查新
收录引用
专题文献检索
外文数据库（机构版）
更多产品
首页
成为会员
我要充值
退出
我的积分：
中文会员
开通
中文文献批量获取
外文会员
开通
外文文献批量获取
我的订单
会员中心
我的包量
我的余额
登录/注册
文献导航
中文期刊
>
中文会议
>
中文学位
>
中国专利
>
外文期刊
>
外文会议
>
外文学位
>
外国专利
>
外文OA文献
>
外文科技报告
>
中文图书
>
外文图书
>
工业技术
基础科学
医药卫生
农业科学
教科文艺
经济财政
社会科学
哲学政法
其他
工业技术
基础科学
医药卫生
农业科学
教科文艺
经济财政
社会科学
哲学政法
其他
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
材料科学
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
马克思主义、列宁主义、毛泽东思想、邓小平理论
哲学、宗教
社会科学总论
政治、法律
军事
经济
文化、科学、教育、体育
语言、文字
文学
艺术
历史、地理
自然科学总论
数理科学和化学
天文学、地球科学
生物科学
医药、卫生
农业科学
工业技术
交通运输
航空、航天
环境科学、安全科学
综合性图书
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
材料科学
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
材料科学
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
美国国防部AD报告
美国能源部DE报告
美国航空航天局NASA报告
美国商务部PB报告
外军国防科技报告
美国国防部
美国参联会主席指示
美国海军
美国空军
美国陆军
美国海军陆战队
美国国防技术信息中心(DTIC)
美军标
美国航空航天局(NASA)
战略与国际研究中心
美国国土安全数字图书馆
美国科学研究出版社
兰德公司
美国政府问责局
香港科技大学图书馆
美国海军研究生院图书馆
OALIB数据库
在线学术档案数据库
数字空间系统
剑桥大学机构知识库
欧洲核子研究中心机构库
美国密西根大学论文库
美国政府出版局（GPO）
加利福尼亚大学数字图书馆
美国国家学术出版社
美国国防大学出版社
美国能源部文献库
美国国防高级研究计划局
美国陆军协会
美国陆军研究实验室
英国空军
美国国家科学基金会
美国战略与国际研究中心-导弹威胁网
美国科学与国际安全研究所
法国国际关系战略研究院
法国国际关系研究所
国际宇航联合会
美国防务日报
国会研究处
美国海运司令部
北约
盟军快速反应部队
北约浅水行动卓越中心
北约盟军地面部队司令部
北约通信信息局
北约稳定政策卓越中心
美国国会研究服务处
美国国防预算办公室
美国陆军技术手册
一般OA
科技期刊论文
科技会议论文
图书
科技报告
科技专著
标准
其它
美国卫生研究院文献
分子生物学
神经科学
药学
外科
临床神经病学
肿瘤学
细胞生物学
遗传学
公共卫生&环境&职业病
应用微生物学
全科医学
免疫学
动物学
精神病学
兽医学
心血管
放射&核医学&医学影像学
儿科
医学进展
微生物学
护理学
生物学
牙科&口腔外科
毒理学
生理学
医院管理
妇产科学
病理学
生化技术
胃肠&肝脏病学
运动科学
心理学
营养学
血液学
泌尿科学&肾病学
生物医学工程
感染病
生物物理学
矫形
外周血管病
药物化学
皮肤病学
康复学
眼科学
行为科学
呼吸学
进化生物学
老年医学
耳鼻喉科学
发育生物学
寄生虫学
病毒学
医学实验室检查技术
生殖生物学
风湿病学
麻醉学
危重病护理
生物材料
移植
医学情报
其他学科
人类生活必需品
作业；运输
化学；冶金
纺织；造纸
固定建筑物
机械工程；照明；加热；武器；爆破
物理
电学
人类生活必需品
作业；运输
化学；冶金
纺织；造纸
固定建筑物
机械工程；照明；加热；武器；爆破
物理
电学
马克思主义、列宁主义、毛泽东思想、邓小平理论
哲学、宗教
社会科学总论
政治、法律
军事
经济
文化、科学、教育、体育
语言、文字
文学
艺术
历史、地理
自然科学总论
数理科学和化学
天文学、地球科学
生物科学
医药、卫生
农业科学
工业技术
交通运输
航空、航天
环境科学、安全科学
综合性图书
主题
主题
题名
作者
关键词
摘要
高级搜索 >
外文期刊
外文会议
外文学位
外国专利
外文图书
外文OA文献
中文期刊
中文会议
中文学位
中国专利
中文图书
外文科技报告
清除
历史搜索
清空历史
首页
>
外文会议
>
Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
召开年：
2004
召开地：
出版时间：
-
会议文集：
-
会议论文
热门论文
全部论文
全选（
0
）
清除
导出
1.
Dynamic optimality - almost competitive online binary search tree
机译：
动态最优-几乎竞争性在线二进制搜索树
作者：
Demaine E.D.
;
Harmon D.
;
Iacono J.
;
Patrascu M.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
optimisation;
computational complexity;
trees (mathematics);
dynamic optimality;
competitive online binary search tree;
2.
Maximizing quadratic programs: extending Grothendieck's inequality
机译：
最大化二次程序：扩展Grothendieck不等式
作者：
Charikar M.
;
Wirth A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
quadratic programming;
computational complexity;
relaxation theory;
approximation theory;
correlation methods;
Grothendieck inequality;
quadratic programming;
approximation algorithm;
canonical semidefinite relaxation;
maximum correlation;
correlation clustering;
MAXCUT problem;
random assignment;
3.
On the integrality ratio for asymmetric TSP
机译：
关于不对称TSP的积分比
作者：
Charikar M.
;
Goemans M.X.
;
Karloff H.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
travelling salesman problems;
integrality ratio;
asymmetric TSP;
Held-Karp bound;
triangle inequality;
travelling salesman problem;
4.
On the list and bounded distance decodibility of Reed-Solomon codes
机译：
关于Reed-Solomon码的列表和有界距离可解码性
作者：
Qi Cheng
;
Daqing Wan
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
Reed-Solomon codes;
decoding;
public key cryptography;
randomised algorithms;
bounded distance decodibility;
Reed-Solomon codes;
error-correcting code;
distance bound;
list decoding problem;
bounded distance decoding problem;
public key cryptosystem;
discrete logarithm problem;
randomized algorithm;
Katz theorem;
5.
The hardness of metric labeling
机译：
公制标签的硬度
作者：
Chuzhoy J.
;
Naor J.S.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
graph theory;
computational complexity;
approximation theory;
metric labeling;
mathematical model;
classification problems;
weighted graph;
metric distance function;
assignment cost;
minimum-cost assignment;
separation costs;
distance functions;
logarithmic approximation;
quasi-polynomial time algorithm;
6.
Maximum matchings via Gaussian elimination
机译：
通过高斯消除进行最大匹配
作者：
Mucha M.
;
Sankowski P.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
randomised algorithms;
graph theory;
matrix multiplication;
Gaussian processes;
maximum matching;
Gaussian elimination;
randomized algorithm;
bipartite graphs;
matrix multiplication;
bipartite matching algorithm;
Lovasz randomized technique;
perfect matching;
7.
No sorting? Better searching! optimal array organization
机译：
没有排序？更好的搜索！ 最佳阵列组织
作者：
Franceschini G.
;
Grossi R.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
computational complexity;
arrays;
data structures;
search problems;
key sorting;
array organization;
multidimensional keys;
array searching complexity;
ordered alphabet;
data organization;
character comparisons;
algorithmics;
unsorted array ordering;
8.
Randomly coloring constant degree graphs
机译：
随机着色恒定度图
作者：
Dyer M.
;
Frieze A.
;
Hayes T.P.
;
Vigoda E.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
graph colouring;
Markov processes;
computational complexity;
random coloring;
constant degree graphs;
Markov chain;
Glauber dynamics;
9.
A polynomial time algorithm for computing an Arrow-Debreu market equilibrium for linear utilities
机译：
用于计算线性公用事业的Arrow-Debreu市场均衡的多项式时间算法
作者：
Jain K.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
marketing;
convex programming;
computational complexity;
game theory;
polynomial time algorithm;
Arrow-Debreu market equilibrium;
linear utilities;
convex program;
ellipsoid algorithm;
simultaneous diophantine approximation;
concave function;
geometric algorithm;
combinatorial optimization;
10.
Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap
机译：
通过2提升和差异与光谱间隙的关系构造扩展图
作者：
Bilu Y.
;
Linial N.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
graph theory;
eigenvalues and eigenfunctions;
computational complexity;
matrix algebra;
expander graph;
2-lifts discrepancy;
nearly optimal spectral gap;
eigenvalues;
d-regular graph;
polynomial time algorithm;
l/sub 1/ norm;
expander mixing lemma;
11.
Dynamic transitive closure via dynamic matrix inverse: extended abstract
机译：
通过动态矩阵逆进行动态传递闭合：扩展的抽象
作者：
Sankowski P.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
directed graphs;
matrix inversion;
determinants;
trees (mathematics);
computational complexity;
query processing;
dynamic transitive closure;
dynamic matrix inverse;
dynamic algebraic function evaluation;
matrix adjoint;
matrix determinant;
spanning trees;
general directed graphs;
12.
Edge pricing of multicommodity networks for heterogeneous selfish users
机译：
异构自私用户的多商品网络边缘定价
作者：
Karakostas G.
;
Kolliopoulos S.G.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
game theory;
network routing;
graph theory;
linear programming;
duality (mathematics);
edge pricing;
multicommodity networks;
heterogeneous selfish users;
selfish behavior;
economic disincentives;
appropriate taxation;
traffic equilibrium;
origin-destination pair;
prescribed minimum-latency flow;
primal-dual linear program;
LP duality;
13.
Hierarchy theorems for probabilistic polynomial time
机译：
概率多项式时间的层次定理
作者：
Fortnow L.
;
Santhanam R.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
probability;
computational complexity;
hierarchy theorems;
probabilistic polynomial time;
probabilistic time;
Barak techniques;
translation argument;
PSPACE-complete problem;
worst-case probabilistic algorithm;
14.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
机译：
MAX-CUT和其他2变量CSP的最佳近似度结果？
作者：
Khot S.
;
Kindler G.
;
Mossel E.
;
ODonnell R.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
computational complexity;
approximation theory;
game theory;
optimisation;
communicating sequential processes;
computability;
graph theory;
optimal inapproximability;
MAX-CUT;
CSP;
NP-hard;
Goemans-Williamson algorithm;
games conjecture;
majority is stablest conjecture;
MAX-2SAT problem;
MAX-2CSP problem;
approximation algorithm;
nonBoolean domains;
15.
Random edge can be exponential on abstract cubes
机译：
在抽象立方体上随机边缘可以是指数的
作者：
Matousek J.
;
Szabo T.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
random processes;
graph theory;
random edge;
abstract cubes;
exponential number;
abstract objective functions;
n-dimensional cube;
random vertex;
probability;
polynomial time;
geometry;
16.
Spectral analysis of random graphs with skewed degree distributions
机译：
倾斜度分布随机图的光谱分析
作者：
Dasgupta A.
;
Hopcroft J.E.
;
McSherry F.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
spectral analysis;
perturbation theory;
matrix algebra;
eigenvalues and eigenfunctions;
graph theory;
random processes;
spectral analysis;
random graphs;
skewed degree distributions;
degree based normalization;
normalized Laplacian;
perturbation theory;
random adjacency matrix;
ubiquitous power law graphs;
power law degree distribution;
eigenvectors;
latent structure;
17.
Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games
机译：
多商品网络和广义拥塞游戏中针对不同自私用户的通行费
作者：
Fleischer L.
;
Jain K.
;
Mahdian M.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
game theory;
telecommunication traffic;
telecommunication congestion control;
graph theory;
heterogeneous selfish users;
multicommodity networks;
generalized congestion games;
linear function;
traffic pattern;
minimum average latency flow;
multicommodity homogeneous users;
single commodity heterogeneous users;
general graphs;
polynomial-sized linear program;
minimum average weighted latency;
minimum maximum latency;
Nash equilibrium;
general nonatomic congestion games;
18.
Adiabatic quantum computation is equivalent to standard quantum computation
机译：
绝热量子计算等效于标准量子计算
作者：
Aharonov D.
;
van Dam W.
;
Kempe J.
;
Landau Z.
;
Lloyd S.
;
Regev O.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
quantum computing;
computational complexity;
adiabatic quantum computation;
standard quantum computation;
computational power;
adiabatic simulation;
quantum algorithm;
standard quantum circuit model;
polynomially equivalent;
19.
Algebras with polynomial identities and computing the determinant
机译：
具有多项式恒等式的代数并计算行列式
作者：
Chien S.
;
Sinclair A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
matrix algebra;
group theory;
polynomials;
polynomial identities;
exponential lower bound;
algebraic branching program;
matrix determinant;
noncommutative algebra;
matrix algebra;
group algebra;
nonabelian finite group;
quaternion algebra;
Clifford algebra;
20.
An approximate max-Steiner-tree-packing min-Steiner-cut theorem
机译：
近似最大施泰纳树堆积最小施泰纳切定理
作者：
Lap Chi Lau
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
trees (mathematics);
approximation theory;
computational complexity;
minimax techniques;
combinatorial mathematics;
max-Steiner-tree-packing theorem;
min-Steiner-cut theorem;
undirected multigraph;
edge-disjoint trees;
APX-hard;
polynomial time constant factor;
approximation algorithm;
approximate min-max relation;
matroid theory;
21.
An edge in time saves nine: LP rounding approximation algorithms for stochastic network design
机译：
时间的优势节省了九个：用于随机网络设计的LP舍入近似算法
作者：
Gupta A.
;
Ravi R.
;
Sinha A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
approximation theory;
stochastic processes;
trees (mathematics);
linear programming;
optimisation;
computer networks;
LP rounding approximation algorithms;
stochastic network design;
stochastic optimization;
probability distributions;
stochastic models;
risk-averse models;
upper bounds;
primal-dual method;
optimal LP relaxation values;
tree-rounding stage;
constant-factor approximation algorithms;
stochastic Steiner tree;
single sink network design problems;
generalized models;
22.
An optimal randomised cell probe lower bound for approximate nearest neighbour searching
机译：
用于近似最近邻居搜索的最优随机细胞探针下界
作者：
Chakrabarti A.
;
Regev O.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
randomised algorithms;
approximation theory;
communication complexity;
information theory;
data compression;
message switching;
theorem proving;
search problems;
optimal randomised cell probe lower bound;
approximate nearest neighbour searching;
Hamming cube;
polynomial storage;
word size;
worst case query time;
approximation factor;
deterministic complexity;
round complexity;
bit complexity;
richness technique;
information theory;
communication complexity;
round elimination;
message compression;
message switching;
23.
An unconditional study of computational zero knowledge
机译：
计算零知识的无条件研究
作者：
Vadhan S.P.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
cryptography;
computational complexity;
theorem proving;
computational zero knowledge;
theorem proving;
one-way functions;
monotone formula closure;
NP problem;
black-box simulators;
nonblack-box simulators;
round complexity;
conditional techniques;
statistical zero knowledge;
24.
Approximating edit distance efficiently
机译：
有效地近似编辑距离
作者：
Bar-Yossef Z.
;
Jayram T.S.
;
Krauthgamer R.
;
Kumar R.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
approximation theory;
string matching;
computational complexity;
edit distance approximation;
natural algorithmic problems;
low-distortion embeddings;
approximate nearest-neighbor schemes;
sketching algorithms;
gap versions;
nonrepetitive strings;
approximation quasilinear time algorithm;
approximation factor;
25.
Approximating the stochastic knapsack problem: the benefit of adaptivity
机译：
近似随机背包问题：适应性的好处
作者：
Dean B.C.
;
Goemans M.X.
;
Vondrdk J.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
stochastic processes;
knapsack problems;
computational complexity;
greedy algorithms;
stochastic knapsack problem;
NP-hard 0/1 knapsack problem;
independent random variables;
nonadaptive policies;
greedy nonadaptive algorithm;
optimal adaptive policy;
adaptive polynomial-time algorithm;
26.
Assignment testers: towards a combinatorial proof of the PCP-theorem
机译：
作业测试人员：寻求PCP定理的组合证明
作者：
Dinur I.
;
Reingold O.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
theorem proving;
computational complexity;
algebra;
graph theory;
assignment testers;
combinatorial proof;
PCP-theorem;
theorem proving;
PCP verifier;
combinatorial aggregation technique;
black-box tester;
algebraic proof techniques;
combinatorial construction;
max-SAT approximation;
quasi-NP-hard;
27.
Deterministic extractors for bit-fixing sources by obtaining an independent seed
机译：
通过获取独立种子来确定位的源的确定性提取器
作者：
Gabizon A.
;
Raz R.
;
Shaltiel R.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
statistical distributions;
random functions;
deterministic extractor;
independent seed;
deterministic bit-fixing source extractor;
universal constant;
statistical distance;
28.
Dynamic approximate all-pairs shortest paths in undirected graphs
机译：
无向图中的动态近似全对最短路径
作者：
Roditty L.
;
Zwick U.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
graph theory;
computational complexity;
query processing;
dynamic approximate all-pairs shortest paths;
dynamic algorithms;
unweighted undirected graphs;
decremental algorithm;
distance query;
amortized update time;
29.
Dynamic speed scaling to manage energy and temperature
机译：
动态速度缩放以管理能量和温度
作者：
Bansal N.
;
Kimbrel T.
;
Pruhs K.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
energy management systems;
computational complexity;
energy conservation;
cooling;
competitive algorithms;
dynamic speed scaling;
energy management;
temperature management;
online speed scaling;
optimal available algorithm;
competitive ratio;
maximum temperature minimization;
Fourier law;
ellipsoid algorithm;
30.
Edge-disjoint paths in planar graphs
机译：
平面图中的边不相交路径
作者：
Chekuri C.
;
Khanna S.
;
Shepherd F.B.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
graph theory;
computational complexity;
maximum edge-disjoint paths;
poly-logarithmic approximation;
undirected planar graphs;
polynomial-factor approximation;
grid-like graphs;
multicommodity flow relaxation;
unsplittable flow problem;
theorem proving;
maxflow-mincut gap;
uniform multicommodity flow;
31.
Exponentially many steps for finding a Nash equilibrium in a bimatrix game
机译：
在双矩阵博弈中找到纳什均衡的指数级步骤
作者：
Savani R.
;
von Stengel B.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
game theory;
computational complexity;
matrix algebra;
Nash equilibrium;
bimatrix game;
Lemke-Howson algorithm;
directed parity argument;
complexity class PPAD;
exponential time;
dual cyclic polytopes;
32.
Extracting randomness using few independent sources
机译：
使用很少的独立来源提取随机性
作者：
Barak B.
;
Impagliazzo R.
;
Wigderson A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
entropy;
number theory;
probability;
graph theory;
random processes;
randomness extraction;
deterministic extractors;
min-entropy;
additive number theory;
positive probability;
stepping-up lemma;
Ramsey number;
hyper-graphs;
33.
Hardness of approximating the shortest vector problem in lattices
机译：
近似格子中最短向量问题的难度
作者：
Khot S.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
computational complexity;
randomised algorithms;
approximation theory;
tensors;
BCH codes;
lattice theory;
shortest vector problem;
lattices;
NP-hard problem;
randomized reduction;
closest vector problem;
BCH codes;
augmented tensor product;
hardness factor;
34.
Hardness of buy-at-bulk network design
机译：
批量购买网络设计的难度
作者：
Andrews M.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
approximation theory;
telecommunication network planning;
computational complexity;
graph theory;
buy-at-bulk network design;
multicommodity demands;
source nodes;
destination nodes;
approximation algorithm;
35.
Holographic algorithms
机译：
全息算法
作者：
Valiant L.G.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
computational complexity;
combinatorial mathematics;
polynomials;
holographic algorithms;
computational problem;
combinatorial problem;
polynomial equations;
integer coefficients;
complex number;
complexity class;
#P-complete problem;
polynomial system;
solvability;
holographic algorithm;
one-to-one mapping;
many-to-one mapping;
one-to-many mapping;
many-to-many correspondence;
polynomial time algorithm;
exponential time algorithm;
36.
Learnability and automatizability
机译：
学习性和自动化性
作者：
Alekhnovich M.
;
Braverman M.
;
Feldman V.
;
Klivans A.R.
;
Pitassi T.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
learning (artificial intelligence);
computational complexity;
decision trees;
graph colouring;
theorem proving;
properly learning concept classes complexity;
polynomial-time PAC learning;
DNF formulae;
OR-of-thresholds;
NP-hard problem;
halfspaces;
decision trees;
nontrivial upper bounds;
approximate hypergraph coloring;
automatizability;
proof complexity;
learnability;
37.
Learning with errors in answers to membership queries
机译：
在会员查询答案中学习错误
作者：
Bisht L.
;
Bshouty N.H.
;
Khoury L.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
learning (artificial intelligence);
query processing;
computational complexity;
error handling;
learning;
limited membership queries;
malicious membership queries;
equivalence queries;
38.
Machine minimization for scheduling jobs with interval constraints
机译：
机器最小化，用于调度具有间隔约束的作业
作者：
Chuzhoy J.
;
Guha S.
;
Khanna S.
;
Naor J.S.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
scheduling;
computational complexity;
linear programming;
relaxation theory;
machine minimization;
job scheduling;
interval constraints;
randomized rounding;
linear programming relaxation;
approximation algorithm;
O(OPT)-approximation;
39.
Measured descent: a new embedding method for finite metrics
机译：
测量下降：一种用于有限度量的新嵌入方法
作者：
Krauthgamer R.
;
Lee J.R.
;
Mendel M.
;
Naor A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
probability;
Hilbert spaces;
graph theory;
computational complexity;
computational geometry;
measured descent;
embedding method;
finite metrics;
metric space decomposition;
probability measure;
Frechet embeddings;
Hilbert space;
geometric estimate;
distortion embedding;
volume-respecting embeddings;
weighted n-point planar graph;
40.
On the (im)possibility of cryptography with imperfect randomness
机译：
具有不完美随机性的密码学的（不可能）可能性
作者：
Dodis Y.
;
Shien Jin Ong
;
Prabhakaran M.
;
Sahai A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
cryptography;
entropy;
cryptography;
imperfect randomness;
bit commitment;
encryption;
secret sharing;
noninteractive zero-knowledge;
secure two-party computation;
nontrivial junction;
less-than-perfect entropy;
unproven assumption;
secure signature;
interactive proofs;
imperfect entropy sources;
41.
On the power of discrete and of lexicographic Helly-type theorems
机译：
关于离散和词典Helly型定理的幂
作者：
Halman N.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
linear programming;
integer programming;
randomised algorithms;
computational complexity;
set theory;
convex objects;
discrete Helly theorems;
lexicographic Helly theorems;
lexicographic-discrete Helly theorems;
linear time optimization;
discrete linear programming;
integer programming;
randomized linear time problems;
discrete p-center on the real line;
discrete weighted 1-center problem;
line transversal;
axis-parallel planar rectangles;
lexicographic rectilinear p-center problem;
42.
On the streaming model augmented with a sorting primitive
机译：
在流模型上增加了排序原语
作者：
Aggarwal G.
;
Datar M.
;
Rajagopalan S.
;
Ruhl M.
会议名称：
《》
|
2004年
关键词：
sorting;
streaming model;
sorting primitive;
computational modeling;
pointer chasing;
external memory algorithms;
43.
Optimal power-down strategies
机译：
最佳掉电策略
作者：
Augustine J.
;
Irani S.
;
Swamy C.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
probability;
computational complexity;
power consumption;
competitive algorithms;
energy conservation;
optimal power-down strategies;
low-power sleep states;
power consumption rate;
probability distribution;
44.
Private codes or succinct random codes that are (almost) perfect
机译：
（几乎）完美的私人密码或简洁的随机密码
作者：
Langberg M.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
decoding;
random codes;
computational complexity;
telecommunication channels;
private codes;
succinct random codes;
coding theory;
noisy channel;
binary symmetric channel;
adversarial channel;
joint secret random string;
decodable code;
45.
Quantum and classical strong direct product theorems and optimal time-space tradeoffs
机译：
量子和经典强直接乘积定理和最佳时空折衷
作者：
Klauck H.
;
Spalek R.
;
de Wolf R.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
quantum computing;
probability;
quantum communication;
protocols;
computational complexity;
matrix multiplication;
Boolean algebra;
classical strong direct product theorems;
optimal time-space tradeoff;
quantum strong direct product theorems;
quantum query complexity;
OR function;
slightly weaker direct product;
total function;
quantum communication protocols;
disjointness function;
quantum computer;
polylog factors;
Boolean matrix-vector multiplication;
quantum theorem;
communication-space tradeoff;
46.
Quantum speed-up of Markov chain based algorithms
机译：
基于马尔可夫链的算法的量子加速
作者：
Szegedy M.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
quantum computing;
Markov processes;
random processes;
quantum speed-up;
Markov chain based algorithms;
random walks;
quadratic speed-up;
transition matrix;
element distinctness;
d-dimensional torus;
quantum escape time;
quantum walks;
47.
Quantum walk algorithm for element distinctness
机译：
用于元素区分的量子行走算法
作者：
Ambainis A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
quantum computing;
quantum walk algorithm;
element distinctness;
query quantum algorithm;
48.
Quantum weak coin-flipping with bias of 0.192
机译：
量子弱硬币翻转，偏差为0.192
作者：
Mochon C.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
quantum cryptography;
protocols;
quantum weak coin-flipping;
protocols;
quantum mechanical setting;
Kitaev description;
semidefinite program;
49.
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique
机译：
排除图最小二等分，最密子图和二分集团的PTAS
作者：
Khot S.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
graph theory;
computational complexity;
polynomials;
PTAS;
graph min-bisection;
densest subgraph;
bipartite clique;
minimum distance of code problem;
quasirandom PCP;
query pattern;
polynomial;
50.
Shuffling by semi-random transpositions
机译：
通过半随机换位进行混洗
作者：
Mossel E.
;
Peres Y.
;
Sinclair A.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
Markov processes;
random processes;
computational complexity;
cryptography;
theorem proving;
semirandom transposition shuffle;
cyclic-to-random shuffle;
cryptographic system;
mixing time;
complex-valued test function;
uniform random permutations;
complex analysis tools;
nonreversible Markov chains;
51.
Stochastic optimization is (almost) as easy as deterministic optimization
机译：
随机优化（几乎）和确定性优化一样简单
作者：
Shmoys D.B.
;
Swamy C.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
stochastic processes;
optimisation;
statistical distributions;
deterministic optimization;
uncertainty modeling;
probability distribution;
well-studied paradigm;
2-stage models;
distributional information;
approximation algorithms;
2-stage discrete stochastic optimization;
random data;
FPRAS;
LP relaxation;
set cover;
vertex cover;
facility location;
multicut;
multicommodity flow problem;
52.
Strong spatial mixing for lattice graphs with fewer colours
机译：
强大的空间混合，可减少颜色的点阵图
作者：
Goldberg L.A.
;
Martin R.
;
Paterson M.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
graph colouring;
free energy;
statistical mechanics;
spin systems;
physics computing;
computational geometry;
theorem proving;
strong spatial mixing;
lattice graphs;
recursively-constructed couplings;
nontree-like graphs;
integer lattice;
triangle-free graph;
spin system;
q-colourings;
statistical physics;
triangular lattice;
infinite-volume Gibbs measure;
macroscopic equilibrium;
hexagonal lattice;
53.
Testing low-degree polynomials over prime fields
机译：
在素数域上测试低次多项式
作者：
Jutla C.S.
;
Patthak A.C.
;
Rudra A.
;
Zuckerman D.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
randomised algorithms;
Reed-Muller codes;
polynomials;
low-degree polynomial testing;
prime fields;
randomized algorithm;
generalized Reed-Muller codes;
54.
Testing polynomials over general fields
机译：
在一般字段上测试多项式
作者：
Kaufman T.
;
Ron D.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
Reed-Muller codes;
polynomials;
computational complexity;
general fields;
polynomial testing;
finite fields;
random affine subspaces;
Reed-Muller codes;
small-weight words;
55.
The exact satisfiability threshold for a potentially intractable random constraint satisfaction problem
机译：
潜在难于解决的随机约束满足问题的确切可满足性阈值
作者：
Connamacher H.
;
Molloy M.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
computability;
constraint theory;
computational complexity;
exact satisfiability threshold;
potentially intractable random constraint satisfaction problem;
NP-hard constraint satisfaction problem;
random k-SAT;
resolution complexity;
SAT conjecture;
XOR-SAT;
56.
The price of stability for network design with fair cost allocation
机译：
具有公平成本分配的网络设计的稳定价格
作者：
Anshelevich E.
;
Dasgupta A.
;
Kleinberg J.
;
Tardos E.
;
Wexler T.
;
Roughgarden T.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
game theory;
protocols;
graph theory;
network design;
fair cost allocation;
strategic behavior;
self-interested agents;
optimum network cost;
network cost allocation;
fair-division scheme;
Shapley value;
best-response dynamics;
near-optimal equilibria;
weighted game;
stability price;
Nash equilibrium;
protocols;
57.
Triangulation and embedding using small sets of beacons
机译：
使用少量信标进行三角剖分和嵌入
作者：
Kleinberg J.
;
Slivkins A.
;
Wexler T.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
Internet;
matrix algebra;
metric embedding;
distance matrix;
node-to-node latency;
low-dimensional Euclidean space;
Internet measurement algorithm;
beacon-based embedding;
beacon-based triangulation;
multiplicative error;
bounded doubling dimension;
triangulation-based reconstruction;
global network positioning algorithm;
58.
Universally composable protocols with relaxed set-up assumptions
机译：
具有轻松设置假设的通用组合协议
作者：
Barak B.
;
Canetti R.
;
Nielsen J.B.
;
Pass R.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
authorisation;
public key cryptography;
universally composable protocols;
relaxed set-up assumptions;
cryptographic protocols;
arbitrary protocols;
common reference string model;
authenticated communication;
public-key infrastructure;
registered public keys;
registration authority;
59.
Worst-case to average-case reductions based on Gaussian measures
机译：
基于高斯度量的最坏情况到平均情况的减少
作者：
Micciancio D.
;
Regev O.
会议名称：
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》
|
2004年
关键词：
Gaussian noise;
approximation theory;
Fourier transforms;
lattice theory;
computational complexity;
worst-case reduction;
average-case reduction;
Gaussian measures;
modular linear equation;
lattice problem;
shortest vector problem;
shortest independent vectors problem;
covering radius problem;
approximation factor;
high dimensional Fourier transform;
Gaussian noise;
uniform distribution;
意见反馈
回到顶部
回到首页
