https://drops.dagstuhl.de/storage/00lipics/lipics-vol275-approx-random2023/LIPIcs.APPROX-RANDOM.2023.66/LIPIcs.APPROX-RANDOM.2023.66.pdf

We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property. Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. However, for testing algorithms to reach their full potential in image processing, they have to be tolerant, which allows them to be resilient to noise. We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so it becomes a half-plane? A representation of a convex object? A representation of a connected object? More precisely, our algorithms approximate the distance to three basic properties (being a half-plane, convexity, and connectedness) within a small additive error ε, after reading poly (1/ε) pixels, independent of the image size. We also design an efficient agnostic proper PAC learner of convex sets (continuous and discrete) in two dimensions under the uniform distribution. Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons P ε such that (1) every convex image has a nearby polygon in P ε and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in P ε .

In this paper we present several results on the expected complexity of a convex hull of $n$ points chosen uniformly and independently from a convex shape. (i) We show that the expected number of vertices of the convex hull of $n$ points, chosen uniformly and independently from a disk is $O(n^{1/3})$, and $O(k \log{n})$ for the case a convex polygon with $k$ sides. Those results are well known (see \cite{rs-udkhv-63,r-slcdn-70,ps-cgi-85}), but we believe that the elementary proof given here are simpler and more intuitive. (ii) Let $\D$ be a set of directions in the plane, we define a generalized notion of convexity induced by $\D$, which extends both rectilinear convexity and standard convexity. We prove that the expected complexity of the $\D$-convex hull of a set of $n$ points, chosen uniformly and independently from a disk, is $O(n^{1/3} + \sqrt{nα(\D)})$, where $α(\D)$ is the largest angle between two consecutive vectors in $\D$. This result extends the known bounds for the cases of rectilinear and standard convexity. (iii) Let $\B$ be an axis parallel hypercube in $\Re^d$. We prove that the expected number of points on the boundary of the quadrant hull of a set $S$ of $n$ points, chosen uniformly and independently from $\B$ is $O(\log^{d-1}n)$. Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in $S$, and is also larger than the number of points of $S$ that are vertices of the convex hull of $S$. Those bounds are known \cite{bkst-anmsv-78}, but we believe the new proof is simpler.

We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter epsilon in (0,1/2), a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it does not. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(1/epsilon) samples. In contrast, we prove that convexity can be tested with O(1/epsilon) queries by testers that can make queries of their choice while uniform testers for this property require Omega(1/epsilon^{5/4}) samples. Previously, the fastest known tester for convexity needed Theta(1/epsilon^{4/3}) queries.

We initiate a systematic study of sublinear algorithms for approximately testing properties of real-valued data with respect to Lp distances for p = 1, 2. Such algorithms distinguish datasets which either have (or are close to having) a certain property from datasets which are far from having it with respect to Lp distance. For applications involving noisy real-valued data, using Lp distances allows algorithms to withstand noise of bounded Lp norm. While the classical property testing framework developed with respect to Hamming distance has been studied extensively, testing with respect to Lp distances has received little attention.

We provide improved approximation algorithms for the min-max generalization problems considered by Du, Eppstein, Goodrich, and Lueker [Du et al. 2009]. Generalization is widely used in privacy-preserving data mining and can also be viewed as a natural way of compressing a dataset. In min-max generalization problems, the input consists of data items with weights and a lower bound w lb , and the goal is to partition individual items into groups of weight at least w lb while minimizing the maximum weight of a group. The rules of legal partitioning are specific to a problem. Du et al. consider several problems in this vein: (1) partitioning a graph into connected subgraphs, (2) partitioning unstructured data into arbitrary classes, and (3) partitioning a two-dimensional array into contiguous rectangles (subarrays) that satisfy these weight requirements. We significantly improve approximation ratios for all the problems considered by Du et al. and provide additional motivation for these problems. Moreover, for the first problem, whereas Du et al. give approximation algorithms for specific graph families, namely, 3-connected and 4-connected planar graphs, no approximation algorithm that works for all graphs was known prior to this work.

