Search for: All records

Two fundamental problems on directed graphs are to decide s-t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s-t connectivity running in polynomial time and no(1) space, and no known algorithm for estimating the n-step random walk matrix running in non-deterministic logspace. We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms A1 and A2 such that for every graph G, either: A1(G) outputs the transitive closure of G in polynomial time and polylogarithmic space. A2(G) outputs an approximation of the n-step random walk matrix of G in non-deterministic logspace. As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch’s theorem can be non-trivially sped up, or randomized space can be almost completely derandomized. We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron–Pyne–Tell STOC 2024, Li–Pyne–Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron–Tell CCC 2024). To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel–Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen–Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting. 

Abstract: Probabilistic polynomials over commutative rings offer a powerful way of representing Boolean functions. Although many degree lower bounds for such representations have been proved, sparsity lower bounds (counting the number of monomials in the polynomials) have not been so common. Sparsity upper bounds are of great interest for potential algorithmic applications, since sparse probabilistic polynomials are the key technical tool behind the best known algorithms for many core problems, including dense All-Pairs Shortest Paths, and the existence of sparser polynomials would lead to breakthrough algorithms for these problems. In this paper, we prove several strong lower bounds on the sparsity of probabilistic and approximate polynomials computing Boolean functions when 0 means "false". Our main result is that the AND of n ORs of c log n variables requires probabilistic polynomials (over any commutative ring which isn't too large) of sparsity n^Ω(log c) to achieve even 1/4 error. The lower bound is tight, and it rules out a large class of polynomial-method approaches for refuting the APSP and SETH conjectures via matrix multiplication. Our other results include: - Every probabilistic polynomial (over a commutative ring) for the disjointness function on two n-bit vectors requires exponential sparsity in order to achieve exponentially low error. - A generic lower bound that any function requiring probabilistic polynomials of degree d must require probabilistic polynomials of sparsity Ω(2^d). - Building on earlier work, we consider the probabilistic rank of Boolean functions which generalizes the notion of sparsity for probabilistic polynomials, and prove separations of probabilistic rank and probabilistic sparsity. Some of our results and lemmas are basis independent. For example, over any basis {a,b} for true and false where a ≠ b, and any commutative ring R, the AND function on n variables has no probabilistic R-polynomial with 2^o(n) sparsity, o(n) degree, and 1/2^o(n) error simultaneously. This AND lower bound is our main technical lemma used in the above lower bounds. 

Abstract Health risks affiliated with exposure to a wide variety of toxic gases and vapors are a certainty for first responders such as firefighters and HAZMAT team members but also for countless other professions from water purification and chemical manufacturing to the oil and gas industry, among others, and even the general public. Here the fabrication and testing of several prototypes for a novel toxic gas sensor platform based on ink‐jet printed nematic liquid crystal patterns are described. These sensors require zero power to operate and are characterized by high sensitivity down to highly relevant ppm and ppb levels, fast response times on the order of seconds, improved durability, and an overall design that is highly customizable by the potential end user. The response times of these sensors exponentially decrease with toxic gas concentration, thereby establishing the toxic gas diffusivity dependence of their mode of action. Such prototypes for two particular toxic gases, chlorine, and phosgene, performing interference testing in high humidity and smoke conditions as well as field testing with active firefighters are demonstrated. 

We conducted a comprehensive, systematic review and meta-analysis on the effects of the BSCS 5E Instructional Model—and its related variants—on science, math, and motivation outcomes. The 5E Instructional Model is a framework for delivering STEM instruction that is based on constructivist learning theory; it has been used throughout the U.S. and other countries, particularly in Turkey. Despite its wide usage, no comprehensive systematic review and meta-analysis on the effects of 5E and related models has yet been conducted. Our search and screening procedures yielded 61 randomized controlled trial studies, estimating 156 effect sizes; 70% of studies met WWC standards with or without reservations. We found that the 5E instructional model resulted in improved science outcomes ( g = 0.82, 95% CI [0.67, 0.97]), but a large amount of heterogeneity requires some caution ( t = 0.56). We explored numerous explanations for the effect heterogeneity and provided practical recommendations. 

For a complexity class $$C$$ and language $$L$$, a constructive separation of $$L\notin C$$ gives an efficient algorithm (also called a refuter) to findcounterexamples (bad inputs) for every $$C$$-algorithm attempting to decide $$L$$.We study the questions: Which lower bounds can be made constructive? What arethe consequences of constructive separations? We build a case thatconstructiveness serves as a dividing line between many weak lower bounds weknow how to prove, and strong lower bounds against $$P$$, $ZPP$, and $BPP$. Putanother way, constructiveness is the opposite of a complexity barrier: it is aproperty we want lower bounds to have. Our results fall into three broadcategories. 1. Our first set of results shows that, for many well-known lower boundsagainst streaming algorithms, one-tape Turing machines, and query complexity,as well as lower bounds for the Minimum Circuit Size Problem, making theselower bounds constructive would imply breakthrough separations ranging from$$EXP \neq BPP$$ to even $$P \neq NP$$. 2. Our second set of results shows that for most major open problems in lowerbounds against $$P$$, $ZPP$, and $BPP$, including $$P \neq NP$$, $$P \neq PSPACE$$,$$P \neq PP$$, $$ZPP \neq EXP$$, and $$BPP \neq NEXP$$, any proof of the separationwould further imply a constructive separation. Our results generalize earlierresults for $$P \neq NP$$ [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and $$BPP\neq NEXP$$ [Dolev, Fandina and Gutfreund, CIAC 2013]. 3. Our third set of results shows that certain complexity separations cannotbe made constructive. We observe that for all super-polynomially growingfunctions $$t$$, there are no constructive separations for detecting high$$t$$-time Kolmogorov complexity (a task which is known to be not in $$P$$) fromany complexity class, unconditionally.