Despite decades of effort, a persistent chasm has existed between the theory and practice of device-level biometric authentication. Theoretical constructions can, in principle, provide biometric authentication with cryptographically secure public enrollment data. However, concrete implementations of these techniques have failed to provide security with real-world parameters. The result is that deployed authentication algorithms rely on data that overtly leaks private information about the biometric; thus systems rely on externalized security measures such as trusted execution environments.

Layer-two blockchain protocols emerged to address scalability issues related to fees, storage cost, and confirmation delay of on-chain transactions. They aggregate off-chain transactions into fewer on-chain ones, thus offering immediate settlement and reduced transaction fees. To preserve security of the underlying ledger, layer-two protocols often work in a collateralized model; resources are committed on-chain to backup off-chain activities. A fundamental challenge that arises in this setup is determining a policy for establishing, committing, and replenishing the collateral in a way that maximizes the value of settled transactions. In this paper, we study this problem under two settings that model collateralized layer-two protocols. The first is a general model in which a party has an on-chain collateral C with a policy to decide on whether to settle or discard each incoming transaction. The policy also specifies when to replenish C based on the remaining collateral value. The second model considers a discrete setup in which C is divided among k wallets, each of which is of size C/k, such that when a wallet is full, and so cannot settle any incoming transactions, it will be replenished. We devise several online policies for these models, and show how competitive they are compared to optimal (offline) policies that have full knowledge of the incoming transaction stream. To the best of our knowledge, we are the first to study and formulate online competitive policies for collateral and wallet management in the blockchain setting.

Permissionless distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties-consistency and liveness-can be guaranteed under specific constraints on the resources available to an adversary relative to the resources of the participants that follow the protocol. Given their permissionless participation convention and their intended long-livedness, a critical open security question is their behavior-and potential resilience-to temporary spikes in adversarial resources. In this work we give the first thorough treatment of the self-healing properties of Nakamoto ledgers, addressing both proof-of-work (PoW) and proof-of-stake (PoS) protocols. First, we present a unified model that allows us to define self-healing for both of these protocol classes. Then we provide a formal analysis establishing self-healing with respect to both consistency and liveness in both classes, quantifying the resulting vulnerability period as a function of the magnitude of the spike. Finally, we provide numerical simulations giving explicit quantitative bounds relevant for practice.

We study the problem of committee selection in the context of proof-of-stake consensus mechanisms or distributed ledgers. These settings determine a family of participating parties---each of which has been assigned a non-negative ''stake''---and are subject to an adversary that may corrupt a subset of the parties. The challenge is to select a committee of participants that accurately reflects the proportion of corrupt and honest parties, as measured by stake, in the full population. The trade-off between committee size and the probability of selecting a committee that over-represents the corrupt parties is a fundamental factor in both security and efficiency of proof-of-stake consensus, as well as committee-run layer-two protocols.

We describe and analyze a simple protocol for$n$parties that implements a randomness beacon: a sequence of high entropy values, continuously emitted at regular intervals, with sub-linear communication per value. The algorithm can tolerate a$(1-\epsilon)/2$fraction of the$n$players to be controlled by an adaptive adversary that may deviate arbitrarily from the protocol. The randomness mechanism relies on verifiable random functions (VRF), modeled as random functions, and effectively stretches an initial$\lambda$-bit seed to an arbitrarily long public sequence so that (i) with overwhelming probability in k-the security parameter-each beacon value has high min-entropy conditioned on the full history of the algorithm, and (ii) the total work and communication required per value is$O(k)$cryptographic operations. The protocol can be directly applied to provide a qualitative improvement in the security of several proof-of-stake blockchain algorithms, rendering them safe from “grinding” attacks.

Risk-limiting audits (RLAs) are rigorous statistical procedures meant to detect invalid election results. RLAs examine paper ballots cast during the election to statistically assess the possibility of a disagreement between the winner determined by the ballots and the winner reported by tabulation. The design of an RLA must balance risk against efficiency: "risk" refers to a bound on the chance that the audit fails to detect such a disagreement when one occurs; "efficiency" refers to the total effort to conduct the audit.The most efficient approaches—when measured in terms of the number of ballots that must be inspected—proceed by "ballot comparison." However, ballot comparison requires an (untrusted) declaration of the contents of each cast ballot, rather than a simple tabulation of vote totals. This "cast-vote record table" (CVR) is then spot-checked against ballots for consistency. In many practical settings, the cost of generating a suitable CVR dominates the cost of conducting the audit which has prevented widespread adoption of these sample-efficient techniques.We introduce a new RLA procedure: an "adaptive ballot comparison" audit. In this audit, a global CVR is never produced; instead, a three-stage procedure is iterated: 1) a batch is selected, 2) a CVR is produced for that batch, and 3) a ballot within the batch is sampled, inspected by auditors, and compared with the CVR. We prove that such an audit can achieve risk commensurate with standard comparison audits while generating a fraction of the CVR. We present three main contributions: (1) a formal adversarial model for RLAs; (2) definition and analysis of an adaptive audit procedure with rigorous risk limits and an associated correctness analysis accounting for the incidental errors arising in typical audits; and (3) an analysis of efficiency.

One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which-in Satoshi Nakamoto's own words-rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world implementations of peer-topeer gossip-style networks used by blockchain protocols rely on a number of ad-hoc attack mitigation strategies that leave a glaring gap between the idealized communication layer assumed in formal security arguments for blockchains and the real world, where a wide array of attacks have been showcased.

Nakamoto proof-of-work ledger consensus currently underlies the majority of deployed cryptocurrencies and smart-contract blockchains. While a long and fruitful line of work has succeeded to identify its exact security region---that is, the set of parametrizations under which it possesses asymptotic security---the existing theory does not provide concrete settlement time guarantees that are tight enough to inform practice.

Neighbor discovery on duty-cycled mobile devices in group settings arises in many applications. In such scenarios, it is sufficient for an arbitrary node in a group to discover a new node. While pairwise neighbor discovery schemes can be directly applied to group settings, their performance can be severely limited as they are not designed to coordinate the efforts of group members. Explicit coordination among the group members, however, can incur large overhead in mobile networks, where the group membership changes dynamically over time. In this paper, we focus on schemes that require no explicit communication among the group members, and nodes follow deterministic schedules that can be succinctly represented. We first define the notion ofideal duty cyclefor a group, and then develop two deterministic neighbor discovery schemes for group settings, and show that both of them achieve effective duty cycle close to the ideal duty cycle. In addition, we show that the schemes are lightweight and easy to implement using experiments in a testbed. Last, we use a case study to demonstrate the usage of our proposed schemes and show that a simple enhancement leveraging the deterministic nature of the schemes leads to significant performance improvement, at the cost of only slight extra overhead.

