首页>外文会议>Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing

Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing

召开年：1996
召开地：Philadelphia, PA(US);Philadelphia, PA(US)
出版时间：-

会议文集：-

会议论文

热门论文

全部论文

全选（0）

1.Convergence complexity of optimistic rate based flow control algorithms (extended abstract)

机译：基于乐观速率的流控制算法的收敛复杂度（扩展摘要）
- 作者：Yehuda Afek;Yishay Mansour;Zvi Ostfeld
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
2.Efficient algorithms for inverting evolution

机译：高效的反演算法
- 作者：Martin Farach;Sampath Kannan
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
3.Modular coloring formulas are hard for cutting planes proofs

机译：模块化着色公式很难用于切割平面样张
- 作者：Xudong Fu
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
4.Towards an analysis of local optimization algorithms

机译：进行局部优化算法分析
- 作者：Tassos Dimitriou;Russell Impagliazzo
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
5.How good is the Goemans-Williamson MAX CUT algorithm?

机译：Goemans-Williamson MAX CUT算法的性能如何？
- 作者：Howard Karloff
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
6.A tight analysis of the greedy algorithm for set cover

机译：集覆盖的贪婪算法的严格分析
- 作者：Petr Slavik
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
- set cover;
7.Computing roadmaps of semi-algebraic sets (extended abstract)

机译：计算半代数集的路线图（扩展摘要）
- 作者：S. Basu;R. Pollack;M.-F. Roy
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
8.Adversarial queueing theory

机译：对抗排队论
- 作者：Allan Borodin;Jon Kleinberg;Prabhakar Raghavan;Madhu Sudan;David P. Williamson
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
9.Computing Betti numbers via combinatorial Laplacians

机译：通过组合拉普拉斯算子计算贝蒂数
- 作者：Joel Friedman
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
10.Adaptively secure multi-party computation

机译：自适应安全的多方计算
- 作者：Ran Canetti;Uri Feige;Oded Goldreich;Moni Naor
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
11.Algorithms for manifolds and simplicial complexes in Euclidean 3-space (preliminary version)

机译：欧几里得三空间中的流形和单纯形复数的算法（初版）
- 作者：Tamal K. Dey;Sumanta Guha
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
- surfaces;
12.Nondeterministic communication with a limited number of advice bits

机译：咨询位数量有限的不确定性通信
- 作者：J. Hromkovic;G. Schnitger
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
13.Noise-tolerant learning near the information-theoretic bound

机译：信息理论界附近的耐噪声学习
- 作者：Nicolo Cesa-Bianchi;Eli Dichterman;Paul Fischer;Hans Ulrich Simon
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
14.Minimum cuts in near-linear time

机译：缩短接近线性时间的时间
- 作者：David R. Karger
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
15.Noise-tolerant distribution-free learning of general geometric concepts

机译：通用几何概念的无噪声无分布学习
- 作者：Nader H. Bshouty;Sally A. Goldman;H. David Mathias;Subhash Suri;Hisao Tamaki
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
16.Using the Groebner basis algorithm to find proofs of unsatisfiability

机译：使用Groebner基算法找到不满足的证据
- 作者：Matthew Clegg;Jeffery Edmonds;Russell Impagliazzo
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
17.Sparsity considerations in Dixon resultants

机译：Dixon结果中的稀疏性考虑
- 作者：Deepak Kapur;Tushar Saxena
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
18.Efficient 3-D range searching in external memory

机译：外部存储器中的有效3-D范围搜索
- 作者：Darren Erik Vengroff;Jeffrey Scott Vitter
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
19.Approximability and nonapproximability results for minimizing total flow time on a single machine

机译：逼近度和非逼近度结果可最大程度地减少单台机器上的总流动时间
- 作者：Hans Kellerer;Thomas Tautenhahn;Gerhard J. Woeginger
- 会议名称：《》 | 1996年
- worst case analysis;
20.Reconstructing a three-dimensional model with arbitrary errors

机译：重建具有任意误差的三维模型
- 作者：Bonnie Berger;Jon Kleinberg;Tom Leighton
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
21.On extracting randomness from weak random sources (extended abstract)

机译：从弱随机源中提取随机性（扩展摘要）
- 作者：Amnon Ta-Shma
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
22.Towards the learnability of DNF formulae

机译：致力于DNF公式的易学性
- 作者：Nader H. Bshouty
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
23.Approximating s-t minimum cuts in O(n2) time

机译：O（n2）时间中的s-t最小削减量
- 作者：Andras A. Benczur;David R. Karger
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
24.Making commitments in the face of uncertainty

