位置：成果数据库 > 会议 > 会议详情页
Exponential Lower Bounds for the PPSZ k-SAT Algorithm
  • 所属机构名称：清华大学
  • 会议名称：The 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
  • 时间：2013.1.6
  • 成果类型：会议
  • 相关项目：通讯、密码及量子信息之复杂性问题研究
作者： S. Chen|D. Scheder|N. Talebanfard|B. Tang|
同会议论文项目
通讯、密码及量子信息之复杂性问题研究
期刊论文 79 会议论文 133
同项目会议论文
Mechanism Design for Route Allocation in Multiple-commodity Network
Streaming and Communication Complexity of Clique Approximation
Path-Loss Fluctuations: Towards Robust Scheduling Algorithms in the SINR Model
PEV-based Reactive Power Compensation for Wind DG Units: A Stackelberg Game Approach
A remark on one-wayness versus pseudorandomness
<span style="font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;font-siz
Lower Bounds for Testing Computability by Small Width OBDDs
Major Coefficients Recovery: a Compressed Data Gathering Scheme for Wireless Sensor Network
Short Propositional Refutations for Dense Random 3CNF Formulas
Controlling Infection by Blocking Nodes and Links Simultaneously
Wind Power Integration via Aggregator-Consumer Coordination: A Game Theoretic Approach
PEV-Based Combined Frequency and Voltage Regulation for Smart Grid
On Secure Two-party Integer Division
Energy Efficient Broadcast in Multiradio Multichannel Wireless Networks
For Robustness of Ultrasound TOA-based Indoor Localization
Polynomial-time isomorphism test for groups with no abelian normal subgroups
On Variants of the Spanning Star Forest Problem
When Backpressure Meets Predictive Scheduling
<span style="font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;font-siz
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
Reversing Longest Previous Factor Tables is Hard
Matroid and Knapsack Center Problems
Distributed Local Broadcasting Algorithms in the Physical Interference Model
Space-Efficient Approximation Scheme for Circular Earth Mover Distance
Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutation
Short Proofs for the Determinant Identities
Inferring Social Ties across Heterogenous Networks
Minimum Latency Aggregation Scheduling for Arbitrary Tree Topologies under the SINR Model
Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain
Randomized Communication Complexity for Linear Algebra Problems over Finite Fields
Fair and Resilient Incentive Tree Mechanisms
Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model
Space-Bounded Communication Complexity
The Preimage Security of Double-block-length Compression Functions
An O(logn) Distributed Approximation Algorithm for Local Broadcasting in Unstructured Wireless Netwo
Optimal Proportional Cake Cutting with Connected Pieces
Characterizing Search Intent Diversity into Click Models
Maximizing Network Lifetime Online by a Localized Probabilistic Cost-Balancing Algorithm
Minimizing Average Interference Through Topology Control
Distributed (&Delta;+1)-Coloring in the Physical Model
Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
<span style="font-family: ;" font-size:10.5pt;?=""><a href="http:/
<span style="font-family: ;" Calibri?,?sans-serif?;font-size:10.5pt;?="">&
<span style="font-family:&quot;TimesNewRoman&quot;,&quot;serif&quot;;font-si
Finding the Maximum Area Parallelogram in a Convex Polygon
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
Computationally-Fair Group and Identity-Based Key-Exchange
Improving Integer Security for Systems
Some remarks on the incompressibility of width-parameterized SAT instances
Efficient Data Gathering using Compressed Sparse Functions
Some Trade-off Results for Polynomial Calculus
Scalable Column Concept Determination for Web Tables Using Large Knowledge Bases
Tight Security Bounds for Key-Alternating Ciphers
Efficient information exchange in single-hop multi-channel radio networks
Reducing Information Gathering Latency through Mobile Aerial Sensor Network
Efficient Distributed Multiple-Message Broadcasting in Unstructured Wireless Networks
Deterministic Distributed Data Aggregation under the SINR model
Dynamic Contention Resolution in Multiple-Access Channels
Tracking States of Electrical Appliances by Lightweight Metering and Sequence Decoding
PIKM 2014: The 7th ACM Workshop for Ph.D. Students in Information and Knowledge Management
<span style="color: rgb(0, 112, 192); font-family: ;" Calibri?,?sans-serif?;font-size:1
Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture
Who will follow you back? Reciprocal Relationship Prediction
Polynomial-time isomorphism test for groups with abelian Sylow towers
Budget feasible mechamism design: From prior-free to Bayesian
The Collision Security of Tandem-DM in the Ideal Cipher Model
Detecting Community Kernels in Large Social Networks
Streaming Algorithms with One-Sided Estimation
The Algorithmic Complexity of k-Domatic Partition of Graphs
Software Fault Isolation with API Integrity and Multi-principal Modules
Characterizing Inverse Time Dependency in Multi-class Learning
Dual-pricing Policy for Controller-side Strategies in Demand Side Management
An Efficient Rational Secret Sharing Scheme Based on the Chinese Remainder Theorem
Quantum Error-Correcting Codes for Amplitude Damping
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=2VnqvpchjSV5jd_uBIfPgmzsKF8Oxlwo
Stam&rsquo;s Conjecture and Threshold Phenomena in Collision Resistance
To Hash or Not to Hash Again? (In)differentiability Result for H^2 and HMAC
Smart Meter Deployment Optimization for Efficient Electrical Appliance State Monitoring
LMP-based Real Time Pricing for Optimal Capacity Planning with Maximal Wind Power Integration
Tracking States of Massive Electrical Appliances by Lightweight Metering and Sequence Decoding
Complexity of Connectivity in Cognitive Radio Networks through Spectrum Assignment
Computationally Limited Randomness
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=FVfJjE1mYfuWScoz_ylM99DkBWcqzGh7
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=UvRbjaTZtqEAcLHJ6TSyhYKAUNcwlq_I
<span style="background:red;font-family:&quot;Calibri&quot;,&quot;sans-serif&
Generating Chinese Classical Poems with Statistical Machine Translation Models
<span style="background: red; font-family: ;" Calibri?,?sans-serif?;font-size:10.5pt;?=
<span style="font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;font-siz
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=VRJnc1k74WGvMwq8arEObHAJnQZnPYLJ
Overcoming Weak Expectations
An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=LKo6lIe4nrugB4AeoG1NJPCZvwePnWQm
Complexity of Total {k}-Domination and Related Problems
<span style="font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;font-siz
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=0Y_I2DXaRRIbA11uZRDEW_DqsqsQKkIk
Leakage-Resilient Symmetric Cryptography Under Empirically Verifiable Assumptions
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
<span style="font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;font-siz
<span style="font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;font-siz
<span style="color: rgb(0, 112, 192); font-family: ;" Calibri?,?sans-serif?;font-size:1
Property Testing Lower Bounds via Communication Complexity
Limits on the Stretch of Non-Adaptive Constructions of Pseudo-Random Generators
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=lsTZdaBYEheFMRF_VIGdZQ9q5lgvAcqN
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=eegvs128nPz5zw6-2T7vFiz6IXGlsl2N
<a href="http://iiis.tsinghua.edu.cn/mydownload.php?fileurl=RjLnGTzdqAR15x1ynn-waQPwkT1_SJUM
On isomorphism testing of groups with normal hall subgroups
Exact Parameterized Multilinear Monomial Counting via k-layer Subset Convolution and k-Disjoint Sum
EIM: Efficient online Interference Measurement in Wireless Sensor Networks
Is global asymptotic cloning state estimation?
Demand Side Management for Wind Power Integration in Microgrid Using Dynamic Potential Game Theory
Pseudorandomness for Read-once Formulas
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
<span style="font-family: ;" Calibri?,?sans-serif?;font-size:10.5pt;?="">&
<span style="font-family:&quot;TimesNewRoman&quot;,&quot;serif&quot;;font-si
<span style="font-family:&quot;TimesNewRoman&quot;,&quot;serif&quot;;font-si
<span style="font-family:&quot;TimesNewRoman&quot;,&quot;serif&quot;;font-si
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
<span style="color: rgb(0, 112, 192); font-family: ;" Calibri?,?sans-serif?;font-size:1
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
<span style="color:#0070C0;font-family:&quot;Calibri&quot;,&quot;sans-serif&
Nearly Optimal Asynchronous Blind Rendezvous Algorithm for Cognitive Radio Networks
Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness
On the Need of Physical Security for Small Embedded Devices: a Case Study with COMP128-1 Implementat
Optimal Allocation for Chunked-Reward Advertising.
Ranking with Diverse Intents and Correlated Contents
Stochastic Combinatorial Optimization via Poisson Approximation
OAKE: A New Family of Implicitly Authenticated Diffie-Hellman Protocols.Berlin, Germany, November 4-
Egalitarian Pairwise Kidney Exchange: Fast Algorithms via Linear Programming and Parametric Flow
Power Distribution Network Reconfiguration for Bounded Transient Power Loss
Predicting Drug-Target Interactions Using Restricted Boltzmann Machines