首页>外文会议>International colloquium on automata, languages and programming;ICALP 2011

International colloquium on automata, languages and programming;ICALP 2011

召开年：2011
召开地：Zurich(CH);Zurich(CH)
出版时间：-

会议文集：-

会议论文

热门论文

全部论文

全选（0）

1.Steiner Transitive-Closure Spanners of Low-Dimensional Posets

机译：低维Poset的Steiner透射闭合扳手
- 作者：Piotr Berman;Arnab Bhattacharyya;Elena Grigorescu;Sofya Raskhodnikova;David P. Woodruff;Grigory Yaroslavtsev
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
2.Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere

机译：通过最小跨度球解决色锥聚类问题
- 作者：Hu Ding;Jinhui Xu
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- high dimension;
- chromatic;
- clustering;
- core-set;
3.Clustering with Local Restrictions

机译：具有局部限制的聚类
- 作者：Daniel Lokshtanov;Daniel Marx
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
4.Popular Matchings in the Stable Marriage Problem

机译：稳定婚姻问题中的热门匹配
- 作者：Chien-Chung Huang;Telikepalli Kavitha
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
5.VC-Dimension and Shortest Path Algorithms

机译：VC维和最短路径算法
- 作者：Ittai Abraham;Daniel Delling;Amos Fiat;Andrew V. Goldberg;Renato F. Werneck
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
6.Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices

机译：分布格的中心稳定匹配和覆盖图的中心
- 作者：Christine Cheng;Eric McDermid;Ichiro Suzuki
- 会议名称：《》 | 2011年
- stable matching;
- fairness;
- median;
- center;
- partially ordered set;
- distributive lattice;
- hypercube;
7.The Complexity of Symmetric Boolean Parity Holant Problems(Extended Abstract)

机译：对称布尔奇偶校验Holant问题的复杂性（扩展摘要）
- 作者：Heng Guo;Pinyan Lu;Leslie G. Valiant
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
8.Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth

机译：永久性没有深度的多项式大小简洁的算术电路
- 作者：Maurice Jansen;Rahul Santhanam
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
9.Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

机译：平面图上节点加权Steiner森林的本原对偶近似算法
- 作者：Carsten Moldenhauer
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
10.Improved Approximation for the Directed Spanner Problem

机译：有向扳手问题的改进近似
- 作者：Piotr Berman;Arnab Bhattacharyya;Konstantin Makarychev;Sofya Raskhodnikova;Grigory Yaroslavtsev
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
11.An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity(Extended Abstract)

机译：最小成本子集k连通性的一种改进的近似算法（扩展摘要）
- 作者：Bundit Laekhanukit
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
12.The Decimation Process in Random k-SAT

机译：随机k-SAT中的抽取过程
- 作者：Amin Coja-Oghlan;Angelica Y. Pachon-Pinzon
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
13.Approximation Schemes for Capacitated Geometric Network Design

机译：电容几何网络设计的近似方案
- 作者：Anna Adamaszek;Artur Czumaj;Andrzej Lingas;Jakub Onufry Wojtaszczyk
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
14.An O(log n)-Competitive Algorithm for Online Constrained Forest Problems

机译：在线约束森林问题的O（log n）竞争算法
- 作者：Jiawei Qian;David P. Williamson
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
15.On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity

机译：下界方法对单向量子通信复杂性的影响
- 作者：Shengyu Zhang
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
16.Advice Coins for Classical and Quantum Computation

机译：古典和量子计算的建议币
- 作者：Scott Aaronson;Andrew Drucker
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- BQP;
- finite automata;
- finite-precision arithmetic;
- PSPACE;
- quantum computation;
- root-finding.;
17.Quantum Commitments from Complexity Assumptions

机译：复杂性假设下的量子承诺
- 作者：Andre Chailloux;Iordanis Kerenidis;Bill Rosgen
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
18.Limitations on Quantum Dimensionality Reduction

机译：减少量子维数的限制
- 作者：Aram W. Harrow;Ashley Montanaro;Anthony J. Short
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
19.On Tree-Constrained Matchings and Generalizations

机译：关于树约束的匹配和推广
- 作者：Stefan Canzar;Khaled Elbassioni;Gunnar W. Klau;Julian Mestre
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
20.Tight Bounds for Linkages in Planar Graphs

机译：平面图中链接的紧边界
- 作者：Isolde Adler;Stavros G. Kolliopoulos;Philipp Klaus Krause;Daniel Lokshtanov;Saket Saurabh;Dimitrios Thilikos
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
21.A Tighter Insertion-Based Approximation of the Crossing Number