机译：面对不确定性做出承诺
- 作者：Baruch Awerbuch;Yossi Azar;Amos Fiat;Tom Leighton
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
25.Lower bounds for on-line graph problems with application to on-line circuit and optical routing

机译：应用于在线电路和光路由的在线图形问题的下界
- 作者：Yair Bartal;Amos Fiat;Stefano Leonardi
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
26.The complexity of matrix rank and feasible systems of linear equations (extended abstract)

机译：矩阵秩的复杂性和线性方程组的可行系统（扩展摘要）
- 作者：Eric Allender;Robert Beals;Mitsunori Ogihara
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
27.Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs

机译：单调跨度程序的极值二部图和超多项式下界
- 作者：Laszlo Babai;Anna Gal;Janos Kollar;Lajos Ronyai;Tibor Szabo;Avi Wigderson
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
28.A lower bound for randomized algebraic decision trees

机译：随机代数决策树的下界
- 作者：Dima Grigoriev;Marek Karpinski;Friedhelm Meyer auf der Heide;Roman Smolensky
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
29.Characterizing linear size circuits in terms of privacy

机译：根据隐私特征描述线性尺寸电路
- 作者：Eyal Kushilevitz;Rafail Ostrovsky;Adi Rosen
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
30.On relationships between statistical zero-knowledge proofs

机译：关于统计零知识证明之间的关系
- 作者：Tatsuaki Okamoto
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
31.Deterministic restrictions in circuit complexity

机译：电路复杂性的确定性限制
- 作者：Shiva Chaudhuri;Jaikumar Radhakrishnan
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
32.The space complexity of approximating the frequency moments

机译：近似频率矩的空间复杂度
- 作者：Noga Alon;Yossi Matias;Mario Szegedy
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
33.Pushing disks together---the continuous-motion case

机译：推盘在一起-连续运动的情况
- 作者：Marshall Bern;Amit Sahai
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
34.Embedding graphs in an arbitrary surface in linear time

机译：在线性时间内将图形嵌入任意表面
- 作者：Bojan Mohar
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
35.Randomness-optimal sampling, extractors, and constructive leader election

机译：随机性最佳抽样，提取器和建设性的领导者选举
- 作者：David Zuckerman
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
36.Generating random spanning trees more quickly than the cover time

机译：比覆盖时间更快地生成随机生成树
- 作者：David Bruce Wilson
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
37.Large-scale assembly of DNA strings and space-efficient construction of suffix trees

机译：DNA字符串的大规模组装和后缀树的空间高效构造
- 作者：S. Rao Kosaraju;Arthur L. Delcher
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
38.A constant-factor approximation algorithm for the k MST problem (extended abstract)

机译：k MST问题的常数因子近似算法（扩展摘要）
- 作者：Avrim Blum;R. Ravi;Santosh Vempala
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
39.Fast algorithms for k-shredders and k-node connectivity augmentation (extended abstract)

机译：用于k粉碎机和k节点连接性增强的快速算法（扩展摘要）
- 作者：Joseph Cheriyan;Ramakrishna Thurimella
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
40.An O(nlogn)-size fault-tolerant sorting network (extended abstract)

机译：O（nlogn）大小的容错分拣网络（扩展的摘要）
- 作者：Yuan Ma
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
41.Learning Sat-k-DNF formulas from membership queries

机译：从成员资格查询中学习Sat-k-DNF公式
- 作者：F. Bergadano;D. Catalano;S. Varricchio
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
42.Testing of the long code and hardness for clique

机译：测试集团的长代码和硬度
- 作者：Johan Hastad
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
43.Translational polygon containment and minimal enclosure using linear programming based restriction

机译：使用基于线性编程的约束，平移多边形包含和最小封闭
- 作者：Victor J. Milenkovic
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
44.Automatic methods for hiding latency in high bandwidth networks (extended abstract)

机译：隐藏高带宽网络中延迟的自动方法（扩展摘要）
- 作者：Matthew Andrews;Tom Leighton;P. Takis Metaxas;Lisa Zhang
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
45.Distributed packet switching in arbitrary networks

机译：任意网络中的分布式数据包交换
- 作者：Yuval Rabani;Eva Tardos
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
46.Non-expansive hashing

机译：非扩展哈希
- 作者：Nathan Linial;Ori Sasson
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
47.Modular competitiveness for distributed algorithms

机译：分布式算法的模块化竞争力
- 作者：James Aspnes;Orli Waarts
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
48.Universal algorithms for store-and-forward and wormhole routing