Recent studies have demonstrated that geographic location features collected using smartphones can be a powerful predictor for depression. While location information can be conveniently gathered by GPS, typical datasets suffer from significant periods of missing data due to various factors (e.g., phone power dynamics, limitations of GPS). A common approach is to remove the time periods with significant missing data before data analysis. In this paper, we develop an approach that fuses location data collected from two sources: GPS and WiFi association records, on smartphones, and evaluate its performance using a dataset collected from 79 college students. Our evaluation demonstrates that our data fusion approach leads to significantly more complete data. In addition, the features extracted from the more complete data present stronger correlation with self-report depression scores, and lead to depression prediction with much higher$F_1$scores (up to 0.76 compared to 0.5 before data fusion). We further investigate the scenario when including an additional data source, i.e., the data collected from a WiFi network infrastructure. Our results show that, while this additional data source leads to even more complete data, the resultant$F_1$scores are similar to those when only using the location data (i.e., GPS and WiFi association records) from the phones.

We establish the optimal security threshold for the Bitcoin protocol in terms of adversarial hashing power, honest hashing power, and network delays. Specifically, we prove that the protocol is secure if [ra < 1/Δ0 + 1/rh,,] where rh is the expected number of honest proof-of-work successes in unit time, ra is the expected number of adversarial successes, and no message is delayed by more than Δ0 time units. In this regime, the protocol guarantees consistency and liveness with exponentially decaying failure probabilities. Outside this region, the simple private chain attack prevents consensus. Our analysis immediately applies to any Nakamoto-style proof-of-work protocol; in the full version of this paper we also present the adaptations needed to apply it in the proof-of-stake setting, establishing a similar threshold there.

We improve the fundamental security threshold of eventual consensus Proof-of-Stake (PoS) blockchain protocols under the longest-chain rule by showing, for the first time, the positive effect of rounds with concurrent honest leaders. Current security analyses reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three events associated with a round: (i) event A: at least one adversarial leader, (ii) event S: a single honest leader, and (iii) event M: multiple, but honest, leaders. We present an asymptotically optimal consistency analysis assuming that an honest round is more likely than an adversarial round (i.e., Pr[S]+Pr[M] > Pr[A]); this threshold is optimal. This is a first in the literature and can be applied to both the simple synchronous communication as well as communication with bounded delays.In all existing consistency analyses, event M is either penalized or treated neutrally. Specifically, the consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that Pr[S] - Pr[M] > Pr[A]; the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that Pr[S] > Pr[A]. Moreover, all existing analyses completely break down when Pr[S] <; Pr[A]. These thresholds determine the critical trade-off between the honest majority, network delays, and consistency error.Our new results can be directly applied to improve the security guarantees of the existing protocols. We also complement these results by analyzing the setting where S is rare, even allowing Pr[S] = 0, under the added assumption that honest players adopt a consistent chain selection rule.

Soft robotic pneumatic grippers have been shown to be versatile, robust to impacts, and safe for use on delicate objects. One type, fluidic elastomer grippers, are characterized by fingers with an inextensible gripping surface backed by extensible pneumatic chambers; when inflated, this mismatch in extensibility results in the finger curling. However, one drawback of these simple fingers is that they have one preprogrammed grasp, usually a simple constant-curvature wrap. While well-suited for finger-sized round objects, they do not grasp flat or small objects well. Here, we present an adaptable tri-stable soft robotic finger that can form either a pinch or wrap grasp based on the shape of the grasped object. We enable this by incorporating two bi-stable springs into the inextensible layer. The three stable positions are: i) open (unpressurized), ii) pinch (with only the proximal section bending), and iii) wrap (with the entire finger bending). We present a simple model of the behavior of our finger and experimental results verifying the model. Further, we apply forces and moments to grasped objects, and show that the tri-stable finger increases the grasping performance when compared to a control gripper with equal gripping force. Our work presents a novel design modification that is unobtrusive, simple, and passive. Our introduction of inexpensive programmable hardware advances the versatility and adaptability of soft grippers.

The blockchain data structure maintained via the longest-chain rule—popularized by Bitcoin—is a powerful algorithmic tool for consensus algorithms. Such algorithms achieve consistency for blocks in the chain as a function of their depth from the end of the chain. While the analysis of Bitcoin guarantees consistency with error 2−k for blocks of depth O(k), the state-of-the-art of proof-of-stake (PoS) blockchains suffers from a quadratic dependence on k: these protocols, exemplified by Ouroboros (Crypto 2017), Ouroboros Praos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017), can only establish that depth Θ(k2) is sufficient. Whether this quadratic gap is an intrinsic limitation of PoS—due to issues such as the nothing-at-stake problem—has been an urgent open question, as deployed PoS blockchains further rely on consistency for protocol correctnes. We give an axiomatic theory of blockchain dynamics that permits rigorous reasoning about the longest-chain rule and achieve, in broad generality, Θ(k) dependence on depth in order to achieve consistency error 2−k In particular, for the first time we show that PoS protocols can match proof-of-work protocols for linear consistency. We analyze the associated stochastic process, give a recursive relation for the critical functionals of this process, and derive tail bounds in both i.i.d. and martingale settings via associated generating functions.

Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery on duty-cycled mobile devices. Most existing studies develop integer schedules where time proceeds in discrete slots and a node is awake or asleep for an entire slot duration. We show that integer schedules can lead to significant waste of resources, and develop a generalized non-integer model, where time is continuous and a node may become awake or asleep at any point of time (subject to a few constraints) so that the resultant schedules can be significantly more efficient than integer schedules. In addition, we provide a reduction that transforms any schedule in the integer model to a corresponding schedule in the generalized non-integer model while reducing the discovery latency by up to a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. We further demonstrate the practicality of non-integer schedules in a testbed, and compare the worst-case discovery latency of several existing schemes under both integer and non-integer models. Last, we establish a family of lower bounds for the best achievable latency guarantee. These lower bounds are applicable to both integer and non-integer models, covering both symmetric and asymmetric settings, and encompassing the existing lower bounds that are only for a subset of settings as special cases.

We present a novel Proof-of-Stake (PoS) protocol, Ouroboros Genesis, that enables parties to safely join (or rejoin) the protocol execution using only the genesis block information. Prior to our work, PoS protocols either required parties to obtain a trusted "checkpoint" block upon joining and, furthermore, to be frequently online or required an accurate estimate of the number of online parties to be hardcoded into the protocol logic. This ability of new parties to "bootstrap from genesis" was a hallmark property of the Bitcoin blockchain and was considered an important advantage of PoW-based blockchains over PoS-based blockchains since it facilitates robust operation in a setting with dynamic availability, i.e., the natural setting---without external trusted objects such as checkpoint blocks---where parties come and go arbitrarily, may join at any moment, or remain offline for prolonged periods of time. We prove the security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake in a partially synchronous network with unknown message delay and unknown, varying levels of party availability. Our security proof is in the Universally Composable setting assuming the most natural abstraction of a hash function, known as the strict Global Random Oracle (ACM-CCS 2014); this highlights an important advantage of PoS blockchains over their PoW counterparts in terms of composability with respect to the hash function formalisation: rather than a strict GRO, PoW-based protocol security requires a "local" random oracle. Finally, proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.

