scientific article; zbMATH DE number 7559051
From MaRDI portal
Publication:5090378
DOI10.4230/LIPIcs.ITCS.2019.8MaRDI QIDQ5090378
Swapnam Bajpai, Srikanth Srinivasan, Nutan Limaye, V. Krishan, Deepanshu Kush
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1809.05932
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
SATpolynomial threshold functionslinear decision treesconstant-depth Boolean circuitszero-error randomized algorithms
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Improving exhaustive search implies superpolynomial lower bounds
- On Improved Degree Lower Bounds for Polynomial Approximation.
- The Chow Parameters Problem
- Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
- An improved exponential-time algorithm for k -SAT
- Log Depth Circuits for Division and Related Problems
- Size--Depth Tradeoffs for Threshold Circuits
- Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
- Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
- New algorithms and lower bounds for circuits with linear threshold gates
- A polynomial restriction lemma with applications
- Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
- Analysis of Boolean Functions
- Faster all-pairs shortest paths via circuit complexity
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Automata, Languages and Programming
This page was built for publication:
