The following pages link to Michal Koucký (Q343854):
Displaying 50 items.
- Towards a reverse Newman's theorem in interactive information complexity (Q343858) (← links)
- Book review of: Oded Goldreich, Computational complexity: a conceptual perspective (Q458505) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\) (Q626674) (← links)
- Incremental branching programs (Q929291) (← links)
- Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)). (Q1401264) (← links)
- Catalytic space: non-determinism and hierarchy (Q1702851) (← links)
- Universal traversal sequences with backtracking. (Q1872734) (← links)
- Stronger lower bounds for online ORAM (Q2175940) (← links)
- Expander construction in \(\mathrm{VNC}^1\) (Q2187260) (← links)
- Does the polynomial hierarchy collapse if onto functions are invertible? (Q2268347) (← links)
- Simulation theorems via pseudo-random properties (Q2281252) (← links)
- What can be efficiently reduced to the Kolmogorov-random strings? (Q2576937) (← links)
- High entropy random selection protocols (Q2659776) (← links)
- The Big Match in Small Space (Q2819448) (← links)
- On Online Labeling with Polynomially Many Labels (Q2912834) (← links)
- The Hardness of Being Private (Q2943893) (← links)
- A New Approach to the Sensitivity Conjecture (Q2989036) (← links)
- Lower bounds for combinatorial algorithms for Boolean matrix multiplication (Q3304119) (← links)
- Incremental Branching Programs (Q3434693) (← links)
- Tight Lower Bounds for the Online Labeling Problem (Q3457193) (← links)
- Inverting Onto Functions and Polynomial Hierarchy (Q3499770) (← links)
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) (Q3521913) (← links)
- Amplifying lower bounds by means of self-reducibility (Q3578198) (← links)
- Bounded-depth circuits (Q3581426) (← links)
- Languages with Bounded Multiparty Communication Complexity (Q3590958) (← links)
- High Entropy Random Selection Protocols (Q3603478) (← links)
- (Q4551339) (← links)
- Cover time and mixing time of random walks on dynamic graphs (Q4584911) (← links)
- (Q4601876) (← links)
- Lower Bounds for Elimination via Weak Regularity (Q4636619) (← links)
- Expander Construction in VNC1 (Q4638081) (← links)
- (Q4967204) (← links)
- Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity (Q5009569) (← links)
- (Q5028438) (← links)
- Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time (Q5056449) (← links)
- Improved Bounds on Fourier Entropy and Min-entropy (Q5066141) (← links)
- (Q5072476) (← links)
- Constant factor approximations to edit distance on far input pairs in nearly linear time (Q5144955) (← links)
- Many Random Walks Are Faster Than One (Q5199503) (← links)
- Simulation beats richness: new data-structure lower bounds (Q5230358) (← links)
- On Online Labeling with Large Label Set (Q5232147) (← links)
- Computing with a full memory (Q5259622) (← links)
- STACS 2004 (Q5309733) (← links)
- On Randomized Online Labeling with Polynomially Many Labels (Q5326569) (← links)
- Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates (Q5346309) (← links)
- Streaming algorithms for embedding and computing edit distance in the low distance regime (Q5361873) (← links)
- (Q5368900) (← links)
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates (Q5415496) (← links)
- Tight lower bounds for the online labeling problem (Q5415544) (← links)