Notable recent security incidents have generated intense interest in adversaries which attempt to subvert---perhaps covertly---crypto\-graphic algorithms. In this paper we develop (IND-CPA) Semantically Secure encryption in this challenging setting. This fundamental encryption primitive has been previously studied in the "kleptographic setting," though existing results must relax the model by introducing trusted components or otherwise constraining the subversion power of the adversary: designing a Public Key System that is kletographically semantically secure (with minimal trust) has remained elusive to date. In this work, we finally achieve such systems, even when all relevant cryptographic algorithms are subject to adversarial (kleptographic) subversion. To this end we exploit novel inter-component randomized cryptographic checking techniques (with an offline checking component), combined with common and simple software engineering modular programming techniques (applied to the system's black box specification level). Moreover, our methodology yields a strong generic technique for the preservation of any semantically secure cryptosystem when incorporated into the strong kleptographic adversary setting.

k-HA (high-Availability) is an important faulttolerance property of VM placement in clouds and clusters - it is the ability to tolerate up to k host failures by relocating VMs from failed hosts without disrupting other VMs. It has long been assumed [1] that deciding the existence of a k-HA placement is ΣP 3 -hard. In a surprising yet simple result we show that k-HA reduces to multiple knapsack and hence is in NP= ΣP 1 . We propose a stochastic model for multiple knapsack that not only captures real-world workloads but also provides a uniform basis for comparing the efficiencies of different polynomial-time heuristics. We prove, using the central limit theorem and linear programming, that, there exists a best polynomial-time heuristic, albeit impractical from the standpoint of implementation. We turn to industry practice and discuss the drawbacks of commonly used heuristics-First- fit,Best-fit,Worst-fit,MTHM and CSP. Load-balancing is a fundamental customer requirement in industry. Based on a large real-world dataset of cluster workloads (from industry leader Nutanix) we show that the natural load-balancing heuristic - Water- filling - has several excellent properties. We compare and contrast Water-filling with MTHM using our stochastic model and find that Water-filling is a heuristic of choice.

This special section comprises ten fully refereed papers whose extended abstracts were presented at the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014) in Philadelphia, Pennsylvania, October 19--21, 2014. The unrefereed conference versions of these papers were published by IEEE in the FOCS 2014 proceedings. The regular conference program consisted of 68 papers chosen from among 273 submissions. These were selected by a program committee consisting of Scott Aaronson, Boaz Barak, Nikhil Bansal, Timothy Chan, Moses Charikar, Shuchi Chawla, Julia Chuzhoy, Andrew Drucker, Valerie King, Robert Kleinberg, Eyal Kushilevitz, James R. Lee, Aleksander Maͅdry, Raghu Meka, Ankur Moitra, Aaron Roth, Alexander Russell, David Steurer, Madhu Sudan, Kunal Talwar, Brent Waters, Ryan Williams, and David Woodruff. The program committee was chaired by Boaz Barak. The papers invited to this special section were also selected with the input of the program committee. The ten papers in this section span a broad range of topics, including fixed-parameter tractability, online algorithms, combinatorics, coding theory, sublinear algorithms, approximation algorithms, hardness of approximation, dynamic algorithms, algebraic complexity and probability theory. Each paper underwent an extensive refereeing process; we thank both the authors and the anonymous referees for their efforts. In addition, we would like to thank SICOMP Editor-in-Chief Leonard Schulman and SIAM Senior Publications Coordinator Heather Blythe for their help in preparing this special section.

We define and construct a novel pseudorandom tool, the Markovian hitter. Given an input sequence of n independent random bits, a Markovian hitter produces a sequence of pseudorandom samples in {0, 1}k, in an online fashion, that hits any subset W ⊂ {0, 1}k of size ∊2k with probability ≈ 1 – 2–(n–k)∊. This is comparable to the behavior of truly random samples or classical pseudorandom hitting sets. A Markovian hitter has an additional “Markovian” property of interest: each pseudorandom sample is a function of only the O(k) most recent bits of the input sequence (of random bits). Such Markovian properties are useful in distributed online settings. In particular, we apply Markovian hitters to obtain a new algorithm for the well-studied blind rendezvous problem for cognitive radios. This is the problem faced by two parties equipped with radios that can access channels in potentially different subsets, S1 and S2, of a universe of n channels. Their challenge is to discover each other (by tuning their radios to the same channel at the same time) as quickly as possible. In prior work [3] it was shown that deterministic schedules have a lower bound for rendezvous time of Ω(|S1| · |S2|). We beat this quadratic barrier by utilizing a public source of randomness in conjunction with a Markovian hitter to achieve rendezvous in expected time We counterbalance this result by establishing two lower bounds on expected rendezvous time: an bound for the setting with public randomness, and an Ω(|S1| · |S2|) bound in the setting with private randomness but no public randomness, which is a strengthening of the result for deterministic schedules.

We present a randomized algorithm for asynchronous task allocation, also known as the write-all or do-all problem. Our algorithm has work complexity O(n+k2log3k) with high probability, where n the number of tasks and k the number of processes that participate in the computation. Our solution uses O(n) shared memory space that supports atomic test-and-set operations and with high probability each participating process uses O(k) internal memory space. This is the first adaptive solution for the write-all problem that has work n plus some additive term which depends only on the number of participating processes k and not the size of the problem n.

Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery between duty-cycled mobile devices. Each node is duty-cycled, i.e., its radio may only be active for a small fraction of the time. The duty cycles of the nodes can be the same or different, leading to symmetric or asymmetric cases of the neighbor discovery problem. In addition, the setting is asynchronous, i.e., clocks of different nodes may not be synchronized. Most existing studies assume an integer model (where time proceeds in discrete steps); two recent studies break away from this assumption, which allows them to develop significantly more efficient schemes. Our study improves the state-of-the-art in three main fronts. Firstly, we develop a generalized non-integer model (where time is continuous) that permits unified treatment of the assumptions in existing studies. We also provide a reduction that transforms any schedule in the basic integer model to a corresponding schedule in the generalized non-integer model while improving the performance by a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. Thirdly, we establish a new family of lower bounds for the best achievable latency guarantee in the non-integer model. They are applicable to both symmetric and asymmetric settings, and encompass the lower bounds for the integer model as special cases. Finally, we develop a novel optimal construction based on Sidon sets for the symmetric setting. Our approach differs from the approaches taken by all existing studies, and provides a new direction for constructing neighbor discovery schedules.

