Publication | Date of Publication | Type |
---|
Tropical Circuit Complexity | 2024-01-09 | Paper |
Coin Flipping in Dynamic Programming Is Almost Useless | 2022-12-05 | Paper |
https://portal.mardi4nfdi.de/entity/Q5090491 | 2022-07-18 | Paper |
Lower bounds for Boolean circuits of bounded negation width | 2022-06-13 | Paper |
Notes on Hazard-Free Circuits | 2021-04-28 | Paper |
Tropical Kirchhoff's formula and postoptimality in matroid optimization | 2020-12-29 | Paper |
Sorting can exponentially speed up pure dynamic programming | 2020-08-04 | Paper |
Approximation Limitations of Pure Dynamic Programming | 2020-02-20 | Paper |
Incremental versus non-incremental dynamic programming | 2019-06-11 | Paper |
Coin Flipping Cannot Shorten Arithmetic Computations | 2019-05-14 | Paper |
Greedy can beat pure dynamic programming | 2018-12-05 | Paper |
Minkowski Complexity of Sets: An Easy Lower Bound | 2018-07-13 | Paper |
Some bounds on multiparty communication complexity of pointer jumping | 2017-11-16 | Paper |
Limitations of incremental dynamic programming | 2017-03-27 | Paper |
Tropical Complexity, Sidon Sets, and Dynamic Programming | 2016-11-11 | Paper |
Lower bounds for monotone counting circuits | 2016-09-12 | Paper |
On the optimality of Bellman-Ford-Moore shortest path algorithm | 2016-04-13 | Paper |
Computational Complexity of Graphs | 2016-01-14 | Paper |
Lower bounds for tropical circuits and dynamic programs | 2015-09-04 | Paper |
Clique problem, cutting plane proofs and communication complexity | 2012-10-23 | Paper |
Cutting planes cannot approximate some integer programs | 2012-09-18 | Paper |
Min-rank conjecture for log-depth circuits | 2012-01-11 | Paper |
Yet harder knapsack problems | 2012-01-09 | Paper |
Boolean function complexity. Advances and frontiers. | 2011-10-26 | Paper |
Extremal Combinatorics | 2010-12-14 | Paper |
A nondeterministic space-time tradeoff for linear codes | 2010-06-16 | Paper |
Entropy of operators or why matrix multiplication is hard for depth-two circuits | 2010-05-10 | Paper |
On convex complexity measures | 2010-04-15 | Paper |
On the P versus NP intersected with co-NP question in communication complexity | 2009-12-18 | Paper |
Representing \((0,1)\)-matrices by Boolean circuits | 2009-12-15 | Paper |
On the minimum number of negations leading to super-polynomial savings | 2009-07-09 | Paper |
On covering graphs by complete bipartite subgraphs | 2009-06-23 | Paper |
On set intersection representations of graphs | 2009-06-16 | Paper |
Expanders and time-restricted branching programs | 2009-01-08 | Paper |
Very large cliques are easy to detect | 2008-07-11 | Paper |
https://portal.mardi4nfdi.de/entity/Q5427806 | 2007-11-27 | Paper |
On Graph Complexity | 2007-02-07 | Paper |
Disproving the Single Level Conjecture | 2006-06-01 | Paper |
On multi-partition communication complexity | 2004-11-12 | Paper |
https://portal.mardi4nfdi.de/entity/Q4471998 | 2004-08-03 | Paper |
On uncertainty versus size in branching programs. | 2003-08-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q4792910 | 2003-06-26 | Paper |
Linear codes are hard for oblivious read-once parity branching programs | 2002-07-25 | Paper |
https://portal.mardi4nfdi.de/entity/Q2762506 | 2002-01-09 | Paper |
Combinatorics of monotone computations | 2001-04-01 | Paper |
On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs | 2000-11-20 | Paper |
https://portal.mardi4nfdi.de/entity/Q4699308 | 1999-11-10 | Paper |
https://portal.mardi4nfdi.de/entity/Q4266528 | 1999-10-03 | Paper |
https://portal.mardi4nfdi.de/entity/Q4255576 | 1999-08-17 | Paper |
Some bounds on multiparty communication complexity of pointer jumping | 1999-05-18 | Paper |
Neither reading few bits twice nor reading illegally helps much | 1998-08-20 | Paper |
A note on read-$k$ times branching programs | 1998-06-11 | Paper |
https://portal.mardi4nfdi.de/entity/Q4375792 | 1998-02-08 | Paper |
Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates | 1997-02-28 | Paper |
Top-down lower bounds for depth-three circuits | 1996-01-07 | Paper |
https://portal.mardi4nfdi.de/entity/Q3496294 | 1990-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3352967 | 1989-01-01 | Paper |
Entropy of contact circuits and lower bounds on their complexity | 1988-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3033329 | 1988-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3795613 | 1988-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3783567 | 1987-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3801064 | 1987-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3801065 | 1987-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3735698 | 1986-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3735699 | 1986-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3751515 | 1986-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3754637 | 1985-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3682473 | 1983-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3662621 | 1982-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3663285 | 1982-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3036681 | 1981-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q4744315 | 1981-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3048204 | 1979-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3888519 | 1979-01-01 | Paper |