| Publication | Date of Publication | Type |
|---|
Notes on Boolean read-k and multilinear circuits
Discrete Applied Mathematics | 2024-12-04 | Paper |
Tropical Circuit Complexity
SpringerBriefs in Mathematics | 2024-01-09 | Paper |
Coin flipping in dynamic programming is almost useless
ACM Transactions on Computation Theory | 2022-12-05 | Paper |
| Lower Bounds for DeMorgan Circuits of Bounded Negation Width | 2022-07-18 | Paper |
Lower bounds for Boolean circuits of bounded negation width
Journal of Computer and System Sciences | 2022-06-13 | Paper |
Notes on hazard-free circuits
SIAM Journal on Discrete Mathematics | 2021-04-28 | Paper |
Tropical Kirchhoff's formula and postoptimality in matroid optimization
Discrete Applied Mathematics | 2020-12-29 | Paper |
Sorting can exponentially speed up pure dynamic programming
Information Processing Letters | 2020-08-04 | Paper |
Approximation limitations of pure dynamic programming
SIAM Journal on Computing | 2020-02-20 | Paper |
Incremental versus non-incremental dynamic programming
Operations Research Letters | 2019-06-11 | Paper |
Coin Flipping Cannot Shorten Arithmetic Computations
The American Mathematical Monthly | 2019-05-14 | Paper |
Greedy can beat pure dynamic programming
Information Processing Letters | 2018-12-05 | Paper |
Minkowski complexity of sets: an easy lower bound
The American Mathematical Monthly | 2018-07-13 | Paper |
Some bounds on multiparty communication complexity of pointer jumping
STACS 96 | 2017-11-16 | Paper |
Limitations of incremental dynamic programming
Algorithmica | 2017-03-27 | Paper |
Tropical complexity, Sidon sets, and dynamic programming
SIAM Journal on Discrete Mathematics | 2016-11-11 | Paper |
Lower bounds for monotone counting circuits
Discrete Applied Mathematics | 2016-09-12 | Paper |
On the optimality of Bellman-Ford-Moore shortest path algorithm
Theoretical Computer Science | 2016-04-13 | Paper |
Computational complexity of graphs
Advances in Network Complexity | 2016-01-14 | Paper |
Lower bounds for tropical circuits and dynamic programs
Theory of Computing Systems | 2015-09-04 | Paper |
Clique problem, cutting plane proofs and communication complexity
Information Processing Letters | 2012-10-23 | Paper |
Cutting planes cannot approximate some integer programs
Operations Research Letters | 2012-09-18 | Paper |
Min-rank conjecture for log-depth circuits
Journal of Computer and System Sciences | 2012-01-11 | Paper |
Yet harder knapsack problems
Theoretical Computer Science | 2012-01-09 | Paper |
Boolean function complexity. Advances and frontiers.
Algorithms and Combinatorics | 2011-10-26 | Paper |
Extremal combinatorics. With applications in computer science
Texts in Theoretical Computer Science. An EATCS Series | 2010-12-14 | Paper |
A nondeterministic space-time tradeoff for linear codes
Information Processing Letters | 2010-06-16 | Paper |
Entropy of operators or why matrix multiplication is hard for depth-two circuits
Theory of Computing Systems | 2010-05-10 | Paper |
On convex complexity measures
Theoretical Computer Science | 2010-04-15 | Paper |
On the P versus NP intersected with co-NP question in communication complexity
Information Processing Letters | 2009-12-18 | Paper |
Representing \((0,1)\)-matrices by Boolean circuits
Discrete Mathematics | 2009-12-15 | Paper |
On the minimum number of negations leading to super-polynomial savings
Information Processing Letters | 2009-07-09 | Paper |
On covering graphs by complete bipartite subgraphs
Discrete Mathematics | 2009-06-23 | Paper |
On set intersection representations of graphs
Journal of Graph Theory | 2009-06-16 | Paper |
Expanders and time-restricted branching programs
Theoretical Computer Science | 2009-01-08 | Paper |
Very large cliques are easy to detect
Discrete Mathematics | 2008-07-11 | Paper |
| Crash course mathematics for computer scientists | 2007-11-27 | Paper |
On Graph Complexity
Combinatorics, Probability and Computing | 2007-02-07 | Paper |
Disproving the Single Level Conjecture
SIAM Journal on Computing | 2006-06-01 | Paper |
On multi-partition communication complexity
Information and Computation | 2004-11-12 | Paper |
| scientific article; zbMATH DE number 2079872 (Why is no real title available?) | 2004-08-03 | Paper |
On uncertainty versus size in branching programs.
Theoretical Computer Science | 2003-08-17 | Paper |
| scientific article; zbMATH DE number 1870232 (Why is no real title available?) | 2003-06-26 | Paper |
Linear codes are hard for oblivious read-once parity branching programs
Information Processing Letters | 2002-07-25 | Paper |
| scientific article; zbMATH DE number 1688365 (Why is no real title available?) | 2002-01-09 | Paper |
Combinatorics of monotone computations
Combinatorica | 2001-04-01 | Paper |
On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
Computational Complexity | 2000-11-20 | Paper |
| scientific article; zbMATH DE number 1361490 (Why is no real title available?) | 1999-11-10 | Paper |
| scientific article; zbMATH DE number 1346504 (Why is no real title available?) | 1999-10-03 | Paper |
| scientific article; zbMATH DE number 1324671 (Why is no real title available?) | 1999-08-17 | Paper |
Some bounds on multiparty communication complexity of pointer jumping
Computational Complexity | 1999-05-18 | Paper |
Neither reading few bits twice nor reading illegally helps much
Discrete Applied Mathematics | 1998-08-20 | Paper |
A note on read-k times branching programs
RAIRO - Theoretical Informatics and Applications | 1998-06-11 | Paper |
| scientific article; zbMATH DE number 1114023 (Why is no real title available?) | 1998-02-08 | Paper |
Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
Information Processing Letters | 1997-02-28 | Paper |
Top-down lower bounds for depth-three circuits
Computational Complexity | 1996-01-07 | Paper |
| scientific article; zbMATH DE number 4170847 (Why is no real title available?) | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4204283 (Why is no real title available?) | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4131667 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4061152 (Why is no real title available?) | 1988-01-01 | Paper |
Entropy of contact circuits and lower bounds on their complexity
Theoretical Computer Science | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4068271 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4068270 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4047114 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 3968574 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3968573 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3987204 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 4002123 (Why is no real title available?) | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3904571 (Why is no real title available?) | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3814977 (Why is no real title available?) | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3815629 (Why is no real title available?) | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3831274 (Why is no real title available?) | 1981-01-01 | Paper |
| scientific article; zbMATH DE number 3799717 (Why is no real title available?) | 1981-01-01 | Paper |
| scientific article; zbMATH DE number 3642675 (Why is no real title available?) | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3694574 (Why is no real title available?) | 1979-01-01 | Paper |