Approximate algebraic structures play a defining role in additive number theory and have found remarkable applications to questions in theoretical computer science, including in pseudorandomness and probabilistically checkable proofs. Here we study approximate representations of finite groups: functions $\psi : G \to \textsf{U}_d$ such that $\Pr[\psi(xy) = \psi(x) \,\psi(y)]$ is large or, more generally, such that the expected $\ell_2$ norm squared $\mathbb{E}_{x,y} \left\| \psi(xy) - \psi(x) \,\psi(y) \right\|_2^2$ is small, where $x, y$ are uniformly random elements of the group $G$ and $\textsf{U}_d$ denotes the group of unitary operators on $\mathbb{C}^d$. We bound these quantities in terms of the ratio $d / d_{\min}$ where $d_{\min}$ is the dimension of the smallest nontrivial representation of $G$. As an application, we bound the extent to which a function $f:G \to H$ can be an approximate homomorphism where $H$ is another finite group. We show that if $H$'s representations are significantly smaller than $G$'s, no such $f$ can be much more homomorphic than a random function. These results demonstrate that if $G$ is quasi-random in the sense of Gowers, that is, if $d_{\min}$ is large, then $G$ cannot be embedded in a small number of dimensions, or in a less-quasi-random group, without significant distortion of $G$'s multiplicative structure. We also prove that our bounds are tight by showing that minors of genuine representations and their polar decompositions are essentially optimal approximate representations.

Subsets of $\mathbb{F}_2^n$ that are $\varepsilon$-biased, meaning that the parity of any set of bits is even or odd with probability $\varepsilon$ close to $1/2$, are powerful tools for derandomization. A simple randomized construction shows that such sets exist of size $O(n/\varepsilon^2)$, and known deterministic constructions achieve sets of size $O(n/\varepsilon^3)$, $O(n^2/\varepsilon^2)$, and $O((n/\varepsilon^2)^{5/4})$. Rather than derandomizing these sets completely in exchange for making them larger, we attempt a partial derandomization while keeping them small, constructing sets of size $O(n/\varepsilon^2)$ with as few random bits as possible. Equivalently, we construct small ensembles of error-correcting codes, most of which meet the Gilbert--Varshamov bound. The naive randomized construction requires $O(n^2/\varepsilon^2)$ random bits. We give two constructions. The first uses Nisan's space-bounded pseudorandom generator to partly derandomize the classic Wozencraft ensemble of error-correcting codes and requires $O(n \log (1/\varepsilon))$ bits. Our second construction requires $O(n \log (n/\varepsilon))$ bits; it adds randomness to a Legendre symbol construction of Alon, Goldreich, H\aastad, and Peralta and uses Weil sums to bound high moments of the bias.

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow packets from multiple simultaneous transmitters to be received successfully at a receiver. Starting with a clique of n nodes, we first analyze a simple Aloha-like algorithm and show that it takes Θ((n ln n)/k) time to discover all neighbors with high probability when allowing up to k simultaneous transmissions. We then design two adaptive neighbor discovery algorithms that dynamically adjust the transmission probability for each node. We show that the adaptive algorithms yield a Θ(ln n) improvement over the Aloha-like scheme for a clique with n nodes and are thus order-optimal. Finally, we analyze our algorithms in a general multi-hop network setting. We show an upper bound of O((Δ ln n)/k) for the Aloha-like algorithm when the maximum node degree is Δ, which is at most a factor ln n worse than the optimal. In addition, when Δ is large, we show that the adaptive algorithms are orderoptimal, i.e., have a running time of O(Δ/k) which matches the lower bound for the problem.

Blind rendezvous is a fundamental problem in cognitive radio networks. The problem involves a collection of agents (radios) that wish to discover each other (i.e., rendezvous) in the blind setting where there is no shared infrastructure and they initially have no knowledge of each other. Time is divided into discrete slots and spectrum is divided into discrete channels, [n] = 1, 2, ..., n. Each agent may access (or hop on) a single channel in a single time slot and two agents rendezvous when they hop on the same channel in the same time slot. The goal is to design deterministic channel hopping schedules for each agent so as to guarantee rendezvous between any pair of agents with access to overlapping sets of channels. The problem has three complicating considerations: first, the agents are asymmetric, i.e., each agent Ai only has access to a particular subset Si⊂ [n] of the channels and different agents may have access to different subsets of channels (clearly, two agents can rendezvous only if their channel subsets overlap), second, the agents are synchronous, i.e., they do not possess a common sense of absolute time, so different agents may commence their channel schedules at different times (they do have a common sense of slot duration), lastly, agents are anonymous i.e., they do not possess an identity, and hence the schedule for Ai must depend only on Si. Whether guaranteed blind rendezvous in the asynchronous model was even achievable was an open problem. In a recent breakthrough, two independent sets of authors, Shin et al. (Communications Letters, 2010) and Lin et al. (INFOCOM, 2011), gave the first constructions guaranteeing asynchronous blind rendezvous in O (n2) and O (n3) time, respectively. We present a substantially improved and conceptually simpler construction guaranteeing that any two agents, Ai, Aj, will rendezvous in O (|Si||Sj| log log n) time. Our results are the first that achieve nontrivial dependence on |Si|, the sizes of the sets of available channels. This allows us, for example, to save roughly a quadratic factor over the best previous results in the important case when channel subsets have constant size. We also achieve the best possible bound of O (1) rendezvous time for the symmetric situation, previous works could do no better than O (n). Using techniques from the probabilistic method and Ramsey theory we establish that our construction is nearly optimal: we show both an Ω (|Si||Sj|) lower bound and an Ω(log log n) lower bound when |Si|, |Sj| ≤ n/2.

Chang's lemma is a useful tool in additive combinatorics and the analysis of Boolean functions. Here we give an elementary proof using entropy. We obtain a tight constant and give a slight improvement in the case where the variables are highly biased.