Unlike the use of DRAM for caching or buffering, certain idiosyncrasies of SSDs make their integration into existing systems non-trivial. Flash memory suffers from limits on its reliability, is an order of magnitude more expensive than the HDD, and can sometimes be as slow as the HDD (due to excessive garbage collection (GC) induced by high intensity of random writes). Given these trade-offs between HDDs and SSDs in terms of cost, performance, and lifetime, the current consensus among several storage experts is to view SSDs not as a replacement for HDD but rather as a complementary device within the high performance storage hierarchy. We design and evaluate such a hybrid system called Hybrid Store to provide: (a) Hybrid Plan: improved capacity planning technique to administrators with the overall goal of operating within cost-budgets and (b) HybridDyn: improved performance/lifetime guarantees during episodes of deviations from expected workloads through two novel mechanisms: write-regulation and fragmentation busting. As an illustrative example of HybridStore's efficacy, Hybrid Plan is able to find the most cost-effective storage configuration for a large scale workload of Microsoft Research and suggest one MLC SSD with ten 7.2K RPM HDDs instead of fourteen 7.2K RPM HDDs only. HybridDyn is able to reduce the average response time for an enterprise scale random-write dominant workload by about 71%as compared to a HDD-based system.

Conserving the energy for motion is an important yet not-well-addressed problem in mobile sensor networks. In this article, we study the problem of optimizing sensor movement for energy efficiency. We adopt a complete energy model to characterize the entire energy consumption in movement. Based on the model, we propose an optimal trapezoidal velocity schedule for minimizing energy consumption when the road condition is uniform; and a corresponding velocity schedule for the variable road condition by using continuous-state dynamic programming. Considering the variety in motion hardware, we also design one velocity schedule for simple microcontrollers, and one velocity schedule for relatively complex microcontrollers, respectively. Simulation results show that our velocity planning may have significant impact on energy conservation.

A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, a subgraph $H = (V,E_H)$ is a $k$-spanner of a graph $G=(V,E)$ if for every pair of vertices $u,v \in V$, the shortest path distance $dist_H(u,v)$ from $u$ to $v$ in $H$ is at most $k.dist_G(u,v)$. We focus on spanners of directed graphs and a related notion of transitive-closure spanners. The latter captures the idea that a spanner should have a small diameter but preserve the connectivity of the original graph. We study the computational problem of finding the sparsest $k$-spanner (resp., $k$-TC-spanner) of a given directed graph, which we refer to as DIRECTED $k$-SPANNER (resp., $k$-TC-SPANNER). We improve all known approximation algorithms for these problems for $k\geq 3$. (For $k=2$, the current ratios are tight, assuming P$\neq$NP.) Along the way, we prove several structural results about the size of the sparsest spanners of directed graphs.

Network alignments are extensively used for comparing, exploring, and predicting biological networks. Existing alignment tools are mostly based on isomorphic and homeomorphic embedding and require solving a problem that is NP-complete even when searching a match for a tree in acyclic networks. On the other hand, if the mapping of different nodes from the query network (pattern) into the same node from the text network is allowed, then trees can be optimally mapped into arbitrary networks in polynomial time.In this paper we present the first polynomial-time algorithm for finding the best matching pair consisting of a subtree in a given tree pattern and a subgraph in a given text (represented by an arbitrary network) when both insertions and deletions of degree-2 vertices are allowed on any path. Our dynamic programming algorithm is an order of magnitude faster than the previous network alignment algorithm when deletions are forbidden. The algorithm has been also generalized to pattern networks with cycles: with a modest increase in runtime it can handle patterns with the limited vertex feedback set.We have applied our algorithm to matching metabolic pathways of four organisms (E. coli, S. cerevisiae, B. subtilis and T. thermophilus species) and found a reasonably large set of statistically significant alignments. We show advantages of allowing pattern vertex deletions and give an example validating biological relevance of the pathway alignment.

The topology of beta-sheets is defined by the pattern of hydrogen-bonded strand pairing. Therefore, predicting hydrogen bonded strand partners is a fundamental step towards predicting beta-sheet topology. At the same time, finding the correct partners is very difficult due to long range interactions involved in strand pairing. Additionally, patterns of amino acids involved, in beta-sheet formations are very general and therefore difficult to use for computational recognition of specific contacts between strands. In this work, we report a new strand pairing algorithm. To address above mentioned difficulties, our algorithm attempts to mimic elements of the folding process. Namely, in addition to ensuring that the predicted hydrogen bonded strand pairs satisfy basic global consistency constraints, it takes into account hypothetical folding pathways. Consistently with this view, introducing hydrogen bonds between a pair of strands changes the probabilities of forming hydrogen bonds between other pairs of strand. We demonstrate that this approach provides an improvement over previously proposed algorithms. We also compare the performance of this method to that of a global optimization algorithm that poses the problem as integer linear programming optimization problem and solves it using ILOG CPLEX package.

