掌桥科研
一站式科研服务平台
科技查新
收录引用
专题文献检索
外文数据库(机构版)
更多产品
首页
成为会员
我要充值
退出
我的积分:
中文会员
开通
中文文献批量获取
外文会员
开通
外文文献批量获取
我的订单
会员中心
我的包量
我的余额
登录/注册
文献导航
中文期刊
>
中文会议
>
中文学位
>
中国专利
>
外文期刊
>
外文会议
>
外文学位
>
外国专利
>
外文OA文献
>
外文科技报告
>
中文图书
>
外文图书
>
工业技术
基础科学
医药卫生
农业科学
教科文艺
经济财政
社会科学
哲学政法
其他
工业技术
基础科学
医药卫生
农业科学
教科文艺
经济财政
社会科学
哲学政法
其他
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
材料科学
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
马克思主义、列宁主义、毛泽东思想、邓小平理论
哲学、宗教
社会科学总论
政治、法律
军事
经济
文化、科学、教育、体育
语言、文字
文学
艺术
历史、地理
自然科学总论
数理科学和化学
天文学、地球科学
生物科学
医药、卫生
农业科学
工业技术
交通运输
航空、航天
环境科学、安全科学
综合性图书
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
材料科学
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
自然科学总论
数学、物理、化学、力学
天文学、地球科学
生物科技
医学、药学、卫生
航空航天、军事
农林牧渔
机械、仪表工业
化工、能源
冶金矿业
电子学、通信
计算机、自动化
土木、建筑、水利
交通运输
轻工业技术
材料科学
电工技术
一般工业技术
环境科学、安全科学
图书馆学、情报学
社会科学
其他
美国国防部AD报告
美国能源部DE报告
美国航空航天局NASA报告
美国商务部PB报告
外军国防科技报告
美国国防部
美国参联会主席指示
美国海军
美国空军
美国陆军
美国海军陆战队
美国国防技术信息中心(DTIC)
美军标
美国航空航天局(NASA)
战略与国际研究中心
美国国土安全数字图书馆
美国科学研究出版社
兰德公司
美国政府问责局
香港科技大学图书馆
美国海军研究生院图书馆
OALIB数据库
在线学术档案数据库
数字空间系统
剑桥大学机构知识库
欧洲核子研究中心机构库
美国密西根大学论文库
美国政府出版局(GPO)
加利福尼亚大学数字图书馆
美国国家学术出版社
美国国防大学出版社
美国能源部文献库
美国国防高级研究计划局
美国陆军协会
美国陆军研究实验室
英国空军
美国国家科学基金会
美国战略与国际研究中心-导弹威胁网
美国科学与国际安全研究所
法国国际关系战略研究院
法国国际关系研究所
国际宇航联合会
美国防务日报
国会研究处
美国海运司令部
北约
盟军快速反应部队
北约浅水行动卓越中心
北约盟军地面部队司令部
北约通信信息局
北约稳定政策卓越中心
美国国会研究服务处
美国国防预算办公室
美国陆军技术手册
一般OA
科技期刊论文
科技会议论文
图书
科技报告
科技专著
标准
其它
美国卫生研究院文献
分子生物学
神经科学
药学
外科
临床神经病学
肿瘤学
细胞生物学
遗传学
公共卫生&环境&职业病
应用微生物学
全科医学
免疫学
动物学
精神病学
兽医学
心血管
放射&核医学&医学影像学
儿科
医学进展
微生物学
护理学
生物学
牙科&口腔外科
毒理学
生理学
医院管理
妇产科学
病理学
生化技术
胃肠&肝脏病学
运动科学
心理学
营养学
血液学
泌尿科学&肾病学
生物医学工程
感染病
生物物理学
矫形
外周血管病
药物化学
皮肤病学
康复学
眼科学
行为科学
呼吸学
进化生物学
老年医学
耳鼻喉科学
发育生物学
寄生虫学
病毒学
医学实验室检查技术
生殖生物学
风湿病学
麻醉学
危重病护理
生物材料
移植
医学情报
其他学科
人类生活必需品
作业;运输
化学;冶金
纺织;造纸
固定建筑物
机械工程;照明;加热;武器;爆破
物理
电学
人类生活必需品
作业;运输
化学;冶金
纺织;造纸
固定建筑物
机械工程;照明;加热;武器;爆破
物理
电学
马克思主义、列宁主义、毛泽东思想、邓小平理论
哲学、宗教
社会科学总论
政治、法律
军事
经济
文化、科学、教育、体育
语言、文字
文学
艺术
历史、地理
自然科学总论
数理科学和化学
天文学、地球科学
生物科学
医药、卫生
农业科学
工业技术
交通运输
航空、航天
环境科学、安全科学
综合性图书
主题
主题
题名
作者
关键词
摘要
高级搜索 >
外文期刊
外文会议
外文学位
外国专利
外文图书
外文OA文献
中文期刊
中文会议
中文学位
中国专利
中文图书
外文科技报告
清除
历史搜索
清空历史
首页
>
外文会议
>
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
召开年:
2003
召开地:
出版时间:
-
会议文集:
-
会议论文
热门论文
全部论文
全选(
0
)
清除
导出
1.
Performance analysis of dynamic processes
机译:
动态过程的性能分析
作者:
Upfal
;
E.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
computer network reliability;
Markov processes;
queueing theory;
game theory;
performance analysis;
dynamic process;
stochastic process;
discrete time Markov process;
continuous time Markov process;
renewal theory;
adversarial queueing theory;
game theor;
2.
On levels in arrangements of curves. II. A simple inequality and its consequences
机译:
在水平上排列曲线。二。一个简单的不平等及其后果
作者:
Chan T.M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
curve fitting;
graph theory;
polynomials;
computational geometry;
computational complexity;
curve arrangement;
k-level;
subquadratic complexity;
planar arrangement;
polynomial graphs;
curve cutting;
sampling;
parabola;
3.
A polynomial algorithm for recognizing perfect graphs
机译:
识别理想图的多项式算法
作者:
Cornuejols G.
;
Xinming Liu
;
Vuskovic K.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
graph theory;
algorithm theory;
polynomial algorithm;
perfect graph recognition;
decomposition theorem;
odd hole;
recognition algorithm;
4.
Hardness of approximating the shortest vector problem in high L/sub p/ norms
机译:
在高L / sub p /范数中逼近最短向量问题的难度
作者:
Khot S.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
vectors;
computational complexity;
randomised algorithms;
polynomial approximation;
shortest vector problem;
L/sub p/ norm;
NP-hard problem;
randomized reduction;
5.
Instability of FIFO at arbitrarily low rates in the adversarial queuing model
机译:
对抗排队模型中FIFO处于任意低速率的不稳定性
作者:
Bhattacharjee R.
;
Goel A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
packet switching;
protocols;
queueing theory;
telecommunication network routing;
FIFO;
first in first out;
adversarial queuing model;
packet forwarding protocol;
unbounded buffer-occupancy;
queuing delay;
injection rate;
6.
On certain connectivity properties of the Internet topology
机译:
关于Internet拓扑的某些连接属性
作者:
Mihail M.
;
Papadimitriou C.
;
Saberi A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Internet;
graph theory;
eigenvalues and eigenfunctions;
matrix algebra;
telecommunication network routing;
connectivity property;
Internet topology;
random graph;
preferential connectivity model;
routing congestion;
spectral gap;
eigenvalues;
random walk;
7.
An in-place sorting with O(n log n) comparisons and O(n) moves
机译:
使用O(n log n)比较和O(n)移动进行就地排序
作者:
Franceschini G.
;
Geffert V.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
sorting;
merging;
computational complexity;
storage management;
in-place sorting;
in-place algorithm;
sorting algorithm;
asymptotic lower bound;
O(n log n) element comparisons;
O(n) element transports;
computational resources;
8.
On the maximum satisfiability of random formulas
机译:
关于随机公式的最大可满足性
作者:
Achlioptas D.
;
Naor A.
;
Peres Y.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Boolean functions;
random processes;
computational complexity;
computability;
probability;
maximum satisfiability;
random formulas;
NP-complete problem;
random instances;
canonical problem;
statistical physics;
maximum clauses;
random k-CNF formula;
asym;
9.
A lattice problem in quantum NP
机译:
NP中的晶格问题
作者:
Aharonov D.
;
Regev O.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
quantum computing;
quantum entanglement;
computational complexity;
graph theory;
lattice problem;
quantum NP;
QMA;
quantum complexity;
QMA+ formulation;
quantum entanglement;
autocorrelation function estimation;
10.
A lower bound for the bounded round quantum communication complexity of set disjointness
机译:
集不相交的有界圆形量子通信复杂度的下界
作者:
Jain R.
;
Radhakrishnan J.
;
Sen P
会议名称:
《》
|
2003年
关键词:
quantum communication;
communication complexity;
Boolean functions;
quantum computing;
round quantum communication complexity;
set disjointness;
qubits transmission;
Boolean valued function;
monotone sensitivity;
quantum communication protocol;
informati;
11.
A non-Markovian coupling for randomly sampling colorings
机译:
用于随机采样颜色的非马尔可夫耦合
作者:
Hayes T.P.
;
Vigoda E.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Markov processes;
sampling methods;
graph colouring;
computational complexity;
nonMarkovian coupling;
random coloring sampling;
Glauber dynamics;
uniform distribution;
Markov chain;
graph coloring;
girth requirements;
maximum degree requirements;
12.
Always Good Turing: asymptotically optimal probability estimation
机译:
Always Good Turing:渐近最优概率估计
作者:
Orlitsky A.
;
Santhanam N.P.
;
Zhang J.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
estimation theory;
probability;
Turing machines;
number theory;
learning (artificial intelligence);
asymptotically optimal probability estimation;
Turing estimator;
probability distribution;
information-theoretic;
machine-learning framework;
per symbol p;
13.
Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
机译:
通过分解有向正则多图的非对称TSP近似算法
作者:
Kaplan H.
;
Lewenstein M.
;
Shafrir N.
;
Sviridenko M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
travelling salesman problems;
graph theory;
theorem proving;
polynomial approximation;
approximation algorithm;
asymmetric TSP;
travelling salesman problem;
directed regular multigraph;
Halls theorem;
d-regular multigraph;
polynomial algorithm;
combinato;
14.
Approximation algorithms for orienteering and discounted-reward TSP
机译:
定向越野和折价TSP的近似算法
作者:
Blum A.
;
Chawla S.
;
Karger D.R.
;
Lane T.
;
Meyerson A.
;
Minkoff M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
travelling salesman problems;
approximation theory;
decision trees;
approximation algorithm;
rooted orienteering problem;
discounted-reward TSP;
travelling salesman problem;
robot navigation;
length limit;
discount factor;
Markov decision processes;
tree;
15.
Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem
机译:
通过分摊费用进行逼近:一种用于多商品租购问题的简单逼近算法
作者:
Gupta A.
;
Kumar A.
;
Pal M.
;
Roughgarden T.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
approximation theory;
computational complexity;
graph theory;
facility location;
approximation algorithm;
cost-sharing;
multicommodity rent-or-buy problem;
edge capacity rental;
network design;
economies of scale;
minimum cost method;
cost allocation;
16.
Average case and smoothed competitive analysis of the multi-level feedback algorithm
机译:
多级反馈算法的平均情况和平滑竞争分析
作者:
Becchetti L.
;
Leonardi S.
;
Marchetti-Spaccamela A.
;
Schafer G.
;
Vredeveld T.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
feedback;
competitive algorithms;
deterministic algorithms;
benchmark testing;
randomised algorithms;
minimisation;
smoothing methods;
average case analysis;
smoothed competitive analysis;
multilevel feedback algorithm;
online algorithms;
smoothed analys;
17.
Bounded geometries, fractals, and low-distortion embeddings
机译:
有界几何图形,分形和低失真嵌入
作者:
Gupta A.
;
Krauthgamer R.
;
Lee J.R.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
fractals;
computational complexity;
computational geometry;
graph theory;
bounded geometries;
normed spaces;
graphs;
fractals;
low-distortion embedding;
doubling metrics;
fixed minor;
snowflaked metric;
decomposition theorem;
dimensionality reduction;
fi;
18.
Bounded-concurrent secure two-party computation in a constant number of rounds
机译:
固定轮数中的有界并发安全两方计算
作者:
Pass R.
;
Rosen A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
cryptography;
concurrency theory;
protocols;
computational complexity;
bounded-concurrent two-party computation;
secure two-party computation;
constant rounds;
general protocol construction;
concurrent composition;
a-priori bound;
concurrent sessions;
bo;
19.
Breaking a time-and-space barrier in constructing full-text indices
机译:
突破全文索引构建的时空障碍
作者:
Wing-Kai Hon
;
Sadakane K.
;
Wing-Kin Sung
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
tree data structures;
computational complexity;
trees (mathematics);
indexing;
text analysis;
time-and-space barrier;
full-text index;
construction algorithm;
space-efficient algorithm;
unit-cost word RAM;
compressed suffix tree;
compressed suffix array;
20.
Broadcasting algorithms in radio networks with unknown topology
机译:
拓扑未知的无线电网络中的广播算法
作者:
Czumaj A.
;
Rytter W.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
radio networks;
randomised algorithms;
deterministic algorithms;
communication complexity;
broadcasting;
unknown topology;
randomized algorithms;
deterministic algorithms;
radio broadcasting;
directed n-node radio networks;
eccentricity;
source node dist;
21.
Clustering with qualitative information
机译:
定性信息聚类
作者:
Charikar M.
;
Guruswami V.
;
Wirth A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
pattern clustering;
pattern classification;
computational complexity;
graph theory;
data analysis;
minimisation;
element clustering;
qualitative information;
pairwise judgment;
minimization;
graph edge labelling;
vertex partitioning;
approximation;
maxim;
22.
Deterministic extractors for bit-fixing sources and exposure-resilient cryptography
机译:
确定性提取器,用于位固定源和弹性曝光加密
作者:
Kamp J.
;
Zuckerman D.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
cryptography;
deterministic algorithms;
random processes;
deterministic extractor;
bit-fixing source;
exposure-resilient cryptography;
deterministic algorithm;
exposure-resilient function;
adaptive transform;
fixed bit;
random bit;
all-or-nothing transfo;
23.
General composition and universal composability in secure multi-party computation
机译:
安全的多方计算中的一般组成和通用可组合性
作者:
Lindell Y.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
cryptography;
multiprocessing systems;
protocols;
concurrency theory;
universal composability;
secure multiparty computation;
concurrent general composition;
secure protocol;
network security;
computer networks;
impossibility results;
nonblack box simula;
24.
Gossip-based computation of aggregate information
机译:
基于八卦的汇总信息计算
作者:
Kempe D.
;
Dobra A.
;
Gehrke J.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
computer networks;
fault tolerant computing;
computer network reliability;
protocols;
gossip-based computation;
aggregate information;
computer connectivity;
distributed systems;
instability;
node failures;
link failures;
volatile systems;
decentralized;
25.
Group strategy proof mechanisms via primal-dual algorithms
机译:
通过原始对偶算法的组策略证明机制
作者:
Pal M.
;
Tardos E.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
competitive algorithms;
game theory;
facility location;
communication complexity;
multiprocessor interconnection networks;
group strategy proof mechanism;
primal-dual algorithm;
metric facility location;
single source rent-or-buy network design;
facility;
26.
I/O-efficient strong connectivity and depth-first search for directed planar graphs
机译:
I / O高效的强连通性和深度优先的有向平面图搜索
作者:
Arge L.
;
Zeh N.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
directed graphs;
tree searching;
tree data structures;
computational complexity;
I/O-efficient strong connectivity;
depth-first search;
directed planar graph;
I/O-efficient algorithm;
depth-first spanning;
DFS tree;
27.
Learning DNF from random walks
机译:
从随机游动中学习DNF
作者:
Bshouty N.
;
Mossel E.
;
ODonnell R.
;
Servedio R.A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Boolean functions;
decision trees;
learning (artificial intelligence);
Fourier analysis;
computational complexity;
DNF;
disjunctive normal form;
random walk;
Boolean function;
polynomial time algorithm;
learning decision tree;
passive learning model;
28.
Linear upper bounds for random walk on small density random 3-CNFs
机译:
小密度随机3-CNF上随机游动的线性上限
作者:
Alekhnovich M.
;
Ben-Sasson E.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
randomised algorithms;
random processes;
linear programming;
computability;
computational complexity;
linear upper bounds;
small density random 3-CNF;
efficiency analysis;
random walk algorithm;
running time;
small clause density;
sub-exponential upper b;
29.
List-decoding using the XOR lemma
机译:
使用XOR引理进行列表解码
作者:
Trevisan L.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
decoding;
theorem proving;
error correction codes;
computational complexity;
polynomials;
randomised algorithms;
list-decoding algorithm;
XOR lemma;
direct product lemma;
error-correcting code;
unique-decoding algorithm;
pairwise independent input;
encod;
30.
Locally testable cyclic codes
机译:
可本地测试的循环码
作者:
Babai L.
;
Shpilka A.
;
Stefankovic D.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
error correction codes;
cyclic codes;
linear codes;
randomised algorithms;
Galois fields;
block codes;
testable cyclic code;
linear code;
normalized distance;
block length;
randomized algorithm;
Hamming distance;
holographic proof;
31.
Logconcave functions: geometry and efficient sampling algorithms
机译:
对数凹函数:几何和有效的采样算法
作者:
Lovasz L.
;
Vempala S.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
sampling methods;
Gaussian distribution;
computational geometry;
computational complexity;
logconcave density function;
geometry;
sampling algorithm;
ball walk;
Metropolis filter;
uniform density;
convex set;
Gaussian generalization;
density function smo;
32.
Lower bounds for non-black-box zero knowledge
机译:
非黑匣子零知识的下界
作者:
Barak B.
;
Lindell Y.
;
Vadhan S.
会议名称:
《》
|
2003年
关键词:
computational complexity;
cryptography;
lower bounds;
nonblack-box zero knowledge;
impossibility results;
general zero-knowledge;
complexity assumptions;
computationally sound argument system;
bounded-resettable zero knowledge;
cryptography;
nontrivial l;
33.
More on average case vs approximation complexity
机译:
有关平均情况的更多信息与近似复杂度
作者:
Alekhnovich M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
computational complexity;
approximation theory;
public key cryptography;
binary codes;
computability;
decoding;
approximation complexity;
average case hardness;
cryptography;
Feiges hypothesis;
random 3CNF;
combinatorial problem;
NP-hardness;
codeword;
m;
34.
On /spl epsiv/-biased generators in NC/sup 0/
机译:
在NC / sup 0 /中的/ spl epsiv /偏置发生器上
作者:
Mossel
;
E.
;
Shpilka
;
A.
;
Trevisan
;
L.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
random number generation;
computational complexity;
/spl epsiv/-biased generator;
NC/sup 0/;
pseudorandom generator;
distinguishing probability;
linear distinguisher;
XOR;
linear testing;
/spl epsiv/-biased space;
polynomial time;
35.
On the impossibility of dimension reduction in /spl lscr//sub 1/
机译:
关于不可能在/ spl lscr // sub 1 /中减小尺寸
作者:
Brinkman
;
B.
;
Charikar
;
M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
linear programming;
computational complexity;
duality (mathematics);
graph theory;
dimension reduction impossibility;
Johnson-Lindenstrauss Lemma;
Euclidean space;
pairwise distance;
lower bound;
series-parallel graph;
linear programming;
point embedding;
36.
On worst-case to average-case reductions for NP problems
机译:
关于NP问题的最坏情况减少到平均情况
作者:
Bogdanov A.
;
Trevisan L.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
computational complexity;
cryptography;
worst case reductions;
average case reductions;
NP problems;
NP-complete problem;
nonadaptive self corrector;
polynomial hierarchy;
third level collapse;
nonadaptive random self reduction;
average case hardness;
on;
37.
Paths, trees, and minimum latency tours
机译:
路径,树木和最小延迟游览
作者:
Chaudhuri K.
;
Godfrey B.
;
Rao S.
;
Talwar K.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
approximation theory;
minimisation;
travelling salesman problems;
trees (mathematics);
approximation algorithm;
latency minimization;
k-traveling repairmen;
multiple depot variant;
minimum latency problem;
minimum latency tours;
38.
Polynomial degree vs. quantum query complexity
机译:
多项式度与量子查询复杂度
作者:
Ambainis A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
quantum computing;
polynomial approximation;
communication complexity;
polynomial degree;
quantum query complexity;
quantum algorithm;
quantum adversary method;
polynomial representation;
superlinear separation;
39.
Quantum search of spatial regions
机译:
空间区域的量子搜索
作者:
Aaronson S.
;
Ambainis A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
quantum computing;
query processing;
search problems;
computational complexity;
graph theory;
spatial region;
quantum search algorithm;
quantum query complexity;
information storage;
black hole thermodynamics;
generalized algorithm;
unitary matrix;
0(/sp;
40.
Rank bounds and integrality gaps for cutting planes procedures
机译:
切割平面程序的秩边界和完整性间隙
作者:
Buresh-Oppenheim J.
;
Galesi N.
;
Hoory S.
;
Magen A.
;
Pitassi T.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
integer programming;
linear programming;
boundary integral equations;
theorem proving;
computability;
computational complexity;
integrality gaps;
cutting planes procedures;
rank bound proving;
proof systems;
unsatisfiability;
near-optimal rank bounds;
Lo;
41.
Simulated annealing in convex bodies and an O*(n/sup 4/) volume algorithm
机译:
凸体中的模拟退火和O *(n / sup 4 /)体积算法
作者:
Lovasz
;
L.
;
Vempala
;
S.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
simulated annealing;
computational complexity;
computational geometry;
randomised algorithms;
simulated annealing;
convex bodies;
volume computation algorithm;
morphing technique;
polynomial time;
randomized algorithm;
complexity;
42.
Stability and efficiency of a random local load balancing protocol
机译:
随机本地负载平衡协议的稳定性和效率
作者:
Anagnostopoulos A.
;
Kirsch A.
;
Upfal E.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
resource allocation;
processor scheduling;
protocols;
distributed algorithms;
randomised algorithms;
computational complexity;
random local load balancing protocol stability;
random local load balancing protocol efficiency;
long term performance;
steady;
43.
Symmetric polynomials over /spl Zopf//sub m/ and simultaneous communication protocols
机译:
/ spl Zopf // sub m /上的对称多项式和同时通信协议
作者:
Bhatnagar
;
N.
;
Gopalan
;
P.
;
Lipton
;
R.J.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
polynomials;
number theory;
Boolean functions;
protocols;
communication complexity;
symmetric polynomials;
/spl Zopf//sub m/;
simultaneous communication protocols;
rings;
symmetric Boolean functions;
equivalence;
degree;
modulo;
bound proving;
lower boun;
44.
The complexity of homomorphism and constraint satisfaction problems seen from the other side
机译:
从另一侧看,同态的复杂性和约束满足问题
作者:
Grohe M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
constraint theory;
computational complexity;
graph theory;
homomorphism complexity;
constraint satisfaction problem;
relational structure;
parameterized complexity theory;
bounded tree-width;
graph homomorphism;
polynomial time;
45.
The resolution complexity of random constraint satisfaction problems
机译:
随机约束满足问题的解析复杂度
作者:
Molloy M.
;
Salavatipour M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
constraint theory;
random processes;
computability;
computational complexity;
resolution complexity;
random constraint satisfaction problems;
domain size;
restrictions;
variables;
constant resolution complexity;
polynomial resolution complexity;
exponent;
46.
Towards a characterization of truthful combinatorial auctions
机译:
刻画真实的组合拍卖
作者:
Lavi R.
;
Ahuva Mualem
;
Nisan N.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
combinatorial mathematics;
computational complexity;
optimisation;
truthful combinatorial auction characterization;
affine maximizer;
exact optimization;
polynomial-time auction;
computational hardness;
computational intractability;
47.
Towards a dichotomy theorem for the counting constraint satisfaction problem
机译:
关于计数约束满足问题的二分定理
作者:
Bulatov A.A.
;
Dalmau V.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
constraint theory;
computational complexity;
graph theory;
constraint handling;
dichotomy theorem;
counting constraint satisfaction problem;
finite domain;
constraint predicate;
Mal'tsev polymorphism;
predicate conjunction;
#CSP parametrization;
constrai;
48.
Proofs of the Parisi and Coppersmith-Sorkin conjectures for the finite random assignment problem
机译:
有限随机分配问题的Parisi和Coppersmith-Sorkin猜想的证明
作者:
Nair C.
;
Prabhakar B.
;
Sharma M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
random functions;
combinatorial mathematics;
probability;
matrix algebra;
task analysis;
parallel machines;
theorem proving;
Parisi conjecture;
Coppersmith-Sorkin conjecture;
finite random assignment problem;
minimum-cost permutation;
combinatorial argum;
49.
Switch scheduling via randomized edge coloring
机译:
通过随机边缘着色进行切换调度
作者:
Aggarwal G.
;
Motwani R.
;
Shah D.
;
An Zhu
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Internet;
graph colouring;
packet switching;
processor scheduling;
communication complexity;
telecommunication network routing;
queueing theory;
randomised algorithms;
switch scheduling;
randomized edge coloring;
Internet router;
n /spl times/ n switch;
50.
A group-theoretic approach to fast matrix multiplication
机译:
基于组理论的快速矩阵乘法
作者:
Cohn H.
;
Umans C.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
group theory;
matrix multiplication;
computational complexity;
group-theoretic approach;
fast matrix multiplication;
exponent bounding;
group identification;
group algebra;
dimension control;
irreducible group representations;
group theory;
representatio;
51.
Algorithms and complexity results for #SAT and Bayesian inference
机译:
#SAT和贝叶斯推理的算法和复杂度结果
作者:
Bacchus F.
;
Dalmao S.
;
Pitassi T.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
computational complexity;
uncertainty handling;
computability;
inference mechanisms;
Bayes methods;
complexity results;
#SAT;
Bayesian inference;
probabilistic reasoning;
satisfying assignment counting;
DPLL;
memorization;
#DPLLCache algorithm;
time comp;
52.
Logics for reasoning about cryptographic constructions
机译:
密码结构推理的逻辑
作者:
Impagliazzo R.
;
Kapron B.M.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
cryptography;
inference mechanisms;
reasoning;
cryptographic constructions;
logical systems;
cryptographic security definitions;
soundness proving;
nonstandard arithmetic models;
formal deduction systems;
meta-logic;
53.
Mixing Markov chain
机译:
混合马尔可夫链
作者:
Randall D.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Markov processes;
sampling methods;
random processes;
Markov chain mixing;
stationary distribution;
running time;
mixing time;
54.
On the (In)security of the Fiat-Shamir paradigm
机译:
关于菲亚特-沙米尔范式的(不)安全性
作者:
Goldwasser S.
;
Kalai Y.T.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
public key cryptography;
message authentication;
theorem proving;
Fiat-Shamir paradigm;
digital signature scheme;
deterministic hash function;
Fiat-Shamir transformation;
nonblack-box access;
3-round public-coin identification schemes;
Random Oracle Mode;
55.
On the implementation of huge random objects
机译:
关于执行巨大的随机对象
作者:
Goldreich O.
;
Goldwasser S.
;
Nussboim A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
random processes;
graph theory;
computational complexity;
random object;
random connected graph;
random bounded-degree graph;
random error-correcting code;
standard query;
edge query;
complex query;
huge random objects;
56.
Proving hard-core predicates using list decoding
机译:
使用列表解码证明核心谓词
作者:
Akavia A.
;
Goldwasser S.
;
Safra S.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
cryptography;
decoding;
error correction codes;
computational complexity;
Boolean functions;
learning (artificial intelligence);
hard-core predicate;
list decoding;
error correcting code;
corrupted codeword;
Fourier representation;
learning algorithm;
Fo;
57.
Solving sparse, symmetric, diagonally-dominant linear systems in time O(m/sup 1.31/
机译:
在时间O(m / sup 1.31 / s)中求解稀疏,对称,对角占优线性系统
作者:
Spielman
;
D.A.
;
Shang-Hua Teng
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
sparse matrices;
computational complexity;
combinatorial mathematics;
sparse symmetric diagonally-dominant linear systems;
solution time;
linear-system solver;
n-by-n symmetric positive semi-definite diagonally dominant matrix;
nonzero entries;
combinato;
58.
The cost of cache-oblivious searching
机译:
缓存忽略搜索的成本
作者:
Bender M.A.
;
Brodal G.S.
;
Fagerberg R.
;
Ge D.
;
Simai He
;
Haodung Hu
;
Iacono J.
;
Lopez-Ortiz A.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
cache storage;
memory architecture;
tree data structures;
tree searching;
cache-oblivious searching;
block transfer;
memory hierarchy;
block size;
van Emde Boas layout;
disk access model;
search structure;
multilevel memory hierarchies;
search costs;
59.
The Ising model on trees: boundary conditions and mixing time
机译:
树木的伊辛模型:边界条件和混合时间
作者:
Martinelli F.
;
Sinclair A.
;
Weitz D.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Ising model;
Potts model;
antiferromagnetism;
trees (mathematics);
Markov processes;
graph colouring;
computational complexity;
Ising model;
trees;
boundary condition;
mixing time;
Glauber dynamics;
log-Sobolev constant;
spectral gap;
antiferromagnetic P;
60.
The value of knowing a demand curve: bounds on regret for online posted-price auctions
机译:
了解需求曲线的价值:在线发布价格拍卖的遗憾界限
作者:
Kleinberg R.
;
Leighton T.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
pricing;
electronic trading;
demand forecasting;
cost optimal control;
demand curve;
online posted-price auction;
upper bound;
lower bound;
sublogarithmic factor;
price setting algorithm;
good valuation;
online transaction;
transaction model;
61.
Zero-knowledge sets
机译:
零知识集
作者:
Micali S.
;
Rabin M.
;
Kilian J.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
cryptography;
computational complexity;
trees (mathematics);
zero-knowledge set;
polynomial-time prover;
arbitrary finite set;
random string;
zero-knowledge database;
elementary database;
62.
Separating the power of monotone span programs over different fields
机译:
分离单调跨度程序在不同领域的功能
作者:
Beimel A.
;
Weinreb E.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
linear algebra;
computational complexity;
cryptography;
polynomials;
monotone span program power;
linear-algebraic model;
linear computation;
linear secret sharing schemes;
cryptography;
finite fields;
super-polynomial separation;
super-polynomial lower;
63.
Tight lower bounds for the distinct elements problem
机译:
独特元素问题的严格下界
作者:
Indyk P.
;
Woodruff D.
会议名称:
《Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on》
|
2003年
关键词:
Boolean functions;
communication complexity;
tight lower bound;
distinct element problem;
space complexity;
data stream element;
one-pass streaming algorithm;
one-way communication complexity;
Boolean function;
Euclidean space;
意见反馈
回到顶部
回到首页