This issue of SICOMP contains eight selected papers from the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010), held June 6--8, 2010, in Cambridge, Massachusetts. The STOC proceedings contained 78 papers, which the program committee selected from 279 submissions. The program committee consisted of Timothy Chan, Ken Clarkson, Constantinos Daskalakis, Irit Dinur, Faith Ellen, Alan Frieze, Parikshit Gopalan, Piotr Indyk, Valentine Kabanets, Yael Tauman Kalai, Howard Karloff, Robert Kleinberg, Assaf Naor, Noam Nisan, Chris Peikert, Jaikumar Radhakrishnan, Oded Regev, Alexander Russell, Leonard Schulman (chair), Aravind Srinivasan, Santosh Vempala, and Andrew Yao. Eight of the STOC papers appear in this special section, each expanded and subjected to the standard thorough reviewing process of the journal. They cover a diverse collection of topics: In “Improving Exhaustive Search Implies Superpolynomial Lower Bounds," R. Ryan Williams shows that there are natural problems in NP and BPP for which algorithms that improve over the naïve deterministic simulation even quite slightly, imply lower bounds such as NEXP $\not\in$ P/poly and LOGSPACE $\neq$ NP. Williams also proves certain unconditional time-space lower bounds for improving on exhaustive search; the length of the witness-string in some standard verification protocol is a key parameter here. In “An Effective Dichotomy for the Counting Constraint Satisfaction Problem," Martin Dyer and David Richerby consider the counting constraint satisfaction problem (\#CSP). This problem asks how many ways there are to satisfy a system of constraints on a set of variables, where a constraint is a relation chosen from a fixed finite set. This class is shown to have a decidable dichotomy, depending on the form of the relations. The dichotomy is that each problem in the class either is in FP or is \#P-complete, with no intermediate cases. In “Pseudorandom Generators for Polynomial Threshold Functions," Raghu Meka and David Zuckerman develop improved (and in many cases the first nontrivial) pseudorandom generators for low-degree polynomial threshold functions; related explicit constructions are also developed. A key ingredient is the use of invariance principles to construct pseudorandom generators. In “Local List-Decoding and Testing of Random Linear Codes from High Error," Swastik Kopparty and Shubhangi Saraf give efficient local list-decoding and testing algorithms for “sparse" random linear codes, and subexponential time algorithms for list-decoding random linear codes, which tolerate error rates approaching $1/2$. In “How to Compress Interactive Communication," Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao attack the important direct sum problem in communication complexity: is the complexity of evaluating $n$ copies of a function ever significantly less than $n$ times the complexity of evaluating it once? By defining a new notion of information cost for protocols --- the so-called internal information cost --- and providing new protocol compression schemes, they prove that computing $n$ copies of any function requires communicating at least $\sqrt{n}$ times as many bits as computing one copy of the function. In “A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations," Daniele Micciancio and Panagiotis Voulgaris provide the first $\exp(O(n))$-time algorithms for the closest vector problem (CVP) and shortest independent vectors problem (SIVP); their algorithm is, moreover, deterministic. Likewise they provide a deterministic algorithm for the shortest vector problem (SVP), whose $\exp(O(n))$ runtime is an improvement over the best known bounds for randomized algorithms. In “Perfect Matchings in $O(n \log n)$ Time in Regular Bipartite Graphs," Ashish Goel, Michael Kapralov, and Sanjeev Khanna provide a randomized algorithm that finds a perfect matching in a $d$-regular $n$-node bipartite graph in time $O(n \log n)$, notably, within time that may be sublinear in the input size and is independent of the degree. In “Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions," Iftach Haitner, Omer Reingold, and Salil Vadhan give a new construction of pseudorandom generators from one-way functions that both simplifies and tightens the acclaimed original construction of Hastad, Impagliazzo, Levin, and Luby. We thank the authors, the STOC program committee, the STOC external reviewers, and the journal referees for all their work to make this special issue possible.

We study the behavior of the A* search algorithm when coupled with a heuristic h satisfying (1-epsilon1)h*

Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671–697], we have known that the permanent of a matrix with entries in $\{0,1\}$ can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra $\mathcal{A}$ and considering the determinant of the resulting matrix. In the case where $\mathcal{A}$ is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first—and therefore the number of trials we need to obtain a good estimate of the permanent—is $(1 + O(1/d))^n$ when $\mathcal{A}$ is the algebra of $d \times d$ matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constant—the only case in which an efficient algorithm is known—we show that the critical ratio exceeds $2^{n} / n^{O(d)}$. Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group.

Large-scale storage systems are crucial components in data-intensive applications such as search engine clusters, video-on-demand servers, sensor networks and grid computing. A storage server typically consists of a set of storage devices. In such systems, data layouts may need to be reconfigured over time for load balancing or in the event of system failure/upgrades. It is critical to migrate data to their target locations as quickly as possible to obtain the best performance. Most of the previous results on data migration assume that each storage node can perform only one data transfer at a time. A storage node, however, can typically handle multiple transfers simultaneously and this can reduce the total migration time significantly. Moreover, storage devices tend to have heterogeneous capabilities as devices may be added over time due to storage demand increase. In this paper, we consider the heterogeneous data migration problem, where we assume that each storage node v has different transfer constraint cv, which represents how many simultaneous transfers v can handle. We develop algorithms to minimize the data migration time. We show that it is possible to find an optimal migration schedule when all cvs are even. Furthermore, though the problem is NP-hard in general, we give an efficient algorithm that offers a rigorous (1 + o(1))-approximation guarantee.

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow multiple packets to be received successfully at a receiver. More specifically, we design and analyze a series of randomized algorithms for neighbor discovery in MPR networks. We start with a simple Aloha-like algorithm that assumes synchronous node transmissions and the number of neighbors, n, is known. We show that the time for all the nodes to discover their respective neighbors is Θ(ln n) in an idealized MPR network that allows an arbitrary number of nodes to transmit simultaneously. In a more realistic scenario, in which no more than k nodes can transmit simultaneously, we show that the time to discover all neighbors is Θ(n ln n/k). When a node knows whether its transmission is successful or not (e.g., based on feedbacks from other nodes), we design an adaptive Aloha-like algorithm that dynamically determines the transmission probability for each node, and show that it yields a ln n improvement over the simple Aloha-like scheme. Last, we extend our schemes to take into account a number of practical considerations, such as lack of knowledge of the number of neighbors and asynchronous algorithm operation, while resulting in only a constant or log n factor slowdown in algorithm performance.

This work explores implementations of multiwriter/multi-reader (MWMR) atomic registers in asynchronous, crash-prone, message-passing systems with the focus on low latency and computational feasibility. The efficiency of atomic read/write register implementations is traditionally measured in terms of the latency of read and write operations. To reduce operation latency researchers focused on the communication costs, expressed as the number of communication round-trips (or rounds), often ignoring the computation costs. In this paper we consider efficiency of a register implementation in terms of both communication and computation costs. As of this writing, algorithm SFW is the sole known MWMR algorithm that allows single round read and write operations. The algorithm uses collections of intersecting sets (quorums), and to enable single round operations, SFW relies on the evaluation of certain predicates. We formulate a new combinatorial problem that captures the computational burden of evaluating the predicates in algorithm SFW and we show that it is NP-Complete. To make the evaluation of the predicates feasible, we present a polynomial log-approximation algorithm for this problem and we show how to use it with algorithm SFW. Then we present a new algorithm, called CWFR, that allows fast operations independently of the underlying quorum system construction. The algorithm implements two-round writes and allows reads to complete in a single round. We conclude with experimental evaluations of our algorithms obtained from simulations in NS2.

It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore et al. [2005] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Ω( n log n ) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because in general it seems hard to implement a given highly entangled measurement. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL( n ,F p m ) and G n where G is finite and satisfies a suitable property.

It is known that any quantum algorithm for graph isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across $\Omega(n\log n)$ coset states. One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's algorithm for the HSP in the dihedral group, in which quantum states are adaptively combined and measured according to the decomposition of tensor products into irreducible representations. This “quantum sieve” starts with coset states and works its way down toward representations whose probabilities differ depending on, for example, whether the hidden subgroup is trivial or nontrivial. In this paper we show that no such approach can produce a polynomial-time quantum algorithm for graph isomorphism. Specifically, we consider the natural reduction of graph isomorphism to the HSP over the wreath product $S_n\wr\mathbb{Z}_2$. Using a recently proved bound on the irreducible characters of $S_n$, we show that no algorithm in this family can solve graph isomorphism in less than $\mathrm{e}^{\Omega(\sqrt{n})}$ time, no matter what adaptive rule it uses to select and combine quantum states. In particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time $\mathrm{e}^{O(\sqrt{n\log n})}$.

Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z 2 n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G , this is the problem of recovering an involution m = ( m 1 ,…, m n ) ∈ G n from an oracle f with the property that f ( x ⋅ y ) = f ( x ) ⇔ y ∈ {1, m }. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G n , where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G n have a simple product structure, they share important representation--theoretic properties with the symmetric groups S n , where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called “standard method” requires highly entangled measurements on the tensor product of many coset states. In this article, we provide quantum algorithms with time complexity 2 O (√ n ) that recover hidden involutions m = ( m 1 ,… m n ) ∈ G n where, as in Simon's problem, each m i is either the identity or the conjugate of a known element m which satisfies κ( m ) = −κ(1) for some κ ∈ Ĝ . Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the “missing harmonic” approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.