Motivated by the widespread proliferation of wireless networks employing directional antennas, we study some capacitated covering problems arising in these networks. Geometrically, the area covered by a directional antenna with parameters α,ρ,r is a set of points with polar coordinates (r,θ) such that r ≤ r and α ≤ θ ≤ α + ρ. Given a set of customers, their positions on the plane and their bandwidth demands, the capacitated covering problem considered here is to cover all the customers with the minimum number of directional antennas such that the demands of customers assigned to an antenna stays within a bound. We consider two settings of this capacitated cover problem arising in wireless networks. In the first setting where the antennas have variable angular range, we present an approximation algorithm with ratio 3. In the setting where the angular range of antennas is fixed, we improve this approximation ratio to 1.5.

MOTIVATION: Complex genomes contain numerous repeated sequences, and genomic duplication is believed to be a main evolutionary mechanism to obtain new functions. Several tools are available for de novo repeat sequence identification, and many approaches exist for clustering homologous protein sequences. We present an efficient new approach to identify and cluster homologous DNA sequences with high accuracy at the level of whole genomes, excluding low-complexity repeats, tandem repeats and annotated interspersed repeats. We also determine the boundaries of each group member so that it closely represents a biological unit, e.g. a complete gene, or a partial gene coding a protein domain. RESULTS: We developed a program called HomologMiner to identify homologous groups applicable to genome sequences that have been properly marked for low-complexity repeats and annotated interspersed repeats. We applied it to the whole genomes of human (hg17), macaque (rheMac2) and mouse (mm8). Groups obtained include gene families (e.g. olfactory receptor gene family, zinc finger families), unannotated interspersed repeats and additional homologous groups that resulted from recent segmental duplications. Our program incorporates several new methods: a new abstract definition of consistent duplicate units, a new criterion to remove moderately frequent tandem repeats, and new algorithmic techniques. We also provide preliminary analysis of the output on the three genomes mentioned above, and show several applications including identifying boundaries of tandem gene clusters and novel interspersed repeat families. AVAILABILITY: All programs and datasets are downloadable from www.bx.psu.edu/miller_lab.

Constructing a sensor network with a mix of mobile and static sensors can achieve a balance between sensor coverage and sensor cost. In this paper, we design two bidding protocols to guide the movement of mobile sensors in such sensor networks to increase the coverage to a desirable level. In the protocols, static sensors detect coverage holes locally by using Voronoi diagrams and bid mobile sensors to move. Mobile sensors accept the highest bids and heal the largest holes. Simulation results show that our protocols achieve suitable trade-off between coverage and sensor cost

Conserving the energy for motion is an important yet not-well-addressed problem in mobile sensor networks. In this paper, we study the problem of optimizing sensor movement for energy efficiency. We adopt a complete energy model to characterize the entire energy consumption in movement. Based on the model, we propose an optimal velocity schedule for minimizing energy consumption when the road condition is uniform; and a near optimal velocity schedule for the variable road condition by using continuous-state dynamic programming. Considering the variety in motion hardware, we also design one velocity schedule for simple microcontrollers, and one velocity schedule for relatively complex microcontrollers, respectively. Simulation results show that our velocity planning may have significant impact on energy conservation

Optimizing the energy consumption in wireless sensor networks has recently become the most important performance objective. We assume the sensor network model in which sensors can interchange idle and active modes. Given monitoring regions, battery life and energy consumption rate for each sensor, we formulate the problem of maximizing sensor network lifetime, i.e., time during which the monitored area is (partially or fully) covered. Our contributions include (1) an efficient data structure to represent the monitored area with at most n/sup 2/ points guaranteeing the full coverage which is superior to the previously used approach based on grid points, (2) efficient provably good centralized algorithms for sensor monitoring schedule maximizing the total lifetime including (1+ln(1-q)/sup -1/)-approximation algorithm for the case when a q-portion of the monitored area is required to cover, e.g., for the 90% area coverage our schedule guarantees to be at most 3.3 times shorter than the optimum, (4) a family of efficient distributed protocols with trade-off between communication and monitoring power consumption, (5) extensive experimental study of the proposed algorithms showing significant advantage in quality, scalability and flexibility.