机译：交叉数的基于更紧密插入的近似
- 作者：Markus Chimani;Petr Hlineny
- 会议名称：《》 | 2011年
22.Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs

机译：平面图，有界图和次要图的线性空间近似距离Oracle
- 作者：Ken-ichi Kawarabayashi;Philip N. Klein;Christian Sommer
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
23.Stochastic Mean Payoff Games:Smoothed Analysis and Approximation Schemes

机译：随机平均收益博弈：平滑的分析和近似方案
- 作者：Endre Boros;Khaled Elbassioni;Mahmoud Fouz;Vladimir Gurvich;Kazuhisa Makino;Bodo Manthey
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
24.Pairwise-Interaction Games

机译：双向互动游戏
- 作者：Martin Dyer;Velumailum Mohanaraj
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- nash equilibrium;
- graphical game;
- computational complexity;
- pairwise interaction;
25.Settling the Complexity of Local Max-Cut (Almost) Completely

机译：完全解决（几乎）局部最大剪切的复杂性
- 作者：Robert Elsaesser;Tobias Tscheuschner
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- Max-Cut;
- PLS;
- graphs;
- local search;
- smoothed complexity;
26.Clique Clustering Yields a PTAS for max-Coloring Interval Graphs

机译：Clique聚类产生最大着色间隔图的PTAS
- 作者：Tim Nonner
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
27.On Variants of File Caching

机译：关于文件缓存的变体
- 作者：Leah Epstein;Csanad Imreh;Asaf Levin;Judit Nagy-Gyoergy
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
28.On the Advice Complexity of the k-Server Problem

机译：关于k服务器问题的咨询复杂性
- 作者：Hans-Joachim Boeckenhauer;Dennis Komm;Rastislav Kralovic;Richard Kralovic
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
29.Sleep Management on Multiple Machines for Energy and Flow Time

机译：在多台机器上进行睡眠管理以获取能量和流动时间
- 作者：Sze-Hang Chan;Tak-Wah Lam;Lap-Kei Lee;Chi-Man Liu;Hing-Fung Ting
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
30.Meeting Deadlines: How Much Speed Suffices?

机译：达到最后期限：多少速度足够？
- 作者：S. Anand;Naveen Garg;Nicole Megow
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
31.Range Majority in Constant Time and Linear Space

机译：恒定时间和线性空间中的范围多数
- 作者：Stephane Durocher;Meng He;J. Ian Munro;Patrick K. Nicholson;Matthew Skala
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
32.Dynamic Planar Range Maxima Queries

机译：动态平面范围最大值查询
- 作者：Gerth Stolting Brodal;Konstantinos Tsakalidis
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
33.Compact Navigation and Distance Oracles for Graphs with Small Treewidth

机译：具有小树宽的图形的紧凑导航和距离Oracle
- 作者：Arash Farzan;Shahin Kamali
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
34.Player-Centric Byzantine Agreement

机译：以玩家为中心的拜占庭协议
- 作者：Martin Hirt;Vassilis Zikas
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
35.Limits on the Computational Power of Random Strings

机译：随机字符串计算能力的限制
- 作者：Eric Allender;Luke Friedman;William Gasarch
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
36.Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority

机译：递归多数的随机决策树复杂度的改进界
- 作者：Frederic Magniez;Ashwin Nayak;Miklos Santha;David Xiao
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
37.The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions

机译：某些布尔函数的傅里叶熵影响猜想
- 作者：Ryan ODonnell;John Wright;Yuan Zhou
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
38.Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm(Extended Abstract)

机译：通过结构连续贪婪算法进行非单调子模最大化（扩展摘要）
- 作者：Moran Feldman;Joseph (Seffi) Naor;Roy Schwartz
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
39.Submodular Cost Allocation Problem and Applications

机译：次模块成本分配问题及其应用
- 作者：Chandra Chekuri;Alina Ene
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
40.Maximizing Polynomials Subject to Assignment Constraints

机译：最大化受分配约束的多项式
- 作者：Konstantin Makarychev;Maxim Sviridenko
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
41.Robust Independence Systems

机译：强大的独立系统
- 作者：Naonori Kakimura;Kazuhisa Makino
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- independence systems;
- matroids;
- exchangeability;
- robustness;
42.Buyback Problem - Approximate Matroid Intersection with Cancellation Costs

机译：回购问题-具有取消成本的近似Matroid相交
- 作者：Ashwinkumar Badanidiyuru Varadaraja
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
43.Tamper-Proof Circuits:How to Trade Leakage for Tamper-Resilience