机译：通用的存储转发和虫洞路由算法
- 作者：Robert Cypher;Friedhelm Meyer auf der Heide;Christian Scheideler;Berthold Vocking
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
49.Digital signets

机译：电子书签
- 作者：Cynthia Dwork;Jeffrey Lotspiech;Moni Naor
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
50.Witness-based cryptographic program checking and robust function sharing

机译：基于见证的加密程序检查和强大的功能共享
- 作者：Yair Frankel;Peter Gemmell;Moti Yung
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
51.Lower bounds for noisy Boolean decision trees

机译：嘈杂的布尔决策树的下界
- 作者：William Evans;Nicholas Pippenger
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
52.Adaptive zero knowledge and computational equivocation (extended abstract)

机译：自适应零知识和计算模棱两可（扩展摘要）
- 作者：Donald Beaver
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
53.The linear-array conjecture in communication complexity is false

机译：通信复杂性中的线性阵列猜想是错误的
- 作者：Eyal Kushilevitz;Nathan Linial;Rafail Ostrovsky
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
54.Generating hard instances of lattice problems (extended abstract)

机译：生成晶格问题的硬实例（扩展摘要）
- 作者：M. Ajtai
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
55.Dynamic deflection routing on arrays (preliminary version)

机译：阵列上的动态偏转布线（普通版）
- 作者：Andrei Broder;Eli Upfal
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
56.Correlated pseudorandomness and the complexity of private computations

机译：相关的伪随机性和私有计算的复杂性
- 作者：Donald Beaver
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
57.Faster isomorphism testing of strongly regular graphs

机译：强正则图的更快同构测试
- 作者：Daniel A. Spielman
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
58.Node-disjoint paths on the mesh and a new trade-off in VLSI layout

机译：网格上的节点不相交路径和VLSI布局中的新权衡
- 作者：Alok Aggarwal;Jon Kleinberg;David P. Williamson
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
59.Deterministic O(nm) time edge-splitting in undirected graphs

机译：无向图中确定性O（nm）时间边缘分裂
- 作者：Hiroshi Nagamochi;Toshihide Ibaraki
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
60.Evaluation may be easier than generation (extended abstract)

机译：评估可能比生成更容易（扩展摘要）
- 作者：Moni Naor
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
61.The PL hierarchy collapses

机译：PL层级崩溃
- 作者：Mitsunori Ogihara
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
62.Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING

机译：由MAX CUT和COLORING产生的半确定程序的有效逼近算法
- 作者：Philip Klein;Hsueh-I Lu
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
63.A fast quantum mechanical algorithm for database search

机译：用于数据库搜索的快速量子力学算法
- 作者：Lov K. Grover
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
64.Constructing evolutionary trees in the presence of polymorphic characters

机译：在多态性特征存在下构建进化树
- 作者：Maria Bonet;Cynthia Phillips;Tandy J. Warnow;Shibu Yooseph
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
65.Towards a syntactic characterization of PTAS

机译：走向PTAS的句法表征
- 作者：Sanjeev Khanna;Rajeev Motwani
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
66.Robot navigation with range queries

机译：机器人导航与范围查询
- 作者：Dana Angluin;Jeffery Westbrook;Wenhong Zhu
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
67.Public vs. private coin flips in one round communication games (extended abstract)

机译：一轮交流游戏中的公共硬币与私人硬币翻转（扩展摘要）
- 作者：Ilan Newman;Mario Szegedy
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
68.On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets

机译：关于贝蒂数的界并计算半代数集的欧拉特征
- 作者：Saugata Basu
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
69.Purely functional representations of catenable sorted lists

机译：可连接排序列表的纯功能表示
- 作者：Haim Kaplan;Robert E. Tarjan
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
70.Fast algorithms for parametric scheduling come from extensions to parametric maximum flow

机译：参数调度的快速算法从扩展到参数最大流量
- 作者：S. Thomas McCormick
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
71.Efficiently four-coloring planar graphs

机译：高效的四色平面图
- 作者：Neil Robertson;Daniel P. Sanders;Paul Seymour;Robin Thomas
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
72.On the boosting ability of top-down decision tree learning algorithms

机译：自顶向下决策树学习算法的提升能力
- 作者：Michael Kearns;Yishay Mansour
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
73.Communication-efficient parallel sorting (preliminary version)

机译：通讯效率高的并行排序（初级版）
- 作者：Michael T. Goodrich
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年
74.A threshold of ln n for approximating set cover (preliminary version)

机译：接近套装覆盖率的ln n阈值（普通版）
- 作者：Uriel Feige
- 会议名称：《Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing》 | 1996年