We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: An upper bound of 3n-1 in general, and an upper bound of 2n-1 if the rectangles tile the underlying space. This improves the upper bounds of 4n in [V. Hai Nguyen and P. Widmayer, Binary Space Partitions for Sets of Hyperrectangles, Lecture Notes in Comput. Sci. 1023, Springer-Verlag, Berlin, 1995; F. d'Amore and P. G. Franciosa, Inform. Process. Lett., 44 (1992), pp. 255--259]. A BSP satisfying the upper bounds can be constructed in O(n log n) time. A worst-case lower bound of 2n-o(n) in general, and $\frac{3n}{2}-o(n)$ if the rectangles form a tiling. The BSP tree is one of the most popular data structures in computational geometry, and hence even "small" factor improvements of $\frac{4}{3}$ or 2 on the previously known upper bounds that we show improve the performances of applications relying on the BSP tree. As an illustration, we present improved approximation algorithms for certain dual rectangle tiling problems using our upper bounds on the size of the BSP trees.

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al.(Proc. 31st ACM STOC, 622-631, 1999). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al., while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al., our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded.

We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase shifting masks in the single exposure regime. We make the following contributions. First, we suggest new two-coloring and compaction approach that simultaneously optimizes layout and phase assignment which is based on planar embedding of an associated conflict graph. We also describe additional approaches to cooptimization of layout and phase assignment for alternating PSM. Second, we give optimal and fast algorithms to minimize the number of phase conflicts that must be removed to ensure two colorability of the conflict graph. We reduce this problem to the T-join problem which asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A if u belongs to a given node subset T of a weighted graph. Third, we suggest several practical algorithms for the T-join problem. In sparse graphs, our algorithms are faster than previously known methods. Computational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithms.

We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase shifting masks in the single exposure regime. We make the following contributions. First, we suggest new two-coloring and compaction approach that simultaneously optimizes layout and phase assignment which is based on planar embedding of an associated conflict graph. We also describe additional approaches to cooptimization of layout and phase assignment for alternating PSM. Second, we give optimal and fast algorithms to minimize the number of phase conflicts that must be removed to ensure two colorability of the conflict graph. We reduce this problem to the -join problem which asks for a minimum weight edge set such that a node is incident to an odd number of edges of if belongs to a given node subset of a weighted graph. Third, we suggest several practical algorithms for the -join problem. In sparse graphs, our algorithms are faster than previously known methods. Computational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithms.

In database searches for sequence similarity, matches to a distinct sequence region (e.g. protein domain) are frequently obscured by numerous matches to another region of the same sequence.In order to cope with this problem, algorithms are developed to discard redundant matches.One model for this problem begins with a list of intervals, each with an associated score; each interval gives the range of positions in the query sequence that align to a database sequence, and the score is that of the alignment.If interval I is contained in interval J, and I's score is less than J's, then I is said to be dominated by J.The problem is then to identify each interval that is dominated by at least K other intervals, where K is a given level of "tolerable redundancy."An algorithm is developed to solve the problem in O(N log N) time and O(N*) space, where N is the number of intervals and N' is a precisely defined value that never exceeds N and is frequently much smaller.This criterion for discarding database hits has been implemented in the Blast program, as illustrated herein with examples.Several variations and extensions of this approach are also described.

MOTIVATION: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments. RESULTS: We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment's length. Practical applications to alignments of genomic DNA sequences are described.

A feedback vertex set of a graph is a subset of vertices that contains at least one vertex from every cycle in the graph. The problem considered is that of finding a minimum feedback vertex set given a weighted and undirected graph. We present a simple and efficient approximation algorithm with performance ratio of at most 2, improving previous best bounds for either weighted or unweighted cases of the problem. Any further improvement on this bound, matching the best constant factor known for the vertex cover problem, is deemed challenging. The approximation principle, underlying the algorithm, is based on a generalized form of the classical local ratio theorem, originally developed for approximation of the vertex cover problem, and a more flexible style of its application.

Given a strong match be%een regions of txvo sequences, horn far can the match be meaningfully extended if gaps are all04 in the resdtinrc aknment?The aim is to aviod sear&ix bwond the point th\t asuseful extension of the a&mm& is l&ly to be found.Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem.Given two sequences and a fixed X > 0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below -X.Our results indicate that computing an optimal alignment under this constraint is very expensive.However, less rigorous conditions on the alignment can be guaranked by quite eiiicient algorithms.One of these variants has been implemented in a new release of the Blast suite of database search programs.a b C Figure 1: Graph model of a simple alignment problem.Dark edges (corresponding to aligning identical letters) score 1, and all other edges score -1.

Article On-line algorithms for Steiner tree problems (extended abstract) Share on Authors: Piotr Berman Penn State University, University Park, PA Penn State University, University Park, PAView Profile , Chris Coulston Penn State University, University Park, PA Penn State University, University Park, PAView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 344–353https://doi.org/10.1145/258533.258618Published:04 May 1997 56citation1,035DownloadsMetricsTotal Citations56Total Downloads1,035Last 12 Months33Last 6 weeks5 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 SiteGet Access

Abstract We study a probabilistic setting for distributed fault diagnosis in multiprocessor systems. A system is an undirected graph with nodes representing processors and edges representing communication links. Processors are assumed to fail independently with some probability p. They test their neighbors, and a fault‐free processor has probability 1 − q of discovering a fault of a failed neighbor in an individual test. Subsequently, fault‐free processors attempt to diagnose all the processors of the system with communication based on the test results. During communication, the behavior of faulty processors may be arbitrary (socalled malicious). For every p ≤ ½, q ≤ 1, we construct systems with O(n log n) links in which distributed probabilistic diagnosis can be achieved with probability of correctness at least 1 − n−1. We also show that for some small fixed p and q a similar result holds for the hypercube. On the other hand, we prove that for sufficiently small k, for a system with n processors and kn log n links, the probability of achieving correct diagnosis cannot exceed n−0.5. © 1994 by John Wiley & Sons, Inc.

This paper investigates the problem of finding an optimal static pessimistic replica control scheme. It has been widely accepted that coteries (proposed by Garcia-Molina and Barbara) provide the most general framework for such schemes. We demonstrate that voting schemes, a very small subset of static pessimistic schemes, are optimal for fully connected networks with negligible link failure rates, as well as for Ethernet systems. We also show that voting is not optimal for somewhat more general systems. We propose a modification of the algorithm of Z. Tong and R.Y. Kain (1988) for computing optimal voting in operation independent case, so that it runs in linear (rather than exponential) time. Finally, we propose the first efficient algorithm for computing the optimal vote assignment and appropriate thresholds for fully connected networks when relative frequencies of read and write operations are known. We also extend this result to Ethernet systems.>

It is shown that in a standard discrete neural network model with small fan-in, tolerance to random malicious faults can be achieved with a log-linear increase in the number of neurons and a constant factor increase in parallel time, provided fan-in can increase arbitrarily. A similar result is obtained for a nonstandard but closely related model with no restriction on fan-in.

The problem of finding an optimal static pessimistic replica control scheme is investigated. It has been widely accepted that coteries (proposed by Garcia-Molina and Barbara) provide the most general framework for such schemes. Under such as assumption, it is demonstrated that the voting scheme is an optimal static pessimistic scheme for fully connected networks with negligible link failure rates, as well as for Ethernet systems. It is also shown that voting is not optimal for somewhat more general systems. The authors propose a modification of the algorithm of Tong and Kain for the best voting in the operation-independent case so that it runs in linear (rather than exponential) time. They also propose a linear-time algorithm for computing the optimal vote assignment when relative frequencies of read and write operations are known.>

In a distributed consensus protocol all processors (of which t may be faulty) are given (binary) initial values; after exchanging messages all correct processors must agree on one of them. The quality of a protocol is measured here using as parameters the total number of processors n, number of rounds of message exchange r, and maximal message length m, with optima, respectively, of 3t+1, t+1, and 1. Although no known protocol is optimal in all these three aspects simultaneously, the protocols that take further steps in this direction are presented. The first protocol has n>4t, r=t+1, and polynomial message size. The second protocol has n>3t, r=3t+3, and m=2, and it is asymptotically optimal in all three quality parameters while using the optimal number of processors. Using these protocols as building blocks, families of protocols with intermediate quality parameters, offering better tradeoffs than previous results, are obtained. All the protocols work in polynomial time and have succinct descriptions.>

Article Free Access Share on Investigations of fault-tolerant networks of computers Authors: Piotr Berman Department of Computer Science, The Pennsylvania State University Department of Computer Science, The Pennsylvania State UniversityView Profile , J'anos Simon Department of Computer Science, The University of Chicago Department of Computer Science, The University of ChicagoView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 66–77https://doi.org/10.1145/62212.62219Online:01 January 1988Publication History 10citation258DownloadsMetricsTotal Citations10Total Downloads258Last 12 Months16Last 6 weeks2 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

We demonstrate that the class of languages accepted by deterministic one-counter machines, or DOCAs (a natural subset of the context-free languages), is learnable in polynomial time. Our learning protocol is based upon Angluin's concept of a "minimally adequate teacher" who can answer membership queries about a concept and provide counterexamples to incorrect hypothesized concepts. We also demonstrate that the problem of testing DOCAs for equivalence may be solved in polynomial time, answering a question posed by Valiant and Paterson.

It is likely that reliable and fast space-bounded probabilistic acceptors are less powerful than nondeterministic ones. We consider a restricted model of space-bounded probabilistic computation, the random analog of a model studied in [CR]. We show that maze traversal (a complete problem for nondeterministic space log n) requires space Ω(log2n/loglogn) by random machines, even if 'fast' is relaxed to mean only 'subexponential'. In particular, the lower bound on space holds for the time complexity of Savitch's algorithm (which can be simulated in the model).