On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms

In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS- relative delay . We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O (1) GPS-relative delay bound is Ω ( log 2 n ) (widely believed as a "folklore theorem" but never proved). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O ( n a ) for 0‹ a ⋵1. This implies that the delay-complexity tradeoff curve is "flat" in the "interval" [ O (1), O ( n )). We later extend both complexity results (for O (1) or O ( n a ) delay) to a much stronger computational model. Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds. This is done by untangling the relationship between the GPS-relative delay bound and the end-to-end delay bound.

Fidelity of enzymatic ligation for DNA computing

We describe a convenient assay for rapid qualitative evaluation of hybridization/ligation fidelity. The approach uses randomized probe strands of DNA and restriction enzyme digestion after amplification of reaction products by the polymerase chain reaction (PCR). We report ligation efficiencies and fidelities of two DNA ligases, T4 DNA ligase and Thermus aquaticus (Taq) DNA ligase, over a range of temperatures.

Molecular computation: RNA solutions to chess problems

We have expanded the field of "DNA computers" to RNA and present a general approach for the solution of satisfiability problems. As an example, we consider a variant of the "Knight problem," which asks generally what configurations of knights can one place on an n x n chess board such that no knight is attacking any other knight on the board. Using specific ribonuclease digestion to manipulate strands of a 10-bit binary RNA library, we developed a molecular algorithm and applied it to a 3 x 3 chessboard as a 9-bit instance of this problem. Here, the nine spaces on the board correspond to nine "bits" or placeholders in a combinatorial RNA library. We recovered a set of "winning" molecules that describe solutions to this problem.

Chess games: a model for RNA based computation

Here we develop the theory of RNA computing and a method for solving the 'knight problem' as an instance of a satisfiability (SAT) problem. Using only biological molecules and enzymes as tools, we developed an algorithm for solving the knight problem (3 x 3 chess board) using a 10-bit combinatorial pool and sequential RNase H digestions. The results of preliminary experiments presented here reveal that the protocol recovers far more correct solutions than expected at random, but the persistence of errors still presents the greatest challenge.

Counting DNA: estimating the complexity of a test tube of DNA

We consider the problem of estimation of the 'complexity' of a test tube of DNA. The complexity of a test tube is the number of different kinds of strands of DNA in the test tube. It is quite easy to estimate the number of total strands in a test tube, especially if the strands are all the same length. Estimation of the complexity is much less clear. We propose a simple kind of DNA computation that can estimate the complexity.

DNA solution of hard computational problems

DNA experiments are proposed to solve the famous "SAT" problem of computer science. This is a special case of a more general method that can solve NP-complete problems. The advantage of these results is the huge parallelism inherent in DNA-based computing. It has the potential to yield vast speedups over conventional electronic-based computers for such search problems.

Botulinum toxin injection for adductor spastic dysphonia: patient self-ratings of voice and phonatory effort after three successive injections

Ten patients (aged 35 to 70 years) with neurologic adductor spastic dysphonia rated themselves on a 7-point scale of severity for degree of voice improvement and physical effort after a series of three injections of botulinum toxin. Symptoms were noticeably reduced 24 and 48 hours after injection; this improvement was followed by considerable fluctuations in voice quality and phonatory effort. With successive injections, patients differed in their post-injection experiences, the time required to reach optimal voice, and the total duration of benefit. The study shows that the course of voice change after botulinum toxin injection is not predictable, uniform, or equal among patients with spastic dysphonia.

Noninvasive technique for estimating subglottic pressure and laryngeal efficiency

The clinical assessment of aerodynamic parameters is important in the physiology and pathophysiology of laryngeal function. Vocal efficiency is among these objective measurements and can be calculated from simultaneous recordings of subglottic pressure, airflow, and sound intensity. Modern techniques allow us to accurately determine sound intensity and airflow. However, methods to determine subglottic pressure are either invasive or laborious. We have evaluated a noninvasive, indirect method to determine subglottic pressure by using a technique based on the interruption of transglottic airflow during phonation. The correlation between the indirectly acquired subglottic pressure measured in the oral cavity by using this technique and the subglottic pressure obtained directly by translaryngeal puncture in human volunteers was highly significant in 35 trials (r = .92, p less than .01). This study describes a reliable technique for the noninvasive measurement of subglottic pressure, sound intensity, and airflow.

Phonatory vocal fold function in the excised canine larynx