In recent years, two distinct electronic voting technologies have been introduced and extensively utilized in election procedures: direct recording electronic systems and optical scan (OS) systems. The latter are typically deemed safer, as they inherently provide a voter-verifiable paper trail that enables hand-counted audits and recounts that rely on direct voter input. For this reason, OS machines have been widely deployed in the United States. Despite the growing popularity of these machines, they are known to suffer from various security vulnerabilities that, if left unchecked, can compromise the integrity of elections in which the machines are used. This article studies general auditing procedures designed to enhance the integrity of elections conducted with optical scan equipment and, additionally, describes the specific auditing procedures currently in place in the State of Connecticut. We present an abstract view of a typical OS voting technology and its relationship to the general election process. With this in place, we lay down a ldquotemporal-resourcerdquo adversarial model, providing a simple language for describing the disruptive power of a potential adversary. Finally, we identify how audit procedures, injected at various critical stages before, during, and after an election, can frustrate such adversarial interference and so contribute to election integrity. We present the implementation of such auditing procedures for elections in the State of Connecticut utilizing the Premiere (Diebold) AccuVote OS; these audits were conducted by the UConn VoTeR Center, at the University of Connecticut, on request of the Office of the Secretary of the State. We discuss the effectiveness of such procedures in every stage of the process and we present results and observations gathered from the analysis of past election data.

A fundamental problem in distributed computing is the problem of cooperatively executing a given set of tasks in a dynamic setting. The challenge is to minimize the total work done and to maintain efficiency in the face of dynamically changing processor connectivity. In this setting, work is defined as the total number of tasks performed (counting multiplicities) by all the processors during the course of the computation. In this scenario, we are given a set of t tasks that must be completed in a distributed setting by a set of p processors where the communication medium is subject to failures. We assume that the t tasks are similar, in that they require the same number of computation steps to finish execution. We further assume that the tasks are idempotent - executing a task multiple times has the same effect as a single execution of the task. The tasks have a dependency relationship defined among them captured by a task dependency graph.

The dramatic exponential speedups of quantum algorithms over their best existing classical counterparts were ushered in by the technique of Fourier sampling, introduced by Bernstein and Vazirani and developed by Simon and Shor into an approach to the hidden subgroup problem. This approach has proved successful for abelian groups, leading to efficient algorithms for factoring, extracting discrete logarithms, and other number-theoretic problems. We show, however, that this method cannot resolve the hidden subgroup problem in the symmetric groups, even in the weakest, information-theoretic sense. In particular, we show that the Graph Isomorphism problem cannot be solved by this approach. Our work implies that any quantum approach based upon the measurement of coset states must depart from the original framework by using entangled measurements on multiple coset states.

Special purpose trusted computing devices are currently being deployed to offer many services for which the general purpose computing paradigm is unsuitable. The nature of the services offered by many of these devices demand high security and reliability, as well as low cost and low power consumption. Electronic Voting machines is a canonical example of this phenomenon. With electronic voting machines currently being used in much of the United States and several other countries, there is a strong need for thorough security evaluation of these devices and the procedures in place for their use. In this work, we first put forth a general framework for special purpose trusted computing devices. We then focus on Optical Scan (OS) electronic voting technology as a specific instance of this framework. OS terminals are a popular e-voting technology with the decided advantage of a user-verified paper trail: the ballot sheets themselves. Still election results are based on machine- generated totals as well as machine-generated audit reports to validate the voting process. In this paper we present a security assessment of the Diebold AccuVote Optical Scan voting terminal (AV-OS), a popular OS terminal currently in wide deployment anticipating the 2008 Presidential elections. The assessment is developed using exclusively reverse-engineering, without any technical specifications provided by the machine suppliers. We demonstrate a number of security issues that relate to the machine's proprietary language, called AccuBasic, that is used for reporting election results. While this language is thought to be benign, especially given that it is essentially sandboxed by the firmware to have only read access, we demonstrate that it is powerful enough to (i) strengthen known attacks against the AV-OS so that they become undetectable prior to elections (and thus significantly increasing their magnitude) or, (ii) to conditionally bias the election results to reach a desired outcome. Given the discovered vulnerabilities and attacks we proceed to discuss how random audits can be used to validate with high confidence that a procedure carried out by special purpose devices such as the AV-OS has not been manipulated. We end with a set of recommendations for the design and safe-use of OS voting systems.

It is known that any quantum algorithm for Graph Isomorphism thatworks within the framework of the hidden subgroup problem (HSP) must performhighly entangled measurements across Ω(n log n) coset states. One ofthe only known models for how such a measurement could be carried outefficiently is Kuperberg's algorithm for the HSP in the dihedral group, in whichquantum states are adaptively combined and measured according to thedecomposition of tensor products into irreducible representations. This "quantum sieve" starts with coset states, and works its way down towardsrepresentations whose probabilities differ depending on, for example, whetherthe hidden subgroup is trivial or nontrivial.

Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an unknown subgroup H of a group G must be determined from a quantum state $\psi$ over G that is uniformly supported on a left coset of H. These hidden subgroup problems are typically solved by Fourier sampling: the quantum Fourier transform of $\psi$ is computed and measured. When the underlying group is nonabelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation, in a suitably chosen basis, as well as its name) occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups H of the q-hedral groups, i.e., semidirect products ${\mathbb Z}_q \ltimes {\mathbb Z}_p$, where $q \mid (p-1)$, and in particular the affine groups $A_p$, can be information-theoretically reconstructed using the strong standard method. Moreover, if $|H| = p/ {\rm polylog}(p)$, these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We compare our algorithms to two weaker methods that have been discussed in the literature—the “forgetful” abelian method, and measurement in a random basis—and show that both of these are weaker than the strong standard method. Thus, at least for some families of groups, it is crucial to use the full power of representation theory and nonabelian Fourier analysis, namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated hidden shift problems, generalizing the work of van Dam, Hallgren, and Ip on shifts of multiplicative characters. Finally, we close by proving a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore, Russell, and Schulman [30] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Ω(n log n) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(n,Fpm) and Gn where G is finite and satisfies a suitable property.