机译：防篡改电路：如何利用泄漏进行防篡改
- 作者：Sebastian Faust;Krzysztof Pietrzak;Daniele Venturi
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
44.Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds

机译：精确的学习算法，博彩游戏和巡回赛下限
- 作者：Ryan C. Harkins;John M. Hitchcock
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
45.New Algorithms for Learning in Presence of Errors

机译：存在错误时的新学习算法
- 作者：Sanjeev Arora;Rong Ge
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
46.Constraint Satisfaction Parameterized by Solution Size

机译：通过解决方案大小参数化的约束满意度
- 作者：Andrei A. Bulatov;Daniel Marx
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
47.Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

机译：树宽预处理：通过内核化的组合分析
- 作者：Hans L. Bodlaender;Bart M.P. Jansen;Stefan Kratsch
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
48.Subset Feedback Vertex Set Is Fixed-Parameter Tractable

机译：子集反馈顶点集是固定参数可操作的
- 作者：Marek Cygan;Marcin Pilipczuk;Michal Pilipczuk;Jakub Onufry Wojtaszczyk
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
49.Domination When the Stars Are Out

机译：星星消失时的统治
- 作者：Danny Hermelin;Matthias Mnich;Erik Jan van Leeuwen;Gerhard J. Woeginger
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
50.A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

机译：代码问题的最小距离的简单确定性减少
- 作者：Per Austrin;Subhash Khot
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
51.Recoverable Values for Independent Sets

机译：独立集的可恢复值
- 作者：Uriel Feige;Daniel Reichman
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
52.Vertex Cover in Graphs with Locally Few Colors

机译：局部颜色较少的图形中的顶点覆盖
- 作者：Fabian Kuhn;Monaldo Mastrolilli
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- approximation;
- local coloring;
- scheduling;
- vertex cover;
53.A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid

机译：用于估计规则拟阵上铁磁Ising模型分配函数的多项式时间算法
- 作者：Leslie Ann Goldberg;Mark Jerrum
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
54.Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width

机译：有界树宽图上子集Glauber动力学的快速混合
- 作者：Magnus Bordewich;Ross J. Kang
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- markov chain monte carlo;
- graph polynomials;
- subset expansion;
- tree-width;
- canonical paths;
- randomised approximation schemes;
- rapid mixing;
55.Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems(Extended Abstract)

机译：通过约束满足问题表征算术电路类（扩展摘要）
- 作者：Stefan Mengel
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
56.On the Power of Algebraic Branching Programs of Width Two

机译：关于宽度为2的代数分支程序的幂
- 作者：Eric Allender;Fengming Wang
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
57.Efficient Sample Extractors for Juntas with Applications

机译：用于Juntas的高效样品提取器及其应用
- 作者：Sourav Chakraborty;David Garcia-Soriano;Arie Matsliah
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- property testing;
- sample extractors;
- implicit learning;
58.Robust Simulations and Significant Separations

机译：稳健的仿真和有效的分离
- 作者：Lance Fortnow;Rahul Santhanam
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
59.Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications(Extended Abstract)

机译：高效可解码的纠错列表分离矩阵及其应用（扩展摘要）
- 作者：Hung Q. Ngo;Ely Porat;Atri Rudra
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
60.A PCP Characterization of AM

机译：AM的PCP表征
- 作者：Andrew Drucker
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
- arthur-merlin games;
- PCPs;
- average-case complexity;
61.Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model

机译：Cell-Probe模型中在线整数乘法和卷积的下界
- 作者：Raphaeel Clifford;Markus Jalsenius
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
62.Automatizability and Simple Stochastic Games

机译：可自动化性和简单的随机游戏
- 作者：Lei Huang;Toniann Pitassi
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
63.Exponential Lower Bounds for AC°-Frege Imply Superpolynomial Frege Lower Bounds

机译：AC°-Frege的指数下界表示超多项式Frege下界
- 作者：Yuval Filmus;Toniann Pitassi;Rahul Santhanam
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
64.Parameterized Bounded-Depth Frege Is Not Optimal

机译：参数化的边界深度镶边不是最佳的
- 作者：Olaf Beyersdorff;Nicola Galesi;Massimo Lauria;Alexander Razborov
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
65.On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution

机译：k-DNF分辨率的最小不满足和时空权衡
- 作者：Jakob Nordstroem;Alexander Razborov
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年
66.Sorting by Transpositions Is Difficult

机译：按换位排序很困难
- 作者：Laurent Bulteau;Guillaume Fertin;Irena Rusu
- 会议名称：《International colloquium on automata, languages and programming;ICALP 2011》 | 2011年