The development of valid objective measurements of vocal cord vibration during phonation is a goal of current research in laryngeal physiology. An excised canine larynx was used to study the effects of vocal cord tension, air flow rate, and glottic width on glottographic parameters. The electroglottographic and photoglottographic wave-forms were simultaneously recorded as the vocal cord tension, glottic width, and air flow rate were systematically varied. These glottographic waveforms were analyzed to determine the open quotient and speed quotient. Multiple regression analysis of the data obtained from 10 larynges showed the open quotient to be directly related to vocal fold tension (p less than 0.001), glottic width (p less than 0.01), and fundamental frequency (p less than 0.001). Speed quotient was inversely related to glottic width and and subglottic pressure (p less than 0.05). Regression analysis also showed frequency of vibration to be directly related to tension (p less than 0.001) and inversely related to glottic width (p less than 0.001), with different combinations of glottic tension and width capable of producing the same frequency. The open and speed quotients thus reflect the changes in the vibratory patterns of the vocal folds produced by alterations in tension and width. The clinical implications of these results will be discussed, with emphasis on glottography as an objective assessment of the various laryngeal framework procedures being performed.

Rhinolift operation in the treatment of the aging nose

Disturbance of the normal relationship between the caudal border of the upper lateral cartilage and the cephalic margin of the lobular cartilage--the so-called "cul-de-sac" area--can result in alar collapse and nasal airway obstruction. This may be caused by either the aging process or trauma, both surgical and nonsurgical. Rhinolift is a surgical procedure that was developed for the treatment of the aging ptotic nasal tip. We have applied this technique to patients with nasal airway obstruction resulting from alar collapse. Elevation of the cephalic margin of the lobular cartilage to a position superficial to the upper lateral cartilage restores the normal relationship between these two structures. The upper lateral cartilage then assists in stenting the vestibule open, and thereby improves nasal breathing. Over the past 10 years, 20 patients have had rhinolifts at our institution for the relief of nasal airway obstruction. Concomitant surgery included nasal septal reconstruction in 12 patients, polypectomy in one patient, and placement of a silicone rubber septal prosthesis for closure of a large septal perforation in three patients. Rhinolift was the sole procedure used for the correction of valvular pathology in 10 patients. The other 10 patients had modifications made in their upper lateral cartilage along with the rhinolift. Five patients described restoration of normal nasal breathing, while 14 patients showed partial symptomatic improvement. One patient reported no improvement in nasal breathing. Rhinolift is a safe effective surgical technique for functional improvement of nasal breathing in patients with alar collapse resulting from inadequate cartilaginous support.

Thyroid carcinoma invading the upper aerodigestive system

Well-differentiated thyroid carcinoma infrequently invades the upper aerodigestive tract. However, when invasion occurs it is the source of significant morbidity and excess mortality. The most common structures invaded by thyroid carcinoma are the recurrent laryngeal nerves, larynx, pharynx, and esophagus, which can produce symptoms of airway insufficiency, dysphagia, and hemoptysis. Locally invasive thyroid carcinoma can often be successfully treated while preserving function of the upper airway. If the tumor involves only the wall of the larynx or trachea without intraluminal extension, "shaving" the tumor from the trachea or larynx will produce local control rates comparable to more radical and destructive procedures. Intraluminal extension is a more serious problem that usually requires resection of a portion of the aerodigestive tract. Even in this situation, partial laryngeal or tracheal resection with preservation of function might be possible and should be used. Adjuvant therapy using radioiodine or external beam radiotherapy should be considered an integral part of any treatment plan for these tumors. These modalities will significantly reduce the rate of local recurrence and control symptomatic local disease.

Physiologic assessment of Isshiki type III thyroplasty

Isshiki type III thyroplasty is a laryngeal framework surgical procedure that lowers a patient's pitch. To objectively assess the procedure, preoperative and postoperative voice recordings, as well as electroglottography and photoglottography were performed. Jitter, shimmer, and glottographic quotients were measured to assess changes in vibratory pattern. The mean and range of frequencies in contextual speech was also determined. Analysis of the preoperative and postoperative data from two patients with over 1 year follow-up showed a decrease in frequency of vibration. Postoperatively, the vocal folds still vibrated in a regular pattern as described by the myoelastic-aerodynamic theory. There was no increase in jitter or shimmer quotient. The Isshiki type III thyroplasty appears capable of lowering fundamental frequency of speech without adversely affecting the vibratory mode of the vocal folds.

Glottographic analysis of phonation in the excised canine larynx

