Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 6 of 6 for “"Circuit lower bounds"”.
-
Connections between circuit analysis problems and circuit lower bounds
A circuit analysis problem takes a Boolean function f as input (where f is represented either as a logical circuit, or as a truth table) and determines some interesting property of f. Examples of circuit analysis problems include Circuit Satisfiability, Circuit Composition, and the Minimum Size …
-
Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds
… and connections between algorithms and circuit lower bounds. We give new results in the following three areas: Oracles and Algorithmic Methods for Proving Lower Bounds: We give an equivalence between relativizing circuit lower bounds (circuit lower bounds which hold with respect to all …
-
Better Hardness via Algorithms, and New Forms of Hardness versus Randomness
… we know certain hardness hypothesis (circuit lower bounds) implies that all randomized algorithms can be derandomized with a polynomial overhead. In another direction, A decade ago, Williams have proved that certain circuit lower bounds follows from non-trivial derandomization. In this …
-
Algebraic dependence testing in the perspective of algebraic matroids
… polynomial identity testing and algebraic circuit lower bounds. We present previous works on this topic including Perron's bound on the annihilating polynomial and the Jacobian criterion. By Perron's bound, there is a brute-force algorithm that solves for the annihilating polynomial in …
-
Intractability Results for some Computational Problems
… as given by Khot. Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching: A monotone Boolean circuit is said to be multilinear if for any AND gate in the circuit, the minimal representation of the two input functions to the gate do not have any variable in common. We show that …
-
The complexity of joint computation
… several computational models: query algorithms, circuits, and Turing machines. We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; …