The quantum Fourier transform (QFT) is a principal ingredient appearing in many efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by “quantizing” the highly successful separation of variables technique for the construction of efficient classical Fourier transforms. Specifically, we apply Bratteli diagrams, Gel'fand-Tsetlin bases, and strong generating sets of small adapted diameter to provide efficient quantum circuits for the QFT over a wide variety of finite Abelian and non-Abelian groups, including all families of groups for which efficient QFTs are currently known and many new families as well. Moreover, our method provides the first subexponential-size quantum circuits for the QFT over the linear groups GL k ( q ), SL k ( q ), and the finite groups of Lie type, for any fixed prime power q .

The symmetric encryption problem which manifests itself when two parties must securely transmit a message m with a short shared secret key is considered in conjunction with a computationally unbounded adversary. As the adversary is unbounded, any encryption scheme must leak information about m; in particular, the mutual information between m and its ciphertext cannot be zero. Despite this, a family of encryption schemes is presented that guarantee that for any message space in {0,1}/sup n/ with minimum entropy n-/spl lscr/ and for any Boolean function h:{0,1}/sup n/ /spl rarr/ {0,1}, no adversary can predict h(m) from the ciphertext of m with more than 1/n/sup /spl omega/(1)/ advantage; this is achieved with keys of length /spl lscr/+/spl omega/(logn). In general, keys of length /spl lscr/+s yield a bound of 2/sup -/spl Theta/(s)/ on the advantage. These encryption schemes rely on no unproven assumptions and can be implemented efficiently. Applications of this to cryptosystems based on complexity-theoretic assumptions are discussed and, in addition, a simplified proof of a fundamental "elision lemma" of Goldwasser and Micali is provided.

We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem in general groups. Specifically, we show that the hidden subgroup problem in the symmetric group cannot be efficiently solved by strong Fourier sampling. Indeed we prove the stronger statement that no measurement of a single coset state can reveal more than an exponentially small amount of information about the identity of the hidden subgroup, in the special case relevant to the graph isomorphism problem.

We report new techniques and theory in computational topology for reconstructing surfaces with boundary. This complements and extends known techniques for surfaces without boundary. Our approach is motivated by differential geometry and differential topology. We have also conducted significant experimental work to test our resultant implementations. We discuss some problematic issues that can arise regarding the roles of the medial axis and sampling density. The crucial topics for C2 manifolds are (1) important defining properties of C2 manifolds with boundary, (2) creation of auxiliary surfaces, with emphasis near the boundary,(3) sampling density, and (4) successful practical algorithms and examples.

The problem of cooperatively performing a set of t tasks in a decentralized computing environment subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work $\Omega(t\cdot g)$ even if each group of processors performs no more than the optimal number of $\Theta(t)$ tasks. Given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. Specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. The performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. The paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. Specifically, it is shown that the simple randomized algorithm obtains the competitive ratio $(1+\mathbf{cw}/e)$, where $\mathbf{cw}$ is the computation width and e is the base of the natural logarithm ($e=2.7182\ldots$); this competitive ratio is then shown to be tight.

The problem of cooperatively performing a set of t tasks in a decentralized setting where the computing medium is subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of their work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, an adversary that is able to partition the network into g components can cause any task-performing algorithm to have work Ω(t•g) even if each group of processors performs no more than the optimal number of Θ(t) tasks.Given such pessimistic lower bounds, and in order to understand better the practical implications of performing work in partitionable settings, we study distributed work-scheduling andpursue a competitiveanalysis. Specifically, we study asimple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. We compare the performance of the algorithm against that of an "off-line" algorithm with full knowledge of the future changes in the communication medium. We describe a notion of computation width, which associates a natural number with a history of changes in the communication medium, and show both upper and lower bounds on competitiveness in terms of this quantity. Specifically, we show that a simple randomized algorithm obtains the competitive ratio (1+cw/e), where cw is computation width; we then show that this ratio is tight.

The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.

We establish a new hardness result that shows that the difficulty of plan- ning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed family of fac- tored MDPs with linear rewards whose optimal policies and value func- tions simply cannot be represented succinctly in any standard parametric form. Previous hardness results indicated that computing good policies from the MDP parameters was difficult, but left open the possibility of succinct function approximation for any fixed factored MDP. Our result applies even to policies which yield a polynomially poor approximation to the optimal value, and highlights interesting connectionswith the com- plexity class of Arthur-Merlin games.

No abstract available.

Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is by broadcast and corrupt players are computationally unbounded. Protocols in this model may involve many asynchronous rounds. We assume that honest players communicate only uniformly random bits. We demonstrate that any n-player coin-flipping protocol that is resilient against corrupt coalitions of linear size must use either at least [1/2 - o(1)]log * n communication rounds or at least [log (2k-1) n ] 1-o(1) communication bits in the kth round, where log (j) denotes the logarithm iterated j times. In particular, protocols using one bit per round require [1/2 - o(1)]log * n rounds. These bounds also apply to the leader election problem. The primary component of this result is a new bound on the influence of random sets of variables on Boolean functions. Finally, in the one-round case, using other methods we prove a new bound on the influence of sets of variables of size $\beta n$ for $\beta > 1/3$.

The emergence of mobile computing paradigms has created new dimensions for the problem of performing a collection of tasks in a distributed setting. Indeed, an intrinsic feature of mobile computing is that the communication topology changes over time, and some devices may not be able to communicate with others for prolonged periods of time. Efficient utilization of resources in such a setting requires tools for structuring computation with highly variable, or absent, processor connectivity. This article provides a family of efficient distributed scheduling building blocks for this purpose. Specifically, this paper presents new bounds for a fundamental distributed cooperation problem under the assumption that processors may need to schedule their work in isolation due to a prolonged absence of communication. The problem for n processors is defined in terms of t tasks that must be performed efficiently and that are known to all processors. This study gives tight bounds on the ability of the processors to schedule their work so that when some group of processors establish communication, the wasted (redundant) work these processors have collectively performed prior to that time is controlled.

We consider a distributed environment consisting of n processors that need to perform t tasks. We assume that communication is initially unavailable and that processors begin work in isolation. At some unknown point of time an unknown collection of processors may establish communication. Before processors begin communication they execute tasks in the order given by their schedules. Our goal is to schedule work of isolated processors so that when communication is established for the first time, the number of redundantly executed tasks is controlled. We quantify worst case redundancy as a function of processor advancements through their schedules.

This work studies a distributed cooperation problem under an extreme assumption that no two processors may be able to communicate during a prolonged period of time. For problems where the quality of distributed decision-making depends on, and can be traded for, communication, the solution space needs to consider the possibility of no communication. Notably, this is the case in the load-balancing setting introduced by Papadimitriou and Yanakakis [PY] and studied by Georgiades, Mavronicolas and Spirakis [GMS]. The distributed cooperation problem that we consider here is defined for n processors in terms of t tasks that need to be performed efficiently and that are known to all processors. The fact that the tasks are initially known makes it possible for the problem to be solved in the absence of communication. The efficiency requirement and the possibility of eventual availability of communication make it desirable to structure the work of the processors so that when eventually some processors are able to communicate, the amount of wasted (redundant) work they have collectively performed prior to that time is controlled. We model solutions to the problem as sets of n lists of distinct tasks from {1,… ,t}. We call such lists schedules. We define and study the notion of k-waste that, for a set of n schedules, measures the maximum number of redundant task identifiers contained in any subset of k (≤ n) schedules. We are interested in expressing k-waste as a function of the length of schedules. Our goal is to construct n schedules of length t such that k-waste is controlled for any prefixes of the schedules.