An excised canine larynx model of phonation was developed to assess the effect of vocal fold length and tension on glottographic waveforms. The canine larynx in an experimentally produced phonatory model vibrated in a two-mass system comparable to human voice production. The recorded glottographic waveforms for the excised canine larynx were similar to signals recorded in humans in the chest register. Vocal fold length, longitudinal vocal fold tension, glottic width, and airflow rate were varied while simultaneous measurements were made of the subglottic pressure, electroglottographic signal, photoglottographic signal, and acoustic signal. The model used is illustrated and discussed, with emphasis on the method of simulating the actions of all of the intrinsic laryngeal muscles, including the thyroarytenoid muscles. The open quotient and speed quotient, calculated from the glottographic signals, were dependent on vocal fold length and tension and glottic width. These results suggest that glottographic analysis, particularly speed quotient and open quotient, provide valuable information on vocal fold vibration during phonation, and may be important in assessing laryngoplasty procedures.

Sectional anatomy of the larynx: implications for the transcutaneous approach to endolaryngeal structures

A transcutaneous, transcricothyroid membrane approach to endolaryngeal structures is used for several techniques such as placement of electrodes for laryngeal electromyography and transcutaneous Teflon injection of the paralyzed vocal fold. The purpose of this study is to examine the sectional anatomy of the larynx with respect to the cricothyroid membrane and describe a suitable transcutaneous approach to endolaryngeal structures. Sixteen whole organ cadaveric larynges were frozen in clear gelatin to facilitate sectioning. Specimens were sectioned in the transaxial, sagittal, and coronal planes as well as 30 degrees, 45 degrees, and 60 degrees from the transaxial plane. For clinical orientation, the transaxial plane was defined as 90 degrees from the most anterior plane of the cricothyroid membrane. Sections were examined and angles and depths of penetration were measured with respect to the transcutaneous approach to endolaryngeal structures.

Intraoperative electrophysiologic monitoring of laryngeal muscle during thyroid surgery

A technique is described for intraoperative electrophysiologic monitoring of laryngeal muscles. This technique has been used to identify the laryngeal nerves during surgery for recurrent tumors of the thyroid gland, when direct visualization of the nerves is difficult or impossible. Laryngeal muscle electrical activity is monitored with endoscopically placed wire-hook electrodes inserted into the vocal folds bilaterally. Neurotonic discharges are detected when the recurrent laryngeal nerves are manipulated during surgical dissection. Precise localization of the recurrent nerves is possible using a hand-held bipolar stimulator.

Surgical treatment of invasion of the upper aerodigestive tract by well-differentiated thyroid carcinoma

Forty-eight patients with well-differentiated thyroid carcinoma invading upper aerodigestive tract structures have been described. Age at diagnosis was found to be a negative prognostic factor, and duration of disease before invasion was found to be a positive prognostic factor. Treatment with radical surgery and adjuvant therapy provided no improvement in survival over treatment with near-total (skeletonizing) excisions combined with adjuvant therapy. All patients treated with partial debulking procedures, with or without tracheotomy, died from disease. We believe that partial resection of upper aerodigestive tract structures without sacrifice of voice, normal breathing, or swallowing should be considered in patients with well-differentiated thyroid carcinoma.

Exercise-induced reversal of age-related declines of oxidative reactions, mitochondrial yield, and flavins in skeletal muscle of the rat

The ability of gastrocnemius muscle homogenates to catalyze the oxidation of succinate, glutamate + malate, pyruvate + malate, palmitoyl-coenzyme A, decanoylcarnitine and palmitoylcarnitine in the presence of ADP decreased by approximately 32% in sedentary male Sprague-Dawley rats between the ages of 9 and 25 months. Following 21 weeks of treadmill training (running), such homogenates from 25-month-old animals catalyzed oxidations 55% more rapidly than those from 25-month-old sedentary rats, and 17% faster than those from 9-month-old sedentary rats. Total and peptide-bound flavin of gastrocnemius muscles also declined between 9 and 25 months of age and were elevated in the 25-month-old endurance trained rats to levels greater than both 9- and 25-month-old sedentary animals. The yield of protein in the mitochondrial fraction from the quadriceps femoris muscle decreased between 9 and 25 months and was restored to the 9-month level by endurance training. The kinetic characteristics of the isolated mitochondria were not influenced by age or exercise. These data indicate that 2-year-old rats retain the capacity to increase skeletal muscle oxidative capacity and mitochondrial population density in response to endurance training.

On the Aanderaa-Rosenberg Conjecture

In a recent paper [1], Rosenberg conjectures that the results found in Holt and Reingold [2], can be generalized. Suppose that graphs are presented via their adjacency matrices. Then Holt and Reingold show that any algorithm which detects whether or not a graph is strongly connected (respectively, contains a cycle) must in worst case probe 0(n 2 ) entries of the given n x n adjacency matrix. Rosenberg then considers restrictions on graph property P such that any algorithm takes in worst case 0(n 2 ) probes to determine whether or not a n-node graph has property P.