We give a nontrivial algorithm for the satisfiability problem for threshold circuits of depth two with a linear number of wires which improves over exhaustive search by an exponential factor. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. Our result generalizes to formulas of arbitrary constant depth. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most linear in the number of variables. One of our motivations is proving strong lower bounds for TC0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where n is the number of variables and cn is the number of constraints. The key idea for the algorithm is a reduction to the Vector Domination problem and a new algorithm for that subproblem.

Background

Few HIV antiretroviral adherence interventions target patients before they start treatment, assess adherence readiness to determine the timing of treatment initiation, or tailor the amount of adherence support. The Supporting Treatment Adherence Readiness through Training (START) intervention, based on the information-motivation-behavioral skills model of behavior change, is designed to address these gaps with the inclusion of (1) brief pill-taking practice trials for enhancing pretreatment adherence counseling and providing a behavioral criterion for determining adherence readiness and the timing of treatment initiation and (2) a performance-driven dose regulation mechanism to tailor the amount of counseling to the individual needs of the patient and conserve resources. The primary aim of this randomized controlled trial is to examine the effects of START on antiretroviral adherence and HIV virologic suppression.

Methods/design

A sample of 240 patients will be randomized to receive START or usual care at one of two HIV clinics. Primary outcomes will be optimal dose-taking adherence (>85 % prescribed doses taken), as measured with electronic monitoring caps, and undetectable HIV viral load. Secondary outcomes will include dose-timing adherence (>85 % prescribed doses taken on time) and CD4 count. Primary endpoints will be month 6 (short-term effect) and month 24 (to test durability of effect), though electronic monitoring will be continuous and a fully battery of assessments will be administered every 6 months for 24 months.

Discussion

If efficacious and cost-effective, START will provide clinicians with a model for assessing patient adherence readiness and helping patients to achieve and sustain readiness and optimal treatment benefits.

Trial registration

ClinicalTrials.gov identifier NCT02329782 . Registered on 22 December 2014.