The Hidden Subgroup Problem is the foundation of many quantum algorithms.An efficient solution is known for the problem over Abelian groups and this was used in Simon's algorithm and Shor's Factoring and Discrete Log algorithms.The non-Abelian case is open; an efficient solution would give rise to an efficient quantum algorithm for Graph Isomorphism.We fully analyze a natural generalization of the Abelian case solution to the non-Abelian case, and give an efficient solution to the problem for normal subgroups.We show, however, that this immediate generalization of the Abelian algorithm does not efficiently solve Graph Isomorphism.

We explore the problem of transforming n independent and identically biased {-1,1}-valued random variables X/sub 1/,...,X/sub n/ into a single {-1,1} random variable f(X/sub 1/,...,X/sub n/), so that this result is as unbiased as possible. In general, no function f produces a completely unbiased result. We perform the first study of the relationship between the bias b of these X/sub i/ and the rate at which f(X/sub 1/,...,X/sub n/) can converge to an unbiased {-1,1} random variable (as n/spl rarr//spl infin/). A {-1,1} random variable has bias b if E(X/sub i/)=b. Fixing a bias b, we explore the rate at which the output bias |E(f(X/sub 1/,...,X/sub n/))| can tend to zero for a function f:{-1,1}*/spl rarr/{-1,1}. This is accomplished by classifying the behavior of the natural normalized quantity /spl Xi/(b)/spl Delta/inf/sub f/[lim/sub n/spl rarr//spl infin//n/spl radic/(|E(f(X/sub 1/,...,X/sub n/))|] this infimum taken over all such f. We show that for rational b, /spl Xi/(b)=(1/s), where (1+b/2)=(r/s) (r and s relatively prime). Developing the theory of uniform distribution of sequences to suit our problem, we then explore the case where b is irrational. We prove a new metrical theorem concerning multidimensional Diophantine approximation type from which we show that for (Lebesgue) almost all biases b, /spl Xi/(b)=0. Finally, we show that algebraic biases exhibit curious "boundary" behavior, falling into two classes. Class 1. Those algebraics b for which /spl Xi/(b)>0 and, furthermore, c/sub 1//spl les//spl Xi/(b)/spl les/c/sub 2/ where c/sub 1/ and c/sub 2/ are positive constants depending only on b's algebraic characteristics. Class 2. Those algebraics b for which there exist n>0 and f: {-1,1}/sup n//spl rarr/{-1,1} so that E(f(X/sub 1/,...,X/sub n/))=0. Notice that this classification excludes the possibility that n/spl radic/(|E(f(X/sub 1/,...,X/sub n/))| limits to zero (for algebraics). For rational and algebraic biases, we also study the computational problem by restricting f to be a polynomial time computable function. Finally, we discuss natural extensions where output distributions other than the uniform distribution on {-1,1} are sought.

We study the computational complexity of solving systems of equations over a finite group. An equation over a group G is an expression of the form w/sub 1//spl middot/w/sub 2//spl middot//spl middot//spl middot//spl middot//spl middot/w/sub k/=id where each w/sub i/ is either a variable, an inverted variable, or group constant and id is the identity element of G. A solution to such an equation is an assignment of the variables (to values in G) which realizes the equality. A system of equations is a collection of such equations; a solution is then an assignment which simultaneously realizes each equation. We demonstrate that the problem of determining if a (single) equation has a solution is NP-complete for all nonsolvable groups G. For nilpotent groups, this same problem is shown to be in P. The analogous problem for systems of such equations is shown to be NP-complete if G is non-Abelian, and in P otherwise. Finally, we observe some connections between these languages and the theory of nonuniform automata.

Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is by broadcast and corrupt players are computationally unbounded. Protocols in this model may involve many asynchronous rounds; we focus on protocols which permit each player to broadcast a single bit per round. We demonstrate that any n-player coin-flipping protocol resilient against corrupt coalitions of linear size must use \\Theta 1=2 \\Gamma o(1) log n rounds of communication. Such a bound also applies to the leader election problem. This extends work of Kahn, Kalai, and Linial, who proved a similar result for single-round protocols. The primary component of the above result is a new bound on the influence of random sets of variables on Boolean functions. Finally, in the one-round case, we prove a new bound on the influence of sets of variables of size fin, for fi ? 1=3. e-ma...

In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect information model: all communication is by broadcast, and the bad players have unlimited computational power. Within a round, they may also wait to see the inputs of the good players. A protocol is called resilient if a good leader is elected with probability bounded away from 0. We give a simple, constructive leader election protocol that is resilient against coalitions of size /spl beta/n, for any /spl beta/<1/2. Our protocol takes log*n+O(1) rounds, each player sending at most log n bits per round. For any constant k, our protocol can be modified to take k rounds and be resilient against coalitions of size /spl epsi/n(log/sup (k)/n)/sup 3/, where /spl epsi/ is a small enough constant and log(k) denotes the logarithm iterated k times. This is constructive for k/spl ges/3.

All-optical networks using wavelength division multiplexing are increasingly coming to be regarded as the technology of choice for the next generation of wide-area backbone networks. These networks incorporate optical switches that employ the concept of Latin Routers for assigning wavelengths to routes. The issue of maximizing wavelength utilization at these switching devices is of great importance since it lends to significant improvements in overall network performance. In this paper we present two fast approximation algorithms-GREEDY and MATCH for the problem of maximizing wavelength utilization at Latin Routers. These are the first known polynomial-time approximation algorithms for the problem of maximizing the number of entries that can be added to a partially filled Latin Square that achieve non-trivial worst-case performance guarantees. These algorithms are easily implementable and have very small constants in their running times making them eminently suitable far actual use in real-world optical switches. We also provide strong experimental evidence to show that, in practice, these algorithms are near-optimal.

Bandwidth is a very valuable resource in wavelength division multiplexed optical networks. The problem of finding an optimal assignment of wavelengths to requests is of fundamental importance in bandwidth utilization. We present a polynomial-time algorithm for this problem on fixed constant-size topologies. We combine this algorithm with ideas from Raghavan and Upfal (1994) to obtain an optimal assignment of wavelengths on constant degree undirected trees. Mihail, Kaklamanis, and Rao (1995) posed the following open question: what is the complexity of this problem on directed trees? We show that it is NP-complete both on binary and constant depth directed trees.

No abstract available.

Article Free Access Share on Efficient probabilistically checkable proofs and applications to approximations Authors: M. Bellare View Profile , S. Goldwasser View Profile , C. Lund View Profile , A. Russell View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 294–304https://doi.org/10.1145/167088.167174Published:01 June 1993Publication History 182citation659DownloadsMetricsTotal Citations182Total Downloads659Last 12 Months70Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF