All reports by Author Andrzej Lingas:

__
TR22-085
| 8th June 2022
__

Andrzej Lingas#### A Note on Lower Bounds for Monotone Multilinear Boolean Circuits

__
TR18-154
| 7th September 2018
__

Stasys Jukna, Andrzej Lingas#### Lower Bounds for Circuits of Bounded Negation Width

__
TR18-108
| 1st June 2018
__

Andrzej Lingas#### Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth

__
TR14-039
| 28th March 2014
__

Andrzej Lingas#### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-)

Revisions: 1

__
TR13-139
| 7th October 2013
__

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu#### Detecting Monomials with $k$ Distinct Variables

__
TR12-176
| 14th December 2012
__

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu#### Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

__
TR06-115
| 26th July 2006
__

Artur Czumaj, Andrzej Lingas#### Finding a Heaviest Triangle is not Harder than Matrix Multiplication

__
TR06-111
| 18th July 2006
__

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas#### Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Revisions: 2

__
TR04-039
| 21st April 2004
__

Andrzej Lingas, Martin WahlĂ©n#### On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

__
TR00-064
| 29th August 2000
__

Klaus Jansen, Marek Karpinski, Andrzej Lingas#### A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

__
TR00-051
| 14th July 2000
__

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas#### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

Andrzej Lingas

A monotone Boolean circuit is a restriction of a Boolean circuit

allowing for the use of disjunctions, conjunctions, the Boolean

constants, and the input variables. A monotone Boolean circuit is

multilinear if for any AND gate the two input functions have no

variable in common. We ...
more >>>

Stasys Jukna, Andrzej Lingas

We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the ``amount of negation'' in such circuits, we introduce the concept of their ``negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely ... more >>>

Andrzej Lingas

We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., ... more >>>

Andrzej Lingas

We observe that if we allow for the use of

division and the floor function

besides multiplication, addition and

subtraction then we can

compute the arithmetic convolution

of two n-dimensional integer vectors in O(n) steps and

perform the arithmetic matrix multiplication

of two integer n times n matrices ...
more >>>

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

We study the complexity of detecting monomials

with special properties in the sum-product

expansion of a polynomial represented by an arithmetic

circuit of size polynomial in the number of input

variables and using only multiplication and addition.

We focus on monomial properties expressed in terms

of the number of distinct ...
more >>>

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>>

Artur Czumaj, Andrzej Lingas

We show that for any $\epsilon > 0$, a maximum-weight triangle in an

undirected graph with $n$ vertices and real weights assigned to

vertices can be found in time $\O(n^{\omega} + n^{2 + \epsilon})$,

where $\omega $ is the exponent of fastest matrix multiplication

algorithm. By the currently best bound ...
more >>>

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

We present two new methods for finding a lowest common ancestor (LCA)

for each pair of vertices of a directed acyclic graph (dag) on

n vertices and m edges.

The first method is a natural approach that solves the all-pairs LCA

problem for the input dag in time O(nm).

The ... more >>>

Andrzej Lingas, Martin WahlĂ©n

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

Klaus Jansen, Marek Karpinski, Andrzej Lingas

The Max-Bisection and Min-Bisection are the problems of finding

partitions of the vertices of a given graph into two equal size subsets so as

to maximize or minimize, respectively, the number of edges with exactly one

endpoint in each subset.

In this paper we design the first ...
more >>>

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

The max-bisection problem is to find a partition of the vertices of a

graph into two equal size subsets that maximizes the number of edges with

endpoints in both subsets.

We obtain new improved approximation ratios for the max-bisection problem on

the low degree $k$-regular graphs for ...
more >>>